On the price of mediation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the price of mediation

Full text

Pdf (508 KB)

Source

Electronic Commerce archive
Proceedings of the tenth ACM conference on Electronic commerce table of contents

Stanford, California, USA

SESSION: Session 9 table of contents

Pages 315-324

Year of Publication: 2009

ISBN:978-1-60558-458-4

Authors

Milan Bradonjic	Los Alamos National Laboratory, Los Alamos, NM, USA
Gunes Ercal-Ozkaya	Kansas University, Lawrence, KS, USA
Adam Meyerson	University of California, Los Angeles, Los Angeles, CA, USA
Alan Roytman	University of California, Los Angeles, Los Angeles, CA, USA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 23, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1566374.1566419 What is a DOI?

ABSTRACT

We study the relationship between the social cost of correlated equilibria and the social cost of Nash equilibria. In contrast to previous work focusing on the possible benefits of a benevolent mediator, we define and bound the Price of Mediation (PoM): the ratio of the cost of the worst correlated equilibrium to the cost of the worst Nash. We observe that in practice, the heuristics used for mediation are frequently non-optimal, and from an economic perspective mediators may be inept or self-interested. Recent results on computation of equilibria also motivate our work.

We consider the Price of Mediation for general games with small numbers of players and pure strategies. For games with two players each having two pure strategies we prove a tight bound of two on the PoM. For larger games (either more players, or more pure strategies per player, or both) we show that the PoM can be unbounded.

Most of our results focus on symmetric congestion games (also known as load balancing games). We show that for general convex cost functions, the PoM can grow exponentially in the number of players. We prove that PoM is one for linear costs and at most a small constant (but can be larger than one) for concave costs. For polynomial cost functions, we prove bounds on the PoM which are exponential in the degree.

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	I. Ashlagi, D. Monderer, and M. Tenneholtz. On the value of correlation. In UAI-05: Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence, 2005.
	2	R. Aumann. Subjectivity and correlation in randomization strategies. Journal of Mathematical Economics, 1:67--96, 1974.
	3	R. Aumann. Correlated equilibrium as an expression of bayesian rationality. Econometrica, 55(1):1--18, January 1987.
	4	X Chen and X. Deng. Settling the complexity of 2-player nash equilibrium. Electronic Colloquium on Computation Complexity.
	5	S.-G. Cheng, D.M. Reeves, Y. Vorobeychik, and M.P. Wellman. Notes on the equilibria in symmetric games. In International Joint Conference on Autonomous Agents and Multi Agent Systems, 6th Workshop on Game Theoretic and Decision Theoretic Agents, August 2004.
	6	Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
	7	D. Foster. Calibrated learning and correlated equilibria. Games95 Conference, 1995.
	8	Amir Jafari , Amy R. Greenwald , David Gondek , Gunes Ercal, On No-Regret Learning, Fictitious Play, and Nash Equilibrium, Proceedings of the Eighteenth International Conference on Machine Learning, p.226-233, June 28-July 01, 2001
	9	E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In STACS 1999.
	10	J. Nash. Equilbrium points in n-person games. Proceedings of the National Academy of Sciences USA, 36:48--49, 1950.
	11	Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060598]
	12	R. Peeters and J. Potters. On the structure of the set of correlated equilibria in two-by-two bimatrix games. Technical report, 1999.
	13	Tim Roughgarden, Intrinsic robustness of the price of anarchy, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA [doi>10.1145/1536414.1536485]
	14	T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000