Game Theory: Practice for the Final Examination

Prepared by:

Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, NY 11451

email: 

malkevitch@york.cuny.edu

web page: 

http://york.cuny.edu

1. Given the election below:



i. Compute the pairwise vote matrix for the election above.

ii. Decide the winner (if there is one) of the election using:

a. Plurality

b. Run-off

c. Sequential Run-off

d. Borda Count

e. Condorcet (draw a digraph to show the results of the 2-way races)

f. Sequential run-off based on the Borda Count (Baldwin)

g. Coombs

h. Bucklin

iii. Be prepared to give a brief account of Arrow's Theorem and why it is important.

iv. Does it ever benefit a voter to "lie" about his/her preferences?

2. i. Use Adams, Jefferson, and Webster to apportion a legislature of 15 seats. Each of three regions is entitled to a minimum of at least one seat. The populations of these regions is shown below. The apportionment should be done "twice:"

a. Using a divisor and rounding (state what divisor you used so that when you rounded as the method requires that 15 seats were distributed). (If a tie occurs when 15 seats are given out, say so.)


b. Using the table method check if you get the same answer as you did for above for Adams, Jefferson, and Webster. For each of these methods indicate the order in which the seats are given out via the table method; when there is a tie, indicate this by having the states share these seats. Thus, here for example, seats 1-3 will be shared.


  A B C
Population 12300 9600 8100


ii. Use Hamilton's method to apportion 15 seats using the data above.

iii. What is required of an apportionment method which obeys "house monotonicity?"

iv. What is required of an apportionment method which obeys "population monotonicity?"

v. What is required of an apportionment method which obeys "quota?"

vi. What does the Balinksi-Young Theorem state?

vii. What is the method currently used for distributing the seats in the House of Representatives? Give a brief description of this method.

3. Given the weighted voting game: [14; 10, 7, 5, 4]

a. List the minimal winning coalitions
b. Determine the Shapley power of each of the players.
c. Determine the Banzhaf power of each of the players.
d. Determine the Coleman power of each of the players.
e. Does this game have any veto players?
f. List all of the winning coalitions for this game.
g. Suppose that secretly the players with weights 5 and 4 agree to always vote together. What are the power relations now as indicated by the Shapley and Banzhaf power indices? (Hint: What is the 3 player game that is now really being played?)

4. Consider the zero-sum games, with payoffs shown from Row's point of view below:

a.

  Column I II III
Row 1 3 -1 6
2 -2 0 5


b.

  Column I II III
Row 1 1 -3 3
2 -4 6 -2


i. What is the best-worst strategy for Row and Column in each game?

ii. Does either game have dominating strategies?

iii. Does either game have a saddle point?

iv. Find the optimal way to play these games for each player. (This means considering issues of dominating strategies or finding a saddle point to find a value for the game, and/or find a small matrix for which one can design optimal spinners.) As part of your solution what is the payoff to each player.

5. Find optimal spinners and the value of the game for the following zero-sum game:

Payoffs below are from Row's point of view.

  Column I Column II
Row 1 7 -4
Row 2 -2 1



6. (a) Find any pure and/or mixed Nash equilibrium (equilibria) for the non-zero-sum game below:

  Column I Column II
Row 1 (7,7) (-9, 6)
Row 2 (6, -9) (-1, -1)



Is this a familiar game? For each outcome cell of the game, are there any Pareto improvements over this outcome?

(b) Find any pure and/or mixed Nash equilibrium (equilibria) for the non-zero-sum game below:

  Column I Column II
Row 1 (0,0) (7, 2)
Row 2 (2, 7) (6, 6)



Is this a familiar game? For each outcome cell of the game, are there any Pareto improvements over this outcome?

7. For the bankruptcy situations below, find what amount from E is given to each player using:

a. Equality of gain

b. Equality of loss (with possible subsidization)

c. Maimonides gain

d. Maimonides loss

e. Shapley value

f. Proportionality

g. Contested garment rule ("Talmudic method") (Only use this when there are two claimants)

i. E = 240; A claims 80; B claims 200

ii. E = 240; A claims 180; B claims 220

iii. E = 240; A claims 40; B claims 300

iv. E = 240; A claims 60; B claims 140; C claims 200

Give several real world examples where bankruptcy problems might/do arise.

8. Find the male optimal and female optimal stable matchings (they may be the same) for the preferences shown below. For the stable matchings you find, give the "rank" of the "mate" each man and woman gets. For example if man 4 is paired with woman 2 she may be his 4th highest choice and he may be her 1st choice. For i and ii. if man i is matched with woman i is the matching stable? If not find a "blocking" pair.

i.

Men:

m1 2 3 1 5 4
m2 1 3 2 5 4
m3 1 5 2 3 4
m4 4 3 1 2 5
m5 5 4 3 2 1


Women:

w1 2 3 1 5 4
w2 1 3 2 4 5
w3 2 4 1 3 5
w4 3 4 1 2 5
w5 5 3 4 1 2


ii.

Men:

m1 2 3 1 5 4
m2 2 5 1 3 4
m3 1 4 2 3 5
m4 2 3 1 4 5
m5 1 4 5 2 3


Women:

w1 2 3 4 5 1
w2 1 3 2 4 5
w3 2 4 3 1 5
w4 3 4 1 2 5
w5 3 5 4 1 2