TY - GEN

T1 - On the existence of Nash equilibria in strategic search games

AU - Àlvarez, Carme

AU - Duch, Amalia

AU - Serna, Maria

AU - Thilikos, Dimitrios

PY - 2012

Y1 - 2012

N2 - We consider a general multi-agent framework in which a set of n agents are roaming a network where m valuable and sharable goods (resources, services, information ....) are hidden in m different vertices of the network. We analyze several strategic situations that arise in this setting by means of game theory. To do so, we introduce a class of strategic games that we call strategic search games. In those games agents have to select a simple path in the network that starts from a predetermined set of initial vertices. Depending on how the value of the retrieved goods is splitted among the agents, we consider two game types: finders-share in which the agents that find a good split among them the corresponding benefit and firsts-share in which only the agents that first find a good share the corresponding benefit. We show that finders-share games always have pure Nash equilibria (pne ). For obtaining this result, we introduce the notion of Nash-preserving reduction between strategic games. We show that finders-share games are Nash-reducible to single-source network congestion games. This is done through a series of Nash-preserving reductions. For firsts-share games we show the existence of games with and without pne. Furthermore, we identify some graph families in which the firsts-share game has always a pne that is computable in polynomial time.

AB - We consider a general multi-agent framework in which a set of n agents are roaming a network where m valuable and sharable goods (resources, services, information ....) are hidden in m different vertices of the network. We analyze several strategic situations that arise in this setting by means of game theory. To do so, we introduce a class of strategic games that we call strategic search games. In those games agents have to select a simple path in the network that starts from a predetermined set of initial vertices. Depending on how the value of the retrieved goods is splitted among the agents, we consider two game types: finders-share in which the agents that find a good split among them the corresponding benefit and firsts-share in which only the agents that first find a good share the corresponding benefit. We show that finders-share games always have pure Nash equilibria (pne ). For obtaining this result, we introduce the notion of Nash-preserving reduction between strategic games. We show that finders-share games are Nash-reducible to single-source network congestion games. This is done through a series of Nash-preserving reductions. For firsts-share games we show the existence of games with and without pne. Furthermore, we identify some graph families in which the firsts-share game has always a pne that is computable in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=84864054089&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84864054089&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-30065-3_4

DO - 10.1007/978-3-642-30065-3_4

M3 - Conference contribution

AN - SCOPUS:84864054089

SN - 9783642300646

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 58

EP - 72

BT - Trustworthy Global Computing - 6th International Symposium, TGC 2011, Revised Selected Papers

T2 - 6th International Symposium on Trustworthy Global Computing, TGC 2011

Y2 - 9 June 2011 through 10 June 2011

ER -