Aman Pratap Singh / (IJCSE) International Journal on Computer Science and Engineering

Vol. 02, No. 09, 2010, 2778-2782

Optimal Solution Strategy for Games

Aman Pratap Singh, Student B.Tech

Computer Science Department, Faculty Of Engineering And Technology
Gurukul Kangri Vishvidayala
Haridwar, India

Abstract—In order to optimize a game, different techniques of detail. Game theory effectively describes the conditions of the
optimization are available. Considering the far wide application game and the strategy of the players but it doesn’t provide the
of game theory it becomes essential to establish the most effective method for the optimal solution of the game. For example in a
method of optimization of games. In this paper a discussion has game of chess the outcomes can be a white win or a black win
been done about the types of games under consideration and the or a draw. The game theory describes how these outcomes can
methods to optimize these games. The paper takes into account be achieved but doesn’t outline the process of playing through
games of pure and mixed strategies and stable and unstable which to achieve these results. Another example could be of
games. Different techniques of optimization are assessed using the political parties negotiating over forming a majority. Game
various detailed examples and theoretical concepts. By studying
theory describes which alliance can form a majority but doesn’t
the payoffs and cooperation between different players in different
techniques the paper establishes a common ground of
describe the negotiation process itself. Cooperative game
comparison for testing the efficiency of the techniques .The paper theory investigates such coalition games with respect to the
also suggests the advantages and disadvantages of each amount of power held by players. In case of a non cooperative
optimization technique with respect to an algorithmic point of game the game theory explicitly models the process of players
view. making choices of their own interest. Nash equilibrium is a
solution concept of a game involving two or more players, in
Keywords-component; Game Theory; Optimization; Nash which each player is assumed to know the equilibrium
Equilibrium; Graphical optimization; Linear Programming strategies of the other players, and no player has anything to
gain by changing only his or her own strategy unilaterally. If
I. INTRODUCTION each player has chosen a strategy and no player can benefit by
A game is a competition situation among N persons or changing his or her strategy while the other player keeps his
groups, called players that is conducted under a prescribed set strategy unchanged, then the current set of strategy choices and
of rules with known payoffs. The rules define the elementary the corresponding payoffs constitute Nash equilibrium. In case
activities, or moves, of the game. Different players may be of finite games which are the target of this paper according to
allowed different moves, but each player knows the moves Mas-Colell etal “Every finite game of perfect information ΓE
available to the other players. Game theory itself is the formal has a pure strategy Nash equilibrium that can be derived by
study of the conflict and cooperation. Game theory concepts backward induction. Moreover if no player has the same
are applicable to any actions or processes which contain several payoffs at any two terminal nodes then there is a unique Nash
agents which are interdependent to attaining similar goals. equilibrium that can be derived in this manner”.[1]
These agents may be individuals, players, organizations etc.
Applying the concepts of game theory a game is a formal II. DISCUSSION
model of an interactive situation typically involving players. A. Pure Strategy
There are various kinds of games. A broad classification of the
A pure strategy is a predetermined plan that prescribes for a
games can be into Passive and Dynamic. The passive games
player the sequence of moves and countermoves he will make
deal with a finite set of strategies which can be simultaneously
during a complete game. An optimal solution to the game is
applied by players. The Dynamic or Stochastic games are
said to be reached if neither player finds it beneficial to alter his
repeated games with probabilistic transitions. The main
strategy. In this case the game is said to be in a state of
difference between the two types of games is the fact that in
equilibrium. This equilibrium is called as Nash Equilibrium.
static games the players have a finite set of pure strategies
The game matrix is usually expressed in terms of a payoff to a
while in a dynamic game the strategies are infinite. Strategies
player. Thus a payoff matrix gives a complete characterization
of a player in a game can be divided into two types i.e. Pure
of a game.
Strategies and Mixed Strategies. In case of a pure strategy there
is a predetermined plan that prescribes for a player the For solving two-person zero-sum games we find the Row
sequence of moves and countermoves the player would make Minimum (Maximin) and Column Maximum (Minimax)
during a complete game. A mixed strategy on the other hand is values. These values provide us with the value of the game and
defined by a probability distribution over the set of pure determine of a saddle point is present in the game or not. In
strategy. Games can be described formally at various levels of case the saddle point is found in a game the game is bound to

ISSN : 0975-3397 2778

 Aman Pratap Singh / (IJCSE) International Journal on Computer Science and Engineering
Vol. 02, No. 09, 2010, 2778-2782

have been played by a pure strategy which would minimize the maximum of 4[3, 4, 2] and a maximum of 6[1, 5, 6] if he plays
losses of each player and maximize their profits correlating his third strategy. Player B playing his second and third
each other. This saddle point also represents the Nash strategy can gain a minimum of 4[7, 4, 5] and 1 [1, 2, 6]. Thus
Equilibrium that will be present in the game. The Nash the maximum value in each column represents the maximum
equilibrium in any game can be achieved by elimination of the loss that Player A will have to accommodate playing that
unfeasible moves for each player. strategy. The minimum value in each row represents the
minimum gain that Player B can get playing that strategy.
PLAYER I Player A by selecting the second strategy is minimizing his loss
while Player B by selecting his second strategy is maximizing
A B C his gain. In the above case the Maximin (M1) is equal to the
Minimax (M2).This equality gives us the saddle point of the
X 1,0 1,3 3,0 game. The condition of optimality is reached here since both
PLAYER J players are not tempted to change their strategies. This saddle
Y 0,2 0,1 3,0 point is also the value of the game. The value of the game
satisfies the following inequality.
Z 0,2 2,4 5,3 M1 ≤Value Of Game≤ M2

Applying elimination of Rows It is clearly noticeable that If this inequality doesn’t hold the game is a said to be a stable
for Player I strategy C is not feasible compared to A or B and game otherwise it’s called an unstable game. Every stable
so it is logical to assume that Player I wouldn’t play this game has a unique value and an optimal (pure) strategy for
strategy. This makes it safe to eliminate this strategy. Now for either player. The optimal strategies can be alternative and not
Player J, strategy X and Z clearly dominate strategy Y and unique. [2,3]
hence Y can also be eliminated.
B. Mixed Strategies
PLAYER I
In case when the game is unstable and no saddle point is
reached, there is no pure strategy for a player. To solve these
A B unstable games, mixed strategies are used. According to these
since there is no pure strategy for a player in an unstable game,
X 1,0 1,3 the player will play a multiple number of strategies to achieve
optimality. This condition of optimality can be found out
PLAYER J Z 0,2 2,4 provided that the random payoff is replaced by its expected
value. For a game with two players A and B, the mixed
strategy for A would be vector A.
Now considering this new matrix, for Player I the optimal A= [a1, a2, a3 ...an] T where an is the probability of selecting the
strategy is B and so Column A can also be eliminated. nth strategy.
Similarly Row X can also be eliminated for Player J. This
shows that for Player I the optimal strategy is B while for
Player J it is Z. This solution to any game is always a stable
one and called as the Nash Equilibrium. Considering another Similarly for player B the mixed strategy would be vector B.
3X3 payoff matrix we calculate the Maximin and the Minimax
so as to find the saddle point of the game if any. B= [b1, b2, b3 ...bn] T where bn is the probability of selecting the
nth strategy.
PLAYER A

5 3 1 1

PLAYER 7 4 5 4(Maximin) If we represent the i,j th entry of the payoff matrix of the game
B as xij, the payoff matrix would look like the following –
1 2 6 1 PLAYER B
x11 x12 ... x1j
7 6 PLAYER A x21 x22 ... x2j
4(Minimax)
... ... ... ...
xi1 xi2 ... xij
In the payoff matrix if Player A chooses his first strategy he
can lose at the maximum of 7[5, 7, 1]. For Player B, playing
the first strategy he can guarantee a minimum gain of 1[5, 3, 1]. Considering the Minimax- Criterion for a mixed strategy i.e.
Now if Player A plays his second strategy he can lose a the maximum value of the minimum expected gain for Player

ISSN : 0975-3397 2779

 Aman Pratap Singh / (IJCSE) International Journal on Computer Science and Engineering
Vol. 02, No. 09, 2010, 2778-2782

A and the minimum value of the maximum expected loss for there are two kinds of nodes: terminating and continuing.
player B. Terminating nodes lead to no other node, and player I receives
the payoff associated with his/her own arcs. Continuing nodes
For any game matrix there exist optimal strategies X and Y lead to at least one additional node. The two players
such that simultaneously choose one node each. For the example, the
E(X,Y)=A=B=G corresponding graph is given in the figure below. In this
directed network the edge goes from vertex u to vertex w, and
Where E(X, Y) = A and B are the if one player chooses w while the other chooses u, the player
vectors representing the probability distribution of the who selects w, which is at the head of arc connecting the two
strategies of the players and G is the expected value of the nodes, receives payoff tuw.
game. Accordingly every pure strategy game is a special case
of the mixed strategy game. Considering that almost all
practical games and their application contain mixed strategy,
analyzing their optimal solution is of critical importance to the
solution of games. [2,3]
III. GRAPHICAL SOLUTION OF TWO PERSON ZERO-
SUM GAMES
Graphical solution of a game provides an easy and efficient
method of optimizing the game. The pros of Graphical methods
are easy approach and simple method of solving while the cons
are that they are only applicable to games where at least one of Figure 1. Graphical Representation Of Two Person Zero-Sum Game
the players has only two strategies. Also they are not
considerate from an algorithmic point of view. Plotting the lines as a function of x1. The Maximin occurs
Considering the following 2x2 game, assuming there is no at x1=1/4 viz. the point of intersection of the lines of the 1st and
saddle point in the game. 2nd strategy. Therefore A’s optimal strategy is x1=1/2, x2=1-
x1=> ¾.
PLAYER B
y1 y2 ... yn
PLAYER A
x1 a11 a12 ... a1n
x2 a21 a22 ... a2n

Since A has two strategies, x1+x2=1 or x2=x1-1 where

x1,x2≥0. The expected payoffs to the pure strategy of B is
(a1n-a2n)x1+a2n where n is the nth pure strategy. Accordingly
the game can be optimized by plotting the graph for x1.
Example
Considering the following 2x3 game Figure 2. Graph of x1for maximin
PLAYER B
j=1 j=2 j=3
PLAYER A The value of the game can be determined by keeping the value
i=1 4 1 3
i=2 2 3 4 of x1 in the 1st and 2nd equations.
2(1/2)+2=5/2
The above game doesn’t have a saddle point. Therefore the -2(1/2)+3=5/2
expected payoff of Player A corresponding to the pure
strategies of B are given by The optimal strategy of B is y1=1/2,y2=1/2,y3=0.
i=1, 2 and j=1, 2 are essential strategies for Player A and B
TABLE I. EXPECTED PAYOFF TABLE
while j=3 is non essential for Player B.[4,5]
Strategy Of B Expected Payoff of A
1 (4-2)x1+2
2 (1-3)x1+3
3 (3-4)x1+4

Graphical representation of the games may be viewed as a

Tournament game played on a directed network. In this setting,

ISSN : 0975-3397 2780

 Aman Pratap Singh / (IJCSE) International Journal on Computer Science and Engineering
Vol. 02, No. 09, 2010, 2778-2782

IV. LINEAR PROGRAMMING OPTIMIZATION

In Linear programming problems the objective is either While Player B’s objective strategy can be represented as
maximization or minimization of the objective function. This
optimization is governed by the constraints and the non
negativity conditions. This is precisely the condition in games.
Each player is trying to maximize his profit and minimize his
loss. Accordingly every finite two person zero sum game can Subject to the constraints yj≥0, j=1, 2...n and
be converted into a linear programming problem. With each
linear programming problem there is associated a dual of the Then for Player B the problem becomes of Minimization of W
problem. The optimal values of the objective functions of the subject to the constraints.
two linear problems are equal, corresponding to the value of
Min W= y1+y2+....+yn
the game. When solving LP by simplex-type methods, the
optimal solution of the dual problem also appears as part of the Subject to
final tableau. When both players select their optimal strategies
one player’s highest expected gain is the other player’s highest a11y1+a12y2+...+a1nyn ≤ 1
expected loss or the dual of the first players programming a21y1+a22y2+...+a2nyn ≤ 1
problem. Suppose that player B is permitted to adopt mixed
strategies, but player A is allowed to use only pure strategies. .
What mixed strategies Y = (y1, y2, y3) should player B adopt .
to minimize the maximum expected payoff v? A moment's
thought shows that player B must solve the following problem: am1y1+am2y2+...+amnym ≤ 1

Min v = y all yi≥0 for i=1, 2,...n where W=1/V

subject T.Y ≤ y The LPP for B is the dual of A and hence solving any one of
to: them yields the solution of the other. Consider the following
UtY = 1 3X3 game which can be represented by the following LPP
PLAYER B
This minimization is over all elements of the decision vector 8 3 -1
Y ≥ 0, the scalar y is unrestricted in sign, and U is an n- PLAYER A
-2 -3 7
dimensional column vector with all elements equal to one. The
left hand side of the first n constraints, by definition, is player -6 4 2
B's expected return against player A's pure strategies. It turns
out that these mixed strategies are still optimal if we allow Maximize W = y1 + y2 + y3 subject to
player I to employ mixed strategies. Hence by solving for any
one of the player’s objective the other player’s objective can be 8y1 + 3y2 – y3 ≤ 1
automatically found.
-2y1 – 3y2 + 7y3 ≤ 1
Player A’s objective strategy can be represented as
-6y1 + 4y2 + 2y3 ≤ 1
where x,y,z≥0
The optimal strategy for B would be W=101/180, y1=13/180,
Subject to the constraints xi>=0, i=1, 2...m and y2=41/180, y3=47/180
Then for Player A the problem becomes of Maximization of Z V=1/W, Y1=y1/W, Y2=y2/w Y3=y3/W
subject to the constraints.
V=180/101, Y1=13/101, Y2=41/101, Y3=47/101
Max Z= x1+x2+....+xm [Y1+Y2+Y3=1]
subject to The optimal strategy for A is the dual of the above given by
a11x1+a21x2+...+am1xm ≥ 1 Z=W=101/180, x1=49/180, x2=5/36, x3=3/20
a21x1+a22x2+...+am2xm ≥ 1 V=1/Z, X1=x1/Z, X2=x2/Z, X3=x3/Z
. V=190/101, X1=49/101, X2=25/101, X3=27/101
[X1+X2+X3=1].[2,4,6]
.
a1nx1+a2nx2+...+amnxm ≥ 1
all xi≥0 for i=1,2,...m where Z=1/A

ISSN : 0975-3397 2781

 Aman Pratap Singh / (IJCSE) International Journal on Computer Science and Engineering
Vol. 02, No. 09, 2010, 2778-2782

V. CONCLUSION REFERENCES
In this paper I studied the different types of games and their
technique of optimization using examples and theoretical [1] Ulrich Schwalbe and Paul Walker, ” Zermelo and the Early History of
Game Theory”. JEL Classification: B19; C70; C72
concepts. Using Graphical and Linear Programming Methods
[2] Richard Bronson, ”Theory And Problems Of Operations
to optimize two person zero-sum games one of the conclusion Research”,McGraw Hill Publications Singapore ,1983
that can be drawn is that since graphical methods are [3] H.A. Taha, ”Operations Research An Introduction”,Macmillian
applicable to only games where at least one of the players has Publishing United States,1982
only two strategies. This hinders the use of graphical methods [4] Professor Hossein Arsham, ”Introduction to Game Theory:Winning
in applications and real life problems since hardly any game Business in A Competitive Environment”,Lecture Series Notes,2009
involves players with limited strategy. On the other hand every [5] “Solving two-person zero-sum repeated games of
game can be represented as a Linear Program and hence can incompleteinformation”, Andrew Gilpin and Tuomas Sandholm, Proc. of
7th Int.Conf. on Autonomous Agents and Multiagent Systems
be optimized as a linear programming problem of (AAMAS2008), Padgham, Parkes, Müller and Parsons (eds.), May, 12-
maximization or minimization. The presence of the dual of a 16.,2008, Estoril, Portugal, pp. XXX-XXX
Linear Programming Problem facilitates the use of linear [6] Hugo Gimbert And Florian Horn, “Solving Simple Stochastic Games
programming since using one objective function and solving With Few Random Vertices” ,Logical Methods In Computer
Science,Vol 5(2:9) 2009,pp 1-17
for it the objective of the other player can also be found. From
an algorithmic point of view linear programming is more
AUTHORS PROFILE
feasible compared to graphical methods since it is modular in
nature and works step by step. Aman Pratap Singh is a 3rd year computer science engineering
student pursuing his degree from Faculty Of Engineering And
Technology,GKV University Haridwar.His research interest
include Optimization,Parallel Processing and Artificial Life.

ISSN : 0975-3397 2782