On the existence of Nash equilibria in strategic search games

Carme Àlvarez, Amalia Duch, Maria Serna, Dimitrios Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationTrustworthy Global Computing - 6th International Symposium, TGC 2011, Revised Selected Papers
Number of pages15
StatePublished - 2012
Event6th International Symposium on Trustworthy Global Computing, TGC 2011 - Aachen, Germany
Duration: Jun 9 2011Jun 10 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7173 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th International Symposium on Trustworthy Global Computing, TGC 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the existence of Nash equilibria in strategic search games'. Together they form a unique fingerprint.

Cite this