## Things a AGTEer Should Do At Least Once

September 28, 2012 by Noam Nisan

Continuing the thread opened by Suresh and continued by Lance, here is a list of things that every researcher that works on the border of Computer Science with Game Theory or Economics should do at least once. Doing it in class does not count.

- Define (and motivate) a new game.
- Find a mixed Nash equilibrium of a game and prove its uniqueness.
- Study at least 3 equilibrium notions from the set:{sub-game-perfect, correlated, coarse, trembling-hand, sink, Walrasian, Bayesian, ex-post, evolutionary} and define a new notion of equilibrium.
- Prove something to be NP complete.
- Find an approximation algorithm.
- Prove a lower bound on some competitive ratio.
- Define a new type of competitive ratio (“Price-of-X”).
- Use or design an auction.
- Consider a game played on networks.
- Design a distributed protocol/algorithm.
- Formulate a linear problem and invoke LP duality.
- Do something with sub-modular functions.
- Reduce an AGTE problem to a purely combinatorial one.
- Use regret-matching (best-expert) and/or secretary problems and/or multi-arm bandits.
- Do something that relates to Arrow’s impossibility result (Gibbard-Satterthwaite also counts.)
- Optimize for efficiency, for revenue, and consider fairness.
- Work on an Internet-motivated problem. Really. And also, not really.
- Publish a paper in a CS conference and in an Economics journal.
- Give a talk to economists.
- Argue about Bayesian vs. worst-case analysis. Both ways.
- Argue about whether Mixed-Nash equilibria make any sense. Then get tired of this argument.

Posted in Uncategorized | 3 Comments

on September 30, 2012 at 3:15 am |Kevin Leyton-BrownMany of these are great, but I question whether it would be such a good thing for every researcher in AGTE to define a new equilibrium concept and a new Price-of-X. It seems to me in both cases that this is something one should do only when it’s really necessary to capture a new idea, and that there will inevitably be fewer such new ideas than new AGTE researchers.

on September 30, 2012 at 6:13 pm |Angelina VidaliNice! Seems to me more of a definition of what researchers in the area work on, and should be able to understand. Great for defining Algorithmic Game Theory in an understandable way to someone in Computer Science or Economics or Math. Also a reminder that sticking to very few of the points and forgetting the rest, does not make you an AGTEer. i.e. It’s more a definition, rather than a checklist, still the title is catchy…

on September 30, 2012 at 7:11 pm |Noam NisanWhile I totally agree that the community shouldn’t buy into most of these new definitions of equilibrium or price-of-X, I still think that coming up with such definitions should be an integral part of one’s research. The way to grapple with the inappropriateness (in many respects) of existing definitions is to try conjuring up alternative ones — even if you end up not liking your own new definition. Similarly, defining what you loose due to various constraints as a “price-of-X” notion makes you formalize what you are talking about in a way that is beneficial for your future thinking.