The Tel Aviv Workshop

Kudos to Eilon for organizing this great workshop. It was exciting to see the lecture hall in the English Literature building full every time I entered, and completely packed for Aumann’s talk. I had to sit on the stairs, as I used to do during my grad years when I was auditing rock-star professor Jerome Mandel’s Medieval English class and found out that the entire university were coalescing there to watch him performing the green knight’s entrance to King Arthur’s court. I only came to the afternoon sessions and still managed to attend talks about stochastic games, repeated games, implementations, auctions, coding, matching, decision theory, bounded rationality. I expected to meet mostly the math game theory community, but I recognized only a small fraction of the participants, who came from econ, math, cs, social sciences, philosophy. Is there any other discipline where a workshop can interest such a wide audience ? and is there any other discipline where a workshop in Israel can attract so many people from out of the country, including some of the big shots ?

I hear I missed an entertaining “ game theory whither” roundtable discussion. I am usually disappointed with these events, since all the seniors agree with each other about everything, and are often wrong about it to boot. But rumor has it that this time was different. The issue seems to have been the importance of cooperative game theory. One discussant suggested that a way to measure the impact of a topic is its coverage in textbooks, and a certain book was mentioned in which the core, Shapley value and bargaining are not even mentioned. I like this suggestion because of its circular nature: game theorists evaluate game theoretic ideas according to the impact they make on the same theorists who also produce these ideas. Wouldn’t life be easier if game theory was applicable for building bridges or curing cancer or making money in the stock market ? Easier perhaps, but not as interesting in my view. Anyway, the suggestion has caused some intellectual controversy. No food fight, but sufficiently close to be interesting.

And speaking of food, the humus you get in the cafeteria near the law school is an offense to all taste and decency, though non-Israelis still enjoyed it (no surprise, it’s still better than what you get in the states under `humus’). If you go to Jerusalem, Lina (just near the via dolorosa, where Jesus of Nazareth has walked twenty centuries ago) was pretty good. The best of the best is Ali Karawan in Jaffa, but I didn’t get to go there this time. And speaking of Jaffa, Rann Smorodinsky got our everlasting admiration for suggesting Haj Kahil for dinner. And btw, Rann didn’t invent Kalai-Smorodinsky bargaining solution when he was six, as somebody suggested to me. That Smorodinsky is the father.

A word about Aumann’s talk: He presented his argument in favor of correlated equilibrium, following his seminal 1987 paper and a more recent paper (pdf) in which he considers the interim stage, after the players receive some information, and asks what payoff  they can rationally expect to receive in the game. (The paper is quite known for his previous ambitious title “when all is said and done, how should you play and what should you expect”). Aumann starts by claiming that game theory should not tell you what to do (as in “play the Nash Equilibrium”) but should only tell you which procedure to follow, and the procedure is to maximize utility with respect to your beliefs. Presumably many readers of this blog are already aware of Aumann’s argument, so i’ll cut directly to the chase. The dubious part is the common prior assumption. To justify it Aumann appeals to a rational expectation argument. John Muth defined “rational expectations” as expectations that are the same as the predictions of the relevant economic theory. This is a seminal concept which in a way captures the essence of game theory and perhaps economics in general: The economic agent, the subject matter of economic theories, takes into account to the predictions of the theories. Whatever theory an economist uses to make predictions, the economic agents already respond to the same theory; Economists are no smarter than their subject matter (contrast with physicists who presumably are smarter than electrons.) But back to Aumann’s point: The prediction of the theory is, says Aumann, the common prior. But I have two reservations here: First, didn’t Aumann say that game theory doesn’t tell you what to do but only which procedure to follow ? So how come the common prior is a prediction about what players believe and what they do ? Second, there are many correlated equilibria in the game, so many possible predictions of the theory. How do the players know which one of them to respond to ?

Let me mention another presentation, by Michael Rabin, whose 1957 paper about computability in game theory I will take with me to a desert island . Rabin presented a simple (“even financiers understood it”) scheme for conducting seal bids auctions which preserves the secrecy of the bids but enables the auctioneers to prove to all participants the truthfulness of the outcome (pdf ). So for example in a second price auction, the auctioneer will verifiably announce the identity of the winner and inform the winner about his price without revealing any information to anybody else. What I found unsatisfactory in this paper — and this is not a criticism of the paper since it is probably completely unrelated to it goal — is the fact that it has nothing to do with game theory: the strategic aspects of auctions are irrelevant here. To my understanding, this is a paper about verifiable computation of a function when the input is distributed between several agents. Auctions are just an example. This is cryptology at its best, but I wish we would see some papers where cryptology is directly relevant for game theory.

Oh, and I need to register a caveat to my previous insinuation that you cannot make omelets out of game theory. Matching theory is an exception. Nobody will suggest to look at game theory textbooks to evaluate the importance of Gale Shapley, since this algorithm and its variations are actually used in real-life situations like assigning med grads to hospitals, kidney pair donation, matching students to public schools. Matching theory lives outside the GT-community circulation of ideas. There were two great matching talks in the workshop, one of Itai about two body problem in the residency program and one by Federico about testable implication of stable matching with and without monetary transfer from aggregate data.

Photos ? Unfortunately I didn’t take any during the workshop. But we have some from the trip. Here is one taken by Itai Ashlagi.
See if you can identify the location and the participants

That’s it folks, thanks to everybody who encouraged me to blog more. Will try.

A post on Rabin

I wrote some time ago about Michael Rabin’s example of how a backward induction argument is killed when you require players’ plans to be computable. Since Rabin’s paper is not available online, I intended to post the proof at some point, but never actually got to do it. Richard Lipton’s post about Emil Post is a good inspiration to pay that debt since the concept of simple set, which was introduced by Post, has a role in Rabin’s example.

A set is simple if is recursively enumerable and its complement is infinite and contains no infinite recursively enumerable subset.

For Rabin’s purpose, what matters is that Post proved the existence of such a set. So Post provides us with a code of a computer program that enumerates over all the elements of and such that no computer program can produce infinitely many elements that are not in . By the way, Post introduces the concept of simple set while working on his eponymous problem which Richard mentions. In fact, if is simple set then is not many-one equivalent to a universal recursively enumerable set.

Now let be a simple set and consider the following three-round game with perfect information. At each round a player announces a natural number (an action): First Alice announces . Then Bob announces and then Alice announces . After the game is played, a winner is determined as follows: Bob wins if and is not the -th element in the enumeration of . Otherwise, Alice wins. Therefore, determining the winner is a task that can be effectively done using the code provided by Post.

Does any of the players have a strategy that guarantee winning regardless of how the opponent play ? The answer to this question depends on which mathematical creature you use to model the intuitive notion of `strategy’.

If by a strategy you mean just a function from histories to current action then Bob has a winning strategy: for every that Alice might chose in the first round there exists some such that , since the complement of is infinite.

But if you think of a strategy as a complete set of instructions, that is a plan or an algorithm that will tell you how to produce your next action given the past, then you want to model a strategy as a computable function. Now, for every computable function that Bob can chose, there exists some such that either or since otherwise would have been a recursive enumeration of infinitely many elements of . In particular, there exists some such that if Alice plays in the first stage and in the third stage she wins against . So, Bob has no winning strategy.

Computability in game theory

Since in the near future I will have to start advocating a computability argument, and since this position is somewhat in contrast to what was my view a couple of years ago when I first came across algorithmic game theory, I thought I should try to clarify my thoughts about the issue in a couple of posts.

The most beautiful example I know for the surprising outcomes we get when taking computability into account in game theory is Michael Rabin’s paper from 1957. Rabin considers a finite win-loss game with perfect information between two players, Alice and Bob. The game is played in three rounds, at each round a player announces a natural number (an action): First Alice announces . Then Bob announces and then Alice announces . After these declaration are made, the game coordinator determines the winner: If Alice wins. If Bob wins. The set , Alice’s winning set, is part of the description of the games. This is a finite game, which can be solved by a background induction. By the so called Zermelo’s Theorem, the game is determined: One of the player has a winning strategy. The identity of the winner depends of course on .

Rabin gives an example for a game with the following propertie:

1. is a decidable set: this means that there is an effective way to decide, for every triple whether or not . So the job of the game coordinator in this game can be performed by a computer program. Games with effectively computable payoff are called actual games: These are the games that can actually be played.
2. Bob has a winning strategy : whatever actions and Alice chooses in the first and third stages, Bob will win the game if in the second stage he chooses : so that for any
3. Bob has no computable winning strategy: For every function that can be computed by a computer program there exist some actions for Alice such that .

Feel the blow ? Bob finds himself in a strange predicament. On the one hand, after observing Alice’s action from the first round, Bob knows that there is some action he can choose that beats any possible response of Alice. However, if Bob tries to `plan ahead’ which action to take after every possible choice of , he cannot produce such a plan. Bob can beat all Alice’s strategies and Alice can beat all Bob’s (computable) strategies. von-Neumann and Morgenstern’s least controversial idea, solving a zero-sum game with perfect information by backward induction, trembles. The argument that in finite zero-sum games with perfect information a player doesn’t care if the opponent finds out his strategy falls apart.

(To be continued…)