Consider a zero-sum game in which a hider selects one of locations and a searcher inspects locations until finding it. Inspection costs are , paid also at the discovered location; the hider maximizes total cost and the searcher minimizes it. Put . The value of a zero-sum game isThe hider uses probabilities . Every complete search order then has the same expected payoff: summing each cost multiplied by the probability that its location or a later one hides the object gives .
For the searcher's matching guarantee, inspect location first with probability , then inspect the remaining locations in a uniformly random order. For distinct , the probability that precedes isIf the object is at , expected total cost is therefore . Both guarantees hold for every opponent choice, proving optimality for any finite number of locations, including the three-location case.
Articles by others on the same topic
There are currently no matching articles.