• Hex is a two player board game. The game board is made up of n² hexagons arranged in n rows and columns. Opposite sides are designated as belonging to the same player (I and II). Each player plays alternately by placing one of his/her markers in one of the unoccupied hexagons. The game is over when one player 's markers make a path connecting his/her opposite sides. The player who has connected the sides is the winner. In the following figure, Player I is red, Player II is blue. Player I has won by connecting opposite edges.
• 
• We considered how play might be visualized for an 3x3 game using a "tree."

Here is a part of that tree showing alternate choices:




• Considering this example we saw that there are 9! possible different sequences for playing the 3x3 game allowing the play to continue till the board is full before determining a winner.

 
• We watched part of a video from For All Practical Purposes introducing matrix games and min-max strategies.
• Next: More on Hex, based on the recent Scientific American Article and matrix games based on the assigned readings.

 

• We started by exploring some of the web resources assembled through the course web site.
• We played some hex games against each other and the computer using winarc.
• We looked at two web sites devoted to hex briefly.
• We then discussed a notation for hex using coordinates to designate the hexes played by each player, e.g. (2,5) and (3,1). These followed a convention in starting the coordinates at 1 for the leftmost and 1 for the bottom most hex (1,1). With this notation a path demonstrating a player had won would be a sequence of ordered pairs satisfying appropriate properties relating the coordinates. This led to a different visualization of the game using a square grid with vertices connected by edges if and only if they correspond to adjacent hexagons.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

• We compared hex with the game "square" which would have similar rules for a board made with squares. The corresponding grid game would have only vertical and horizontal edges. In playing this game we saw that each player had a strategy that could prevent the other player from winning... thus the game under best play would turn out to be a draw.
• The game of hex is not as simple as square... In fact we will show next class that there are no draws in hex and that in theory the first player has a winning strategy.
• We finished the class watching the end of the For All Practical Purposes video on 2 person -zero sum games illustrating the ideas of saddle/equilibrium solutions to a matrix game with minimax strategies, and the use of mixed strategies. We will continue this discussion as well at our next meeting, Wed., Sept. 6.

 

• More on Hex and games in extensive form.
• Hex is never a draw.

Proof: Look at dual graph game. (see above)
Surround the game with an extra layer and mark vertices 1 or 2 depending on which player has taken the hex. Label the outer vertices as appropriate to the players borders.
Now walk through the rooms using edges labeled 1 and 2.
Note: There are no loops in this walk & only one edge to cross entering and leaving a cell.
Since there are only a finite number of cells, you must end by leaving at one of the corners. The path indicates the game has been won by either player 1 or 2.
• In a game in extensive form "with complete information" which has no draws either there is a winning strategy for player 1 or there is a winning strategy for player 2. (Note: There is another proof in Davis.)

Proof: Discuss "Pruning" and the decision tree.
Next class we' prove Hex is a win for Player I.
• More on mixed strategies and matrix game extensions.
• What is a mixed strategy?  How is this extend the nature of the game?
• A quick look at finite probability:
• Sample spaces: outcomes and events.
• Probalities of outcomes and events.
• Random variables and expected values (averages).
• Vectors and inner products.
• Mixed Strategies for matrix games:

Computing expected values for the extended games.
G is a game with matrix A, q is a mixed strategy for the Row Player, q is a mixed strategy for the column player. E(G;p,q) is the expected value for the game played with these stratgies: E(G;p,q) = pAq'  where q' indicates the transpose of the vector q.
• (Nash) Equilibrium and the value of a game.
• Finding equilibria for 2xm and nx2 games.

Equilization of expected returns.

• Discussion of relation of saddles to minimax and maximins based on homework problems.
• Hex is a win for Player I.

Proof: Stategy stealing. ("hidden board")

• More on games in extensive form.
• What is an information set?
• Chance moves.
• Games with perfect (complete) information.
• More on Nash Equilibrium.
• Nash's theorem for 2 person zero sum matrix games.

• P. Chinn on NIM games.
• FAPP Video start on linear programming.

• Optimization- linear programming excursion.

Connection to zero sum games.

• "Closing" on LP- duality and stategies for the row player in zero sum games.
• Start utility.

• We looked at software the solve games in extensive and normal form.
• We looked at axioms for utility and lotteries  and discussed problems of using these for models.

• We proved existence and uniqueness of utility functions.
• we discussed the relation of zero sum 2-person games to constant sum and general sum 2- person games.

 
 

Two Results of some importance:
Nash's theorem was announced.

• Movement diagrams and Nash equilibria.

 
• An outcome M(a,b) is Pareto optimalif

for any x,y, either M(x,y) is not pairwise comparable to M(a,b) or M_i(x,y)<= M_i(a,b) for i= 1 and 2.
 
• Pareto Principle: A solution to a game should have a Pareto optimal outcome.

(group rationality- may not apply in non-cooperative context)
 
• Payoff polygons used to visualize bimatrix games

	A	B
I	(2,3)	(3,2)
II	(1,0)	(0,1)

 
A vertex corresponds to payoff for pure strategy selection. M(a,b).
An edge corresponds to payoffs from mixed strategies. M(a,b) to M(c,d).
Pareto Optimal : "northeast" edge.
Nash Equilibrium: "Above or to the right of alternatives."
• Prudent strategies: (maxi min) Choose a strategy with best of worst results (this can be pure or mixed). The value of this strategy is called the player's security level.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

A counter prudential strategy is the best response to the opponent's prudent strategy. See p 70 for game 11.1.


 
• A Game is Solvable in a Strict Sense: Existence: Pareto optimal Nash equilibrium

Uniqueness: Equivalent and interchangeable.

• For an example we considered the game with matrices:
• A=

2	3	-1
0	2	4

• B=

-1	2	3
1	4	0

• These are transformed  ...
• A="A+2"

4	5	1
2	4	6

• B="B-5"

-6	-3	-2
-4	-1	-5

Now we considered the properties a non-cooperative equilibrium, p*..q* must have for this game:
p*=(p1*,p2*)   q*=(q1*,q2*,q3*). Let ER*=p*Aq*' and EC*=p*Bq*, then
from the property that these are N-equilibrium we saw that

4q1*+5q2*+1q3* <= ER*  and when < is true then p1*=0
2q1*+4q2*+6q3* <= ER* and when < is true then p2*=0
and similarly
-6p1*-4p2*<= EC* and when < is true then q1*=0
-3p1*-1p2*<= EC* and when < is true then q2*=0
-2p1*-5p2*<= EC* and when < is true then q3*=0

Now by dividing these inequalities by ER*>0 and  - EC* >0 as appropriate and letting x1=q1*/ER*, etc., we have that

4x1+5x2+1x3 <= 1  and when < is true then y1=0
2x1+4x2+6x3 <= 1 and when < is true then y2=0
and similarly
-6y1-4y2<= -1 and when < is true then x1=0
-3y1-1y2<= -1 and when < is true then x2=0
-2y1-5y2<= -1 and when < is true then x3=0.

Now, if these conditions are satisfied for non-negative values of x1,x2,x3,y1,and y2, then by using x$=x1+x2+x3 and y$=y1+y2 and q1#=x1/x$; etc. p1#=y1/y$,..
then q# and p# are non cooperative equilibrium strategies and ER(p#,q#)=1/x$ and EC(p#,q#)= -1/y$

In general we have the following theorem due to Lemke and Howson that gives these conditions for the existence of  of a non-cooperative equilibrium.






• So to find a non-cooperative equiuibrium pair,

it suffices to find x1,x2,x3,y1,and y2, non-negative that satisfy the complimentarity conditions.

These inequalities are translated into equalities by introducing "slack" variables.
the complementarity conditions also translate into conditions about the relationship between the slack variables and the corresponding strategy variables.

• These equations are now transformed using matrices and pivot operations until we arrive at a solution to the inequalities that does satisfy the required conditions.







• Discussion of proof of  Nash Equilibrium Theorem using transformations and fixed points. [Details distributed in class.]
• 10/30 Discussion of Fixed point theorem.

[Details to follow.]
• 11/1 We started by watching the video on power and fair division from the For All Practical Purposes series on Social Choice. This introduced voting games and the Banzhaff Power index with several examples illustrating the concepts of coalitions, having veto power, being powerless, and also a method for a "fair division" of a cake.

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

The discussion then turned to n - person games in normal form and an example of the visualization of a 3 person 2x2x2 game using a cube.

We then started a discussion of games in characteristic function form, with superadditivity.
ASSUMING that communication and side-payments are possible we will focus on the issue of finding a "fair allocation" of the value of the game to all the players.

We examined the example in the text where v(A)=v(B)=v(C) = 0 ; v(AB)=2, v(AC)= 4, and v(BC)=6, while v(ABC)=7.
Here we noted how if the coalition of ABC was formed sequentially, we could determine what each player added in value to the coalition as it was being formed. There are 6 ways for the coalition to form, so we computed the added values
 

	A	B	C
ABC	0	2	5
ACB	0	3	4
BAC	2	0	5
BCA	1	0	6
CAB	4	3	0
CBA	1	6	0
Totals	8	14	20

We to saw that these totals gave a proportion of contribution of 8:14:20 or 4:7:10. Allocation the 7 units under this scheme gave an imputation of (4/3, 7/3, 10/3)... which is also the average of the totals by the 6 permutations used in the considering how the added values could have arisen sequentially.
This imputation is called the Shapley value of the game, and it is characterised by the following properties that suggest something of its fairness.

Axioms for Shapley Value q of a game in characteristic form:
1. q depends only on v.
2. If  players have symmetric roles, then their payoffs under q should be equal.
3. If a player adds no value to any coalition S (a "dummy"), then that player has a payoff 0 under q.
4. Adding players who are dummies doesn't effect the payoffs to any of the other players under q.
5. If we add games A and B that have the same players, then the Shapley value q of the sum is the sum of the respective Shapley values for A and B

The major theorem which we will proceed with next class is that there is always one and only one imputation that will satisfy these axioms.
 
 

Def'n.:The core of a game  is the set of all imputations y where there is no x that dominates y.

Def'n.: A set V of imputations is called a stable set  for v if
(i) for each x and y in V, it is not the case that x<y, and
(ii) if y is not in V then there is some x in V where x dominates y.
 

• 2- person non-zero sum games with cooperation but no transferable utility.

VN-M : An arbitrated solution  (r*,c*) should be
• Pareto optimal.
• At or above the security level of each player.
  
  
• The negotiation set is the set of (r,c) that are Pareto optimal and at or above the security level of each player.
  
  
• The Nash Arbitration Scheme:
• Status Quo (SQ) Point is assumed to be the result if no aggreement reached.

Given polygon and SQ, there should be a unique point N*= (r*,c*) in the polygon satisfying the following properties:
• Rationality: N* is in the negotiation set.
• Linear Invariance: If R or C's utilities are transformed by a positive linear function, then N* is transformed by the same function.
• Symmetry: It the poygon is symmetric about the line through SQ with slope +1, then the solition N* should be on this line.
• Independence of Irrelevant Alternatives:  Suppose N* is the solution for the polygon P with SQ , and P' is another polygon which contains SQ and N* and P' is a subset of P. Then N* is also a solution for P' with staus quo point SQ.
  
  
• Theorem: [Nash]. There is one and only one arbitration scheme for a polygon with staus quo point SQ=(x0,y0) satisfying the four propoerties above: This is found to be the unique pair (x,y) in the polygon with x>=x0, y>=y0 that maximizes the product (x-x0)(y-y0).
  
  
• Proof:  Suppose polygon Q woth SQ=(x0,y0). Let N* be the point in Q that maximizes the product. Show N* must be the solution of any arbitration scheme satisfying the properties.

Translate problem to SQ=(0,0) by linear invariance.
Then muliply [ again by invariance] so that N*= (1,1).
Now the polygon must lie on or below xy = 1 in the first quadrant. Since Q is convex, Q lies below the tangent at (1,1) , i.e., x+y=2.
Now enclose Q in a larger polygon P with X+Y=2 as the northeast boundary symmetric wrt y=x. Now the solution to the problem with P and SQ=(0,0) must be (1,1), and thus the same is true for Q by the Iof IA.
 
• How do you choose SQ?  Use the security levels?

Use Threats. R threatens to play strategy r#, C threatens strategy c# leading to N*(r#,c#).
Nash: The game choose r#, c# is a zero sum game with a solution- the optimal threat strategy.