Questions & explanations
1. Give an example where a random utility model predicts a violation of weak stochastic transitivity.
Consider three options: A, B, C. Suppose utilities are random: U(A)=0 with probability 0.4, U(A)=10 with probability 0.6; U(B)=5 always; U(C)=0 with probability 0.6, U(C)=10 with probability 0.4. Then P(A>B)=0.6, P(B>C)=0.6, but P(A>C)=0.52 (since A wins when both are 10 or both 0? Actually compute: A and C independent? Let's fix: A=0 or 10, C=0 or 10, independent. P(A>C)=P(A=10,C=0)+P(A=10,C=10)*0.5? No ties? Assume ties broken randomly. P(A=10)=0.6, P(C=0)=0.6, so P(A=10,C=0)=0.36; P(A=0,C=10)=0.4*0.4=0.16; ties: P(A=10,C=10)=0.6*0.4=0.24, half to A gives 0.12; P(A=0,C=0)=0.4*0.6=0.24, half to A gives 0.12; total P(A>C)=0.36+0.12+0.12=0.6. So actually weak stochastic transitivity holds. Need a violation: classic example is the 'Bicycle' example: P(A>B)=0.6, P(B>C)=0.6, P(C>A)=0.6, violating weak transitivity. This can arise from a random utility model with correlated utilities? Actually, random utility models always satisfy weak stochastic transitivity? I recall they satisfy 'moderate stochastic transitivity'? Let's correct: Random utility models with independent utilities satisfy
2. In a congestion game with two players and two resources, each player picks one resource. If both pick the same resource, each gets payoff 0; if they pick different resources, each gets payoff 1. Show that this is a potential game by finding a potential function.
This is a congestion game where each resource has a congestion cost: cost 0 if one player uses it, cost 1 if two players use it. A potential function can be the sum over resources of the total cost experienced by players on that resource. For resource A, if x players use it, the contribution is x * (x-1)/2? Actually, we need a function that changes exactly when a player changes strategy. For this game, define potential Φ = (number of players on resource A) * (number on B)? Simpler: Let Φ = 0 if players are on different resources, and Φ = 1 if they are on the same resource. Check: If a player switches from same to different, their payoff changes from 0 to 1 (+1), and Φ changes from 1 to 0 (-1). The change in payoff equals the change in Φ? No, we need the change in payoff to equal the change in potential. Actually, for potential games, the change in a player's payoff when they switch equals the change in the potential function. Here, switching from same to different: player's payoff increases by 1, potential decreases by 1? That's not equal. Let's correct: A standard potential function
3. Give an example of a game where one player has a dominant strategy and the other does not.
Consider a game where Player 1 chooses Up or Down, and Player 2 chooses Left or Right. Payoffs: (Up, Left) = (3,1), (Up, Right) = (3,2), (Down, Left) = (1,0), (Down, Right) = (0,3). Player 1's Up gives 3 regardless of Player 2's choice, so Up is dominant. Player 2's best response depends: if Player 1 picks Up, Right gives 2 > 1; if Player 1 picks Down, Left gives 0 > -? Actually Right gives 3 > 0? Wait, check: (Down,Left)= (1,0), (Down,Right)=(0,3). So Player 2 prefers Right when Player 1 picks Down, and Right when Player 1 picks Up. So Right is also dominant? Actually Right gives 2 vs 1 when Up, and 3 vs 0 when Down, so Right is dominant for Player 2. So both have dominant strategies. A better example: modify so Player 2's payoffs: (Up,Left)=(3,2), (Up,Right)=(3,1), (Down,Left)=(1,3), (Down,Right)=(0,0). Then Player 1 has dominant Up, but Player 2: if Up, Left gives 2 > 1; if Down, Left gives 3 > 0, so Left is dominant too. Actually both dominant again. Let's try: (Up,Left)=(2,1), (Up,Right)=(2,0), (Down,Left)=(1,2), (Down,Right)=(0,1). Player 1: Up gives 2 > 1 or 0, so dominant. Pl
4. Find the saddle point in this matrix: Row: Up: 3, Down: 2; Column: Left: 1, Right: 4. (Assume 2x2 matrix with Up row: [3,1]; Down row: [2,4])
The matrix is:
Left Right
Up 3 1
Down 2 4
Check each cell: For Up-Left (3): smallest in row? Row Up has 3 and 1, smallest is 1, so 3 is not smallest. Up-Right (1): smallest in row? Yes, 1 is smallest. Largest in column? Column Right has 1 and 4, largest is 4, so 1 is not largest. Down-Left (2): smallest in row? Row Down has 2 and 4, smallest is 2, so 2 is smallest. Largest in column? Column Left has 3 and 2, largest is 3, so 2 is not largest. Down-Right (4): smallest in row? No, smallest is 2. So no saddle point. Actually, let me recompute: The correct matrix for saddle point: Up row: [3,1]; Down row: [2,4]. Check Up-Right: 1 is smallest in row (1<3), but largest in column? Column Right: 1 and 4, largest is 4, so 1 is not largest. Down-Left: 2 is smallest in row (2<4), but largest in column? Column Left: 3 and 2, largest is 3, so 2 is not largest. So no saddle point. But if matrix were Up: [3,2]; Down: [1,4], then Up-Left: 3 is not smallest; Up-Right: 2 is smallest in row? 2<3 yes, largest in column? Column Right: 2 and 4, largest is 4, no. Down-Left: 1 is
5. In a shared irrigation system, two farmers can either maintain the canal (M) or not (N). Maintaining costs 2 each. If both maintain, each gets benefit 4 from water. If one maintains and the other does not, the maintainer gets benefit 2 (some water loss) and the non-maintainer gets benefit 4. If neither maintains, each gets 0. What is the Nash equilibrium? How can the government change the game to encourage maintenance?
Payoffs: both M: 4-2=2 each. Both N: 0 each. One M, one N: M gets 2-2=0, N gets 4. Check both N: each gets 0. If one switches to M, that player gets 0 (same), so both N is an equilibrium? Actually switching from N to M gives 0, which is not better, so both N is an equilibrium. Both M: each gets 2. If one switches to N, that player gets 4 (better), so both M is not equilibrium. Asymmetric: (M, N) gives M 0, N 4. M switching to N gives 0 (same), N switching to M gives 2 (worse), so (M, N) is an equilibrium? Wait, N switching to M gives 2, which is worse than 4, so N does not want to switch. M gets 0, switching to N gives 0, so no improvement. So (M, N) and (N, M) are also equilibria. So there are three Nash equilibria: both N, and the two asymmetric ones. To encourage maintenance, the government could subsidize maintenance by 1, so that M gets an extra 1. Then payoffs: both M: 2+1=3; one M: M gets 0+1=1, N gets 4; both N: 0. Then both M becomes an equilibrium because switching to N gives 4? Actually if both M, each gets 3. Switching to N gives 4 (if other stays M) which is better, so s
6. In a game with three players, the total value is 10. Player 1 alone can get 2, player 2 alone can get 3, player 3 alone can get 1. Any two players together can get 6. Which of the following divisions is in the core? (a) (2,3,5) (b) (3,3,4) (c) (4,3,3).
Division (c) (4,3,3) is in the core. Check: each player gets at least their solo value (4≥2, 3≥3, 3≥1). Any two players together get at least 6: players 1 and 2 get 4+3=7≥6, players 1 and 3 get 4+3=7≥6, players 2 and 3 get 3+3=6≥6. Total is 10. Division (a) gives player 3 only 5, but players 1 and 2 together get 2+3=5 < 6, so not in core. Division (b) gives players 1 and 2 together 3+3=6, okay, but players 2 and 3 get 3+4=7≥6, players 1 and 3 get 3+4=7≥6, and each gets at least solo value? Player 1 gets 3≥2, player 2 gets 3≥3, player 3 gets 4≥1. So (b) also satisfies all conditions? Wait, check player 1 and 2: 3+3=6 exactly, okay. So (b) and (c) both seem in core? Actually (b) is (3,3,4) and (c) is (4,3,3). Both satisfy. But the question says 'which of the following' implying one correct? Let's re-evaluate: For (b), players 1 and 2 together get 6, which is at least 6, okay. Players 1 and 3 get 3+4=7≥6, players 2 and 3 get 3+4=7≥6. So (b) is also in core. So both (b) and (c) are in core. But maybe the intended correct is (c) because (b) gives player 3 more? Actually both are fine. I'l
7. Compare potential games and congestion games: Is every potential game also a congestion game? Give a counterexample or reason.
Not every potential game is a congestion game. Congestion games are a specific subclass of potential games where the payoff to each player depends only on the number of players using each resource, and resources are shared. Potential games are more general: any game that admits a potential function is a potential game. For example, consider a game with two players where each chooses a number between 1 and 10, and player 1's payoff is the square of the number chosen by player 2, while player 2's payoff is the square of the number chosen by player 1. This game has a potential function: Φ = (player1's number)^2 + (player2's number)^2? Actually, check: If player 1 changes, his payoff changes by (new square of player2) - (old square of player2) which is zero if player2 unchanged. So potential change? Better example: A game where each player's payoff depends on the sum of all players' actions. That can be a potential game but not a congestion game because congestion games require that payoffs depend on per-resource congestion, not just a global sum. So potential games are a broader class.
8. Give an example of an imputation in the bargaining set but outside the core.
Consider a 3-player game with v({1,2})=10, v({1,3})=10, v({2,3})=0, v({1,2,3})=10, and v(S)=0 otherwise. The core is empty. The bargaining set includes (5,5,0). Check objections: Player 1 can object against 2 using coalition {1,3}: gives 10, player 1 gets 5, player 3 gets 5, so objection. Player 2 can counterobject using {2,3}? v({2,3})=0, so no. So (5,5,0) is not in bargaining set? Actually, need to check properly. The bargaining set definition: an objection is a pair (S,y) such that y(S)=v(S), y_i > x_i for i in S. A counterobjection is (T,z) with T containing the objector but not the objected, z(T)=v(T), z_j ≥ x_j for j in T, and z_k ≥ y_k for k in T∩S. For (5,5,0), player 1 objects against 2 with S={1,3}, y=(5,0,5)? Actually y must give more to 1: say y1=6, y3=4, sum=10. Then player 2 can counterobject with T={2,3}? v({2,3})=0, so no. So (5,5,0) is not in bargaining set. A correct example: game with v({1,2})=10, v({1,3})=10, v({2,3})=6, v({1,2,3})=12. The core is empty. The bargaining set includes (4,4,4)? Check: objections? Possibly (4,4,4) is in bargaining set but not core.
9. In a network game of peer effects, suppose each student chooses whether to study (1) or not (0). A student's payoff is 1 if they study, plus 0.5 times the number of studying friends, minus a cost of 0.8 if they study. Find a Nash equilibrium in a network of two friends connected to each other.
Let the two players be A and B, connected. If both study: each gets payoff = 1 (own study) + 0.5*1 (one friend studying) - 0.8 = 0.7. If A studies and B does not: A gets 1 + 0.5*0 - 0.8 = 0.2; B gets 0 (since not studying) + 0.5*1 = 0.5. If neither studies: both get 0. Check best responses: If B studies, A's payoff from studying is 0.7, from not studying is 0.5 (since B studies gives A 0.5). So A prefers studying (0.7 > 0.5). If B does not study, A's payoff from studying is 0.2, from not studying is 0. So A prefers studying (0.2 > 0). So studying is a dominant strategy for A? Actually, 0.2 > 0, so yes, studying is better regardless. Similarly for B. So the unique Nash equilibrium is both study. But if cost were higher, say cost=1.2, then if B studies, A's payoff from studying is 1+0.5-1.2=0.3, from not studying is 0.5, so A prefers not studying. If B does not study, A's payoff from studying is 1+0-1.2=-0.2, from not studying is 0, so prefers not studying. Then both not studying is the Nash equilibrium. So the equilibrium depends on parameters.
10. In a 2x2 game, Row has strategies U and D, Column has L and R. Payoffs: (U,L): (2,1), (U,R): (0,0), (D,L): (0,0), (D,R): (1,2). Draw the best-response correspondences for each player. What are the Nash equilibria?
For Row: if Column plays L, Row's best response is U (2 > 0). If Column plays R, Row's best response is D (1 > 0). So Row's best response to L is U, to R is D. For Column: if Row plays U, Column's best response is L (1 > 0). If Row plays D, Column's best response is R (2 > 0). Plot these on a graph with q (probability Column plays L) on x-axis and p (probability Row plays U) on y-axis. Row's best response: for q > 1/2? Actually, we need to find where Row is indifferent: Row's payoff from U: 2q + 0*(1-q)=2q; from D: 0q + 1*(1-q)=1-q. Indifference when 2q = 1-q => q=1/3. So for q < 1/3, Row prefers U (p=1); for q > 1/3, Row prefers D (p=0); at q=1/3, any p is best. Column's indifference: payoff from L: p*1 + (1-p)*0 = p; from R: p*0 + (1-p)*2 = 2(1-p). Indifference when p = 2(1-p) => p=2/3. So for p < 2/3, Column prefers R (q=0); for p > 2/3, Column prefers L (q=1); at p=2/3, any q. The intersections are at (p=1, q=0) and (p=0, q=1) and the mixed equilibrium at (p=2/3, q=1/3). So Nash equilibria: (U,L), (D,R), and mixed.
11. Compare the Nash and Kalai-Smorodinsky bargaining solutions. How do they differ?
Both are fair ways to divide gains, but they use different ideas. Nash maximizes the product of gains. Kalai-Smorodinsky gives each player the same proportion of their maximum possible gain. For example, if player A can get at most 8 and player B at most 2, Nash might give (4,6) if product is max? Actually need to compute. Kalai-Smorodinsky would give each the same percentage of their max, so if total is 10, A gets 8*(10/(8+2))=8, B gets 2, but that sums to 10? Actually that gives A 8, B 2, but then A gets 100% of max, B gets 100%? That seems off. Let's correct: Kalai-Smorodinsky equalizes the ratios of gain to maximum possible gain. So if A's max is 8, B's max is 2, and total is 10, then we find x such that x/8 = (10-x)/2, solving gives x=8, so A gets 8, B gets 2. So it gives A all the surplus? That seems extreme. Actually, the Kalai-Smorodinsky solution is the point on the Pareto frontier where the line from the disagreement point to the utopia point intersects. So it depends on the shape.
12. In a network game with local public goods, each player chooses a level of effort. Their payoff is the sum of their own effort plus the average effort of their neighbors, minus the cost of their own effort. Explain how this creates a strategic complementarity.
Strategic complementarity means that a player's optimal effort increases when their neighbors' efforts increase. In this game, a player's payoff includes the average effort of neighbors. If neighbors put in more effort, the player's benefit from their own effort also increases because the total benefit (own plus neighbors' average) is higher. However, the marginal benefit of own effort is constant (1), while the marginal cost is also constant. Actually, the complementarity arises if the marginal benefit of own effort increases with neighbors' effort. Here, the benefit from own effort is just own effort, so marginal benefit is 1, independent of neighbors. So there is no strategic complementarity in this simple version. To have complementarity, the payoff could be the product of own and neighbors' efforts. For example, if payoff = (own effort) * (average neighbor effort) - cost, then higher neighbor effort increases the marginal return to own effort, creating complementarity.