IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1909.10502.html
   My bibliography  Save this paper

Weighted Envy-Freeness in Indivisible Item Allocation

Author

Listed:
  • Mithun Chakraborty
  • Ayumi Igarashi
  • Warut Suksompong
  • Yair Zick

Abstract

We introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1): strong, where envy can be eliminated by removing an item from the envied agent's bundle, and weak, where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent's bundle in the envying agent's bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.

Suggested Citation

  • Mithun Chakraborty & Ayumi Igarashi & Warut Suksompong & Yair Zick, 2019. "Weighted Envy-Freeness in Indivisible Item Allocation," Papers 1909.10502, arXiv.org, revised Mar 2021.
  • Handle: RePEc:arx:papers:1909.10502
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    2. Mas-Colell, Andreu & Whinston, Michael D. & Green, Jerry R., 1995. "Microeconomic Theory," OUP Catalogue, Oxford University Press, number 9780195102680.
    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. Wright, Austin L. & Sonin, Konstantin & Driscoll, Jesse & Wilson, Jarnickae, 2020. "Poverty and economic dislocation reduce compliance with COVID-19 shelter-in-place protocols," Journal of Economic Behavior & Organization, Elsevier, vol. 180(C), pages 544-554.
    2. Jolian McHardy & Michael Reynolds & Stephen Trotter, 2012. "The Stackelberg Model as a Partial Solution to the Problem of Pricing in a Network," Working Paper series 19_12, Rimini Centre for Economic Analysis.
    3. Janvier D. Nkurunziza, 2005. "Reputation and Credit without Collateral in Africa`s Formal Banking," Economics Series Working Papers WPS/2005-02, University of Oxford, Department of Economics.
    4. Pizer, William A. & Kopp, Raymond, 2005. "Calculating the Costs of Environmental Regulation," Handbook of Environmental Economics, in: K. G. Mäler & J. R. Vincent (ed.), Handbook of Environmental Economics, edition 1, volume 3, chapter 25, pages 1307-1351, Elsevier.
    5. Houba, Harold & van der Laan, Gerard & Zeng, Yuyu, 2014. "Asymmetric Nash Solutions in the River Sharing Problem," Strategic Behavior and the Environment, now publishers, vol. 4(4), pages 321-360, December.
    6. Stephanie Rosenkranz & Patrick W. Schmitz, 2007. "Can Coasean Bargaining Justify Pigouvian Taxation?," Economica, London School of Economics and Political Science, vol. 74(296), pages 573-585, November.
    7. Mackowiak, Piotr, 2010. "The existence of equilibrium without fixed-point arguments," Journal of Mathematical Economics, Elsevier, vol. 46(6), pages 1194-1199, November.
    8. Vadim Borokhov, 2014. "On the properties of nodal price response matrix in electricity markets," Papers 1404.3678, arXiv.org, revised Jan 2015.
    9. Daniel Sutter & Daniel J. Smith, 2017. "Coordination in disaster: Nonprice learning and the allocation of resources after natural disasters," The Review of Austrian Economics, Springer;Society for the Development of Austrian Economics, vol. 30(4), pages 469-492, December.
    10. Aad Ruiter, 2020. "Approximating Walrasian Equilibria," Computational Economics, Springer;Society for Computational Economics, vol. 55(2), pages 577-596, February.
    11. Hanming Fang & Peter Norman, 2014. "Toward an efficiency rationale for the public provision of private goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 375-408, June.
    12. Arnott, Richard & Hochman, Oded & Rausser, Gordon C., 2008. "Pollution and land use: Optimum and decentralization," Journal of Urban Economics, Elsevier, vol. 64(2), pages 390-407, September.
    13. Erlanson, Albin & Szwagrzak, Karol, 2013. "Strategy-Proof Package Assignment," Working Papers 2013:43, Lund University, Department of Economics.
    14. Dirk Bergemann & Stephen Morris, 2019. "Information Design: A Unified Perspective," Journal of Economic Literature, American Economic Association, vol. 57(1), pages 44-95, March.
    15. David Wilson & John Gowdy, 2015. "Human ultrasociality and the invisible hand: foundational developments in evolutionary science alter a foundational concept in economics," Journal of Bioeconomics, Springer, vol. 17(1), pages 37-52, April.
    16. Wei-Bin Zhang, 2015. "A Portfolio Equilibrium Model of Gold and Capital in an Integrated Walrasian General Equilibrium and Neoclassical Growth Theory," International Journal of Economics and Empirical Research (IJEER), The Economics and Social Development Organization (TESDO), vol. 3(12), pages 616-627, December.
    17. Gintis, Herbert, 2004. "Modeling cooperation among self-interested agents: a critique," Journal of Behavioral and Experimental Economics (formerly The Journal of Socio-Economics), Elsevier, vol. 33(6), pages 695-714, December.
    18. Elie Gray & André Grimaud, 2016. "The Lindahl equilibrium in Schumpeterian growth models," Journal of Evolutionary Economics, Springer, vol. 26(1), pages 101-142, March.
    19. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press, vol. 33(4), pages 541-571.
    20. Mendoza, Guillermo A. & Prabhu, Ravi, 2006. "Participatory modeling and analysis for sustainable forest management: Overview of soft system dynamics models and applications," Forest Policy and Economics, Elsevier, vol. 9(2), pages 179-196, November.

    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:1909.10502. See general information about how to correct material in RePEc.

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

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.