Course allocation at Wharton: looking under the hood

A new paper by Budish, Cachon, Kessler and Othman gives more detail on how the course allocation tool at Wharton works at a computational level. It's a great example of practical market design as economic engineering.

Course Match: A Large-Scale Implementationof Approximate Competitive Equilibrium from Equal Incomesfor Combinatorial Allocation⇤
Eric Budish, Gerard P. Cachon, Judd Kessler, and Abraham Othman¶
July 23, 2015

Abstract:  Combinatorial allocation involves assigning bundles of items to agents when the use of money is not allowed. Course allocation is one common application of combinatorial allocation, in which the bundles are schedules of courses and the assignees are students. Existing mechanisms used in practice have been shown to have serious flaws, which lead to allocations that are inefficient, unfair, or both. A new mechanism proposed by Budish [2011] is attractive in theory, but has several features that limit its feasibility for practice: reporting complexity, computational complexity, and approximations that can lead to violations of capacity constraints. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that enhances the Budish [2011] mechanism in various ways to make it suitable for practice. To find allocations, Course Match performs a massive parallel heuristic search that solves billions of Mixed-Integer Programs to output an approximate competitive equilibrium in a fake-money economy for courses. Quantitative summary statistics for two semesters of full-scale use at a large business school (Wharton, which has about 1,700 students and up to 350 courses in each semester) demonstrate that Course Match is both fair and efficient, a finding reinforced by student surveys showing large gains in satisfaction and perceived fairness
*****************

In the conclusion, they write

"A critical feature for the success of Course Match is its “strategy-proof” property — a student’s best strategy is to report her true preferences no matter what preferences other students report or what capacities are assigned to each course. This greatly simplifies the student’s reporting task because the student need not form beliefs about how other students will “play” or what clearing prices might be for courses. In contrast, the Wharton Auction (as well as all other course-allocation mechanisms implemented in practice) was not strategy-proof. For example, if a student desires a course but believes that it will have a zero clearing price, then the student should rationally submit a low bid and save tokens to bid on other courses. However, the student may make a mistake and not receive the course she desires if the clearing price turns out to be higher than expected. This bidding mistake is not trivial and it could even lead a student with ample tokens to receive zero courses. Such errors do not happen with Course Match because Course Match effectively bids on behalf of students after all of the clearing prices have been revealed."
...
"while the Course Match mechanism has many desirable theoretical properties, if the preference language given to students is not sufficiently rich (i.e., it does not allow students to express critical preferences) or if students are not able to “speak” this language (i.e., they cannot use the language to correctly report their preferences), then Course Match may not yield desirable results. We are not able to provide direct evidence of the quality of the Course Match preference reporting language and user interface, but the high overall student satisfaction scores provide indirect evidence that the Course Match language is su!ciently rich and easy to use."
...
"We do not claim that the Course Match computational architecture is “optimal.” Indeed, an important question left for future research is whether there are better approaches to finding approximate market-clearing prices than that described here. We do show, however, that the Course Match computational architecture works at Wharton. To borrow a common analogy (e.g., Roth [2002]), ours is an exercise of engineering rather than physics."

NBER workshop on Market Design: call for papers (October 23-24, in Cambridge)

Mike Ostrovsky and Parag Pathak have announced the following call for papers:

From:  Michael Ostrovsky and Parag Pathak
To:  NBER Market Design Working Group

The National Bureau of Economic Research workshop on Market Design is
a forum to discuss new academic research related to the design of
market institutions, broadly defined. The next meeting will be held in
Cambridge, Massachusetts, on October 23-24, 2015.

We welcome new and interesting research, and are happy to see papers
from a variety of fields. Participants in the past meeting covered a
range of topics and methodological approaches.  Last year's program
can be viewed at:  http://conference.nber.org/confer/2014/MDs14/program.html

The conference does not publish proceedings or issue NBER working
papers - most of the presented papers are presumed to be published
later in journals.

There is no requirement to be an NBER-affiliated researcher to
participate.  Younger researchers are especially encouraged to submit
papers.

If you are interested in presenting a paper this year, please
upload a PDF version by August 1, 2015 to this link:
http://papers.nber.org/confsubmit/backend/cfp?id=MDf15

Preference will be given to papers for which at least a preliminary
draft is ready by the time of submission. Only authors of accepted
papers will be contacted.

For presenters and discussants in North America, the NBER will cover
the travel and hotel costs. For speakers from outside North America,
while the NBER will not be able to cover the airfare, it can provide
support for hotel accommodation.

There are a limited number of spaces available for graduate students
to attend the conference, though we cannot cover their costs. Please
email ppathak@mit.edu a short nominating paragraph.

Please forward this announcement to any potentially interested
scholars.  We look forward to hearing from you.

Scott Kominers on market design (and a conference in August)

INTERVIEWS

Prof. Scott Duke Kominers: ‘There are many new areas of market design worth exploring’

BY  EDITORIAL STAFFON JUNE 18, 2015

0

Prof. Scott Duke Kominers is a Junior Fellow at the Harvard Society of Fellows, a Research Scientist at the Harvard Program for Evolutionary Dynamics, and an Associate of the Harvard Center for Research on Computation and Society. He also will be a General Co-Chair at AMMA 2015, The Third Conference on Auctions, Market Mechanisms and Their Applications. We talked with him about the upcoming conference and about the most interesting potential areas in market design and the challenges this field will face in the near future.

AMMA 2015 will be held August 8-9, 2015 in Chicago. What will the main focus of the conference be?

AMMA focuses on the theory and practice of market design, at the intersection of economics, computer science, operations research, and applied math.

What are, in your opinion, interesting potential areas researchers in the field of market design should take into account?

Prof. Scott Duke Kominers, General Co-Chair at AMMA 2015

Market design has already proven useful in addressing real-life problems in settings like school choice, entry-level labor markets, kidney exchange, and auction design. Financial market design has flourished recently, as has the design of intellectual property markets. Personally, I am especially excited about “generalized matching,” which blends together ideas from matching and auction theory to show how markets with complex contract structure can be cleared using relatively simple mechanisms. I think there’s a lot of potential for generalized matching mechanisms to be useful in new real-world applications. In addition, there are many new areas of market design worth exploring: market designers are starting to think about the structure of healthcare marketplaces and adoption services. And of course, online platforms are everywhere. Furthermore, a popular press book on market design has just been published: http://www.hmhbooks.com/whogetswhat/index.html.

What challenges do you expect market design will face in the near future?

I think one of the greatest challenges going forward is about translation: we need to find good ways of teaching what we know about marketplace design to policymakers, entrepreneurs, and other practitioners. In some cases, there is work to be done in understanding how to simplify our mechanisms in ways that would make them more accessible to their users. Meanwhile, on the research side, market design has traditionally mixed powerful theory with empirical analysis, experiments, and computational methods. As we build more and more technical facility with our existing tools, and as we add new approaches to our toolkits, it is increasingly challenging – but also increasingly important – to make sure that we let real-world structure guide our methodological choices in applied work.

Two interviews by the Minneapolis Fed with two Stanford economists: me -- and Raj Chetty

The Minneapolis Fed publishes a magazine called The Region that features long interviews with economists, accompanied by nice photos. Their current issue, just out, has an interview with me.

You can read the whole thing here:

Interview with Alvin Roth

Stanford economist on matching theory, kidney markets and the importance of coffee

Douglas Clement | Editor, The Region  Published June 15, 2015   |  June 2015 issue

Here's the final exchange, about Pittsburgh and coffee:

"Region: One last question, if I might. Many of your major breakthroughs occurred when you were at Pittsburgh. What was it about the research environment there that was so conducive to Nobel-winning work?

Roth: Well, Pittsburgh was a lot of fun. The living was easy. I walked to work. I’d walk with my kids to school and drop them off and walk on into work. My colleagues and I spent a lot of time drinking coffee and talking about economics.

The mathematician Alfréd Rényi is said to have said that a mathematician is a machine for turning coffee into theorems. Maybe economists turn decaf into models.

There were lots of people to talk to at Pittsburgh. It was a fruitful time. And it was a very good department. I think a lot of what makes a department a good place to work is that when you’re onto something you’re excited about and you walk out the door of your office and tell one of your colleagues about it, he’s excited to hear about it, too. He says “That’s great. Let’s go have a cup of coffee, and you can tell me about it.” So there’s the positive reinforcement you get just from having people think, “Isn’t that great you’re excited about something. You’re thinking about something interesting.” It makes places fun to work.

Here at Stanford, I try to organize regular coffees—I did this at Harvard and I do it here—regular coffees with students interested in different things. We have a Tuesday morning coffee for experimental economics and a Thursday morning coffee for market design. I think that a lot of intellectual interaction arises out of social interaction. You have to be talking to people before you’re talking about work.

Region: Wonderful. It’s been a pleasure talking with you. Thank you."

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

The December 2014 issue had an interview with an even better-looking economist

You can read it here:

Interview with Raj Chetty

Harvard economist explores work on income mobility, education, taxation and labor supply

Douglas Clement | Editor, The Region Published December 10, 2014   |  December 2014 issue

Raj and I were colleagues at Harvard, and if my experience moving to Stanford is any guide, he is going to have a fine time here at Stanford.

Welcome, Raj.

Marketplace Innovation Workshop, Columbia U, June 10 2015

This looks like an exciting conference, I would go if I weren't already committed to be elsewhere...

"Marketplace Innovation" Workshop Conference Organized by Ramesh Johari, Costis Maglaras, and Gabriel Weintraub Wednesday, June 10, 2015 from 9:00 AM to 3:00 PM (EDT) New York, NY

Workshop on “Marketplace Innovation”

June 10, 2015

Columbia University

In conjunction with the 2015 Informs Revenue Management Conference

Organized by Ramesh Johari, Costis Maglaras, and Gabriel Weintraub

Markets are an ancient institution for matching the supply for a good or service with its demand. Physical markets were typically slow to evolve, with simple institutions governing trade, and trading partners generally facing a daunting challenge in finding the "right" partner.  The information technology revolution, however, has generated a sea of change in how markets function: now, markets are typically complex platforms, with a range of mechanisms involved in facilitating matches among participants.  Recent trends point to an unprecedented level of control over the design, implementation, and operation of markets: more than ever before, we are able to engineer the platforms governing transactions among market participants. As a consequence, market operators or platforms can control a host of variables such as pricing, liquidity, visibility, information revelation, terms of trade, and transaction fees. On its part, given these variables, market participants often face complex problems when optimizing their own decisions. In the supply side such decisions may include the assortment of products to offer and their price structure, while in the demand side they may include how much to bid for different goods and what feedback to offer about past purchasing experiences. The decisions made by the platform and the market participants interact, sometimes in intricate and subtle ways, to determine market outcomes.

In this workshop we seek work that improves our understanding of these markets, both from the perspective of the market operator and the market participants. With respect to the former we are particularly interested in work that derives useful insights on how to design these markets, taking into account their operational details and engineering and technological constraints. With respect to the market participants, we seek for work that introduces novel approaches to optimize their decisions and improves our understanding of their interactions within the market. We look for a mix of approaches including modeling, theoretical, and empirical, using a wide range of tools drawn from operations management, game theory, auctions and mechanism design, optimization stochastic modeling, revenue management, econometrics, or statistics.

The list of markets to be studied includes but it is not restricted to:

--Online marketplaces, such as eBay, Etsy, etc.

--Internet advertising, including sponsored search and display ad exchanges.

--Sharing economy markets, such as Uber/Lyft, AirBnb, etc.

--Online labor markets, such as Amazon mTurk, oDesk, Elance, etc.

--Procurement markets, such as technology-enabled government procurement

--Health care exchanges

--Financial exchanges

The talks are by invitation only and the list of confirmed speakers is:

• Gad Allon (Kellogg)
• Itai Ashlagi (MIT)
• Eric Budish (Chicago Booth)
• Gerard Cachon (Wharton)
• Anindya Ghose (NYU)
• Karan Girotra (INSEAD)
• Steve Graves (MIT)
• Nicole Immorlica (Microsoft)
• Hamid Nazerzadeh (USC)
• Christian Terwiesch (Wharton)
• Rakesh  Vohra (Penn)
• Assaf Zeevi (Columbia)

The program is here

The dangers of designing markets for illegal goods: Silk Road Founder Ross Ulbricht--'Dread Pirate Roberts'-- Sentenced to Life in Prison

Designing illegal markets (and shutting them down) is the story of the day, with stories about the late Silk Road, and it's successors.

The WSJ has the story on the life sentence of Dread Pirate Roberts:
Silk Road Founder Ross Ulbricht Sentenced to Life in Prison
Ulbricht was convicted of running underground online drug bazaar

"The sentence handed down by U.S. District Judge Katherine Forrest followed an emotional three-hour hearing. Judge Forrest said she spent more than 100 hours grappling with the appropriate sentence, calling the decision “very, very difficult.”

But ultimately, she gave Mr. Ulbricht the harshest sentence allowed under the law, saying Silk Road was “an assault on the public health of our communities” by making it easy for people around the world to buy illegal drugs."
...
"Prosecutors have described Silk Road as a criminal marketplace of unprecedented scope and sophistication. The site, which operated for two years, facilitated millions of dollars in transactions between buyers and sellers, who hawked illegal goods ranging from cocaine to fake driver’s licenses. At the heart of the criminal conspiracy, prosecutors say, was Mr. Ulbricht, who allegedly ran the site using the pseudonym Dread Pirate Roberts.
...
"In many ways, the Silk Road case was the first of its kind. The site operated on a hidden part of the Internet called the Tor network, and its only accepted form of payment was bitcoin, a digital currency whose movements are difficult to trace. The anonymity of the site’s transactions posed new challenges for law enforcement and forced them to depart from investigative techniques that would have been used in a traditional street drug case.

"Mr. Ulbricht is also not the typical drug kingpin. He was an Eagle Scout and grew up with a close-knit family in Austin, Texas, according to his lawyer. Mr. Ulbricht studied physics at the University of Texas in Dallas on a full scholarship and completed a master’s degree in material sciences at Pennsylvania State University."
*********

For some background, here's a long excerpt from an essay by Henry Farrell on the Silk Road and Dread Pirate Roberts
"The Silk Road might have started as a libertarian experiment, but it was doomed to end as a fiefdom run by pirate kings"
...
"This hidden internet is a product of debates among technology-obsessed libertarians in the 1990s. These radicals hoped to combine cryptography and the internet into a universal solvent that would corrupt the bonds of government tyranny. New currencies, based on recent cryptographic advances, would undermine traditional fiat money, seizing the cash nexus from the grasp of the state. ‘Mix networks’, where everyone’s identity was hidden by multiple layers of encryption, would allow people to talk and engage in economic exchange without the government being able to see.

Plans for cryptographic currencies led to the invention of Bitcoin, while mix networks culminated in Tor. The two technologies manifest different aspects of a common dream – the utopian aspiration to a world where one could talk and do business without worrying about state intervention – and indeed they grew up together. For a long time, the easiest way to spend Bitcoin was at Tor’s archipelago of obfuscated websites.

Like the pirate republics of the 18th century, this virtual underworld mingles liberty and vice. Law enforcement and copyright-protection groups such as the Digital Citizens’ Alliance in Washington, DC, prefer to emphasise the most sordid aspects of Tor’s hidden services – the sellers of drugs, weapons and child pornography. And yet the effort to create a hidden internet was driven by ideology as much as avarice. The network is used by dissidents as well as dope-peddlers. If you live under an authoritarian regime, Tor provides you with a ready-made technology for evading government controls on the internet. Even some of the seedier services trade on a certain idealism. Many libertarians believe that people should be able to buy and sell drugs without government interference, and hoped to build marketplaces to do just that, without violence and gang warfare.
...
"Would-be criminals on the hidden internet repeatedly complain that they have been ripped off. In the description of one commenter on the Hidden Wiki:
I have been scammed more than twice now by assholes who say they’re legit when I say I want to purchase stolen credit cards. I want to do tons of business but I DO NOT want to be scammed. I wish there were people who were honest crooks. If anyone could help me out that would be awesome! I just want to buy one at first so I know the seller is legit and honest.

This creates a market niche for intermediaries, who can become entrepreneurs of trust, supporting relationships between buyers and sellers who otherwise would not trust each other. Again, the Sicilian Mafia provides a precedent. Gambetta finds that they began as brokers of trust between buyers and sellers in a rural society without effective laws. The Mafia made money by guaranteeing transactions, threatening cheaters, and sometimes cultivating a general atmosphere of paranoia in order to ensure demand for their services. In other words, it built an informal order of its own, inimical to conventional laws, that gradually began to supplant the traditional state.

When Ulbricht began to grow hallucinogenic mushrooms and sell them on the internet in 2010, he didn’t see himself either as a Mafioso or a state builder. Instead, it appears that he was driven by enthusiasm for the libertarian thinker Murray Rothbard. On his LinkedIn profile, Ulbricht declared his intention to use ‘economic theory as a means to abolish the use of coercion and aggression amongst mankind’, and to build an ‘economic simulation’ that would let people see what it was like to live in a world without the ‘systemic use of force’. At the same time, he didn’t mind turning a profit from his activism – his diary entries show that he was pleased to make money from his first crop of mushrooms, and disappointed that he cashed out his first profits before the price of Bitcoin peaked.
...
"Seller pseudonyms provided a rough equivalent to a commercial brand. As the Stanford economist David Kreps has noted, a secured brand name with a reputation for honest dealing is an asset, and the desire to preserve its value can provide the incentive for future honesty. Not that the value is dependent on the actual owner of the name: a trademark can be sold or passed from one individual to another without losing its power. Ulbricht’s own pseudonym suggests that he had given this some thought: the original Dread Pirate Roberts appears in William Goldman’s comic fantasy novel The Princess Bride (1973), where it is a composite identity, passed from pirate captain to pirate captain as a kind of guarantee of fearsomeness.
...
"Yet market competition was no guarantee of honesty. Sometimes traders wanted to build up a reputation for honest dealing so that they could take the money and run. Several scammers gamed the system by establishing themselves as apparently reliable drug dealers, making a large number of near-simultaneous sales, demanding that customers finalise the payment before they got the goods and then disappearing with the money. Since the scammers used pseudonyms and Tor just like everyone else, outraged customers could do little except issue grandiose threats in the discussion forum.

They were vulnerable to more profound betrayals, too. Customers had to give mailing addresses to dealers if they wanted their drugs delivered. Under Silk Road’s rules, dealers were supposed to delete this information as soon as the transaction was finished. However, it was impossible for Ulbricht to enforce this rule unless (as happened once) a dealer admitted that he had kept the names and addresses. It’s likely that Silk Road dealers systematically broke these rules. At least one former Silk Road dealer, Michael Duch, who testified at Ulbricht’s trial, kept the names and addresses of all his clients in a handy spreadsheet.
"This created an obvious vulnerability – indeed, an existential threat to Ulbricht’s business. If any reasonably successful dealer leaked the contact details for users en masse, customers would flee and the site would collapse. And so, when a Silk Road user with the pseudonym FriendlyChemist threatened to do just that, Ulbricht did not invoke Silk Road’s internal rules or rely on impersonal market forces. Instead, he tried to use the final argument of kings: physical violence. He paid $150,000 to someone whom he believed to be a senior member of the Hells Angels to arrange for the murder of his blackmailer, later paying another $500,000 to have associates of FriendlyChemist murdered too.

It is unclear if anyone was, in fact, killed by anyone else. Indeed, it seems most likely that the whole affair was a scam in which FriendlyChemist and his purported assassin were associates (or possibly the same person). Still, it marked the final stage in an extraordinary transformation. Ulbricht began as an idealist, setting out to build a market free from what he described as the ‘thieving murderous mits’ of the state. He ended up paying muscle to protect the bureaucratic system that he had created."
*********

The Guardian writes about the dark markets that have sprung up to replace Silk Road: Dread Pirate Roberts may have been sentenced to life, but experts and customers say the tide has turned and internet markets for illicit products are here to stay

"James – not his real name – is the editor of DeepDotWeb, a news site which focuses on darknet marketplaces and maintains an up-to-date list of which markets are on or offline. He said the current market was “WAY bigger” than it was in the days of Silk Road.

James said it could safely be assumed that the daily turnover of the biggest markets – Agora is the largest, followed in no particular order by Nucleus, Middle Earth, Abrax, and Alphabay – is in the order of more than a million dollars a day. He estimated the market cap to be in the “hundreds of millions” of dollars.

“It’s becoming bigger all the time,” James told the Guardian. “Currently there are over 40 markets, forums, private vendor shops and a higher number of product listings than ever. I can personally testify that we, as a site who is reporting the darknet, see more and more traffic from people searching for specific markets – 1000% more than we saw last year.”

He said that since Ulbricht’s arrest people had “lost the sense of being invincible”, but also that they learned from Ulbricht’s mistakes and were now more careful, and more aware both of the dangers of law enforcement and of scams.

On Reddit, the subreddit for darknet markets has almost 60,000 subscribers. Among users asked by the Guardian what they thought the future holds, opinion was split. Many were worried by the instability of the new markets, suggesting that once vendors had enough repeat custom they would move to a direct-deal model rather than advertising on marketplaces that were vulnerable to exit scams. Vendors were the biggest losers in the Evolution exit scam.

But others thought the new order was here to stay.

“As long as our customers understand that purchasing their drugs through a DNM [Dark Net Market] is WAY safer than doing it in person, this will continue forever,” said one user, who gave his name as John. “People aren’t afraid of being robbed, beaten or killed because they went to their corner drug dealer when they can go to a DNM instead.”"

Multi-unit allocation workshop at Penn, Apr 26, 2015

WORKSHOP ON MULTIUNIT ALLOCATION , April 26

Time	Speaker/Presentation
9:30 - 10:30 am	Jacob Leshno (Columbia) A Supply and Demand Framework for Two-Sided Matching Markets
10:45 - 11:45 am	Bumin Yenmez (CMU Econ) Matching with Externalities
11:45 - 12:45 pm	Break
12:45 - 1:45 pm	Michael Richter (Yeshiva) Continuum Mechanism Design with Budget Constraints
2:00 - 3:00 pm	Gabriel Y. Weintraub (Columbia) Repeated Auctions with Budgets in Ad Exchanges: Approximations and Designs
3:15 - 4:15 pm	Haoxiang Zhu (MIT) Welfare and Optimal Trading Frequency in Dynamic Double Auctions
4:30 - 5:30 pm	Tadashi Hashimoto (Yeshiva) Equilibrium Selection and Inefficiency in Internet Advertising Auctions

Organizer: Mariann Ollar

Sponsored by the UPenn Market Design Working Group

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

A quick internet search for the marriage-market illustration yields this:

Caption	The Marriage Market in 1950. Anti-suffragette postcard.
Artist	English School (20th Century)
Artwork medium	colour lithograph
Copyright notice	© Look and Learn / Elgar Collection