EE Seminar: Cooperative Search Games: Symmetric Equilibria, Robustness, and Price of Anarchy
(The talk will be given in English)
Speaker: Prof. Amos Korman, CNRS
University Paris Diderot
Monday, March 25th, 2019
15:00 - 16:00
Room 011, Kitot Bldg., Faculty of Engineering
Cooperative Search Games: Symmetric Equilibria, Robustness, and Price of Anarchy
Abstract
(Joint work with Yoav Rodeh)
Assume that a treasure is placed in one of M boxes according to a known distribution and that k searchers are searching for it in parallel during T rounds. We study the question of how to incentivize selfish players so that the success probability, i.e., the probability that at least one player finds the treasure, would be maximized. We identify a reward policy that yields the best possible price of anarchy, which turns out to be precisely $(1-(1-{1}/{k})^{k})^{-1}$. This exclusive policy yields high levels of competition, as it rewards a player (with a reward of 1) only if it finds the treasure strictly before others.
Together with an appropriate reward policy, a central entity can suggest players to play particular strategies at equilibrium. For such purposes, we advocate the use of symmetric equilibria. Besides being fair, we argue that symmetric equilibria can also become highly robust to crashes of players. Indeed, in many cases, despite the fact that some small fraction of players crash (or refuse to participate), symmetric equilibria remain efficient in terms of their group performances and, at the same time, serve as approximate equilibria.
We show that this principle holds for a class of games, which we denote by socially monotone games. This applies in particular for our search game, assuming the natural sharing policy, in which all players that simultaneously find the treasure for the first time equally share the reward of 1. For the exclusive policy, however, this does not apply, yet we show that the symmetric strategy with the highest success probability is both at equilibrium and, under mild assumptions, robust to crashes. Finally, for the sharing policy, we present an algorithm to construct an efficient and robust approximate equilibrium.
