A mixed strategy is a probability distribution over the set of pure strategies. When a player implements a mixed strategy, she chooses a pure strategy at the outset of the game, and follows that pure strategy all through the game.
A behavior strategy is a function that assigns a mixed action to each of the player’s information sets. When a player implements a behavior strategy, whenever the play reaches an information set the player chooses an action according to the mixed action that corresponds to that information set.
Thus, if the play crosses twice the same information set, a mixed strategy will choose the same action in both visits, while a behavior strategy will choose each time the action to play independently of past play.
The well known Kuhn’s Theorem states that in extensive-form games with perfect recall, the notions of mixed strategies and behavior strategies are the same: it is irrelevant whether the player makes her choices when the play visits the information set, or whether she makes these choices at the outset of the game, because the condition of perfect recall implies in particular that the play can cross each information set only once.
Kuhn’s Theorem holds for finite games: the depth of the game is finite, and there are finitely many actions in each decision nodes. The theorem can be extended to the case of infinite trees (countably many nodes), provided the number of actions in each decision nodes is finite.
In stopping problems the number of nodes is of the cardinality of the continuum, and therefore Kuhn’s Theorem does not apply. Stopping problems are a model that is used in mathematical finance: at every stage an agent receives payoff-relevant information, and she has to choose when to stop (when to sell stocks, or when to exercise options). The payoff is given by some stochastic process. Yuri Kifer asked me a question that boiled down to the following: in the model of stopping problems, are mixed strategies and behavior strategies equivalent? My first response was “sure”. Yuri wanted to see a proof. When I tried to write down the proof, a technical issue emerged. It required some time and the energy of three people to be able to provide a definite answer: “sure”.
. The matrix 
and the RHS vector 
are all rational. Let 
be an optimal extreme point solution and 
the absolute value of the determinant of the optimal basis. Then, 
must be an integral vector. Equivalently, if in our original linear program we scale the constraints by 
be a set of agents, 
a set of distinct goods and 
the utility that agent 
enjoys from consuming the bundle 
. Note, no restrictions on 
beyond non-negativity and quasi-linearity.
if the bundle 
is assigned to agent 
must be in agent 
for all 
and 
is an integer. Now construct an enlarged economy as follows.
by a factor of 
clones. It should be clear now where this is going, but lets dot the i’s. To formulate the problem of finding an efficient allocation in this enlarged economy let 
if bundle 
clone of agent 
be the utility function of the 
, the 
a bundle 
for both. Let 
be the density function over types. To avoid clutter, assume the uniform distribution, i.e., 
. Nothing in the subsequent analysis relies on this.
and agent 2 reports type 
, denote by 
the probability that outcome 
is selected. The 
‘s must be non-negative and satisfy 
that determines, along with her type, the utility she enjoys from a given allocation. In particular, given the allocation rule 
of type 
A similar expression holds agent 2.
Interpret the 
‘s as the `quantity’ of goods that each agent receives. Dominant strategy implies that 
should be monotone increasing in 
should be monotone increasing in 
Bayesian incentive compatibility (BIC) implies that the 
‘s should be monotone. To determine if given BIC interim `quantities’ ![\displaystyle \sum_{r \in A}a_{1r}[z_r(i,j) - z_r(i-1,j)] \geq 0\,\, \forall \,\, i = 2, \ldots, m \ \ \ \ \ (1)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Br+%5Cin+A%7Da_%7B1r%7D%5Bz_r%28i%2Cj%29+-+z_r%28i-1%2Cj%29%5D+%5Cgeq+0%5C%2C%5C%2C+%5Cforall+%5C%2C%5C%2C+i+%3D+2%2C+%5Cldots%2C+m+%5C+%5C+%5C+%5C+%5C+%281%29&bg=ffffff&fg=000000&s=0 "\displaystyle \sum_{r \in A}a_{1r}[z_r(i,j) - z_r(i-1,j)] \geq 0\,\, \forall \,\, i = 2, \ldots, m \ \ \ \ \ (1)")
![\displaystyle \sum_{r \in A}a_{2r}[z_r(i,j) - z_r(i,j-1)] \geq 0\,\, \forall \,\, j = 2, \ldots, m \ \ \ \ \ (2)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Br+%5Cin+A%7Da_%7B2r%7D%5Bz_r%28i%2Cj%29+-+z_r%28i%2Cj-1%29%5D+%5Cgeq+0%5C%2C%5C%2C+%5Cforall+%5C%2C%5C%2C+j+%3D+2%2C+%5Cldots%2C+m+%5C+%5C+%5C+%5C+%5C+%282%29&bg=ffffff&fg=000000&s=0 "\displaystyle \sum_{r \in A}a_{2r}[z_r(i,j) - z_r(i,j-1)] \geq 0\,\, \forall \,\, j = 2, \ldots, m \ \ \ \ \ (2)")
![\displaystyle \sum_{r \in A}a_{1r}[z_r(i,j) - z_r(i-1,j)] + w_{ij} - u_{ij} = 0\,\, \forall \,\, i = 2, \ldots, m\,\, (\mu_{ij}) \ \ \ \ \ (7)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Br+%5Cin+A%7Da_%7B1r%7D%5Bz_r%28i%2Cj%29+-+z_r%28i-1%2Cj%29%5D+%2B+w_%7Bij%7D+-+u_%7Bij%7D+%3D+0%5C%2C%5C%2C+%5Cforall+%5C%2C%5C%2C+i+%3D+2%2C+%5Cldots%2C+m%5C%2C%5C%2C+%28%5Cmu_%7Bij%7D%29+%5C+%5C+%5C+%5C+%5C+%287%29&bg=ffffff&fg=000000&s=0 "\displaystyle \sum_{r \in A}a_{1r}[z_r(i,j) - z_r(i-1,j)] + w_{ij} - u_{ij} = 0\,\, \forall \,\, i = 2, \ldots, m\,\, (\mu_{ij}) \ \ \ \ \ (7)")
![\displaystyle \sum_{r \in A}a_{2r}[z_r(i,j) - z_r(i,j-1)] + h_{ij} - v_{ij} = 0\,\, \forall \,\, j = 2, \ldots, m\,\, (\nu_{ij}) \ \ \ \ \ (8)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Csum_%7Br+%5Cin+A%7Da_%7B2r%7D%5Bz_r%28i%2Cj%29+-+z_r%28i%2Cj-1%29%5D+%2B+h_%7Bij%7D+-+v_%7Bij%7D+%3D+0%5C%2C%5C%2C+%5Cforall+%5C%2C%5C%2C+j+%3D+2%2C+%5Cldots%2C+m%5C%2C%5C%2C+%28%5Cnu_%7Bij%7D%29+%5C+%5C+%5C+%5C+%5C+%288%29&bg=ffffff&fg=000000&s=0 "\displaystyle \sum_{r \in A}a_{2r}[z_r(i,j) - z_r(i,j-1)] + h_{ij} - v_{ij} = 0\,\, \forall \,\, j = 2, \ldots, m\,\, (\nu_{ij}) \ \ \ \ \ (8)")
be an optimal solution to this program.
such that 
. I will argue that there must exist an 
. Suppose not, then for each 
, either 
or 
and 
(at optimality, it cannot be that 
and 
are both non-zero). In this case![\displaystyle m[Q_1(p)-Q_1(p-1)] = \sum_j\sum_{r \in A}a_{1r}z^*_r(p,j) - \sum_j\sum_{r \in A}a_{1r}z^*_r(p-1,j)](http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+m%5BQ_1%28p%29-Q_1%28p-1%29%5D+%3D+%5Csum_j%5Csum_%7Br+%5Cin+A%7Da_%7B1r%7Dz%5E%2A_r%28p%2Cj%29+-+%5Csum_j%5Csum_%7Br+%5Cin+A%7Da_%7B1r%7Dz%5E%2A_r%28p-1%2Cj%29+&bg=ffffff&fg=000000&s=0 "\displaystyle m[Q_1(p)-Q_1(p-1)] = \sum_j\sum_{r \in A}a_{1r}z^*_r(p,j) - \sum_j\sum_{r \in A}a_{1r}z^*_r(p-1,j)")
![= \sum_{j: w^*_{pj} > 0}a_{1r}[z^*_r(p,j) - z^*_r(p-1,j)]](http://s0.wp.com/latex.php?latex=%3D+%5Csum_%7Bj%3A+w%5E%2A_%7Bpj%7D+%3E+0%7Da_%7B1r%7D%5Bz%5E%2A_r%28p%2Cj%29+-+z%5E%2A_r%28p-1%2Cj%29%5D&bg=ffffff&fg=545454&s=0 "= \sum_{j: w^*_{pj} > 0}a_{1r}[z^*_r(p,j) - z^*_r(p-1,j)]")
. This last term is negative, a contradiction. Therefore, there is a 
such that 
but 
.
, 
and denote by 
the point 
. Observe that 
of 
for all 
. Thus choosing 
‘s amounts to choosing a point 
. Equivalently, choosing a point 
and that 
is full dimensional. This avoids having to deal with secondary arguments that obscure the main idea.
implies that 
. Take all points 
and shift them horizontally to the right by 
. Call these new points 
. Observe that 
for all 
. Next, take all points 
and shift them horizontally to the left by 
. These points are also in 
unchanged.
reduces 
while the rightward shift of 
reduces 
. Thus, we get a new solution with higher objective function value, a contradiction.
. In this case, shift 
. Similarly with 
Recent Comments