Showing posts with label matching. Show all posts
Showing posts with label matching. Show all posts

Friday, November 1, 2024

Lanchester prize to Ashlagi, Kanoria, Leshno, Braverman and Shi (post 2 of 2)

 INFORMS has now announced the details of the Frederick W. Lanchester Prize, which went to two teams, one of which worked on matching and market design.

Here is the matching team, with a little more detail than in my previous post*, about the papers that were recognized by the award.

2024 - Winner(s)

2024 Winner(s)

Winning material: Collection of Papers: “Unbalanced random matching markets: The stark effect of competition” and “Clearing matching markets efficiently: informative signals and match recommendations
 ############
Here's the prize citation (sent to me by Sasa Pekec, the chair of the prize committee):
"The 2024 Lanchester Prize is awarded to Itai Ashlagi, Mark Braverman, Yash Kanoria, Jacob Leshno, and Peng Shi for their papers “Unbalanced random matching markets: The stark effect of competition” and “Clearing matching markets efficiently: Informative signals and match recommendations”.
These papers have advanced the field of market design by providing fundamental insights into the performance of two-sided matching markets. By introducing a novel theoretical approach, they resolve a long-standing empirical puzzle: why the set of stable matchings is small in many practically important matching markets. Moreover, by creatively integrating match recommendations and signaling strategies, they demonstrate how to reduce congestion in these markets. These contributions have profoundly impacted both methodological work and practical applications focused on the conduct and organization of centralized and decentralized markets."

The other members of the prize committee were Francis de Véricourt, Wedad Elmaghraby, Fatma Kilinç-Karzan, Azarakhsh Malekian, and Mengdi Wang
#########
Itai shared with me his brief remarks upon accepting the award on behalf of the team at the recent Seattle meeting:
 
"This is a real honor and it is very special to share the prize with my wonderful coauthors Mark Braverman, Yash Kanoria, Jacob Leshno and Peng Shi who could not attend this event today.  It is a great honor and humbling to share this award with  Anatoli Juditsky and Arkadi Nemirovski as well as the distinguished past recipients of the prize. 34 years ago, Alvin Roth and Marilda Sotomayor were awarded the prize for their remarkable and beautiful book on two-sided matching. The last two decades, matching in two-sided markets has been and still is a very active area in Operations Research and economics, with many successful applications and a rich theory. We are grateful to be able to contribute to this area. Thanks to Sasa and the committee. It is a real honor being part of this community."

 ###########

*Earlier: Wednesday, October 23, 2024 Lanchester Prize (Post 1 of 2)

Wednesday, October 23, 2024

Lanchester Prize (Post 1 of 2)

 The 2024 INFORMS meetings in Seattle this weekend was the occasion of a number of awards, including the Lanchester Prize, the big publication award in operations research and management science.  Congratulations to the two winning publication teams.

One of the teams will be familiar to the readers of this blog: Itai Ashlagi, Yash Kanoria, Jacob Leshno, Mark Braverman and Peng Shi.  They received the award for a series of papers on matching, about which I'll blog in a subsequent post.

The Lanchester Prize is awarded for the best contribution to operations research and the management sciences published in English in the past five years. 

Learn more about the Lanchester Prize and how to be nominated on the INFORMS website.

WINNING TEAM ONE

Université Grenoble-Alpes

Anatoli Juditsky

Université Grenoble-Alpes
Georgia Tech

Arkadi Nemirovski

Georgia Tech

WINNING TEAM TWO

Stanford University

Itai Ashlagi

Stanford University
Columbia University

Yash Kanoria

Columbia University
Chicago University

Jacob Leshno

Chicago University
Princeton University

Mark Braverman

Princeton University
University of Southern California

Peng Shi

University of Southern California

Honorable Mention

The Chinese University of Hong Kong, Shenzhen

Guillermo Gallego

The Chinese University of Hong Kong, Shenzhen
Cornell University

Huseyin Topaloglu

Cornell University

 

 

Tuesday, October 22, 2024

Stability vs. No Justified Envy, by Romm, Roth and Shorrer

 Here's a recent paper that clarifies some of the prior literature on comparing stability in two-sided matching with a related kind of envy-freeness in allocations of goods to individuals using priorities.


Romm, Assaf, Alvin E. Roth, and Ran I. Shorrer, "Stability vs. No Justified Envy," Games and Economic Behavior, Volume 148, November 2024, Pages 357-366  https://doi.org/10.1016/j.geb.2024.10.002
 
Abstract: Stability and “no justified envy” are used almost synonymously in the matching theory literature. However, they are conceptually different and have logically separate properties. We generalize the definition of justified envy to environments with arbitrary school preferences, feasibility constraints, and contracts, and show that stable allocations may admit justified envy. When choice functions are substitutable, the outcome of the deferred acceptance algorithm is both stable and admits no justified envy.

Sunday, October 13, 2024

Stable matching in Scientific American

 Here's a short article in Scientific American, describing the deferred acceptance algorithm and mentioning some uses for stable matching. (When I was a child, Scientific American opened a window on science for me...)

The ‘Stable Marriage Problem’ Solution Underpins Dating Apps and School Admissions. An elegant matchmaking algorithm called Gale-Shapley can find the best possible pairings for everybody.   By Max Springer

"Let’s create a reality dating show unlike any other in one key aspect. First, we’ll rent a villa on a tropical island. Then we’ll fly in five men and five women, each with their own (heterosexual) dating preferences. Our goal, though, is the exact opposite of the Love Island franchise: we want absolutely zero drama. Can we ensure that everyone pairs off with a partner and sticks with them, without jealousy rearing its ugly head?" 

########

Along the way they briefly quote these luminaries (in the order in which they appear): 

Vijay Vazirani, Jon Kleinberg, Utku Ünver, and Éva Tardos.

Thursday, September 26, 2024

Many preference signals as a soft cap on number of applications in medical residency matching

 Here's a review article on matching for medical residents,  with particular attention to neurosurgery, in the Cureus Journal of Medical Science.  In specialties that (like neurosurgery) allow applicants to send many signals, many applicants signal to and match with programs with which they have some prior connection.

Ozair, Ahmad, Jacob T. Hanson, Donald K. Detchou, Matthew P. Blackwell, Abigail Jenkins, Marianne I. Tissot, Umaru Barrie et al. "Program Signaling and Geographic Preferences in the United States Residency Match for Neurosurgery." Cureus 16, no. 9 (2024).


Abstract: Postgraduate residency training has long been the cornerstone of academic medicine in the United States. The Electronic Residency Application Service (ERAS), managed by the Association of American Medical Colleges (AAMC), is the central residency application platform in the United States for most clinical specialties, with the National Residency Matching Program (NRMP) being the algorithm for matching residency programs with applicants. However, the determination of the best fit between ERAS applicants and programs has been increasingly challenged by the rising number of applicants per residency spot. This application overburdening across competitive specialties led to several adverse downstream effects, which affected all stakeholders. While several changes and proposals were made to rectify the issue of application overburdening, the 2020-2021 ERAS Match Cycle finally saw several competitive specialties, including otolaryngology and urology, utilize a new system of supplemental residency application based on preference signals/tokens. These tokens permit applicants to electronically signal a select number of programs in a specialty of choice, with the program reviewing the application now cognizant that they have been signaled, i.e., the applicant has chosen to use up a limited set of signals for their program. Initial results from otolaryngology and urology, as described in this article, indicated the value of this new system to both applicants and educators. Given the favorable outcomes and broader uptake of the system among other specialties, the field of neurosurgery adopted the utilization of the ERAS-based program signaling and geographic preference for the first time for the 2022-2023 Residency Application Cycle and later opted to continue them for the 2023-2024 and 2024-2025 cycles. For the 2024-2025 Match Cycle, neurosurgery applicants have 25 signals, i.e., a "high-signal" approach, where non-signaled programs have a low interview conversion rate. This literature review discusses the rationale behind the change, the outcomes of other competitive specialties from prior cycles, the evolving nature of the change, and the potential impact on applicants and programs. As we describe in this review, signaling may potentially represent a surrogate form of an application cap. Other considerations relate to cost savings for both applicants and programs from a high-signal approach in neurosurgery. These modifications represent a foundational attempt to alleviate the application overburdening and non-holistic review in the residency application process, including for neurosurgery. While these changes have been a welcomed addition for all stakeholders in residency match cycles so far, further prospectively directed surveys along with qualitative research studies are warranted to better delineate the downstream impact of these changes and guide further optimization of the application system.







Wednesday, July 17, 2024

Becoming a matchmaker

 The company built around the marriage pact is now offering matchmaking tools to the public: Matchbox.

"Matchbox is the matching algorithm behind your next great event.

"We know how to make great matches, but the event is yours⁠—⁠decide who to invite, where to host, and when.

"We’ll give you everything you need to run the matching algorithm."

Sunday, June 16, 2024

Internal Talent Markets, by Cowgill, Davis , Montagnes, and Perkowski

 Here's a paper that deals with the tradeoff between centralized assignment and market-like mechanisms for job assignment within a firm, 

Stable Matching on the Job? Theory and Evidence on Internal Talent Markets, by Bo Cowgill , Jonathan M. V. Davis , B. Pablo Montagnes , Patryk Perkowski, Managment Science, Published Online:6 Jun 2024https://doi.org/10.1287/mnsc.2023.01373

Abstract: "A principal often needs to match agents to perform coordinated tasks, but agents can quit or slack off if they dislike their match. We study two prevalent approaches for matching within organizations: centralized assignment by firm leaders and self-organization through market-like mechanisms. We provide a formal model of the strengths and weaknesses of both methods under different settings, incentives, and production technologies. The model highlights trade-offs between match-specific productivity and job satisfaction. We then measure these trade-offs with data from a large organization’s internal talent market. Firm-dictated matches are 33% more valuable than randomly assigned matches within job categories (using the firm’s preferred metric of quality). By contrast, preference-based matches (using deferred acceptance) are only 5% better than random but are ranked (on average) about 38 percentiles higher by the workforce. The self-organized match is positively assortative and helps workers grow new skills; the firm’s preferred match is negatively assortative and harvests existing expertise."


"In our empirical results, we find a high degree of match-specific productivity and specialization. As a result, there are large potential gains in match quality from the executive’s perspective. However, workers and managers are apathetic about these assignments. Our results suggest that these differences arise in part through differences in assortative matching. In the workforce-driven match, the firm’s best workers and managers team up together. However, from the CEO’s perspective, a good manager is more helpful in carrying the bad workers. We also find that workers prioritize opportunities for on-the-job skill development—especially in non–firm-specific skills—and the firm does not."

Saturday, June 1, 2024

The Path to a Match for Interventional Cardiology Fellowships

The Society for Cardiovascular Angiography & Interventions has started a fellowship match, and here's an article describing the familiar marketplace failure that led to that decision, involving unraveling of application, interview and appointment dates, with the resulting congestion and exploding offers, and the process of reaching sufficient consensus to move to a centralized match ( to be run by the NRMP).

The Path to a Match for Interventional Cardiology Fellowship: A Major SCAI Initiative  by Douglas E. Drachman MD, FSCAI (Chair) a, Tayo Addo MD b, Robert J. Applegate MD, MSCAI c, Robert C. Bartel MSc, CAE d, Anna E. Bortnick MD, PhD, MSc, FSCAI e, Francesca M. Dea d, Tarek Helmy MD, MSCAI f, Timothy D. Henry MD, MSCAI g, Adnan Khalif MD, FSCAI h, Ajay J. Kirtane MD, SM, FSCAI i, Michael Levy MD, MPH, FSCAI j, Michael J. Lim MD, MSCAI k, Ehtisham Mahmud MD, MSCAI l, Nino Mihatov MD, FSCAI m, Sahil A. Parikh MD, FSCAI i, Laura Porter CMP d, Abhiram Prasad MD n, Sunil V. Rao MD, FSCAI o, Louai Razzouk MD, MPH, FSCAI o, Samit Shah MD, PhD, FSCAI p, Adhir Shroff MD, MPH, FSCAI q, Jacqueline E. Tamis-Holland MD, FSCAI r, Poonam Velagapudi MD, FSCAI s, Fredrick G. Welt MD, FSCAI t, J. Dawn Abbott MD, FSCAI (Co-Chair), Journal of the Society for Cardiovascular Angiography & Interventions, in press.

"Abstract: The field of interventional cardiology (IC) has evolved dramatically over the past 40 years. Training and certification in IC have kept pace, with the development of accredited IC fellowship training programs, training statements, and subspecialty board certification. The application process, however, remained fragmented with lack of a universal process or time frame. In recent years, growing competition among training programs for the strongest candidates resulted in time-limited offers and high-pressure situations that disadvantaged candidates. A grassroots effort was recently undertaken by a Society for Cardiovascular Angiography & Interventions task force, to create equity in the system by establishing a national Match for IC fellowship. This manuscript explores the rationale, process, and implications of this endeavor."


"over the past several years program directors and candidates found that the process has devolved, with wide variation in application timelines and on-the-spot offers, which disadvantage candidates and programs looking to interview a range of applicants.

"The pressures and unfair features of the existing system were further fueled by the transition to virtual interviews related to the COVID-19 pandemic. With logistics of travel no longer a consideration, programs could commence interviews nearly immediately after the applications became available. This led to more candidates being interviewed in rapid succession, and a system evolved in which programs quickly assessed candidates, offered positions, and applied pressure for candidates to accept offers or be passed over for other candidates.

"In response to the shortcomings of the current system, members of Society for Cardiovascular Angiography & Interventions (SCAI) were inspired to lead a grassroots educational campaign to organize IC program directors and the broader interventional community to commit to a regulated “Match” process under the established National Resident Match Program (NRMP). This manuscript provides an account of how this process unfolded and how a Match for IC fellowship was ultimately created.

...

"From the applicant’s perspective, the lack of a structured timeline for the application process required candidates to make career decisions early in the first year of cardiovascular disease training and to compose their application materials 2 years in advance of starting IC training. With ERAS open to application submission in the fall of the second year for the December release to programs, fellows had limited time on clinical rotations to determine their interest and aptitude for IC. Additionally, letters of recommendation, written at this early stage, risked not being fully reflective of each candidate’s capacity to improve and develop the technical skills and clinical knowledge important for success in the field. There were other disadvantages to candidates in the existing system. Fellows at programs with an IC fellowship had an advantage of securing an internal spot but were often pressured to limit their exploration of the opportunities at other programs, potentially disadvantaging them in the long term.

"Another problem with the existing system was that the pressure to recruit candidates on a tight timeline limited the opportunity to interview applicants from a wide variety and diversity of programs, potentially reducing the ability to recruit underrepresented candidates from varied programs. Despite an overall increase in the diversity of physicians entering the workforce,11 there has been little change in the applicant pool for IC over the years, with fewer than 5% of applicants self-reporting as Black race or Hispanic ethnicity and only 10% identifying as women.12

"Competition among the programs, each vying for the seemingly strongest candidates, degenerated into a system that favored quick decision-making on the part of programs to offer positions as early as possible. The influence of the COVID-19 pandemic in 2020 and 2021 negatively impacted an already high-pressure application process, compounding its many weaknesses.13 Fellowship interviews were hosted virtually rather than in person, which enabled candidates to interview at a greater number of programs without the need to travel. In addition, the virtual format accelerated the tempo of an application process that was already felt to be too fast, resulting in an increase in so-called “exploding offers”—offers that required the accepted candidate to respond within a very short timeframe or risk losing the offer. This practice placed significant pressure on candidates to make quick decisions, often forcing them to determine whether to accept the offer from 1 institution before having the opportunity to participate in interviews with—let alone see and evaluate—other programs or fully understand the ramifications of accepting an offer on their personal lives. At the same time, the accelerated timetable left many programs scrambling to identify applicants, as the number of available candidates diminished rapidly due to applicants accepting time-sensitive, exploding offers.

...

"As with other national efforts of this magnitude, the path to develop consensus in favor of a Match was not without challenges. There were several program directors around the country who strongly opposed the institution of a Match. These were well-regarded academicians and clinician educators who expressed very sincere concerns about the impact on fellows in their programs. The members of the SCAI Match Task Force addressed as many concerns as possible, providing the information necessary for each program director to make the best decision for their institution. A minority of program directors remained opposed to the initiative or did not engage with Task Force members despite multiple attempts to be contacted.

"The Match campaign proved highly effective, and by November 2022, the 75% threshold of programs and positions to implement the Match was met

...

"As the sponsor of the Match, SCAI considered the pros and cons of the “All In Policy,” where registered programs must attempt to fill all ACGME positions at the program through the Match.15,16 SCAI opted out of the “All In Policy” to allow programs to have flexibility for unique situations that require commitment to a candidate outside of the Match. 

...

"As a result of the successful implementation of the Match in IC, the first Match cycle for incoming IC fellows will open in the summer of 2024. Individuals eligible to apply include cardiovascular disease fellows in their third or final year of training and graduates who have completed fellowship and are in clinical practice. This class will start IC training in July 2025"



Sunday, May 26, 2024

Recent papers on matching: May GEB

 The May issue of Games and Economic Behavior has several papers on matching that caught my eye:

Games and Economic Behavior, Volume 145, May 2024

Strong core and Pareto-optimality in the multiple partners matching problem under lexicographic preference domains, by Péter Biró and Gergely Csáji

Abstract: We study strong core and Pareto-optimal solutions for multiple partners matching problem under lexicographic preference domains from a computational point of view. The restriction to the two-sided case is called stable many-to-many matching problem and the general one-sided case is called stable fixtures problem. We provide an example to show that the strong core can be empty even for many-to-many problems, and that deciding the non-emptiness of the strong core is NP-hard. On the positive side, we give efficient algorithms for finding a near feasible strong core solution and for finding a fractional matching in the strong core of fractional matchings. In contrast with the NP-hardness result for the stable fixtures problem, we show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many-to-many problems. Finally, we show that for reverse-lexicographic preferences the strong core is always non-empty in the many-to-many case.


Bayesian stable states, by Yi-Chun Chen and Gaoji Hu 

Abstract: This paper extends the Bayesian stability notion of Liu (2020) to define the Bayesian stability of a market state, which consists of a matching outcome and an information structure. The information structure can be arbitrarily heterogeneous and can accommodate learning among agents. We first establish that a Bayesian stable matching function of Liu (2020) can be recast as Bayesian stable market states with homogeneous information. We then illustrate the usefulness of such an extension by (i) refining Liu's Bayesian efficiency notion to define the Bayesian efficiency of a market state and (ii) generalizing his result—that Bayesian stable matching functions are Bayesian efficient—to an analogous one for market states. More importantly, we show that (iii) a decentralized matching process converges to a Bayesian stable market state and thereby offer a decentralized foundation for Liu's Bayesian stable matching function.


Efficient matching under general constraints  by Kenzo Imamura, Yasushi Kawase

Abstract: We study indivisible goods allocation problems under constraints and provide algorithms to check whether a given matching is Pareto efficient. We first show that the serial dictatorship algorithm can be used to check Pareto efficiency if the constraints are matroid. To prove this, we develop a generalized top trading cycles algorithm. Moreover, we show that the matroid structure is necessary for obtaining all Pareto efficient matchings by the serial dictatorship algorithm. Second, we provide an extension of the serial dictatorship algorithm to check Pareto efficiency under general constraints. As an application of our results to prioritized allocations, we discuss Pareto improving the deferred acceptance algorithm.


Friday, May 3, 2024

Matching markets and organ transplantation at the Istituto Superiore di Sanità in Rome on Monday

 I'm traveling this weekend to help inaugurate  the celebration of the 90th anniversary of Italy's Istituto Superiore di Sanità (Higher Institute of Health).  Below is their press release, which also notes that my talk will mark the 20th anniversary of the publication of my paper with Tayfun Sonmez and Utku Unver:

Roth, Alvin E., Tayfun Sonmez, and M. Utku Unver, "Kidney Exchange," Quarterly Journal of Economics, 119, 2, May, 2004, 457-488


Nobel Prize winner Alvin Roth opens the series of conferences dedicated to the 90th anniversary of the ISS

"Thanks to his work, 'crossover' kidney transplants are possible; next May 6th lectio magistralis in person and streaming.

"The cycle of scientific conferences that the Istituto Superiore di Sanità dedicates to the 90th anniversary of its foundation begins with a lectio magistralis by the Nobel Prize winner for economics Alvin Roth. On May 6th at 12.30 pm, Professor Roth, whose work has paved the way for the possibility of carrying out crossed kidney transplants between incompatible couples, will hold a keynote address entitled "Matching markets and organ transplantation".

"Exactly 20 years ago, in May 2004, Roth published "Kidney Exchange" in the Quarterly Journal of Economics (the oldest economic studies journal in the United States), the article in which the scholar exposed his "matching theory" by applying it to problem of compatibility between donor and recipient in living kidney transplantation and the need to find a sufficient number of donors for patients waiting for an organ. Roth demonstrated mathematically that, by cross-referencing the immunological data of all couples in which a healthy person wants to donate a kidney to a sick family member but cannot do so due to lack of compatibility, all patients could receive the organ they need. For his studies on stable allocations, defined by the Royal Swedish Academy as "a masterpiece of economic engineering", Roth was awarded the Nobel Prize in 2012.

"Starting from that first algorithm developed by Roth, today cross-kidney transplant programs between incompatible couples (called "crossover") have become a reality in many countries around the world: in Italy 132 transplants of this type have been carried out so far thanks to crossing of 85 pairs of donors and recipients, as part of a complex clinical and logistical program managed by the National Transplant Center which has so far involved 20 different hospitals. In 2023 alone there were 17 crossover transplants, of which 2 were carried out thanks to international exchange programmes: the first, last June, performed in Padua thanks to the crossing with two other Spanish couples, one in Bilbao and one in Barcelona, and the second in Vicenza, with an exchange organized with the Porto hospital.

"Professor Roth will hold his dissertation at the invitation of the National Transplant Center, the Galilean School of Higher Studies and the Department of Economic and Business Sciences of the University of Padua, the university at which the Stanford University economist will continue his series of conferences in Italy. The event, which will be held in the Pocchiari Hall of the Higher Institute of Health starting from 12.30, will be attended by Rocco Bellantone (president of the ISS), Giuseppe Feltrin (director of the National Transplant Center), Antonio Nicolò (professor of Economic Theory at the University of Padua) and Lucrezia Furian ( responsible for the Kidney and Pancreas Transplant Surgery Unit - Department of Surgical, Oncological and Gastroenterological Sciences of the University Hospital of Padua).

"It will be possible to follow the event in person (the request for accreditation can be made to ufficio.stampa@iss.it) and in streaming on the Institute's home page."

Thursday, April 25, 2024

The Matching Society by Melchior Simioni and Philippe Steiner

"If we put on the glasses of economic sociology, it appears ... that matching corresponds to a specific form of coordination close but distinct from both planning and the market."

That's a sentence that caught my eye (using Google translate) from the recent book by the French sociologists Melchior Simioni and Philippe Steiner

La société du matching (The Matching Society) 


Here's how the publisher's web page introduces it:

"The upheavals brought about by the irruption of matching technology, in all its dimensions, are updating major challenges in our societies. The matching society is not the future of our modern societies, it is its present. The ambition of this essay is to to understand what it changes in our lives.  

"At several decisive stages of our lives, we entrust our fate to algorithms that sort individuals according to a very singular pattern: we choose and we are chosen at the same time. Access to resources as essential as training (with Parcoursup or Affelnet), a romantic partner (Tinder, Meetic and so many others), certain care or a job depends on this technology.

"Unlike the market relationship, where paying is enough, or social benefits, which are paid as a matter of right, matching presupposes a new social relationship: we express our wishes according to the information at our disposal and it is on the basis of the data we provide that the selection is made.

"This principle profoundly changes our relationship with the collective. Because it forces us to tell the truth about ourselves, our hopes, our desires, it accelerates the advent of a singularist society."

########

I've had occasion to blog about the work of Professor Steiner before:

Friday, August 12, 2022

Monday, November 30, 2020

Sunday, March 31, 2024

MATCH-UP 2024 7th International Workshop on Matching Under Preferences, Oxford, 9 - 11 September, 2024

 Here's the announcement and call for papers of the latest edition of the Match-Up series of conferences.

MATCH-UP 2024   7th International Workshop on Matching Under Preferences 

University of Oxford, United Kingdom   9 - 11 September, 2024

 "MATCH-UP 2024 is the 7th workshop in an interdisciplinary and international workshops in the series on matching under preferences. It will take place on 9 - 11 September 2024, hosted by the University of Oxford, United Kingdom.

"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 preference lists 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.

"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, and thus a key objective is to bring together the research communities of the related areas.

"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)

Thursday, January 18, 2024

It's a dominant strategy for deferred acceptance proposers to state true preferences in the marriage problem: simple proof

This post is not entirely self-contained, it is in some sense a continuation of and addition to my talk last year at the Simons Institute, which you can see at this link: 

Simple Proofs of Important Results in Market Design-- (video of my talk at Berkeley's Simons Institute)

In that talk (based on work I'm doing with Mike Ostrovsky) I defined the marriage model of Gale and Shapley, gave necessary definitions,  and following the style of their original article, I showed simple, verbal proofs of a number of results, including the constant employment ("lone wolf") theorem:

Constant employment theorem: In a "marriage market"(M,W, P) with strict preferences, the set of people who are single is the same for all stable matchings.

Now based on that theorem, here's a simple proof of the dominant strategy theorem, inspired by a  very short proof (with attributions to Alex Teytelboym and Ravi Jagadeesan) in Nick Arnosti's recent blog post A Short Proof of the Truthfulness of DA by Nick Arnosti 2023/10/01 

Here's the theorem to be proved:

Dominant Strategy Theorem (Dubins and Freedman, Roth): In the M-optimal stable mechanism for the marriage problem (e.g. when the man-proposing deferred acceptance algorithm is used, which produces the most favorable stable matching for every man) it is a dominant strategy for each man i to state a preference list corresponding to his true preferences ≻.


Notation: for any preference ≻′ of player i, an outcome is ≻′-stable if it is stable when i reports ≻′ and everyone else's preferences remain constant.

Proof (following Arnosti)

Suppose that the theorem is false. That is, suppose there exist preferences for all other agents such that when i reports ≻, the resulting ≻-stable matching μ gives μ(i)=w, and when i reports ≻′ ≠ ≻, the resulting ≻′-stable matching μ′ gives μ′(i)=w′≻w. (Note that the final comparison is ≻, i.e. take ≻ to be i's true preference list.)

Consider the market in which i lists w′ as the only acceptable woman (and everyone else's preferences remain fixed). We'll see that this will lead to a contradiction with the constant employment theorem, by implying that there must exist a {w'}-stable matching in which i matches to w′, and another {w'}-stable matching in which i is unmatched. 

1. The matching μ′ assigns i to w′. Because it is ≻′-stable, it must also be {w′}-stable: the only difference between ≻′ and {w'} is that we have removed women from i’s list, which clearly does not create any new blocking pairs.

Note: this step uses only the definition of stability.

2. Let ≻′′ be the deviation in which i truncates ≻ below w′ (i leaves everyone below w′ off of his list), and let μ′′ be the resulting matching.

a. The matching μ′′ leaves i unassigned.  This follows from the fact that, if it matched i, then μ″ would be ≻-stable, since ≻ differs from ≻'' only in that it restores the truncated elements of i's preference, which would be below i's match and hence not introduce any new blocking pairs (since it wouldn't change i's match). But  μ″ can't be ≻-stable,  because w is i’s best ≻-stable partner by assumption, and is worse than all women listed in ≻′′.*

Note: this step uses the definition of stability and fact that μ is optimal for i.

b. Because μ′′  (which leaves i unassigned) is ≻′′-stable, it is also {w′}-stable: the only difference between ≻′′ and {w′} is that we have removed women from i’s list, which does not create any new blocking pairs).

Note: this step uses only the definition of stability.

To recap: μ′ and μ′′ must both be {w′}-stable, but i is matched to w′ by μ′ and unmatched by μ′′ (a contradiction).

This completes the proof.

*Note that the reason μ′′ isn't ≻-stable is that it leaves i unassigned, and so creates new blocking pairs involving i with respect to his true full preferences.


Monday, January 15, 2024

Matching and market design in the latest GEB (stack overflow...)

 The current (January 2024) issue of Games and Economic Behavior presents an increasingly common dilemma (faced by scholars in burgeoning fields, and maybe by aging scholars...). Papers I should read are being written much faster than I can read them.

Here are 9 papers in that issue that are pretty clearly about matching and market design (which leaves out some papers on auctions and one on unraveling of the timing of markets) :

  1. Obvious manipulations of tops-only voting rules

    Pages 12-24
    View PDF
  2. Rejection-proof mechanisms for multi-agent kidney exchange

    Pages 25-50
    View PDF