skip to main content
10.5555/1496770.1496850guideproceedingsArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
research-article
Free access

Improved equilibria via public service advertising

Published: 04 January 2009 Publication History

Abstract

Many natural games have both high and low cost Nash equilibria: their Price of Anarchy is high and yet their Price of Stability is low. In such cases, one could hope to move behavior from a high cost equilibrium to a low cost one by a "public service advertising campaign" encouraging players to follow the low-cost equilibrium, and if every player follows the advice then we are done. However, the assumption that everyone follows instructions is unrealistic. A more natural assumption is that some players will follow them, while other players will not. In this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. Unlike the "value of altruism" model, we assume everyone will ultimately act in their own interest.
We analyze this question for several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, and party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random α fraction of the population following the given advice is sufficient to get a guarantee within an O(1/α) factor of the price of stability for any α > 0. For other games (such as party affiliation games), there is a strict threshold (in this case, α < 1/2 yields almost no benefit, yet α > 1/2 is enough to reach near-optimal behavior). Finally, for some games, such as scheduling, no value α < 1 is sufficient. We also consider a "viral marketing" model in which certain players are specifically targeted, and analyze the ability of such targeting to influence behavior using a much smaller number of targeted players.

References

[1]
A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. O(&radic;logn) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems. In Proc. 37th STOC, 2005.
[2]
S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty. On Nash equilibria for a network creation game. In Proc. 17th ACM-SIAM SODA, 2006.
[3]
N. Andelman, M. Feldman, and Y. Mansour. Strong Price of Anarchy. In Proc. 18th ACM-SIAM SODA, 2007.
[4]
E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The Price of Stability for Network Design with Fair Cost Allocation. In FOCS, 2004.
[5]
M. Charikar, H. Karloff, C. Mathieu, J. Naor, and M. Saks. Online multicast with egalitarian cost sharing. In Proc. 20th SPAA, 2008.
[6]
G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proc. 37th STOC, 2005.
[7]
G. Christodoulou, V. S. Mirrokni, and A. Sidiropoulos. Convergence and approximation in potential games. In Proc. 23rd STACS, 2006.
[8]
J. R. Correa, A. S. Schulz, and N. E. Stier-Moses. Selfish routing in capacitated networks. Mathematics of Operations Research, 29(4):236--259, 2004.
[9]
A. Czumaj and B. Voecking. Tight bounds for worst-case equilibria. In Proc. 13th ACM-SIAM SODA, 2002.
[10]
E. D. Demaine, M. T. Hajiaghayi, H. Mahini, and M. Zadimoghaddam. The price of anarchy in network creation games. In Proc. 17th SODA, 2006.
[11]
E. Even-Dar, A. Kesselman, and Y. Mansour. Convergence time to Nash equilibrium in load balancing. ACM Transactions on Algorithms, 3(3), 2007.
[12]
A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker. On a network creation game. In Proc. 22nd PODC, 2003.
[13]
D. Fotakis, S. Kontogiannis, and P. Spirakis. Selfish unsplit-table flows. Theoretical Computer Science, 348(2):226--239, 2005.
[14]
E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proc. 16th STACS, pages 404--413, 1999.
[15]
D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14:124--143, 1996.
[16]
N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, editors. Algorithmic Game Theory. Cambridge, 2007.
[17]
T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236--259, 2002.
[18]
Y. Sharma and D. P. Williamson. Stackelberg thresholds in network routing games or the value of altruism. In ACM Conference on Electronic Commerce, 2007.

Cited By

View all
  • (2016)Decentralized dynamics for finite opinion gamesTheoretical Computer Science10.1016/j.tcs.2016.08.011648:C(96-115)Online publication date: 4-Oct-2016
  • (2014)Near-Optimality in Covering Games by Exposing Global InformationACM Transactions on Economics and Computation10.1145/25978902:4(1-22)Online publication date: 28-Oct-2014
  • (2012)Decentralized Dynamics for Finite Opinion GamesProceedings of the 5th International Symposium on Algorithmic Game Theory - Volume 761510.5555/2954155.2954168(144-155)Online publication date: 22-Oct-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
SODA '09: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms
January 2009
1297 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2009

Qualifiers

  • Research-article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)15
  • Downloads (Last 6 weeks)8
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Decentralized dynamics for finite opinion gamesTheoretical Computer Science10.1016/j.tcs.2016.08.011648:C(96-115)Online publication date: 4-Oct-2016
  • (2014)Near-Optimality in Covering Games by Exposing Global InformationACM Transactions on Economics and Computation10.1145/25978902:4(1-22)Online publication date: 28-Oct-2014
  • (2012)Decentralized Dynamics for Finite Opinion GamesProceedings of the 5th International Symposium on Algorithmic Game Theory - Volume 761510.5555/2954155.2954168(144-155)Online publication date: 22-Oct-2012
  • (2011)Computing stable outcomes in hedonic games with voting-based deviationsThe 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 210.5555/2031678.2031697(559-566)Online publication date: 2-May-2011
  • (2011)Leading dynamics to good behaviorACM SIGecom Exchanges10.1145/1998549.199855310:2(19-22)Online publication date: 1-Jun-2011
  • (2010)Computing stable outcomes in hedonic gamesProceedings of the Third international conference on Algorithmic game theory10.5555/1929237.1929253(174-185)Online publication date: 18-Oct-2010
  • (2010)Approximating pure nash equilibrium in cut, party affiliation, and satisfiability gamesProceedings of the 11th ACM conference on Electronic commerce10.1145/1807342.1807353(73-82)Online publication date: 7-Jun-2010
  • (2009)On Strong Equilibria in the Max Cut GameProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_62(608-615)Online publication date: 9-Dec-2009
  • (2009)On the Power of MediatorsProceedings of the 5th International Workshop on Internet and Network Economics10.1007/978-3-642-10841-9_42(455-462)Online publication date: 9-Dec-2009

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media