Bounding the Inefficiency of Compromise

Bounding the Inefficiency of Compromise

Ioannis Caragiannis, Panagiotis Kanellopoulos, Alexandros A. Voudouris

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 142-148. https://doi.org/10.24963/ijcai.2017/21

Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today's life. They have facilitated information dissemination in ways that have been beneficial for their users but it is also a common belief that they are often used strategically in order to spread information that only serves the objectives of particular users. These properties have inspired a revision of classical opinion formation models from sociology using game-theoretic notions and tools. We follow the same modeling approach, focusing on scenarios where the opinion expressed by each user is a compromise between her internal belief and the opinions of a small number of neighbors among her social acquaintances. We formulate simple games that capture this behavior and quantify the inefficiency of equilibria using the well-known notion of the price of anarchy. Our results indicate that compromise comes at a cost that strongly depends on the neighborhood size.
Keywords:
Agent-based and Multi-agent Systems: Economic paradigms, auctions and market-based systems
Agent-based and Multi-agent Systems: Noncooperative Games