Networks: Fall 2019 homework 2
homework – 该题目是一个homework代写的题目
Networks: Fall 2019 homework 2
Austin Benson and David Easley Due 11:15am, Friday, September 20, 2019
As noted on the course home page, homework solutions must be submitted by upload to the CMS site, athttps://cmsx.cs.cornell.edu/. The file you upload must be in PDF format. Your homework submissions need to be typeset (hand-drawn figures are OK). You can use any typesetting system, such as Word; from Word, you can save the file out as PDF for uploading.
The CMS site will stop accepting homework uploads after the posted due date. We cannot accept late homework except for University-approved excuses (which include illness or a family emergency).
Reading:The questions below are primarily based on the material in Chapters 6 and 8 of the book.
(1)In this question we will consider several two-player games. In each payoff matrix below the rows correspond to player As strategies and the columns correspond to player Bs strategies. The first entry in each box is player As payoff and the second entry is player Bs payoff. Both players prefer higher payoffs to lower payoffs. (a)Find all pure (non-randomized) strategy Nash equilibria for the game described by the payoff matrix in Figure 1.
Player A
Player B
L R
U 3 , 2 0 , 4
D 5 , 0 1 , 1
Figure 1: The payoff matrix for Question (1a).
(b)Find all pure (non-randomized) strategy Nash equilibria for the game described by the payoff matrix in Figure 2.
Player A
Player B
L R
U 1 , 0 3 , 1
D 3 , 2 4 , 0
Figure 2: The payoff matrix for Question (1b).
(c)FindallNash equilibria for the game described by the payoff matrix in Figure 3. Provide a brief explanation for your answer.
Player A
Player B
L R
U 0 , 1 3 , 3
D 1 , 1 2 , 0
Figure 3: The payoff matrix for Question (1c).
[Hint: This game has two pure strategy equilibria and a mixed strategy equilibrium. To find the mixed strategy equilibrium let the probability that player A uses strategy U bepand the probability that player B uses strategy L beq. As we learned in our analysis of penalty kicks, if a player uses a mixed strategy (one that is not really just some pure strategy played with probability one) then the player must be indifferent between two pure strategies. That is the strategies must have equal expected payoffs. So for player A to use a mixed strategy, player Bs probabilities of playing L,q, and R, 1q, must be such that player As two pure strategies have equal payoffs.]
(2)FindallNash equilibria for the game described by the payoff matrix in Figure 4. Provide a brief explanation for your answer.
Player A
Player B
L R
U 1 , 1 4 , 0
D 3 , 0 2 , 1
Figure 4: The payoff matrix for Question (2).
(3)All of our examples of games had only two strategies for each player, but the concept of Nash equilibrium also applies to games with many strategies for each player. In this question we will consider a two-player game in which player A has four strategies and player B has three strategies. The matrix below describes the payoffs to these strategies. A Nash equilibrium is still a pair of strategies that are best responses to each other.
Player A
Player B
L M R
r 4 , 5 1 , 0 3 , 3
s 1 , 9 2 , 1 4 , 6
t 3 , 4 5 , 0 7 , 6
u 2 , 0 8 , 3 1 , 1
Figure 5: Payoff Matrix for Question 3
(a)Does either player have a dominant strategy? If so, which player(s)? Explain briefly (1-3 sentences). (b)Is there a strategy that player A should not use as there is another strategy that always (regardless of what player B does) yields a higher payoff? Is there a strategy that player B should not use as there is another strategy that always yields a higher payoff, regardless of what player A does? (c)Find all pure strategy Nash equilibria for this game. [Your answer to part (b) should be helpful in answering this question.]
(4)In this problem we will consider an attack-defense game. (This particular game is a simple version of the Colonel Blotto game which was first proposed byEmile Borel in 1921.) There is a military battle taking place at two nearby mountain passes, which well call A and B, and two Colonels from opposing armies are directing the battle. One Colonel theattacker is trying to break through at least one of these mountain passes to the territory beyond, while the other Colonel thedefender is trying to prevent this from happening. The defender has to decide which of the two mountain passes to reinforce. His possible actions are to reinforce pass A or to reinforce pass B. He cant defend both passes. The attacker has to decide which pass to attack. He can either attack pass A or attack pass B. He cant attack both passes. The two Colonels make their decisions simultaneously and independently. The attacker wins the game if the pass he attacks is not reinforced by the defender. The defender wins the game otherwise that is, the defender wins if he reinforces the pass that the attacker attacks. Both Colonels obviously want to win. Lets suppose that for each Colonel the payoff to winning iswand the payoff to losing isl(the Colonel who does not win is the loser), with w > l. (a)Set up the payoff matrix for this game. (b)Is there a pure strategy equilibrium? Find all such equilibria, if there are any. (c)Find a mixed strategy equilibrium. (d)Your answer to part (c) should not depend on the values ofw andl (as long as w > l). Can you explain why the actual values ofwandldo not affect the probabilities for the mixed strategy in (c)?
(5)One hundred travelers begin in city A and must travel to city B. There are two routes between A and B. Route I begins with a local street from A to C that takesx/5 hours per traveler on it wherexis the number of travelers on the street, and then is followed by a highway from city C to city B that takes 5 hours of travel time per traveler regardless of the number of travelers on it.
Route II begins with a highway from A to D that takes 13 hours per traveler regardless of the number of travelers on it, and then is followed by a local street from city D to city B that takesy/25 hours of travel time per traveler whereyis the number of travelers on the street. Both routes I and II use only one-way roads. (a)Travelers simultaneously choose which route to use. Find Nash equilibrium values of xandy, and either provide calculations for your answer or explain your answer. (b)Now a one-way highway is constructed running from city C to city D. The C to D highway requires 0 hours of travel time per traveler regardless of the number of travelers who use the road. Letvbe the number of travelers who use the C to D road. Find a Nash equilibrium for this new road network. Be sure to specifyv, xandy and either provide calculations for your answer or explain your answer.
(6)One hundred travelers begin in city A and must travel to city B. There are two routes between A and B. Route I begins with a road from city A to city C which takesx/20 hours of travel time per traveler, wherexis the number of travelers who use it. It ends with a highway from city C to city B which takes 1 hour of travel time regardless of the number of travelers on it. Route II begins with a highway from city A to city D, which takes 8 hours of travel time regardless of the number travelers on it. It ends with a street from city D to city B which requiresy/50 hours of travel time per traveler, whereyis the number of travelers who use it. All roads are one-way roads. (a)Travelers simultaneously chose which route to use. Find Nash equilibrium values of x and y. (b)Now the government builds a new highway directly connecting cities A and B. The travel time per traveler on this highway is 5 hours per traveler regardless of the number of travelers who use it. Letzbe the number of travelers who use this new route. Find a Nash equilibrium for this new road network. Be sure to describe x, y and z.