You are currently browsing the tag archive for the ‘matching’ tag.

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.

Follow

Get every new post delivered to your Inbox.

Join 132 other followers