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!

Advertisement