Lloyd Shapley

I am not the right person to write about Lloyd Shapley. I think I only saw him once, in the first stony brook conference I attended. He reminded me of Doc Brown from Back to The Future, but I am not really sure why. Here are links to posts in The Economist and NYT following his death.

 

Shapley got the Nobel in 2012 and according to Robert Aumann deserved to get it right with Nash. Shapley himself however was not completely on board: “I consider myself a mathematician and the award is for economics. I never, never in my life took a course in economics.” If you are wondering what he means by “a mathematician” read the following quote, from the last paragraph of his stable matching paper with David Gale

The argument is carried out not in mathematical symbols but in ordinary English; there are no obscure or technical terms. Knowledge of calculus is not presupposed. In fact, one hardly needs to know how to count. Yet any mathematician will immediately recognize the argument as mathematical…

What, then, to raise the old question once more, is mathematics? The answer, it appears, is that any argument which is carried out with sufficient precision is mathematical

 

In the paper Gale and Shapley considered a problem of matching (or assignment as they called it) of applicants to colleges, where each applicant has his own preference over colleges and each college has its preference over applicants. Moreover, each college has a quota. Here is the definition of stability, taken from the original paper

Definition: An assignment of applicants to colleges will be called unstable if there are two applicants and who are assigned to colleges and , respectively, although prefers to and prefers to .
According to the Gale-Shapley algorithm, applicants apply to colleges sequentially following their preferences. A college with quota maintains a `waiting list’ of size with the top applicants that has applied to it so far, and rejects all other applicants. When an applicant is rejected from a college he applies to his next favorite college. Gale and Shapley proved that the algorithm terminates with a stable assignment.

One reason that the paper was so successful is that the Gale Shapley method is actually used in practice. (A famous example is the national resident program that assigns budding physicians to hospitals). From theoretical perspective my favorite follow-up  is a paper of Dubins and Freedman “Machiavelli and the Gale-Shapley Algorithm” (1981): Suppose that some applicant, Machiavelli, decides to `cheat’ and apply to colleges in different order than his true ranking. Can Machiavelli improves his position in the assignment produced by the algorithm ? Dubins and Freedman prove that the answer to this question is no.

Shapley’s contribution to game theory is too vast to mention in a single post. Since I mainly want to say something about his mathematics let me mention Shapley-Folkman-Starr Lemma, a kind of discrete analogue of Lyapunov’s theorem on the range of non-atomic vector measures, and KKMS Lemma which I still don’t understand its meaning but it has something to do with fixed points and Yaron and I have used it in our paper about rental harmony.

I am going to talk in more details about stochasic games, introduced by Shapley in 1953, since this area has been flourishing recently with some really big developments. A (two-player, zero-sum) stochastic game is given by a finite set of states, finite set of actions for the players, a period payoff function , a distribution over for every state and actions , and a discount factor . At every period the system is at some state , players choose  actions simultaneously and independently. Then the column player pays to the row player. The game then moves to a new state in the next period, randomized according to . Players evaluate their infinite stream of payoofs via the discount factor . The model is a generalization of the single player dynamic programming model which was studied by Blackwell and Bellman. Shapley proved that every zero-sum stochastic game admits a value, by imitating the familiar single player argument, which have been the joy and pride of macroeconomists ever since Lucas asset pricing model (think Bellman Equation and the contraction operators). Fink later proved using similar ideas that non-zero sum discounted stochastic games admit perfect markov equilibria.

A major question, following a similar question in the single player setup, is the limit behavior of the value and the optimal strategies when players become more patient (i.e., goes to ). Mertens and Neyman have proved that the limit exists, and moreover that for every there strategies which are -optimal for sufficiently large discount factor. Whether a similar result holds for Nash equilibrium in -player stochastic games is probably the most important open question in game theory. Another important question is whether the limit of the value exists for zero-sum games in which the state is not observed by both players. Bruno Zilloto has recently answered this question by providing a counter-example. I should probably warn that you need to know how to count and also some calculus to follow up this literature. Bruno Zilloto will give the Shapley Lecture in Games2016 in Maastricht. Congrats, Bruno ! and thanks to Shapley for leaving us with some much stuff to play with !

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.