Is the set of stable matchings generically small? Ashlagi, Kanoria and Leshno on large random marriage markets

Suppose you have a matching market with two kinds of players, say each player of one kind owns a single left shoe and the other kind each owns a single right shoe, and they can earn $1 by assembling a pair of shoes.  Then if there are more left shoe owners than right shoe owners, the core of the game will give $1 to every right shoe owner and $0 to every left shoe owner. (Here's an old  experiment on such a game.)

The situation is very much less clear if the game isn't played for money, and if the players are not all identical. But in a surprising result, Itai Ashlagi, Yash Kanoria and Jacob Leshno have shown that in a two sided marriage model (in which each man has preferences over all the women and each women over all the men, so agents aren't at all identical), then even a slight imbalance in the sizes of the two sides of the market makes the set of stable matchings very small: Unbalanced random matching markets, by Itai Ashlagi, Yashodhan Kanoria, and Jacob D. Leshno.

"Abstract: We analyze large random matching markets with unequal numbers of men and women. We fi nd that being on the short side of the market confers a large advantage. For each agent, assign

a rank of 1 to the agent's most preferred partner, a rank of 2 to the next most preferred partner

and so forth. If there are n men and n + 1 women then, we show that with high probability, in

any stable matching, the men's average rank of their wives is no more than 3 logn, whereas the

women's average rank of their husbands is at least n/(3 logn). If there are n men and (1 +lamda )n

women for lamda> 0 then, with high probability, in any stable matching the men's average rank of

wives is O(1), whereas the women's average rank of husbands is Omega(n). Simulations show that

our results hold even for small markets."

We already knew that large matching markets have small sets of stable matchings when preference lists are short. This result suggests that small sets of stable matchings may arise for quite different reasons.

Who Gets What: video of a lecture I gave at Stanford GSB

One hour of market design (45 minutes of lecture, 15 of very good questions and my attempts to answer them...)

"Published on May 13, 2013

Stanford University Professor and 2012 Nobel Laureate Al Roth speaks on his prize-winning research and ground-breaking successes with exchange markets and his life-saving favorite, kidney exchanges.

Dr. Roth was the keynote speaker for the GSB Spring Reunions on May 3, 2013. He was introduced by Dean Garth Saloner.

Roth is the Craig and Susan McCaw Professor of Economics at Stanford University.

Related Links
http://alumni.gsb.stanford.edu/events...

Selected Works from Dr. Roth

http://www.stanford.edu/~alroth/

• Category

  Education

• License

  Standard YouTube License"

Matching in Paris: conference this week

Workshop on “Advances in Mechanism Design”, June 11–12, 2013
Paris School of Economics, “Grande Salle”, 48 Boulevard Jourdan, 75014 Paris, France

Here's the program:
Tuesday, June 11
09:00 - 10:00: Fuhito Kojima (Stanford):
“Efficient Matching under Distributional Constraints: Theory and Applications”
10:00 - 11:00: Dorothea Kubler (WZB Berlin):
“Implementing Quotas in University Admissions: Experimental Evidence”
Coffee Break
11:30 - 12:30: Yinghua He (TSE):
“Competitive Equilibrium from Equal Incomes for Two-Sided Matching”
Lunch
14:00 - 15:00: Alfred Galichon (Sciences Po):
“The Roomate Problem Is More Stable Than You Think”
15:00 - 16:00: Estelle Cantillon (ULB):
“Endogenous Preferences and the Role of the Mechanism in School Choice”
Coffee Break
16:30 - 17:30: Eduardo Azevedo (U Penn):
“A Supply and Demand Framework for Two-Sided Matching Markets”

Wednesday, June 12
09:00 - 10:00: Jinwoo Kim (Seoul National U):
“Stable Matching in Large Economies”
10:00 - 11:00: Francis Bloch (Polytechnique):
“Dynamic Allocation of Objects to Queuing Agents”
Coffee Break
11:30 - 12:30: Sonia Jaffe (Harvard):
“Taxation in Matching Markets”
Lunch
14:00 - 15:00: Tadashi Hashimoto (Stanford):
“The Generalized Random Priority Mechanism with Budgets”
15:00 - 16:00: Clayton Featherstone (U Penn):
“A Rank-based Refinement of Ordinal Efficiency and a New (but familiar) Class of Ordinal
Assignment Mechanisms”
Coffee Break
16:30 - 17:30: Muriel Niederle (Stanford):
“Propose with a Rose? Signaling in Internet Dating Markets”

Matching news from Peter Biro: a conference volume, a summer school at the end of the month and a workshop in October

Peter Biro writes:

The proceedings of the Japanese-Hungarian Symposium is now available online:

http://www.cs.bme.hu/~jh2013/nagy.pdf

with papers on stable matchings and flows from pages: 55, 65, 133, 225, 243, 301, 347

Our summer school starts in 2 weeks time with 83 participants (+speakers)

registered: http://econ.core.hu/english/res/MatchingSchool.html

The COST Action will have a workshop on 16-18 October in Barcelona, organised locally by Flip. The topics will be matchings and information merging (WGs 3 and 4 of the action: http://www.illc.uva.nl/COST-IC1205/).

You would be very welcome there as well if you have time.

Operations Research Conference in Memory of Professor Uriel G. Rothblum (June 11, 2013)

I am in Israel to participate in a conference honoring my old friend Uri Rothblum. The instructions to the presenters were to try to present a talk that Uri would have liked to hear...

Technion honorary doctorate ceremony

The Technion will broadcast its honorary doctorate ceremony here: Honorary Doctors Ceremony - June 10, 2013 – 8:00 pm, 1:00 pm EDT, USA

I don't imagine that it will be gripping to watch, but I will be there. I served for a number of years on the Technion's Board of Governors, and I am in Israel for the memorial conference of my old friend Uri Rothblum.

Honorary 7th dan black belt in JKA Shotokan karate, presented by Sensei Masataka Mori

When I was an undergraduate at Columbia University, from the Fall of 1968 through the summer of 1971, I spent a lot of time practicing Shotokan karate, which was very satisfying and which taught me that I could work harder than I had thought. Our instructor was the now legendary Sensei Masataka Mori, who came to New York in 1968, where he founded the NY Dojo, and also taught at Columbia.

It turns out that Nobel prizes are followed by other recognitions, and the most unexpected of those that I have received is that the Japan Karate Association in Tokyo has made me an honorary 7^th-degree black belt, something that, given my athletic abilities, is even more unimaginable than being a Nobel laureate.

Sensei Mori came out to San Francisco earlier this year to make the presentation:  in the photo below, he and I are holding the certificate.

Next to me is my wife Emilie, and next to Sensei Mori is T.J. Stiles, the Pulitzer Prize/National Book Award winning biographer of Cornelius Vanderbilt (and Jesse James, too, but in a different book, it turns out that they weren't the same person:).  T.J. is a 5th dan black belt and the chief instructor of the JKA San Francisco dojo.

Behind the camera was Dr. Jacob Levitt, a 4th dan black belt who made the trip with Sensei Mori from New York, where he teaches and practices dermatology at Mt. Sinai Hospital.

Emilie and I felt that we were in the company of three unusually accomplished people.

Here is what I gather is an approximate English translation of the Japanese certificate:

Information about live kidney donors, for those who need them

The Living Kidney Donors Network is organizing two webinars:

LKDN is Offering two Kidney Kampaign Webinars:

Click here to register for June 10, 2013, 7:00 PM - 8:00 PM CDT or

Click here to register for June 18, 2013, 7:00 - 8:00 PM CDT.

To learn more about the LKDN Webinars, Click Here

NEW link and information: Developing Your Kidney Kampaign. Click HERE

The Living Kidney Donors Network is a not-for-profit organization whose primary Mission is to educate people who need a kidney transplant about the living donation process and to prepare them to effectively communicate their need to family members and friends.

Notes on teachers and students from the rabbinical literature

As I get older I appreciate more the bonds between teachers and students. These aren't as recognized in modern literature as are other kinds of bonds, between parents and children, husbands and wives, brothers and sisters... One exception is in the rabbinical literature.

Here's a brief collection of quotes, I'd be glad to know of more.

Rabbi Yitzchok Etshalom Talmud Torah 5:13
13. The students add to the teacher's wisdom and expand his understanding. The sages said: I have learned much wisdom from my teacher, more from my colleagues and the most from my students (BT Ta'anit 7a); and just as a small piece of wood ignites a large one, similarly a small student sharpens the teacher['s mind] until he extracts from him, through his questions, wondrous wisdom.

http://www.torah.org/learning/rambam/talmudtorah/tt5.13.html

alternate translation, from Maimonides, Laws of Torah Study, http://www.panix.com/~jjbaker/MadaTT.html chapt 5:
13) Students add to the wisdom of their Rabbi, and open his heart. The Sages said that they learnt more from their Rabbis than from their friends, but learnt even more from their students. Just as a small candle can light a big one so a student sharpens his Rabbi's wits, by extracting from him his wisdom by means of questions.

Pirkei avot: Chapter 1.1
The Men of the Great Assembly had three sayings:
Be deliberate in judging;
Educate many students;
Make a fence around the Torah.

Pirkei avot: (Chapte 1, 6) Joshua ben Perachyah and Nittai the Arbelite received the Torah from them. Joshua ben Perachyah said: Provide [make] for yourself a teacher and get [acquire] yourself a friend; and judge every man towards merit. http://www.shechem.org/torah/avot.html

Some commentaries have trouble with the first two clauses, and I've seen "get a friend" translated as "find someone to study with." But another way to understand it  (maybe, I'm no Talmud scholar) is that teachers and friends (and students and friends) can intersect and be the same folks...

5.12 12. There are four types of student. One who is quick to understand and quick to forget--his flaw cancels his virtue. One who is slow to understand and slow to forget--his virtue cancels his flaw. One who is quick to understand and slow to forget--his is a good portion. One who is slow to understand and quick to forget--his is a bad portion.

Sanhedren p105, side B: no man envies the accomplishments of his children or his students


"דאמר רב יוסי בר חוני בכל אדם מתקנא חוץ מבנו ותלמידו" "Reb Yossi bar Honi said 'of everyone a man is envious except his son and his student'."
( סנהדרין • קה ב )

*******
update: I should note that another literature/tradition in which bonds between teachers and students are noted is in martial arts .

Update: Charlie Nathanson reminds me of  Perkei Avot chapter 4, verse 12 (https://www.sefaria.org/Pirkei_Avot.4.12

רַבִּי אֶלְעָזָר בֶּן שַׁמּוּעַ אוֹמֵר, יְהִי כְבוֹד תַּלְמִידְךָ חָבִיב עָלֶיךָ כְּשֶׁלְּךָ, וּכְבוֹד חֲבֵרְךָ כְּמוֹרָא רַבְּךָ, וּמוֹרָא רַבְּךָ כְּמוֹרָא שָׁמָיִם:

"Rabbi Elazar ben Shammua said: let the honor of your student be as dear to you as your own, and the honor of your colleague as the reverence for your teacher, and the reverence for your teacher as the reverence of heaven."

Kidney exchange between Jewish and Arab families in Israel

Kidney exchange erases boundaries, here's the story from Haaretz (in Hebrew, with Google translate:)

דו קיום: ערבייה תרמה כליה ליהודי; בנו תרם לערבי

Coexistence: Jews receive Arab donated kidney; son contributed to an Arab

Cross-transplant saved lives - and put hearts: the wife of Muhammad Eckert Haifa donated a kidney to Ben Yair. Exchange contributed son of Yair kidney to her husband. "For them it does not matter who contributed to whom. Them they saved the family" 

A more usual story is of ordinary deceased donation: here's one from the Jerusalem Post
Jewish kidney donation saves Palestinian boy
"Kidney of Israeli boy who suffered brain death saves Palestinian child; Peres: We are proud of your contribution to peace."

Conference in Memory of Jean Francois Mertens, Jerusalem, June 6,7, and 9.

Conference in Memory of Jean Francois Mertens, Jerusalem, June 6,7, and 9.

Thursday, June 6
09:00 – 09:30 Welcome
09:30 – 10:15 Robert J. Aumann , “My Jean-François”
10:15 – 11:00 Françoise Forges, “Bayesian Repeated Games”
11:00 – 11:30 Break
11:30 – 12:15 Claude d'Aspremont, “Some Remarks on Bayesian Incentive Compatibility and the Core in the Absence of Wealth Effects”
12:15 – 13:00 Hari Govindan, “Toward a Theory of Stability in Repeated Games”
(joint with Aldo Rustichini and Bob Wilson)
13:00 – 14:30 Lunch
14:30 – 15:15 François Maniquet, “Strategic Voting under Proportional Representation”
15:15 – 16:00 Anna Rubinchik, “Regularity and Stability of Equilibria in an Overlapping Generations Model with Exogenous Growth” (joint with Jean François-Mertens)
16:00 – 16:15 Break
16:15 – 17:00 Sergiu Hart, “Correlated Equilibria: Markets, Dynamics, and Computation”

Friday, June 7
09:30 – 10:15 Alvin Roth, “Deceased Organ Donation and Solicitation in Israel and the U.S”
10:15 – 11:00 Geoffroy de Clippel , “Egalitarianism under Incomplete Information”
11:00 – 11:30 Break
11:30 – 12:15 Olivier Gossner , “The Value of Information in Zero-Sum Games” (joint with Jean- François Mertens)
12:15 – 13:00 Yair Tauman ,“Voting Power and Proportional Representation of Voters”
(joint with Artyom Jelnov)
13:00 – 14:30 Lunch
14:30 – 15:15 Elon Kohlberg , “The Shapley Value of Stochastic Games”
Sunday, June 9
09:30 – 10:15 Eric Maskin , “Markov Equilibrium” (joint with Jean Tirole)
10:15 – 11:00 Bernard de Meyer, “Risk Aversion and Price Dynamics on the Stock Market”
11:00 – 11:30 Break
11:30 – 12:15 Adi Karni & Jacques Drèze , “Subjective Expected Utility with State-Dependent Utility and ActionDependent Probabilities”
12:15 – 13:00 Pierre Dehez , “How to Share Joint Liability: A Cooperative Game Approach”
(joint with Samuel Ferey)
13:00 – 14:30 Lunch
14:30 – 15:15 Abraham Neyman , “Continous-Time Stochastic Games”
15:15 – 16:00 Shmuel Zamir , “The MZ Formula: Origins and Recent Application”
16:00 – 16:15 Break
16:15 – 17:00 Roger Myerson , “Settled Equilibria” (joint with Jörgen Weibull)

Jerusalem School in Economic Theory: Decision Making: June 10-19 2013

The 24th Jerusalem School in Economic Theory

Decision Making

Lecturers

Maya Bar-Hillel	Hebrew University
Itzhak Gilboa	Tel Aviv University
Daniel Kahneman	Princeton University
David Laibson	Harvard Universit
Mark Machina	University of California, San Diego
Eric Maskin	Harvard Universit
Wolfgang Pesendorfer	Princeton University
Ariel Rubinstein	Tel Aviv University
Eyal  Winter	Hebrew University

 Decision making is at the heart of economics: production, exchange, and consumption are all the result of choices made by individual agents. For over sixty years, the benchmark framework for studying agents' decisions whose consequences are uncertain has been the expected utility model. But anomalies from experimental work in psychology and behavioral economics have led to revisions of expected utility and of utility theory more generally. The Summer School will explore both the standard model and some of the most important alternatives

Here's the program (Manny Yaari speaks about Newcomb's paradox on the last day, although he's not listed as one of the 'lecturers'...)

2013 Results and Data Book from NRMP’s Main Residency Match

Here's the press release: 2013 Results and Data Book from NRMP’s Main Residency Match, and here's the data book for the 2013 Match

The data book also reports on the second year of the new SOAP scramble, but not in the same detail as last year's report. Last year I predicted that more of the visible action would move to the first round (reflecting more action before the beginning of the official scramble), but this year's data book doesn't give that information.

Here's the press release, though, which gives a good overview of the data, which seem to reflect a successful match year.

The National Resident Matching Program® (NRMP®) is pleased to announce the publication of its Results and Data 2013 Main Residency Match --- the most comprehensive Match data resource produced annually by the NRMP. The report provides statistics on the most successful Match in NRMP history, in which 28,130 of 29,171 available residency positions were filled.    

Included in the report are statistical tables and data graphs from the Main Residency Match and a state by state breakdown of each participating U.S. residency training program, with the number of positions offered and filled for each. This year, for the first time, the report includes results and charts from the Match Week Supplemental Offer and Acceptance Program® (SOAP®)-- the process used by NRMP for unfilled residency positions.

This year’s Results and Data Book is notable because the 2013 Match was the first to utilize NRMP’s All In Policy, which requires participating programs to register and attempt to fill all their positions through The Match.

NRMP Executive Director Mona M. Signer said, “Readers of the 2013 Results and Data Book will see the overwhelming success of the All In Policy. The 2013 Match produced the highest fill rate in NRMP history, and match rates rose for nearly every applicant group.”

Results and Data 2013 Book Facts

Applicant Numbers (Comparisons to 2012) 

• 40,335 registrants (1,958 more)
• 34,355 active applicants (3,000 more)
• 17,487 U.S. allopathic medical school seniors (960 more)
• 2,677 osteopathic medical school students/graduates (317 more, highest ever)
• 5,095 U.S. citizen international medical school students/graduates (U.S. IMGs) (816 more)
• 7,568 non-U.S. citizen international medical school students/graduates (IMGs) (740 more)

Applicant Match Rates 

• 74.1 percent of all applicants were matched to PGY-1 positions
• 93.7 percent of U.S. allopathic seniors matched to PGY-1 positions; of those, 78.8 percent matched to one of their top three choices
• 53.1 percent of U.S. IMGs were matched to PGY-1 positions, up from 49.1 percent in 2012 and the highest Match rate for this applicant group since 2005
• 47.6 percent PGY-1 Match rate for IMGs, an increase of seven percentage points from 2012

Increased Positions/High Fill Rates
Available residency positions increased to 29,171, 2,399 (9 percent) more than in 2012, when 26,772 positions were offered. The increase is due primarily to implementation of the All In Policy, which resulted in some specialties offering significantly more positions in 2013. Internal Medicine offered 1,000 more positions, Family Medicine offered 297 more, and Pediatrics offered 141 more than the prior year.

The overall position fill rate increased 1.1 percentage points to 96.4 percent, the highest in NRMP history. In 2013, only 1,041 first-year and second-year positions were unfilled; of those, 939 were placed in SOAP, and all but 61 were filled.

Notable Specialties
Often Match results can be an indicator of competitiveness. This year, several specialties and specialty tracks had 100 percent fill rates: 

• Medicine Emergency Medicine
• Pediatrics Primary
• Pediatrics/Psychiatry/Child Psychiatry
• Physical Medicine and Rehabilitation – Post graduate year one (PGY-1)
• Plastic Surgery – Post graduate year two (PGY-2)
• Psychiatry Family Medicine
• Radiation Oncology (PGY-1)
• Thoracic Surgery

The following specialties filled more than 90 percent of positions with U.S. seniors: 

• Plastic Surgery: 95.7 percent
• Otolaryngology: 94.5 percent
• Neurological Surgery: 93.1 percent
• Orthopedic Surgery: 91.8 percent

Couples in the Match
In 2013, a record 1,870 applicants (935 couples) participated in the 2013 Match. They continued to enjoy great success with a match rate of 95.2 percent. Couples have been able to participate together in The Match since 1984. The two partners identify themselves as a couple to the NRMP and submit rank order lists of identical length. The algorithm treats their lists as a unit, matching the couple to the highest linked program choices where both partners match.

SOAP - Supplemental Offer and Acceptance Program
The NRMP launched the Match Week SOAP in 2012 to replace the "Scramble" and to streamline the process for unmatched applicants and the directors of unfilled programs. During SOAP, eligible applicants use ERAS® to apply to programs with unfilled positions and offers are extended to applicants based upon the number of unfilled positions remaining in the program.

U.S. seniors accepted the majority of positions (595 of 878) filled during SOAP. More than 13,808 applicants were SOAP-eligible, 261 more than in 2012. This year, 406 unfilled programs elected to participate in SOAP, offering 939 of the 1,041 positions not filled when the matching algorithm was processed.

A total of 1,327 offers were sent to applicants. By the conclusion of SOAP, 93.5 percent (878 of 939) of the positions had been filled.

How the Match Works
Conducted annually by the NRMP, The Match uses a computerized mathematical algorithm to align the preferences of applicants with the preferences of residency program directors in order to fill the training positions available at U.S. teaching hospitals. Research on the NRMP algorithm was a basis for Dr. Alvin Roth’s receipt of the 2012 Nobel Prize in Economics.

# # #
The National Resident Matching Program® (NRMP®) is a private, non-profit organization established in 1952 at the request of medical students to provide an orderly and fair mechanism for matching the preferences of applicants for U.S. residency positions with the preferences of residency program directors. In addition to the Main Residency Match, the NRMP conducts matches for more than 40 subspecialties. For more information, contact NRMP at 1-866-653-NRMP (6767) or visit http://www.nrmp.org. For interviews, please email cherbert@nrmp.org.

Read more: http://www.digitaljournal.com/pr/1278215#ixzz2V7ttPAqX

Breadwinner wives

In his NY Times column, Dick Thaler writes about the "interesting new paper by Marianne Bertrand, Emir Kamenica and Jessica Pan, three economists who are colleagues of mine at the University of Chicago’s Booth School of Business. They found that traditional views of gender identity, particularly the view that the right and proper role of the husband is to make more money than the wife, are affecting choices of whom to marry, how much to work, and even whether to stay married."

 He ends with this:
"But now back to the notion of couples’ contentment: Is there any way to tell whether it’s the wife or the husband who becomes unhappy when the wife earns more? Does he think that she is threatening his manliness, or does she think that he’s a slacker?

That may be impossible to answer, partly because of something I learned long ago from Alvin E. Roth, a Nobel laureate in economics last year. I call it Roth’s rule: In equilibrium, it’s impossible for you to be happier than your spouse.

If you and your spouse both understand that rule, you’re both likely to be happier — regardless of how much money either of you make."

Matt Jackson on market design

Matching, Auctions, and Market Design

Matthew O. Jackson 

Stanford University - Department of Economics; Santa Fe Institute; Canadian Institute for Advanced Research (CIFAR)
April 10, 2013
Abstract:      
I provide a brief introduction to the early literatures on Matching, Auctions, and Market Design.

The design of matching markets and auctions has brought economic theory and practice together. Indeed, this is an area where microeconomic theory has had its largest direct impact. This is in part because it focuses on settings where people interact according to very clearly delineated rules. Thus, the strategic interactions of the participants are relatively easy to model, and outcomes are comparatively straightforward to assess relative to the many other less structured interactions that occur in an economy. In view of this, these are arenas where economic theory has directly shaped institutions ranging from the systems by which students are assigned to public schools to the manner in which governments have auctioned to the rights to parts of the broadcast spectra in particular geographic regions.

Experimental Economics and Market Design in Zurich: ESA meetings July 11-14, 2013

The international meeting of the Economic Science Association will be in Zurich. (Jacob Goeree will become the president of ESA at that time.) Registration deadline is June 1...

Keynote lectures will be delivered by:

• Peter Bossaerts (California Institute of Technology)
• Alessandra Casella (Columbia University)
• John Wooders (University of Technology, Sydney)

The ESA meetings will be preceded by a market design workshop:

On Thursday, July 11 the ESEI center for market design will host their second workshop.  Details about the workshop can be found on the website for the ESA World Meetings esa2013.esei.ch ("ESEI Workshop" tab) 

The workshop is organized around 5 major market design questions with presentations delivered by the following speakers:

1. Electricity Markets

o   Wedad Elmaghraby (University of Maryland)

o   Axel Ockenfels (University of Cologne)

2. Financial Markets

o   Paul Klemperer (Oxford University)

o   Peter Bossaerts (California Institute of Technology)

o   Jürgen Huber (University of Innsbruck)

3. Spectrum Auctions

o   Martin Bichler (Technical University of Munich)

o   Maarten Janssen (University of Vienna)

4. Airport Resource Allocation

o   Hamsa Balakrishnan (Massachusetts Institute of Technology)

5. Online Markets

o   Yan Chen (University of Michigan)

o   Tuomas Sandholm (Carnegie Mellon University)

The workshop starts at 8:20AM and ends at 5:00PM, when the reception for the ESA World Meetings starts.   The workshop is open to everyone and we very much welcome ESA conference participants.  

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)

Symposium on Visions of the Theory of Computing at the new Berkeley Simongs Institute

Berkeley's new Simons Institute for the Theory of Computing announces the following symposium:

 Symposia | Spring 2013

Visions of the Theory of ComputingMay 29–31, 2013
Berdahl Auditorium, Stanley Hall, UC Berkeley
Schedule

Pending speaker approval

Wednesday, May 29

8:15 – 8:45 a.m.	Coffee and Check-In
8:45 a.m.	Welcome from Richard Karp, Director of the Simons Institute Remarks from Greg Hager, incoming CCC Vice Chair Introduction to the Symposium Christos Papadimitriou, UC Berkeley
9 – 10 a.m.	What Should a Computational Theory of Cortex Explain? Leslie Valiant, Harvard University
10 – 11 a.m.	Why You Should Love Quantum Entanglement John Preskill, Caltech
11 – 11:30 a.m.	Break
11:30 a.m. – 12:30 p.m.	Why Biology is Different Bernard Chazelle, Princeton University
12:30 – 1:30 p.m.	Lunch Break
1:30 – 2:30 p.m.	Big Data and New Models Needed to Study DNA Variation in Evolution and Cancer David Haussler, UC Santa Cruz
2:30 – 3 p.m.	Break
3 – 4 p.m.	Perfection and Beyond Maria Chudnovsky, Columbia University
4 – 5 p.m.	Bursts, Cascades, and Hot Spots: Algorithmic Models of Social Phenomena Jon Kleinberg, Cornell University
5 – 6:30 p.m.	Reception

Thursday, May 30

8:30 – 9 a.m.	Coffee and Check-In
9 – 10 a.m.	Interaction: How and Why? Shafi Goldwasser, MIT
10 – 11 a.m.	Phase Transitions in Large Scale Computation: A Statistical Physics Perspective Marc Mézard, ENS Paris
11 – 11:30 a.m.	Break
11:30 a.m. – 12:30 p.m.	Theory of Data Streams S. Muthu Muthukrishnan, Rutgers University and Microsoft Research
12:30 – 1:30 p.m.	Lunch Break
1:30 – 2:30 p.m.	Intelligence and Machines: Creating Intelligent Machines By Modeling the Brain Jeff Hawkins, Numenta
2:30 – 3:30 p.m.	The Online Revolution: Learning Without Limits Daphne Koller, Stanford University
3:30 – 4 p.m.	Break
4 – 5 p.m.	Programming Nanoscale Structure Using DNA-Based Information Ned Seeman, New York University

Friday, May 31

8:30 – 9 a.m.	Coffee and Check-In
9 – 10 a.m.	Five Discontinuities that Reshaped My Research (and a Lot Else) Prabhakar Raghavan, Google
10 – 11 a.m.	Market Design and Computer-Assisted Markets: An Economist’s Perspective Alvin Roth, Stanford University
11 – 11:30 a.m.	Break
11:30 a.m. – 12:30 p.m.	Evolution and Computation Christos Papadimitriou, UC Berkeley
12:30 – 1:30 p.m.	Lunch Break
1:30 – 2:30 p.m.	The Mathematics of Casual Inference, with Reflections on Machine Learning and the Logic of Science Judea Pearl, UCLA
2:30 – 3:30 p.m.	The Gospel According to TCS Avi Wigderson, Institute for Advanced Study, Princeton
3:30 – 4 p.m.	Break
4 – 5 p.m.	The Modern Astrophysics Stack: Automated Action and Insight Josh Bloom, UC Berkeley

And then there was France...

but the opposition to same sex marriage in France hasn't vanished: Huge anti-gay marriage protest march in Paris

Forges, Haeringer and Iehle on matching

Appariement: des modeles de Lloyd Shapley a la conception de march es d'Alvin Roth.

Francoise Forges ,  Guillaume Haeringer,, Vincent Iehle

Here's the English summary:


Matching: from Lloyd Shapley's models to Alvin Roth's market design.

Summary
Alvin Roth and Lloyd Shapley have received in 2012 the Sveriges Riksbank prize in economic sciences in memory of Alfred Nobel, for their work on the centralized organization of some economic markets, which rely on the matching of agents of two different types (students and schools, for instance). Shapley is the co-author, with David Gale, of the seminal paper of the area, which proposes an algorithm to reach a stable matching. Roth directed the reform of the entry level labor market for American physicians (the National Resident Matching Program) and the design of a market for kidney transplants. After having surveyed these contributions, we also give an account of Shapley's leading role in game theory.

update: here's the citation,
Francoise Forges ,  Guillaume Haeringer, Vincent Iehle
Matching: from Lloyd Shapley's models to Alvin Roth's market design
REVUE D ECONOMIE POLITIQUE  Volume: 123   Issue: 5   Pages: 663-696    SEP-OCT 2013

Yan Chen chosen president-elect of Economic Science Association

Here's the announcement from the University of Michigan (one will come from the ESA after the international meetings in Zurich this summer):
Yan Chen chosen president-elect of Economic Science Association

Professor Yan Chen has been chosen as the president-elect of the Economic Science Association (ESA), a professional organization devoted to using controlled experiments to learn about economic behavior.

Experimental methods allow researchers to control economic institutions, information, policies, and other important variables, both in the laboratory and in the field. Experiments have provided important information about economic behavior in a variety of subdisciplines of economics, including game theory, consumer behavior, industrial organization, public finance, and labor economics.

The ESA membership includes economists interested in the results of such experiments, as well as scholars in psychology, business, political science, and other related fields. The association publishes a quarterly journal, Experimental Economics, sponsors conferences, and maintains online discussion groups for its members.

The president-elect serves for two years, followed by two years as president. Among Chen’s responsibilities as president will be the planning of the annual meeting and oversight of the association’s journals. She is currently a member of the association's executive committee, serving a three-year term which was to end in 2015.

The association’s current president, Al Roth, won the Nobel Memorial Prize for economics in 2012.

New in Iran: Donate one of your kidneys to be exempted from military service

There's a new development regarding kidney donation and sales in Iran. Google translate renders the headline Donate one of your kidneys to be exempted from military service

I am assured on good authority that the story says that kidney donors will be exempted from military service.

Here's how Google Translate renders the story:

"Acting Human Resources department Stadkl Armed Forces exemptions from military service the soldiers announced the donor organ. According to ISNA, General Moussa Kamali on donor exemption from military service, said the donor organ to make it happen efficiency, We'll exempt him from military service. According to him, for example, people who donate one of his kidneys has been the inclusion of medical waivers are exempt from military service. Stadkl Armed Forces Acting Human Resources department stating Srfdashtn donation card member, was not the reason for exemption from military service, said those who donate their organ, even during military service are exempt from military service."


Here's the article in Farsi: http://www.alef.ir/vdcgnu9qzak9774.rpra.html?187850 for those who can make your own translation.

HT: Mohammad Akbarpour

Economic rewards to motivate blood donations, by Lacetera, Macis and Slonim

This just out in Science: Economic rewards to motivate blood donations. It suggests that old conclusions need to be revisited based on new evidence.

"The position and guidelines of the World Health Organization (WHO) and several national blood collection agencies for nearly 40 years have been based on the view that offering economic incentives to blood donors is detrimental to the quantity and safety of the blood supply (1). The guidelines suggest that blood should be obtained from unpaid volunteers only (2). However, whether economic incentives positively or negatively affect blood donations (and other prosocial activities) has remained the subject of debate since the positions were established (2–8).

"Evidence consistent with the WHO position came originally from uncontrolled studies using nonrandom samples and, subsequently, from surveys and laboratory studies indicating that economic incentives can “crowd out” (decrease) intrinsic motivations to donate and can attract “worse” donors (9). This evidence arguably affected policies, such as bans on compensation for blood and organ donations in many countries.
...
"With a few early exceptions based on small, nonrepresentative samples (12), field trial evidence on how economic incentives affect blood donations has been absent. But field-based evidence from large, representative samples has recently emerged. The results are clear and, on important questions, opposite to the uncontrolled studies, surveys, and laboratory evidence preceding them."
...
"Conclusion

"In light of the recent evidence, it is time to re-examine policy guidelines for increasing and smoothing blood supply, including whether incentives can play a role. There are efforts under way from different parts of society toward using rewards to increase donations. The U.S. 9th Circuit Court of Appeals' 2012 ruling legalizing compensation for bone marrow donations through apheresis was initiated by private individuals (32). A company prompted a 2010 European Court of Justice ruling that allowed importation of blood products obtained from compensated donors (33). Researchers and clinicians have noted that some WHO guidelines (e.g., emphasis on exclusive use of nonremunerated donors and centralizing blood collection organizations) are unintentionally adversely affecting blood collection in sub-Saharan Africa (34).

"In addition to economic incentives, policy-makers should consider nonpecuniary rewards (e.g., symbolic and with social recognition) and various appeals. Debates on ethical issues around giving rewards for donations (35) should be encouraged. But there should be little debate that the most relevant empirical evidence shows positive effects of offering economic rewards on donations."

Same sex marriage in Latin America

Things are changing all over the Americas regarding this no longer so repugnant transaction: How Latin Culture Got More Gay

"BRAZIL is potentially poised to become the third and largest country in Latin America to legalize same-sex marriage, following a judicial order on Tuesday. Argentina was the first, in 2010, after the government brushed aside objections from Cardinal Jorge Bergoglio of Buenos Aires, now the pope. The Uruguayan legislature followed suit last month. Mexico City has allowed such unions since 2010, and the Mexican state of Quintana Roo since 2011.
...
"These developments not only undermine stereotypes about machismo, but also the assumption that the prominence of Catholicism makes progressive change impossible. Same-sex marriage is legal in Belgium, Portugal and Spain, and Ireland recognizes civil unions. As the United States Supreme Court debates same-sex marriage, perhaps it should consider the precedent set by other nations of the Western Hemisphere."

Deceased donor waiting lists in Germany: scandal and aftermath

In an article entitled "Trust is Everything," Sue Pondrom reports in the American Journal of Transplantation (May 2013, vol 13 issue 5 pp1115-6) on the aftermath of a German transplant scandal.

"After a scandal regarding transplant corruption in Germany, the Deutsche Stiftung Organ transplantation (DSO), Germany's organ procurement organization, has announced that organ donations in the country were down nearly 13% by the end of last year.

"Public confidence in Germany's transplant system has suffered dramatically since newspapers throughout the country described cases of waitlist manipulation over the last 10 years at four liver transplant centers: University of Göttingen, University of Regensburg, Munich Klinikum rechts der Isar hospital and University Hospital Leipzig. At all four centers, doctors falsified liver patient medical records to indicate the patients were also undergoing dialysis. As a result, those patients were erroneously moved up the waiting list."

Post ATC post

Well, I'm back from the American Transplant Congress in Seattle, and it was quite nice to see multiple sessions on various aspects of kidney exchange, which has now graduated to the status of one of the standard ways of arranging kidney transplantation.

Here's the ATC's coverage of my Sunday talk: Keynote: Medical Community, Economist Collaboration Essential in Kidney Exchange

Alvin E. Roth, PhD: ‘Economics is about more than money and prices. It's also about organization, cooperation and coordination.'

If ever an endeavor existed that calls for careful, thoughtful collaboration, it is paired kidney exchange. Nobel laureate economist Alvin E. Roth, PhD, addressed the challenges in such exchanges and what economists can bring to this collaboration when he delivered Sunday's Keynote Lecture, "Kidney Exchange: An Economist's Perspective."

"Many things must happen to bring kidney transplant donors and recipients into the operating room," said Dr. Roth, the Craig and Susan McCaw Professor of Economics at Stanford University and the George Gund Professor Emeritus at Harvard University. "For some of those things, it has proven beneficial to look beyond the boundaries of the medical community to economists and market designers. Economics is about more than money and prices. It's also about organization, cooperation and coordination. 

Interdisciplinary collaboration is common in market design because market designers help experts in specific areas organize to achieve their goals. Dr. Roth said some remarkable transplant surgeons have collaborated with him and his colleagues in the ongoing effort to increase transplantation through exchange.

Even more collaboration will be required to coordinate among the multiple organizations involved in kidney exchange. A collaborative system that encompasses the largest pool of patients theoretically would produce the most transplants, but large organizations can be bureaucratic and inhibit innovation if not properly structured, he said. Some of the fastest-moving, entrepreneurial, innovative transplant organizations have been arranging the most transplants.

"Collaboration among kidney exchange programs is going to be important," Dr. Roth said. "However, we will have to put some careful thought in how to do it." 

In discussing logistics, he praised the non-directed, non-simultaneous donor chain as an innovation that has allowed the exchange of more kidney donations and has led to an increasing number of transplants. The chain begins with a non-directed donor, i.e. one who does not have an intended recipient and who donates to a patient in the kidney exchange pool of patient-donor pairs. That patient's donor continues the chain by donating to another patient in the pool, and so on, typically ending in a donation to a patient who has no donor.

"The ability to make non-simultaneous donations has allowed these chains to become quite long," Dr. Roth said. "That, in turn, has produced many more kidney transplants, which can include more of the most highly sensitized patients."

As more transplant centers have become adept at kidney exchange, there is a growing tendency for them to hold back their easy-to-match patients from the centralized kidney exchange pools to match these patients in their own centers. The consequence has been that hard-to-match patients are overly represented in kidney exchange pools.

"Easy-to-match patients in the mix are good for hard-to-match patients," Dr. Roth said. "We need to find ways to make it reasonable for the easy-to-match pairs to be in the large kidney exchange pools."

Finance also is an issue. Kidney exchange involves collaboration among hospitals, each of which may have different charges for nephrectomies, for example. One solution may involve developing a standard acquisition charge to make live kidney donation as uniform as it already is for deceased donor kidneys.

And expect kidney exchange design to remain in flux.

"The design of how kidney exchanges are organized is an ongoing process that has to change in reaction to changes in how transplant centers behave and what the patient pool looks like," Dr. Roth said. "We shouldn't think of it as something that is fixed in time but something that requires constant attention." 

5 Are Convicted in Kosovo Organ Trafficking

Here's the story from the NY Times: 5 Are Convicted in Kosovo Organ Trafficking

"Five people were convicted Monday in Pristina, the capital of Kosovo, in connection with an elaborate organ-trafficking network that lured poor people to the country to sell their kidneys and other organs to wealthy transplant recipients from Israel, the United States, Canada and Germany. Organs sold for as much as $130,000 each.
"The defendants, all Kosovars, were tried before a panel of two European Union judges and one Kosovar judge. A special prosecutor for the union, Jonathan Ratel, called the case a landmark because doctors had been convicted.
...
“The sole and driving motive for this exploitation of the poor and the indigent was the opportunity for obscene profit and human greed,” Mr. Ratel, the prosecutor, said Monday. “In every sense this was a cruel harvest of the poor.”
...
"According to the indictment in the case, traffickers in the network promised payments of up to $26,000 to poor people in Turkey, Moldova and Russia to persuade them to travel to Kosovo and donate an organ. They were asked to sign false documents saying they were donating to a relative for humanitarian reasons.

"Two dozen donors were taken in by the scheme; many were never given any compensation and were released without adequate medical care."
...
"Mr. Ratel said the Dervishis were aided by Dr. Yusuf Sonmez, whom he called a notorious international organ trafficker. Dr. Sonmez is a fugitive and may be in South Africa, Mr. Ratel said."