Questions for Paolo Galeazzi

Posted on January 26, 2017

Jan van Eijck

photograph: Peter van Emde Boas

photograph: Peter van Emde Boas

On Wednesday Jan 25 was the PhD Thesis defense of Paolo Galeazzi. The thesis, Play Without Regret, is about Game Theory and Decision Theory, and it is a remarkably mature piece of work. Paolo does not only show mastery of these two disciplines, but he also has a clear perspective on how the disciplines relate, on where the area is going, and on what can be learned from these disciplines when we reflect on things that really matter. The defense went splendidly, which was also felt by the audience, for when the promotion committee left the aula for deliberation we could hear a spontaneous round of applause.

The interaction during the question and answer session made clear that the committee members were all impressed by the exceptional quality of the thesis. In many places abroad this thesis would have earned a special distinction or cum laude. The mathematical sciences in Amsterdam have decided quite a while ago to abolish this, on the grounds that the cum laude distinction is subject to inflation. Paolo would have earned the cum laude accolade almost everywhere but here in Amsterdam.

As a member of the thesis committee, I had prepared a number of questions for Paolo. I had taken part in the Workshop on Rationality, Logic, and Decisions which took place the day before the defense, where I was one of the speakers. Here is a link to the slides of my talk. Unfortunately, I had to leave early, so I had to miss the closing talk by Paolo. I had promised to cook dinner for my family, and that is why I did not know that the key example of Paolo’s talk was exactly the example of my first question. As a consequence of this, I wasted a lot of time explaining the example in detail, even telling the audience that the purpose of my explanation was to get everyone in the room in the know. Well, more than half of the people that were present at the defense had also attended the workshop. Malvin Gattinger told me later that he felt sorry he had no means of signaling me.

photograph: Peter van Emde Boas

photograph: Peter van Emde Boas

Now I have to assume that not all readers of this were present at the workshop or at the defense, so I will have to explain the example again. Fortunately, readers can skip where listeners can only look bored. But this was one thing Paolo could not afford to do in the circumstances. Instead, he listened intently to my explanation.

I also wasted time on flourishes and compliments, by the way, but that is a customary thing to do. Next, I remarked that I saw a certain tension in the thesis between the normative and the descriptive perspective on game theory. Does evolutionary game theory describe how rational agents, humans, in fact behave when they interact (or interact repeatedly) in an environment consisting of other rational agents of certain types? Or does the discipline describe how rational agents should behave, given certain goals, and given a context of other agents with other goals?

You see the same tension in logic. Logic is normative: it describes how ideal rational agents should reason. At the same time it sheds light on how human beings in fact reason. It can explain, e.g., why certain inferences are harder than others, which is then confirmed by observations about how humans perform on certain reasoning tasks.

My intention was to present three examples where this tension surfaces, but as said, I did not get further than the first. In the examples, the tension is between how people really behave on one hand, and what game and decision theory have to say about this on the other hand.

OK, here is the first example: the travelers’ dilemma. Dear reader, ship this, please, please, if you already know it. Others, please read on, for the example is quite interesting, really. Imagine two passengers A and B of an airline company that both have lost a suitcase. For the purpose of the example, imagine that the suitcases are identical. Imagine they have the same worth. Imagine also that the airline company knows this. The airline company proposes the following game. A and B should both fill in a form stating the value of their suitcase, say in a range from 180 to 300 euros. If A and B state the same value, they both get what they claimed. If they state different values, the player who claimed the lowest value, say V, will get V plus a bonus of 25 euros. The other player gets V minus 25 euros.

If you are familiar with game theory, you can calculate that the Nash equilibrium of this game is a claim of 180 euros. If you don’t know game theory, you will not even know what a Nash equilibrium is. So let me explain. Readers who know this should know by now what to do. Nash equilibrium is named after the American mathematician John Nash, who some of you may know from the movie A Beautiful Mind. In a game for two players, where both players have indicated the move that they are going to play, this pair of moves is a Nash equilibrium if it is the case that neither of the two players can improve her pay-off by unilaterally diverging from her choice. The travelers’ dilemma is a two player game. Consider the case where both players claim the maximum amount of 300 euros. Then player A can improve her payoff by claiming 299 euros instead of 300, because this will get her 299+25=324 euros instead of 300. But then player B can undercut this by claiming 298 euros. And so on, until the players reach rock bottom at 180 euros. If both players claim 180 euros, then neither player can improve her payoff by unilaterally deviating from this. So (180,180) is a Nash equilibrium for the travelers’ dilemma game.

Now if the game were offered to me, I would reason as follows. “This game sucks. They should have offered the average of the two claims. But you know what? I am going to claim the maximum amount, and just hope that the other guy is not a sucker who believes in game theory. Then the two of us can teach them a lesson.” Interestingly, that is how many people seem to behave. Ariel Rubinstein commented on this (cited in Paolo’s book at the beginning of the final chapter): “I am not aware of any game theoretical model that can, in fact, explain this.”

So my question to Paolo: can your theory explain this? And does game theory in general, or your theory in particular, have anything useful to say about how the agents should behave in this kind of situation?

Paolo’s answer was a reference to an alternative solution concepts for strategic games proposed not too long ago (2011) by Joe Halpern and Rafael Pass: elimination of strategies that minimize regret, in the sense of “I wish I had claimed amount X instead of my actual claim”. This works different from Nash-style reasoning, for now we have to assume that we do not know the claim of the other player. So assume A claims X and does not know the claim Y of B. This claim might be 300. In this case A receives X + 25, but could have received 299 + 25 had she played 299. So the maximal regret is 299 - X. Paolo referred to this in his answer, and the reference is also in his thesis. But this does still not explain the tendency of players to “jump out of the game” by putting the maximum claim.

At this point in the exchange I was stopped by Peter van Emde Boas, the chair of the session. My question time was over, much to my regret, as I still had two example game situations in store that I wanted to quiz Paolo about. Well, never mind. Here they are.

This is an example from real life, my personal experience. Some 25 years ago I was selling a house in Cambridge. A house with lots of character, bay windows in front, open fire places in all the rooms, a large garden with an old air raid shelter still in place at the back, and it was in a very nice location. The address was 33 Emery Street, for those who know Cambridge. A house that I loved. There was a quite lot of interest, and one of viewers was a particularly nice man. He told me that he loved the house, and that he was going to make me a good offer. He just had to inquire with his bank what he could afford. Later the estate agent called me to say that the offer was made. The offer was 10 percent below the asking price, but his advice was to accept. I was quite pleased with the offer, and I liked the guy, so I told my estate agent that I accepted. The next day, my estate agent called me again. “Mister Van Eijck, I have good news for you. There is another ten thousand pounds for you to be made. I have a client here who is willing to pay the asking price.” “But I have given my word.” “Oh, that is not a real problem. There is nothing on paper yet, and according to British law nothing is binding until there is a written agreement.” The question I would have liked to have asked Paolo: can game theory give useful advice for my next move in this game?

Final example. A Zen story. My note on this already said: only if there is time. Fishermen in a poor village find a dead body in the sea. They infer from the rich clothing that this must be the son of a rich family. They locate the family and ask a huge sum of money in return for the body. The family of the drowned man go to a Zen monk and ask for advice, for they they think the fishermen ask way too much money. The monk says: “Any amount of money you offer should be good enough. After all, they cannot sell to anyone else.” The mourning family tells this to the fishermen, but this does not resolve the issue. So the fishermen also go to the monk. The monk says: “You can ask any amount of money you want, because you have something to sell that they can buy from no-one else.” After that, the monk is silent.

OK, we do not know what Paolo would have said, but to me, these “games” seem to indicate that the essence of play is that we can change the rules in the course of the game. That is the kind of play that Plato had in mind, it seems to me, when he said that you can discover more about a person in an hour of play than in a year of conversation. Motto of Chapter 6 in Paolo’s dissertation. The Thesis has very nice mottos for every Chapter, by the way. It pleases me to think that Plato meant play in the way in which a mother plays with her baby, or in the way children play, or in the way a lover plays with his beloved.

In the final chapter of the book, Paolo is trying to come up with a theory of rational behaviour, a kind of anthropology based on game theory. But game theory is in fact about the outcomes of competitions with fixed rules. And isn’t it part of the essence of being human to be able to transcend any set of rules, to jump out of any game? What about our ability to see through the rules? Doesn’t this ability change the games that we are playing? Does the solution of tragedy of the commons situations not lie in the fact that we can reflect on the situation, and as a result of that reflection realize that we have a common interest?

That is also the point of the Zen story. The story is a very powerful pointer to the four noble truths of Buddhism about the existence of suffering and its causes. The way out of suffering is to transcend the boundaries of the game we are in, to relax, to release, to let go, and be free.

I am very interested in hearing comments to this, of game theorists and of other readers.