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