One-Sided Matching with Limited Complementarities

Thanh Nguyen (), Ahmad Peivandi () and Rakesh Vohra ()
Additional contact information
Thanh Nguyen: Krannert School of Management, Purdue University
Ahmad Peivandi: Department of Economics, Northwestern University
Rakesh Vohra: Department of Economics, University of Pennsylvania

PIER Working Paper Archive from Penn Institute for Economic Research, Department of Economics, University of Pennsylvania

Abstract: The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, of computing resources like CPU time, memory and disk space to computing tasks and the truck loads of food to food banks. In these settings the complementarities in preferences are small compared with the size of the market. We exploit this to design mechanisms satisfying efficiency, envy-freeness and asymptotic strategy-proofness. Informally, we assume that agents do not want bundles that are too large. There will be a parameter k such that the marginal utility of any item relative to a bundle of size k or larger is zero. We call such preferences k-demand preferences. Given this parameter we show how to represent probability shares over bundles as lotteries over approximately (deterministic) feasible integer allocations. The degree of infeasibility in these integer allocations will be controlled by the parameter k. In particular, ex-post, no good is over allocated by at most k -1 units.

Keywords: Fair Allocation; Indivisible Goods (search for similar items in EconPapers)
JEL-codes: C61 D47 D63 (search for similar items in EconPapers)
Pages: 37 pages
Date: 2014-03-01
New Economics Papers: this item is included in nep-gth and nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://economics.sas.upenn.edu/sites/default/files/filevault/14-030.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pen:papers:14-030

Access Statistics for this paper

More papers in PIER Working Paper Archive from Penn Institute for Economic Research, Department of Economics, University of Pennsylvania 133 South 36th Street, Philadelphia, PA 19104. Contact information at EDIRC.
Bibliographic data for series maintained by Administrator ().