Graphical Resource Allocation with Matching-Induced Utilities
Authors: Zheng Chen
Bo Li
Minming Li
Guochuan Zhang
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Fair Division
Graphical Resources
Matching
Maximin Share
Envy-freeness.

Abstract: Motivated by real-world applications, we study the fair allocation of graphical resources, where 
the resources are the vertices in a graph. Upon receiving a set of resources, an agent's utility equals the weight of the maximum matching in the induced subgraph. We care about maximin share (MMS) fairness and envy-freeness up to one item (EF1). Regarding MMS fairness, the problem does not admit a finite approximation ratio for heterogeneous agents. For homogeneous agents, we design constant-approximation polynomial-time algorithms, and also note that significant amount of social welfare is sacrificed inevitably in order to ensure (approximate) MMS fairness. We then consider EF1 allocations whose existence is guaranteed. We show that for homogeneous agents, there is an EF1 allocation that ensures at least a constant fraction of the maximum possible social welfare. However, the social welfare guarantee of EF1 allocations degrades to $1/n$ for heterogeneous agents, where $n$ is the number of agents. Fortunately, for two special yet typical cases, namely binary-weight and two-agent, we are able to design polynomial-time algorithms ensuring a constant fractions of the maximum social welfare.

Graphical Resource Allocation with Matching-Induced Utilities
Anonymous Author(s)
Affiliation Address
email
Abstract
Motivated by real-world applications, we study the fair allocation of graphical resources, where the resources are the vertices a graph. Upon receiving a set resources, agent's 's utility equals the weight of the maximum matching in the induced subgraph. We care about maximin share (MMS) fairness and envy-freeness up item (EF1). Regarding MMS faimess, the problem does not admit finite approximation ratio for heterogeneous agents. For homogeneous agents, we design constant-approoximaton polynomial-time algorithms, and also note that significant amount of social welfare is sacrificed inevitably in order to ensure (approximate) MMS fairness. We then consider EFI allocations whose existence is guaranteed. We show that for homogeneous agents, there is an EFI allocation that ensures at least constant fraction of the maximum possible social welfare. However, the social welfare guarantee of EF1 allocations degrades to 1/n for heterogeneous agents, where n is the number of agents. Fortunately, for two special yet typical cases, namely binary-weigh and two-agent, we are able to design polynomial-timg algorithms ensuring a constant fractions of the maximum social welf
2
4
6
8
10
11
12
13
14
15
Introduction
16
Resource allocation has been actively studied due its practical applications [Moulin 2003 Goldman and Procaccia 2014; Flanigan et al. 2021]. Traditionally, the utilities are assumed to be additive which means an agent's value for a bundle of resources equals the sum of each single item's marginal utility. But in many real-word problems, the resources have graph structures and thus the agents' utilities are not additive but depend on the structural properties of the received resources. For example, Peer Instruction (PI) has been shown to be an effective learning approach based on project conducted at Harvard University, and one of the simplest ways to implement and Mazur 200T]. Consider the situation when we partition students to advisors, where the advisors 25 will adopt PI for their assigned students. Note that the advisors may hold different perspectives on how to pair the students based on their own experience and expertise, and they want to maximize
17
18
19
20
21
23
to pair the students [Crouch]
24
27 the efficiency of conducting PI in their own assigned students. How should we assign the students fairly to the advisors? How assignments? In this work, we take an algorithm design perspective to solve these two questions. Similar pairwise joint work also appears as long-trip coach driver co-driver and accountant vs cashier, which is widely investigated in matching theory [Lovász and Plummer 2009].
maximize the social welfare among all (approximately) fair
29
31
The graphical nature of resources has been considered in the literature (see, e.g.. [oouveett et al. 33 2017: Suksompong 2019 Bild el af.) 2019 [garashi and Peters, 2019]). this line of research, the graph used to characterize feasible allocations (such as the resources allocated to each agent should 35 be connected), but the agents still have additive utilities over allocated items. With graphical resources, the value of set of resources does not solely depend on the vertices or the edge weights, but decided
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37
by the combinatorial structure of the subgraph, namely, maximum matching in our problem. Graph structure is also considered in cooperative game theory (i.e., hedonic games) Bogomolnaia and
38
39
Jackson 2002 Elkind and Wooldridge 22099] Aziz et al. 2019], but this is not a resource allocation problem and its major concern is how stable coalition structure can be formed.
40
41
Our problem also aligns with the research of balanced graph partition [Miyazawa et al. 202 Although there are heuristic algorithms in the literature [Kress et al. 2015: Barketau et al. 2015 that partition a graph when the subgraphs are evaluated by maximum matchings, these algorithms do not have theoretical guarantees. Our first faimesss criterion the maximin share (MMS) fairness proposed by Budish| 2 which generalizes the max-mil min objective in Santa Claus problem (Bansal and
42
43
44
45
Sviridenko 2006 Informally, the MMS value of an agent is her best guarantee she is partition the graph into several subgraphs but receives the worst one. We aim at designing efficient algorithms with provable approximation guarantees. As will be clear later, to achieve (approximate) MMS fairnss,, a significant amount of social welfare has to be inevitably sacrificed. Our second fairness notion is envy-freeness (EF) [Foley] 1967]. In an EF allocation, no agent prefers the allocation of another agent to her own. Since the resources are indivisible, such allocation barely exists, and recent research in fair division focuses on achieving its relaxations instead. One of the most widely accepted and studied relaxations is envy-freeness up to one item (EFI) [Budish] 201T]. which requires the envy to be eliminated after removing one item. Lipton et al. 2004 proved that an EF1 allocation always exists even with combinatorial valuations It is noted that arbitrary EFI allocation may have low social welfare, and our goal is to compute an EFI allocation which preserves a large fraction of the maximum social welfare without fairness constraints. The social welfare loss by enforcing the
46
47
48
49
50
51
52
53
54
56
58
allocations to be EF1 is quantified by price of EFI (Bei et al. 2021
59
1.1
Our Results
60
We study the fair allocation of graphical resources when the resources are indivisible and correspond to the vertices in the graph, and the agents' valuations are measured by the weight of the maximum matchings in the induced subgraphs. The fairess of an allocation is measured by maximin share (MMS) and envy-free up to one item (EF1). We aim at designing efficient algorithms that compute fair allocations with high social welfare. Our main contributions are summarized as follows.
61
62
63
64
65 We first consider homogeneous agents when their valuations are identical. For homogeneous agents, the MMS fairness degenerates to the max-min objective, i.e., partitioning the vertices so that the minimum weight of the maximum matchings in the subgraphs is maximized. It is easy to see that an MMS fair allocation always exists but finding it is NP-hard. We design a polynomial-tim 1/ /paapprrxinntoion algorithm for arbitrary number of agents, and show that when the problem only involves two agents, the approximation ratio can be improved to 2/3. It is noted that, to ensure any finite approximation of MMS fairness, significant amount of social welfare is inevitably sacrificed.
66
87
68
69
70
71
72 Regarding EF1 fairness, we design a sayyoooill-iimm algorithm that computes an EFi allocation
73
whose social welfare is at least 2/3 + 2/(9n 3) fraction of the maximum social welfare that can be achieved without fairness constraints, where n is the number of agents. Note that when n = 2, the approximation ratio is 4/5, and we conjecture that there always exists an EFI allocation that achieves the maximum social welfare for any number of agents.
74
75
76
77 We then consider the case of heterogeneous agents. Unfortunately, we show strong impossibility
78 results for the general case. Particularly, for MMS fairness, no algorithm has bounded approximation
79 ratio even if there are two agents with binary weights. For EFI fairness, no EFI allocation can ensure
80 better than 1/n fraction of the maximum social welfare, but this result does not exclude the possibility
81 of constant approximations for two special cases. In fact, for both two-agent case and binary-
82 case we design polynomial-timm algorithms that guarantee 1/3 fraction of the maximum social
83 welfare. Moreover, for the two-agent case, the approximation ratio is the best possible.
84
1.2 Related Works
85 Two separate research lines are closely related to our work, namely graph partition and fair division.
'The algorithm in Lipton et al. 2004 was originally published in 2004 with different targeting property. In 2,11, Budish 2011 formally proposed the notion of EFI faimeess.

---

86
Graph Partition. Partitioning graphs into balanced subgraphs has been extensively studied in opera- tions research MMyyzaaw et al. [02T] and computer science [Buluç et al. 2016]. There are several popular objectives for evaluating whether a partition is balanced. Among the most prominent ones are the max-min (or min-max) objectives, where the goal is to maximize (or minimize) the total weight of the minimum (or maximum) part. Particularly, the vehicle routing problem (VRP) [Koç et al.) 2016), which generalizes the travelling salesperson problem (TSP), is closely related to our work. It asks for an optimal set of routes for a number of vehicles, to visit set of customers. There are number of popular variants for the VRP, e.g., the so called heterogeneous vehicle routing problem many other combinatorial structures studied in graph
87
88
89
90
91
93
94
Yaman 2006, Rathinam et al. 2020]. There partitioning problems. For example, in the min-mat min--ax tree cover (a.k.a. nurse station location) problem. the task is to trees to cover edge- weighted graph such that the largest tree is minimized [Khani and Salavatipour/ 2014). This problem also falls under the umbrella of a more general problem, the graph covering problem, where set of pairwise disjoint subgraphs (called templates) is used to cover a given graph, such as paths [Farbstein and Levin 2013). cycles (Traub and Tröbst 2020 and matchings [Kress et al., 2015].
95
97
98
99
100
101
Fair Division. Allocating a set of indivisible items among multiple agents is a fundamental problem in the fields of multi-agent systems and computational social choice, and we refer the readers to recent surveys [Amanatidis et al. 2022 Aziz et al. 2022] for more detailed discussion. Envy- freeness (EF) and maximin share faimess (MMS) are two well accepted and extensively studied solution concepts. However, with indivisible items, these requirements are demanding and thus the oftte-of-the-art research mostly studies their relaxations and approximations. For example,
102
103
105
107
EF1 allocation is studied as relaxation of EF which always exists [Lipton et al. 20044). Various constant approximation algorithms for MMS allocations are proposed in [Kurokawa et al. 2018]
108
109
Garg and Taki, (202T] for additive valuations and in [Brrman and Krishnamurthy] 20220 2
Ghodsi er
al. 20188 for subadditive valuations. Our work focuses on indivisible graphical items where agents 110
have combinatorial valuations (neither subadditive nor superadditive) depending on the structural properties. Moreover, all the existing algorithms for non-additive valuations run in polynomial time only if the computation of valuations is assumed to be effortless (i.e., oracles). In contrast, in this work, we aim designing truly polynomial time approximation algorithms without valuation oracles. 114
111
112
113
115 2
Preliminaries
116
Denote by G= (V, E) an undirected graph without reflexive edges, where V contains all vertices and contains all the edges. The vertices are the items that are to be allocated to n heterogeneous agents, denoted by N. Each agent has edge weight function w; E + I U {0), which may be diffcrent from others'. If (e) E {0, 1} for all e E E, then the weight function is called binary. Let w (Wi, wa). A matching M C E is a set of vertex-disjoint edges, and let (M = EeEM (e).). For any subgraph G', let ((G) and E(G") be the sets of vertices and edges in G", respectively. An allocation X- = (XI....,
117
119
121
122
is a partition of V such that UiEN = V and X, n X, = 0 for i & j. If Xi Ç V. the allocation is called partial. Each agent i has utility function
2V + IR. U (0), where u; (X,) equals the weight of maximum (weighted) matching G[X,]. When the agents have identical valuations (i.e., homogeneous agents), we omit the subscript and use w(-) and u(-) to denote all agents' weight and utility functions. A problem instance is denoted by I = (G, N). When we want to highlight the weight function, w is also included as parameter, i.e., I = (G, w...
124
125
127
129
Next we introduce the solution concepts. Our first fairness notion is maximin share (MMS) [Budish] Letting II, (V) be the set of all n- n-partitions of V. the maximin share of agent is
130
2011
MMS, (T) = max min (X,).
(V)
131
We may write MMS, for short if I is clear from the context. Therefore agent is satisfied regarding MMS fairness if her utility is no smaller than MMS,
132
133
Definition 2.1 (a-MMS). For any 2 O, an allocation X = (X1,... ,x)) is called a-approximate
134
maximin share (a-MMS) fair for all agents i E N,
(x(..) 2 a- MMS,
135
The allocation is called MMS fair if 1.
3

---

138
The second fairness notion is about envy-freeness (EF). An allocation X is called EF if no agent envies any other agent's bundle, i.e.,
137
uy (x,) 2 (x,)) for all agents i,j E N.
We observe that it is very hard to satisfy EF for arbitrary instance. Consider a simple counter example, where the graph is a triangle and two agents have weight 1 for all edges. Then in every allocation, there is one agent who gets at most one vertex (with utility 0) and the other agent gets at least two vertices (which contains an edge and thus has utility 1). Accordingly, we focus on the envy-free up one item instead [Budish] 2011].
139
140
141
142
Definition 2.2 (EFI), An allocation X = (X,,... Xx)) is called envy-free up to I item (EFI) for any and j. there exists E X3 such that (X,,)) 2 (X; \ (g])..
144
145
Besides faimess, also want the allocation to be efficient. Given allocation X = (X1, Xnn). the social welfare of X is sw(X) = LiEN (X)). Note that given any instance I, the best possible social welfare of any allocation is the weight of a maximum matching in the graph G by setting the weight of each edge to maxieN we(e),, which is denoted by sw" sZ" If the instance I is clear from the context, we also denote sw" (I) as sw" for short.
146
147
148
149
Homogeneous Agents
150
We start with the case of homogeneous agents when the agents have identical valuations.
152
3.1
MMS Fair Allocations for Homogeneous Agents
153
With identical valuations, the MMS fairness degenerates to the max-min objective, where the problem is to partition graph into subgraphs so that the smallest weight of the maximum matchings in these subgraphs is maximized. is easy to see that finding such an allocation is NP-hard even when there are two agents and the graph contains set of disjoint edges, which is essentially Partition problem. Therefore, we aim at designing polynomial- time approximation algorithms to achieve the MMS fair objective. Without loss of generality, in this section, we assume w(e) 2 1 for all E. Since the agents have identical valuations, we omit the subscript in MMS, and simply write MMS.
155
157
159
160
Our main result in this section is as follows.
181
Theorem 3.1. We can compute 1/8-MMS allocation in polynomial time for homogeneous agents.
162
Before proving the theorem, we explain the intuition of Algorithm Given an instance I (G, N). to ensure the maximum matching in every subset of vertices to be large, we first try to allocate maximum matching in the original graph. Specifically, we compute a maximum matching in G
163
164
denoted by M C E, and then partition M into bundles (M MM)) where w(Mi) 2
166
w( (M,) such that w (M,) is as large as possible. This task hP-hard and thus we instead use the following simple greedy solution, which we call greedy partition of M
168
Greedy Partition.
Given a matching M, partition M into I(M) = (M,,
.. ... M,)) as follows.
169
Sort and rename the edges in M such that w(ez)) 2 ... 2 w((x) where k: IM.
Initially set M1
Mn = 0.
*
For i = 1,... J, select j such that w(M) S w (M².) for all j' and set M, = M2 U (es).
172
* Sort and rename Mj, ,M, so that w(M) 2 ... (MM). Mn,
173
The greedy partition of M corresponds to an allocation of vertices where unmatched vertices
174
can be allocated arbitrarily. The good news is that such an allocation achieves MMS faimess when the graph is unweighted, i.e., w(e) = w(e') for all e, E F.
V = UieN
175
178
Lemma 3.2. If G unweighted, the greedy partition (M1, Mn,) of M an MMS allocation.
177
The bad news is that such an allocation does not have any bounded approximation guarantee when the edges have distinet weights. Consider the following example with two agents and the graph is shown in Figure D where A > 1 is arbitrarily large. Any allocation with bounded approximation ratio
178

---

A
U2
Figure 1: A bad example when greedy partition does not have bounded approximation guarantee of MMS.
180
of MMS fairness ensures that every agent has value 1, but by partitioning the maximum matching (which contains a single edge with weight A) the smaller bundle has value O. However, if [M 2
181
182
such an allocation is 1/2-MMS.
185
Lemma 3.3.
|M| 2, ((M)) corresponds to an allocation that is 1 122-MMS fair.
184
The tricky case is when M1 contains single edge e". To use the approach in Lemma 3.3 to derive 1/2-MMS fair, we iteratively decrease the weight of e* and re-compute a maximum matching until
185
186
Mi 2 2. For simplicity, assume all edge weights are powers of 2. This is without much loss of generality which decreases the approximation ratio by at most 1/2.
187
188
Lemma 3.4. LetI= = NG,N, w) and I' = NG,N,o w') be two instances where I' is obtained from by rounding all edge weights down to the nearest power of If (X1, (Xn) is an a-MMS allocation of T', then it is 0:/2-MMS allocation I. I.
189
We prove Lemmas 3.2
3.3 and 3.4 in the appendix. Now We first compute a maximum matching M* and its greedy partition [ T(M*) (M1,'.. .... M, such
ready to describe Algorithm T
182
193
that w(M1 2 2 wM,.). If Mi| 2 2, combining Lemmas 3.3 and 3.4 we are safe to output
194
the corresponding partition of vertices so that the approximation ratio is at least 1/4. If [M] = 1,
195
we consider two cases. If (M,) 2 1/2 w(M)). w(M,,) is still not too small and we can stop the algorithm with constant approximation ratio. However, if w(M,) < 1/2 w (MM)) it means the utility of the smallest bundle much less than that of the largest bundle. Then we update the edge weights: Let H be the edges with weights no smaller than w(e1) where is the edge in M1, and decrease their weights to 1/2 w(e)). By repeating the above procedure, eventually we reach an allocation such that w( (M,) 2 1/2 w/ (Mi) or Mi
196
197
198
199
Algorithm 1: Approximately MMS Fair Allocation Algorithm for Homogeneous Agents
Input: Instance I N) with G (V, E; w) Output: Allocation X (X1,- ... (,,). 1: For all e reset
w(e) = 20o w(e)]]
2: Find a maximum matching M* G. Denote by V the set of unmatched vertices.
3: Find the greedy partition ((M*) (M,.... Ma) of M* such that w(M)) 2 ... w/ (M,).
4: while (M, > w(M,) and G has different weights do
5: Let e1 be the edge in M1 and H {e E E w(e) w(e1))
6: Let w(e) = (et)/2 for all e H.
7: Re-compute maximum matching M*
8: Re-set V to be unmatched vertices by M
9: Re-compute the greedy partition [(M") (M1,' Mn) such that
w( w(M,) 2 ... 2 (M,).
10: end while
11: Set X; = V(M)) for in 1, ..,,.nn 11
12: Set X,, ((M,) UV'
13: Return allocation (X1,-.. Xn).
200
We now ready prove Theorem
3.1
202
First, we show Algorithm I is well-defined and runs in polynomial time. Every time when the condition of the while loop holds, either the graph has different weights and an allocation is returned or the weights of the heaviest edges are decreased by 1/2 with some 2 1.
Proof of Theorem 3.1
204
205
Thus the while loop is executed O Ommaxee E log w(e)) rounds.
206
Next we prove the approximation ratio. By Lemma 3.4 we only need to consider the instance where the edge weights are powers of 2 and show the allocation is 1/4-approximate MMS fair. Denote by
5

---

208 -= (01, ... On)) the optimal solution, where u(O1) 2 ... u(On) and MMS(Z) = =(OO)). The
209
first time when we reach the while loop, if ((M) 2 w(M)))
1 MMS(Z),
wMMM), 2 2 w M1) 2 ,.,).
2
210
where the second inequality holds because M a maximum matching in G. Thus the allocation is 1/2-MMS. If all edges have the same weight, then by Lemma 3.2 the allocation is optimal.
212
We move into the while loop if ww 2- wo (M,) and the edge weights are not identical. Note that w(M1 > 2- w(M,) implies M1 contains single edge denoted by e1. Otherwise consider the last edge added M1 in the greedy partition, denoted by e'. Then wMM1 {e'}) S ((M,) and w(e') I w(( w,M,), which implies w(M] Mi) < 2 w (. After the while loop, denote by I' the instance, by w-(-) the new weights with new utility function v' v'(:), by O' = (0,,'. O², the new optimal solution and by M' the maximum matching with greedy partition (Mi ... M₁), Then we
213
214
216
217
218
have the following claim, which is proved in the appendix.
219
Claim 3.5. After each while loop, one of the following two cases holds true.
Case wo(er) MMS(Z), then MMS(I') MMS(I);
220
. Case 2, w(er) < 2 MMS(Z). then 2 MMS(I') MMS(I) and w' (M1) s 2-220 w/ (M,)).
222
By Claim 3.5 the while loop will not execute Case it executes Case 1 for several times and
223
then Case 2 for exactly once. If Case is not executed, then the allocation is 1/2-MMS fair and the analysis the same with the case when the while loop not executed.
224
225
Case 2 is executed once, then by Claim 3.5
1
1 MMS(Z). MMS(T)) 4
w' (Mr) 2
w (MM) 2
226
Finally, by Lemma 3.4 the allocation 1/8-MMS for any instance with arbitrary weights.
227
Remark. When n = 2, we can improve Algorithm | and obtain better approximation ratio of 2/3.
228
Due to the space limit, we provide the refined algorithm the appendix.
229
3.2
Efficient and EF1 Allocations for Homogeneous Agents
230
Recall the example shown in Figure I The maximum social welfare is sw = A, but any allocation with bounded approximation ratio for MMS fairness has social welfare << A, which means to ensure MMS, we lose significant amount of efficiency. Note that the existence of EFI allocations is guaranteed by the envy-cycle elimination algorithm designed by Lipton al. [2004). But the social welfare of the returned allocation does not have any guarantee. In this section, we aim at computing
232
233
234
235
an EF1 allocation that also preserves high social welfare.
Theorem 3.6. For any instance I (G. N), Algorithm welfare at least (2/3 - 2/(9n - 3)) sw" (I) in polynomial time.
2 returns EFI allocation with social
237
We prove Theorem in the appendix. and in the following we briefly discuss the idea of Algorithm 2
239
We first introduce the EFI-graph, inspired by the envy-graph introduced in (Lipton et al. 2004
Given (partial) allocation (X1,-. Xx,), construct the corresponding EF1-graph & (N,
241
where the nodes are agents (and thus are used interchangeably) and there is a directed edge from to j if envies j (or Xy) for more than one item,
(x(X,) < ux(X, (v}) for every v E Xj-
When the agents have identical utility functions, we have the following simple observation. Observation 3.7. The EFI-graph is acyclic; The in-degree of the agent with smallest utility is zero.
245 Similar with Algorithm| 1 in Algorithm 2 we first compute maximum weighted matching M and let the corresponding unmatched vertices be V". If [M S n. by allocating each edge in M
247 to a different agent and V to one agent who has the smallest utility is EFI, since by removing
vertex from edge, the remaining subgraph does not have edges any more. If M > find

---

Algorithm 2: Computing EFI Allocations with High Social Welfare for n Homogeneous Agents
Input:
Instance (G,N N) with (V, Rr).)
Output:
Allocation X = (X1,.... Xx)
Find maximum matching M G. Denote by V the set of unmatched vertices by M
2: Find the greedy partition (M,,-* ... ;M,) of edges in M such that w(M1) 2 ... w (M,).
3: Set X; = (M,) for 1..-.,
4: if [MM < then
5: Let X, = (VM,)VV .X)).
6: Return
7: end if
8: Construct the EFI-graph G (N, E) based on (X1, .x)).
9: Set Q be the agents with positive in-degree.
10: for i E Q do
11: Let 6 = (U11, U22) be the last edge added to Mj in the greedy-partition procedure.
X; X; {va) and V V {va).
13: end for
for V" do
15: Let i = arg minleN u(X)).
Set X; = X, (u).
17: end for
Return (. Xn).
greedy-partition r(M*) = (M,,... M,) of M such that (MM)) 2 ... w(Ma). However, by simply assigning X, = (MM) for every i, it may not be EFI, which is illustrated in the appendix.
250
To overcome this difficulty, we utilize the EFI-graph G (N,E) on the partial allocation (V ..)..... (M,)). Let Q C N be the set of agents who have positive in-degree, i.c., are agent for more than n É Q. Moreover, since M,, has the smallest weight in the greedy partition I(M*), n has an edge to every agent in Q. We first consider the partial allocation after the for loop in Step [O, which is denoted by Y == (Y,,... Y.). We can prove that Y is EFI, and moreover, it ensures the desired social welfare guarantee. Finally, the remaining steps preserve the ness and can only increase the social welfare the allocation. The formal analysis is deferred to the appendix.
252
envied by
item. By Observation 3.7 if G is nonempty, Q * 0 and
254
256
258
Heterogeneous Agents
259
260
In this section, we discuss the general case of heterogeneous agents. We first show the negative results for MMS and EFI allocations, and then focus on the special cases when we are able to obtain positive results. Due to space limit, all the results in this section are proved in the appendix.
281
262
4.1
Negative Results for MMS and EFI Allocations
284
We present the main theorems below whose proofs are in the appendix.
265
Theorem 4.1. No algorithm has bounded approximation guarantee for MMS fairness, even for the case of two agents with non-identical binary weight functions on the graph.
287
Theorem 4.2. No algorithm has better than 1/n approximation of social welfare for EF1 fairness for heterogeneous agents.
288
289
Theorem
is very strong in the sense that it excludes the possibility of designing algorithms with bounded approximation ratio for MMS even for the special cases of two-agent binary weight functions. However, Theorem 4.2 retains this possibility for EF1, and we design polynomial-tin
270
271
272
algorithms to compute EFI allocations that ensure constant fractions of the maximum social welfare for these two cases. In the appendix, we complement Theorem 4.2 with positive result where we design an algorithm that has (1/n?)) approximation guarantee of social welfare for the general case.
274
275
4.2
Binary Weight Functions

---

Algorithm 3: Computing EFI Allocations for Heterogencous Agents with Binary Weights
Input: Instance (G. N, w) with G= (V, F). Xx).
Output: Allocation X = (X1,
I: Initialize X; f i E N. Let M, be the maximum matching in G|X,] for agent Denote by
G" = EN, the envy-graph on X.
2: P (X, U...U.UU U,,,,,,,, be the set unallocated items (called pool).
3: Partition agents i E N into & groups A (A..... AA) such that agents in the same group have the same value, i.e., uz(X,,, = ux(X,) for i,j A and E [k]. Assume A is are ordered,
i.c., uy (X,, < uy (X,) for agents E Ae. E At, and t < tz.
4: Let + 1 and T + A
5: while {t < 7 do
6: // Case 1. Directly Allocate
7: if there exists agent E A₁ such that (1) there is edge in G[P) with wx(e) 1 and (2)
allocating the two endpoints U1, U/ of e to agent i does not break EF1 then
8:
X; f X; (1), 22). P PP {2I, Update uz (X;) for E N and the envy-graph G'.
9:
10:
Update the partition of agents in A.
11:
Reset & <- and r + |A].
I/ Case 2. Exchange and Allocate
13:
else if there exists agent E N and i E A, such that j envies i and there exists a subset with minimum size V P in graph G such that (V*)) (X,)) then
14:
Let V S P be set with minimum size such that vv(V)) uu( Let V S X; be a set with minimum size such that (Vj" = uy((x)
16:
P - (P) V UX, (VF)..
17:
X; K V,, , Update u, (X,) for E N and the envy-graph g'. Update the partition of agents A.
18:
19:
20:
Reset & +-1 and
A
21:
else
22:
// Case 3. Skip the Current Agent
23:
t ++
24:
end if
25:
end while
26: Execute the envy-cycle elimination procedure the remaining items P.
27: Return the allocation (X1,".. .,)).
278
We first show that if the agents have binary weight functions, we can compute an EFI allocation whose social welfare is at least 1/3 fraction of the optimal social welfare. Before introducing our algorithm, we recall the envy-cycle elimination algorithm proposed by Lipton er al. [2004), ) which always returns an EFI allocation. Given (partial) allocation (X1,--- , Xn), we construct the corresponding envy graph G' (N, E), where the nodes are agents (and thus are used interchangeably) and there is directed edge from agent to agent j if and only if (X,) < un (X,). The envy-cycle elimination algorithm runs follows. We first find an agent who not envied by the others, and allocate a new item to her. If there is such an agent, there must be cycle in the corresponding envy graph. Then we resolve this cycle by reallocating the bundles: every agent gets the bundle the agent that she envies in the cycle. We repeat resolving cycles until there is an unenvied agent. The above procedures continue until all the items are allocated. Note that in the execution of the algorithm, the agents' utilities can only increase, and the returned allocation is EFI
277
278
279
280
281
282
284
286
288
not hard verify that the envy-cycle elimination algorithm does not have any social welfare guarantee. There are several reasons. First, the algorithm does not control which item should be allocated to the unenvied agent so that the agent may receive set of independent vertices. Second, once an item is allocated it cannot be recalled so that we are not able to revise any bad decision we have made. increase the social welfare, each round of our algorithm, we try to allocate an edge
289
290
291
292
(i.e., two items) to the agent i with the smallest value so that the social welfare can increase by 1. However, we need to be very careful by allocating two items which may break the EF1 requirement
294
even if is not envied by the others. If allocating an edge to makes some agent j envy i for more
8

---

296
than one item, we check whether i can maintain her utility by selecting a bundle from unallocated items. If so, we execute exchange procedure by asking j to (properly) select a bundle from X, and to (properly) select bundle from unallocated items so that the social welfare is increased by 1. All the items in X; and the items in Xj that are not selected by i are returned to the algorithm. If not, we try to allocate an edge to the agent with the second smallest value by executing the above procedures,
297
299
300
301
and so on. The description is in Algorithm [ and we prove the following theorem in the appendix.
Theorem 4.3. For any instance I (G, N) where agents have binary weights, Algorithm 3 returns an EFI allocation with social welfare at least 1/3 sw (I) in polynomial time.
303
304
4.3
Two Heterogeneous Agents
305
We then discuss the case of two agents, and show that Algorithm 4 Jensures at least 1/3 fraction of the optimal social welfare. Intuitively, in Algorithm 4 we first check whether there is a single edge e for which some agent has value at least 1/3 sw (I). If so. allocating to i already ensures
306
307
308
1/3 sw" (I). Moreover, this partial allocation is EF1 since the removal of one item in results in no
309 edges, and thus we can use the envy-cycle climination algorithm to allocate the remaining vertices, which returns an EF1 allocation and can only increase the social welfare. Otherwise, we compute a social welfare maximizing allocation (M1, M2), i.e., (M(M + u2 (M2) = sw" (Z). Without loss
310
312 of generality, assume u u,(M (M,) I uz(M2) We temporarily allocate M, to agent for i = 1,2. If the allocation is not EFI, since in (M1) S u2 (M2), it can only be the case that agent I envies agent 2 but agent 2 does not envy agent 1. Then we move items in agent 2's bundle one by one to agent 1. It can be shown that there must be time after which the allocation is EFI, and the first time when the allocation becomes EFI, the resulting social welfare must be at least 1/3 sw" (I). Formally, we have the following theorem. Interestingly, despite the simplicity of Algorithm 4 can also show that there is no algorithm that has better than 1/3 approximation.
314
316
318
Theorem 4.4. For any instance I with two heterogeneous agents, Algorithm 4 returns an EFI
320
allocation with social welfare at least 1/3. sw (I). Moreover, the approximation of 1/3 is optimal.
Algorithm 4: EF1 Allocation with tight social welfare guarantee for 2 Heterogeneous Agents
Input: Instance I = (G, N, w) with G = (V, E). Output: Allocation X (X1, 1, X2).
1: if there is E E such that (e) 2 1/3 sw (Z) for some i = 1,2 then
2: Assign e to agent i and run envy-cycle elimination algorithm for the vertices.
3: else
4: Computing a social welfare maximizing allocation (M, M2). Without loss of generality, assume #1 (M1) S uz( (M2), and assign M, to agent i for i = 1,2.
5: while agent 1 envies agent 2 for more than one item do
6: Reallocate some item e E X₂ to agent 1, i.e., X2 + X² \ {v) and X1 < X, Ut)(..
7: end while
8: end if
9: Return the allocation (X1, Xx))
321
5
Conclusion and Future Directions
322
In this work, we study the fair (and efficient) allocation of graphical resources when the agents' utilities are determined by the weights of the maximum matchings in the obtained subgraphs. We provide a string of algorithmic results regarding MMS and EFL, but also leave some problems open. For example, for the cases of homogeneous agents and binary valuations, we believe EFI allocations have better social welfare guarantee. It is also interesting to identify hard instances and study the efficiency limit of EF1 allocations. We can also improve the approximation ratio for the MMS allocation among homogeneous agents. Our work also uncovers many interesting future directions.
323
324
325
326
327
328
329
Firstly, regarding MMS, although we show that there is no bounded multiplicative approximation, may admit good additive or bi-factor approximations. Secondly, we only focus on the matching- induced utilities in this work, and it is intriguing to consider other combinatorial structures such as independent set, network flow and more. Thirdly, we can extend the framework to the fair allocation of graphical chores when agents have costs to complete the assigned items.
330
332

---

References
335
Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris. Fair division of indivisible goods: A survey. CoRR, abs/2202.07551, 2022.
337
Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional hedonic games. ACM Trans. Economics and Comput., 7(2):6:1-6:29 2019.
Haris Aziz, Bo Li, Hervé Moulin, and Xiaowei Wu. Algorithmic fair allocation of indivisible items: A survey and new questions. CoRR, abs/2202.08713. 2022.
340
Nikhil Bansal and Maxim Sviridenko. The santa claus problem. In STOC, pages 31-40, 2006.
342
Maksim Barketau, Erwin Pesch, and Yakov M. Shafransky. Minimizing maximum weight of subsets of a maximum matching in a bipartite graph. Discret. Appl. Math., 196:4-19, 2015.
Siddharth Barman and Sanath Kumar Krishnamurthy. Approximation algorithms for maximin fair division. ACM Trans. Economics and Comput., 8(1):5:1-5:28, 2020.
345
346
Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. The price of fairness for indivisible goods. Theory Comput. Syst. 65(7):1069-1099) 2021.
347
348
Vittorio Bild, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. In ITCS, volume 124 of L/Plcs, pages 14:1-14:21. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2019.
349
350
352
Anna Bogomolnaia and Matthew O. Jackson. The stability of hedonic coalition structures. Games Econ. Behav. 38(2):201-233 2002.
354
Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In IJCAI, pages 135-141. ijeai.org, 2017.
355
Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 1196));06111100; 2011.
357
Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. Recent advances in graph partitioning. In Algorithmm Engineering, volume 9220 of Lecture Notes in Computer Science pages 117-158. 2016.
359
361
Joannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable faimess of maximum nash welfare. ACM Trans. Economics and Comput., 12:1112::11 2019.
382
383
364
Catherine H Crouch and Eric Mazur. Peer instruction: Ten years of experience and results. American journal of physics, 69(9)997-9977, 2001.
366
Edith Elkind and Michael Wooldridge. Hedonic coalition nets. In AAMAS (1), pages 417-424. IFAAMAS, 2009.
368
Boaz Farbstein and Asaf Levin. Min-max cover of graph with a small number of parts. Discret. Optim., 16:51-61, 2015.
389
Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D Procaccia. Fair algorithms for selecting citizens' assemblies. Nature, pages 1-5, 2021.
371
372 D. K. Foley. Resource Allocation and the Public Sector. Yale Econ. Essays, 7, 1967.
Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. Artificial Intelligence, 300, 2021.
374
Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi
376
Yami. Fair allocation of indivisible goods: Improvements and generalizations. In EC, pages 539-556, 2018.
10

---

378
Jonathan R. Goldman and Ariel D. Procaccia. Spliddit: unleashing fair division algorithms. SIGecom Exch. 13(2):11-6,, 2014.
379
380
Ayumi Igarashi and Dominik Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In AAAI, pages 2045-2052. AAAI Press, 2019.
M. Reza Khani and Mohammad R. Salavatipour. Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica, 69(2):443-46)) 2014.
383
384
Çagii Kog, Tolga Bektas, Ola Jabali, and Gilbert Laporte. Thirty years of heterogeneous vehicle routing. Eur. J. Oper. Res., 249(1):1-21, 2016.
385
386
Dominik Kress, Sebastian Meiswinkel, and Erwin Pesch. The partitioning min-m max weighted matching problem. Eur. J. Oper. Res., 247(3):745-754, 2015.
387
D. Kurokawa, A. Procaccia, and J. Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM, 65(2):8, 2018.
389
390
Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In EC, pages 125-131. ACM, 2004.
I László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009.
393
394
Flávio Keidi Miyazawa, Phablo F. S. Moura, Matheus J. Ota, and Yoshiko Wakabayashi. Partitioning graph into balanced connected classes: Formulations, separation and experiments. Eur. J. Oper. Res., (93(3):2268866 2021.
395
Hervé Moulin. Fair division and collective welfare. MIT Press, 2003.
Sivakumar Rathinam, R. Ravi, J. Bae, and Kaarthik Sundar. Primal-dual 2-approximation algorithm for the monotonic multiple depot heterogeneous traveling salesman problem. In SWAT, volume 162 of L/Plcs, pages 33:1-33:13, 2020.
399
Warut Suksompong. Fairly allocating contiguous blocks of indivisible items. Discret, Appl. Math., 260:227-236, 2019,
402
403
Vera Traub and Thorben Tröbst. A fast (2 + apprroxppoinnnooonn algorithm for capacitated cycle covering. In IPCO, pages 391-404. Springer, 2020.
404
405
Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare allocation almost envy-free. In IJCAI, 2021.
Hande Yaman. Formulations and valid inequalities for the heterogeneous vehicle routing problem. Math. Program., 106(2):365-39) 2006.
408

---

Checklist
409
410
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
412
contributions and scope? [Yes]
413
(b) Did you descrihe the limitations of your work? [Yes]
414
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
416
417
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
419
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
422
423
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
425
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
426
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
428
429
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
430
(a) If your work uses existing assets, did you cite the creators? [N/A]
431
(b) Did you mention the license of the assets? [N/A]
432
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
434
(d) Did you discuss whether and how consent was obtained from people whose data you're ro using/curating? [N/A]
435
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
437
438
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
440
441
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
442
443
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "QZm7Rt1sdGI", "reviewer": "Reviewer_UCR6", "summary": "This paper studies a variant of the indivisible item allocation problem. In this variant, the items are vertices of an edge-weighted graph. An agent’s valuation on a bundle is given by the weight of the maximum weight matching on the subgraph induced by the vertices in the bundle. In the homogeneous setting, the same edge-weighted graph is defined as the valuation of all the agents. In the heterogeneous setting, different agents have different weights for the edges in the graph. The motivation of this model is that, in a company or a department, workers many need to work in pairs. Thus, if workers are viewed as items, an agent would like to have a set of pairs of workers so that the collective contribution for each pair of workers (modeled by the weight of the edge) is large.\n\nThe authors study MMS and EF1 allocations, and the design of approximation algorithm for optimizing the social welfare. Notice that the approximation ratio is not defined in its typical way in a constrained optimization problem. In particular, the social welfare output by the algorithm is not compared with the optimal social welfare *subject to MMS/EF1*; instead, it is compared with the optimal social welfare without any fairness constraint. This is like the algorithm-design aspect of the “price of fairness”. I think this is also okay.\n\nFor the homogeneous setting, the authors provide a greedy-based algorithm that output a 1/8-MMS allocation. This is done by a combination of multiple techniques, including the greedy technique in the scheduling-like problems, the rounding of edge weights to integer powers of 2, and the treatment of the hard special case where the maximum-value bundle contains a single matching edge. The authors also present an algorithm that returns an EF1 allocation with social welfare at least about 2/3 of the optimal social welfare. For the heterogeneous setting, the authors show that MMS cannot be satisfied for any bounded approximation ratio, even for two agents with binary weight functions. The authors also show that there is a gap of 1/n between the optimal social welfare and the best social welfare subject to EF1. However, for EF1, the authors present some nice positive results for 1) binary edge-weights and 2) two agents. In both special cases, we can obtain an EF1 allocation with 1/3 approximation to the optimal social welfare. Most technical details of these results are deferred to the appendix.\n", "questions": " For the result with 1/8-MMS, do you have any tight examples?", "limitations": "The authors have addressed this in the conclusion section, where a list of future directions is provided. I think this is satisfactory.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The results are relatively complete for both the homogeneous setting and the heterogeneous setting. For MMS, we know it is achievable (with a constant factor approximation) for the homogeneous setting, but the price of MMS is unbounded; we know it is not achievable in the heterogenous setting. For EF1, it is always achievable. The price of EF1 is low for the homogeneous setting, and it is high for the heterogeneous setting. The authors also have completed the results for the two special cases with 1) binary edge-weights and 2) two agents. We know MMS is not achievable even when both 1) and 2) hold, and price of EF1 is low if either 1) or 2) holds. I would say the results are quite complete.\n2. The 1/8-approximation algorithm for MMS is a neat one, although it is not very technically complicated. I have not checked the details in the appendix, so I am uncertain about the technical novelty for the remaining results. Nevertheless, it seems to me that there are some technical novelty for this paper.\n\nWeakness:\n1. My main concern to this paper is its model. I feel like the problem studied is too specific and the model has limited applications. I could understand the motivation provided by the authors. However, I still believe there are not a lot of practical scenarios where workers have to work in *pairs*. Why not groups of three or four, or even larger?\n2. The complexity results (e.g., hardness-of-approximation) are mostly absent from this paper. The authors provide many tight examples for the approximation algorithms designed in this paper. I think this paper could be improved by a lot if some lower-bound results can be proved. However, I do not view this as a major weakness of the paper.\n\nOverall, I think this is a borderline paper for a strong conference like NeurIPS. I like the fact that the results form a relatively complete landscape, and I also like the techniques behind those algorithms. On the other hand, I am uncertain about the significance of the problem studied in the paper (as I have addressed in 1 of “weakness”). I can see the motivation the authors provided, and I am convinced that the model may have some applications. However, I still do not think it is significant enough.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NMLd8DxhEnT", "reviewer": "Reviewer_JkrW", "summary": "This paper studies mechanisms for the graphical resource allocation problem with two types of fairness: approximate maximin share (MMS) and envy-freeness up to one item (EF1). The problem is defined as follows: the resources are represented as nodes in an undirected graph, and the goal is to allocate (or partially allocate) the nodes to n agents. Each agent has an edge weight function for each edge in the graph, and an agents’ utility on one partition is the weight of a maximum matching in the subgraph induced by the nodes in the partition. \n\nThe authors first consider a setting of homogeneous agents that all agents have identical valuation functions. They show that a naive greedy partition is an MMS allocation for unweighted graphs, but does not have any bounded approximation guarantee in more general cases. Then they propose an algorithm that computes a ⅛-MMS allocation in polynomial time. Because any bounded approximation ratio for MMS fairness could have unbounded social welfare loss, EF1 is also studied to preserve high social welfare while having fairness guarantee. Theorem 3.6 shows that a polynomial time algorithm returns an EF1 allocation with an approximate optimal social welfare.  \n\nFor agents that have heterogeneous valuation functions, the authors first show some negative results that no algorithm has bounded approximation for MMS and no algorithm has better than 1/n approximation of social welfare for EF1 fairness. Then they consider two special cases: 1, when the agents have binary weight functions, Algorithm 3 returns an EF1 allocation with 1/3 -approximate social welfare. 2, In the case that there are only two agents, Algorithm 4 returns an EF1 allocation with a tight ⅓ approximation ratio to the optimal social welfare.\n", "questions": "* Are there more closely related works that combine graph partition and fair division together? See my comments in “Strengths And Weaknesses”.\n* Could you give some lower bounds of the results? See my comments in “Limitations”. \n* Page 5, line 198: “The approximation ratio is at least 1/4”. By Lemma 3.3, why isn’t the approximation ratio ½?\n", "limitations": "One thing could make this paper stronger is to have more lower bound results. Theorem 4.4 showed that the 1/3 -approximation to social welfare with EF1 is tight, but most of the results in this paper are without lower bounds. It would be interesting to see some lower bounds, even loose ones. The authors have addressed this in Section 5 “Future Directions”.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Originality: This work proposes a setting of fair division on indivisible graphical items where agents have combinatorial valuations. Two commonly used fairness concepts MMS and EF1 are studied. Related works on graph partition and fair division are properly cited. I do wonder if there are more closely related works that combine graph partition and fair division together?\n* Quality: The notations are well defined. The theorems / lemmas are neatly presented and proved. \n* Clarity: This paper is well written and organized. Some minor comments:\n  * Page 1, line 15: “ensuring constant fraction” -> ensuring a constant fraction\n  * Page 2, line 49: “significant amount of” -> a significant amount of\n  * Page 2, line 53: “widely accepted and studies” -> widely accepted and studied\n  * Page, line 83: “for two-agent case” -> for the two-agent case\n  * Page 9, line 295 “smallest ” -> the smallest; page 9 line 302: “second smallest ” -> the second smallest\n* Significance: The results in both the homogeneous and heterogeneous settings are interesting and could be building blocks for future works in this line.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DlfpV41Mdyz", "reviewer": "Reviewer_Vymq", "summary": "The paper considers a new variant of fair resource allocation problem: given a set of resources as vertices of a graph, the goal is to partition the resources among N agents -- an agent utility is given by the maximum matching on the induced subgraph of his partition. They consider two fairness measures on the utilities received by each agent : max min share (MMS) - where the minimum utility of agents is maximized, envy free upto one item (EF1) - where the no agent envies others' allocation after removing upto one item.\n\nThe main results of the work are the following: a 1/8 approximation algorithm for MMS version of the problem where all the agents are identical and a constant approximation for the EF1 variant. The work also gives some hardness results and better approximation in certain special cases.", "questions": "As mentioned above, the authors must address two issues with the paper: are there any real motivating examples/usecases for the problem? Secondly, what is the key central novel contribution of the work. ", "limitations": "N/A", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is reasonable well written and easy to follow. Unfortunately, there are multiple severe issues with it.\n\nFirstly, I am really not convinced of the motivation behind defining the problem. The motivating example of \"pairing up employees\" is really weak and sounds made-up to fit the problem definition. \n\nIn spirit of a theoretical work, the motivation can be ignored if there are sufficiently interesting results. Unfortunately, the algorithms and analysis is just a rehashing of existing ideas. \n\nFor instance, for the MMS version of the problem, the approach is to find a maximum matching followed by a decomposition of the independent edges. This is really the first approach one can think of and in fact, putting aside the paper, I came up with it myself in 5 mins. The paper then elaborates a way to decompose the independent edges in N parts. But this is a standard problem in approximation algorithms used for example load-balancing and several other scheduling problems. Indeed, in bin packing, adding items to lowest occupied bin yields a simple 2-approximation and these results are known from the 1960s. Spending 2-3 pages on this result really underlines the technical inferiority of the work. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CPlFahNUQ3q", "reviewer": "Reviewer_N528", "summary": "This paper deals with a novel variant of the fair division problem which deals with the allocation of indivisible items to multiple agents with complementarities. Each agent’s valuations are given by a weighted undirected graph where there is a node for each item and the edge weights correspond to the value the agent receives when the items corresponding to the end points of the edge are paired together. The value for a bundle of items is given by the total value of the maximum weight matching that can be obtained in the subgraph induced by the nodes corresponding to the items in the bundle. The authors motivate this setting by the example of departments (agents) in an engineering firm having to pair up the engineers (resources / items) assigned to the department, and other settings where employees must be paired to achieve tasks that generate positive value.\n\nThe main results deal with computing fair, i.e., envy-free up to one item [EF1] and maximin-share [MMS], and efficient, i.e., social welfare maximizing, allocations of items to agents. The authors provide several interesting positive and negative results on efficiently computing allocations that guarantee a (fraction of) agents’ MMS share or total social welfare under constraints such as guaranteeing EF1 under settings with homogeneous (all agents have identical valuation functions / graphs) or heterogeneous (agents have possibly different valuations) agents.", "questions": "No significant questions. Please see detailed comments.", "limitations": "The authors do not identify the societal impact of this work. [Neutral]", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n[Conceptual contributions]\n+ The setting is novel and possibly interesting to the overall research community studying fair division of indivisible items.\n+ The proposed model presents interesting directions for future work, as the authors note. In particular, other valuation functions that depend on the subgraph induced by the items in a bundle open several interesting possibilities.\n\n[Technical contributions]\n+ The theoretical results are non-trivial and the proof sketches in the main body are convincing.\n+ The results in the paper are therefore a good first step.\n\nWeaknesses:\n- [Relevance] I am struggling to find the relevance to NeurIPS, although I will leave this matter for later discussion, and have not allowed it to affect my final recommendation at this time.\n- [Motivation] The motivating examples are unconvincing and lack any citations or references. For example, the authors claim that the motivating problem of a company with departments who have preferences over how to pair engineers is a real-world scenario. I think I understand what they refer to, but the authors provide no formal references or citations.\n- [Significance] While the technical results are interesting, due to the poor presentation, the significance of the results is not clear.\n\n[Presentation]\n- Poor quality of writing overall. See detailed comments below.\n- Several theorem statements are imprecise. Detailed comments below.\n- Several arguments are vague. I understand that there is a space limitation, but perhaps this can be revised in a future iteration. Detailed comments below.\n- There are some interesting technical results, but perhaps the most interesting and significant results can be highlighted more prominently. In particular, the results for heterogeneous agents on the \"price of EF1\" in terms of social welfare and impossibility of guaranteeing any constant fraction of the MMS share are interesting negative results.\n- A conjecture is presented in the Section 1.1 that an EF1 and social welfare maximizing allocation always exists but no argument is provided in the relevant Section 3.2 [I apologize if I missed it, and am happy to be corrected].\n\nDetailed comments:\n\n[Writing]\n- L1: Motivated by the real ... - > Motivated by real ...\n- L4: We care both ... -> Consider revising\n- L5: Regarding MMS ... -> Consider revising\n- L5: ... does not admit finite ... -> ... does not admit a finite ...\n- L20-22: Needs more explanation or context of what is meant by a graphic resource (especially i did not understand how graph neural networks are relevant here)\n- L23-26: Please cite some references (e.g. related work) for this motivating example. Also, the work on hedonic games may be relevant to discuss at some point.\n- L52-56: EF1 was proposed by Budish, 2011 (later) and proven to always exist by Lipton et al., 2004. This is confusing. I am familiar with the literature. Perhaps there is a better way to write this?\n- L127: ... if the weight function is highlighted. Consider revising this sentence.\n- L128-132: The imaginary experiment leaves some questions, and can perhaps be made more precise. From the description, it is not clear if the agent has knowledge of other agents' valuations and therefore of how other agents will pick the partitions. AFAIK, MMS is defined for the worst-case. Perhaps it is better to describe it as the maximum value the agent can have for the worst partition in any n-partitioning. And not involve the selections of other agents.\n- L136: ... if for all agent ... -> ... if for all agents ...\n- L137: ... is called MMS fairness ... -> ... is called MMS fair ...\n- L143: Accordingly, people mostly ... - > Please consider revising\n- L145: The line claims that EF1 is widely accepted and studied. But no citations or references are provided. I suggest that this be motivated and discussed earlier (e.g. Introduction or Related Works) and not repeated here, and only formal definitions and helpful examples be provided in the Preliminaries.\n- L199: ... decent ... -> Not clear what this means\n- L200: ... far smaller ... -> Consider revising\n- Algorithm 3: The comments for the different cases are not made consistently. Please consider revising.\n- L299: ... if so we do exchange ... -> Please consider revising.\n- L302: ... and so on so forth. -> ... and so on.\n\n[Theorem statements]\n- L164: I believe this only applies to the case of homogeneous agents, which is not clear from the theorem statement.\n- L222: ... two cases happens. -> ... two cases hold true. (or something similar)\n- L268 and L270: Please consider specifying that this is for the case of heterogeneous agents.\n- L297: ... j envies i ... -> ... j envy i ...\n- L304: Please clarify whether this result only holds for binary weights.\n\n[Arguments]\n- L158-160: Please consider making this more precise and providing a brief argument and cite the (variant of the) Partition problem.\n- L169: This task is NP-hard ... -> Why? [I think I know why] Please specify and consider rewriting to avoid repetitions.\n- L188-190: I don't think this statement is as helpful as it was perhaps intended to be. It is too vague.\n- L211: Not clear what optimal means here (could be MMS or max SW). Is O any MMS allocation?\n- L226-227: Please consider revising this. It is hard to parse this sentence.\n- L245: In the equation, please consider revising: for any v ... -> for every v ... Currently, it reads like EFX\n- L254-261: Please consider using a proof sketch environment if possible and avoid mixing descriptions of the algorithm with the proof.\n- L271 and Theorem 4.1: Please consider including the here, since it is indeed a strong negative result.\n- L293: It is not clear why this matters. Please consider revising and illustrating this with an example.\n\n[Others]\n- Algorithm 1: It appears that e_1 is always the highest weight edge (due to it being the only edge in M_1) and in line 5, H is the set of all highest weight edges.\n- Line 290: Please consider providing an example here.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject