Matching with complex constraints

At the NBER market design conference yesterday, Fuhito Kojima spoke about his paper with Yuchiro Kamada on matching with 'upper bound' constraints of the kind that occur in matching children to day care in Japan.

Here's the paper:

FAIR MATCHING UNDER CONSTRAINTS: THEORY AND
APPLICATIONS by YUICHIRO KAMADA AND FUHITO KOJIMA

Abstract. This paper studies a general model of matching with constraints. Observing that a stable matching typically does not exist, we focus on feasible, individually rational, and fair matchings. We characterize such matchings by fixed points of a certain function. Building on this result, we characterize the class of constraints on individual schools under which there exists a student-optimal fair matching (SOFM), the matching that is the most preferred by every student among those satisfying the three desirable properties. We study the numerical relevance of our theory using data on governmentorganized
daycare allocation.

Centralized Admissions for Engineering Colleges in India

Yesterday I had the opportunity to hear Yash Kanoria discuss the implementation and operation of a centralized college admissions system for engineering colleges in India.  It replaces a semi-centralized process that left some seats unfilled (when IIT and non-IIT seats were allocated to the same people).

There are some novel constraints that have to be satisfied, some of which can theoretically present intractable problems, but in practice they don't.

An appendix on history and background is a quick education in Indian education.

Below is a link to the paper, which seems to be a fine example of market design as economic engineering, which solved some important problems and has now operated successfully for several years. There are also problems (e.g. concerning vacancies in non-IITs) left to solve...:

Centralized Admissions for Engineering Colleges in India
by Surender Baswana, Partha Pratim Chakrabarti, Sharat Chandran, Yashodhan Kanoria, Utkarsh Patange

Abstract We designed and implemented a new joint seat allocation process for undergraduate admissions to over 500 programs spread across 80 technical universities in India, including the prestigious Indian Institutes of Technology (IITs). Our process is based on the well known Deferred Acceptance algorithm, but complex affirmative action seat reservations led us to make a number of algorithmic innovations, including (i) a carefully constructed heuristic for incorporating non-nested common quotas that span multiple programs, (ii) a method to utilize unfilled reserved seats with no modifications to the core software, and (iii) a robust approach to reduce variability in the number of reserved category candidates admitted, while retaining fairness. Our new seat allocation process went live in 2015, and based on its success, including significant and provable reduction in vacancies, it has remained in successful use since, with continuing improvements.

NBER Market Design Conference at Stanford, October 19-20

Here's the program and participant list:

Friday, October 19
8:30 am	Continental Breakfast
9:00 am	Olivier Terceiux, Top Trading Cycles in Prioritized Markets, a synthesis of:
	Yeon-Koo Che, Columbia University Olivier Tercieux, Paris School of Economics Top Trading Cycles in Prioritized Matching: An Irrelevance of Priorities in Large Markets
	Atila Abdulkadiroglu, Duke University and NBER Yeon-Koo Che, Columbia University Parag A. Pathak, Massachusetts Institute of Technology and NBER Alvin E. Roth, Stanford University and NBER Olivier Tercieux, Paris School of Economics Minimizing Justified Envy in School Choice: The Design of New Orleans’ OneApp
9:45 am	Surender Baswana, IIT Kanpur Partha Pratim Chakrabarti, IIT Kharagpur Sharat Chandran, IIT Bombay Yash Kanoria, Columbia University Utkarsh Patange, Columbia University Centralized Admissions for Engineering Colleges in India
10:30 am	Break
11:00 am	Onur Kesten, Carnegie Mellon University Selcuk Ozyurt, Sabanci University Efficient and Incentive Compatible Mediation: An Ordinal Market Design Approach
11:45 am	Dirk Bergemann, Yale University Benjamin A. Brooks, University of Chicago Stephen Morris, Princeton University Revenue Guarantee Equivalence
12:30 pm	Lunch Talk Michael Schwarz, Microsoft Market Design, Reputation Systems, UX, and the Cost of User Time
2:00 pm	Xiao Liu, Tsinghua University Zhixi Wan, Didi Chuxing Technology Co. Chenyu Yang, University of Rochester The Efficiency of A Dynamic Decentralized Two-Sided Matching Market
2:45 pm	Hongyao Ma, Harvard University Fei Fang, Carnegie Mellon University David Parkes, Harvard University Spatio-Temporal Pricing for Ridesharing Platforms
3:30 pm	Break
4:00 pm	Mohammad Akbarpour, Stanford University Farshad Fatemi, Sharif University of Technology Negar Matoorian, Stanford University A Monetary Market for Kidneys
4:45 pm	Alvin E. Roth, Stanford University and NBER Recent Developments in Kidney Exchange: Market Design in a Large World
5:30 pm	Adjourn
6:30 pm	Dinner Joya Restaurant 339 University Avenue Palo Alto, CA
Saturday, October 20
8:30 am	Continental Breakfast
9:00 am	Atila Abdulkadiroglu, Duke University and NBER Joshua Angrist, Massachusetts Institute of Technology and NBER Yusuke Narita, Yale University Parag A. Pathak, Massachusetts Institute of Technology and NBER Impact Evaluation in Matching Markets with General Tie-Breaking
9:45 am	Yuichiro Kamada, Harvard University Fuhito Kojima, Stanford University Fair Matching under Constraints: Theory and Applications (slides)
10:30 am	Break
11:00 am	Tamas Fleiner, Budapest University of Technology and Economics Ravi Jagadeesan, Harvard University Zsuzsanna Jankó, Corvinus University Alexander Teytelboym, University of Oxford Trading Networks with Frictions
11:45 am	Piotr Dworczak, Northwestern University Scott Duke Kominers, Harvard University Mohammad Akbarpour, Stanford University Redistribution through Markets
12:30 pm	Adjourn

Participant List

Atila Abdulkadiroglu Duke University and NBER

Nikhil Agarwal Massachusetts Institute of Technology and NBER

Mohammad Akbarpour Stanford University

Nick Arnosti Columbia University

Susan Athey Stanford University and NBER

Lawrence Ausubel University of Maryland

Moshe Babaioff Microsoft Research

Aaron L. Bodoh-Creed University of California at Berkeley

Eric Budish University of Chicago and NBER

Jeremy I. Bulow Stanford University and NBER

Gabriel Carroll Stanford University

Yeon-Koo Che Columbia University

Laura Doval California Institute of Technology

Jeremy T. Fox Rice University and NBER

Guillaume Haeringer Baruch College

Jonathan Hall Uber Technologies

John W. Hatfield University of Texas, Austin

Yinghua He Rice University

Ravi Jagadeesan Harvard University

Yuichiro Kamada Harvard University

Yash Kanoria Columbia University

Adam Kapor Princeton University and NBER

Jakub Kastl Princeton University and NBER

Onur Kesten Carnegie Mellon University

Fuhito Kojima Stanford University

Scott Duke Kominers Harvard University

Nicolas S. Lambert Stanford University

Shengwu Li Harvard University

Shuya Li Carnegie Mellon University

Hongyao Ma Harvard University

Mohammad Mahdian Google Research

Negar Matoorian Stanford University

Stephen Morris Princeton University

Yusuke Narita Yale University

Hamid Nazerzadeh University of Southern California

Afshin Nikzad Stanford University

Michael Ostrovsky Stanford University and NBER

Selcuk Ozyurt Sabanci University

Utkarsh Patange Columbia University

Parag A. Pathak Massachusetts Institute of Technology and NBER

Ali O. Polat Carnegie Mellon University

Daniel Quint University of Wisconsin

David H. Reiley Jr. Pandora Media, Inc

Alvin E. Roth Stanford University and NBER

Daniela Saban Stanford University

Michael Schwarz Microsoft

Ilya Segal Stanford University

Sven Seuken University of Zurich

Kane Sweeney eBay Research Labs

Steven Tadelis University of California at Berkeley and NBER

Olivier Tercieux Paris School of Economics

Zhixi Wan Didi Chuxing Technology Co.

Robert Wilson Stanford University

Xingye Wu Tsinghua University

Chenyu Yang University of Rochester

Haoxiang Zhu Massachusetts Institute of Technology and NBER

Cannabis in Canada--legal since yesterday

Here's yesterday's headline in The Globe and Mail:
Green dawn: The first day of cannabis legalization in Canada, from coast to coast

"From St. John’s to Vancouver, from Southern Ontario to the Far North, Canada’s nearly century-old prohibition on recreational cannabis lifted on Wednesday – and in Ottawa, the federal government is expected to announce how those convicted of possession under the old laws will be able to apply for pardons.

"Not everyone who wants to smoke up on the first day will be able to: Relatively few bricks-and-mortar stores are open, and in Ontario, the most populous province, online retail is the only option until physical stores get the go-ahead next year. Retailers are warning of shortages in the first few weeks, and at the production end, suppliers face formidable obstacles to catch up with expected demand."

Here's the story in the WSJ:
Cannabis is now legal in Canada, but pot companies expect a rocky start

"After nearly a century of prohibition, Canada became only the second country in the world, and the only member of the G-7, to legalize the drug for recreational use. Marijuana is officially legal in Canada.
...
"With little history or precedent for Canada to follow, the early months of recreational cannabis sales face ambitious timelines set by the governing party, a different set of laws in each of the country’s 10 provinces, and potential supply shortages as Canada’s federally licensed producers expand production.
...
"There are also a shortage of retail locations. In the country’s most populous province, Ontario, there are no bricks-and-mortar stores open on Wednesday, and won’t be for months. After a new government took power in a recent election, Ontario opted to sell pot online via a government-run store and allow private companies to open up stores on the ground. In Quebec, the second most populous province, there will only be a handful of stores around the two major cities, Montreal and Quebec City."

The FATE of technology at Penn, today

Fairness, Accountability, Transparency and Ethics are topics on which economics and computer science intersect each other , and some other fields as well:

The “FATE” of Technology: Fairness, Accountability, Transparency and Ethics

October 17, 2018 | Glandt Forum, Singh Center for Nanotechnology

Wednesday, October 17th, 2018

Glandt Forum, Singh Center for Nanotechnology

Celebrating Five Years of the Warren Center

Reception to follow

1:00 pm: Welcome and brief remarks

Michael Kearns, Professor and National Center Chair of Computer and Information Science

Rakesh Vohra, George A. Weiss and Lydia Bravo Weiss University Professor

1:10 pm: Aaron Roth, Class of 1940 Bicentennial Term Associate Professor of Computer and Information Science

“Ethical Algorithms”

1:30 pm: Annie Liang, Assistant Professor of Economics

“Predicting and Understanding Human Behaviors through Machine Learning”

1:50 pm: Sandra González-Bailón, Associate Professor at the Annenberg School for Communication

“Digital Technologies and Access to News”

2:15 pm: Break
2:30 pm: Panel with members of the Warren Center

Emily Falk, Associate Professor of Communication, Psychology, and Marketing

Junhyong Kim, Patricia M. Williams Term Professor of Biology

Konrad Kording, Penn Integrates Knowledge University Professor of Neuroscience and Bioengineering

3:00 pm: Keynote: Matthew Salganik, Professor of Sociology, Princeton University

“The Fragile Families Challenge”

4:00 pm: Michael Kearns, Professor and National Center Chair of Computer and Information Science

“The AlgoWatch Initiative”

4:30 pm: Concluding remarks by Vijay Kumar, Nemirovsky Family Dean

Kim Krawiec on Repugnant Markets

One of my favorite scholars on one of my favorite subjects:


"In this episode, Kimberly D. Krawiec, Kathrine Robinson Everett Professor of Law at Duke University School of Law, discusses her scholarship on "repugnant markets" or "taboo trades," including prostitution and kidneys. Listeners might be interested in her papers "If We Pay Football Players, Why Not Kidney Donors?"; "If We Allow Football Players and Boxers to Be Paid for Entertaining the Public, Why Don't We Allow Kidney Donors to Be Paid for Saving Lives?"; "Repugnance Management and Transactions in the Body"; "Organ Entrepreneurs"; and "Contract Development in a Matching Market: The Case of Kidney Exchange." Of course, there are many more excellent papers on her SSRN page."

On her own blog linking to the podcast, Kim also included links to the following papers:

Kidney Exchange to Overcome Financial Barriers to Kidney Transplantation(with Michael A. Rees et. Al)

Lessons from Law About Incomplete Commodification in the Egg Market

Quartz writes about Uber and other tech firms that hire economists

Here's the story, which prominently features Uber's Jonathan Hall:

Uber’s secret weapon is its team of economists
By Alison Griswold, October 14, 2018

"Uber is so fond of economists that it employs more than a dozen PhDs from top programs at its San Francisco headquarters. The group acts as an in-house think tank for Uber, gathering facts from quants and data scientists and synthesizing them to arm the lobbyists and policy folks who fight some of Uber’s biggest battles. Officially, this team is known as “Research and Economics.” Internally, it’s also been called Ubernomics.
...
"The Krueger paper was the launch pad Ubernomics needed. Over the next few years, the company landed unpaid collaborations with academics at top US universities, including MIT, NYU, and Yale. Hall started to receive dozens of requests a week from academics about working with Uber’s data. Earlier this year, Richard Thaler, winner of the 2017 Nobel Prize in economic sciences, approached Uber about a possible collaboration. Uber turned him down."