標題: Bounds on the price of anarchy for a more general class of directed graphs in opinion formation games
作者: Chen, Po-An
Chen, Yi-Le
Lu, Chi-Jen
資訊工程學系
資訊管理與財務金融系 註:原資管所+財金所
Department of Computer Science
Department of Information Management and Finance
關鍵字: Opinion formation;Price of anarchy;Local smoothness
公開日期: 十一月-2016
摘要: 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. (C) 2016 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.orl.2016.10.001
http://hdl.handle.net/11536/132840
ISSN: 0167-6377
DOI: 10.1016/j.orl.2016.10.001
期刊: OPERATIONS RESEARCH LETTERS
Volume: 44
Issue: 6
起始頁: 808
結束頁: 811
顯示於類別:期刊論文