Multi-round cooperative search games with multiple players

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 policiesC(ℓ) spe...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2020-11, Vol.113, p.125-149
Main Authors: Korman, Amos, Rodeh, Yoav
Format: Article
Language:English
Subjects:
Algorithmic mechanism design
Collaborative search
Computer Science
Distributed, Parallel, and Cluster Computing
Fault-tolerance
Parallel algorithms
Price of anarchy
Price of stability
Symmetric equilibria
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 policiesC(ℓ) 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.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2020.05.003