Power and stability in connectivity games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Power and stability in connectivity games

Full text

Pdf (341 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2 table of contents

Estoril, Portugal

SESSION: Economic paradigms table of contents

Pages 999-1006

Year of Publication: 2008

ISBN:978-0-9817381-1-6

Authors

Yoram Bachrach	The Hebrew University of Jerusalem, Israel
Jeffrey S. Rosenschein	The Hebrew University of Jerusalem, Israel
Ely Porat	Bar-Ilan University, Ramat-Gan, Israel

Sponsors

AAAI : Association for the Advancement of Artifical Intelligence
ACM: Association for Computing Machinery

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 52, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

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

ABSTRACT

We consider computational aspects of a game theoretic approach to network reliability. Consider a network where failure of one node may disrupt communication between two other nodes. We model this network as a simple coalitional game, called the vertex Connectivity Game (CG). In this game, each agent owns a vertex, and controls all the edges going to and from that vertex. A coalition of agents wins if it fully connects a certain subset of vertices in the graph, called the primary vertices.

We show that power indices, which express an agent's ability to affect the outcome of the vertex connectivity game, can be used to identify significant possible points of failure in the communication network, and can thus be used to increase network reliability. We show that in general graphs, calculating the Banzhaf power index is #P-complete, but suggest a polynomial algorithm for calculating this index in trees. We also show a polynomial algorithm for computing the core of a CG, which allows a stable division of payments to coalition agents.

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	Yoram Bachrach , Jeffrey S. Rosenschein, Computing the Banzhaf power index in network flow games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329433]
	2	J. F. Banzhaf. Weighted voting doesn't work: a mathematical analysis. Rutgers Law Review, 19:317--343, 1965.
	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	P. Dubey and L. Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99--131, 1979.
	5	E. Elkind, L. A. Goldberg, P. W. Goldberg, and M. Wooldridge. Computational complexity of weighted threshold games. In The National Conference on Artificial Intelligence, pages 718--723, 2007.
	6	Joan Feigenbaum , Christos H. Papadimitriou , Scott Shenker, Sharing the cost of multicast transmissions, Journal of Computer and System Sciences, v.63 n.1, p.21-41, August 2001 [doi>10.1006/jcss.2001.1754]
	7	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	8	D. B. Gillies. Some theorems on n-person games. PhD thesis, Princeton University, 1953.
	9	A. Laruelle. On the choice of a power index. Papers 99-10, Valencia --- Instituto de Investigaciones Economicas, 1999.
	10	D. Leech. Voting power in the governance of the International Monetary Fund. Annals of Operations Research, 109(1--4):375--397, 2002.
	11	M. Machover and D. S. Felsenthal. The treaty of Nice and qualified majority voting. Social Choice and Welfare, 18(3):431--464, 2001.
	12	I. Mann and L. S. Shapley. Values of large games, IV: Evaluating the electoral college by Monte-Carlo techniques. Technical report, The Rand Corporation, Santa Monica, CA, 1960.
	13	Y. Matsui and T. Matsui. A survey of algorithms for calculating power indices of weighted majority games. Journal of the Operations Research Society of Japan, 43, 2000.
	14	Yasuko Matsui , Tomomi Matsui, NP-completeness for calculating power indices of weighted majority games, Theoretical Computer Science, v.263 n.1-2, p.306-310, July 28 2001
	15	J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing, 12(4):777--788, 1983.
	16	L. S. Shapley. A value for n-person games. Contributions to the Theory of Games, pages 31--40, 1953.
	17	L. S. Shapley and M. Shubik. A method for evaluating the distribution of power in a committee system. American Political Science Review, 48:787--792, 1954.
	18	P. Straffin. Homogeneity, independence and power indices. Public Choice, 30:107--118, 1977.
	19	Salil P. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, SIAM Journal on Computing, v.31 n.2, p.398-427, 2001 [doi>10.1137/S0097539797321602]
	20	L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8:410--421, 1979.
	21	M. Yokoo, V. Conitzer, T. Sandholm, N. Ohta, and A. Iwasaki. Coalitional games in open anonymous environments. In The 20th National Conference on Artificial Intelligence, pages 509--514, 2005.