A Classical Search Game in Discrete Locations
Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among $n$ discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location $i$ takes $t_i$ time units and detects the hider -- if hidden there -- independently with probability $q_i$, for $i=1,\ldots,n$. The hider aims to maximize the expected time until detection, while the searcher aims to minimize it. We prove the existence of an optimal strategy for each player. In particular, the hider's optimal mixed strategy hides in each location with a nonzero probability, and the searcher's optimal mixed strategy can be constructed with up to $n$ simple search sequences. We develop an algorithm to compute an optimal strategy for each player, and compare the optimal hiding strategy with the simple hiding strategy which gives the searcher no location preference at the beginning of the search.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Partial Solution to Continuous Blotto
This paper analyzes the structure of mixed-strategy equilibria for Colonel Blotto games, where the outcome on each battlefield is a polynomial function of the difference between the two players' allocations. This paper s…
Gradient Methods for Solving Stackelberg Games
Stackelberg Games are gaining importance in the last years due to the raise of Adversarial Machine Learning (AML). Within this context, a new paradigm must be faced: in classical game theory, intervening agents were huma…
Implicit Search via Discrete Diffusion: A Study on Chess
In the post-AlphaGo era, there has been a renewed interest in search techniques such as Monte Carlo Tree Search (MCTS), particularly in their application to Large Language Models (LLMs). This renewed attention is driven …
Efficient allocations in double auction markets
This paper proposes a simple descriptive model of discrete-time double auction markets for divisible assets. As in the classical models of exchange economies, we consider a finite set of agents described by their initial…
DescriptiveA fractional-order difference Cournot duopoly game with long memory
We reconsider the Cournot duopoly problem in light of the theory for long memory. We introduce the Caputo fractional-order difference calculus to classical duopoly theory to propose a fractional-order discrete Cournot du…