Mark Braverman wins Abacus Medal (formerly Nevanlinna Prize)

 Mark Braverman, a computer scientist whose work touches on mechanism design, has won the Abacus Medal of the International Mathematical Union.

Here are some links: citation, video, write-up, CV/publications, proceedings, interview, Plus magazine! article

Readers of this blog may be interested in these papers:

Optimization-friendly generic mechanisms without money

Mark Braverman

"The goal of this paper is to develop a generic framework for converting modern optimization algorithms into mechanisms where inputs come from self-interested agents. We focus on aggregating preferences from n players in a context without money. Special cases of this setting include voting, allocation of items by lottery, and matching. Our key technical contribution is a new meta-algorithm we call \apex (Adaptive Pricing Equalizing Externalities). The framework is sufficiently general to be combined with any optimization algorithm that is based on local search. We outline an agenda for studying the algorithm's properties and its applications. As a special case of applying the framework to the problem of one-sided assignment with lotteries, we obtain a strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits that there is a (fractional) allocation and a set of item prices such that the allocation is a competitive equilibrium given prices. We further show that there is always a reweighing of the players' utility values such that running unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices. Interestingly, not all HZ competitive equilibria come from VCG prices. As part of our proof, we re-prove the [HZ79] result using only Brouwer's fixed point theorem (and not the more general Kakutani's theorem). This may be of independent interest."

**********

Clearing Matching Markets Efficiently: Informative Signals and Match Recommendations by Itai Ashlagi , Mark Braverman, Yash Kanoria , Peng Shi , Management Science, 2020, 66(5), pp.2163-2193.  https://doi.org/10.1287/mnsc.2018.3265

Abstract: "We study how to reduce congestion in two-sided matching markets with private preferences. We measure congestion by the number of bits of information that agents must (i) learn about their own preferences, and (ii) communicate with others before obtaining their final match. Previous results suggest that a high level of congestion is inevitable under arbitrary preferences before the market can clear with a stable matching. We show that when the unobservable component of agent preferences satisfies certain natural assumptions, it is possible to recommend potential matches and encourage informative signals such that the market reaches a stable matching with a low level of congestion. Moreover, under our proposed approach, agents have negligible incentive to leave the marketplace or to look beyond the set of recommended partners. The intuitive idea is to only recommend partners with whom there is a nonnegligible chance that the agent will both like them and be liked by them. The recommendations are based on both the observable component of preferences and signals sent by agents on the other side that indicate interest."

 ***********

Update: from Quanta.

The Scientist Who Developed a New Way to Understand Communication. Mark Braverman has spent his career translating thorny problems into the language of information complexity.  by Stephen Ornes

"While Braverman continues to guide the theory as his former students and postdocs push it forward, the bulk of his work is done. Now his interests are more focused on a new field called mechanism design, which uses the mathematical approaches of economics and game theory. "