Name
Abstract | ||
|---|---|---|
We study a multi-step hider-seeker game where the hider is moving on a graph and, in each step, the seeker is able to search c subsets of the graph nodes. We model this game as a zero-sum Bayesian game, which can be solved in weakly polynomial time in the players' action spaces. The seeker's action space is exponential in c, and both players' action spaces are exponential in the game horizon. To manage this intractability, we use a column/constraint generation approach for both players. This approach requires an oracle to determine best responses for each player. However, we show that computing a best response for the seeker is NP-hard, even for a single-step game when c is part of the input, and that computing a best response is NP-hard for both players for the multi-step game, even if c = 1. An integer programming formulation of the best response for the hider is practical for moderate horizons, but computing an exact seeker best response is impractical due to the exponential dependence on both c and the horizon. We therefore develop an approximate best response oracle with bounded suboptimality for the seeker. We prove performance bounds on the strategy that results when column/constraint generation with approximate best responses converges, and we measure the performance of our algorithm in simulations. In our experimental results, column/constraint generation converges to near-minimax strategies for both players fairly quickly. |
Year | Venue | Keywords |
|---|---|---|
2009 | IJCAI | c subsets,approximate best responses converges,action space,multi-step game,game horizon,multi-step multi-sensor hider-seeker game,multi-step hider-seeker game,best response,zero-sum bayesian game,single-step game,approximate best response oracle,col,bayesian game,polynomial time |
Field | DocType | Citations |
Mathematical optimization,Computer science,Best response,Oracle,Integer programming,Artificial intelligence,Sequential game,Time complexity,Bayesian game,Game tree,Machine learning,Bounded function | Conference | 30 |
PageRank | References | Authors |
2.40 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik Halvorson | 1 | 31 | 3.14 |
| Vincent Conitzer | 2 | 3111 | 261.71 |
| Ronald Parr | 3 | 2428 | 186.85 |