Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games

DOI10.1016/J.ORL.2016.10.001zbMATH Open1408.91040arXiv1602.02527OpenAlexW2539079415MaRDI QIDQ1709974FDOQ1709974

Authors: Po-An Chen, Yi-Le Chen, Chi-Jen Lu 

Publication date: 15 January 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Abstract: In opinion formation games with directed graphs, a bounded price of anarchy is only known for weighted Eulerian graphs. Thus, we bound the price of anarchy for a more general class of directed graphs with conditions intuitively meaning that each node does not influence the others more than she is influenced, where the bounds depend on such difference (in a ratio). We also show that there exists an example just slightly violating the conditions with an unbounded price of anarchy.

Full work available at URL: https://arxiv.org/abs/1602.02527

Recommendations

• Opinion Formation Games with Dynamic Social Influences
• Opinion formation games with dynamic social influences
• Local and global price of anarchy of graphical games
• The Local and Global Price of Anarchy of Graphical Games
• Opinion formation games with aggregation and negative influence

zbMATH Keywords

opinion formationprice of anarchylocal smoothness

Mathematics Subject Classification ID

Models of societies, social and urban evolution (91D10) Social networks; opinion dynamics (91D30) Games involving graphs (91A43)

Cites Work

• Algorithmic Game Theory
• Reaching a Consensus
• Intrinsic robustness of the price of anarchy
• Social influence and opinions
• How bad is forming your own opinion?
• Coevolutionary opinion formation games
• Local smoothness and the price of anarchy in atomic splittable congestion games
• On discrete preferences and coordination

Cited In (8)

• Multiagent learning for competitive opinion optimization
• The Local and Global Price of Anarchy of Graphical Games
• A game approach to multi-dimensional opinion dynamics in social networks with stubborn strategist agents
• Influence in social networks with stubborn agents: from competition to bargaining
• Opinion dynamics with limited information
• Mixed integer programming and LP rounding for opinion maximization on directed acyclic graphs
• Opinion dynamics with limited information
• Opinion formation games with aggregation and negative influence

This page was built for publication: Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709974)