Refugee resettlement and the top trading cycles algorithm, by Farajzadeh, Killea, Teytelboym, and Trapp

 Here's a recent paper that (among other things) considers using the top trading cycles algorithm for matching refugees to sponsors (under a special program for Ukraine), to satisfy the location preferences of refugees.

Optimizing Sponsored Humanitarian Parole by Fatemeh Farajzadeh, Ryan B. Killea, Alexander Teytelboym, Andrew C. Trapp, working paper, 2023

Abstract: The United States has introduced a special humanitarian parole process for Ukrainian citizens in response to Russia’s 2022 invasion of Ukraine. To qualify for parole, Ukrainian applicants must have a sponsor in the United States. In collaboration with HIAS, a refugee resettlement agency involved in the parole process, we deployed RUTH (Refugees Uniting Through HIAS), a novel algorithmic matching system that is driven by the relocation preferences of refugees and the priorities of US sponsors. RUTH adapts Thakral [2016] Multiple-Waitlist Procedure (MWP) that combines the main First-In/First-Out (FIFO) queue with location specific FIFO queues in order to effectively manage the preferences of refugees and the supply of community sponsors. In addition to refugee preferences and sponsor priorities, RUTH incorporates various feasibility considerations such as community capacity, religious, and medical needs. The adapted mechanism is envy-free, efficient and strategy-proof for refugees. Our analysis reveals that refugee preferences over locations are diverse, even controlling for observables, by demonstrating the difficulty of solving a much simpler problem than modeling preferences directly from observables. We use our data for two counterfactual simulations. First, we consider the effects of increased waiting times for refugees on the quality of their matches. We find that with a periodic Top Trading Cycles algorithm, increasing period length from 24 days to 80 days, improves average rank of a refugee’s match from 3.20 to 2.44. On the other hand, using the available preference data RUTH achieved an average rank of 4.07 with a waiting time of 20 days. Second, we estimate the arrival rates of sponsors in each location that would be consistent with a long-run steady state. We find that more desirable locations (in terms of refugee preferences) require the highest arrival rates suggesting that preferences might be a useful indicator for investments in sponsorship capacity. Our study highlights the potential for preference-based algorithms such as RUTH to improve the efficiency and fairness of other rapidly-deployed humanitarian parole processes.

#######

Earlier:

Sunday, December 18, 2022

Resettling refugees using preferences of refugees and hosts

Minimal envy mechanisms, by Julien Combe

 Here's an article I missed when it came out online:

Reallocation with priorities and minimal envy mechanisms, by Julien Combe, Economic Theory volume 76, 551–584 (2023)

"Abstract: We investigate the problem of reallocation with priorities where one has to assign objects or positions to individuals. Agents can have an initial ownership over an object. Each object has a priority ordering over the agents. In this framework, there is no mechanism that is both individually rational (IR) and stable, i.e. has no blocking pairs. Given this impossibility, an alternative approach is to compare mechanisms based on the blocking pairs they generate. A mechanism has minimal envy within a set of mechanisms if there is no other mechanism in the set that always leads to a set of blocking pairs included in the one of the former mechanism. Our main result shows that the modified Deferred Acceptance mechanism (Guillen and Kesten in Int Econ Rev 53(3):1027–1046, 2012), is a minimal envy mechanism in the set of IR and strategy-proof mechanisms. We also show that an extension of the Top Trading Cycle (Karakaya et al. in J Econ Theory 184:104948, 2019) mechanism is a minimal envy mechanism in the set of IR, strategy-proof and Pareto-efficient mechanisms. These two results extend the existing ones in school choice."

Pitfalls of digital scholarship: Machiavelli and Matching

 One of the alluring features of the digitization of texts is that they can be searched, their citations can be examined and cross-referenced, and facts about texts, and the literatures that they comprise, can be detected.  But of course,  digital searches can also lead you astray.

Something like that may have happened in this study of business ethics. (Relax, this isn't a blog post about questionable ethics in science.)  

Maity, M., Roy, N., Majumder, D. et al. Revisiting the Received Image of Machiavelli in Business Ethics Through a Close Reading of The Prince and Discourses. J Bus Ethics (2023). https://doi.org/10.1007/s10551-023-05481-2

The authors of the above paper searched in journals related to business and economics, for papers  about Niccolò Machiavelli, the 16th century author of The Prince, whose name has entered into the language to describe the kind of advice he gave: Machiavellian.

Looking at the most highly cited papers, and their network of co-citations (i.e. citations of each other) they find three clusters in the Machiavelli literature. They note that two of the clusters include many citations from one to the other, but that the third cluster (in green) is not connected to the other two.  The third cluster they label "matching problems in markets." (In fairness, the authors of the paper note this separation, and concentrate their analysis on the first two clusters.)

Here are the papers in the clusters. The papers in cluster 3 will be familiar to many readers of this blog.

Here in larger font is cluster 3, of papers on "Matching problems in markets": Abdulkadiroǧlu et al. (2003), Abdulkadiroǧlu and Sönmez (2003), Dubins and Freedman, (1981), Gale and Shapley (1962), Gale and Sotomayor (1985a), Gale and Sotomayor (1985b), Kojima and Pathak (2009), Roth (1982, 1984a, 1984b, 1985, 2002), Roth and Sotomayor (1990), Roth and Peranson (1999).

This cluster indeed contains well cited papers that cite one another. Yet I'm pretty sure that none of them cite Machiavelli, nor would most readers think that they connect to The Prince.

This latter cluster was almost surely included because of the titles of two of the included papers, neither of which in fact cites Machiavelli. (His name made it into the titles in a sort of jokey way, having to do with the fact that players in matching games may sometimes profit from behaving unstraightforwardly.) They are:

Dubins, Lester E., and David A. Freedman. "Machiavelli and the Gale-Shapley algorithm." The American Mathematical Monthly 88, no. 7 (1981): 485-494.

and

Gale, David, and Marilda Sotomayor. "Ms. Machiavelli and the stable matching problem." The American Mathematical Monthly 92, no. 4 (1985): 261-268.

But Machiavelli might be proud to be included in an economic literature on incentives.

The critical role of Kelso & Crawford in the development of the stable matching literature

 In the physics literature there has long been an interest in economics (econophysics) that takes many forms. Here's a review of stable matching, which identifies Kelso and Crawford as a critical step in the evolution of the matching literature following Gale and Shapley.

Danilov, V.I. Review of the Theory of Stable Matchings and Contract Systems. Computational Mathematics and Mathematical Physics. 63, 466–490 (2023). https://doi.org/10.1134/S0965542523030065

"The real development was started by the work of Kelso and Crawford [123], who considered the more general problem of hiring workers (many-to-one). Their problem statement differed from the college admission problem in that the behavior of firms was more flexible than simply setting a quota in [81]. When hiring workers, the firm dealt with a “crowd” of candidates and chose the group of workers it needed from among this crowd. The description of the behavior of such a firm was no longer given by a simple ranking of candidates, but by a choice function. Below, we consider such functions in more detail. An important merit of Kelso and Crawford was that they found the “correct” condition on the choice function, which generalized the Gale–Shapley “linear” choice and which had previously appeared in economics as a substitutability condition. (Later it turned out that such a condition had already been introduced in the choice theory [152] under the name path independence.) Using this condition, Kelso and Crawford [123] showed that the Gale–Shapley algorithm works and gives a stable distribution of workers among firms. In [88], the notion of substitutability was used in the case of indivisible goods and led to a series of papers on this topic (see [79, 51, 65, 103]). Two years later, Roth [158] showed that the same substitutability condition also works well in a many-to-many situation, when firms could hire many workers and workers could work in several firms, see [62]. The results of this direction were summed up in the monograph [160]."

Transition from medical school to residency: defending the parts that work well (namely the NRMP Resident Match)

This post is about a recently published paper concerning the design of the market for new doctors in the U.S.  But it will require some background for most readers of this blog.   The short summary is that the market is experiencing problems related to congestion, and one of the proposals to address these problems was deeply flawed, and would have reduced market thickness and caused substantial direct harm to participants if implemented, and created instabilities that would likely have caused indirect harms to the match process in subsequent years. But this needed to be explained in the medical community, since that proposal was being  very actively advocated.

For those of you already steeped in the background, you can go straight to the paper, here.

Itai Ashlagi, Ephy Love, Jason I. Reminick, Alvin E. Roth; Early vs Single Match in the Transition to Residency: Analysis Using NRMP Data From 2014 to 2021. J Grad Med Educ 1 April 2023; 15 (2): 219–227. doi: https://doi.org/10.4300/JGME-D-22-00177.1

If the title doesn't remind you of the vigorous advocacy for an early match for select positions, here is some of the relevant back story.

The market for new doctors--i.e. the transition from medical school to residency--is experiencing growing pains as the number of applications and interviews has grown, which imposes costs on both applicants and residency programs.  

Below is a schematic of that process, which begins with applicants submitting applications electronically, which makes it easy to submit many.  This is followed by residency programs inviting some of their applicants to interview. The movement to Zoom interviews has made it easier to have many interviews also (although interviews were multiplying even before they moved to Zoom).  

After interviews, programs and applicants participate in the famous centralized clearinghouse called The Match, run by the NRMP. Programs and applicants each submit rank order lists (ROLs) ranking those with whom they interviewed, and a deferred acceptance algorithm (the Roth-Peranson algorithm) produces a stable matching, which is publicly announced on Match Day. (Unmatched people and positions are invited into a now computer-mediated scramble, called SOAP, and these matches too are announced on Match  Day.)

The Match had its origins as a way to control the "unraveling" of the market into inefficient bilateral contracts, in which employment contracts were made long before employment would commence, via exploding offers that left most applicants with very little ability to compare options.  This kind of market failure afflicted not only the market for new physicians (residents), but also the market for later specialization (as fellows). Consequently, over the years, many specialties have turned to matching for their fellowship positions as well.

  The boxes in brown in the schematic are those that constitute "The Match:" the formulation and submission of the ROLs, and the processing of these into a stable matching of programs to residents.  Congestion is bedeviling the parts in blue.

The boxes colored brown are 'The Match' in which participants formulate and submit rank order lists (ROLs), after which a deferred acceptance algorithm produces a stable matching of applicants to programs, which is accepted by programs and applicants on Match Day. The boxes in blue, the applications and interviews that precede the Match, are presently suffering from some congestion.  Some specialties have been experimenting with signals (loosely modeled on those in the market for new Economics PhDs, but implemented differently by different medical specialties).

The proposal in question was to divide the match into two matches, run sequentially, with the first match only allowing half of the available positions to be filled.  The particular proposal was to do this first for the OB-GYN specialty, thus separating that from the other specialties in an early match, with only half of the OB-GYN positions available early.

This proposal came out of a study funded by the American Medical Association, and it was claimed, without any evidence being offered, that it would solve the current problems facing the transition to residency.  Our paper was written to provide some evidence of the likely effects, by simulating the proposed process using the preferences (ROLs) submitted in previous years.  

The results show that the proposal would largely harm OB-GYN applicants by giving them less preferred positions than they could get in a traditional single match, and that it would create instabilities that would encourage strategic behavior that would likely undermine the successful operation of the match in subsequent years.

Itai Ashlagi, Ephy Love, Jason I. Reminick, Alvin E. Roth; Early vs Single Match in the Transition to Residency: Analysis Using NRMP Data From 2014 to 2021. J Grad Med Educ 1 April 2023; 15 (2): 219–227. doi: https://doi.org/10.4300/JGME-D-22-00177.1

Abstract:

"Background--An Early Result Acceptance Program (ERAP) has been proposed for obstetrics and gynecology (OB/GYN) to address challenges in the transition to residency. However, there are no available data-driven analyses on the effects of ERAP on the residency transition.

"Objective--We used National Resident Matching Program (NRMP) data to simulate the outcomes of ERAP and compare those to what occurred in the Match historically.

"Methods--We simulated ERAP outcomes in OB/GYN, using the de-identified applicant and program rank order lists from 2014 to 2021, and compared them to the actual NRMP Match outcomes. We report outcomes and sensitivity analyses and consider likely behavioral adaptations.

"Results--Fourteen percent of applicants receive a less preferred match under ERAP, while only 8% of applicants receive a more preferred match. Less preferred matches disproportionately affect DOs and international medical graduates (IMGs) compared to US MD seniors. Forty-one percent of programs fill with more preferred sets of applicants, while 24% fill with less preferred sets of applicants. Twelve percent of applicants and 52% of programs are in mutually dissatisfied applicant-program pairs (a pair in which both prefer each other to the match each received). Seventy percent of applicants who receive less preferred matches are part of a mutually dissatisfied pair. In 75% of programs with more preferred outcomes, at least one assigned applicant is part of a mutually dissatisfied pair.

"Conclusions--In this simulation, ERAP fills most OB/GYN positions, but many applicants and programs receive less preferred matches, and disparities increase for DOs and IMGs. ERAP creates mutually dissatisfied applicant-program pairs and problems for mixed-specialty couples, which provides incentives for gamesmanship."

************

I'm hopeful this paper will effectively contribute to the ongoing discussion of how, and how not, to modify the design of the whole process of transition to residency with an aim to fixing the parts that need fixing, without damaging the parts that work well, i.e. while doing no harm. 

(Signaling will likely continue to play a role in this.)

Predicting the future in Japan: Kojima, Narita, Saito and Uchida

A new book in Japanese has appeared, whose translated title is "Future Prediction of Geniuses."

My attempt to post about it caused html errors on the blog, so this is a replacement for the original post, with just a link to the twitter thread here: https://twitter.com/booksmagazine/status/1611291463291404288

Google translate works pretty well at letting English speakers know what it says.

Resettling refugees using preferences of refugees and hosts

 Here's the latest report from HIAS on matching Ukrainian refugees to hosts in the U.S.

How an Innovative Algorithm Helps Ukrainian Refugees Find New Homes  By Brian Zumhagen

"Odessa residents Max and Yuna* fled Ukraine on the day the Russian invasion began, February 24, 2022. It took them 7 days to reach the Polish border.

"The couple, both in their early 20s, spent the next several months in Poland. In September, they started applying for relocation to the United States with the help of HIAS. But unlike most refugees, Max and Yuna were among the first to use a new system that allowed them to list their preferences about where to be resettled, and any special needs they might have — thanks to a matching algorithm known as RUTH, which stands for Refugees Uniting Through HIAS. (The name was also inspired by the biblical Book of Ruth, which tells the story of how Ruth is herself welcomed as a foreigner).

...

"Back in Poland, HIAS Relocation Officer Denis Ruksha said some of the refugees from Ukraine he works with are relocated through European Welcome Circles, while others are resettled through circles in the United States. For those heading to the U.S., Ruksha has been using the RUTH platform for the last 3 months, entering beneficiaries’ preferences about where they would like to be relocated, along with other information. “It allows people to mention almost everything they think is relevant,” he said. In the U.S., volunteers in HIAS Welcome Circles can, in turn, enter their own preferences, such as the number of people they can host.

...

"RUTH isn’t the first computer system with a human name that HIAS has used to make its resettlement work easier and more effective. In 2018, the organization worked with partners to create matching software named after the first immigrant registered at Ellis Island in 1892. “Annie MOORE” (Matching and Outcome Optimization for Refugee Empowerment) used past employment data to direct refugees to locations where they would have the greatest chance of finding work.

"But where Annie focused on optimizing estimated employment outcomes, RUTH makes the relocation process faster and more transparent, according to the new platform’s developers. “This is the first time ever that preferences of refugees and priorities of hosts have been systematically used in the resettlement process,” said Andrew Trapp, associate professor of operations and industrial engineering at Worcester Polytechnic Institute.

"His colleague, Alexander Teytelboym, associate professor of economics at the University of Oxford, put it this way: “We think people are more likely to thrive in places where they prefer to live. Citizens are given a choice about almost anything of such consequence — so why shouldn’t refugees?”

********

Here are my previous posts on HIAS and refugee resettlement 

Limiting congestion by limiting applications, or making them costly

 Here's a paper that investigates two alternatives to limiting congestion in college admissions: one is to limit applications, and the other is to add a small cost for each additional application. (This is a current topic of discussion in a number of other applications, including matching of new doctors to residencies.)

Application Costs and Congestion in Matching Markets by YingHua He and Thierry Magnac, The Economic Journal,  https://doi.org/10.1093/ej/ueac038 (online early)

Abstract: "A matching market often requires recruiting agents, or ‘programmes’, to costly screen ‘applicants’, and congestion increases with the number of applicants to be screened. We investigate the role of application costs: higher costs reduce congestion by discouraging applicants from applying to certain programmes; however, they may harm match quality. In a multiple-elicitation experiment conducted in a real-life matching market, we implement variants of the Gale-Shapley deferred-acceptance mechanism with different application costs. Our experimental and structural estimates show that a (low) application cost effectively reduces congestion without harming match quality."

"Our empirical strategy is novel. It begins with a multiple-elicitation field experiment that enables us to directly evaluate the effects of application costs. The experiment involves the real-life matching of 129 applicants to the seven master’s programmes at the Toulouse School of Economics (TSE), and was conducted in May 2013 for admission in the 2013–4 academic year. The experimental market designs are three variants of the Gale-Shapley deferred-acceptance (DA) mechanism encountered in practice: the traditional DA mechanism, under which applicants can apply to all programmes without any cost; the DA mechanism with truncation (DA-T), under which applicants can apply to no more than four programmes (hence, DA-T-4); and the DA mechanism with cost (DA-C), under which applicants must write a motivation letter for each additional application beyond the first three applications. Under each mechanism, every applicant is required to submit a rank-ordered list of programmes (ROL). As applicants are informed that one of the mechanisms will be implemented, they have incentives to behave optimally under each mechanism.

"To evaluate the performance of a matching procedure, we focus on two dimensions of a matching outcome: the congestion and match quality. The former is measured by screening costs and approximated by the number of applicants to screen; the latter is measured by the welfare of both sides, the number of unmatched applicants, as well as the number of blocking pairs. A pair comprising applicant and programme blocks a matching if both would be better off by being matched together after leaving their current matches. The stability of a matching, defined as the absence of any blocking pair, is the key to the success of matching markets (Roth, 1991). Importantly, stability implies Pareto efficiency when both sides are endowed with strict preferences (Abdulkadiroğlu and Sönmez, 2013)."

Sorority rush: the paper and the podcast

 Years ago, my late student Sue Mongell and I wrote a paper about sorority rush:

Mongell, Susan, and Alvin E. Roth. "Sorority rush as a two-sided matching mechanism." The American Economic Review (1991): 441-464.
 

Just over 20 years later, you can listen to a short NPR broadcast about it on Planet Money (which leaves out a few of the details;-)

THE INDICATOR FROM PLANET MONEY

The economics behind sorority rush

October 5, 2022 by WAILIN WONG and ADRIAN MA

8-Minute Listen

"how do new recruits land at their sorority houses?

"The answer lies in a classic economic concept used in contexts ranging from organ donation to New York public high schools. Today, we're exploring matching markets"

Market design workshop at Iowa State University

 I'll give a public talk this evening to open a market design workshop tomorrow and Saturday:

Two-day Workshop: September 23-24, 2022, Heady Hall 360A, Iowa State University

Organizers: Ran Shorrer, Bumin Yenmez, Bertan Turhan  

Program: MARKET DESIGN WORKSHOP PROGRAM

Day 1: Friday, September 23, 2022 (Heady Hall 368A)

SESSION 1

8:00-8:40 Rakesh Vohra (w/ Thanh Nguyen)

“(Near) Substitute Preferences and Equilibria with Indivisibilities”

8:40-9:20 Federico Echenique (w/ Sumit Goel and SangMok Lee)

“Stable Allocations in Discrete Economies”

9:20-10:00 Marzena Rostek

“Decentralized-Market Design”

Chair: Tarun Sabarwal

------------------------------------------------------------------------------------------------

BREAK: 10:00-10:30

------------------------------------------------------------------------------------------------

SESSION 2

10:30-11:10 Karam Kang (w/ Giulia Brancaccio)

“Search Frictions and Product Design in the Municipal Bond Market”

11:10-11:50 Mariana Lavarde

“Distance to Schools and Equal Access in School Choice Systems”

11:50-12:30 Atila Abdulkadiroğlu (w/ Aram Grigoryan)

“Priority-based Assignment with Reserves and Quotas”

Chair: David Cooper

------------------------------------------------------------------------------------------------

LUNCH: 12:30-1:40 (Heady 360)

------------------------------------------------------------------------------------------------

SESSION 3

1:40-2:20 Bumin Yenmez (w/ Isa Hafalir and Fuhito Kojima)

“Design on Matroids: Diversity vs Meritocracy”

2:20-3:00 Orhan Aygün (w/ Bertan Turhan)

“Affirmative Action in India: Restricted Strategy Space, Complex Constraints, and

Direct Mechanism Design”

3:00-3:40 Nick Arnosti

“Explainable Affirmative Action”

Chair: Atila Abdulkadiroğlu

------------------------------------------------------------------------------------------------

BREAK: 3:40-4:10

------------------------------------------------------------------------------------------------

SESSION 4

4:10-4:50 Eric Budish

“The Economic Limits of Bitcoin and Anonymous, Decentralized Trust on the Blockchain”

4:50-5:30 Eduardo Azevedo (w/ David Mao, Jose Montiel Olea, and Amilcar Velez)

“A/B Testing with Gaussian Priors”

5:30-6:10 Ran Shorrer (w/ Yannai Gonczarowski and Scott Kominers)

“To Infinity and Beyond: Scaling Economic Theories via Logical Compactness”

Chair: Al Roth

---------------------------------------------------------------------------------- 

Day 2: Saturday, September 24, 2022

SESSION 5

8:00-8:40 Thayer Morrill (w/ Peter Troyan)

“Desirable Rankings: A New Method for Ranking Outcomes of a Competitive Process”

8:40-9:20 Lars Ehlers (w/ Christian Basteck)

“Strategy Proof and Envy-Free Random Assignment”

9:20-10:00 Itai Ashlagi (w/ Jacob Leshno, Pengyu Qian, and Amin Saberi)

“Price Discovery in Waiting Lists: A Connection to Stochastic Gradient Descent”

Chair: Rakesh Vohra

------------------------------------------------------------------------------------------------

BREAK: 10:00-10:30

------------------------------------------------------------------------------------------------

SESSION 6

10:30-11:10 Josue Ortega (w/ Thilo Klein)

“Improving Efficiency and Equality in School Choice”

11:10-11:50 Aram Grigoryan

“Transparency in Allocation Problems”

11:50-12:30 Inácio Bó (w/ Rustam Hakimov)

“Pick-an-Object Mechanisms”

Chair: Federico Echenique

Matching versus menus

When preferences are simple, marketplaces can match you quickly, e.g. Uber knows travelers want a nearby car that will come quickly, so it gives drivers some choices but matches travelers without asking them much. But Airbnb knows that travelers might have complex preferences, so it gives them a menu of choices to look at.

Here's a forthcoming paper by Peng Shi on what's going on.

Shi, Peng. "Optimal Matchmaking Strategy in Two-sided Marketplaces." Management Science (2022).

Abstract: Online platforms that match customers with suitable service providers utilize a wide variety of matchmaking strategies; some create a searchable directory of one side of the market (i.e., Airbnb, Google Local Finder), some allow both sides of the market to search and initiate contact (i.e., Care.com, Upwork), and others implement centralized matching (i.e., Amazon Home Services, TaskRabbit). This paper compares these strategies in terms of their efficiency of matchmaking as proxied by the amount of communication needed to facilitate a good market outcome. The paper finds that the relative performance of these matchmaking strategies is driven by whether the preferences of agents on each side of the market are easy to describe. Here, “easy to describe” means that the preferences can be inferred with sufficient accuracy based on responses to standardized questionnaires. For markets with suitable characteristics, each of these matchmaking strategies can provide near-optimal performance guarantees according to an analysis based on information theory. The analysis provides prescriptive insights for online platforms.

MEDIEVAL MATCHING MARKETS by Lars Boerner and Daniel Quint

 As I'll explain below, here's a long-awaited paper that fully qualifies for that description:

MEDIEVAL MATCHING MARKETS by Lars Boerner and Daniel Quint, International Economic Review, First published: 15 July 2022 https://doi.org/10.1111/iere.12600

Abstract: We study the regulation of brokerage in wholesale markets in premodern Central Western Europe. Examining 1,804 sets of rules from 82 cities, we find brokerage was primarily a centralized matchmaking mechanism. Brokerage was more common in towns with larger populations, better access to sea ports and trade routes, and greater political autonomy. Brokers' fee structures varied systematically: price-based fees were more common for highly heterogeneous goods, quantity-based fees for more homogeneous goods. We show theoretically that this was broadly consistent with total surplus maximization, and that brokerage was more valuable in markets with unequal numbers of buyers and sellers.

...

"We investigate how societies organized markets and whether their market policies were well designed to have a positive effect on welfare. We look at one important type of regulated allocation process, the organization of intermediation in the form of brokerage, primarily in wholesale markets. Regulated intermediation first appeared in European towns during the second half of the 13th century. Early regulations can particularly be found in Italy and the Lower Countries (van Houtte, 1936; Rezzara, 1903). However, a comprehensive quantitative study on the origin, spread and development of the brokerage institution is missing so far. Origins of brokerage have been linked to the urbanization process of the 13th century (van Houtte, 1936); whether it can be related to preceding medieval Arabic merchant institutions or Roman law is an open debate (van Houtte, 1936; Lieber, 1968).

"We study 231 cities in Central and Western Europe, roughly in the area of the Holy Roman Empire north of the Alps, during the period from 1200 to 1700. This area and period are particularly appealing for empirical investigation because local municipalities were typically economically and politically autonomous. Thus, each city could implement its own types of regulations and allocation mechanisms, leading to potentially rich variation in detail.

"We identify cities with (and without) brokerage regulations and find in cities with regulations a dominant brokerage design with specific combinations of rules. The dominant design was a sort of centralized matchmaking mechanism: a few licensed brokers specializing in a particular product were given the exclusive right to offer a service pairing mainly foreign merchants with local buyers, and their behavior was strictly regulated. Brokers were not allowed to do any business on their own behalf and were restricted in what information they could disclose. The brokerage service was open to everybody, to the rich and poor, and to foreign and local merchants. Brokers received a predefined fee based on the transactions they generated—most commonly either a fixed fee per unit traded or a fixed fraction of the sales price."

**********

I normally don't blog about papers twice, i.e. if I've blogged about the working paper I don't blog again about the published paper.  But this one has changed since I first blogged about it, and it implicitly tells us something about the current (but still medieval) publication system in Economics, since that was more than a decade ago. Here's the earlier (2011) blog.

Wednesday, February 16, 2011

Medieval Matching Markets

Scott Cunningham's Mixtape Podcast Interview with Alvin Roth

 Here's Scott Cunningham's Mixtape Podcast Interview with Alvin Roth... "We discuss Gale and Shapley, Roth and Sotomayor, game theory and more"

You can listen to our conversation at the link above.  He drew me out about some things I hadn't thought of in a while, such as my varied relationships with Gale, Shapley and Bob Wilson, and how my ideas about matching markets developed over the course of my career (which started in Operations Research and then morphed into Economics...)

He also reveals the manner in which he was the perfect reader of my 1990 book Two-Sided Matching with Marilda Sotomayor. 

His site is multi-media, if you scroll down you'll find a video (the one below in on YouTube), and if you keep scrolling down you'll find an essay he wrote called "Paying it Forward..." which recounts more about what our book meant to him and some of our subsequent interactions over the years. And below that is his Transcript of [our] podcast interview, for those who prefer to read rather than listen or watch.

**********

I've had occasion to blog about Scott:

Friday, February 16, 2018

Sex work, Craigslist, and the law; podcast with Scott Cunningham

Here's a link to an interview with Scott Cunningham, whose work on sex work I've blogged about before. There's a surprising amount of discussion about causal inference and differences in differences. (I always suspected that econometrics was sexy, but this is the first time I’ve heard a podcast about that.)

Wednesday, August 30, 2017

The accidental experiment with legal prostitution in Rhode Island

A scholarly paper and an easy to read-or-listen-to NPR report recount the period in which indoor prostitution was legal in Rhode Island.

Tuesday, September 14, 2010

The Craigslist market for erotic/adult services

Matching prisoners to jails: peer effects are of first order importance

 Akhil Vohra points me to this very interesting matching problem, which is apparently quite far from a good solution:

RIKERS ISLAND: City Jails Scrap Last Remnants of Pricey Consultant Plan as Deaths Mount BY  REUVEN BLAU, May 18, The City

"In 2018, the city Department of Correction began using a new detainee classification process created at great expense by consulting group McKinsey & Company. 

"The de Blasio administration had paid the white-shoe firm $27.5 million to create the system that used an algorithm based on a host of factors — including age, possible gang affiliation, and any prior history in jail — to determine where to house people behind bars with the least risk for confrontation. 

"On Tuesday, jail Commissioner Louis Molina announced that the pricey system — widely criticized for failing to reduce violence — will be formally scrapped after just four years as part of the department’s court-mandated overhaul plan. 

...

"jail officials have long struggled where to place new detainees to reduce the likelihood of fights. Top jail supervisors have traditionally tried to avoid creating housing units based on gang affiliation, according to current and former jail insiders. 

"Units made up of just one gang tend to get along with each other but also have the ability to gang up on the officers in the area and are more likely to join forces to ignore basic orders, jail experts say. 

"Housing units mixed with people from at least two different gangs as well as some people who are totally unaffiliated are considered the golden standard, according to criminologists. 

"But other factors are also important such as a person’s prior criminal history, age, and possible previous record in jail. 

...

"“It’s a revolving door of stupidity and poor decisions,” one high-ranking jail official, who spoke on condition of anonymity, told THE CITY. 

“We changed from that system because it wasn’t working, now we are reverting back to it,” the jail insider said. 

...

"Jail officials said the result was part of the chaos that has led to a massive spike in the number of stabbings and slashings among detainees and assaults on staff."

(Mis)Matching airmen to bases

 The Military Times has this story, suggesting that the Air Force still has lots of room to improve it's internal matching procedures:

Air Force to end preferred basing for enlisted as it changes how airmen find new jobs.  By Rachel S. Cohen

"The Air Force this month will suspend its 4-year-old “base of preference” program for airmen who are on at least their second enlistment contract, saying it fails to send most applicants to the installations they want.

"Stopping the initiative at the end of May can also offer the service more flexibility to move airmen around as military staffing needs dictate.

The change affects “career airmen,” or those who have reenlisted at least once. They previously needed to spend at least four years in their jobs before leaving for a preferred base.

...

"That success rate would have been way higher if we actually had a resource where your standard airman could easily see what bases had openings/low manning, without having to have your [senior enlisted leader] ask your [career field manager] (who probably gets pinged about that at least once a week from people all over the world),” Reddit user JustHangInThere wrote April 28."

**********

Here's a post from 2020 about a NAS report that offered some suggestions on how to improve Air Force matching of personnel to bases and jobs:

Tuesday, December 1, 2020

The labor market that is the military: a report from the National Academies of Science, Engineering, and Medicine

HT: Cherie Shauvin

Süleyman Kerimov defends his dissertation

 Süleyman Kerimov defended his dissertation yesterday, in Stanford's MS&E department. He studies matching, and will teach at Rice next year.

His main advisors are both named Itai.

These are the papers he spoke about:

• Dynamic Matching: Characterizing and Achieving Constant Regret, with Itai Ashlagi and Itai Gurvich, . [pdf] [SSRN]


• Scrip Systems with Minimal Availability, with Itai Ashlagi, working paper.
  • Appeared as an extended abstract in the 15th Conference on Web and Internet Economics (WINE 2019).

Mazel tov and tebrikler, Suleyman.

Welcome to the club.

Two courses on matching and market design in Stanford's MS&E department, by Ashlagi and Saberi (first meeting is today)

Itai Ashlagi and  Amin Saberi are offering courses on matching theory and market design this quarter. First meetings are today, in the morning and in the afternoon:

MS&E 230: Market design for engineers

Itai Ashlagi  T-Thu 9:45-11:15

Course description:  Marketplaces use algorithms and sets of rules in order to allocate resources among self-interested agents, who often hold necessary information. This course will provide key principles in engineering a marketplace, to identify relation between the rules in the marketplace and market failures, and how to redesign them to achieve desirable outcomes.  The course provides foundations of resource allocation systems building on game theoretic analysis.  The course explores economic and algorithmic tools from matching, mechanism design, auction theory and information design. Cases of existing and future marketplaces will be discussed, including ride-sharing systems, school choice programs, online dating, online advertising and organ allocation.

Some applied questions include: How should we assign students to schools? How should we match doctors to residency programs? Shall we price roads and the impact of tolls? How should we allocate affordable housing and arrange waiting lists? How should we incentivize hospitals to collaborate on kidney exchanges? How should we allocate food to food banks? How should reduce organ discards?  How can we assist in migration?  Why is some marketplace decentralized (college admissions) and others are more controlled? How should platforms set incentives? What incentives and frictions arise in blockchains? 

 **********

MS&E 319: Matching Theory
Amin Saberi  T Th 01:30p-03:00p

The theory of matching with its roots in the work of mathematical giants like Euler and Kirchhoff has played a central and catalytic role in combinatorial optimization for decades. More recently, the growth of online marketplaces for allocating advertisements, rides, or other goods and services has led to new interest and progress in this area.  

The course starts with classic results characterizing matchings in bipartite and general graphs and explores connections with algebraic graph theory and discrete probability. Those results are complemented with models and algorithms developed for modern applications in market design, online advertising, and ride-sharing.

Topics include: 

Matching, determinant, and Pfaffian
Matching and polynomial identity testing
Isolating lemma and matrix inversion, matching in RNC

Combinatorial and polyhedral characterizations 
The assignment problem and its dual, primal-dual, and auction algorithms
Tutte’s theorem, Edmond’s LP, and the Blossom algorithm

The Gallai-Edmonds decomposition, Berge-Tutte formula, and applications in Nash bargaining

The stable marriage problem
Gale-Shapley theorem, incentive and fairness issues
LP characterization, counting stable matchings

Matching in dynamic environments
Online matching under various arrival models
Applications in ride-sharing and online advertising

 

Computation of matching  

Combinatorial vs continuous algorithms, near-linear time algorithms

Matchings in sub-linear time, streaming computational models

Sparsifiers and stochastic matching 

Counting matchings  
The Van der Waerden conjecture, Bregman-Minc’s inequality
Deterministic approximations, counting matchings in planar graphs
Markov chain Monte Carlo algorithms, sequential importance sampling
The Ising model, applications, and basic properties

***********

 

 

Course on Matching, in Barcelona, by Péter Biró and David Manlove, April 27-28

If you are a Ph.D. student interested in matching, here's a two day course in Barcelona, by experts in the field.

V SEIO Course on Game Theory   

The University of Barcelona, the BEAT Research Institute, and the Game Theory and Assignment Markets Research Group are delighted to host the V SEIO Course on Game Theory on April 27 and 28, 2022.

The course is targeted at PhD students and early career researchers working in areas related to game theory. Besides covering a very active research topic, it is also an opportunity to meet with other researchers working in similar areas. 

The two-day course will cover algorithmic and game theoretic aspects of matching markets. Participants are welcome to present their game theory related research during a poster session.

The course will be delivered by Péter Biró (Head of  the Mechanism Design Group at KRTK) and David Manlove (Professor of Algorithms and Complexity at the University of Glasgow).

Registration deadline:  April 1, 2022  Registration is free, please fill in the on-line form to register.

Day 1 (April 27)

 09:00-09:30 Registration and welcome session

09:30-10:20 Stable Marriage and Hospitals / Residents problems: classical results

10:20-10:50 Coffee break

10:50-11:40 Decentralised matching markets, path-to-stability results

11:50-12:40 Hospitals / Residents problem: extensions (ties, couples, lower quotas)

12:40-14:10 Lunch

14:10-15:00 Hungarian university admissions: matching with contracts, choice functions, cutoff

stability

15:00-15:30 Coffee break

15:30-16:20 Housing markets: exchange of indivisible goods

16:30-17:20 Respecting improvement property for housing markets

Day 2 (April 28)

 09:00-09:50 House Allocation problem: Pareto optimal, popular and profile-based optimal matchings

10:00-10:50 School choice and constrained welfare-maximizing solutions

10:50-11:50 Coffee break and poster session

11:50-12:40 Stable roommate problems

12:40-14:10 Lunch

14:10-15:00 Matching with payments, auctions

15:00-15:30 Coffee break

15:30-16:20 Kidney Exchange

16:30-17:20 Generalized matching games, international kidney exchange

Matching and market design in the January issue of Theoretical Economics

 The current issue has three papers on the market design of matching markets.

Theoretical Economics, Volume 17, Number 1 (January 2022): Table of Contents

Here are the market design articles that caught my eye:

Rank-optimal assignments in uniform markets  by Afshin Nikzad

"We prove that in a market where agents rank objects independently and uniformly at random, there exists an assignment of objects to agents with a constant average rank (i.e., an average rank independent of the market size). The proof builds on techniques from random graph theory and the FKG inequality (Fortuin et al. (1971)). When the agents’ rankings are their private information, no Dominant Strategy Incentive Compatible mechanism can implement the assignment with the smallest average rank; however, we show that there exists a Bayesian Incentive Compatible mechanism that does so. Together with the fact that the average rank under the Random Serial Dictatorship (RSD) mechanism grows infinitely large with the market size, our findings indicate that the average rank under RSD can take a heavy toll compared to the first-best, and highlight the possibility of using other assignment methods in scenarios where average rank is a relevant objective.

*******

Family ties: school assignment with siblings by Umut Dur, Thayer Morrill, and William Phan

"We introduce a generalization of the school choice problem motivated by the following observations: students are assigned to grades within schools, many students have siblings who are applying as well, and school districts commonly guarantee that siblings will attend the same school. This last condition disqualifies the standard approach of considering grades independently as it may separate siblings. We argue that the central criterion in school choice—elimination of justified envy—is now inadequate as it does not consider siblings. We propose a new solution concept, suitability, that addresses this concern, and we introduce a new family of strategy-proof mechanisms where each satisfies it. Using data from the Wake County magnet school assignment, we demonstrate the impact on families of our proposed mechanism versus the “naive” assignment where sibling constraints are not taken into account."

**********

Optimal organ allocation policy under blood-type barriers with the donor-priority rule by Jaehong Kim and Mengling Li

"Shortages in organs for transplantation have resulted in a renewed interest in designing incentive policies to promote organ supply. The donor-priority rule, which grants priority for transplantation based on deceased organ donor registration status, has proven to be effective in both theory and practice. This study investigates the implications of the donor-priority rule for optimal deceased organ allocation policy design under a general formulation of blood-type barriers. We find that for any blood typing and organ matching technology, reserving type X organs for only type X patients maximizes the aggregate donation rate under regular distributions, which also ensures equity in organ sharing. Moreover, this is the unique optimal allocation policy if and only if the directed compatibility graph that corresponds to a given organ matching technology is acyclic."

Matchup 2022: matching and market design in Vienna, August 25-2

 Here's the announcement and call for papers

Matchup 2022 

MATCH-UP 2022 is the 6th workshop in an interdisciplinary and international workshop series on matching under preferences . It will take place on 25-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)
• Vijay Vazirani (University of California, Irvine)