# Game theory - Finding Nash Equilibria

i have to solve these questions. I already came up with a solution. Can anyone look over it and state their opinion? Many thanks in advance :)

CHALLENGE I

1. Consider the following game between Sheldon, Leonard, Rajesh, Howard and Penny who all pay €1 to participate. Each player must simultaneously choose a number (integers) between 1 and 100. All aim to win the game by outguessing one another. The person that is closest to 1/3 of the average of all guesses wins €100. The others get nothing. In case of ties, the €100 is split equally between the winners. This game has a unique Nash equilibrium; what is it and why?

1) The number of Nash Equilibria of the game presented in the first question is one. The first thing that comes into the mind of the players should be that the “winning number” is lower than 33 (or in extreme case 33 itself) since all of the higher numbers than 1/3 of 100 are “loosing numbers” for the simple reason that they are higher than 1/3 of the highest number. So now they will have the same game but with a smaller range: 1-33, and if all of the player are thinking in the same way then the new “winning number” would be 11, if they keep going on this reasoning (strong and necessary assumption) the only available solution as Nash Equilibrium is the number 1 since all the others number will be eliminated one by one.

**2. Sheldon, who won the previous game, feels a bit sorry for the “losers”. To get rid of this uncomfortable mood, he wants to offer the others an opportunity to win back part of their submission fee. Towards that end, he decides to auction €1. The rules are as follows: (1) The highest bidder wins the €1 and (2) the two highest bidders both have to pay their bids to Sheldon. Leonard and Penny are both eager to win back part of their money and Leonard places a bid of €0.01. Penny responds with a bid of €0.02. This process of outbidding each other continues until at some point Penny bids €0.98 and Leonard responds with a bid of €0.99. Please, answer the following two questions:

(1) Is this a Nash equilibrium? Why or why not?

(2) Recall that Leonard did start the auction with an opening bid of €0.01. In retrospect, was it wise of Penny to respond with a bid of €0.02? Explain.**

2.1) This is not a Nash Equilibrium and never it will. The reasoning behind it is that both of the player keep raising their bid since they don’t want to lose their money and this procedure continues, as we have already seen, until their bidding arrives to $0,99\$ $, in favor of Leonard. Now Penny obviously does not want to lose its$0,98\ and would prefer to pay $1\$ $for$1\, that will lead to an offer of $1\$ $from Penny. The situation then becomes more complicated. In this way Leonard would lose$0,99\ if he does not raise the bid, and he would prefer to pay $1.01\$ $and lose just$0,01\ winning the bidding than obviously lose $0,99\$ $, and then it comes his offer. This reasoning can go on until the end of the day and for them would always be better do another offer and “lose less” than stop the bidding. 2.2) It wasn’t wise at all, since it led to the situation discussed in the point 2.1. It would have been better for Penny to bid directly$0,99\, in this way she would have not arrived at the uncomfortable situation discussed before, and she would have gained at least $0,01\$ $(coming out with a slight prize, but still far better off than the previous situation). However, if possible an even better decision would have been to not bid and share the profits, in that case it would have been$1-0,01= 0,99$;$0,99/2 = 0,495$for both. In addition, they should request Sheldon to play this game repeatedly but only If they agree on not biding. Because from the point onwards if the lower bid reaches$0,50 \ Sheldon makes profit, whereas penny and Leonard are less likely to make profits if they try to outbid each other.

• First question: I aggree with you, that 1 is the nash-Equilibrium. A general advice: It is not a good idea to post several exercises, especially if they have so much text. You should split your question into 2-3 seperate questions. – callculus Sep 18 '15 at 8:51

On part $1$, your proof is wrong both in spirit and in detail. You seem to be reasoning about the players' thought processes; at least you're using language that seems to imply that. A Nash equilibrium has nothing to with the players' thought processes; it's defined entirely objectively as an equilibrium in which no player could profit from switching strategies. Most of your proof could be translated into objective language about the expected values of strategies, but there's also one substantial error: The numbers from $33$ to $100$ aren't losing numbers. If all five players choose $100$, $100$ is a winning number.

Here's how I'd write the proof: Assume that some player, say, Raj, has a non-zero probability to play $100$. If all other players also have a non-zero probability of playing $100$, Raj can improve his expected payoff by playing $99$ instead of $100$: This makes him better off if all others play $100$, and at least not worse off otherwise. If not all other players also have a non-zero probability of playing $100$, Raj's expected payoff if he chooses $100$ is $0$, whereas there is some smaller number for which he'd have positive expected payoff (you'd have to prove this, but that shouldn't be too hard). Thus, in either case, Raj can profit from switching strategies. It follows that in a Nash equilibrium none of the players has a non-zero strategy of playing $100$.

Also, none of the players can ever profit from switching to $100$. It follows that we can ignore the option of playing $100$. But now we can apply this reasoning iteratively, as you did in your proof, eliminating $99$, $98$, ..., until only $1$ remains. Thus in a Nash equilibrium no player has a non-zero probability for playing any number other than $1$, so the only Nash equilibrium is the pure-strategy equilibrium in which all players play $1$ with probability $1$.

In part 2, the question is very badly posed. It describes a sequence of moves and not a strategy, so the question "Is this a Nash equilibrium?" makes no sense, since a Nash equilibrium is a strategy profile and not a sequence of moves. It's not clear which strategy profile leading to this sequence of moves is implied. (A strategy includes what to do at every potential stage of the game, not just at the actual stages of an actual instance played.) Another problem is that the game is not finite, but the payoffs are only defined for cases in which the game ends after a finite number of bids. To complete the definition of the game, it would have to specify the payoffs also for infinite sequences of bids (or introduce some limit on the bids).

To remedy these problems, we might assume a) that the payoff for infinite sequences of bids is $-\infty$ for the players bidding infinitely often and $0$ for the remaining players, and b) that the implied pure strategy profile presented as a Nash equilibrium candidate is given by "start the bidding with a bid of $€0.01$" for Leonard, "if you don't have the highest bid, bid $€0.01$ above the highest bid, unless you'd be bidding $€1.00$ or more" for both Leonard and Penny, and "don't bid" for Howard and Raj. (In your analysis, you talk about Leonard and Penny continuing to bid beyond $€1.00$, but I interpret the question such that it specifies all bids made and there are no further bids.)

With these assumptions, this strategy profile is not a Nash equilibrium, since e.g. Penny could improve her payoff either by going on to bid $€1.00$ or by stopping to bid at any earlier stage.

That leaves the question of finding other Nash equilibria. One equilibrium is where Howard starts the bidding with $€0.01$ and threatens to bid indefinitely if anyone bids against him (this is just the sort of annoying thing that Howard might do) and no one else bids. (By "Howard threatens", which sounds a bit like your subjective language, I mean that Howard's strategy specifies that this is how he plays, so it's an objective fact about his strategy.)

This is a Nash equilibrium since Howard wins the prize at minimal cost, so he can't profit from switching, and everyone else could only switch either to bidding a finite number of times, paying their last bid but not getting the prize, or to bidding an infinite number of times, for an even worse payoff of $-\infty$.

• Thank you very much for your extensive answer. I agree with 1 and 2.1 but I came up with another solution for 2.2 – Maxime Sep 20 '15 at 19:25
• As Penny’s intention of participating in this auction is to win back at least some of her money, it was not clever of her to respond with a bid of €0.02. Since you can only place a bid in exchange with your auction partner (that is, with Leonard), Penny can only have even bids, while Leonard submits the uneven bits. This is what makes her end up in a situation of having €0.98 as her last bid against Leonard’s bid of €0.99. – Maxime Sep 20 '15 at 19:26
• Now that Leonard has already placed his bid of €0.99 cents, Penny has foregone the opportunity of gaining back at least some money from the previous game. All she can do now is trying to minimise her losses of this auction, as it is described in 2.1. That this was going to happen should have been clear to her all along - even having placed her very first bid of €0.02. Therefore, her decision to respond with a bid of €0.02 in the first place was not wise. – Maxime Sep 20 '15 at 19:26
• In total, it is not wise to enter the game at all if only two players will play, as in this situation, the game will always go the way as explained in 2.1. Therefore, after Leonard already made his bid, Penny should not enter the game at all. – Maxime Sep 20 '15 at 19:27
• @Maxime: None of that makes any sense if you don't fill the gaps in the definition of the game that I pointed out. – joriki Sep 21 '15 at 9:53