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 / 226 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 seddighin.masood@gmail.com Hamed Saleh hameelas@gmail.com Mohammad Ghodsi ghodsi@sharif.edu 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
