Bargaining for Revenue Shares on Tree Trading Networks

1 Introduction

[Demko and Hill, 1988] addressed the problem of equitably allocating a set of indivisible goods to n agents (n ≥ 2). The agents have possibly different utilities for the individual goods, and an agent's utility for a bundle B is defined as the sum of individual utilities for the goods in B. After a normalization, it is assumed that everyone has utility 1 for the whole set of goods.

Demko and Hill's work focused on how good the least happy agent can value his share. It is to find a threshold tn ∈ [0, 1] such that, in any case, there exists an allocation where each of the n agents has utility at least tn for his share. To be complete, tn should come with a family of instances without any feasible allocation where everyone values his share tn + ϵ (or more) for some positive ϵ.

∗This research has been supported by the project ANR-09BLAN-0361 GUaranteed Efficiency for PAReto optimal solutions Determination (GUEPARD).

In the context of sharing divisible goods, it is long known that tn = 1/n [Steinhaus, 1948]. Dealing with indivisible goods leads to a trickier situation. As a devastating example, imagine n agents having utility 1 for the same item, say i1, and utility 0 for any other item. The agents who do not receive i1 have a global utility of 0, meaning that tn equals to 0. Meanwhile, if the maximum utility for a good was upper bounded by a quantity tending to 0, the indivisible model would gradually tend to the divisible model, where tn = 1/n. Then, what is tn between these two extremal cases?

In fact, the maximum value for a single element appears to significantly influence tn, as in the pioneering work of [Hill, 1987] who defined a family of nonincreasing functions Vn : [0, 1] → [0, n-1 ] for any integer n ≥ 2 (see Definition 1 and Figure 1). Following [Hill, 1987], [Demko and Hill, 1988] considered the parameter α ∈ [0, 1], defined as the maximum value assigned by an agent to a single good, and showed that it is possible to allocate the indivisible goods to n agents such that every agent's valuation for his share is at least Vn(α). In addition, they showed with some instances that Vn is exactly the best utility of the least happy agent for some values of α, but the instances do not cover the entire interval [0, 1].

Defining αi as agent i's maximum valuation for a single item, [Markakis and Psomas, 2011] have recently strengthened the results of Demko and Hill. Indeed, they show the existence of an allocation guaranteeing Vn(αi) for every agent i. Since Vn is nonincreasing, Vn(αi) ≥ Vn(α) holds and the vector (Vn(αi))i∈[n] weakly Pareto dominates (Vn(α))i∈[n] . The other contribution of Markakis and Psomas relies on the fact that, unlike the results in [Hill, 1987; Demko and Hill, 1988], the allocations are obtained with a deterministic algorithmwhich runs in polynomial time.

Our work deals with a problem which encompasses the allocation of indivisible goods. It is a problem on a matroid (defined in Section 3) where one has to find a common solution (base) to n agents. The agents have possibly different utilities for the elements of the matroid, and an agent's utility for a solution B is defined as the sum of individual utilities for the elements in B. After a normalization ensuring that the maximum utility for a solution of the matroid is exactly 1 for everyone, we define αi as the maximum value that agent i assigns to a single element, and α = maxi∈[n] αi.

Interestingly, we show that Vn is still valid in this generalized context and we can even improve it. We propose a family of functions Wn : [0, 1] → [0, n-1 ] defined for any positive integer n (see Definition 2). We have Wn(x) ≥ Vn(x) for all x ∈ [0, 1], and Wn(x) > Vn(x) for values of x where Vn(x) is not tight (see Figure 1 for illustration). Like Vn, Wn is piecewise linear on [0, 1] but unlike Vn, Wn alternates decreasing and increasing phases. This gives a new insight in the particularity of handling indivisible objects.

We also propose a deterministic algorithm which is an extension of the one in [Markakis and Psomas, 2011] for the generalized problem on matroids. The algorithm returns a solution (base) where every agent i has utility at least Wn(αi).

In all, our contribution consists of dealing with matroids which capture more situations than the basic model of allocating indivisible goods, the new functions Wn improve on Vn, and the solution is built by a polynomial time algorithm.

The rest of the article is organized as follows. In section 2, we discuss some related work. In order to be self-contained, we give basic notions on matroids in Section 3. Section 4 introduces the model that we deal with. In section 5, we present a polynomial time algorithm which provides a solution in which every agent i receives at least Wn(αi). Due to lack of space, some parts of proofs are omitted. Further results and future directions are given in Section 6.

2 Related work

Sharing scarce resources like food, energy or jobs is a very old, but never outdated, issue. From the various fields where this problem is addressed, the recurrent challenge is obviously to reach fairness and efficiency.

Fair division is to allocate a set of goods to a set of n agents, having heterogeneous valuations, in a way that leaves every agent satisfied. It is extensively studied in economics (especially social choice theory), mathematics and political science. However, computer science (CS) comes naturally into play when the computational aspects of allocation procedures are investigated [Chevaleyre et al., 2007]. During the last few years, the CS community (especially in Artificial Intelligence) has shown a growing interest in the topic [Bouveret and Lang, 2008; Procaccia, 2013].

The literature on fair division usually distinguishes the case of divisible goods (e.g. cakes) and the case of indivisible goods (e.g. houses) [Young, 1994; Brams and Taylor, 1996; Moulin, 2003]. Typically desired properties are proportionality (each of the n agents gets at least a proportion of 1/n of the goods) and envy-freeness (every agent weakly prefers his share to the share of any other agent).

Proportionality for n agents (Banach-Knaster [Steinhaus, 1948]) and envy-freeness can be reached in the divisible case [Brams and Taylor, 1995] but it is not true for indivisible goods. Instead, one can seek for allocations that minimize envy [Lipton et al., 2004] or maximize the utility of the least happy agent [Asadpour and Saberi, 2010]. These approaches lead to computationally hard optimization problems.

Another approach for indivisible goods is to determine a value, and guarantee the existence of an allocation such that the relative utility of the poorest agent is at least this value. This is the path followed by [Demko and Hill, 1988] on the basis of [Hill, 1987]. Recently, [Markakis and Psomas, 2011]

proposed a deterministic algorithm for computing such a solution in polynomial time. From a computational perspective, this task is less demanding than the maximization of the poorest agent's utility.

3 Matroids

Matroid theory is central in combinatorial optimization. In particular, it has permitted to unify apparently separated structures like trees and matchings in a graph. In order to be selfcontained, we give some basic notions on matroids. An interested reader may refer to [Schrijver, 2003; Korte and Vygen, 2007; Oxley, 1992] for more details.

A matroid M = (X, F) consists of a finite set of elements X and a collection F of subsets of X such that:

• (i) ∅ ∈ F,
• (ii) if F2 ⊆ F1 and F1 ∈ F then F2 ∈ F,
• (iii) for every F1, F2 ∈ F where |F1| < |F2|, ∃ e ∈ F2\F1 such that F1 ∪ {e} ∈ F.

The elements of F are called independent sets. Inclusionwise maximal independent sets are called bases. All bases of a matroid M have the same cardinality r(M), defined as the rank of M. Given a matroid M = (X, F) and a subset X′ ⊂ X, if X′ ∈ F, the contraction of M by X′ , denoted byM/X′ , is the structure (X \ X′ , F ′ ) where F ′ = {F ⊆ X \ X′ : F ∪X′ ∈ F}. It is well known that M/X′ is a matroid.

A typical example of a matroid is the forests (acyclic set of edges) of a multigraph G, usually called the graphic matroid. The bases are the spanning trees if the graph G is connected.

Another example is the partition matroid: given k disjoint sets P1, . . . , Pk which form a ground set P = ∪ki=1Pi and k nonnegative integers bi (i = 1..k), the sets F ⊆ P satisfying |F ∩ Pi| ≤ bi form a matroid. Notably (and it is crucial in the present work), allocating a set of m indivisible items to n agents can be seen as a partition matroid. Build m sets Pi = {i1 , i2 , . . . , in} and let bi = 1 for i ∈ [m]. Taking ik means allocating item i to agent k.

Last example of a well known matroid is the "matching" matroid defined over a graph G = (V,E): take X = V and define F as the subsets of V which can be covered by a matching of G.

When every element e ∈ X has a weight w(e) ∈ IR+, a classical optimization problem consists in computing a base B ∈ F that maximizes ∑e∈B w(e). This problem is solved in polynomial time by the famous GREEDY algorithm (also known as Kruskal's algorithm for the maximum weight spanning tree problem) described in Algorithm 1.

Let us give here a general lemma that we will find useful in Section 5.

Lemma 1 Let M = (X, F) be a matroid and a function w : X → IR+ such that w(X′ ) = ∑e∈X′ w(e), ∀X′ ⊆ X. Given F1, F2 ∈ F where |F1| < |F2|, suppose that F2 = {e1 , . . . , e|F2|} with w(e1 ) ≥ · · · ≥ w(e|F2| ). In the contracted matroid M/F1, ∃E ⊆ F2\F1 such that E is independent inM/F1 (i.e. F1 ∪E ∈ F) where |E| = |F2|-|F1| and w(E) ≥ w ({e|F1|+1 , . . . , e|F2|}).

Proof. By induction on k = |F2| - |F1|, we prove that there is an independent set Ek satisfying the lemma.

For k = 1, from property (iii) of matroids, ∃e ∈ F2\F1 such that F1 ∪ {e} ∈ F. Since w(e1 ) ≥ · · · ≥ w(e|F2| ), then w(e) ≥ w(e|F2| ). Hence, E1 = {e}.

We assume that Lemma 1 is true for k ≥ 1 and we show it for k + 1. Let F1, F2 ∈ F such that |F2| - |F1| = k + 1, F2 = {e1 , . . . , e|F1|+k+1} and w(e1 ) ≥ ... ≥ w(e|F1|+k+1 ). Let F ′2 = F2\{e|F1|+k+1}. Using the inductive hypothesis, ∃Ek ⊆ F ′2\F1 in the contracted matroid M/F1 such that F1 ∪ Ek ∈ F, |Ek| = |F ′2 | - |F1| = k and w(Ek) ≥ w ({e|F1|+1 , . . . , e|F1|+k }).

Consider the sets F1 ∪Ek and F2 where |F1 ∪Ek| = |F1|+k and |F2| = |F1| + k + 1. From property (iii) of matroids, ∃e ∈ F2\(F1 ∪ Ek) such that F1 ∪ Ek ∪ {e} ∈ F. In other words, Ek ∪ {e} is an independent set of M/F1. Since w(e1 ) ≥ · · · ≥ w(e|F1|+k+1 ) then, w(e) ≥ w(e|F1|+k+1 ). Let Ek+1 = Ek ∪ {e}. Hence, w(Ek+1) ≥ w ({e|F1|+1 , . . . , e|F2|}) as claimed. ✷

Algorithm 1 GREEDY

Require: M= (X, F), w : X → IR+

• 2: F ← ∅

3: for i = 1 to |X| do

4:

if F ∪ {ei} ∈ F then

5: F ←F ∪ {ei}

• 6: end if
• 7: end for
• 8: return F

The time complexity of matroid algorithms depends of the difficulty of testing if a set F ∈ F. This is usually done by a dedicated subroutine called the independence oracle. We always assume that this subroutine runs in polynomial time.

4 The model

We are given a matroid M = (X, F), a set of agents N = {1, ..., n} and ui(e) ∈ IR+ for every pair (i, e) ∈ N × X. Actually, ui(e) is the utility of agent i for the element e. With a slight abuse of notation, the utility of an agent i ∈ N for a subset X′ of X is denoted by ui(X′ ) and defined as ∑x∈X′ ui(x). As a convention, ui(∅) is equal to 0.

Agent i prefers the solutions (bases) that maximize ui. One of these solutions, denoted by B∗ i , can be built by the GREEDY algorithm. We can assume that B∗ i is a base of M because utilities are nonnegative. We suppose w.l.o.g. that every base B∗ i optimal for agent i satisfies ui(B∗ i ) = 1. This normalization allows to capture the agents' relative utilities instead of their absolute utilities. If ui(B∗ i ) ̸= 1 for some agent i, it suffices to replace ui(e) by ui(e)/ui(B∗ i ) for all e ∈ X. This is trivially done in polynomial time.

Throughout the article, we use αi = max{e}∈F ui(e), the maximal utility that agent i has for an element of the matroid and α = maxi∈N αi, the maximal utility assigned to an element of the matroid, over all agents.

Following [Demko and Hill, 1988], we are interested in determining a value tn such that, in any case, there exists a solution B ∈ F satisfying ui(B) ≥ tn, ∀i ∈ N. As done in [Markakis and Psomas, 2011], a strengthening of this result would be a vector (ti,n)i∈N such that, in any case, there exists a solution B of the matroid with ui(B) ≥ ti,n ≥ tn, ∀i ∈ N.

Since our model extends the one in [Demko and Hill, 1988; Markakis and Psomas, 2011], parameters α and αi play an important role in the determination of tn and (ti,n)i∈N .

In Section 3, we see that the allocation of indivisible goods is a particular case of our model. A possible application of the matroid model, that allocation of indivisible goods cannot cover, is the following: consider a bipartite graph (A∪T,E) whose node sets A and T correspond to a set of activities and a set of time slots, respectively. At most one activity can be scheduled during a time slot and there is an edge (a, t) ∈ E iff activity a is available during time slot t. It is possible to schedule a subset of activities A′ if there exists a matching covering A′ . As mentioned in Section 3, the subsets of A for which a feasible schedule exists, form a matroid. In the presence of n agents having heterogeneous utilities for the activities, it is relevant to seek for a common set of activities that is feasible and fair.

5 Technical results

Let us begin by defining the function Vn of Hill.

Definition 1 [Hill, 1987; Markakis and Psomas, 2011] Given any integer n ≥ 2, let Vn : [0, 1] → [0, n-1 ] be the unique nonincreasing function satisfying Vn(x) = 1/n for x = 0, whereas for x > 0:

[Markakis and Psomas, 2011] produce an allocation such that each agent i receives at least Vn(αi) which is tight in I(n, p). We define a new function Wn.

Definition 2 Given any integer n ≥ 1, let Wn : [0, 1] → [0, n-1 ] be the function satisfying W1(x) = 1, ∀x ∈ [0, 1], whereas for any integer n ≥ 2,

Note that I(n,p) ̸= I(n, p). In the following, we use only the intervals defined in Definition 2. We see that Wn(x) > Vn(x) for intervals I 2 (n,p) and I 3 (n,p) , and Vn(x)=Wn(x) elsewhere.

The following properties can easily be proved:

Property 1 Given any integers n ≥ 2 and p ≥ 1,

Now, we present Algorithm 2 which constructs a base (solution) by executing THRESHOLD(N,M, (ui)i∈N, ∅).

Algorithm 2 THRESHOLD

Require: N,M= (X, F), (ui)i∈N, B 1: for all i ∈ N do 2: B∗ i ←GREEDY(M, ui) 3: for all e ∈ X do 4: ˜ui(e) ← ui(e)/ui(B∗ i ) 5: end for 6: αi ← max {e}∈F ˜ui(e) 7: Si ← ∅ 8: add in a greedy manner elements of B∗ i to Si by nonincreasing order of ˜ui until ˜ui(Si) ≥W|N|(αi) 9: end for 10: pick i ∈ N such that |Si| ≤ |Sk|, ∀k ∈ N 11: Bi ←Si 12: B ←B ∪Bi 13: if |N| = 1 then 14: return B 15: else 16: let M/Bi = (X\Bi, ˜ F) be the contraction of M to Bi where F ∈ ˜ F iff F ∪Bi ∈ F 17: THRESHOLD(N\{i}, M/Bi, (˜uk)k∈N\{i}, B) 18: end if

THRESHOLD is an adaptation of the algorithm of [Markakis and Psomas, 2011] on matroids. Our algorithm sorts the set X, this is done in O(|X| ln |X|), then tests the independence of adding elements of X to the solution, done in O(θ|X|), where θ is the complexity of the independence oracle. Since we repeat these steps n times (induction), the complexity of THRESHOLD is O(n|X|max{ln |X|, θ}). θ is not given explicitly, it depends on the matroid under consideration. In our study, we suppose that θ is a polynomial.

In the rest of the paper, we always assume that agent i has been selected during the i-th call of THRESHOLD. So, B = B1∪· · ·∪Bi and the contracted matroid isM/(B1∪· · ·∪Bi) at the end of the i-th call. At the end of the n-th call of THRESHOLD, B = B1 ∪ · · · ∪ Bn and it is a base of M because during the n-th call, the algorithm adds by construction an independent set which is a base of M/(B1 ∪ · · · ∪Bn-1).

Example 1 Consider a set of agents N = {1, 2} and the graphic matroid defined over a connected graph G = (V, E), illustrated by Figure 2. The aim is to find a common base to 2 agents with a guarantee on the utility of each one. In the graphic matroid of G, a base corresponds to a spanning tree.

During the first call of THRESHOLD, we have B∗ 1 = {(v1, v2), (v2, v3), (v4, v5), (v5, v1)} and B∗ 2 = {(v2, v3), (v1, v3), (v3, v4), (v5, v1)} with u1(B∗ 1 ) = 8 and u2(B∗ 2 ) = 10 where B∗ i corresponds to a maximum spanning tree in (G, ui) (for instance, by applying GREEDY or Kruskal's algorithm). The algorithm normalizes utilities ui(e) to get ˜ui(e) = ui(e)/ui(B∗ i ), ∀i ∈ {1, 2}, ∀e ∈ E. Then, α1 = 3/8 ∈ I 3 (2,1) and α2 = 3/10 ∈ I 1 (2,2) . So, W2(α1) = α1 = 3/8 and W2(α2) = 1 - 2α2 = 4/10. Now, each agent i ∈ {1, 2} builds a forest Si by adding the heaviest edges of B∗ i until ˜ui(Si) ≥ W2(αi). We find S1 = {(v1, v2)} and S2 = {(v2, v3), (v1, v3)}. Since |S1| < |S2|, we have i = 1, B1 = S1 and B = B1.

Now, let G/B1 be the new graph obtained by contracting edge (v1, v2) of B1 into vertex v1,2 as it is done in Figure 3.

The utilities of agent 1 are omitted because he has already chosen his edges. Recall that the second agent's utility has been normalized during the first call of THRESHOLD ˜u2(e) = u2(e)/u2(B∗ 2 ). Let ˜B∗ 2 be an optimal base of the contracted matroid (G/B1, ˜u2). During the second call of THRESHOLD, the algorithm finds ˜B∗ 2 = {(v1,2, v3), (v3, v4), (v5, v1,2)} with ˜u2( ˜B∗ 2 )=7/10. Now, the utilities of agent 2 are normalized ˜˜u2(e)=˜u2(e)/˜u2( ˜B∗ 2 ) and ˜α2=3/10 ∗ 10/7=3/7. Then, agent 2 builds a forest ˜ S2 by adding the heaviest edges of ˜B∗ 2 until the threshold ˜˜u2( ˜ S2)≥W1(˜α2)=1 is reached. So, B2 = ˜B∗ 2 and finally THRESHOLD returns B = B1 ∪ B2 = {(v1, v2), (v2, v3), (v3, v4), (v5, v1)} where u1(B) = 7 ≥ W2(α1)u1(B∗ 1 ) and u2(B) = 8 ≥ W2(α2)u2(B∗ 2 ).

Theorem 1 THRESHOLD returns a base B which satisfies ui(B) ≥ W|N|(αi)ui(B∗ i ) for all i ∈ N.

Proof. Let n = |N| and recall that the base returned by THRESHOLD is B = B1 ∪ · · · ∪ Bn.

Actually, we will prove, by induction on n, a stronger result: ui(Bi) ≥ Wn(αi)ui(B∗ i ), ∀i ∈ N. Because the utilities are nonnegative, we conclude ui(B) ≥ ui(Bi).

For n = 1, line 8 of THRESHOLD is equivalent to applying GREEDY(M, u1) to get the base B = B1 = B∗ 1 which satisfies: ˜u1(B1)≥W1(α1)=1 because W1(x)=1, ∀x ∈ [0, 1]. Thus, u1(B1) = W1(α1)u1(B∗ 1 ).

Let n ≥ 2. We assume that r(M) ≥ n because otherwise all bases have size at most n - 1 and then, ∀i ∈ N, αi ≥ 1/(n - 1). In this case, ∀i ∈ N, Wn(αi) = 0 and the result is trivially satisfied.

For similar reasons, we assume that αi < 1/(n-1), ∀i ∈ N because otherwise, for agents i with αi ≥ 1/(n - 1), we get Wn(αi) = 0 and the bounds of agents i are clearly satisfied. W.l.o.g., we assume that agent 1 has been selected first. So, B1 = S1 and

In order to avoid confusion between the notations during first and second calls of THRESHOLD, we add a tilde for the notations used during the second call of THRESHOLD (like it is done in Example 1). Hence, ˜N = N \ {1}, ˜ui(e) = ui(e)/ui(B∗ i ), ˜M = M/B1 = (X\B1, ˜ F) and ˜B∗ i is an optimal base of ( ˜M, ˜ui). Moreover for i ∈ ˜N, ˜˜ui(e) = ˜ui(e)/˜ui( ˜B∗ i ) for the elements e ∈ X\B1 of ˜Mand ˜αi = max{e}∈ ˜ F ˜ui(e).

The inductive hypothesis affirms that

and we want to show that ui(Bi)≥Wn(αi)ui(B∗ i ), ∀i ∈ N or equivalently ˜ui(Bi) ≥ Wn(αi), ∀i ∈ N. By construction of THRESHOLD, during the first call we have (lines 3-8):

Since B1 = S1, then by (3), we get the expected result for agent 1. In addition, since the sets Si = {e1i , . . . , e|Si| i } are minimal for inclusion, we deduce:

Let k ∈ ˜N. We decompose B∗ k = B∗1 k ∪B∗2 k such that B∗1 k contains the |B1| first largest elements of B∗ k . It is possible because of (1) and recalling that Sk ⊆ B∗ k . Hence, B∗1 k ⊆ Sk and

Since for n ≥ 2, Wn(x) ≤ 1/n ≤ 1/2 (see 1. of Property 1) and r(M) ≥ n ≥ 2, we must have |B1| < |B∗ 1 | = |B∗ k | (all the bases have the same size r(M)). We can prove it by contradiction: assume |B1| = |B∗ 1 |. Since S1 =B1 and S1 ⊆B∗ 1 , we have S1 = B1 = B∗ 1 so, ˜u1(S1)=˜u1(B∗ 1 ) = 1. By (4), ˜u1(S1\{e|S1| 1 }) = ˜u1(S1) - ˜u1(e|S1| 1 ) = 1 - ˜u1(e|S1| 1 ) < Wn(α1) ≤ 1/2 so, ˜u1(e|S1| 1 ) > 1/2. Since |S1| = r(M) ≥ 2 and S1 is sorted by nonincreasing order of ˜u1, we get ˜u1(S1) ≥ 2˜u1(e|S1| 1 ) > 1which is a contradiction.

Hence, we can apply Lemma 1 for M, w = ˜uk, F1 = B1 and F2 = B∗ k . We deduce that there exists E ⊆ B∗ k \B1 such that B1 ∪ E ∈ F where |E| = |B∗ k | - |B1| = |B∗2 k | and ˜uk(E) ≥ ˜uk(B∗2 k ). E is an independent set of ˜M = M/B1 whereas ˜B∗ k is a base of ˜M maximum for ˜uk. So, ˜uk( ˜B∗ k ) ≥ ˜uk(E) ≥ ˜uk(B∗2 k ). Due to the normalization, we get ˜uk( ˜B∗ k ) ≥ 1 - ˜uk(B∗1 k ). From (5) and the previous inequality, it holds that:

and by (2) and (6),

Now, from line 6 of THRESHOLD, we know that:

By (6), the last inequality becomes

Let pk∈IN∗ such that αk∈I(n,pk) (see Definition 2).

We first show that |Sk| ≥ pk. By contradiction, suppose that |Sk| ≤ pk - 1. Then, by the definition of αk, ˜uk(Sk) ≤ (pk - 1)αk. Using 3. of Property 1, we get (pk - 1)αk < Wn(αk) which leads to a contradiction with (3). Now, we distinguish two cases: |Sk| = pk and |Sk| ≥ pk + 1.

Case 1: |Sk| = pk. Line 6 of THRESHOLD implies that ˜uk(Sk) ≤ pkαk. Inequality (7) becomes

and by (8),

So, either ˜αk ∈ I 1 (n-1,pk) or ˜αk ≤ pk+1 pk((pk+1)(n-1)-1) . (a) If ˜αk ∈ I 1 (n-1,pk) then Wn-1(˜αk) = 1-pk(n-2)˜αk. From (9), we deduce that ˜uk(Bk) ≥ (1 - pk(n - 2)˜αk) (1pkαk). Finally, using (10), we get that ˜uk(Bk) ≥ (1 - pk(n-2)αk 1-pkαk ) (1-pkαk) = 1-pk(n-1)αk ≥ Wn(αk), which can easily be checked because αk ∈ I(n,pk). (b) Otherwise, ˜αk ≤ pk+1 pk((pk+1)(n-1)-1) . Using 2. of Property 1 if n ≥ 3 or W1(x) = 1 if n = 2, we obtain Wn-1(˜αk) ≥ pk (pk+1)(n-1)-1 . By (9), ˜uk(Bk) ≥ pk (pk+1)(n-1)-1 (1 - pkαk) ≥ Wn(αk), which can easily be checked because αk ∈ I(n,pk).

Case 2: |Sk| ≥ pk + 1. Then, we prove that pk ≥ 2. By contradiction, assume pk = 1, then |Sk| ≥ 2. Since, n ≥ 2, 3. of Property 1 with αk ∈ I(n,pk) gives Wn(αk) ≤ pkαk = αk because pk = 1. Thus, agent k reaches the threshold ˜uk(Sk) = αk ≥ Wn(αk) just by selecting the heaviest element of B∗ k which is a contradiction with |Sk| ≥ 2.

Since |Sk| ≥ pk + 1, (4) implies that Wn(αk) > ˜uk(Sk\{e|Sk| k }) ≥ ˜uk(e1k ) + (pk - 1)˜uk(epk k ) = αk + (pk - 1)˜uk(epk k ) because |Sk| ≥ pk + 1, the elements of Sk are sorted by nonincreasing order of ˜uk and ˜uk(e1k ) = αk. From this inequality, we deduce ˜uk(e|Sk| k ) ≤ ˜uk(epk k ) < Wn(αk)-αk pk-1 because pk ≥ 2. Finally, by adding the last inequality of ˜uk(e|Sk| k ) to (4), we get:

On the one hand, by (7) and (11) we have:

On the other hand, by (8) and (11) we get:

Let us analyze the different cases according to the values of αk in I(n,pk) = I 1 (n,pk) ∪ I 2 (n,pk) ∪ I 3 (n,pk) . (a): αk ∈ I 1 (n,pk) . Then by construction, Wn(αk) = 1 - pk(n - 1)αk. Using (12), we obtain:

On the other hand, by (13) we get:

Using 2. of Property 1 if n ≥ 3 with this last inequality of ˜αk or W1(x) = 1 if n = 2, we deduce: Wn-1(˜αk) ≥ pk (pk+1)(n-1)-1 . Inequality (14) becomes ˜uk(Bk) ≥ ( pk (pk+1)(n-1)-1 ) ((n-1)p2k+1)αk-1 pk-1 ≥ 1-pk(n1)αk = Wn(αk) which can easily be checked because αk ∈ I 1 (n,pk) .

(b): αk ∈ I 2 (n,pk) . Then by construction, Wn(αk) = pk(1-pkα) (pk+1)(n-1)-1 . On the one hand, by (12),

On the other hand, by (13),

Using 2. of Property 1 if n ≥ 3 with this last inequality of ˜αk or W1(x) = 1 if n = 2, we deduce that Wn-1(˜αk) ≥ pk (pk+1)(n-1)-1 . Inequality (15) implies ˜uk(Bk) ≥ pk(1-pkαk) (pk+1)(n-1)-1 = Wn(αk) which can easily be checked because αk ∈ I 2 (n,pk) .

(c): αk ∈ I 3 (n,pk) . Then by construction, Wn(αk) = pk(αk+pk-1) np2k-pk-n+2 . On the one hand, by (12),

On the other hand, by (13),

Using 2. of Property 1 if n ≥ 3 with this last inequality of ˜αk or W1(x) = 1 if n = 2, we deduce that Wn-1(˜αk) ≥ pk (pk+1)(n-1)-1 . Inequality (16) implies ˜uk(Bk) ≥ pk(αk+pk-1) np2k-pk-n+2 = Wn(αk) which can easily be checked because αk ∈ I 3 (n,pk) .

The induction is proved and the result follows. ✷

6 Discussion

Recall that THRESHOLD provides a solution which is a base B of a matroid with a relative utility ˜ui(B) ≥ Wn(αi) for each agent i which is tight in I(n,1) ∪ I 1 (n,p) for any integers n ≥ 1 and p ≥ 2.

Unlike Vn, Wn is not monotonic, so it is not obvious that we may guarantee a relative utility of Wn(α) for each agent. However, for n = 2 agents, a slight modification of the selected agent in each call of THRESHOLD, allows us to provide a guarantee of at least max{W2(αi);W2(α)} for each agent i ∈ N = {1, 2}. Moreover, this latter bound can be shown tight when α ∈ I(2,1) ∪ (∪p≥2I 1 (2,p) ∪ I 2 (2,p)). An interesting challenge is to know if a bound of max{Wn(αi); Wn(α)} for each agent i ∈ N can be reached when n ≥ 3.

Another perspective is to study the same approach for a more general structure like matroid intersection.