https://www.dagstuhl.de/21301

July 25 – 30 , 2021, Dagstuhl Seminar 21301

Matching Under Preferences: Theory and Practice

Organizers

Haris Aziz (UNSW – Sydney, AU)
Péter Biró (Hungarian Academy of Sciences – Budapest, HU)
Tamás Fleiner (Budapest University of Technology & Economics, HU)
Bettina Klaus (University of Lausanne, CH)
David Manlove (University of Glasgow, GB)

For support, please contact

Dagstuhl Service Team

Documents

Due to maintenance activity, guest services will be restricted or not available on January 26th 2022 from 2 PM to 8 PM UTC. We regret the inconvenience caused.

Dagstuhl Report, Volume 11, Issue 6 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

Matching under preferences is a general field spanning computer science, economics, and mathematics. The seminal paper in the field is one by Gale and Shapley (1962) that launched an algorithmic approach to matching agents with preferences. The central problems in the field involve matching agents to each other and to resources in a stable and efficient manner. Matching market algorithms based on the preferences of the agents have several applications such as in school admissions, placement of hospital residents, and centralized kidney markets. Topics in the field include two-sided matchings involving agents on both sides (e.g., job markets, school choice, etc.); two-sided matchings involving agents and items (e.g. course allocation, project allocation, assigning papers to reviewers etc.); one-sided matchings (roommates problem, kidney exchanges, etc.); and matching with payments (assignment game, auctions, etc.).

The topic of matching under preferences not only has tremendous applications but is based on a deep mathematical theory that has been developed by multiple research communities including theoretical computer science, artificial intelligence, discrete mathematics, game theory, and microeconomics. One of the main purposes of the seminar was to bring together leading researchers from various communities working on the topic and facilitate collaboration. The participant list was a mixture of researchers from computer science, mathematics, and economics. The seminar provided a platform to discuss state of the art in matching under preferences; identify new and exciting applications of developing research; and understand the mathematical and algorithmic requirements of new and upcoming problems in the field.

The seminar was conducted in a hybrid manner, with 15 participants attending the seminar physically from the Dagstuhl center and 34 participants attending online. The hybrid nature of the work required the need for careful planning to keep participants engaged and to facilitate collaboration between off-site and on-site participants. The online participation was managed via zoom and gather-town softwares.

The four main focus topics of the workshop were the following ones.

  1. Matching markets with distributional constraints,
  2. Probabilistic and Fractional Matching,
  3. Matching in online and dynamic settings, and
  4. Matching Markets and machine learning.

All of the four focus areas are important directions for the field. As new applications arise, it is clear that many real-life matching markets have additional feasibility and distributional constraints. Secondly, most of the theoretical developments in the field concern deterministic outcomes, so one of the goals was to make further progress on probabilistic mechanisms. During the seminar, current and new research on probabilistic approaches was discussed. Thirdly, many practical matching markets have online and dynamic aspects. There were several discussions on how to model and solve online matching problems. Fourthly, with the increased importance of machine learning in building computer systems, the seminar provided an opportunity to discuss how learning approaches help solve market design problems.

On each of the first four days, there was a one-hour survey talk given by an expert on the above topics. On the first day, Yash Kanoria presented a survey on "online matching markets". On the second day, John Dickerson gave a survey talk on machine learning and matching markets. On day three, Makoto Yokoo presented an overview of "matching under constraints." On day four, Jay Sethuraman surveyed "probabilistic matchings."

On each of the days there were several shorter scientific presentations. During the workshop, two rump sessions were organized to facilitate different time zones. The rump sessions gave an opportunity to the participants to give brief updates or share open problems.

During the week, there were several time slots dedicated to flexible discussion and collaboration as well as dedicated working groups working on particular research topics. Apart from collaborations in smaller groups, the workshop witnessed major collaboration or discussion around several topics. Robert Bredereck brought up the issue of unifying and streamlining terminology and discussed the issue of using gender-neutral terms. There was a large working group led by Sushmita Gupta and Pallavi Jain that examined computational problems that combine the goals of stability and popularity. There was a group led by Bettina Klaus on lexicographic preferences in matching and market design. Finally, Florian Brandl led a group on the intersection between matching and fair division.

On the last day, there was a panel discussion that was moderated by Haris Aziz and Bettina Klaus. The discussants in the panel were Péter Biró, Ágnes Cseh, Lars Ehlers, Alex Teytelboym, and Utku Ünver. The main topics discussed included ways to build synergies between research communities and having an impact on the practice of matching markets.

The organisers thank all the Dagstuhl staff members for their professional support, the participants for enriching the seminar, Somouaoga Bonkoungou and Alex Lam for providing video conferencing support, and Seçkin Özbilen for his support in putting together the abstracts that compose this report.

Summary text license
  Creative Commons BY 4.0
  Haris Aziz, Péter Biró, Tamás Fleiner, and Bettina Klaus

Classification

  • Artificial Intelligence / Robotics
  • Data Structures / Algorithms / Complexity
  • Society / Human-computer Interaction

Keywords

  • Matching under preferences
  • Market design
  • Organ exchange
  • Stable matching

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.