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

详细信息    查看全文

• 作者：Po-An Chen^a ; ^{poanch@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; ^{poanchen@nctu.edu.tw" class="auth_mail" title="E-mail the corresponding author} ; Yi-Le Chen^a ; ^{jairachen78@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Chi-Jen Lu^b ; ^c ; ^{cjlu@iis.sinica.edu.tw" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Opinion formation ; Price of anarchy ; Local smoothness
• 刊名：Operations Research Letters
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：44
• 期：6
• 页码：808-811
• 全文大小：357 K

文摘

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.