Feeds:
Posts

## Sandy and STOC

The deadline for submissions to STOC has been extended to Monday, Nov 5 2012 5:00 p.m. EST. The change has been announced on the STOC submission website.

## Russell Crowe was wrong

Yesterday I taught the first of five algorithmic economics lectures in my undergraduate AI course. This lecture just introduced the basic concepts of game theory, focusing on Nash equilibria. I was contemplating various ways of making the lecture more lively, and it occurred to me that I could stand on the shoulders of giants. Indeed, didn’t Russell Crowe already explain Nash’s ideas in A Beautiful Mind, complete with a 1940’s-style male chauvinistic example?

The first and last time I watched the movie was when it was released in 2001. Back then I was an undergrad freshman, working for 20+ hours a week on the programming exercises of Hebrew U’s Intro to CS course, which was taught by some guy called Noam Nisan. I didn’t know anything about game theory, and Crowe’s explanation made a lot of sense at the time.

I easily found the relevant scene on youtube. In the scene, Nash’s friends are trying to figure out how to seduce a beautiful blonde and her less beautiful friends. Then Nash/Crowe has an epiphany. The hubbub of the seedy Princeton bar is drowned by inspirational music, as Nash announces:

If we all go for the blonde, we block each other. Not a single one of us is gonna get her. So then we go for her friends, but then they give us the cold shoulder because nobody likes to be second choice. Well, what if no one goes for the blonde? We don’t get in each other’s way, and we don’t insult the other girls. That’s the only way we win. … Adam Smith said the best result comes from everyone in the group doing what’s best for himself, right? … The best result would come from everyone in the group doing what’s best for himself and the group!

But if no one goes for the blonde, wouldn’t a player gain from deviating to the blonde, without making others worse off? This game has Pareto efficient Nash equilibria (one player goes for the blonde, the others go for her friends), but the strategy profile advocated by Crowe is not Pareto efficient, nor an equilibrium.

Nash concludes by proclaiming “Adam Smith was wrong!” Maybe, but so was Russell Crowe.

## STOC Submissions: message from the PC Chair

Joan Feigenbaum, the PC chair for STOC 2013 would like to urge all those submitting (deadline: November 2nd) to pay attention to the new submission instructions, which are not what we are used to.  In particular, “we strongly suggest that you create your user account on the submission server NOW…”and “Length and formatting requirements will be enforced strictly and literally”.

## Annual Crowdsourced Jobs Post

The academic hiring season is starting again, and as a service to the AGTE/econ-cs community we’d like to provide a place for advertising new research positions in the field.  This includes academic positions as well as industrial research ones, permanent and postdoc positions, in all areas related to the border between CS and game-theory and economics (interpreted widely).  Please post any such open position announcements as comments to this thread.

## Workshop on The Economics of Web Search and Social Networks

Workshop on The Economics of Web Search and Social Networks will be held in Rome on February 4th 2013 in conjunction with the   Submission deadline: Nov 15th.

## Al Roth and Lloyd Shapley

Congratulations!

Some more from our corner of the blogosphere: Al himself, Lance, Gans, Mallesh.

## Wildly cited algorithmic economics papers

Here on Turing’s Invisible Hand we make it our mission to address the most profound questions of algorithmic economics. This post fearlessly tackles one of those timeless questions: “Which are the 10 most cited algorithmic economics papers?”

Methodology

I searched on Google Scholar for the names of researchers who I thought were likely to be highly cited, and checked out their highly cited algorithmic economics papers (see discussion). To be eligible, a paper has to be:

1. A research paper. For example, Papadimitriou’s Algorithms, Games, and the Internet is not eligible.
2. Published in a CS conference or journal. For example, the Edelman et al. GSP paper is not eligible.

I tabulated eligible papers with more than 500 citations to obtain a ranking. The information was recorded roughly a week ago.

Results

1. 1210 citations: Maximizing the spread of influence through a social network (Kempe, Kleinberg, Tardos)
2. 1203 citations: Worst-case equilibria (Koutsoupias and Papadimitriou)
3. 1150 citations: Algorithmic mechanism design (Nisan and Ronen)
4. 1043 citations: How bad is selfish routing? (Roughgarden and Tardos)
5. 1035 citations: Algorithm for optimal winner determination in combinatorial auctions (Sandholm)
6. 605 citations: The Michigan Internet AuctionBot: A confi gurable auction server for human and software agents (Wurman, Wellman, Walsh)
7. 600 citations: Incentives for sharing in peer-to-peer networks (Golle, Leyton-Brown, Mironov, Lillibridge)
8. 599 citations: A market-oriented programming environment and its application to distributed multicommodity flow problems (Wellman)
9. 560 citations: Truth revelation in approximately efficient combinatorial auctions (Lehmann, O’Callaghan, Shoham)
10. 518 citations: a tie between Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches (Fujishima, Leyton-Brown, Shoham) and Robust incentive techniques for peer-to-peer networks (Feldman, Lai, Stoica, Chuang)

Discussion

Apart from its general stone-age level of sophistication, the methodology has several specific shortcomings. First, in some cases the the journal version of a paper does not have the same title as the conference version. I took this into account in the case of #5, but I may have missed some other instances. Interestingly, the Daskalakis et al. work on complexity of Nash is conspicuously missing from the list. The SICOMP 2009 version has 134 citations, and the STOC 2006 version has 360 citations, so the combined paper almost makes it. To make things more confusing, there is an ECCC 2005 paper that extends the reduction from four to three players, and has 128 citations. Presumably, though, people cited the last paper together with the STOC paper, until the SICOMP paper came along. In any case, no doubt this work will find its way to the top of the list in a few years.

Second, and more importantly, it is of course unclear what counts as an algorithmic economics paper. I guess the criterion I had in mind is something like: if an author gave a great presentation to the well-rested attendees of an algorithmic economics seminar (so the audience is a mix of computer scientists and microeconomists), nobody would fall asleep. This criterion arguably rules out some important AI data-mining-type papers that could be outside the scope of what would keep the economists awake. Hurray, finally we have a clear-cut definition for the field!