Random popular matchings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Random popular matchings

Full text

Pdf (120 KB)

Source

Electronic Commerce archive
Proceedings of the 7th ACM conference on Electronic commerce table of contents

Ann Arbor, Michigan, USA

Pages: 238 - 242

Year of Publication: 2006

ISBN:1-59593-236-4

Author

Mohammad Mahdian

Microsoft Research, Redmond, WA, USA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 43, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1134707.1134733 What is a DOI?

ABSTRACT

We consider matching markets where a centralized authority must find a matching between the agents on one side of the market, and the items on the other side. Such settings occur, for example, in mail-based DVD rental services such as NetFlix or in some job markets. The objective is to find a popular matching, or a matching that is preferred by a majority of the agents to any other matching. This concept was first defined and studied by Abraham et al. The main drawback of this concept is that popular matchings sometimes do not exist. We partially address this issue in this paper, by proving that in a probabilistic setting where preference lists are drawn at random and the number of items is more than the number of agents by a small multiplicative factor, popular matchings almost surely exist. More precisely, we prove that there is a threshold α ≈ 1.42 such that if the number of items divided by the number of agents exceeds this threshold, then a solution almost always exists. Our proof uses a characterization result by Abraham et al., and a number of tools from the theory of random graphs and phase transitions.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Abraham, N. Chen, V. Kumar, and V.S. Mirrokni. Assignment problems in rental markets. 2006.
	2	David J. Abraham , Robert W. Irving , Telikepalli Kavitha , Kurt Mehlhorn, Popular matchings, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	3	D. J. Abraham and T. Kavitha. Voting paths. manuscript, 2005.
	4	N. Alon and J. Spencer. The probabilistic method. John Wiley & Sons, 2000.
	5	B. Bollobàs. Random Graphs. Cambridge University Press, 2001.
	6	D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9--15, 1962.
	7	P. Gardenfors. Match making: assignment based on bilateral preferences. Behaviourial Sciences, 20:166--173, 1975.
	8	Nicole Immorlica , Mohammad Mahdian, Marriage, honesty, and stability, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	9	D. E. Knuth, R. Motwani, and B. Pittel. Stable husbands. Random Structures and Algorithms, 1:1--14, 1990.
	10	J. Mestre. Weighted popular matchings. manuscript, 2005.
	11	A. Roth, T. Sonmez, and M. U. Unv er. Kidney exchange. Quarterly Journal of Economics, 119(2):457--488, May 2004.
	12	A. E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. forthcoming in Econometrica.
	13	A.E. Roth and E. Peranson. The redesign of the matching market for american physicians: Some engineering aspects of economic design. American Economic Review, 89:748--780, 1999.
	14	L. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:23--28, 1974.