Greedy Allocations and Equitable Matchings

Quitz\'e Valenzuela-Stookey

Papers from arXiv.org

Abstract: I provide a novel approach to characterizing the set of interim realizable allocations, in the spirit of Matthews (1984) and Border (1991). The approach allows me to identify precisely why exact characterizations are difficult to obtain in some settings. The main results of the paper then show how to adapt the approach in order to obtain approximate characterizations of the interim realizable set in such settings. As an application, I study multi-item allocation problems when agents have capacity constraints. I identify necessary conditions for interim realizability, and show that these conditions are sufficient for realizability when the interim allocation in question is scaled by 1/2. I then characterize a subset of the realizable polytope which contains all such scaled allocations. This polytope is generated by a majorization relationship between the scaled interim allocations and allocations induced by a certain ``greedy algorithm''. I use these results to study mechanism design with equity concerns and model ambiguity. I also relate optimal mechanisms to the commonly used deferred acceptance and serial dictatorship matching algorithms. For example, I provide conditions on the principal's objective such that by carefully choosing school priorities and running deferred acceptance, the principal can guarantee at least half of the optimal (full information) payoff.

Date: 2022-07, Revised 2022-10
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2207.11322 Latest version (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:arx:papers:2207.11322

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().