Feeds:
Posts

## Battle of the Students

The Game Theory course that I am teaching is accompanied by weekly exercises which include a so-called G-exercise. G-exercises are games that the students play with or against each other. The (expected) payoff they receive will be accumulated and counts towards their final course grade. Starting with the Prisoner’s Dilemma, these exercises include classics like “Guess 2/3 of the Average“, Centipede, the El Farol Bar game, and an All-Pay Auction.

Last week the students were randomly matched into pairs and were asked to play a variant of the Battle of the Sexes (we slightly changed the payoffs and made the game symmetric).

The students are assigned a private chat channel with their partner and have a couple of days to discuss their strategies. By Saturday Midnight, each student has to privately submit his (possibly mixed) strategy using an online form. Players then directly receive their expected payoff.

Despite its simplicity, this G-exercise turned out to one of the most interesting ones because, over the years, students consistently reinvented solutions concepts such as Stackelberg strategies and correlated equilibrium. At the time the exercise is introduced, the students know about basic concepts such as Pareto optimality, dominated strategies, and maximin strategies. They barely know about Nash equilibrium.

Many students try to agree on one of the pure equilibria. Of course, this turns out to be difficult because of the unfair payoff distribution. Some students are successful in compensating each other (e.g., by offering beers in return for payoff 3). Others aim at evenly dividing the total payoff and agree on randomizing uniformly between A and B. This gives both players an expected payoff of 1, but obviously suffers from the fact that it’s not an equilibrium. So in some cases, players agree to play 50:50, and then one of them (or both!) eventually submit A. In the latter case, they both get no payoff. Some students succeed in computing the mixed equilibrium (3/4 A + 1/4 B), share it with their partner, and submit their strategies. This yields an expected payoff of 3/4 for both players. However, playing the maximin strategy (1/4 A + 3/4 B) guarantees exactly the same payoff no matter what the other player does. Many students seem to realize this and play the maximin strategy instead. A perhaps unexpected tactic by many players is to try to turn this into a sequential game by committing to strategy A:

Good morning,

I have already submitted strategy A (see the attached screenshot). I will be on a hiking trip over the weekend and won’t have Internet access. You can maximize your payoff by choosing B.

Have a nice weekend!

This Stackelbergian bully strategy works surprisingly well (although the screenshot cannot serve as a proof; players can revise their strategies as many times as they like until the deadline).

Finally, a handful of students reinvent the concept of correlated equilibrium. Frustrated by the fact that any real randomization will put positive probability on the undesirable (0,0) outcomes, they decide to randomize between the two pure equilibria. For example, they meet in the cafeteria and throw a coin that decides which pure equilibrium is played. This year, there was a public holiday shortly before the submission deadline, which prevented some students from meeting in person. They therefore designed elaborate mechanisms (correlation devices) to simulate the coin flip, e.g., by checking the timestamp of the first article appearing on a national news website on a given day or by adding their student ID numbers and observing whether the last digit of the sum is odd or even.

These are the little things that make teaching worthwhile.

PS: The final statistics were as follows:

### One Response

1. Dear Professor,

I have found a new complexity class that I called “equivalent-P” and I have showed it has a close relation with the P versus NP Problem. I have been making a paper that explain my ideas, and in the meantime, I decided to share them as a preprint in the web.

Here, I show you the abstract of the paper (so you can capture the idea):

“The P versus NP problem is one of the most important and unsolved problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by Kurt Gödel to John von Neumann in 1956. However, the precise statement of the P versus NP problem was introduced in 1971 by Stephen Cook in a seminal paper. We consider a new complexity class, called equivalent-P, which has a close relation with this problem. The class equivalent-P has those languages that contain ordered pairs of instances, where each one belongs to a specific problem in P, such that the two instances share a same solution, that is, the same certificate. We demonstrate that equivalent-P = NP and equivalent-P = P. In this way, we find the solution of P versus NP problem, that is, P = NP.”

In this preprint, I shall show that there is an NP-complete problem in equivalent-P and a P-complete problem in equivalent-P. Moreover, I shall show the complexity class equivalent-P is closed under reductions. Since P and NP are also closed under reductions, then we can conclude that P = NP.