New interface

# Multi-round cooperative search games with multiple players

2 GANG - Networks, Graphs and Algorithms
Inria de Paris, IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
Abstract : A treasure is placed in one of M boxes according to a known distribution and k searchers are searching for it in parallel during T rounds. How can one incentivize selfish players so that the probability that at least one player finds the treasure is maximized? We focus on congestion policies $C()$ specifying the reward a player receives being one of the players that (simultaneously) find the treasure first. We prove that the exclusive policy, in which $C(1) = 1$ and $C() = 0 for > 1$, yields a price of anarchy of $(1 − (1 − 1/k) k) −1$ , which is the best among all symmetric reward policies. We advocate the use of symmetric equilibria, and show that besides being fair, they are highly robust to crashes of players. Indeed, in many cases, if some small fraction of players crash, symmetric equilibria remain efficient in terms of their group performance while also serving as approximate equilibria.
Document type :
Journal articles

Cited literature [43 references]

https://hal.inria.fr/hal-02989497
Contributor : Amos Korman Connect in order to contact the contributor
Submitted on : Saturday, November 7, 2020 - 5:23:39 PM
Last modification on : Tuesday, October 25, 2022 - 4:19:25 PM
Long-term archiving on: : Monday, February 8, 2021 - 6:48:24 PM

### File

multiround_Nash.pdf
Files produced by the author(s)

### Citation

Amos Korman, Yoav Rodeh. Multi-round cooperative search games with multiple players. Journal of Computer and System Sciences, 2020, 113, pp.125-149. ⟨10.1016/j.jcss.2020.05.003⟩. ⟨hal-02989497⟩

Record views