On the performance of mildly greedy players in cut games

Vittorio Bilò () and Mauro Paladini
Additional contact information
Vittorio Bilò: University of Salento
Mauro Paladini: University of Salento

Journal of Combinatorial Optimization, 2016, vol. 32, issue 4, No 5, 1036-1051

Abstract: Abstract We continue the study of the performance of mildly greedy players in cut games initiated by Christodoulou et al. (Theoret Comput Sci 438:13–27, 2012), where a mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than $$1+\epsilon $$ 1 + ϵ , for some given $$\epsilon \ge 0$$ ϵ ≥ 0 . Hence, in presence of mildly greedy players, the classical concepts of pure Nash equilibria and best-responses generalize to those of $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate pure Nash equilibria and $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate best-responses, respectively. We first show that the $$\epsilon $$ ϵ -approximate price of anarchy, that is the price of anarchy of $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate pure Nash equilibria, is at least $$\frac{1}{2+\epsilon }$$ 1 2 + ϵ and that this bound is tight for any $$\epsilon \ge 0$$ ϵ ≥ 0 . Then, we evaluate the approximation ratio of the solutions achieved after a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate one-round walk starting from any initial strategy profile, where a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate one-round walk is a sequence of $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate best-responses, one for each player. We improve the currently known lower bound on this ratio from $$\min \left\{ \frac{1}{4+2\epsilon },\frac{\epsilon }{4+2\epsilon }\right\} $$ min 1 4 + 2 ϵ , ϵ 4 + 2 ϵ up to $$\min \left\{ \frac{1}{2+\epsilon },\frac{2\epsilon }{(1+\epsilon )(2+\epsilon )}\right\} $$ min 1 2 + ϵ , 2 ϵ ( 1 + ϵ ) ( 2 + ϵ ) and show that this is again tight for any $$\epsilon \ge 0$$ ϵ ≥ 0 . An interesting and quite surprising consequence of our results is that the worst-case performance guarantee of the very simple solutions generated after a $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate one-round walk is the same as that of $$(1+\epsilon )$$ ( 1 + ϵ ) -approximate pure Nash equilibria when $$\epsilon \ge 1$$ ϵ ≥ 1 and of that of subgame perfect equilibria (i.e., Nash equilibria for greedy players with farsighted, rather than myopic, rationality) when $$\epsilon =1$$ ϵ = 1 .

Keywords: Cut games; (Approximate) Nash equilibria; Price of anarchy (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9898-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:4:d:10.1007_s10878-015-9898-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9898-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().