Response factor

2013-02-25T08:21:32Z

82.186.243.243: /* Expression */

[[Image:Game with no value.svg|thumb|240px|Game square (that is, the payoff to player I) for a game with no value, due to Sion and Wolfe. The payoff is 0.5 along the two diagonal lines]]

In [[game theory]], and in particular the study of [[zero-sum]] [[continuous game]]s, it is commonly assumed that a game has a [[minimax]] value. This is the [[expected value]] to one of the players when both play a perfect strategy (which is to choose from a particular [[probability density function|PDF]]).

This article gives an example of a [[zero sum game]] that has no [[minimax|value]]. It is due to Sion and Wolfe.<ref>
{{citation | chapter = On a game without a value | first1 = Maurice | last1 = Sion | first2 = Phillip | last2 = Wolfe | pages = 299-306 | title = Contributions to the Theory of Games III | editor1-first = M. | editor1-last = Dresher | editor2-first = A. W. | editor2-last = Tucker | editor3-first = P. | editor3-last = Wolfe | year = 1957 | isbn = 9780691079363 | publisher = Princeton University Press | series = Annals of Mathematics Studies 39}}</ref>

Zero sum games with a finite number of pure strategies are known to have a [[minimax]] value (originally proved by [[John von Neumann]]) but this is not necessarily the case if the game has an infinite set of strategies. There follows a simple example of a game with no minimax value.

The existence of such zero-sum games is interesting because many of the results of [[game theory]] become inapplicable if there is no minimax value.

==The game==

Players I and II each choose a number, <math>x</math> and <math>y</math> respectively, with <math>0\leq x,y\leq 1</math>; the payoff to I is

:<math>K(x,y)=
\begin{cases}
-1 & \text{if } x<y<x+1/2 \\
0 & \text{if } x=y \text{ or } y=x+1/2\\
1 & \text{otherwise}
\end{cases}</math>

(i.e. player II pays <math>K(x,y)</math> to player I;the game is [[zero-sum]]). Sometimes player I is referred to as the ''maximizing player'' and player II the ''minimizing player''.

If <math>(x,y)</math> is interpreted as a point on the unit square, the figure shows the payoff to player I. Now suppose that player I adopts a mixed strategy: choosing a number from [[probability density function|probability density function (pdf)]] <math>f</math>; player II chooses from <math>g</math>. Player I seeks to maximize the payoff, player II to minimize the payoff. Note that each player is aware of the other's objective.

== Game value ==

Sion and Wolfe show that

:<math>
\sup_f \inf_g \iint K\,df\,dg=\frac{1}{3}
</math>

but

:<math>
\inf_g \sup_f \iint K\,df\,dg=\frac{3}{7}.
</math>

These are the maximal and minimal expectations of the game's value of player I and II respectively.

The <math>\sup</math> and <math>\inf</math> respectively take the supremum and infimum over pdf's on the unit interval (actually [[Borel measure|Borel probability measures]]). These represent player I and player II's (mixed) strategies. Thus, player I can assure himself of a payoff of at least 3/7 if he knows player II's strategy; and player II can hold the payoff down to 1/3 if he knows player I's strategy.

There is clearly no [[epsilon equilibrium]] for sufficiently small <math>\epsilon</math>, specifically, if <math>\epsilon < \frac{1}{2}\left(\frac{3}{7}-\frac{1}{3}\right)\simeq 0.0476</math>. Dasgupta and Maskin<ref>{{cite journal | author=[[Partha Dasgupta|P. Dasgupta]] and [[Eric Maskin|E. Maskin]] | title=The Existence of Equilibrium in Discontinuous Economic Games, I: Theory | journal= [[Review of Economic Studies]]| year=1986 | volume=53 | pages=1–26 | doi=10.2307/2297588 | issue=1 | jstor=2297588}}</ref> assert that the game values are achieved if player I puts probability weight only on the set <math>\left\{0,1/2,1\right\}</math> and player II puts weight only on <math>\left\{1/4,1/2,1\right\}</math>.

[[Glicksberg's theorem]] shows that any zero-sum game with [[upper semicontinuous|upper]] or [[lower semicontinuous]] payoff function has a value (in this context, an upper (lower) semicontinuous function ''K'' is one in which the set <math>\{P|K(P)<c\}</math> (resp <math>\{P|K(P)>c\}</math>) is [[open set|open]] for any [[real number|real]] ''c'').

Observe that the payoff function of Sion and Wolfe's example is clearly not semicontinuous. However, it may be made so by changing the value of ''K''(''x'', ''x'') and ''K''(''x'', ''x'' + 1/2) [i.e. the payoff along the two discontinuities] to either +1 or −1, making the payoff upper or lower semicontinuous respectively. If this is done, the game then has a value.

==Generalizations==

Subsequent work by Heuer <ref>{{cite journal | author=G. A. Heuer | title=Three-part partition games on rectangles | journal= Theoretical Computer Science| year=2001 | volume=259 | pages=639–661 | doi=10.1016/S0304-3975(00)00404-7}}</ref> discusses a class of games in which the unit square is divided into three regions, the payoff function being constant in each of the regions.

== References ==
{{reflist}}

[[Category:Game theory]]
[[Category:Mathematical examples]]

formulasearchengine - User contributions [en]

Response factor