Boolean combinations of weighted voting games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Boolean combinations of weighted voting games

Full text

Pdf (262 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 1 table of contents

Budapest, Hungary

SESSION: Economic approaches/auctions/mechanism design table of contents

Pages 185-192

Year of Publication: 2009

ISBN:978-0-9817381-6-1

Authors

Piotr Faliszewski	AGH Univ. of Science and Technology, Kraków, Poland
Edith Elkind	Univ. of Southampton, UK/Nanyang Technological University, Singapore
Michael Wooldridge	Univ. of Liverpool, Liverpool, United Kingdom

Sponsors

: The Foundation for Intelligent Physical Agents
Microsoft Research : Microsoft Research
: Wiley - Blackwell Ltd
: Whitestein Technologies
: European Office of Aerospace Research and Development, Air Force Office of Scientific Research, United States Air Force Research Laboratory
: Drexel University

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 36, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Weighted voting games are a natural and practically important class of simple coalitional games, in which each agent is assigned a numeric weight, and a coalition is deemed to be winning if the sum of weights of agents in that coalition meets some stated threshold. We study a natural generalisation of weighted voting games called Boolean Weighted Voting Games (BWVGs). BWVGs are intended to model decision-making processes in which components of an overall decision are delegated to committees, with each committee being an individual weighted voting game. We consider the perspective of an individual who has some overall goal that they desire to achieve, represented as a propositional logic formula over the decisions controlled by the various committees. We begin by formulating the framework of BWVGs, and show that BWVGs can provide a succinct representation scheme for simple coalitional games, compared to other representations based on weighted voting games. We then consider the computational complexity of problems such as determining the power of a particular player with respect to some goal, and investigate how the power of a player with respect to the overall goal is related to the power of that player in individual games. We show trade-offs between the complexity of these problems, the nature of underlying Boolean formulas used, and representations of weights (binary versus unary) in our games.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Vincent Conitzer , Tuomas Sandholm, Complexity of constructing solutions in the core based on synergies among coalitions, Artificial Intelligence, v.170 n.6, p.607-619, May 2006 [doi>10.1016/j.artint.2006.01.005]
	2	Vincent Conitzer , Tuomas Sandholm , Jérôme Lang, When are elections with few candidates hard to manipulate?, Journal of the ACM (JACM), v.54 n.3, p.14-es, June 2007 [doi>10.1145/1236457.1236461]
	3	Xiaotie Deng , Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Mathematics of Operations Research, v.19 n.2, p.257-266, May 1994 [doi>10.1287/moor.19.2.257]
	4	E. Elkind, L. Goldberg, P. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In Proc. AAAI-2007s, 2007.
	5	E. Elkind, L. Goldberg, P. Goldberg, and M. Wooldridge. On the dimensionality of voting games. In Proc. AAAI-2008, 2008.
	6	U. Endriss and J. Lang, editors. Proc. COMSOC-2006. 2006.
	7	Piotr Faliszewski , Lane A. Hemaspaandra, The Complexity of Power-Index Comparison, Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management, p.177-187, June 23-25, 2008, Shanghai, China [doi>10.1007/978-3-540-68880-8_18]
	8	M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman, 1979.
	9	Paul Harrenstein , Wiebe van der Hoek , John-Jules Meyer , Cees Witteveen, Boolean games, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	10	Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , Richard E. Stearns, The Complexity of Planar Counting Problems, SIAM Journal on Computing, v.27 n.4, p.1142-1167, Aug. 1998 [doi>10.1137/S0097539793304601]
	11	Samuel Ieong , Yoav Shoham, Marginal contribution nets: a compact representation scheme for coalitional games, Proceedings of the 6th ACM conference on Electronic commerce, p.193-202, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064030]
	12	C. List. Judgment aggregation: A short introduction. In Handbook of the Philosophy of Economics. Elsevier, 2008.
	13	Y. Matsui and T. Matsui. A survey of algorithms for calculating power indices of weightyed majority games. Jnl of the Oper. Res. Soc. of Japan, 43:71--86, 2000.
	14	S. Muroga. Threshold Logic and its Applications. Wiley, 1971.
	15	M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
	16	C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
	17	A. Taylor and W. Zwicker. Weighted voting, multicameral representation, and power. Games&Econ. Beh., 5:170--181, 1993.
	18	A. D. Taylor and W. S. Zwicker. Simple Games. Princeton University Press, 1999.