Sunday, October 21, 2018

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.

Saturday, October 20, 2018

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.


Friday, October 19, 2018

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

Thursday, October 18, 2018

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

Wednesday, October 17, 2018

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 VohraGeorge 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 LiangAssistant Professor of Economics
“Predicting and Understanding Human Behaviors through Machine Learning”
1:50 pm: Sandra González-BailónAssociate 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 SalganikProfessor 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

Tuesday, October 16, 2018

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:

Monday, October 15, 2018

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