[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2207.11322.html
   My bibliography  Save this paper

Greedy Allocations and Equitable Matchings

Author

Listed:
  • Quitz'e Valenzuela-Stookey
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.

Suggested Citation

  • Quitz'e Valenzuela-Stookey, 2022. "Greedy Allocations and Equitable Matchings," Papers 2207.11322, arXiv.org, revised Oct 2022.
    • Handle: RePEc:arx:papers:2207.11322
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2207.11322
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    2. Matthews, Steven A, 1984. "On the Implementability of Reduced Form Auctions," Econometrica, Econometric Society, vol. 52(6), pages 1519-1522, November.
    3. Bocar Ba & Patrick Bayer & Nayoung Rim & Roman Rivera & Modibo Sidibé, 2021. "Police Officer Assignment and Neighborhood Crime," NBER Working Papers 29243, National Bureau of Economic Research, Inc.
    4. Andreas Kleiner & Benny Moldovanu & Philipp Strack, 2021. "Extreme Points and Majorization: Economic Applications," Econometrica, Econometric Society, vol. 89(4), pages 1557-1593, July.
    5. Mierendorff, Konrad, 2011. "Asymmetric reduced form Auctions," Economics Letters, Elsevier, vol. 110(1), pages 41-44, January.
    6. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    7. Yeon‐Koo Che & Jinwoo Kim & Konrad Mierendorff, 2013. "Generalized Reduced‐Form Auctions: A Network‐Flow Approach," Econometrica, Econometric Society, vol. 81(6), pages 2487-2520, November.
    8. Roth, Alvin E., 1985. "The college admissions problem is not equivalent to the marriage problem," Journal of Economic Theory, Elsevier, vol. 36(2), pages 277-288, August.
    9. Kim Border, 2007. "Reduced Form Auctions Revisited," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 31(1), pages 167-181, April.
    10. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    11. Eric Budish & Yeon-Koo Che & Fuhito Kojima & Paul Milgrom, 2013. "Designing Random Allocation Mechanisms: Theory and Applications," American Economic Review, American Economic Association, vol. 103(2), pages 585-623, April.
    12. , Emin & , Bumin & , Ali, 2013. "Effective affirmative action in school choice," Theoretical Economics, Econometric Society, vol. 8(2), May.
    13. Maskin, Eric S & Riley, John G, 1984. "Optimal Auctions with Risk Averse Buyers," Econometrica, Econometric Society, vol. 52(6), pages 1473-1518, November.
    14. Rochet, Jean-Charles, 1987. "A necessary and sufficient condition for rationalizability in a quasi-linear context," Journal of Mathematical Economics, Elsevier, vol. 16(2), pages 191-200, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xu Lang, 2022. "Reduced-form budget allocation with multiple public alternatives," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(2), pages 335-359, August.
    2. Erya Yang, 2021. "Reduced-form mechanism design and ex post fairness constraints," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 9(2), pages 269-293, October.
    3. Xu Lang & Zaifu Yang, 2023. "Reduced-Form Allocations for Multiple Indivisible Objects under Constraints," Discussion Papers 23/02, Department of Economics, University of York.
    4. Saeed Alaei & Hu Fu & Nima Haghpanah & Jason Hartline & Azarakhsh Malekian, 2019. "Efficient Computation of Optimal Auctions via Reduced Forms," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 1058-1086, August.
    5. Xu Lang, 2022. "Reduced-Form Allocations with Complementarity: A 2-Person Case," Papers 2202.06245, arXiv.org, revised Feb 2022.
    6. Goeree, Jacob K. & Kushnir, Alexey, 2016. "Reduced form implementation for environments with value interdependencies," Games and Economic Behavior, Elsevier, vol. 99(C), pages 250-256.
    7. Li, Yunan, 2019. "Efficient mechanisms with information acquisition," Journal of Economic Theory, Elsevier, vol. 182(C), pages 279-328.
    8. Sergiu Hart & Philip J. Reny, 2015. "Implementation of reduced form mechanisms: a simple approach and a new characterization," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 3(1), pages 1-8, April.
    9. Hafalir, Isa E. & Kojima, Fuhito & Yenmez, M. Bumin, 2022. "Interdistrict school choice: A theory of student assignment," Journal of Economic Theory, Elsevier, vol. 201(C).
    10. Xu Lang & Zaifu Yang, 2021. "Reduced-Form Allocations for Multiple Indivisible Objects under Constraints: A Revision," Discussion Papers 21/05, Department of Economics, University of York.
    11. Pai, Mallesh M. & Vohra, Rakesh, 2014. "Optimal auctions with financially constrained buyers," Journal of Economic Theory, Elsevier, vol. 150(C), pages 383-425.
    12. Yunan Li, 2017. "Efficient Mechanisms with Information Acquisition," PIER Working Paper Archive 16-007, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 23 Jun 2017.
    13. Xu Lang, 2023. "A Belief-Based Characterization of Reduced-Form Auctions," Papers 2307.04070, arXiv.org.
    14. Xu Lang & Zaifu Yang, 2021. "Reduced-Form Allocations for Multiple Indivisible Objects under Constraints," Discussion Papers 21/04, Department of Economics, University of York.
    15. Mierendorff, Konrad, 2016. "Optimal dynamic mechanism design with deadlines," Journal of Economic Theory, Elsevier, vol. 161(C), pages 190-222.
    16. Mierendorff, Konrad, 2011. "Asymmetric reduced form Auctions," Economics Letters, Elsevier, vol. 110(1), pages 41-44, January.
    17. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    18. Yunan Li, 2017. "Mechanism Design with Costly Verification and Limited Punishments, Third Version," PIER Working Paper Archive 16-009, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 28 Sep 2017.
    19. Andreas Kleiner & Benny Moldovanu & Philipp Strack, 2021. "Extreme Points and Majorization: Economic Applications," Econometrica, Econometric Society, vol. 89(4), pages 1557-1593, July.
    20. Li, Yunan, 2020. "Mechanism design with costly verification and limited punishments," Journal of Economic Theory, Elsevier, vol. 186(C).

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2207.11322. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.