Maximin share guarantee for goods with positive externalities
- PDF / 2,152,133 Bytes
- 34 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 222 Views
Maximin share guarantee for goods with positive externalities Masoud Seddighin1 · Hamed Saleh2 · Mohammad Ghodsi1,3 Received: 24 June 2019 / Accepted: 12 August 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
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 ( 𝖬𝖬𝖲 ) to achieve a new criterion, namely, extended-maximin-share ( 𝖤𝖬𝖬𝖲 ). Next, we consider two problems concerning our model. First, we discuss the computational aspects of finding the value of 𝖤𝖬𝖬𝖲 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 𝖤𝖬𝖬𝖲 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 𝛼-self-reliant, an 𝛼∕2 -𝖤𝖬𝖬𝖲 allocation always exists. This, combined with the former result yields a polynomial-time 𝛼∕4-𝖤𝖬𝖬𝖲 allocation algorithm. A version of this work is accepted in TheWebConf (WWW) 2019. * Masoud Seddighin [email protected] Hamed Saleh [email protected] Mohammad Ghodsi [email protected] 1
School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
2
University of Maryland, College Park, USA
3
Sharif University of Technology, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
13
Vol.:(0123456789)
M. Seddighin et al.
1 Introduction Consider a scenario where there is a collection of m indivisible goods that are to be divided amongst n agents. For a properly chosen notion of fairness, we desire our division to be fair. Motivating examples are dividing the inherited wealth among heirs, dividing assets of a bankrupt company among creditors, divorce settlements, task assignments, etc. Fair division has been a central problem in Economic Theory. This subject was first introduced in 1948 by Steinhaus (1948). The primary model used the metaphor of cake to represent a single divisible resource that must be divided among a set of agents. Proportionality is one of the most well-studied notions defined to evaluate the fairness of a cake division protocol. An allocation of a cake to n agents is proportional if every agent feels that his allocated share is worth at least 1/n of the entire cake. Despite many positive re
Data Loading...
