Congratulations to Roth and Shapley and John Novak

Posted by Chad Orzel on October 15, 2012
(1)
More »

The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel has just been announced, and goes to Alvin E. Roth and Lloyd S. Shapley “for the theory of stable allocations and the practice of market design.” I know basically nothing about these guys, but I assume they’ve earned their Sveriges Riksbank Prize, so congratulations to them. And congratulations also to John Novak, who correctly called Shapley in the annual betting pool.

I think that’s all the winners for this year, both of Nobel Prizes and from the betting pool. If I missed one, please point it out to me. And if you won a prize in the betting pool, send me email to claim it.

(1)
More »

Comments

  1. #1 John Novak
    October 15, 2012

    First, last, and only time I will see my name on the same headline with Nobel Winners.

    I’m not as familiar with Roth as I am with Shapley, but Shapley is one of those guys that it’s sort of inconceivable that it took this long to get a Nobel Prize– Shapley is game theory, and game theory is economics. You really can’t study game theory without tripping across his name, like you do with John Nash.

    The Bondareva-Shapley theorem, the Shapley value, and the Shapley-Shubik index are all named for him (and collaborators.)

    The first is a characterization of when all players in a coooperative game can (“should”) cooperate, vs when sub-coalitions will form and exclude other players. The second is a description of how much a player in a coalition can “demand” of his fellow coalition members when splitting up the profits. The Shapley-Shubik index is a description of the power of particular voters in particular voting games.

    Those are the named results I’m familiar with off the top of my head, and you can probably see the thread of the research: It’s all about distribution of power and rewards in cooperative, non-zero-sum games.

    In less detail, I know he was instrumental in developing utility theory in general (after von Neumann and Morganstern) which is one of the cornerstones of modern Artificial Intelligence– assigning utility functions to agents, in terms of rewards and penalties, turns out to be a fantastically effective way to analyze and develop algorithms. If you generalize that far enough, you eventually get to reward functions in noisy environments (where your observations or actions are uncertain) and to noisy games (where you have multiple players acting in such environments.

    The proper name for those are stochastic games, sometimes partially observable stochastic games. Stochastic games, it tuns out, were first developed by, yes, Lloyd Shapley. Back in the 1950s. They also turn out to be powerful descriptions of multi-agent artificial intelligence.

    Now, Lloyd Shapely was not, by any stretch of the imagination, an artificial intelligence theorist. He was an economist and a game theorist. But this does explain why a CS/AI geek would even know about him, much less think of him as a pick for a Nobel Prize– his ideas are profound and powerful enough to revolutionize not just his own field of economics, but a field which effectively didn’t even exist (artificial intelligence) when he was publishing some of his best work.

    And that’s just the work of his I’m familiar with– wikipedia will show a hell of a lot more.

    Roth, unfortunately, I’m familiar with, but not as familiar. I think of him as the kidney matching chain guy, where the idea is that if you have N patient-donor pairs, none of whom match, you can try to mix and match between them to get larger match sets. (This is one of those things that sounds obvious, but it is illegal to create binding contracts in organ donation, so everything has to happen with a degree of simultaneity that is difficult to achieve.)

    I gather his research has broader applicability to exotic matching markets– I see his name associated a lot with student/school matchings as well– but I don’t think I can say anything more intelligent about it than to go look at his Wikipedia page.