CDAM: Computational, Discrete and Applicable Mathematics@LSE

CDAM Research Report, LSE-CDAM-2007-32

December 2007

Equilibria of two-sided matching games

Steve Alpern and Ioanna Katrantzi

Problems of matching have long been studied in the operations research literature (assignment problem, secretary problem, stable marriage problem). All of these consider a centralized mechanism whereby a single decision maker chooses a complete matching which optimizes some criterion. This paper analyzes a more realistic scenario in which members of the two groups (buyers-sellers, employers-workers, males-females) randomly meet each other in pairs (interviews, dates) over time and form couples if there is mutual agreement to do so. We assume members of each group have common preferences over members of the other group. Generalizing an earlier model of Alpern and Reyniers (2005), we assume that one group (called males) is r times larger than the other, r > 1. Thus all females, but only 1/r of the males, end up matched. Unmatched males have negative utility -c. We analyze equilbria of this matching game, depending on the parameters r and c. In a region of (r,c) space with multiple equilibria, we compare these, and analyze their `efficiency' in several respects. This analysis should prove useful for designers of matching mechanisms when information about individuals is not available centrally but only statistical properties of the groups are known.

A PDF file (516 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2007-32, together with your name and postal address to:

CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk