Videos from PapaFest

Videos of all PapaFest talks and panels are here.

Read Full Post »

Blind Folks and the Evolving Elephant – by Vijay Vazirani

One of my favorite parables ever since childhood was that of the four blind men and the elephant, with each man announcing the local image evoked in his mind’s eye on touching a different part of the elephant. This parable has provided an interesting metaphor even for serious scientific matters, a well-known one being wave-particle duality in physics.

But when it comes to matching markets, the parable has taken an unusual twist, with the proverbial elephant undergoing a metamorphosis of its own! The “blind men’’ in this case are entire disciplines which can lay claim to the field of matching markets. Of course, the obvious one is economics – the founders of this field, namely Gale and Shapley, were mathematical economists and the 2012 Nobel Prize in Economics was awarded to Alvin Roth and Lloyd Shapley for work on these markets.

A key enabler was researchers in systems and networking. Their scientific revolutions of the Internet and mobile computing put matching markets on an exciting, new journey and their systems run these centralized markets on powerful computers.

The discipline of algorithm design has had an umbilical connection to matching markets: At the birth of this field lies the highly sophisticated Gale-Shapley stable matching algorithm (1962), whose pivotal game-theoretic property of incentive compatibility follows as a free gift from polynomial time solvability — it was established two decades after the discovery of the algorithm! Yet most researchers, including those in theoretical computer science, are not aware that algorithm design is also a legitimate claimant to this field. Indeed, the very “engine’’ that runs almost each one of these markets is a sophisticated algorithm chosen from the “gold mine’’ of matching theory! Besides stable matching, this includes maximum matching and online matching and their numerous variants.

Looking back at the huge expansion of matching markets over the last decade-and-a-half, one can see that all three disciplines were faced with numerous challenges: understanding the incentive structure of a new market; finding ways of dealing with terra-bytes of data, and choosing and delivering within milli-seconds the “right’’ ads to show with a user query; and designing an algorithm for the latest variant of online matching. And they all delivered!

The rich and diverse set of research talks given at the recent Simons program on matching markets is proof enough that the elephant is still evolving!

Advertisement

Read Full Post »

Highlights Beyond EC – Call for Nominations

The 21st ACM Conference on Economics and Computation (EC’20) will host a special plenary session highlighting some of the best work in economics and computation that appears in conferences and journals other than EC, or mature working papers. The intention of this session is to expose EC attendees to related work just beyond the boundary of their current awareness. We seek nominations for papers in Economics and Computation that have made breakthrough advances, opened up new horizons for research, made interesting connections between different scientific areas, or had significant impact on practice. Examples of relevant conferences and journals include STOC/FOCS/SODA/ITCS, AAAI/IJCAI/AAMAS, NIPS/ICML/COLT, WWW/KDD, AER/Econometrica/JPE/QJE/RESTUD/TE/AEJ Micro/JET/GEB, and Math of OR/Management Science/Operations Research.

Who can nominate? This call is open to everyone (self-nominations are also allowed), but we particularly encourage members of PCs or editorial boards in various venues to submit nominations.

Deadline: December 23, 2019.

Nomination format: Nominations should be emailed to HighlightsBeyondEC2020@gmail.com, and should include:

• Paper title and author names.
• Publication venue or online working version. Preference will be given to papers that have appeared in a related conference or journal within the past two years, or have a working version circulated within the past two years.
• A short (2-3 paragraph) justification letter, explaining the significance of the paper.
• Names of 1-3 experts on the area of the paper.

Committee members:

• Michal Feldman (Tel Aviv University)
• Hervé Moulin (University of Glasgow)
• Michael Wellman (University of Michigan)
• Adam Wierman (California Institute of Technology)

Read Full Post »

Matching Markets @ Simons: Driven by Theory, Driving the Economy

[Guest post by Sid Banerjee.]

Divergent Evolution: The formation of new species when populations experience different selective pressures.

While the canonical example is Darwin’s finches, it could apply as well to matching theorists! A notable feature of the first and second workshops at the Simons Institute program on Matching Markets was how researchers in Economics, Operations Research and TCS all share common antecedents (Fulkerson, Gale, Scarf, Shapley, Walras — to name but a few giants invoked regularly), and yet have taken the theory in diverse directions. The workshops helped create a healthy dialogue between the communities, as everyone tries to understand each other’s objectives and techniques. 

A more notable aspect of matching theory in recent years has been its impact on the design of real-world marketplaces. Over the two workshops, a mix of speakers from academia and industry covered a host of markets, including payment routing, online advertising, kidney exchange, real-estate, public housing, ride-sharing, long-haul trucking, restaurant reviews, school choice, food-banks and many many others. A common theme that emerged was that online marketplaces, with the support of good algorithm and mechanism designers, are slowly taking over the economy.

And talking of giants of matching theory, another event held in parallel with the program was a celebration of the achievements and contributions of Dick Karp, with Vijay Vazirani giving the inaugural lecture of the Simons Institute Richard M. Karp Distinguished Lecture Series. Vijay’s talk touched on both the above themes, with a sweeping overview of three great threads in matching theory (stable matching, market equilibria, and online matching). He highlighted the critical role of algorithmic thinking in their development, and concluded with a tantalizing 40-year-old open problem connected to finding a polynomial-time algorithm for the Hylland-Zeckhauser market equilibrium. It is an excellent starting point for those interested in the program, or matching markets in general!

Read Full Post »

SIGecom Dissertation Award — Call for Nominations

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 29, 2020.  This award is given to a student who defended a thesis in 2019.  It is a prestigious award and is accompanied by a $1500 prize.  In the past, the prize has been awarded to:

2018: Yannai Gonczarowski, “Aspects of Complexity and Simplicity in Economic Mechanisms”

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 nine runner-ups: Nika Haghtalab, Haifeng Xu, 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,

Ozan Candogan

Renato Paes Leme (Chair)

Yiling Chen

Read Full Post »