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

DOI10.1016/J.ORL.2016.10.001MaRDI QIDQ1709974zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(8)

• Opinion formation games with aggregation and negative influence
• The Local and Global Price of Anarchy of Graphical Games
• Multiagent learning for competitive opinion optimization
• 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

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)