| Prev | Next | Top | Problem15_1 |
\newcommand{\P}{{\bf P}}
A
and
B
simultaneously choose a coin (which they own) of value
x
or
y
where
x \neq y
.
If the chosen coins have the same value, player
A
gets
to keep them.
Otherwise player
B
gets to keep them.
We use
P( b , a )
to denote the payoff from
player
B
to player
A
when
A
chooses
a
and
B
chooses
b
.
The following table gives the payoff from player
B
to player
A
for each of the possible cases:
\[
\begin{array}{ll}
P(x, x) = x & P(x, y) = -y \\
P(y, x) = -x & P(y, y) = y
\end{array}
\]
A
(if the strategy is discovered by
B
) solves the problem
\[
{\rm maximize} \left[ \inf_{b \in \P(2)}
b_1 x a_1 - b_1 y a_2 - b_2 x a_1 + b_2 y a_2
\right] \; w.r.t. \; a \in \P(2)
\]
Applying the inf
part of the lemma for matrix games,
we obtain the equivalent problem:
\[
{\rm maximize} \left[
\min \left( x a_1 - y a_2 \; , \; - x a_1 + y a_2 \right)
\right] \; w.r.t. \; a \in \P(2)
\]
Because there are only two components of
a
,
we can use
a_2 = 1 - a_1
to replace
a_2
in the objective
and obtain the equivalent problem
\[
{\rm maximize} \left[
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\right] \; w.r.t. \; a_1 \in [0, 1]
\]
The function
\[
f( a_1 ) =
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\]
has constant derivative on the interval
[0,1]
except for
three points.
Thus, there are three possible solutions for the maximum:
a_1 = 0
,
a_1 = 1
or the solution of the following
equation
\[
\begin{array}{rcl}
(x + y) a_1 - y & = & y - (x + y) a_1 \\
a_1 & = & y / (x + y)
\end{array}
\]
The corresponding objective function values are
\[
\begin{array}{rclcrcl}
0 & = & a_1 & \Rightarrow & -y & = &
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\\
1 & = & a_1 & \Rightarrow & -x & = &
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\\
y / (x + y) & = & a_1 & \Rightarrow & 0 & = &
\min \left( (x + y) a_1 - y \; , \; y - (x + y) a_1 \right)
\end{array}
\]
It follows
(from the fact that
x > 0
and
y > 0
)
that the optimal strategy for
A
is to choose
x
with probability
y/(x + y)
and to choose
y
with probability
x/(x + y)
.
In this case, the expected payoff of the game is zero
(provided that player
B
plays in an optimal fashion).
B
(if the strategy is discovered by
A
) solves the problem
\[
{\rm minimize} \left[ \sup_{a \in \P(2)}
b_1 x a_1 - b_1 y a_2 - b_2 x a_1 + b_2 y a_2
\right] \; w.r.t. \; b \in \P(2)
\]
Applying the sup
part of the lemma for matrix games,
we obtain the equivalent problem:
\[
{\rm minimize} \left[
\max \left( b_1 x - b_2 x \; , \; - b_1 y + b_2 y \right)
\right] \; w.r.t. \; b \in \P(2)
\]
Because there are only two components of
b
,
we can use
b_2 = 1 - b_1
to replace
b_2
in the objective
and obtain the equivalent problem
\[
{\rm minimize} \left[
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\right] \; w.r.t. \; b_1 \in [0, 1]
\]
The function
\[
g( b_1 ) =
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\]
has constant derivative on the interval
[0,1]
except for
three points.
Thus, there are three possible solutions for the maximum:
b_1 = 0
,
b_1 = 1
or the solution of the following
equation
\[
\begin{array}{rcl}
x ( 2 b_1 - 1 ) & = & ( 1 - 2 b_1 ) y
\\
2 (x + y) b_1 & = & (x + y)
\\
b_1 & = & 1 / 2
\end{array}
\]
The corresponding objective function values are
\[
\begin{array}{rclcrcl}
0 & = & b_1 & \Rightarrow & y & = &
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\\
1 & = & b_1 & \Rightarrow & x & = &
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\\
1 / 2 & = & b_1 & \Rightarrow & 0 & = &
\max \left( x ( 2 b_1 - 1 ) \; , \; (1 - 2 b_1 ) y \right)
\end{array}
\]
It follows
(from the fact that
x > 0
and
y > 0
)
that the optimal strategy for
B
is to choose
x
with probability
1/2
and to choose
y
with probability
1/2
.
In this case, the expected payoff of the game is zero
(provided that player
A
plays in an optimal fashion).