Couples on the labor market

One of the longstanding puzzles in market design is why we have been as lucky as we have been in the design and operation of labor market clearinghouses that allow couples to state preferences over pairs of jobs. You can't get a stable matching without allowing couples to state their preferences this way, but when they do, the set of stable matching can be empty. But it almost never is, in practice.

Here's a first step towards understanding that:
Kojima, Fuhito, Parag A. Pathak, and Alvin E. Roth, " Matching with Couples: Stability and Incentives in Large Markets," working paper, April 8 2010.

Abstract: Complementarities pose problems in models of two-sided matching markets. This has been a longstanding issue in the design of centralized labor market clearinghouses that need to accommodate complementarities due to couples, as in the US market for medical doctors. These clearinghouses aim for a stable matching but a stable matching does not necessarily exist when
couples are present. This paper provides conditions under which a stable matching exists with high probability in large markets. Moreover, we present a mechanism that finds a stable matching with high probability and in which truth-telling by all participants is an approximate equilibrium. We relate these theoretical results to data from the labor market for clinical psychologists, in which stable matchings exist for all years of our data, despite the presence of couples.

Match Day!

This year's schedule for announcing the results of the resident match ends today, when most graduating medical students will learn where they have been matched.

Over the last few days, those who were not matched in the main match learned of this, so that they could "scramble" to match by the time that their colleagues would learn of their matches.

Here's this year's schedule:

March 15, 2010--Applicant matched and unmatched information posted to the Web site at 12:00 noon eastern time.
March 16, 2010--Filled and unfilled results for individual programs posted to the Web site at 11:30 a.m. eastern time.
Locations of all unfilled positions are released at 12:00 noon eastern time. Unmatched applicants may begin contacting unfilled programs at 12:00 noon eastern time.
March 18, 2010--Match Day! Match results for applicants are posted to Web site at 1:00 pm eastern time.

Next year this will all play out differently, since the NRMP has decided to organize a "managed scramble":

"The NRMP Board of Directors has voted to proceed with implementation of a "managed" Scramble for the 2012 Main Residency Match. Under the plan, unfilled positions must be offered and accepted through the NRMP R3 System during Match Week. Offers will be made every three hours Wednesday - Friday of Match Week, and applicants will be able to receive multiple simultaneous offers. Match Day will be moved from Thursday to Friday. Questions should be directed to nrmp@aamc.org."

Right now there is pressure on the number of residencies that can be funded, so there may not be as much problem with congestion as would otherwise be a concern. We'll have to wait until next year to find out. (I wasn't involved in this latest design discussion.)

New clearinghouse for new doctors in Scotland

There have been some changes in the SCOTTISH FOUNDATION ALLOCATION SCHEME, the program that matches new medical graduates to their first positions (which would be called residencies in the US) in Scotland.

Two features stand out in comparison to the American system (the NRMP).

First, employers may not submit preferences, but rather are all constrained to rank potential employees by their exam scores.

Second, couples cannot submit preferences over pairs of positions. Instead, each member of the couple submits a rank ordering of individual positions, and the algorithm combines these into a joint preference over pairs that is a function of the submitted rank order list and a table of compatibilities of positions.

"To accommodate linked applicants, a joint preference list is formed for each such pair, using their individual preference lists and the programme compatibility information. If such a pair, a and b, have individual preferences p1, p2, . . . , p10 and q1, q2, . . . , q10 respectively (with a the higher scoring applicant), then the joint preference list of the pair (a,b) is (p1,q1), (p1,q2), (p2,q1), (p2,q2), (p1,q3), (p3,q1), (p2,q3), (p3,q2), . . ., (p9,q10), (p10,q9), (p10,q10) (except that incompatible pairs of programmes are omitted)
In the main body of the algorithm, the members of a linked pair are handled together, so the match of the pair (a,b) to the programmes (p,q) will be accepted only if each of these programmes either has an unfilled place or a lower scoring applicant who can be displaced. A complication arises when one member x of a linked pair has to be withdrawn from a programme p because his/her partner was displaced from their current assigned programme. In this case, some other applicants may have been rejected by p because of the presence of x, and any such applicant a must be withdrawn from their current programme, if any, and have their best achievable preference reset to p. (A corresponding, but more complex reset operation is needed if a is a member of a linked pair). This reset operation thereby allows a further opportunity for applicant a to be matched to programme p.
The algorithm terminates when every single applicant and linked pair is either matched or has been rejected by, or displaced from, every entry in their preference list with no possibility of reconsideration by a programme that has had a withdrawal.
The final matching is stable for single applicants, as before, but also for linked pairs, in the sense that:
there can be no linked pair (a,b) of applicants who would prefer to be matched to compatible programmes (p,q), and at the same time, each of p and q has an unfilled place or an assigned applicant with a lower score than a and b respectively."

HT: Rob Irving, who has designed and implemented the algorithm.

Here are some related papers by members of the Scottish matching group.

Keeping partners together: algorithmic results for the hospitals/residents problem with couples by Eric J. McDermid and David F. Manlove in
Journal of Combinatorial Optimization, (2009)

R.W. Irving, D.F. Manlove and S. Scott, The stable marriage problem with master preference lists, Discrete Applied Mathematics vol. 156 (2008), pp. 2959-2977.

The market for lawyers, a modest proposal

Ashish Nanda at the Harvard Law School has a modest proposal for how the jobmarket for new associates at large law firms should be organized, particularly in light of some of the problems that have been exposed in the current recession: Lawyers Should Be Recruited Like Doctors

"The current oversupply of new associates has sent law firms scrambling to implement short-term adjustments, such as secondments and deferrals. But the legal profession needs more than temporary half-measures. The new-associate recruitment market is fundamentally broken, and it has been for some time. Incremental changes are not going to address its underlying problems. The market needs a structural fix -- a centralized matching authority, like the one that the medical profession has been using for more than half a century. "

HT: Guhan Subramanian

Would Professor Moriarty have invented an eBay, a Paypal or a Craigslist?

Professor Moriarty was, of course, Sherlock Holmes' nemesis (or was it the other way around)? I ask the question in the title of this post because a much more modern criminal mastermind has just been sentenced. Here's the headline from the London Telegraph: Mastermind behind 'eBay for criminals' is facing jail

"Renukanth Subramaniam, from north London, established the website DarkMarket, which threatened every bank account and credit card holder in Britain and caused tens of millions of pounds of losses.
It was described as a "one-stop shop" for fraudsters buying and selling stolen details such as PIN numbers, account balances, answers to account security questions and passwords for social networking websites.

"The site even offered criminal users a secure payment system, training and advertising space to sell equipment used to clone bank and credit cards.
DarkMarket operated for almost three years as a “criminals only” forum, with more than 2,500 members at its peak, who could buy up to 10 credit card numbers along with other personal information for around £30.
It was shut down after a two-year global investigation in which undercover agents from the FBI and the Serious Organised Crime Agency infiltrated the site by posing as criminals.
A spokesman for Soca called it “one of the most pernicious online criminal websites in the world” and estimated that its victims lost tens of millions of pounds.
Officials said there was a code of “honour amongst thieves” on the site.
There was a secure payment system between criminals – described by Judge John Hillen as a "PayPal for criminals". "

See my earlier post: More on Darkmarket, the Craigslist of Crime

Progress towards a sensibly organized national kidney exchange

An important story has played out one more quite positive step in the dry prose of medical bureaucracy, in the form of a report of the Policy Oversight Committee of the Organ Procurement and Transplantation Network (OPTN) of the Health Resources and Services Administration (HRSA). (All of the reports are found here.)

The report in question is this one, OPTN/UNOS Policy Oversight Committee, Report to the Board of Directors, November 16-17, 2009, and the item in question has to do with how a pilot national kidney exchange might be organized, if it overcomes some hurdles presently standing in its way. In particular, the cumbersome review process is catching up with the progress being made in regional kidney exchanges, in which chains have become important, expecially since the introduction of Non-simultaneous kidney exchange chains .

"The Committee supports the Kidney Transplantation Committee’s proposal to include living donors and donor chains in the Kidney Paired Donation Pilot Program. (Item 3, Page 6)."

Here it is:

"3. Proposal to include non-directed living donors and donor chains in the Kidney Paired Donation Pilot Program.

Currently, the Kidney Paired Donation (KPD) Pilot Program only allows living donors with incompatible potential recipients to participate. Non-directed (or altruistic) living donors (those who are not linked to an incompatible potential recipient) have no way to enter the program. Also, candidate / donor pairs can only be matched in groups of two or three, and all donor nephrectomies in the group must occur simultaneously. This proposal would allow non-directed living donors to participate in the KPD Pilot Program and add donor chains as an option in the system. A donor chain occurs when a non-directed living donor gives a kidney to a recipient whose living donor in turn gives a kidney to another recipient and continues the chain. This proposal would allow two types of donor chains: open and closed. Closed chains start with a non-directed living donor and end with a donation to a recipient on the deceased donor waiting list. Open chains start with a non-directed living donor and end with a bridge donor who will start another segment in the open chain. In open chains, the
bridge donor nephrectomy does not occur at the same time as the other living donor nephrectomies. Donor chains have the potential to increase the number of transplants in a KPD system.
The Committee used the scorecard to assess this policy, and the proposal received an overall score of 23.5. The proposal received average score of greater than 2.3 in every category except patient safety and oversight, geographical equity, and operational effectiveness.
The Committee unanimously supported this proposal by a vote of 9 in favor, 0 opposed, and 0 abstentions."

Deferred acceptance in Ghanian school choice

Kehinde Ajayi, a Ph.D. Candidate in the Department of Economics at the University of California, Berkeley, is studying school choice in Ghana. She recently sent me a 2005 document from Ghana's (then) Ministry of Education and Sport "that the government produced when the Computerised School Selection and Placement System (CSSPS) was initially introduced."

It describes a version of a deferred acceptance algorithm (a clearinghouse algorithm that has been discovered a number of times and places, but that game theorists associate with Gale and Shapley 1962), and describes an essential feature, which is that if student A would have displaced student B at school S had he ranked school S first, he will also displace student B at school S even if he ranks school S second (or lower). This is what makes it safe to list schools in your true order of preferences.

"4.2 Displacement
a. Selection on Merit
The computer places all qualified candidates into their first choice schools using the ranking order. The aggregate score of six subjects of each candidate is used to do the ranking.
b. Displacement of 1st choice candidates by 2nd choice candidates as a matter of merit or better performance
The ranking may displace 1st choice candidates with 2nd choice candidates; this will be on merit and not choice. The following table is an illustration:
"Kwasi and Kofi make the following choices of schools and programmes.
...[Table showing that Kwasi, with an aggregate 'score' of 400 ranks Anglican as his second choice, while Kofi, with a score of only 350 ranks Anglican as his first choice...]
"Suppose the cut-off for Science Programme for Opoku Ware is 420 and that for Anglican School is 350, Kwasi is sent to Anglican to compete with first choice candidates for science Programme because his aggregate score is just below the cut-off for Science Programme for Opoku Ware School. Kwasi is then sent to Anglican to compete with the first choice science candidates. Since Kwasi’s aggregate score is higher than that of Kofi’s, Kwasi will then displace Kofi."

New York City High School choices are due Dec 4

These days I follow the NYC high schools from a distance, but it's gratifying to see some of the long lasting changes that Atila Abdulkadiroglu and Parag Pathak and I got to help put in place (described here, and for those really interested in technical detail, here).

Here's some advice on ranking schools, from a contemporary observer at InsideSchools.org: HS applications due Dec. 4: How to rank the schools

"Your favorite should come first. You don’t need to play guessing games or set up an elaborate strategy. You have nothing to lose and everything to gain by ranking your top choice number one on your list because schools won’t see how you ranked them.
However if you are applying to a school for which you do not qualify — say you want to apply to a school that accepts only Manhattan residents and you live in Queens — you are wasting a spot on your list if you put it down. Likewise, if a school looks for students with an 85 average or above and your GPA is 70, your chances of getting accepted are slim to none.
What about the schools that tell you, you must put them first, or they won’t consider you? According to the Department of Education, that policy was done away with several years ago. Schools no longer see who lists them first, and they have to come up with their own ranking of students from first to last."

Complementarities in markets and computers

One thing that makes it difficult for markets to clear efficiently is if goods are complements, so that you only want good A if you can also have good B (e.g. you need two licences of adjacent-frequency radio spectrum to carry out your broadband business plan, or you are willing to take job A only if your spouse can get an appropriate job in the same city). If the market isn't designed to take this into account, there might be coordination failures, in which some buyer ends up having paid good money but having gotten only part of what he needs, or in which you and your spouse end up with jobs in different cities. Combinatorial auctions, and labor clearinghouses that accomodate couples, are market designs that seek to avoid these kinds of coordination failures.

The same kind of thing can cause your computer to freeze. If program A needs parts X and Y of your computer memory, and so does program B, and they each lock up one of those components while they try to call the other, you may have to send the children out of the room and reboot. The programming solutions for avoiding this can involve some sort of clearinghouse. Here's an article on the subject from Dr. Dobb's Journal: Lock Options, A compile-time deadlock prevention scheme.

The introduction begins:
"The two major problems in concurrent programs are data races and deadlocks. Races occur when two or more threads are accessing shared memory without proper synchronization. Deadlocks occur when synchronization is based on locking and multiple threads block each other's progress. In a typical deadlock scenario, thread A locks the mutex X, and thread B locks the mutex Y. Now, in lockstep, thread A tries to lock Y and B tries to lock X. Neither can make progress, waiting forever for the other thread to release its lock. The program freezes.
In a sense, data races are the opposite of deadlocks. The former result from not enough synchronization, the latter usually happen when there's too much synchronization and it gets out of hand.
There are sophisticated schemes to prevent races and/or deadlocks, but they either require special language support or strict discipline on the part of programmers. Here I present a solution based on a well-known deadlock-avoidance protocol and show how it can be enforced by the compiler. It can be applied to programs in which the number of locks is fixed and known up front."
HT: Ted Roth

Authors' Registry: Clearinghouse for small payments

How should small fees for copying copyrighted material be collected and distributed? About once a year, I get a communication from The Authors Registry , which works to find authors on whose behalf such fees--presumably collected by the penny in copyshops and libraries--have been collected.

"The Authors Registry is a not-for-profit clearinghouse for payments to authors, receiving royalties from organizations and distributing them to U.S. authors. It was founded in 1995 by a consortium of U.S. authors' organizations: The Authors Guild, The American Society of Journalists & Authors, the Dramatists Guild, and the Association of Authors' Representatives. To date, the Authors Registry has distributed over $8,000,000 to authors in the United States."

They seem to be closely affiliated with the Authors' Licensing & Collecting Society (UK).

"The Authors’ Licensing and Collecting Society (ALCS) represents the interests of all UK writers and aims to ensure writers are fairly compensated for any works that are copied, broadcast or recorded. Writers’ primary rights are protected by contract, but it is the life of the work over the following decades that needs to be monitored and fairly rewarded. It is with secondary rights that copyright has an important role to play in protecting writers and creators from unpaid use and moral abuse of their work. Secondary use ranges from photocopying and repeat broadcast transmission in the UK and overseas to reproduction in journals and repeat use via the internet and digital reproduction."

"Photocopying of books and serials currently accounts for approximately 70% of income. The ALCS together with the Publishers Licensing Society (PLS) has appointed the Copyright Licensing Agency (CLA) to act as its agent to license the photocopying right on its behalf and on behalf of its members on a non-exclusive basis. A small number of CLA licences now include the authority for limited scanning. Public Lending Right ALCS administers German, Austrian, Dutch and French Public Lending Right (PLR) for UK authors, and is in the process of entering into agreements with other European countries where PLR is being incorporated in to national legislation. UK PLR is administered by Public Lending Right based in Stockton-upon-Tees and funded by the Department of Culture, Media and Sport (DCMS). "

The collections are quite small; e.g. my recent statement, which seems to originate in the ALCS looks like this:

PHOTOCOPYING - OVERSEAS Miscellaneous CLA Monies - Inside EU 1.02
NON TITLE SPECIFIC Miscellaneous CLA Monies - UK 40.03
PHOTOCOPYING - OVERSEAS Miscellaneous CLA Monies - Outside EU 15.52
SUBVENTION ON ACCOUNT Miscellaneous CLA Photocopying Fees 7.97
PLS Balancing Payment General CLA Photocopying Fees 2007 - 2008 34.56

Update: for those of you who don't normally click to see comments, the comment below by Jon Baron, the eminent Penn psychologist, is well worth reading...

Medical match policies (NRMP)

The NRMP has some new rules for 2009, which suggests that there have been some new problems (I haven't been involved for a while).

• "Applicants who obtain positions through the Matching Program are prohibited from discussing, interviewing for, or accepting a concurrent year position with another program before a waiver has been granted by the NRMP.
• The deadline for an applicant to request a waiver based on change of specialty is the January 15 prior to the start of training in the matched program.
• Programs shall use the Applicant Match History in the Match Site to determine the match status of any applicant considered for appointment to the program.
• Applicants must provide complete, timely, and accurate information to programs.
• Programs are prohibited from requiring applicants to reveal ranking preferences or the names or identities of programs to which they have or may apply.

Two-career job searches

When a couple needs two career-track jobs, they face a hard problem of coordination with each other and with their prospective employers. If they are in different industries, they need to find a four-way match, between the two of them and two different employers. If they are academics, they can at least try to find two jobs at the same university, but if they are in different disciplines the negotiations will involve different departments (and maybe different schools, i.e. different deans), and so the search and negotiation process can be complex, and can still involve potentially very different timing of searches and hiring.

The Chronicle of Higher Ed has a first person account of one such struggle, that ended successfully with two tenure-track assistant professorships at the same university: Lessons of a Dual Hire.

The (pseudonymous) author writes:"After three years of job searching for me in the geological sciences, and four years for my husband in engineering, we successfully maneuvered this year to find two tenure-track positions at the same university. Here's how it happened."

The article goes on to explain some of the difficulties that were overcome in the most recent, successful job search.

Here are two earlier related posts, both of which touch on my work on making the clearinghouse for new doctors, the National Resident Matching Program, more friendly to couples.

Job market for couples (which concerns law schools hiring of couples); and

Match Day for new doctors, which is specifically about couples who are both seeking jobs as new doctors.

Even the medical clearinghouse doesn't do much to help doctors whose spouses have non-medical careers (or even doctors whose spouses have medical careers with different years of graduation from medical school). Some years ago, I was asked to respond to an essay from a doctor's spouse which suggested that maybe the market would work better without a match, i.e. without any centralized clearinghouse. That essay, and my reply, were published in an online student edition of JAMA that no longer exists, on web pages that are no longer maintained. However I am linking to them below, on the remarkable internet archive also known as the Wayback Machine.

Mismatch, by Betsy Brody, University of Notre Dame

Response to Betsy Brody's "Mismatch" by Alvin E. Roth (both originally in MSJAMA, April 7, 1999.

Rereading my response, I would have written it a bit differently today, but the basic point still seems right. But two-career searches are tough, no doubt about it.

Matching for school choice

School choice has received some extended coverage lately, with articles intended to appeal to a broad audience interested in education issues and mathematics, respectively. Both focus on work that Atila Abdulkadiroglu, Parag Pathak, Tayfun Sonmez and I have had the opportunity to help put into practice (and both are related to ongoing work in CA being spearheaded by Muriel Niederle and Clayton Featherstone).

Over at Education Sector, the September 2009 issue of their feature Ideas at Work covers the new school choice mechanisms for Boston Public Schools and New York City high schools:
MATCHMAKING: ENABLING MANDATORY PUBLIC SCHOOL CHOICE IN NEW YORK AND BOSTON, By Thomas Toch and Chad Aldeman. (It also comes with a 10 minute podcast you can listen to: "A Closer Look at Mandatory School Choice", in which Aldeman interviews me and Atila...)

Joseph Malkevitch has written one of the American Mathematical Society's Monthly Essays, called School Choice.
It's an introduction to Gale and Shapley's basic deferred acceptance algorithm, with a discussion of some applications, with attention paid to the fact that the student proposing algorithm makes it safe for families to reveal their preferences.

Kidney exchange: moving towards a national program

Kidney exchange, which works best with a thick market (lots of patient-donor pairs), is now moving towards experimenting with a national matching program: UNOS Currently Accepting Proposals for Kidney Paired Donation Pilot Program

"United Network for Organ Sharing (UNOS) is developing a national kidney paired donation (KPD) system. UNOS, as the OPTN contractor, will administer this system and it will be open to all OPTN/UNOS-approved transplant programs that perform living donor kidney transplants.
To help prepare for the final implementation, UNOS will begin an interim implementation of the KPD Pilot Program in September 2009. The interim implementation will allow UNOS staff to gain experience with KPD and refine its business processes before rolling out the full system in 2010. We will limit the interim implementation to two to four groups initially.
Any living kidney programs who would like to participate in the interim implementation must submit a proposal... by August 5, 2009.
A complete copy of the Request for Proposal (RFP), including details about who can participate, is available on the UNOS Web site. Learn more now "

School choice in Belgium: update

In an earlier post, I discussed some of the problems in the school choice systems in Belgium, and noted that Estelle Cantillon had organized a conference on the subject in Brussels in January.

Estelle's conference has had some effect. She writes "The parliament of the French-speaking Community will adopt tomorrow a new school enrollment decree. The article says that it will be centralized (coordination among networks), that parents will be asked for their preferences, ... The details will be worked out after the elections in June. " Inscriptions: un nouveau décret, trois mesures

Market for airline flights

As the pricing, scheduling, and seating options grow more complex, booking an airline ticket is looking more like a combinatorial auction. Some travel sites, like TripAdvisor and Kayak.com aim to help with that by displaying more clearly the available bundles of choices: A Clearing in the Fog of Complicated Booking.

" ' We’re bringing clarity to the marketplace, with disclosure up front,” said Bryan Saltzburg, the TripAdvisor general manager for new initiatives. More clarity and disclosure in the marketplace? Let’s hope it’s a trend."

Financial market design: the view from the Fed

Fed chairman Ben Bernanke, in a speech today (March 10) to the Council on Foreign Relations, after speaking of immediate steps to bail out financial institutions, talks about ways in which the financial markets might be redesigned in the longer term.

"At the same time that we are addressing such immediate challenges, it is not too soon for policymakers to begin thinking about the reforms to the financial architecture, broadly conceived, that could help prevent a similar crisis from developing in the future. We must have a strategy that regulates the financial system as a whole, in a holistic way, not just its individual components. In particular, strong and effective regulation and supervision of banking institutions, although necessary for reducing systemic risk, are not sufficient by themselves to achieve this aim.
Today, I would like to talk about four key elements of such a strategy. First, we must address the problem of financial institutions that are deemed too big--or perhaps too interconnected--to fail. Second, we must strengthen what I will call the financial infrastructure--the systems, rules, and conventions that govern trading, payment, clearing, and settlement in financial markets--to ensure that it will perform well under stress. Third, we should review regulatory policies and accounting rules to ensure that they do not induce excessive procyclicality--that is, do not overly magnify the ups and downs in the financial system and the economy. Finally, we should consider whether the creation of an authority specifically charged with monitoring and addressing systemic risks would help protect the system from financial crises like the one we are currently experiencing."

Regarding the financial infrastructure, he mentions among other things that
"To help alleviate counterparty credit concerns, regulators are also encouraging the development of well-regulated and prudently managed central clearing counterparties for OTC trades. Just last week, we approved the application for membership in the Federal Reserve System of ICE Trust, a trust company that proposes to operate as a central counterparty and clearinghouse for CDS transactions. "

On the subject of clearinghouses, he goes on to say
"The Federal Reserve and other authorities also are focusing on enhancing the resilience of the triparty repurchase agreement (repo) market, in which the primary dealers and other major banks and broker-dealers obtain very large amounts of secured financing from money market mutual funds and other short-term, risk-averse sources of funding.
...
it may be worthwhile considering the costs and benefits of a central clearing system for this market, given the magnitude of exposures generated and the vital importance of the market to both dealers and investors. "

His comments on "procyclicality" e.g. on making sure that regulation of capital reserves don't cause banks to cut back lending just when credit needs to be loosened, are also worth reading. His concluding paragraph is a sober look at market design contemplated (as it often must be) in advance of reliable scientific knowledge, but in light of recent experience:

"Financial crises will continue to occur, as they have around the world for literally hundreds of years. Even with the sorts of actions I have outlined here today, it is unrealistic to hope that financial crises can be entirely eliminated, especially while maintaining a dynamic and innovative financial system. Nonetheless, these steps should help make crises less frequent and less virulent, and so contribute to a better functioning national and global economy."