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

Opinion Formation Games with Aggregation and Negative Influence

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

Abstract

In this paper, we study continuous opinion formation games with aggregation aspects. In many domains, expressed opinions of people are not only affected by local interaction and personal beliefs, but also by influences that stem from global properties of the opinions present in the society. To capture the interplay of such global and local effects, we propose a model of opinion formation games with aggregation, where we concentrate on the average public opinion as a natural way to represent a global trend in the society. While the average alone does not have good strategic properties as an aggregation rule, we show that with a limited influence of the average public opinion, the good properties of opinion formation models are preserved. More formally, we show that a unique equilibrium exists in average-oriented opinion formation games. Simultaneous best-response dynamics converge to within distance ε of equilibrium in O(n2 ln(n/ε)) rounds, even in a model with outdated information on the average public opinion. For the Price of Anarchy, we show an upper bound of 9/8 + o(1), almost matching the tight bound for games without aggregation. We prove some of the results in the context of a general class of opinion formation games with negative influences, and we extend our results to cases where expressed opinions must come from a restricted domain.

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

References

  1. Altafini, C.: Consensus problems on networks with antagonistic interactions. IEEE Trans. Autom. Control 58(4), 935–946 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  2. Auletta, V., Caragiannis, I., Ferraioli, D., Galdi, C., Persiano, G.: Generalized discrete preference games. In: Proc. of the 25th International Joint Conference on Artificial Intelligence (IJCAI ’16), pp. 53–59 (2016)

  3. Barberà, S.: An introduction to strategyproof social choice functions. Soc. Choice Welf. 18, 619–653 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bhawalkar, K., Gollapudi, S., Munagala, K.: Coevolutionary opinion formation games. In: Proc. of the 45th ACM Symposium on Theory of Computing (STOC ’13), pp. 41–50 (2013)

  5. Bilȯ, V., Fanelli, A., Moscardelli, L.: Opinion formation games with dynamic social influences. In: Proc. of the 12th Conference on Internet and Network Economics (WINE ’16), volume 10123 of LNCS, pp. 444–458 (2016)

  6. Bindel, D., Kleinberg, J.M., Oren, S.: How bad is forming your own opinion? In: Proc. of the 52nd IEEE symposium on foundations of computer science (FOCS ’11), pp. 57–66 (2011)

  7. Chazelle, B., Wang, C.: Inertial Hegselmann-Krause systems. IEEE Trans. Autom. Control 62, 3905–3913 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, P.-A., Chen, Y.-L., Lu, C.-J.: Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games. Oper. Res. Lett. 44(6), 808–811 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  9. DeGroot, M.H.: Reaching a consensus. J. Am. Stat. Assoc. 69, 118–121 (1974)

    Article  MATH  Google Scholar 

  10. Ferraioli, D., Goldberg, P., Ventre, C.: Decentralized dynamics for finite opinion games. Theor. Comput. Sci. 648, 96–115 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fotouhi, B., Rabbat, M.G.: The effect of exogenous inputs and defiant agents on opinion dynamics with local and global interactions. IEEE J. Selected Topics Signal Process. 7(2), 347–357 (2013)

    Article  Google Scholar 

  12. Friedkin, N.E., Johnsen, E.C.: Social influence and opinions. J. Math. Sociol. 15(3-4), 193–205 (1990)

    Article  MATH  Google Scholar 

  13. Ghaderi, J., Srikant, R.: Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate. Automatica 50, 3209–3215 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  14. Golub, B., Jackson, M.O.: Naive learning in social networks and the wisdom of crowds̈. Am. Econ. J. Microecon. 2(1), 112–149 (2010)

    Article  Google Scholar 

  15. Hegselmann, R., Krause, U.: Opinion dynamics and bounded confidence models, analysis, and simulation. J. Artif. Societ. Soc. Simul, 5 (2002)

  16. Jackson, M.O.: Social and Economic Networks. Princeton University Press (2008)

  17. Moulin, H.: On strategy-proofness and single-peakedness. Public Choice 35, 437–455 (1980)

    Article  Google Scholar 

  18. Quattrociocchi, W., Caldarelli, G., Scala, A.: Opinion dynamics on interacting networks: Media competition and social influence. Sci. Rep. 4, 4938 (2014)

    Article  Google Scholar 

  19. Rosen, J.B.: Existence and uniqueness of equilibrium points in concave n-person games. Econometrica 33, 520–534 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  20. Roughgarden, T., Schoppmann, F.: Local smoothness and the price of anarchy in splittable congestion games. J. Economic Theory 156, 317–342 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  21. Yildiz, E., Ozdaglar, A., Acemoglu, D., Saberi, A., Scaglione, A.: Binary opinion dynamics with stubborn agents. ACM Trans. Econ. Comput. 1(4), 19,1–19,30 (2013)

    Article  Google Scholar 

Download references

Acknowledgments

Supported by DFG grant EXC 284 (Cluster of Excellence MMCI at Saarland University).

Author information

Authors and Affiliations

  1. Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA, USA

    Markos Epitropou

  2. Yahoo Research, New York, NY, USA

    Dimitris Fotakis

  3. School of Electrical and Computer Engineering, National Technical University of Athens, Athens, Greece

    Dimitris Fotakis & Stratis Skoulakis

  4. Institut für Informatik, Goethe-Universität Frankfurt am Main, Frankfurt, Germany

    Martin Hoefer

Authors
  1. Markos Epitropou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dimitris Fotakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martin Hoefer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Stratis Skoulakis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stratis Skoulakis.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the Topical Collection on Special Issue on Algorithmic Game Theory (SAGT 2017)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Epitropou, M., Fotakis, D., Hoefer, M. et al. Opinion Formation Games with Aggregation and Negative Influence. Theory Comput Syst 63, 1531–1553 (2019). https://doi.org/10.1007/s00224-018-9891-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-018-9891-0

Keywords

Search

Navigation