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 ().