Fair Division with Social Impact

Michele Flammini, Gianluigi Greco, Giovanna Varricchio · 2024

Read Fair Division with Social Impact by Michele Flammini, Gianluigi Greco, Giovanna Varricchio (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-14818.txt.

Introduction

Michele Flammini, Gianluigi Greco, and Giovanna Varricchio study fair splits of goods when each gift also affects society in 2024. Each person holds two scores for a good: private worth and social worth. The aim is a fair split for the people that keeps society glad. Social gladness is summed across all gifts.

The authors prove tight limits on what is possible. No method can promise better than a weak share of the social best while staying fair. The block is that agents ignore their own social effect. When agents are made socially aware, new fairness rules can align the two goals. The paper maps where fairness and welfare can meet.

Catalog record

CREATORMichele Flammini, Gianluigi Greco, Giovanna Varricchio
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-14818

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fair Division with Social Impact Michele Flammini, Gianluigi Greco, Giovanna Varricchio Abstract In this paper, we consider the problem of fair division of indivisible goods when the allocation of goods impacts society. Specifically, we introduce a second valuation function for each agent, determining the social impact of allocating a good to the agent. Such impact is considered desirable for the society – the higher, the better. Our goal is to understand how to allocate goods fairly from the agents’ perspective while maintaining society as happy as possible. To this end, we measure the impact on society using the utilitarian social welfare and provide both possibility and impossibility results. Our findings reveal that achieving good approximations, better than linear in the number of agents, is not possible while ensuring fairness to the agents. These impossibility results can be attributed to the fact that agents are completely unconscious of their social impact. Consequently, we explore scenarios where agents are socially aware, by introducing related fairness notions, and demonstrate that an appropriate definition of fairness aligns with the goal of maximizing the social objective. 1 Introduction Fair division is a fundamental research area at the intersection of economics and computer science. In the last decade, it turned out to be a particularly active field due to its applications to several real-world contexts. It focuses on distributing resources (goods) among individuals (agents) in a fair manner according to their valuations. To achieve fairness, various criteria have been studied, including envy-freeness ( \mathsf{EF} ) [ 20 ] , where every agent weakly prefers her bundle over the bundle received by any other, and proportionality ( \mathsf{PROP} ) [ 25 ] , where every agent values her bundle at least as much as her proportional share, that is, the value she attributes to the whole set of goods normalized by the number of agents. Unfortunately, in indivisible settings, \mathsf{EF} and \mathsf{PROP} allocations do not always exist. Consequently, several relaxations have been considered. These include, but are not limited to, the up to one [ 16 ] , up to any [ 18 ] , epistemic [ 2 , 17 ] , and randomized [ 3 ] variants of \mathsf{EF} , \mathsf{PROP} , and related notions. The fair division model has also been extended to deal with more complex scenarios, e.g., endowing agents with entitlements [ 27 , 19 , 4 , 21 ] or introducing additional constraints [ 12 , 8 , 13 ] . In most of this literature, the focus has been put on achieving fairness for the involved agents, possibly subject to efficiency, without considering any kind of externality. However, there are many scenarios in which allocating resources has an impact on society. We can imagine, for example, there are some green strategies that the government must assign to companies. A company will profit from implementing the strategy (as companies more sensitive to green aspects are increasingly appealing to customers), while the implementation will positively impact society by reducing emissions. Companies judge the outcome based solely on the profit they and other companies can attain, whereas society aims to maximize the overall reduction of emissions. With this paper, we expand the scope of fair division of indivisible goods incorporating the concept of social impact. Our goal is twofold: To ensure fairness among agents and guarantee a high social impact. Our Contribution. Price of \mathsf{EF}1 \mathsf{EFX} \mathsf{EF}2 \mathsf{PROP}1 epistemic \mathsf{EF}1 UB O(n^{2}) (Thm. 4 ) n^{\star} (Thm. 3 ) n (Thm. 5 ) n (Thm. 6 ) n (Thm. 6 ) n^{\dagger} (Thm. 2 ) LB n (Thm. 1 ) n (Cor. 1 ) n-1 (Thm. 1 ) n (Cor. 2 ) n (Cor. 2 ) Table 1: Lower (LB) and upper (UB) bounds to the PoF w.r.t. the maximum utilitarian social impact. The results marked with † and ⋆ hold for ordered and identical valuations, respectively. All the LBs have been proven even under identical valuations. We refer to the preliminaries for the formal definition of the considered fairness criteria. In this work, we aim at determining the loss in efficiency (expressed by the utilitarian welfare w.r.t. the social impact of agents, i.e., the sum of the social impact of agents) while pursuing fairness. In particular, we estimate the Price of Fairness (PoF), that is, the worst-case ratio between the value of the maximum utilitarian welfare and the maximum utilitarian welfare achievable by a fair solution. Besides determining suitable bounds for several fairness notions, we also provide efficient algorithms for computing the corresponding approximately optimal and fair allocations. An overview of our results for n agents is given in Table 1 . For all the fairness notions we considered, an approximation better than linear in the number of agents is not possible. This can be attributed to the fact that agents are unconscious of their social impact. We therefore investigate which kind of consciousness on the agents’ side allows the existence of fair and optimal outcomes. To this end, we introduce the notion of socially aware envy-freeness ( \mathsf{sEF} ) and establish that an allocation maximizing the utilitarian social impact and \mathsf{sEF} up to one good always exists. Due to space constraints, we refer to the full paper for the details. Related Work. The literature on fair division is wide; we refer the interested reader to some recent surveys [ 1 , 26 , 27 ] . We next discuss the work directly related to our. The goal of achieving fairness while maximizing the utilitarian welfare has been extensively studied when s_{i}=v_{i} . Allocations having maximum agents’ utilitarian social welfare do not necessarily guarantee fairness, even in divisible settings. For this reason, the PoF with respect to such a welfare has been extensively studied [ 24 , 7 , 10 , 22 ] . In this stream of research, several fairness notions as well as restrictions on the valuations have been exploited. Furthermore, the problem of determining whether there exists a fair allocation that is also socially optimal has been considered in [ 6 , 14 ] . In a nutshell, they show that for all the considered criteria, both determining the existence of a maximum utilitarian allocation which is also fair and computing an allocation that maximizes the utilitarian welfare among fair solutions are strongly NP-hard problems. The idea of employing two distinct valuation functions for each agent has been examined in prior research [ 15 ] albeit from a different viewpoint. In this approach, one valuation function captures the agent’s preferences while the other represents the allocator’s interpretation of the agent’s preferences – what the allocator thinks a bundle of goods should value for a certain agent. The main objective in [ 15 ] was to achieve fairness in both the agents’ and the allocator’s perspectives. In our model, society does not care if the allocation is fair according to the social impact functions; rather, society would like the allocation to maximize its own interests. In [ 15 ] , the authors briefly discuss the problem of maximizing the allocator’s utilitarian welfare by providing a simple m -approximation algorithm, where m is the number of goods. With our contribution, we improve this result achieving an approximation polynomial in the number of

Read the complete text