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

Po-An Chen*, Yi Le Chen, Chi Jen Lu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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.

Original languageEnglish
Pages (from-to)808-811
Number of pages4
JournalOperations Research Letters
Volume44
Issue number6
DOIs
StatePublished - 1 Nov 2016

Keywords

  • Local smoothness
  • Opinion formation
  • Price of anarchy

Fingerprint Dive into the research topics of 'Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games'. Together they form a unique fingerprint.

Cite this