The list of accepted papers for FOCS 2012 is out. As always, there are lots of interesting titles on the list. By my count, three of the accepted papers are explicitly in the area of Game Theory or Economics:
- The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
Zhiyi Huang and Sampath Kannan
- Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg
- Concave Generalized Flows with Applications to Market Equilibria
Laszlo A. Vegh
The following five papers are on closely related topics.
- A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Yuval Filmus and Justin Ward
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz
- The Dynamics of Influence Systems
- Online Matching with Stochastic Rewards
Aranyak Mehta and Debmalya Panigrahi
- Matching with Our Eyes Closed
Gagan Goal and Pushkar Tripathi
This year represents a pretty noticeable dip in the number of accepted Algorithmic Game Theory/Economics papers compared to the last two years of STOC and FOCS. I’m curious if this stems from a dip in the number of submissions related to Game Theory or Economics (possibly linked to the vastly greater number of papers in EC this year, though it seems doubtful that a large number of FOCS papers in prior years had been rejected from the previous EC), or if the percentage of accepted AGT/E papers is significantly lower in this FOCS than in recent history. (In the latter case, I’m inclined to attribute it to random fluctuation rather than conscious bias, especially considering who the program committee chair was!)
In other news, the Call for Papers for ITCS 2013 was announced yesterday. Now in its fourth year, ITCS (formerly known as ICS) is a conference that seeks to promote research in theoretical computer science that carries a strong conceptual message. In its first three years, the conference has been very friendly to Algorithmic Game Theory and Economics research, and some excellent papers have appeared there. (See my blog post reporting on this year’s ITCS, for example.) This year I’m chairing the PC, and we’ve decided to adopt EC’s policy allowing authors to designate their submission as a working paper, meaning that the conference proceedings will contain only a one-page abstract (together with a link to the full paper) rather than the paper itself. This helps with the dilemma faced by authors who want to present their research in a CS conference and then submit it to an Economics journal. Unlike EC in past years, authors selecting the working-paper option do not forfeit their eligibility for the Best Student Paper award. (There is no Best Paper award at ITCS.) I hope many of the readers of this blog will submit some of their work!
More controversially, the ITCS call for papers includes the option of submitting work that is previously published or has been accepted for publication, e.g. in a journal, provided this work has never been presented at a CS conference before. (Nor has it been accepted, or simultaneously submitted, to such a conference.) This policy is primarily aimed at helping out with some of the dilemmas faced by authors who work on the interface of TCS and the physical and biological sciences, but it may affect some authors working at the TCS interface with social sciences as well. At the very least, it will be interesting to see how many submissions we receive under this new policy, and what research areas they come from.