Matching Under Preferences: Theory and Practice
( 25. Jul – 30. Jul, 2021 )
- 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)
- Michael Gerke (für wissenschaftliche Fragen)
- Simone Schilke (für administrative Fragen)
- Behavioral Stable Marriage Problems : article in DAI 2021: Distributed Artificial Intelligence - Berlin : Springer, 2022. - pp. 150-170 - Martin, Andrea; Venable, Kristen Brent; Mattei, Nicholas - Berlin : Springer, 2022. - pp. 150-170.
- Maximum-utility popular matchings with bounded instability - Schlotter, Ildiko; Cseh, Agnes - Cornell University : arXiv.org, 2022. - 33 pp..
Matching under preferences has witnessed remarkable growth as a field that spans multiple disciplines. The research field’s depth and impact was recognized when the 2012 Nobel Prize in Economic Sciences was awarded to Shapley and Roth for their work on the theory of stable allocations and the practice of market design. Most of the developments in the field have taken place within at least three communities:
- ECON (Economics): Game Theory, Mechanism Design, and Market Design are the main subfields of economics, where matching market research is deeply studied.
- CS (Computer Science): Theoretical Computer Science (TCS) and Artificial Intelligence (AI) are the subfields that have been home to many new developments on matching under preferences. The research interface between economics and CS has led to several sub-disciplines and communities, including economics and computation, algorithmic game theory, and computational social choice.
- OR (Operations Research): From among mathematicians working in OR, research continues on the solvability and structure of matching problems under preferences using the theories of graphs, matroids, and lattices. The field is also witnessing developments within the optimization community that tackles hard matching problems with integer linear programming, SAT-solving, and other optimization techniques.
Currently there are several approaches and perspectives towards matching under preferences. These include (1) design of algorithms and understanding the computational complexity of this class of matching problems; (2) formalizing and understanding desirable axioms and properties of matching methods and outcomes; (3) strategic analysis, and mechanism design approaches to matching under preferences; (4) the use of machine learning to find appropriate matches. Approach (1) is largely considered in the CS and OR communities. Approaches (2) and (3) were initiated and are primarily considered by the economic theory community. Approach (4) is mainly considered in CS/AI, but preference estimation is also a classical research topic in ECON, and there have been solutions.
The next decade will witness further developments in the theory and applications of matching under preferences. In this context, it is important to exploit the synergies of the various research communities working on the same research topic from different angles. The specific goal of the seminar is to identify new challenges and opportunities in both the theoretical foundations as well as the applications of matching markets. This Dagstuhl Seminar will set up new links between novel applications and theoretical research which will provide researchers with new research directions.
Topics that the seminar will focus on include (but will not be limited to): (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. Other relevant topics may emerge through suggestions from the participants of the seminar.
The seminar will comprise survey lectures and presentations of recent results to outline the current research frontier in the mornings and interdisciplinary working groups that will work together in the afternoons. Towards the end of the week, there will be an opportunity for working groups to informally report back on their findings.
- Report from Dagstuhl: Matching Under Preferences: Theory and Practice, Edited by Haris Aziz, Péter Biró, Tamás Fleiner, and Bettina Klaus
Blog post by Alvin Roth in "Market Design"
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.
- Matching markets with distributional constraints,
- Probabilistic and Fractional Matching,
- Matching in online and dynamic settings, and
- 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.
- Péter Biró (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Somouaoga Bonkoungou (University of Lausanne, CH)
- Florian Brandl (Universität Bonn, DE) [dblp]
- Jiehua Chen (TU Wien, AT) [dblp]
- Ágnes Cseh (Hasso-Plattner-Institut, Universität Potsdam, DE) [dblp]
- Lars Ehlers (University of Montreal, CA) [dblp]
- Tamás Fleiner (Budapest University of Technology & Economics, HU) [dblp]
- Martin Hoefer (Goethe-Universität - Frankfurt am Main, DE) [dblp]
- Zsuzsanna Jankó (Corvinus University - Budapest, HU) [dblp]
- Bettina Klaus (University of Lausanne, CH) [dblp]
- Simon Mauras (University Paris Diderot, FR) [dblp]
- Seckin Özbilen (University of Lausanne, CH)
- Katarzyna Paluch (University of Wroclaw, PL) [dblp]
- Jan Christoph Schlegel (City - University of London, GB)
- Karolina Lena Johanna Vocke (Universität Innsbruck, AT)
- Haris Aziz (UNSW - Sydney, AU) [dblp]
- Martin Bichler (TU München, DE) [dblp]
- Felix Brandt (TU München, DE) [dblp]
- Robert Bredereck (HU Berlin, DE) [dblp]
- Christine Cheng (University of Wisconsin - Milwaukee, US) [dblp]
- Sanmay Das (George Mason University - Fairfax, US)
- John Dickerson (University of Maryland - College Park, US) [dblp]
- Di Feng (University of Lausanne, CH)
- Sushmita Gupta (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Klaus Heeger (TU Berlin, DE)
- Hadi Hosseini (Pennsylvania State University, US)
- Pallavi Jain (Indian Institute of Techology, IN)
- Yash Kanoria (Columbia University - New York, US) [dblp]
- Flip Klijn (CSIC - Barcelona, ES) [dblp]
- Fuhito Kojima (University of Tokyo, JP) [dblp]
- Alexander Lam (UNSW - Sydney, AU)
- Irene Y. Lo (Stanford University, US)
- Nicholas Mattei (Tulane University - New Orleans, US) [dblp]
- Michael McKay (University of Glasgow, GB) [dblp]
- Shuichi Miyazaki (Kyoto University, JP) [dblp]
- Thayer Morrill (North Carolina State University - Raleigh, US)
- Thanh Nguyen (Purdue University - West Lafayette, US) [dblp]
- Sofiat Olaosebikan (University of Glasgow, GB)
- Daniel Paulusma (Durham University, GB) [dblp]
- Baharak Rastegari (University of Southampton, GB)
- Ildikó Schlotter (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Jay Sethuraman (Columbia University - New York, US) [dblp]
- Kavitha Telikepalli (TIFR Mumbai, IN) [dblp]
- Alexander Teytelboym (University of Oxford, GB)
- Utku Unver (Boston College, US) [dblp]
- Toby Walsh (UNSW - Sydney, AU) [dblp]
- Mobin YahyazadehJeloudar (Stanford University, US)
- Yu Yokoi (National Institute of Informatics - Tokyo, JP)
- Makoto Yokoo (Kyushu University - Fukuoka, JP) [dblp]
- artificial intelligence / robotics
- data structures / algorithms / complexity
- society / human-computer interaction
- Matching under preferences
- market design
- organ exchange
- stable matching