Maximin share guarantee for goods with positive externalities

Masoud Seddighin (), Hamed Saleh () and Mohammad Ghodsi ()
Additional contact information
Masoud Seddighin: Institute for Research in Fundamental Sciences (IPM)
Hamed Saleh: University of Maryland
Mohammad Ghodsi: Institute for Research in Fundamental Sciences (IPM)

Social Choice and Welfare, 2021, vol. 56, issue 2, No 4, 324 pages

Abstract: Abstract One of the important yet insufficiently studied subjects in fair allocation is the externality effect among agents. For a resource allocation problem, externalities imply that the share allocated to an agent may affect the utilities of other agents. In this paper, we conduct a study of fair allocation of indivisible goods with positive externalities. Inspired by the models in the context of network diffusion, we present a simple and natural model, namely network externalities, to capture the externalities. To evaluate fairness in the network externalities model, we generalize the idea behind the notion of maximin-share ( $$\mathsf {MMS}$$ MMS ) to achieve a new criterion, namely, extended-maximin-share ( $$\mathsf {EMMS}$$ EMMS ). Next, we consider two problems concerning our model. First, we discuss the computational aspects of finding the value of $$\mathsf {EMMS}$$ EMMS for every agent. For this, we introduce a generalized form of partitioning problem that includes many famous partitioning problems such as maximin, minimax, and leximin. We further show that a 1/2-approximation algorithm exists for this partitioning problem. Next, we investigate approximate $$\mathsf {EMMS}$$ EMMS allocations, i.e., allocations that guarantee each agent a utility of at least a fraction of his extended-maximin-share. We show that under a natural assumption that the agents are $$\alpha$$ α -self-reliant, an $$\alpha /2$$ α / 2 - $$\mathsf {EMMS}$$ EMMS allocation always exists. This, combined with the former result yields a polynomial-time $$\alpha /4$$ α / 4 - $$\mathsf {EMMS}$$ EMMS allocation algorithm.

Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00355-020-01278-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:sochwe:v:56:y:2021:i:2:d:10.1007_s00355-020-01278-8

Ordering information: This journal article can be ordered from
http://www.springer. ... c+theory/journal/355

DOI: 10.1007/s00355-020-01278-8

Access Statistics for this article

Social Choice and Welfare is currently edited by Bhaskar Dutta, Marc Fleurbaey, Elizabeth Maggie Penn and Clemens Puppe

More articles in Social Choice and Welfare from Springer, The Society for Social Choice and Welfare Contact information at EDIRC.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().