We consider multi-agent item allocation problems where we differentiate between items that are good for all agents or bad for all agents. For this model with social items, we study six new properties that relax economic equity: three of them are based on the idea of removing one good or removing one bad; the other three of them are based on the idea of removing one good or duplicating one bad. We also give solutions for returning allocations of limited agent pairwise inequality, whenever agents have additive preferences for the items. Some of these solutions run in polynomial time, which makes them practical as opposed to standard intractable approaches such as minimizing the Gini index.
resource allocation [1, 2, 3]. An extremely popular case Reducing inequalities and ensuring no one is left behind for allocation is when the resource is represented by a are integral to achieving the United Nations’ Sustainable collection of indivisible items. This is an appealing case Development Goals. Inequality within and among coun- when studying inequalities because most possessions in tries is a persistent cause for concern. Despite some pos- our life are indivisible. For example, if the neighbour itive signs toward reducing inequality in some dimen- has a car and we do not, we might be jealous of them. sions, such as reducing relative income inequality in some Furthermore, if they have a house and a car, our jealousy countries and preferential trade status benefiting lower- increases, but not as much as when we also have a house income countries, inequality still persists. Inequalities or a car. Perceiving lower inequalities might, therefore, are also deepening for vulnerable populations in coun- relate to how comfortable we feel living in a given neightries with weaker health systems and those facing existing bourhood, district, and city and, consequently, to how humanitarian crises. Refugees and migrants, as well as well we perform in society. That is, reducing inequalities indigenous peoples, older persons, people with disabil- improves our well-being in the community! ities, and children, are particularly at risk of being left Dividing private items is, however, not the only applicabehind. There are many obstacles when it comes to reduc- tion in which we may want to reduce inequalities. Often, ing inequalities. For example, we often do not perceive we may need to decide how to divide public (social) items inequalities of others as a problem but rather as an oppor- among agents. For instance, consider two friends, say Antunity for our own development. Also, we are often not ton and Bob, deciding what film to watch. Both of them fully aware of the main factors causing inequalities and obviously like films if they are deciding that. However, let the current mechanisms reducing inequalities, simply due us suppose that Anton prefers action films, whereas Bob to the fact that these factors and mechanisms are not as prefers thriller films. When there is only a single decision transparent and explainable as we would like them to be. to make, Nash [4] proposed maximizing the Nash welfare As a consequence, we are often part of the problem and as an elegant solution to arrive at a mutually agreeable not part of the solution, thus compensating regularly for decision. However, in this single-decision setting, it might the successful efforts made by the United Nations in the be impossible to make both Anton and Bob happy. By direction of reducing inequalities. Indeed, we agree that it comparison, if we could get to make multiple decisions is hard to imagine a world without inequalities. But, can for multiple items, we might be able to reach a consensus we imagine a world where inequalities are limited? by making sure that both Anton and Bob are happy with at least some of the decisions. For example, if they were to AAAI 2023 Spring Symposia, Socially Responsible AI for Well-being, follow their movie with a beer, then Bob might be willing March 27–29, 2023, USA to agree to watch an action movie if he got to pick his *$Comrraerstipno.anldeiknsganadurthoovr@.fu-berlin.de (M. D. Aleksandrov) favorite bar, and Anton might accept this compromise. https://martofena.github.io/ (M. D. Aleksandrov) Likewise, Anton might be willing to agree to watch a 0000-0003-0047-1235 (M. D. Aleksandrov) thriller movie if he got to pick his favorite bar, and Bob © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License might accept this compromise.
CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutiRon 4W.0Iontrekrnsathioonapl(CPCrBoYc4e.0e)d.ings (CEUR-WS.org)
Mathematically, this scenario can be modelled as hav- Eliminating inequalities is a special case of reducing
ining two indivisible items (a cinema location and a bar equalities. An appealing axiomatic property that encodes
location) and two agents (Anton and Bob) who have addi- the absence of inequalities is jealousy freeness [
Indivisible social items appear naturally in a number of real-world applications: (a) allocating research funds and their associated responsibilities among multiple re- 2. Limiting Inequalities search positions; (b) allocating paper tasks such as writing and editing, and their associated publication cred- We propose three new relaxations of jealousy freeness. An its among researchers; (c) sharing credit, rent, and fare allocation is Jealousy-Free Up To Every Removed Item (http://www.spliddit.org/); (d) healthcare decisions regard- (JFX0) if it is jealousy-free and, otherwise, an agent who ing utility-attractiveness of therapies of varying effective- is jealous becomes jealousy-free of another agent, after ness and societal benefit. any bad is removed from the jealous agent’s bundle or any
In such applications, after the agents submit their utili- good is removed from the jealousy-free agent’s bundle.
ties, a (central) planner decides on a complete allocation Also, an allocation is Jealousy-Free Up To Every
Nonthat gives each item to an agent. Two common tasks of zero valued Removed Item (JFX) whenever the removed
the planner are to compute allocations that minimise envy item is non-zero valued, and Jealousy-Free Up To Some
[
These properties relate to limiting inequalities, which is Example 1. Let us consider agents 1, 2, and 3 with utility
a task considered in economics for more than one hundred profiles (−, −, −) , (−, −, −) , and (−1, −1, −1) ,
years [
Gourvès et al. [
in static domains like ours where the entire resource is 4. Comparing Properties ifxed and available at one point in time; in dynamic domains where, for each out of multiple points in time, we We next compare the triple DJFX0, DJFX, and DJF1, and have a static problem; in repeated domains such as althe triple JFX0, JFX, and JF1. For example, in general, locating resources in multiple rounds. This work offers each property limits from above the absolute inequality therefore a stepping stone for a better understanding of pairwise difference between agent utilities in an alloca- limiting inequalities in these domains. For example, in tion. The limit is the maximum absolute agent utility static domains, such allocations limit the agent pairwise for an item. So, we might be indifferent between the difference in utility levels. Also, in dynamic domains, triples. But, in Example 1, we show that the former triple there are multiple points in time and, at each next point, might be preferred to the latter triple. Indeed, achieving we could bias the computation of allocations of the current DJFX0, DJFX, and DJF1 might optimise various welfares resources with respect to (w.r.t.) the (aggregated) utility whereas achieving JFX0, JFX, and JF1 might fail to do so. levels agents received in the previous points in time. FiThe planner could use this as a secondary criterion when nally, in repeated domains, we can also do that w.r.t. the deciding which triple of properties to use in practice. utility levels agents received in the previous rounds.
7.1. Model Definition 3. (DJF1) is DJF1 if, ∀, ∈ [] s.t. agent is not DJFX of agent , (1) ∃ ∈ s.t. () ≥ () + () or (2) ∃ ∈ s.t. () ≥ () − (). 7.2. Properties We look at instances with [] = {1, . . . , } of ∈ N≥2 agents and [] = {1, . . . , } of ∈ N≥1 indivisible A DJFX0 allocation satisfies further DJFX, i.e. DJFX 0 items. We let each ∈ [] use a utility function : is stronger than DJFX. Also, DJFX is stronger than DJF1. 2[] → R. We let (∅) = 0 hold. We write () for These relations follow directly by the definitions of these ({}). For ⊆ [], we say that ( ) is additive axiomatic concepts. iff ( ) = ∑︀∈ (). The utilities are identical iff, In a similar fashion, we define JFX 0, JFX, and JF1 for each ∈ [], () = () for each , ∈ []. We for a given allocation, where () ≥ () + () may write () in this case. Further, let us consider agent in each of the definitions of DJFX 0, DJFX, and DJF1 is ∈ [] and item ∈ []. We say that is good for if replaced with () − () ≥ (), respectively. () ≥ 0 holds. We refer to as pure good whenever JFX0 is stronger than JFX and JFX is stronger than JF1. () > 0 holds for each ∈ []. Similarly, we say that baids bwahdenfoerverif(()<)≤ 0 h0ohlodlsdfso.rWeaecrhefer∈to[].aWspeulreet D eifinsitnioont j4e.alo(uJsFyX-f0re)eoifs aJFgXen0t if,,∀(1,)⋆ ∈∀[]∈s.t.agesn.tt. [] be partitioned into (social) goods and (social) bads, () ≤ () − (): () − () ≥ () respectively = { ∈ []|∀ ∈ [] : () ≥ 0} and and (2) ∀ ∈ s.t. () ≥ () − (): = { ∈ []|∀ ∈ [] : () ≤ 0}. A complete () ≥ () − (). allocation = (1, . . . , ) is such that (1) is the bundle of agent ∈ [], (2) ⋃︀∈[] = [] holds, and (3) ∩ = ∅ holds for each , ∈ [] with ̸= .
Definition 5. (JFX) is JFX if, ∀, ∈ [] s.t. agent is not JFX0 of agent , (1)⋆ ∀ ∈ s.t. () < () − (): () − () ≥ () and (2) ∀ ∈ s.t. () > () − (): () ≥ () − ().
and . One of them is jealousy-free of the other one, say . Some of our notions rely on the idea of decreasing the utility of the agent who is jealousy-free, i.e. the ’s utility.
Thus, agent is DJFX0 of agent whenever ’s utility is at least as much as ’s utility, after duplicating each individual bad from ’s bundle into ’s bundle and removing each individual good from ’s bundle.
Definition 1. (DJFX0) is DJFX0 if, ∀, ∈ [] s.t. agent is not jealousy-free of agent , (1) ∀ ∈ s.t. () ≤ () − (): () ≥ () + () and (2) ∀ ∈ s.t. () ≥ () − (): () ≥ () − ().
Definition 2. (DJFX) is DJFX if, ∀, ∈ [] s.t. agent is not DJFX0 of agent , (1) ∀ ∈ s.t. () < () − (): () ≥ () + () and (2) fies DJFX 0 (JFX0). ∀ ∈ s.t. () > () − (): () ≥ () − ().
Definition 6. (JF1) is JF1 if, ∀, ∈ [] s.t. agent is not JFX of agent , (1)⋆ ∃ ∈ s.t. () − () ≥ () or (2) ∃ ∈ s.t. () ≥ () − ().
spectively with JFX0, JFX, and JF1 in instances with just goods, whereas DJFX0, DJFX, and DJF1 differ respectively from JFX0, JFX, and JF1 in instances with bads: see Example 1.
by any allocation even in instances with identical additive
utilities, which are often considered by [
Theorem 1. There are instances with 2 agents and identical additive utilities, where none of the allocations satisProof. We will show the result in an instance with goods and in an instance with bads, where there is one item that delivers zero utility to each agent. Such items might be good in cases when agents do not mind carrying another item (e.g. have space in the knapsack) with them but bad in cases when agents do mind carrying another item (e.g.
do not have space in the knapsack) with them.
We first show the result with goods. Let us consider Theorem 2. In fair division with additive utilities for 2 agents, item , and item . We define the utilities goods and bads, the leximin ++ solution could return in as: 1() = 2() = 1, 1() = 2() = 0. By () time a DJFX allocation. the symmetry of the utilities, we consider only two allocations: = ({}, {}), = ({, }, ∅). We argue Proof. Let denote a leximin++ allocation. Suppose that none of these allocations is DJFX0. To see this, we that is not DJFX for a pair of agents , ∈ [] with next give all violations of this property for each alloca- ̸= . That is, () < (). Also, (1) () < tion: (1) 2(2) = 0 < 1 = 1(1 ∪ {}) and (2) () + () holds for ∈ with () < 2(2) = 0 < 1 = 1(1 ∖ {}). We argue in a sim- () − () or (2) () < () − () holds ilar way that none of the allocations is JFX0. To see for ∈ with () > () − (). Wlog, let this, we observe the following violations of this prop- 1(1) ≤ . . . ≤ () denote the utility order induced erty: (1) 2(2 ∖ {}) = 0 < 1 = 1(1) and (2) by . We let = arg max{ ∈ []|() ≤ ()}. 2(2) = 0 < 1 = 1(1 ∖ {}). The result follows. We note ≤ and < . We next consider two cases
We next show the result with bads. Let us consider depending on whether condition (1) or condition (2) holds. 2 agents, item , and item . We define the utilities Case 1: Let (1) hold for bad ∈ . Let us move as: 1() = 2() = −1, 1() = 2() = 0. By from to . We let denote this new allocation. That the symmetry of the utilities, we consider only two al- is, = ∖ {}, = ∪ {} and = for locations: = ({}, {}), = ({, }, ∅). We argue each ∈ [] ∖ {, }. We argue that ≻ ++ holds. that none of these allocations is DJFX0. To see this, we We note that = holds for each ∈ [] ∖ {}. next give all violations of this property for each alloca- We show ( ) > () where is the th agent tion: (1) 1(1) = −1 < 0 = 2(2 ∖ {}) and (2) in the utility order induced by . If this agent is , then 1(1) = −1 < 0 = 2(2 ∪ {}). We argue in a () = () − () > () = () by similar way that none of the allocations is JFX0. To see (1). If this agent is , then () = () + () > this, we observe the following violations of this prop- () = () by (1). Otherwise, ( ) = erty: (1) 1(1) = −1 < 0 = 2(2 ∖ {}) and (2) +1(+1) > () by the choice of . It follows in 1(1 ∖ {}) = −1 < 0 = 2(2). The result follows. each case that () ≥ ( ) > () holds for This concludes the proof. each agent ∈ [] ∖ [([] ∖ {}) ∪ {}]. Therefore, cannot be leximin++.
In instances with additive pure goods, an allocation Case 2: Let (2) hold for good ∈ . Let us move only
is DJFX0 (JFX0) iff it satisfies equitability up to every item from to . We let denote this allocation:
non-zero item [
Such allocations are returned by the leximin++ solu- Finally, we conclude with the time complexity needed tion, proposed by [17]. To define it, we let→− () ∈ R for computing the leximin++ solution. This solution can denote the utility vector in , which is (re-)arranged in be computed by a simple naive brute-force algorithm that some non-decreasing order. We write next ≻ ++ if starts from a given allocation and, for each allocation , there exists an index ≤ such tha→t− () =→− () checks whether ≻ ++ holds and if it holds continues and | | = | | for each 1 ≤ < , and eithe→r− () > with and, otherwise, with . The allocation returned by →− (), o→r− () =→− () and || > ||. this simple algorithm is maximal under the operator ≻ ++
The leximin++ solution is defined as a maximal ele- and, therefore, the leximin++ solution. The algorithm ment under ≻ ++. It maximises the least agent’s utility, has to visit all () allocations (i.e. each out of items then maximises the bundle’s size of an agent with the least can be allocated to each out of agents) in the worst case. utility, before it maximises the second least utility and the Therefore, it will terminate in () time at the latest. second least utility bundle’s size, and so on. This concludes the proof.
tee DJFX in polynomial time for instances with additive utilities for goods and bads, even though intractable such allocations exist by Theorem 2. For this reason, we leave open this question. On the other hand, we can do this for JFX allocations in such instances. For this purpose, we give Algorithm 1.
Algorithm 1 first partitions the items into goods and bads. Until all goods are allocated, the algorithm then picks the least utility agent and gives them their most preferred remaining good. Until all bads are allocated, the algorithm then picks the greatest utility agent and gives them their least preferred remaining bad. This gives us a JFX allocation.
Algorithm 1 A JFX allocation with additive utilities. 10: 11: 12: 13: 14: 1: procedure JFX-ADDITIVE([], [], ()) 2: ∀ ∈ [] : ← ∅ 3: + ← 4: − ← 5: while + ̸= ∅ do 6: ← arg min∈[] () 7: ← arg max∈+ () 8: ← ∪ {} 9: + ← + ∖ {} while − ̸= ∅ do ← arg max∈[] () ← arg min∈− () ← ∪ {} − ← − ∖ {} 15: return ◁ i.e. allocate all goods ◁ i.e. allocate all bads
If () > (+), then would have picked before + by the fact that agents pick goods in a non-increasing utility order. Hence, it must be the case that each non-zero marginal good + ∈ is such that (+) ≥ (). This implies ()+()− () ≥ ()+()− (+) for each + ∈ ∪ {}. remains JFX of even after receives .
Case 2: If ∈ − is bad for everyone, then = ∪{}. Hence, ()+() ≤ (). Recall, ∈ [] and ∈ − are such that () is maximum and () is minimum. We note that all goods are allocated at this point.
Sub-case 2.1 ( → ): By the choice of , () ≥ () holds for each ∈ []. It follows () + () − () ≥ () and () ≥ () − (+) for each non-zero marginal good + ∈ . Let − ∈ be a non-zero marginal bad.
If () < (− ), then would have picked before − by the fact that agents pick bads in a non-decreasing utility order. Hence, it must be the case that each non-zero marginal bad − ∈ is such that (− ) ≤ (). This implies () + () − (− ) ≥ () + () − () for each − ∈ ∪ {}. remains JFX of even after receives .
Sub-case 2.2 ( → ): As satisfies JFX, we have () + (− ) ≥ () for each non-zero bad − ∈ and () ≥ () + (+) for each non-zero good + ∈ . But, as () ≤ 0, it follows () ≥ () + () and () − (+) ≥ () + () − (+). remains JFX of . This concludes the proof.
by computing a ranking of the items for each of the Theorem 3. In fair division with additive utilities for agents. Computing such rankings can be done in goods and bads, Algorithm 1 returns in ( ln ) ( ln ) time and space. time a JFX allocation. To sum up, we might prefer JFX to DJFX in instances Proof. Let us consider the partial allocation . We as- with additive utilities because it remains unknown whether sume that is JFX and, under this assumption, we prove DJFX allocations are tractable in every instance, even that extending with the chosen item preserves JFX. though such allocations exist by Theorem 2. The result would then follow by the observation that the allocation when no item is allocated is JFX. 10. Jealousy Freeness Up To
Case 1: If ∈ + is good for everyone, then = ∪ {}. Hence, () + () ≥ (). Moreover, Some Item we note that no agent has any bad in their bundle. This fact follows from the observation that the algorithm allocates As we showed, the leximin++ solution is DJFX and it all goods before any bads. can be computed in () time. This might be fine for
Sub-case 1.1 ( → ): is JFX. Therefore, () ≥ a constant . However, can be much larger than in (.As) −(()++) for(ea)c≥h non(-zero), m arregminaailngsoJoFdXo+f ∈ pDrJaFc1ticaell.oFcoartitohniss.rWeaesocna,nwdeo mthaiys wwiitshh Atolgreotruitrhnmtra2c.table even after receives . Algorithm 2 allocates the items one by one. If the
Sub-case 1.2 ( → ): As is a minimum utility current item is good, then the algorithm gives it to the agent in , () ≥ (). It immediately follows least utility agent. Otherwise, the algorithm gives it to () ≥ () + () − (). Let + ∈ be a the greatest utility agent in a thought experiment, where a non-zero marginal good. copy of the bad is allocated to every agent.
1–8
running time is dominated by computing a sorting of the agents’ bundle utilities for each of the items.
By Theorem 3, it follows that JFX allocations exist and, as by definition, such allocations satisfy JF1, it follows that Algorithm 1 returns JF1 allocations as well.
To sum up, we may be indifferent between DJF1 and JF1 in instances where agents have additive utilities for goods and bads, because both properties are tractable. 11. Future Directions
For example, by Theorem 2, we know that intractable DJFX allocations exist in instances where agents have additive utilities for goods and bads, but we could not design a tractable algorithm that returns DJFX allocations in such instances. Another future direction is to study interactions of the proposed properties with economic efficiency criteria such as Pareto optimality. Finally, as social resources in practice are either public goods or public bads, we focused on instances with such items. However, in future work, we will also consider instances in which a fixed item can be good for some agents and bad for other agents. Algorithm 2 A DJF1 allocation with additive utilities.
←
are allocated. This is DJF1. In the hypothesis, we let denote the partial allocation and assume that is DJF1.
In the step case, we show that allocating to agent preserves DJF1. By the hypothesis, agents ̸= and ̸= remain DJF1 after is allocated to because their allocations remain intact.
Case 1: Let be a social good. In this case, () + () ≥ () and () ≥ () for each ∈ []. 12. Acknowledgements Let us consider some agent ̸= . If () + () > (), it follows that () ≥ () + () − () holds. If () + () = (), it follows that () ≥ () + () holds. remains DJF1 of .
In the opposite direction, as is DJF1, we conclude () ≥ ()− (+) for some non-zero marginal References good + ∈ or () − (− ) ≥ () for some non-zero marginal bad − ∈ . Thus, as item is social good, we derive () + () ≥ () and () + () − (− ) ≥ () − (− ). remains DJF1 of .
Case 2: Let be a social bad. In this case, () + () ≤ () and () + () ≤ () + () for each ∈ []. Let us consider some agent ̸= . For the sake of contradiction, let us suppose that is not DJF1 of . This implies that ()+() < ()+() must hold. But, this contradicts the choice of . remains DJF1 of agent .
In the opposite direction, as is DJF1, we conclude () ≥ () + (+) for some non-zero marginal good + ∈ or () ≥ () + (− ) for some non-zero marginal bad − ∈ . Thus, as item is social bad, we derive () + () + (− ) ≤ () + (− ) and () + () − (+) ≤ () − (+). Agent remains DJF1 of agent . [1] S. J. Brams, A. D. Taylor, Fair Division - from
Cake-cutting to Dispute Resolution, Cambridge University Press, 1996. URL: https://doi.org/10.1017/
CBO9780511598975. [2] H. Steinhaus, The problem of fair division, Econometrica 16 (1948) 101–104. URL: https://fu-berlin. primo.exlibrisgroup.com/discovery/openurl? institution=49KOBV_FUB&vid=49KOBV_FUB: FUB&rft.epage=104&rft.volume=16&url_ver= Z39.88-2004&rft.date=1948&rft.spage=101&rft. jtitle=Econometrica&rft.atitle=The%20problem% 20of%20fair%20division&rft.title=Econometrica. [3] H. P. Young, Equity: In Theory and Practice, Princeton University Press, 1995. URL: https://press.princeton.edu/books/paperback/ 9780691044644/equity. [4] J. Nash, The bargaining problem, Econometrica 18 (1950) 155–162. URL: https://doi.org/10.1515/ 9781400829156-007.