SAGT 2014

The 7th International Symposium on Algorithmic Game Theory (SAGT) will take place in Haifa, Israel, from September 30 to October 2, 2014.  The submission deadline is May 1st, and the Call for Papers is here.  This would be the place to send all your papers that were rejected from EC…

This year, EC will feature three workshops. All of them are inviting contributed papers. I hope you will consider submitting some of your work to one of these!

  1. The Tenth Ad Auction Workshop  (here is the call for papers)
    • Date: June 8, 2014, 8:30-15:30
    • Submission deadline: April 22, 2014, (23:59 Hawaii time)
    • Organizing Committee: adauctions2014@gmail.com
      Itai Ashlagi (MIT Sloan)
      Patrick Jordan (Microsoft)
      De Liu (University of Kentucky)
      Renato Paes Leme (Google)
      Chris Wilkens (Yahoo)
    • Keynote speakers: Hal Varian (Google) and Paul Milgrom (Stanford).
  2. The Fourth Workshop on Social Computing and User-Generated Content  (here is the call for papers)
    • Dates: June 8-9, 2014, 14:00-15:30 on June 8 and 8:30-12:30 on June 9.
    • Submission deadline: April 25, 2014
    • Organizing Committee: scugc2014@easychair.org
      Yan Chen (University of Michigan)
      Yiling Chen (Harvard University)
      Arpita Ghosh (Cornell University)
      Ashish Goel (Stanford University)
      Alex Slivkins (Microsoft Research)
  3. The Second Workshop on Crowdsourcing and Online Behavioral Experiments (here is the call for papers)
    • Date: June 8, 2014, 16:00-18:00
    • Submission deadline: April 30, 2014
    • Organizing Committee:
      Siddharth Suri (Microsoft Research NYC)
      Winter A. Mason (Facebook)
      Daniel G. Goldstein (Microsoft Research NYC & London Business School)


The list of accepted papers for ACM EC 2014 has been posted.

PS: Since I accepted the intimidating invitation below, I’ve been thinking of what my first post should be about. Now I have to admit I took the easy way out. Thanks for letting me participate. I’ll try to think of something more original next time.


Over the last half century, our community has discovered several Chapters from The Book on the theory of algorithms and computational complexity, such as those on randomized algorithms, approximation algorithms, cryptography, and hardness of approximation. (Yes, I agree this sounds Erdosian, but when it comes to our fabulous theory, surely it is justified!)

Spectacular work, much of it done over the last decade, has revealed a new Chapter: on equilibrium computation. The following striking dichotomies, based on these insights, speak for themselves. For the readers’ convenience, all the relevant references have been hyperlinked.


2-Nash k-Nash, k ≥ 3
Nature of solution Rational [1] Algebraic;
irrational example [2]
Complexity PPAD-complete [3]
[4] [5]
FIXP-complete [6]
Practical algorithms Lemke-Howson [1] —?—
Decision version NP-complete [7][8] ETR-complete [9][10]


SPLC utilities PLC utilities
Nature of solution Rational [11][12] Algebraic [12];
irrational example [17]
Complexity PPAD-complete [11] [13] FIXP-complete [14] [15]
Practical algorithms Lemke-based [16] —?—
Decision version NP-complete [11] ETR-complete [14]


SPLC production PLC production
Nature of solution Rational [18] Algebraic [15];
irrational example [18]
Complexity PPAD-complete [18] FIXP-complete [15] [14]
Practical algorithms Lemke-based [18] —?—
Decision version NP-complete [18] ETR-complete [14]


Note: PLC = piecewise-linear concave

SLPC = separable, piecewise-linear concave

In the third table, the utilities of agents are: for all negative results we assume the most restricted utilities, i.e., linear, and for positive results we assume SPLC.

These dichotomies were first identified in [15]. This paper also extends the second and third dichotomies from SPLC to the new class of Leontief-free functions, which properly contains SPLC.

Noam and I

Late last Friday night, after reaching SF airport to take a red-eye to Atlanta, I peeked at my email and found a one-liner from Noam, asking if I wanted to join as a co-blogger. In no time I found myself sending the reply “Happy to join”, then I boarded my flight and immediately snoozed off. After a couple of hours, I woke up sweating and full of anguish: How had I taken this relatively big step with so little thought? Do I have the time, do I have ideas, do I have ways of talking about them, how will I be judged by people, and do I need to put myself through this? Then I was reminded of my (very positive) ventures with Noam, my mind calmed down, and I slipped back into deep slumber.

The year is 1998 or 99, the venue is STOC or FOCS; here is my 30 second conversation with Noam:

Me: I hear you are working in economics these days. How does a top-notch complexity theorist make such a big change?

Noam: That is where the future lies!

Me: Hmmmm?!

Fast forward to March 2001. My book on Approximation Algorithms is almost ready to go to the publishers. I do not want to work in this area anymore — the big problems I wanted to solve in recent years, Steiner tree and asymmetric TSP, have not yielded despite a huge investment — and I can see the BIG VOID approaching! I have already written a paper in game theory but I know so little about the area. Even worse, I can’t seem to understand what game theory papers are really talking about. If only I could gather 5 top experts in the area andhave them tell me about their work …

I soon realize that many other people are in the same boat! So I approach Fred Roberts, Director of DIMACS, with a proposal for a workshop. He is excited and immediately commits generous funding. I know a few potential speakers, but to make it a good event I will need to find a suitable co-organizer. The choice is obvious — Noam — and he agrees! And the workshop ends up being a big success and plays a key role in getting AGT started. (One small gripe: DIMACS still hasn’t listed the co-organizers in alphabetical order.)

Fast forward to December 2005. A publishing rep visits and asks which book I would like to write next. I tell her it would be on AGT but I don’t know enough to write a complete book, and what is more, no one else does either! The rest of the conversation goes something like this (the “….” represent switches in the person speaking):

Rep: You should produce an encyclopedia on AGT …. You will be the Editor-in-Chief and you will have (innumerable) editors, subeditors, reviewers …. The encyclopedia will have extensive bibliographies on all aspects. …. We will make sure every library gets a copy. …. You will get x% of the total sales.

Me: We need an edited book, with chapters written by many top experts working on different aspects of AGT …. I will need to find 2 or 3 well-chosen co-editors …. The chapters should expound the main ideas in the clearest possible manner using simple settings and relegate more complex developments to exercises. They should provide only the absolutely essential references and not be structured as surveys but as pedagogical tools …. If we do a really good job, just about every CS Dept. will be using it for a semester-long course. …. No one should get royalties, not even the co-editors. Instead the price of the book should be set as low as possible and the book should be made available online.

As you can see, we were on completely different wavelengths! But the conversation had already set me in motion, and an obvious choice of co-editor was Noam!

My stance and my creed: My work sits at the extreme “A” end of AGT&E. Fortunately, a lot has happened at that end over the last ten to twelve years and that is what I will mostly talk about.

I consider our theory of algorithms and computational complexity sacrosanct and I believe we need to carefully maintain its integrity. My recent guest posts reflect this, e.g., on Galactic P and Galactic PTAS and on the class FIXP, and so does my recent paper on non-bipartite matching, in which I have made a special point of not sparing myself. Of course, I can’t claim that my viewpoint is the right one, and I will always seek extensive discussion from you all. Hope you will participate.

There’s a changing of the guard happening at Turing’s Invisible Hand — I am following Ariel into retirement and some new additions to the team will be announced soon. I’d like to thank Noam for the opportunity to participate and my co-bloggers for the good times.

Before I go, a quick update on the algorithmic game theory courses that I’ve been teaching at Stanford this year. Last fall quarter I taught an intro to AGT course (mechanism design, price of anarchy, learning algorithms, complexity of equilibria, applications, etc.). I wrote detailed notes for all 20 lectures, which were also videotaped; see the intro AGT course page for details. I hope that some of you find the materials useful for teaching or self-study.

This quarter, I’m teaching a sequel course on topics in mechanism design. The topics range from the classic (matching markets, gross substitutes, etc.) to the hot-off-the-press (price of anarchy of simple auctions, multi-parameter revenue maximization, etc.). I am again making videos and accompanying lecture notes available; see the advanced AGT course page. As always, I’d be grateful for any suggestions and corrections that you have.

When I was 21, I used to go to the gym three times a week, rain or shine. After a few years I shaved off a weekly session, and a few years later I was down to one gym session a week. By the time we moved to Pittsburgh, playing Dance Central with my wife seemed like a demanding workout.

Why am I telling you this? Because blogging is a bit like going to the gym  as the following graph suggests (the y axis shows the number of blog posts posted by yours truly, excluding announcements and guest posts):


But blogging is definitely more fun than going to the gym, and I did have a lot of fun blogging these past 2+ years; I want to thank Noam for this opportunity. Unfortunately, it’s no longer as fun as it used to be, and I decided to quit while I’m ahead. Since my blogging career was defined by ranking and listing stuff, I would like to finish with a vainglorious list of some of my own posts that I especially like:

Now that I think about it, blogging is more like singing in the shower: it’s a creative form of self-expression, and you have no idea who’s listening. If you have been listening for the last two years, I’m grateful for your attention I sing like a crow!