Designing Markets with Complementarities

Lead Research Organisation: University of Oxford
Department Name: Economics

Abstract

Many real-world markets would function poorly if they did not have clear rules and coordinated transactions. The supply of generated electricity must match demand at all times otherwise there will be rolling blackouts. If local authorities do not centralise primary school admissions, many parents would be pressured into accepting places in schools where their children would not thrive. If the government gives away mobile spectrum licenses for free, then spectrum might not end up with telecoms companies that can provide the best service for the public.

Many markets can be drastically improved using insights from a branch of economics called "market design". Market designers use economic theory to develop market rules and create infrastructure that facilitates market transactions. Company shares, commodities, and even electricity are traded in organised exchanges. Centralized two-sided matching markets are used to match doctors to hospitals, children to schools and universities, one incompatible kidney donor-patient pair to another, and army cadets to branches of service. Auctions are used to find the most willing buyers for swathes of mobile spectrum, precious antiques, and search engine adverts.

Market designers have created many ways to design markets that superbly allocate similar (identical or substitutable) items. These include auctions for antiques and preference-based matching systems used by local authorities to allocate children to primary schools.

But one particular feature that drastically complicates the design of markets is complementarity. Things are complements when the value of them together is greater than the sum of their individual parts.

Coming back to an example above, suppose that the government wanted to sell mobile spectrum licenses. Telecoms companies value nearby licenses a great deal as it allows them to provide a better service for customers. Should the government bundle nearby licenses together or sell them separately? Now suppose that in order to sell spectrum licenses to telecoms companies the government first has to buy these spectrum licenses from hundreds of television stations. Should the government buy and sell these licenses at the same time? Finally, suppose that the government could also move some television stations to broadcast on other parts of the spectrum. Which stations should it move while avoiding broadcast interference? Answering all these questions involves tackling different types of complementarity.

There are other examples of real-world markets with complementarities. Property developers bidding in a land auction often want to buy adjacent plots of land. Boat captains often want to exchange some of their fishing quota for quota of other species. In order to avoid blackouts, the electricity grid operator has to make sure that certain fossil fuel and renewable generators are producing energy at the same time.

These examples make clear that in the presence of complementarities market design can be crucial to ensure the market works well. Coordination is required to ensure that as many of the complementary transactions take place as possible. However, when there are complementarities, simple, classic auctions and matching algorithms can fail dramatically. Therefore new theoretical tools are needed.

In this work, I develop new theoretical and practical tools - auctions, matching markets, and trading networks - to design markets with different types of complementarity. I also test one new auction in a series of laboratory experiments. This work has a number of important applications for the redesign of many existing markets and for the design of new ones, including markets for biodiversity conservation, peer-to-peer energy trading, auctions and exchanges of fishing quota, and matching systems for the allocation of resettled refugees.

Planned Impact

Every theoretical model developed in this research programme is inspired by, or is directly applicable to, designing real-world markets. Therefore, this research will have an impact on a number of beneficiaries outside academia. In the Pathways to Impact, I address specifically how I will engage and collaborate with these beneficiaries, disseminate my research, and establish opportunities for knowledge exchange.

Project 3 on matching markets with complementarities is directly related to an application of refugee resettlement. Several governments, including the United States, Canada, France, and the United Kingdom, resettle a total of around 100,000 refugees annually directly from refugee camps. These resettlement destinations lack tools to match refugee families to fitting local areas. In this research programme, I will not only develop better algorithms for existing resettlement models, but also link the matching system to financing of resettlement by governments and social impact investors. I am already working closely with one US resettlement agency to create such a matching system and I hope to apply these methods at other agencies and governments. This work also interests a number of foundations and non-governmental organisations, such as the Center for Global Development, Open Society Foundations, and Oxfam.

A key application of Project 1 (auctions with complements) in this research programme is environmental market design, in particular biodiversity conservation and investment in renewable natural resources. If a government agency (e.g. Defra or Natural England) or firms (e.g. Unilever) is interested in investing in biodiversity conservation or ecosystem service provision, they will often be interested in large swathes of land that can comprise many adjacent private properties. This is because natural ecosystems do not usually respect property boundaries but still must be protected as a whole. This work is also related to my involvement in a grant from The Nature Conservancy, an American environmental charity.

As more consumers begin to generate renewable electricity with solar panels and install batteries at home, there will be more intermediaries in the electricity market who are buying and selling electricity. In order to ease power line congestion and create a resilient energy system with a large fraction of renewables, electricity pricing will have to expand from a single market price to locational pricing and eventually to peer-to-peer pricing. I expect that both grid operators and peer-to-peer electricity start-ups will benefit of a new understanding of pricing in networks. These sorts of systems can be easily deployed on micro-grids which are becoming prevalent in rural areas of developing countries. I develop a new theory of networked market design to advance this application in Project 2.

Ideas developed in Project 1 and Project 2 will also benefit stakeholders and producer organisations in the fishing industry. Fishing quota is often allocated through auctions. Many fish species breed together so when fishermen target one fish species they inadvertently catch another species. Since fish discard is often prohibited, fishermen must buy quota for both types of fish making the quota for different species complementary. Another interesting application is an exchange of fishing quota after an auction. Boat captains buy an amount of quota for different species that is based on their projection of marine ecology. However, fishing can be highly unpredictable and once the net is cast and the catch is brought in, boat captains often need to trade quota of one species for another. Boat captains might want to sell some quota and buy quota for other species at the same time. I am already involved with designing fishing auctions in the Faroe Islands. I will explore complex quota auctions and quota exchanges with the Faroese, Scottish, and English fisheries managers based on the results of the research programme.

Publications

10 25 50
publication icon
Ahani N (2021) Placement Optimization in Refugee Resettlement in Operations Research

publication icon
Ahani N (2021) Placement Optimization in Refugee Resettlement in Operations Research

publication icon
Fleiner T (2019) Trading Networks With Frictions in Econometrica

publication icon
Fleiner T (2023) Complexity of stability in trading networks in International Journal of Game Theory

publication icon
Hadad J (2022) Improving refugee resettlement: insights from market design in Oxford Review of Economic Policy

publication icon
Jagadeesan R (2021) Matching and Money

publication icon
Kasy M (2023) Matching with semi-bandits in The Econometrics Journal

publication icon
Kasy M (2020) Adaptive targeted infectious disease testing in Oxford Review of Economic Policy

 
Description I have studied a new auction format called the Combinatorial Multi-Round Auction (CMRA) which turns out to have surprisingly good properties for selling complementary goods and has already been used in Danish and Norwegian spectrum auctions (Project 1).

COVID has meant that I needed to pivot from the original objectives from Project 1, however, that resulted in a very fruitful project on understanding how to maximise welfare in matching markets when the returns from individual matches were unknown.

I have analyzed the properties of market-clearing prices in trading networks in the presence of frictions: competitive equilibrium outcomes turn out to coincide with outcomes that satisfy a natural cooperative property (Project 2). I have applied this model to several designs of peer-to-peer energy markets.

I have deeply analyzed a model of matching with multidimensional constraints by considering near-feasible matchings (Project 3). I showed that small perturbation of capacity means that stable matchings can be admitted. I applied this model to refugee resettlement.

My work has led to a number of important applications. First, the model of matching with multidimensional constraints has been used to help match refugees to local areas in the United States. The first matching algorithm, called Annie, uses employment probabilities in order to match refugees to local areas. The second matching algorithm, called RUTH, uses only preferences to match refugees to private sponsors. Second, the trading networks models has been applied to the design of peer-to-peer electricity networks.
Exploitation Route There is a lot of scope for designing market mechanisms for settings in which goods are complementary and bidders experience income effects.
Sectors Communities and Social Services/Policy,Digital/Communication/Information Technologies (including Software),Energy,Environment

URL http://t8el.com/?page_id=992
 
Description The findings from this research programme have been used to design the first refugee-community matching system which was implemented by HIAS in the United States. This matching system, called Annie MOORE, is able to dramatically increase employment outcomes of resettled refugees and improve the quality of refugee-community matches. A second version of the software that allows for dynamic placement optimization is being launched in 2021. In 2022, together with HIAS we launched RUTH (Refugee Uniting Through HIAS), the first software ever to take refugee preferences over locations into account in the resettlement process (these ideas are based on my papers, especially "Matching Mechanisms for Refugee Resettlement" in this project). RUTH has been used to match several dozen Ukrainian refugees to sponsors. A draft of a research paper reporting on these results is due in May 2023. A combinatorial auction for ecosystem restoration which I described in one of the papers written for this awards is now being implemented jointly with RSPB. In March 2021, we piloted the first-ever combinatorial auction for the provision of bird habitat. Farmers are being paid to provide features of bird habitat on their land, but the auction selects the combination of bids that maximises ecological value across space (per pound of funding). The auctions have been completed and we have analysed the preliminary data. Landowners have been surveyed to check the followed through on their winning bids; the completion rate is exceptionally high.
First Year Of Impact 2022
Sector Agriculture, Food and Drink,Communities and Social Services/Policy,Digital/Communication/Information Technologies (including Software),Environment,Government, Democracy and Justice,Security and Diplomacy
Impact Types Societal,Economic,Policy & public services

 
Description Participation in the Dasgupta Review on the Economics of Biodiversity
Geographic Reach Multiple continents/international 
Policy Influence Type Contribution to a national consultation/review
URL https://www.gov.uk/government/collections/the-economics-of-biodiversity-the-dasgupta-review
 
Description (DUALMARKETS) - Duality in Market Design: Theory and Applications
Amount € 1,060,381 (EUR)
Funding ID 949699 
Organisation European Commission 
Sector Public
Country European Union (EU)
Start 07/2021 
End 06/2025
 
Description Leverhulme Centre for Nature Recovery
Amount £10,000,000 (GBP)
Organisation The Leverhulme Trust 
Sector Charity/Non Profit
Country United Kingdom
Start 05/2022 
End 05/2032
 
Description OPEN Leader
Amount £8,000 (GBP)
Organisation University of Oxford 
Sector Academic/University
Country United Kingdom
Start 11/2022 
End 07/2023
 
Description Annie MOORE 
Organisation HIAS Inc.
Country United States 
Sector Charity/Non Profit 
PI Contribution We deployed the first-ever refugee-community matching software, called Annie MOORE. The software suggests to HIAS staff where resettled refugees should be placed in order to maximize their employment chances. In January 2021, we developed a second version of Annie that suggests dynamic placements. Our matching algorithms are able to reach 98% of hindsight-optimal employment levels. I coordinated this project from the very start. The ideas in Annie MOORE are based on my model of matching with multidimensional constraints developed in this grant.
Collaborator Contribution HIAS implemented the algorithm. Andrew Trapp and Narges Ahani participated in the software and algorithm development for the first version of Annie. Paul Goelz and Ariel Procaccia also participated in the software and algorithm development for the second version of Annie.
Impact Papers: "Placement Optimization in Refugee Resettlement" (with Narges Ahani, Tommy Andersson, Alessandro Martinello, and Andrew C. Trapp) forthcoming at Operations Research. "Matching Mechanisms for Refugee Resettlement" (with David Delacrétaz and Scott Duke Kominers). "Dynamic Placement in Refugee Resettlement" (with Narges Ahani, Paul Goelz, Ariel Procaccia and Andrew C. Trapp).
Start Year 2018
 
Description RSPB Turtle Doves Auction 
Organisation Department For Environment, Food And Rural Affairs (DEFRA)
Country United Kingdom 
Sector Public 
PI Contribution We have suggested, designed and implemented the first-ever combinatorial auction for ecosystem restoration. In this auction, farmers compete to provide habitat for turtle doves. The key feature of this auction is the presence of ecological complementarities. Birds require food patches, scrub for nesting and water for drinking to be spatially co-located. The auction finds the most cost-effective combination of bids that deliver the most ecological value. The first auction was held in February-March 2021. Another auction will take place in June.
Collaborator Contribution Defra provided the funding for farmer payments. RSPB provided guidance on ecological complementarities and marketed the auction to the farmers. DotEcon and EnTrade provided the back-end and the front-end of the auction software respectively.
Impact The original idea was this kind of auction was described in my paper "Natural Capital Market Design". Except the auction itself, there have not been any outputs, but there are plans for research papers and reports.
Start Year 2019
 
Description RSPB Turtle Doves Auction 
Organisation DotEcon
Country United Kingdom 
Sector Private 
PI Contribution We have suggested, designed and implemented the first-ever combinatorial auction for ecosystem restoration. In this auction, farmers compete to provide habitat for turtle doves. The key feature of this auction is the presence of ecological complementarities. Birds require food patches, scrub for nesting and water for drinking to be spatially co-located. The auction finds the most cost-effective combination of bids that deliver the most ecological value. The first auction was held in February-March 2021. Another auction will take place in June.
Collaborator Contribution Defra provided the funding for farmer payments. RSPB provided guidance on ecological complementarities and marketed the auction to the farmers. DotEcon and EnTrade provided the back-end and the front-end of the auction software respectively.
Impact The original idea was this kind of auction was described in my paper "Natural Capital Market Design". Except the auction itself, there have not been any outputs, but there are plans for research papers and reports.
Start Year 2019
 
Description RSPB Turtle Doves Auction 
Organisation Entrade
Country United Kingdom 
Sector Private 
PI Contribution We have suggested, designed and implemented the first-ever combinatorial auction for ecosystem restoration. In this auction, farmers compete to provide habitat for turtle doves. The key feature of this auction is the presence of ecological complementarities. Birds require food patches, scrub for nesting and water for drinking to be spatially co-located. The auction finds the most cost-effective combination of bids that deliver the most ecological value. The first auction was held in February-March 2021. Another auction will take place in June.
Collaborator Contribution Defra provided the funding for farmer payments. RSPB provided guidance on ecological complementarities and marketed the auction to the farmers. DotEcon and EnTrade provided the back-end and the front-end of the auction software respectively.
Impact The original idea was this kind of auction was described in my paper "Natural Capital Market Design". Except the auction itself, there have not been any outputs, but there are plans for research papers and reports.
Start Year 2019
 
Description RSPB Turtle Doves Auction 
Organisation Royal Society for the Protection of Birds (RSPB)
Country United Kingdom 
Sector Charity/Non Profit 
PI Contribution We have suggested, designed and implemented the first-ever combinatorial auction for ecosystem restoration. In this auction, farmers compete to provide habitat for turtle doves. The key feature of this auction is the presence of ecological complementarities. Birds require food patches, scrub for nesting and water for drinking to be spatially co-located. The auction finds the most cost-effective combination of bids that deliver the most ecological value. The first auction was held in February-March 2021. Another auction will take place in June.
Collaborator Contribution Defra provided the funding for farmer payments. RSPB provided guidance on ecological complementarities and marketed the auction to the farmers. DotEcon and EnTrade provided the back-end and the front-end of the auction software respectively.
Impact The original idea was this kind of auction was described in my paper "Natural Capital Market Design". Except the auction itself, there have not been any outputs, but there are plans for research papers and reports.
Start Year 2019
 
Title Annie MOORE 
Description Annie MOORE uses machine learning and integer optimization to suggest placements of refugees across American communities in order to maximise employment outcomes. 
Type Of Technology Software 
Year Produced 2018 
Impact Used weekly by HIAS for refugee placements. Dramatic improvement in employment and needs-services matches. 
URL http://www.refugees.ai
 
Title RUTH: Refugees Uniting Through HIAS 
Description RUTH uses a matching algorithm to match (Ukrainian) refugees to American sponsors. The algorithm takes into account the preferences of refugees and the constraints of sponsors to find the best matches and given refugees a choice of whether to accept the first offer or to wait longer at a more preferred location. 
Type Of Technology Software 
Year Produced 2022 
Impact 50 Ukrainian refugees resettled with another 30 more on the waiting list. 
URL https://hias.org/news/how-innovative-algorithm-helps-ukrainian-refugees-find-new-homes/
 
Description A press release about RUTH (refugee matching software) 
Form Of Engagement Activity A press release, press conference or response to a media enquiry/interview
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact We built software (RUTH) that is matching Ukrainian refugees to American sponsors. RUTH has matched around 50 refugees with another 80 on the waiting list. This is the first time preferences over location have been used as the main input in the refugee resettlement process.
Year(s) Of Engagement Activity 2022
URL https://hias.org/news/how-innovative-algorithm-helps-ukrainian-refugees-find-new-homes/
 
Description Article in The Atlantic 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Article "HOW TECHNOLOGY COULD REVOLUTIONIZE REFUGEE RESETTLEMENT" about our refugee resettlement software Annie MOORE appeared in The Atlantic on 26 April 2019
Year(s) Of Engagement Activity 2019
URL https://www.theatlantic.com/international/archive/2019/04/how-technology-could-revolutionize-refugee...
 
Description Article in The Daily Telegraph 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Article titled "Post-Brexit farm subsidy will see landowners paid to protect the turtle dove" about our forthcoming auction appeared in the Daily Telegraph on 6 January 2021.
Year(s) Of Engagement Activity 2021
URL https://www.telegraph.co.uk/news/2021/01/06/post-brexit-farm-subsidy-plans-will-see-landowners-paid-...
 
Description Article in The Economist 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact An article in The Economist on 24 July 2021 "How an auction is helping Britain's turtle doves. Economists seek to save a romantic species" about our auction for turtle dove habitat.
Year(s) Of Engagement Activity 2021
URL https://www.economist.com/britain/2021/07/22/how-an-auction-is-helping-britains-turtle-doves
 
Description Article in The Financial Times 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Article titled "Just the job: how AI is helping build a better life for refugees" about Annie MOORE appeared in The Financial Times on 21 November 2018.
Year(s) Of Engagement Activity 2018
URL https://www.ft.com/content/9332fffc-ec57-11e8-89c8-d36339d835c0
 
Description Article in the Financial Times 
Form Of Engagement Activity A magazine, newsletter or online publication
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Public/other audiences
Results and Impact Article in the Financial Times titled "Economists develop UK subsidy auction to save endangered turtle dove" on 23 July 2021 about our auction for turtle dove habitat.
Year(s) Of Engagement Activity 2021
URL https://www.ft.com/content/6bfbd5e2-10f9-4400-b4e1-258225e3ac0f
 
Description Co-organising the Matching Under Preferences (MATCH-UP) Workshop 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Professional Practitioners
Results and Impact MATCH-UP 2022 is the 6th workshop in an interdisciplinary and international workshop series on matching under preferences .

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.

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)
Year(s) Of Engagement Activity 2022
URL https://ac.tuwien.ac.at/matchup2022/
 
Description Expert witness at an appeal against the design of the Irish 5G auction 
Form Of Engagement Activity A formal working group, expert panel or dialogue
Part Of Official Scheme? No
Geographic Reach National
Primary Audience Industry/Business
Results and Impact I was asked to be an expert witness by the Irish Communications Regulation Commission at an appeal against the design of their auction to allocate radio spectrum. The reason for my being invited was my expertise in auctions for complements (which is a topic analyzed in the grant). The court case will be held in June 2021. The background work I did for the court case appears to be leading to a research paper on a new auction format.
Year(s) Of Engagement Activity 2021
URL https://www.comreg.ie/publication/appeal-by-three-in-relation-to-multi-band-spectrum-award-the-700-m...
 
Description Frontiers of Market Design Workshop at ACM EC'22, EC'21, EC'19, and EC'18 conferences. 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Other audiences
Results and Impact I have co-organized four Frontiers of Market Design Workshops at four consecutive ACM EC conferences.

This workshop on market design is organized by the INFORMS Section on Auctions and Market Design in conjunction with the ACM EC 2021 conference. The workshop brings together researchers and also practitioners designing markets, developing algorithms and theory for multi-object markets with or without money.
Year(s) Of Engagement Activity 2018,2019,2021,2022
URL https://connect.informs.org/auctionsandmarketdesign/events/recentcommunityeventsdashboard/new-item25...
 
Description NBER Decentralisation Conference "Mechanism Design for Vulnerable Populations" 
Form Of Engagement Activity Participation in an activity, workshop or similar
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Postgraduate students
Results and Impact I co-organized the 50th NBER Decentralisation Conference "Mechanism Design for Vulnerable Populations" (main website: https://sites.google.com/view/caasi-pitt/decentralization-2021/conference-program). One of my contribution was putting together half a day on "Migration and Refugees" which included a keynote, a panel, and a problem-solving session (details: https://drive.google.com/file/d/1aLNv7Sq5weAeg-7tZ0pVFpX5linMSiEC/view and my video blurb: https://www.youtube.com/watch?v=EAT62YXYLcI). The conference was attended by many practitioners from NGOs working with refugees and other vulnerable migrant populations.
Year(s) Of Engagement Activity 2021
URL https://sites.google.com/view/caasi-pitt/decentralization-2021/conference-program
 
Description What Economists Really Do: Economics of Biodiversity 
Form Of Engagement Activity A talk or presentation
Part Of Official Scheme? No
Geographic Reach International
Primary Audience Undergraduate students
Results and Impact I gave a talk at the Department of Economics series "What Economists Really Do" called "The Economics of Biodiversity and Markets for Biodiversity" that covered the RSPB auction for turtle dove habitat and fishing quota auctions.
Year(s) Of Engagement Activity 2021
URL https://www.youtube.com/watch?v=VJojdYeMkkc