MATCH-UP 2022 is the 6th workshop in an interdisciplinary and international workshop series on matching under preferences . It will take place on 24-26 August 2022, hosted by TU Vienna and co-located with MFCS 2022 (47th International Symposium on Mathematical Foundations of Computer Science).

Matching problems with preferences occur in widespread applications such as the assignment of school-leavers to universities, junior doctors to hospitals, students to campus housing, children to schools, kidney transplant patients to donors and so on. The common thread is that individuals have preferences over the possible outcomes and the task is to find a matching of the participants that is in some sense optimal with respect to these preferences. There has been a resurgence of activity in this area in recent years, with online and mobile computing opening up new avenues of research and novel, path-breaking applications.

The remit of this workshop is to explore matching problems with preferences from the perspective of algorithms and complexity, discrete mathematics, combinatorial optimization, game theory, mechanism design, and economics. Thus, a key objective is to bring together the research communities of the related areas. Another important aim is to convey the excitement of recent research and new application areas, exposing participants to new ideas, new techniques, and new problems.

List of Topics

The matching problems under consideration include, but are not limited to:

• Two-sided matchings involving agents on both sides (e.g., college admissions, medical resident allocation, job markets, and school choice)

• Two-sided matchings involving agents and objects (e.g., house allocation, course allocation, project allocation, assigning papers to reviewers, and school choice)

• One-sided matchings (e.g., roommate problems, coalition formation games, and kidney exchange)

• Multi-dimensional matchings (e.g., 3D stable matching problems)

• Matching with payments (e.g., assignment game)

• Online and stochastic matching models (e.g., Google Ads, ride sharing, Match.com)

• Other recent applications (e.g., refugee resettlement, food banks, social housing, and daycare)

Invited Speakers

• Sophie Bade (Royal Holloway College, University of London)

  

  Bio: Sophie Bade is a Professor of Economics at Royal Holloway. She received her PhD from NYU under the supervision of Efe Ok. In her PhD, Sophie worked on game theoretic models where the players’ behavior deviates from standard rationality assumptions. While she continues to be interested in how to integrate novel decision theoretic models into interactive settings, she developed a second strand of research on mechanism design. As a first step in that direction, Sophie worked on house matching markets with endogenous information acquisition. More recent interests include random matching models, the notion of obvious strategyproofness, and matching problems with convex preferences.

  Talk: A procession of Royals: Incentives, Efficiency and Fairness in Two-sided Matching

  Abstract: We study the set of incentive compatible and efficient two-sided matching mechanisms. We classify all such mechanisms under an additional assumption – “gender-neutrality" – which guarantees that the two sides be treated symmetrically. All group strategy-proof, efficient, and gender-neutral mechanisms are defined recursively in a sequence of rounds. In each round two agents are selected, one from each side. These agents are either “matched-by-default" or “unmatched-by-default." In the former case either of the selected agents can unilaterally force the other to match with them while in the latter case, they may only match together if both agree. In either case, if this pair of agents is not matched together, each gets their top choices among the set of remaining agents. As an important step in the characterization, we first show that in one-sided matching all group strategy-proof and efficient mechanisms are sequential dictatorships. An immediate corollary is that there are no individually rational, group strategy-proof and efficient one-sided matching mechanisms.

  Joint work with Joseph Root.

• Vijay Vazirani (University of California, Irvine)

  

  Bio: Vijay Vazirani got his undergraduate degree from MIT in 1979 and his PhD from the University of California, Berkeley in 1983. He is currently a Distinguished Professor at the University of California, Irvine.

  Vazirani has made fundamental contributions to several areas of the theory of algorithms, including algorithmic matching theory, approximation algorithms and algorithmic game theory, as well as to complexity theory, in which he established, with Les Valiant, the hardness of unique solution instances of NP-complete problems. Over the last four years, he has been working on algorithms for matching markets.

  In 2001 he published Approximation Algorithms, which is widely regarded as the definitive book on the topic. In 2007, he published the co-edited book Algorithmic Game Theory. Another co-edited book, Online and Matching-Based Market Design, will be published by Cambridge University Press this November; see its flyer .

  Talk: Online Bipartite Matching and Adwords (talk shared with MFCS )

  Abstract: Over the last three decades, the online bipartite matching (OBM) problem has emerged as a central problem in the area of Online Algorithms. Perhaps even more important is its role in the area of Matching-Based Market Design. The resurgence of this area, with the revolutions of the Internet and mobile computing, has opened up novel, path- breaking applications, and OBM has emerged as its paradigmatic algorithmic problem. In a 1990 joint paper with Richard Karp and Umesh Vazirani, we gave an optimal algorithm, called RANKING, for OBM, achieving a competitive ratio of (1 – 1/e); however, its analysis was difficult to comprehend. Over the years, several researchers simplified the analysis.

  We will start by presenting a “textbook quality” proof of RANKING. Its simplicity raises the possibility of extending RANKING all the way to a generalization of OBM called the adwords problem. This problem is both notoriously difficult and very significant, the latter because of its role in the AdWords marketplace of Google. We will show how far this endeavor has gone and what remains. We will also provide a broad overview of the area of Matching-Based Market Design and pinpoint the role of OBM.

  Based on the following paper .

Poster

A poster with the main information is available here .