AF: Small: Algorithmic Problems in Online and Matching-Based Market Design

University Of California-Irvine, Irvine CA

Investigators

Abstract

The area of online and matching-based market design started with the seminal 1962 paper of Gale and Shapley on stable matching. Over the decades, it led to highly successful applications, having economic as well as sociological impact, including matching medical interns to hospitals, matching students to schools, and matching kidney transplant recipients with compatible donors. The importance and impact of this interdisciplinary work led to the award of the 2012 Nobel Prize in Economics to Alvin Roth and Lloyd Shapley. Over the last two decades, the revolutions of the Internet and mobile computing opened up altogether new avenues of research and novel, path-breaking applications. These applications include the ad auction marketplace of search engine companies, which matches user queries to advertisers; ride-sharing, matching drivers to riders; markets matching employers to workers; platforms matching people to each other; and others. This "second life" of the field has been even more interdisciplinary than the first, with computer scientists playing a major role along with the economists. The optimal algorithm for the online bipartite matching problem, called RANKING, given in a 1990 joint paper of the investigator, has become the paradigm-setting algorithmic idea in the second life, much as stable matching was in the first. A recently developed simple proof of RANKING has opened up new opportunities, leading to three of the four problems proposed for study under the current project: (i) obtaining algorithms for online hypergraph matching and its generalizations -- these have applications to network revenue management and ride-sharing; (ii) extending RANKING to the adwords problem under small bids, so as to get a budget-oblivious algorithm which will be useful in autobidding platforms; (iii) obtaining high probability statements for online algorithms, which have thus far been analyzed in expectation only. The fourth problem addresses the paucity of general mechanisms for matching markets under cardinal utility functions; this paucity became apparent via recent work of the investigator, which led to proof of intractability of the classic Hylland-Zeckhauser mechanism (1979). The investigator has proposed Nash-bargaining-based mechanisms as a replacement and wishes to develop efficient implementations for them. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.