Simple Games

by Taylor, Alan D.

• ISBN13: 9780691001203
• ISBN10: 0691001200
• Format: Hardcover
• Copyright: 1999-09-22
• Publisher: Princeton Univ Pr

Summary

Simple games are mathematical structures inspired by voting systems in which a single alternative, such as a bill, is pitted against the status quo. The first in-depth mathematical study of the subject as a coherent subfield of finite combinatorics--one with its own organized body of techniques and results--this book blends new theorems with some of the striking results from threshold logic, making all of it accessible to game theorists. Introductory material receives a fresh treatment, with an emphasis on Boolean subgames and the Rudin-Keisler order as unifying concepts. Advanced material focuses on the surprisingly wide variety of properties related to the weightedness of a game. A desirability relation orders the individuals or coalitions of a game according to their influence in the corresponding voting system. As Taylor and Zwicker show, acyclicity of such a relation approximates weightedness--the more sensitive the relation, the closer the approximation. A trade is an exchange of players among coalitions, and robustness under such trades is equivalent to weightedness of the game. Robustness under trades that fit some restrictive exchange pattern typically characterizes a wider class of simple games--for example, games for which some particular desirability order is acyclic. Finally, one can often describe these wider classes of simple games by weakening the total additivity of a weighting to obtain what is called a pseudoweighting. In providing such uniform explanations for many of the structural properties of simple games, this book showcases numerous new techniques and results.

Author Biography

Alan D. Taylor is the Marie Louise Bailey Professor of Mathematics at Union College. William S. Zwicker is Professor of Mathematics at Union College. Both have taught at Union for twenty-four years; their research has been in the areas of combinatorial set theory and applications of mathematics to political science, including social choice theory, fair division, and game theory.

Table of Contents

Preface	ix
Acknowledgments	xv
Fundamentals	3	(40)
Introduction	3	(5)
Examples	8	(6)
The Dual Game	14	(5)
The Algebra of Simple Games	19	(7)
The Two-Point Constant-Sum Extension of a Game	26	(3)
Pregames and Weighted Graphs	29	(5)
Vector-Weighted Simple Games and Dimension Theory	34	(5)
The Voting Bloc and Bicameral Meet Characterization	39	(1)
The Game behind a Simple Game	40	(3)
General Trading: Weighted Games	43	(43)
Introduction	43	(2)
Trading Transforms and Trading Matrices	45	(9)
Sequential Transfers	54	(2)
The Trading Characterization of Weighted Games	56	(7)
Pregraphs and Graphs	63	(5)
The Traditional Approaches: Systems of Linear Inequalities and Separating Hyperplanes	68	(6)
The Gabelman Examples	74	(5)
A General Framework	79	(7)
Pairwise Trading: Linear Games and Winder Games	86	(39)
Introduction	86	(1)
The Desirability Relation on Individuals and Swap Robustness	87	(5)
Shift Minimal Winning Coalitions and the Ordinal Power Structure of a Simple Game	92	(5)
A Classification Theorem for Linear Games	97	(6)
Chvatal's Conjecture	103	(7)
The PSA Pseudoweighting Characterization of Linear Games	110	(5)
The Local Weighting Characterization of Linear Games	115	(5)
Two-Trade Robustness and Winder Games	120	(2)
A Weighting Characterization of Winder Games	122	(1)
The Hereditarily Dual-Comparable Characterization of Winder Games	123	(2)
Cycle Trading: Weakly Acyclic Games and Strongly Acyclic Games	125	(53)
Introduction	125	(2)
An Impossibility Result for Coalitional Desirability Relations	127	(7)
Possibilities, and More Impossibilities, from the Weight-Induced Order	134	(5)
Lapidot's Desirability Relation on Coalitions and Weakly Acyclic Games	139	(3)
The SSA Pseudoweighting Characterization of Weakly Acyclic Games, and a Generalization	142	(3)
An Inductive Construction of SSA Pseudoweightings for Weakly Acyclic Games	145	(5)
Winder's Desirability Relation on Coalitions and Strongly Acyclic Games	150	(6)
A Pseudoweighting Characterization of Strongly Acyclic Games	156	(1)
Sequential Transfer Trading for <L and <W	157	(8)
Peleg's Question on the Weightedness of Constant-Sum Acyclic Games	165	(13)
Almost General Trading: Chow Games, Completely Acyclic Games, and Weighted Games	178	(37)
Introduction	178	(1)
Chow Games and Chow-Lapidot Parameters	179	(4)
A Gabelman-Style, Nonweighted Chow Game	183	(7)
The Trading Version of Lapidot's Desirability Relation	190	(6)
The Trading Version of Winder's Desirability Relation	196	(5)
Multiweightings	201	(4)
Weighted Games and the Weight-Induced Order	205	(10)
Appendix I: Systems of Linear Inequalities	215	(5)
Appendix II: Separating Hyperplanes	220	(3)
Appendix III: Duality and Transitivity for Binary Relations	223	(6)
References	229	(6)
Index	235