Suchergebnisse

AbstractWe investigate the problem in which an agent has to find an object that moves between two locations according to a discrete Markov process (Pollock, Operat Res 18 (1970) 883–903). At every period, the agent has three options: searching left, searching right, and waiting. We assume that waiting is costless whereas searching is costly. Moreover, when the agent searches the location that contains the object, he finds it with probability 1 (i.e. there is no overlooking). Waiting can be useful because it could induce a more favorable probability distribution over the two locations next period. We find an essentially unique (nearly) optimal strategy, and prove that it is characterized by two thresholds (as conjectured by Weber, J Appl Probab 23 (1986) 708–717). We show, moreover, that it can never be optimal to search the location with the lower probability of containing the object. The latter result is far from obvious and is in clear contrast with the example in Ross (1983) for the model without waiting. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009

AbstractWe study subgame $$\phi $$
ϕ
-maxmin strategies in two-player zero-sum stochastic games with a countable state space, finite action spaces, and a bounded and universally measurable payoff function. Here, $$\phi $$
ϕ
denotes the tolerance function that assigns a nonnegative tolerated error level to every subgame. Subgame $$\phi $$
ϕ
-maxmin strategies are strategies of the maximizing player that guarantee the lower value in every subgame within the subgame-dependent tolerance level as given by $$\phi $$
ϕ
. First, we provide necessary and sufficient conditions for a strategy to be a subgame $$\phi $$
ϕ
-maxmin strategy. As a special case, we obtain a characterization for subgame maxmin strategies, i.e., strategies that exactly guarantee the lower value at every subgame. Secondly, we present sufficient conditions for the existence of a subgame $$\phi $$
ϕ
-maxmin strategy. Finally, we show the possibly surprising result that each game admits a strictly positive tolerance function $$\phi ^*$$

ϕ
∗

with the following property: if a player has a subgame $$\phi ^*$$

ϕ
∗

-maxmin strategy, then he has a subgame maxmin strategy too. As a consequence, the existence of a subgame $$\phi $$
ϕ
-maxmin strategy for every positive tolerance function $$\phi $$
ϕ
is equivalent to the existence of a subgame maxmin strategy.