Archive for January, 2019

My Picture


[The following guest post was written by Vijay Vazirani.]






What the cutting locust left, the swarming locust has eaten. What the swarming locust left, the hopping locust has eaten, and what the hopping locust left, the destroying locust has eaten.

Joel 1:4

A few years ago, while attending a Dagstuhl program on Equilibrium Computation, I embarked on one of the traditional long hikes through the beautiful woods surrounding Schloss Dagstuhl and happened to be walking next to a senior member of the Operations Research community. In no time we got immersed in a lively discussion on the style of research going on in Algorithmic Game Theory. We both agreed that the progress made in a matter of a few years was nothing short of phenomenal. At this point, my colleague remarked that AGT was no exception and that when TCS researchers enter a new area, they go in with such energies and enthusiasm that in no time not only is all low hanging fruit gone but in fact the entire area is devoid of any reasonable open problems! “They attack the area like swarms of locusts devouring foliage in biblical lands, consuming not only fruit and leaves but even shrubs and twigs,” he added. “Yes, and only sh*t is left behind!” I chimed in.

As AGT is reaching that stage, with researchers yearning for new issues/problems for their students and their own research and grant proposals, there is a reprieve emerging on the horizon: a program at Simons on “Online and Matching-Based Market Design” in Fall 2019.

This is by no means a new area. In fact, the first such market, for matching medical residents to hospitals, dates back to 1920s, well before the classic — and by now Nobel Prize winning — work of Gale and Shapley on the stable matching problem, which provided the canonical algorithm for this market. In recent years, the advent of the Internet and the relocation of our most important activities to online platforms have led to an explosion of such marketplaces (for examples, see the Simons web page) and they have been occupying an ever-increasing fraction of our economy.

AGT, CS and Economics have already had a massive impact via these markets. My own experience comes from Google’s multi-billion dollar Adwords market in which sophisticated algorithmic ideas have also played a central role, e.g., see the Simons talk “Google’s AdWords Market: How Theory Influenced Practice“.

Clearly, the stakes are high. There is a real opportunity of extending the already existing highly inter-disciplinary theory in substantial ways and making an even bigger impact. Considering this and the enthusiasm of the researchers who have agreed to be participants in this program, Federico Echenique, Nicole Immorlica and I have launched the project of publishing a comprehensive volume of contributed chapters on this topic. More information on this will be coming soon.


Read Full Post »

The deadlines to submit nominations for the Gödel Prize, Knuth Prize, and SIGACT Distinguished Service Award are coming soon. Calls for nominations for all three awards can be found at the links below. Note that March 1 is now the permanent deadline for SIGACT Distinguished Service Award nominations, this year and in future years.

  • Gödel Prize: deadline February 15, 2019
  • Knuth Prize: deadline February 15, 2019
  • SIGACT Distinguished Service Award: deadline March 1, every year (including 2019)
    Those who intend to submit a nomination for the Distinguished Service Award are strongly encouraged to inform the Selection Committee Chair at least two weeks in advance.

Read Full Post »

Please consider nominating graduating Ph.D. students for the SIGecom Dissertation Award.  If you are a graduating student, consider asking your adviser or other senior mentor to nominate you.
Nominations are due on February 28, 2019.  This award is given to a student who defended a thesis in 2018.  It is a prestigious award and is accompanied by a $1500 prize.  In the past, the grand prize has been awarded to:
2017: Aviad Rubinstein, “Hardness of Approximation Between P and NP”
2016: Peng Shi, “Prediction and Optimization in School Choice”
2015: Inbal Talgam-Cohen, “Robust Market Design: Information and Computation “
2014: S. Matthew Weinberg, “Algorithms for Strategic Agents”
2013: Balasubramanian Sivan, “Prior Robust Optimization”
And the award has had seven runner-ups: Rachel Cummings, Christos Tzamos, Bo Waggoner, James Wright, Xi (Alice) Gao, Yang Cai, and Sigal Oren.  You can find detailed information about the nomination process at: http://www.sigecom.org/awardd.html. We look forward to reading your nominations!
Your Award Committee,
Renato Paes Leme
Aaron Roth (Chair)
Inbal Talgam-Cohen

Read Full Post »