COMPACT REPRESENTATIONS OF SEARCH IN COMPLEX DOMAINS

Yosi Ben-Asher () and Eitan Farchi ()
Additional contact information
Yosi Ben-Asher: CS department haifa university, Haifa, Israel
Eitan Farchi: I.B.M Research Center, Haifa, Israel

International Game Theory Review (IGTR), 2005, vol. 07, issue 01, 73-90

Abstract: We introduce a new zero-sum matrix game for modeling search in structured domains. In this game, one player tries to find a "bug" while the other tries to hide it. Both players exploit the structure of the "search" domain. Intuitively, this search game is a mathematical generalization of the well known binary search. The generalization is from searching over totally ordered sets to searching over more complex search domains such as trees, partial orders and general set systems. As there must be one row for every search strategy, and there are exponentially many ways to search even in very simple search domains, the game's matrix has exponential size ("space"). In this work we present two ways to reduce the space required to compute the Nash value (in pure strategies) of this game:• First we show that a Nash equilibrium in pure strategies can be computed by using a backward induction on the matrices of each "part" or sub structure of the search domain. This can significantly reduce the space required to represent the game.• Next, we show when general search domains can be represented as DAGs (Directed Acycliqe Graphs). As a result, the Nash equilibrium can be directly computed using the DAG. Consequently the space needed to compute the desired search strategy is reduced toO(n2)wherenis the size of the search domain.

Keywords: Nash equilibrium; search games; pure strategies; mixed strategies (search for similar items in EconPapers)
JEL-codes: B4 C0 C6 C7 D5 D7 M2 (search for similar items in EconPapers)
Date: 2005
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198905000399
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:07:y:2005:i:01:n:s0219198905000399

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198905000399

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().