Course allocation at Stanford

 The Stanford Daily has the story:

New course enrollment system proposed to decrease stress and increase equity

"An alternative enrollment system called Griffin could allow students to submit proposed class schedules during a one-to-two week window.

"Griffin, presented by computer science professor Philip Levis at the Undergraduate Senate’s (UGS) Wednesday meeting, would replace the current system in which many students attempt to enroll in classes at the same time.

"The system’s proposed algorithm, called Approximate Competitive Equilibrium from Equal Incomes (A-CEEI), would process submitted courses and return final schedules within 48 hours. Levis says Griffin would prevent system crashes, increase equity and improve the experience of course enrollment.

“It’s strategy-proof, so there’s no way to game the system,” Levis said. “It reduces stress. There’s no time limit you have to submit in, no rush to submit in your time window. You just submit and you know it’s going to be fair.”

"Paul Nuyujukian M.D. ’12 Ph.D. ’14, assistant professor of bioengineering and a member of the Committee on Academic Computing and Information Systems (C-ACIS), said that 10% of Stanford courses are “oversubscribed,” meaning that enrollment is more than 95% of the classes’ capacity. According to Nuyujukian, a quarter of these classes have enrollments that exceed the enrollment cap.

...

"In contrast to the current scramble for courses, timing would have no impact on enrollment outcomes."

Further progress on course allocation, by Budish, Gao, Othman, Rubinstein and Zhang

 Here are some new developments in the course allocation mechanism used initially in Wharton and now elsewhere.  It turns out that strategy-proofness in the (very) large doesn't imply strategyproofness in samples of realistic size, but this seems to be fixable (and profitable manipulations were not easy to find). The paper concludes with some far ranging thoughts on the econ-cs interface.

Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)   by ERIC BUDISH, RUIQUAN GAO, ABRAHAM OTHMAN  AVIAD RUBINSTEIN, and QIANFAN ZHANG

Abstract: "Approximate Competitive Equilibrium from Equal Incomes (A-CEEI) is an equilibrium-based solution concept for fair division of discrete items to agents with combinatorial demands. In theory, it is known that in asymptotically large markets:

•For incentives, the A-CEEI mechanism is Envy-Free-but-for-Tie-Breaking (EF-TB), which implies that it is Strategyproof-in-the-Large (SP-L).

•From a computational perspective, computing the equilibrium solution is unfortunately a computationally intractable problem (in the worst-case, assuming PPAD≠FP).

We develop a new heuristic algorithm that outperforms the previous state-of-the-art by multiple orders of magnitude. This new, faster algorithm lets us perform experiments on real-world inputs for the first time. We discover that with real-world preferences, even in a realistic implementation that satisfies the EF-TB and SP-L properties, agents may have surprisingly simple and plausible deviations from truthful reporting of preferences. To this end, we propose a novel strengthening of EF-TB, which dramatically reduces the potential for strategic deviations from truthful reporting in our experiments. A (variant of ) our algorithm is now in production: on real course allocation problems it is much faster, has zero clearing error, and has stronger incentive properties than the prior state-of-the-art implementation"

Here's an intriguing passage:

"In Section 6 we use our manipulation-finding algorithm in combination with our fast A-CEEI finding algorithm to explore the plausibility of effective manipulations for students bidding in ACEEI. Originally, we had expected that since our mechanism satisfies the EF-TB and SP-L properties, it would at least be practically strategyproof — if even we don’t really understand the way our algorithm chooses among the many possible equilibria, how can a student with limited information learn to strategically bid in such a complex environment? 

"Indeed, in 2 out of 3 schools that we tested, our manipulation-finding algorithms finds very few or no statistically significant manipulations at all. However, when analyzing the 3rd school, we stumbled upon a simple and effective manipulation for (the first iteration of) our mechanism. We emphasize that although the manipulation is simple in hindsight, in over a year of working on this project we failed to predict it by analyzing the algorithm — the manipulation was discovered by the algorithm. 

"Inspired by this manipulation, we propose a natural strengthening of envy-free (discussed below), which we call contested-envy free. We encode the analogous contested EF-TB as a new constraint in our algorithm (specifically, the integer program for finding optimal budget perturbations). Fortunately, our algorithm is still very fast even with this more elaborate constraint. And, when we re-run our manipulation-finding experiments, we observe that contested EF-TB significantly reduces the potential for manipulations in practice."

...

"Conclusion:  In this work, we give a significantly faster algorithm for computing A-CEEI. Kamal Jain’s famous formulation “if your laptop cannot find it then neither can the market” [Papadimitriou 2007] was originally intended as a negative result, casting doubt on the practical implications of many famous economic concepts because of their worst-case computational complexity results. Even for course allocation, where a heuristic algorithm existed and worked in practice, Jain’s formulation seemed to still bind, as solving A-CEEI involved an intense day-long process with a fleet of high-powered cloud servers operating in parallel. The work detailed in this paper has significantly progressed what laptops can find: even the largest and most challenging real course allocation problems we have access to can now be solved in under an hour on a commodity laptop. 

"This significant practical improvement suggests that the relationship between prices and demand for the course allocation problem—and potentially other problems of economic interest with complex agent preferences and heterogeneous goods—may be much simpler than has been previously believed and may be far more tractable in practice than the worst-case theoretical bounds. Recalling Jain’s dictum, perhaps many more market equilibria can be found by laptops—or, perhaps, Walras’s original and seemingly naive description of how prices iterate in the real world may in fact typically produce approximate equilibria. 

"Our fast algorithm also opens the door for empirical research on A-CEEI, because we can now solve many instances and see how the solution changes for different inputs. We took it in one direction: empirically investigating the incentives properties of A-CEEI for the first time. For course allocation specifically, this faster algorithm opens up new avenues for improving student outcomes through experimentation. For instance, university administrators often want to subsidize some 6 group of students (e.g., second-year MBA students over first-year MBA students), but are unsure how large of a budget subsidy to grant those students to balance equity against their expectations. Being able to run more assignments with different subsidies can help to resolve this issue."

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

Earlier related posts:

Thursday, April 23, 2009

Course allocation, by Eric Budish

Sunday, October 4, 2009

Course allocation by Budish, updated

Thursday, May 30, 2013

Wharton's new Course Match for MBA students to choose their classes: market design in action

Monday, August 3, 2015

Course allocation at Wharton: looking under the hood

Tuesday, June 9, 2020

Cognomos--course allocation software by Eric Budish et al.

Course allocation at Eötvös Loránd University, by Attila Rusznák, Péter Biró, and Rita Fleiner)

At Eötvös Loránd University in Hungary, there's a course allocation system that gives rise to intense course exchange after its official conclusion (some of which may be planned in advance). Here's a description and analysis:

Seat transfers in the course allocation mechanism of Eötvös Loránd University  by A. Rusznák, P. Biró and R. Fleiner, 2021 IEEE 15th International Symposium on Applied Computational Intelligence and Informatics (SACI), 2021, pp. 503-508, doi: 10.1109/SACI51354.2021.9465548.

"Abstract: We initiate the study of the course allocation mechanism of the largest Hungarian university, ELTE, based on a real data provided for three semesters in 2018-2019. Besides introducing their priority based mechanism and the structure of their course registration data provided, we analyse a special issue coming from a students’ survey related to seat transfer. We identify the seat transfer actions in the last stage of the mechanism from the data that we describe in a transfer graph, and we analyse this network observing interesting patterns."

"In Hungary the course allocations are conducted at every major university by the same administrative system, called Neptun, and most universities use a simple first-come-first-served method. However, the largest university in Hungary, ELTE, uses a three-phase priority-based method [12]. In the first phase the students can submit their most preferred bundles, and the university admission may adjust the quotas of the courses based on these initial inputs. The second phase is the most important, where the students are ranked at each course based on a scoring system and lottery for breaking ties. They have a week to select their best bundles, but the mechanism is dynamic, the students can be unsure whether they will really get admission to a course. After finalising the assignment based on priorities and quotas, in the third phase of the mechanism a simple first-come-first-served method is used to allocate the remaining open slots. This final round also facilitates the informal seat transfers and swaps, a topic that we focus on in this paper. We conducted an online survey at ELTE sent to all registered students, and we received more than 3000 replies in total, so we could identify the main practices and issues for this priority based mechanism. We also received the complete course allocation record from their Neptun system for three recent semesters in 2018-2019. We will use this rich data to check the issues and strategies reported in the students’ survey, starting with the analysis of the seat transfers and swaps in the last stage of the mechanism.

...

"One of most critical comments was concerned with the rejection of the students even from their main courses that fits in their ideal curriculum. Some students mentioned that they could only get admission to some of their important courses by getting a favour from another student, who had higher priority at that course, so could take it in the second stage, and then transfer the course to them in the third stage. The transfer can be observed in the data as the withdrawal of a student and an almost immediate registration by another student. In this paper we initiate the study of this issue by studying the course allocation record of ELTE for the years of 2018-2019, that we describe in the next section."

Course allocation with minimum quotas, by Bichler, Hammerl, Waldherr, and Morrill

Here's a course allocation problem:, "Our specific task was to assign students to classes in the computer science and information systems department at the Technical University of Munich, a large European university. This department is currently the largest department at the university with more than 6,000 students."

How to Assign Scarce Resources Without Money:  Designing Information Systems that are Efficient, Truthful, and (Pretty) Fair
Martin Bichler, Alexander Hammerl, Stefan Waldherr,  Thayer Morrill
INFORMATION SYSTEMS RESEARCH, forthcoming.

"Matching with preferences has great potential to coordinate the efficient allocation of scarce resources in organizations when monetary transfers are not available, and thus can provide a powerful design principle for information systems. Unfortunately, it is well-known that it is impossible to combine all three properties of truthfulness, efficiency, and fairness (i.e. envy-freeness) in matching with preferences. Established mechanisms are either efficient or envy-free, and the efficiency loss in envy-free mechanisms is substantial. We focus on a widespread representative of a matching problem: course assignment where students have preferences for courses and organizers have priorities over students. An important feature in course assignment is that a course has both a maximum capacity and a minimum required quota. This is also a requirement in many other matching applications such as school choice, hospital-residents matching, or the assignment of workers to jobs. We introduce RESPCT, a mechanism that respects minimum quotas and is truthful, efficient, and has
low levels of envy. The reduction in envy is significant and is due to two remarkably effective heuristics. We follow a design science approach and provide analytical and experimental results based on field data from a large-scale course assignment application. These results have led to a policy change and the proposed assignment system is now being used to match hundreds of students every semester."

Cognomos--course allocation software by Eric Budish et al.

Cognomos is a site that will put school administrators in touch with the designers of  Wharton's Course Match, which I've blogged about here and here with links to the underlying academic papers.

You can hear Eric Budish talk about it in the videos below.

Unraveling of finance internships, and a black market for courses

Mallesh Pai points me to this story in Philadelphia Magazine, from the University of Pennsylvania:

Desperate for High-Paying Wall Street Jobs, Penn Students Try Buying Their Way Into the Right Classes--Out-of-control corporate recruiting — and a new black market  by DAVID MURRELL

"...students had been posting in Penn student group chats saying they’d be willing to pay their way into courses they hadn’t been able to get into. There was a simple workaround: These students would offer money to entice another student to drop the class, then swoop in through the online registration portal to take the newly free seat. The going rate looked to be about $50 to $60 for a class.
...
"Five years ago, sophomores like Current might not have been so desperate. Back then, finance companies hired for their all-important junior-year summer internships just a few months ahead of time. But recently, in an attempt to scoop up the best students before anyone else, companies have moved up the timeline. It’s now standard practice for finance firms to recruit sophomores like Current — who has only completed three semesters of college and hasn’t even declared a major — for those same junior-year summer internships a full 18 months in advance.
...
"As it happened, Current’s scheme to buy his way into Corporate Valuation didn’t quite work as planned. He was foiled by the course registration system. His co-conspirator did indeed drop the class, but a spot never opened up. (Current now thinks he failed to account for a wait-list.) But while he came up empty, other students say they know people who have succeeded.

“This is very common,” says junior Valentina Losada, another vet of the corporate recruiting wars. “It’s not even seen as something bad.”
...
"firms have realized they don’t need the university anymore; they can conduct phone and Skype interviews, then bring candidates to New York City for the final round. When deciding whether to recruit on campus at Penn or bypass the school and face no institutional regulation, guess which option the banks have chosen?

"Having granted themselves free rein, many companies are now acting like monopolistic bullies. They move the recruiting cycles ever earlier in a race to reach job applicants first. (Shout-out to the free market!) They don’t give students time to consider other internships, sometimes requiring job commitments just one or two days after the initial offer. Escudero says she’s had friends who received offers only to be told they had to give their answer on the spot — take it or leave it.
...
"The pressure also produces some peculiar unintended consequences, like the underground course-swap marketplace. Both Losada and Bomba say they have friends who have successfully bought or sold classes. "
************

Here's a related story in the Daily Pennsylvanian:

Ilyse Reisman | Penn students, please don’t sell your classes | Classes should not be treated like stocks

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

Students selling seats in popular courses

An Unusual Honor-Code Violation: Students Selling Seats in Popular Courses
(ungated access here: http://www.aacrao.org/resources/resources-detail-view/an-unusual-honor-code-violation--students-selling-seats-in-popular-courses )

"Course registration can be a stressful process on many college campuses, but students at Emory University have channeled their frustration into creative solutions—some more ethical than others.

The university’s stratified registration process gives priority access to students who have earned the most credits, such as seniors and juniors, and students who hold merit scholarships. So crafty students have devised a way to game the system: Those with earlier registration times enroll in courses to save spots for their friends, who arrange to pick up those class spots during the university’s "add-drop-swap" open-enrollment period, in the last weeks of a semester.

Some students even enroll in popular classes to try to sell their spots to others, according to some undergraduates.

"I’ve definitely heard it’s happened," said Priyanka Krishnamurthy, a senior. "I’ve seen Facebook statuses: ‘I’m willing to pay anybody who drops this class.’" In one case, students told a professor, the price for a spot in a prime course, such as a chemistry class or business-school prerequisite, was advertised at $100.

The practice is considered a violation of Emory’s honor code because it confers "unfair academic advantage" on those who have not earned it, according to Joanne Brzinski, senior associate dean for undergraduate education.

Payoffs for class slots have occurred, she said, and have been advertised via social-media posts. But Ms. Brzinski believes there have been only a handful of such cases.

"Quite frankly, that’s the sort of thing we’re more concerned about than anything," she said. "It would mean that students who can afford to pay for courses get an advantage."

Dan Fragiadakis (job market candidate)

Among the economists I'm engaged with on the job market this year is Dan Fragiadakis. You should think about hiring him.  His job market paper is


Improving Welfare in Assignment Problems: an Experimental Investigation (pdf) (with Peter Troyan). 
Abstract:
"Many institutions face the task of allocating objects (such as university dormitories) to individuals (students) without the use of monetary transfers.  A common solution to this problem is the Random Serial Dictatorship (RSD): agents are ordered randomly, and one at a time, each is assigned her favorite good according to her submitted preferences.  While RSD provides each agent with a dominant strategy of ranking objects truthfully, it may produce socially undesirable outcomes whereby it is possible to make some agents substantially better off at only a small cost to others.  In this paper, we study the prospect of raising welfare in assignment problems by incentivizing agents to report goods they value similarly as indifferent.  Specifically, we modify RSD by ordering agents earlier who report more indifference, a method similar to that used by the Stanford Graduate School of Business to assign MBA students to educational trips abroad.  While theory predicts weak welfare gains in equilibrium, this requires agents to calculate nontrivial best response strategies that deviate from simple truth-telling. In practice, it is unknown whether agents will be able to find these equilibria and, if they cannot, what the welfare implications of using such mechanisms will be. Motivated by these observations, we run a lab experiment where we find  that many agents follow natural heuristics that entail reporting indifferences between objects that are similar in value. Average earnings increase significantly compared to RSD, but the way in which indifference is rewarded can alter the variance in earnings.  This suggests that institutions that use RSD can benefit by rewarding indifference, but should choose how to do so carefully."

I wrote about another of Dan's papers with Pete Troyan yesterday, which is Pete's job market paper.

Course allocation at U. Toronto

U of T students trade cash for seats in full classes

University of Toronto students are buying and selling spots in fully-booked courses, turning registration into a bidding war.

“$100 to whomever drops (History of Modern Espionage),” posted Christopher Grossi on Facebook Tuesday. “I really need this course.”

The third-year history student said the 180-person course filled up before his designated registration time. After talking to the professor without success, he said offering money was his last chance to coax someone to trade with him.

The university’s course registration system prioritizes students based on need and creates a wait list for full classes, said Glenn Loney, assistant dean and faculty registrar of the university’s Faculty of Arts and Science.

But there is a narrow window of opportunity in the days after the wait list closes and before the final deadline for students to add or drop courses.

“Once the university drops the wait list, it’s mostly just every man for themselves,” Grossi said.

Some students have taken to Facebook to name a price for their coveted seat. In a post earlier this week, one student offered to sell her spots in two psychology courses for $50 apiece — or she’ll swap for a space in another psychology class.

Third-year computer science student “Lee,” who would not give his full name for fear of repercussions by the university, said he has sold his spot in courses twice, for $20 each. After arranging the deal through the university’s internal email system, Lee met the buyer in the library. On the university’s registration website, Lee dropped the course and the buyer applied for it immediately afterward, snagging Lee’s newly vacated spot.

Loney said students have been swapping spots in courses for years and there are no rules against it.

“There’s nothing that would put it in the same league as cheating, or an academic advantage,” he said, adding there is a limit to the number of courses a student can enrol in to prevent someone from stocking up on courses with the intent to sell.

Where arrangements were once made through friends, social media has created a much larger marketplace to connect desperate buyers with enterprising sellers.

“Most students find it reprehensible, and don’t participate in it at all,” Loney said. “There’s usually a torrent of abuse heaped on the people who are trying to sell.”

Wharton's new Course Match for MBA students to choose their classes: market design in action

Eric Budish, Judd Kessler and Abe Othman (all veterans of my market design class at Harvard) have been champions in helping Wharton adopt and implement the course scheduling technology that Eric developed for his dissertation.  Here is Wharton's introductory video (and the course match site is here: Course Match)

Here's the Faculty FAQ:

Course Match FAQ for Faculty

How it works

With Course Match students express their relative preferences across sections. Each student is endowed with a set of course tokens which are used to purchase seats.  Second year students are given more tokens than first year students, and first year students are given more tokens the more fixed core courses they waive. Students must submit their preferences by August 14^th. Then Course Match establishes a clearing price for each section such that (a) every student gets the best schedule they can afford and (b) course capacity constraints are satisfied.  A Drop/Add period begins shortly before classes start to allow students to make final adjustments to their schedule.

How many students will be enrolled in my class?

Each section has a target capacity, T, and is assigned in a room that has a legal limit of C seats, where clearly T <= C.  Typical values for T are 36, 60 and 78. Course Match attempts to assign no more than T students to a section.  However, the maximum number that will be enrolled is min{1.1 T, C}. We refer to this as the “10% rule” – if the room allows it, we will allow up to 10% more students above the target capacity in order to optimize the solution if necessary. For example, if T = 60, but the section is assigned to a room that legally can seat as many as 78 students, then Course Match may assign as many as 1.1 x 60 = 66 students.  However, if the section is assigned to a room that seats 60, then no more than 60 students will be enrolled. Note, the target capacity remains the target – Course Match attempts to adhere to the target. For example, if T = 60, Course Match views a solution with 60 students as preferred over a solution with 64 students (and 64 would be considered only if it is legal). But as Course Match utilizes a complex integer programming optimization engine, the quality of the overall solution improves considerably by allowing 10% leeway.

Does the 10% rule apply to every section?

Yes.

When will I be able to see my course enrollment?

On August 21 fall semester enrollments will be available to students and faculty.

How will drop/add work?

Students submit requests to drop or add sections. Students must always have a feasible section. Therefore, if they add a section that conflicts with a section they already own (e.g., the two sections are the same course or they meet at the same time), then the added section is retained and the other section is automatically dropped from the student’s schedule. First-come first-served waitlists are maintained for every section, and students are removed from the waitlist whenever a seat becomes available.  “Chain reactions” of drops and adds are possible. For example, if a student adds course A, which triggers that student to drop course B, then the first student on course B’s waitlist is automatically added to the course, which may cause that student to drop a course (because of a conflict). The series of adds and drops continues as far as it progresses to maximize the number of trades and to remove as many students from waitlists as possible.

When will the Add period start and end?

The add period starts shortly before classes begin and continues to September 9^th – the Add period ends once every section has met at least once. Students will not be able to add Q1 and semester courses after September 9^th.

Can students add my class after the add period ends?

Yes, but after the add deadline, students may add a course only with written permission from the instructor.

Will the course waitlist be maintained after the add period?

No. At the end of the add period, waitlists are deleted.

If my enrollment is greater than my target, T, will students be added to the class?

No. If, due to the 10% rule, enrollment slightly exceeds T, students will be added to the class only when enrollment falls below T.

The academic papers on which this work is based, so far, are here (from Eric Budish's site, so when there's no author listed, it's just Eric):

• The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes
  Published: Journal of Political Economy Vol. 119(6), Dec 2011, pp 1061-1103
  2010 Working Paper Version
  Data Appendix 
• The Multi-Unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard
  (with Estelle Cantillon)
  Published: American Economic Review Vol 102(5), Aug 2012, pp 2237-71.
  Data Appendix 
• Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation
  (with Abe Othman and Tuomas Sandholm)
  Published: Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010)

Bad market design by design at U of Central Florida...and Craigslist?

Course registration can be a pain, but at the University of Central Florida they apparently don't want anyone trying to make it easier: Student Is Punished for Creating Class-Registration Web

"A student at the University of Central Florida has been placed on academic probation for creating a Web site that tells students when a seat becomes available in a given class.

"Tim Arnold, a senior at Central Florida, built the U Could Finish site this year. The site became available in June, but, within days, was blocked from accessing the university site without notice. The Office of Student Conduct then told Mr. Arnold that he had violated university policy regarding technology use..."
*********

It's easier to see how Craigslist might have a legitimate interest in preventing entrepreneurs from developing superior front ends (recall eBay vs. Bidder's Edge): The SF Chronicle has the story.
3taps, PadMapper face Craigslist challenge

"Kidd's 3taps and a website that uses the data it collects, PadMapper, are the latest in a long line of Web developers to face legal action from Craigslist, the San Francisco company that has dominated the online classified advertising market for 17 years. Since 2008, at least three dozen similar services such as MapsKreig, Craiglook and CraigsFish have received cease-and-desist letters from Craigslist, most for building websites that presented Craigslist listings in ways they considered to be more dynamic, visually appealing and helpful.
...
"Craigslist has never added features such as mapping, videos and mobile apps, or any other tools that would improve user experiences. It still sorts items in chronological order, and doesn't allow nationwide searches of all its local websites at once. Its reluctance to update its Web services has opened the door for Kidd and other developers like him.

"Some of the developers shut down by Craigslist pulled data directly from its website, but 3taps uses a novel approach - searching Craigslist through Google, copying the data off Google, reordering it and then formatting it in a way other websites can easily display. PadMapper uses content generated by 3taps for its mapping services.

"Kidd noted that Craigslist chooses to allow price, location and description information from listings to appear on Google. As a result, he said, it shouldn't be allowed to stop other websites from displaying the same information in unique maps and tables. And the online classifieds leader certainly can't claim that data points as crucial to commerce as prices, locations and basic descriptions can be copyrighted.

"Legal experts say presenting the entirety of listings in the same format as Craigslist would be troublesome, but that's not what PadMapper is doing. And a 1991 case dealing with phone books suggests that the bare-bones data in listings is not subject to copyright law, these experts say.
...
"Craigslist and its lawyers did not respond to requests for comment. In the lawsuit, Craigslist says that "the originality, simplicity, and clarity" of its website "are fundamental to Craigslist's reputation and garner substantial and valuable goodwill with users." 

Matching in the August AER

Three papers in the August issue of the American Economic Review suggests that the study of matching is thriving.

(2) A Field Study on Matching with Network Externalities

Mariagiovanna Baccara, Ayşe İmrohoroğlu, Alistair J. Wilson and Leeat Yariv

We study the effects of network externalities within a protocol for matching faculty to offices in a new building. Using web and survey data on faculty's attributes and choices, we identify the different layers of the social network: institutional affiliation, coauthorships, and friendships. We quantify the effects of network externalities on choices and outcomes, disentangle the layers of the networks, and quantify their relative influence. Finally, we assess the protocol used from a welfare perspective. Our study suggests the importance and feasibility of accounting for network externalities in assignment problems and evaluates techniques that can be employed to this end. (JEL C78, C93, D62, D85, Z13)

Full-Text Access | Supplementary Materials

(10) Organ Allocation Policy and the Decision to Donate

Judd B. Kessler and Alvin E. Roth

Organ donations from deceased donors provide the majority of transplanted organs in the United States, and one deceased donor can save numerous lives by providing multiple organs. Nevertheless, most Americans are not registered organ donors despite the relative ease of becoming one. We study in the laboratory an experimental game modeled on the decision to register as an organ donor and investigate how changes in the management of organ waiting lists might impact donations. We find that an organ allocation policy giving priority on waiting lists to those who previously registered as donors has a significant positive impact on registration. (JEL C91, D64, I11)

Full-Text Access | Supplementary Materials

(17) The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard

Eric Budish and Estelle Cantillon

We use theory and field data to study the draft mechanism used to allocate courses at Harvard Business School. We show that the draft is manipulable in theory, manipulated in practice, and that these manipulations cause significant welfare loss. Nevertheless, we find that welfare is higher than under its widely studied strategyproof alternative. We identify a new link between fairness and welfare that explains why the draft performs well despite the costs of strategic behavior, and then design a new draft that reduces these costs. We draw several broader lessons for market design, regarding Pareto efficiency, fairness, and strategyproofness. (JEL D63, D82, I23)

Full-Text Access | Supplementary Materials

A market design collaboration between an economist and computer scientists

I've written earlier about the work on course allocation by Eric Budish. The new mechanism he proposed is by no means computationally trivial to implement, and together with Abe Othman, a computer science grad student at CMU (who took my Market Design class when he was an undergraduate at Harvard), he has been working on making this a practical too. A report of their work has now appeared:

Finding Approximate Competitive Equilibria: Efficient and Fair
Course Allocation, Abraham Othman, Eric Budish, and Tuomas Sandholm, Proc. of 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), van der Hoek, Kaminka, Lespérance, Luck and Sen (eds.), May, 10–14, 2010, Toronto, Canada, pp. 873-880


Abstract: In the course allocation problem, a university administrator seeks to efficiently and fairly allocate schedules of over-demanded courses to students with heterogeneous preferences. We investigate how to computationally implement a recently-proposed theoretical solution to this problem (Budish, 2009) which uses approximate competitive equilibria to balance notions of efficiency, fairness, and incentives. Despite the apparent similarity to the well-known combinatorial auction problem we show that no polynomial-size mixedinteger program (MIP) can solve our problem. Instead, we develop a two-level search process: at the master level, the center uses tabu search over the union of two distinct neighborhoods to suggest prices; at the agent level, we use MIPs to solve for student demands in parallel at the current prices. Our method scales near-optimally in the number of processors used and is able to solve realistic-size
problems fast enough to be usable in practice.

Course allocation at HBS

Some of the gems of the market design literature involve the careful analysis of existing institutions for allocating scarce goods, to understand the good and bad properties of those mechanisms, and the incentives they give to participants.

The latest example analyzes the way second year MBA courses at the Harvard Business School are assigned.

The Multi-unit Assignment Problem: Theory and Evidence from Course Allocation at Harvard by Eric Budish and Estelle Cantillon

Abstract: "This paper uses data consisting of agents. strategically reported preferences and their underlying true preferences to study strategic behavior in the course allocation mechanism used at Harvard Business School. We show that the mechanism is manipulable in theory, manipulated by students in practice, and that these manipulations cause meaningful welfare losses. However, we also find that ex-ante welfare is higher than under the Random Serial Dictatorship (RSD), which is the only known mechanism that is anonymous, strategyproof and ex-post efficient. We trace the poor ex-ante performance of RSD to a phenomenon, "callousness", specific to multi-unit assignment and unrelated to risk attitudes. We draw lessons for the design of multi-unit assignment mechanisms and for market design more broadly."

A related paper is Budish's proposal for an alternative mechanism: The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes.
(And here's my earlier post on an early version of that paper.)

Course allocation by Budish, updated

Eric Budish's updated (and still remarkable) paper is here:
The Combinatorial Assignment Problem: Approximate Competetive Equilibrium From Equal Incomes,
and Eric himself is now at Chicago's Booth School of Business.

Here is my previous post on the first version of that paper (which was Eric's jobmarket paper).

Course allocation, by Eric Budish

The problem of allocating courses to students is a famously hard problem of market design. The reasons include the fact that, in most applications, it isn't acceptable to sell the most desirable class places at higher prices to richer students. Also, students take multiple classes, and may have preferences for how their bundle is composed. So the problem is substantially more difficult than how to auction multiple goods, or how to allocate each student a single place, as comes up e.g. in assigning students to schools.

Eric Budish, who defended his Ph.D. dissertation at Harvard this week, has made a substantial, practical dent in the problem. His motivation comes from a detailed study, with Estelle Cantillon, of how classes are assigned to second year MBA students at the Harvard Business School, and how students approach this assignment problem strategically: Strategic Behavior in Multi-Unit Assignment Problems: Theory and Evidence from Course Allocations .

Largely motivated by what they learn about the good and not so good properties of the HBS mechanism, Eric then proposes a new mechanism: The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Eric's work, like market design in general, is eclectic. Among other things, he formulates new notions of what constitutes "fair" outcomes in cases hedged in by the impossibility results that abound when allocating indivisible goods.

Although allocating multiple indivisible items to each student makes the standard economic goals involving efficiency and incentives more difficult to achieve, it gives the designer somewhat more leeway to think about fairness, since although class places are indivisible, the package of classes that each student gets is not. And Eric’s investigations of existing course allocation institutions has convinced him that concerns about avoiding excessive ex-post unfairness are an important constraint on what kinds of mechanisms can be implemented in practice.

Eric's mechanism looks like it has legs, and may be ready for practical implementation in the not so distant future. Perhaps he'll get a chance to have more than the usual impact next year when he brings market design to U. Chicago's Booth School of Business (until recently Chicago GSB).

Welcome to the club, Eric.