Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Inefficiency of Games with Social Context

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

The study of other-regarding player behavior such as altruism and spite in games has recently received quite some attention in the algorithmic game theory literature. Already for very simple models, it has been shown that altruistic behavior can actually be harmful for society in the sense that the price of anarchy may increase as the players become more altruistic. In this paper, we study the severity of this phenomenon for more realistic settings in which there is a complex underlying social structure, causing the players to direct their altruistic and spiteful behavior in a refined player-specific sense (depending, for example, on friendships that exist among the players). Our findings show that the increase in the price of anarchy is modest for congestion games and minsum scheduling games, whereas it might be drastic for generalized second price auctions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. To see this, note that, by dividing all α i j by α i i >0, the set of equilibria and the social cost of any outcome remain the same.

  2. More precisely, this is shown to hold for the more general case when the social cost is an arbitrary nonnegative linear combination of the player’s cost. From a scheduling game instance described in [18], it follows that this bound is tight, i.e., that the coarse correlated price of anarchy is actually exactly 4.

  3. If k<n we can add n−k dummy slots with click-through rate 0; if k>n we can remove the k−n last slots.

References

  1. Anagnostopoulos, A., Becchetti, L., de Keijzer, B., Schäfer, G.: Inefficiency of games with social context. In: Vöcking, B. (ed.) Proceedings of the 6th International Symposium on Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 8146, pp. 219–230. Springer (2013)

  2. Ashlagi, I., Krysta, P., Tennenholtz, M.: Social context games. In: Proceedings of the 4th International Workshop on Internet and Network Economics, pp. 675–683 (2008)

  3. Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th ACM Symposium on Theory of Computing, pp. 57–66 (2005)

  4. Bilò, V., Celi, A., Flammini, M., Gallotti, V.: Social context congestion games. In: Proceedings of the 18th international conference on Structural Information and Communication Complexity, pp. 282–293. Springer (2011)

  5. Bilò, V., Fanelli, A., Flammini, M., Moscardelli, L.: Graphical congestion games. Algorithmica 61(2), 274–297 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  6. Brandt, F., Sandholm, T., Shoham, Y.: Spiteful bidding in sealed-bid auctions. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence, pp. 1207–1214 (2007)

  7. Buehler, R., Goldman, Z., Liben-Nowell, D., Pei, Y., Quadri, J., Sharp, A., Taggart, S., Wexler, T., Woods, K.: The price of civil society. In: Proceedings of the 7th International Workshop on Internet and Network Economics, pp. 375–382 (2011)

  8. Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight bounds for selfish and greedy load balancing. In: Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 4051, pp. 311–322. Springer (2006)

  9. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: On the efficiency of equilibria in generalized second price auctions. In: Proceedings of the 12th ACM Conference on Electronic Commerce, pp. 81–90 (2011)

  10. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Papaioannou, E.: The impact of altruism on the efficiency of atomic congestion games. In: Proceedings of the 5th Symposium on Trustworthy Global Computing (2010)

  11. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M., Lucier, B., Leme, R.P., Tardos, É.: On the efficiency of equilibria in generalized second price auctions. CoRR 1201.6429 (2012)

  12. Chen, P.A., de Keijzer, B., Kempe, D., Schäfer, G.: The robust price of anarchy of altruistic games. In: Proceedings of the 7th International Workshop on Internet and Network Economics, pp. 383–390 (2011)

  13. Chen, P.A., de Keijzer, B., Kempe, D., Schäfer, G.: Altruism and its impact on the price of anarchy. ACM Transactions on Economics and Computation (2014, to appear)

  14. Chen, P.A., Kempe, D.: Altruism, selfishness, and spite in traffic routing. In: Proceedings of the 9th ACM Conference on Electronic Commerce, pp. 140–149 (2008)

  15. Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th ACM Symposium on the Theory of Computing, pp. 67–73 (2005)

  16. Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. Theor. Comput. Sci. 438, 13–27 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  17. Cole, R., Correa, J.R., Gkatzelis, V., Mirrokni, V., Olver, N.: Inner product spaces for minsum coordination mechanisms. In: Proceedings of the 43rd ACM Symposium on the Theory of Computing, pp. 539–548 (2011)

  18. Correa, J.R., Queyranne, M.: Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Nav. Res. Logist. 59(5), 384–395 (2012)

    Article  MathSciNet  Google Scholar 

  19. de Keijzer, B.: Externalities and Cooperation in Algorithmic Game Theory. Ph.D. thesis, Centrum voor Wiskunde en Informatica (CWI) (2014)

  20. Elias, J., Martignon, F., Avrachenkov, K., Neglia, G.: Socially-aware network design games. In: Proceedings of the 29th Conference on Computer Communications, pp. 41–45 (2010)

  21. Fehr, E., Schmidt, K.M.: The Economics of Fairness, Reciprocity and Altruism: Experimental Evidence and New Theories, Handbook on the Economics of Giving, Reciprocity and Altruism, vol. 1, chap. 8, pp. 615–691. Elsevier (2006)

  22. Fotakis, D., Gkatzelis, V., Kaporis, A.C., Spirakis, P.: The impact of social ignorance on weighted congestion games. In: Proceedings of the 5th International Workshop on Internet and Network Economics, pp. 316–327. Springer (2009)

  23. Hoefer, M., Skopalik, A.: Altruism in atomic congestion games. Trans. Econ. Comput. 1(4), 21 (2009)

    Google Scholar 

  24. Hoefer, M., Skopalik, A.: Stability and convergence in selfish scheduling with altruistic agents. In: Proceedings of the 5th International Workshop on Internet and Network Economics, pp. 616–622 (2009)

  25. Hoefer, M., Skopalik, A.: Social context in potential games. In: Proceedings of the 8th International Conference on Internet and Network Economics, pp. 364–377 (2012)

  26. Hoeksma, R., Uetz, M.: The price of anarchy for minsum related machine scheduling. In: Proceedings of the 9th International Conference on Approximation and Online Algorithms, 261–273 (2012)

  27. Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, pp. 404–413 (1999)

  28. Leme, R.P., Tardos, É.: Pure and bayes-nash price of anarchy for generalized second price auction. In: 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 735–744 (2010)

  29. Lucier, B., Leme, R.P.: GSP auctions with correlated types. In: Proceedings 12th ACM Conference on Electronic Commerce (EC), pp. 71–80 (2011)

  30. Rahn, M., Schäfer, G.: Bounding the inefficiency of altruism through social contribution games. In: Chen, Y., Immorlica, N. (eds.) Proceedings of the 9th International Conference on Web and Internet Economics (WINE), Lecture Notes in Computer Science, Vol. 8289, pp. 391–404. Springer (2013)

  31. Roughgarden, T.: The price of anarchy in games of incomplete information. In: Proceedings of the 13th ACM Conference on Electronic Commerce, pp. 862–879 (2012)

  32. Roughgarden, T., Schoppmann, F.: Local smoothness and the price of anarchy in atomic splittable congestion games. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 255–267 (2011)

  33. Roughgarden, T.: Intrinsic robustness of the price of anarchy. Commun. ACM 55(7), 116–123 (2012). (Preliminary version appeared in STOC 2009.)

    Article  Google Scholar 

  34. Suri, S., Tóth, C.D., Zhou, Y.: Selfish load balancing and atomic congestion games. In: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 188–195. ACM (2004)

  35. Syrgkanis, V.: Bayesian games and the smoothness framework. CoRR 1203.5155 (2012)

  36. Syrgkanis, V., Tardos, É.: Composable and efficient mechanisms. In: Proceedings of the 45th ACM Symposium on the Theory of Computing (2013)

  37. Young, H.P., Strategic Learning and its Limits. Oxford University Press (1995)

Download references

Acknowledgments

We would like to thank Ludovic Amruthalingam (from the Institut für Theoretische Informatik, ETH Zürich) for useful feedback on a preliminary version of this paper. We would also like to thank the anonymous reviewers (both of TOCS and of the preliminary conference version [1]) for their valuable comments.

Author information

Authors and Affiliations

  1. Sapienza University of Rome, Rome, Italy

    Aris Anagnostopoulos, Luca Becchetti & Bart de Keijzer

  2. CWI and VU University of Amsterdam, Amsterdam, The Netherlands

    Bart de Keijzer & Guido Schäfer

Authors
  1. Aris Anagnostopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luca Becchetti
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bart de Keijzer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Guido Schäfer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Aris Anagnostopoulos.

Additional information

This research was partially supported by the EU FET projects MULTIPLEX no. 317532 and SIMPOL no. 610704, the ERC StG Project PAAI 259515, the FET-Open FOC no. 255987, the Google Research Award for “Economics and Market Algorithms,” and the Google Focused Research Award “Algorithms for Large-scale Data Analysis.”

Appendices

Appendix A: Proofs of Theorems 1 and 2

Proof (Theorem 1)

Let σ be a coarse correlated equilibrium for Γα and let s be a random variable with distribution σ. Further, let s ∗∈Σ be an optimal strategy profile. The coarse correlated equilibrium condition implies that for every player i∈N:

$$\sum\limits_{j = 1}^{n} \alpha_{ij} \mathbf{E}[c_{j}({s}^{*}_{i}, s_{-i})] - \sum\limits_{j = 1}^{n} \alpha_{ij} \mathbf{E}[c_{j}(s)] \geq 0. $$

By summing over all players and using linearity of expectation, we obtain

$$\mathbf{E}[C(s)] \leq \mathbf{E}[C(s)] + \mathbf{E}\left[\sum\limits_{i=1}^{n} \sum\limits_{j = 1}^{n} \alpha_{ij}(c_{j}({s}^{*}_{i}, s_{-i}) - c_{j}(s))\right]. $$

Now we use the smoothness property (2) and obtain

$$\mathbf{E}[C(s)] \leq \mathbf{E}[C(s)] + \mathbf{E}[\lambda C(s^{*}) + (\mu-1) C(s)] = \lambda C(s^{*}) + \mu \mathbf{E}[C(s)]. $$

Since μ<1, this implies that the coarse correlated price of anarchy is at most λ/(1−μ). □

Proof (Theorem 2)

Consider a sequence \(s^{1}, \dots , s^{T}\) of outcomes of Γα that satisfies the vanishing average external regret property, i.e., for every player i∈N

$$ \frac{1}{T} \sum\limits_{t=1}^{T} c^{\alpha}_{i}(s^{t}) \le \frac{1}{T} \left[\min_{s^{\prime}_{i} \in {\Sigma}_{i}} \sum\limits_{t=1}^{T} c^{\alpha}_{i}(s^{\prime}_{i}, s^{t}_{-i})\right] + o(1). $$
(10)

Let s ∗ be an optimal outcome that minimizes the social cost function C. Define □

Appendix B: Proof of Lemma 2

Proof (Lemma 2)

It is easy to check that the claim holds if x=0 or y=0. Let x≥1 and y≥1. Recall that 1+φ=φ 2. We have

$$\begin{array}{@{}rcl@{}} \varphi^{2} y^{2} &-& 2 xy + \frac{1}{\varphi^{2}} x^{2} + \varphi x - \varphi^{2} y = \left(\varphi y - \frac{1}{\varphi} x\right)^{2} + \varphi x - (1+\varphi) y \\ &\ge& 2 \varphi y - \frac{2}{\varphi} x - 1 + \varphi x - (1+\varphi) y = (\varphi - 1) y + \left(\varphi - \frac{2}{\varphi}\right) x - 1 \\ &=& \frac{1}{\varphi} y + \left(1 - \frac{1}{\varphi}\right) x - 1 \ge 0, \end{array} $$

where the first inequality follows because z 2≥2z−1 for every \(z \in \mathbb {R}\) and the last one holds because x≥1 and y≥1. □

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Anagnostopoulos, A., Becchetti, L., de Keijzer, B. et al. Inefficiency of Games with Social Context. Theory Comput Syst 57, 782–804 (2015). https://doi.org/10.1007/s00224-014-9602-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-014-9602-4

Keywords

Search

Navigation