Laurent Gourvès
email: laurent.gourves@dauphine.fr

Agreeable Sets with Matroidal Constraints

Keywords: Allocation of indivisible goods, Matroids, Approximation

, Suksompong models a problem of this kind as the search of an agreeable subset of a given ground set of goods. A subset is agreeable if it is weakly preferred to its complement by every agent of the group. Under natural assumptions on the agents' preferences such as monotonicity or responsiveness, an agreeable set of small cardinality is guaranteed to exist, and it can be efficiently computed. This article deals with an extension to subsets which must satisfy extra matroidal constraints. Worst case upper bounds on the size of an agreeable set are shown, and algorithms for computing them are given. For the case of two agents having additive preferences, we show that an agreeable solution can also be approximately optimal (up to a multiplicative constant factor) for both agents.

Introduction

Social choice theory addresses the recurrent challenge of reaching an agreement for a group of agents who have possibly heterogeneous preferences. The underlying problems often have a combinatorial nature like the fair allocation of indivisible items, or the election of a committee. Beyond its existence, the quick computation of a common solution that several agents consider as being agreeable, or fair, has recently received much attention, see for example two recent textbooks on computational social choice [START_REF] Brandt | Handbook of Computational Social Choice[END_REF][START_REF] Rothe | Economics and Computation, An Introduction to Algorithmic Game Theory[END_REF].

Suppose we are given a set of goods S and a group of agents N . When it is not possible to keep all the goods, a compromise must be found. A possible candidate is an agreeable set T ⊆ S such that every agent in N finds T at least as good as its complement S \ T . This approach is particularly relevant when the complement S \ T is left in the possession of an opponent of the group of agents N .

As an example, consider a sport league which consists of a set of teams S. A company who sells sporting goods of a given brand, wants to sign a sponsoring contract with a subset T of S. The other teams (S \ T ) receive sporting goods from a rival company whose brand is different. In this context, the persons who work in the board of the first company would accept T if they agree on the fact that it is at least as good as S \ T . Said differently, they should not envy their rival.

The problem of finding an agreeable set has been introduced by Suksompong [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF]. Agreeability is related to envy-freeness [START_REF] Foley | Resource allocation and the public sector[END_REF], a well established notion of fairness where one wants to distribute some goods over a group of agents so that everyone finds his share at least as good the share of another agent. Agreeability takes the viewpoint of a group instead of the viewpoint of every single agent. Moreover, agreeability is unilateral as one wishes that the group of agents N does not envy the opponent's share.

In his work, Suksompong makes a natural monotonicity assumption on every preference relation over the possible subsets of S. A preference relation is monotonic if every T is at least as good as T when T ⊆ T . An obvious agreeable set contains all the elements of S. In the previous example with the sport league, it would correspond to a monopoly, which is unlikely. Thus, it is more realistic to find a small agreeable set. How small can an agreeable set be? Following [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF], every instance with monotonic preferences admits an agreeable set of size min m+n-1

2

, m where n and m denote the number of agents in N and the number of goods, respectively. Beyond the existence of an agreeable set, its efficient algorithmic construction is possible when the preference relations are responsive (a special case of monotonicity that can be found in e.g. [START_REF] Barberà | Ranking sets of objects[END_REF][START_REF] Brams | The undercut procedure: an algorithm for the envy-free division of indivisible items[END_REF]), and |N | ∈ {2, 3}.

In the present work, we intend to extend the problem of finding a small agreeable set to richer cases. Concretely, we introduce an additional constraint on the set of items that the agents, together with their opponent, select. Let us provide two examples of this extension.

Example 1. A university is recruiting q students who will work in one of the two departments: physics and biology. By the law, a certain parity between men and women must be satisfied, i.e., the set of recruited students must contain at most αq members of each sex, for a given parameter α ∈ (0.5, 1]. The sets of female and male candidates are denoted by S f and S m , respectively. Let T and C be the set of students recruited by the department of physics and biology, respectively. A feasible solution must satisfy

T ∩ C = ∅, T ∪ C ⊆ S f ∪ S m , |T ∪ C| ≤ q, and max(|(T ∪ C) ∩ S f |, |(T ∪ C) ∩ S m |) ≤ αq.
An instance of this example can be

S f = {f 1 , f 2 , f 3 , f 4 , f 5 }, S m = {m 1 , m 2 , m 3 , m 4 }, q = 5, and α = 3/5. If T = {f 3 , m 2 , m 3 }, then C can be any member of C = {{f, m} ∈ S f \ {f 3 } × {m 1 , m 4 }} ∪ {{f, f } | f = f and f, f ∈ S f \ {f 3 }},
or a proper subset of some {f, m} ∈ C if less than q students are recruited.

Example 2. The main cities of a given country need to be connected with highways. The connection network consists of links between pairs of cities. The objective is to guarantee the existence of a path between every pair of cities. Since the construction and maintenance are expensive, the network should be inclusion-wise minimal. Two rival companies compete for the construction and maintenance of the network. We denote by T and C the links of the first and second company, respectively. Thus, T and C should be disjoint and their union should be a tree spanning all big cities.

For instance, consider the network of In Example 1, we take the point of view of a department, say physics, who would like to choose a best set T of students. The opponent is the department of biology who receives C. In Example 2, we take the point of view of one company, say the first one, who would like a best set T of links. The opponent is the second company who builds and maintains C.

Both examples depart from the framework of [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] because the set of selected elements must satisfy extra feasibility contraints. It is not always true that C = S \ T . Moreover, when T is fixed, the way to define a complement C of T is not necessarily unique.

Therefore, our model imposes to propose an adapted notion of agreeability. We will do it in two ways in this article. Either every agent finds the current solution at least as good as any complement, or every agent finds the current solution at least as good as at least one complement. We are going to refer to these two notions as strong and weak agreeability, respectively.

The focus of the present work is on a certain type of feasibility constraints for the solutions, namely those defined by a matroid [START_REF] Oxley | Matroid Theory[END_REF]. Indeed, the model of [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] and Examples 1 and 2 are based on matroids which are free, laminar, and graphic, respectively (defined in section 2.1). A matroid is a well studied combinatorial structure which generalizes the notion of independence. Matroid theory has significantly contributed to the understanding of some important combinatorial optimization problems, such as spanning trees and matchings of a graph [START_REF] Schrijver | Combinatorial Optimization: Polyhedra and Efficiency[END_REF][START_REF] Korte | Combinatorial Optimization: Theory and Algorithms[END_REF]. The literature on the allocation of resources comprises applications having matroidal constraints like quotas, see for example [START_REF] Gale | College admissions and the stability of marriage[END_REF][START_REF] Gusfield | The Stable Marriage Problem: Structure and Algorithms[END_REF][START_REF] Biró | The college admissions problem with lower and common quotas[END_REF]. Matroids have also been studied in the context of allocating goods, see for example [START_REF] Gourvès | A matroid approach to the worst case allocation of indivisible goods[END_REF][START_REF] Ferraioli | On regular and approximately fair allocations of indivisible goods[END_REF][START_REF] Gourvès | Object allocation problems under constraints[END_REF].

In order to propose a self-contained work, some basic notions of matroid theory are provided in section 2.1. The type of preference relations under consideration are defined in section 2.2: they are monotonic or responsive. The next section deals with adapted notions of agreeability to the specific context of matroids. Namely, agreeability can be strong or weak. Results for the existence of an agreeable set of bounded size are presented in section 3. These contributions are paired with tight polynomial-time algorithms.

Before concluding, the case of two agents having additive preference relations is studied in section 4. Though approximation results cannot be obtained for every instance, we show that it is possible to compute in polynomial time a set which is, at the same time, agreeable and approximately optimal within a constant multiplicative factor for the class of simple matroids.

Fundamental Concepts

Matroids

In this document, [i] denotes {1, 2, . . . , i}. For a set S and an element e, we sometimes write S + e to denote S ∪ {e}, and S -e to denote S \ {e}. Definition 1. A matroid (E, I) consists of a finite set E = {e 1 , . . . , e m } of elements and a collection I of subsets of E such that:

• (M1) ∅ ∈ I; • (M2) if I 2 ⊆ I 1 and I 1 ∈ I, then I 2 ∈ I; • (M3) if I 1 , I 2 ∈ I such that |I 1 | < |I 2 |, then there exists e ∈ I 2 \I 1 such that I 1 ∪ {e} ∈ I.
The elements of I are called independent sets, and inclusion-wise maximal independent sets are called bases.

The rank of a subset S ⊆ E is defined as rank(S) := max{|I| : I ⊆ S, I ∈ I}. All the bases of a matroid have the same cardinality r := rank(E), also called the rank of the matroid.

The time complexity of an algorithm that manipulates a matroid depends on the time for testing if a set is independent. This is done with a test called the independence oracle. Here, we assume that the independence oracle runs in polynomial time with respect to |E|. For the ease of presentation, we often write that a matroid is part of the input of an algorithm but concretely, we only require E and the independence oracle.

Let us give some well known matroids:

• With every graph (V, E) is associated a graphic matroid (E, I) such that I ∈ I iff it is an acyclic set of edges.

• For a set of m elements E and a bound b ∈ [m], a uniform matroid (E, I) is such that I := {I ⊆ E : |I| ≤ b}. The rank of a uniform matroid is its bound b. In this article, a uniform matroid with bound b is also called a b-uniform matroid.

• For a partition of E in k subsets (E 1 , . . . , E k ) and k bounds (b 1 , . . . , b k ), a partitional matroid (E, I) is such that

I := {I ⊆ E : |I ∩ E j | ≤ b j , ∀j ∈ [k]}.
• The partitional matroid can be extended to the laminar matroid if for each pair of subsets

(E i , E j ), it holds that E i ⊆ E j , or E j ⊆ E i , or E i ∩ E j = ∅.
The unconstrained case of allocating indivisible goods, i.e. the one studied in e.g. [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF][START_REF] Manurangsi | Computing an approximately optimal agreeable set of items[END_REF] and [START_REF] Bouveret | Fair allocation of indivisible goods[END_REF], corresponds to a free matroid: a free matroid (E, I) is such that I := 2 E . Example 1 corresponds to a laminar matroid.

Partitional and laminar matroids can capture known constraints like upper quotas [START_REF] Gale | College admissions and the stability of marriage[END_REF][START_REF] Gusfield | The Stable Marriage Problem: Structure and Algorithms[END_REF] and common upper quotas [START_REF] Biró | The college admissions problem with lower and common quotas[END_REF]. Other applications can be found with other matroids (e.g. see [11, Example 1] and [9, Example 2] for the transversal matroid).

Preference Relations

Let denote a reflexive, complete, and transitive preference relation on 2 E , where E is a set of elements. The strict part of is denoted by . We sometimes write e e instead of {e} {e }.

Definition 2. is monotonic if E + e E for all E ∈ 2 E and e ∈ E.
Definition 3. is responsive if it satisfies the following two conditions:

• is monotonic; Let be a preference relation on E. As a notation, we reserve and for preference relations on 2 E and E, respectively. The strict part of and are denoted by and , respectively. Definition 4. We say that is consistent with when e e ⇔ e e , ∀ e, e ∈ E.

• E -e + e E
The next observation provides a sufficient, but not necessary, condition for a set I to be preferred to another set J when is unknown but is consistent with a given relation .

Observation 1. For a responsive preference relation consistent with and two sets I, J ∈ 2 E , we have I J if there exists a matching that saturates1 J in the bipartite graph (I ∪ J, {(e i , e j ) ∈ I × J | e i e j }).

Proof. Let µ be a matching that saturates J in the bipartite graph. Denote by µ(e) the element of I that is matched with e ∈ J, and let µ(J) = {µ(e) : e ∈ J}. By the responsiveness of and its consistency with , µ(J) J. Since µ(J) ⊆ I, the monotonicity property gives I µ(J) and the result follows by transitivity of .

This observation, together with the notion of most preferred base, will be used several times in rest of this article. Given a matroid (E, I) and a preference relation on E, the most preferred base problem is to find a base B of (E, I) such that B B holds for every base B and every preference relation consistent with . Interestingly a most preferred base always exists and the well known GREEDY algorithm for computing a base of maximum weight (additive preference) also solves the most preferred base problem. Unfortunately, GREEDY is not guaranteed to work if is monotonic but not responsive. Indeed, suppose E = {a, b, c}, I = {I ⊆ E : |I| ≤ 2}, a b c and {b, c} {a, b} {a, c} {a} {b} {c} ∅.

Agreeability: Instances and Problems

An instance of agreeable problem consists of a matroid (E, I) of rank r, a set N of n agents, and for every agent ∈ N , a preference relation over E. Though the preference relation of an agent over I is not part of the input, we assume that is consistent with . Moreover is always monotonic, and is sometimes responsive. The motivation comes from the fact that it is difficult to have a compact representation of , as opposed to . The instances considered in [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] are a special case of the model proposed in this article ((E, I) is a free matroid). Our generalization comes with an important difference since an independent set does not need to have a unique complement. For this reason, we shall introduce a different notion of agreeability when a set is compared to all its complements (strong agreeability, abbreviated s-agreeability), or only compared to a single complement (weak agreeability, abbreviated w-agreeability). Definition 6. A set I ∈ I is s-agreeable to agent if I J holds for all J ∈ C(I). A set I ∈ I is w-agreeable to agent if there exists J ∈ C(I) such that I J and J is maximal for inclusion. For t ∈ {s,w}, a set I ∈ I is t-agreeable if it is t-agreeable to every agent in N .

In this definition, both I and its complement J are independent sets of the same matroid. This constraint captures the fact that the agents in N and their possible opponent evolve in the same environment. Thus, they are bound to build solutions which fit this environment. In Examples 1 and 2, the environments are the global parity constraint imposed to the university by the law, and the inclusion-wise minimality of the entire network, respectively. Definition 6 extends the notion of agreeability for which there is a unique complement [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF]. In case of a free matroid, s-agreeability and w-agreeability coincide.

For every instance, every base of the underlying matroid must be (strong or weak) agreeable since its only complement is the empty set. The difficulty relies on the existence, and efficient construction, of an agreeable set of small size. A challenging aspect of the construction problem comes from the fact that the agents' preferences over 2 E are unknown, but the preferences over E are given. Indeed, it is difficult to elicit and communicate the agents' preferences over 2 E . However, this is easier for the agents' preferences over E. This motivates the following notion of necessarily agreeable set which generalizes [18, Definition 5].

Definition 7. Given a preference relation over E, a set I ∈ I is necessarily s-agreeable (resp., necessarily w-agreeable) with respect to if I is s-agreeable (resp., w-agreeable) for any responsive preference relation consistent with . For t ∈ {s,w}, a set I ∈ I is necessarily t-agreeable if it is necessarily t-agreeable with respect to , ∀ ∈ N .

Small Agreeable Sets

We first address the existence of an agreeable set whose size is not trivial (i.e. not equal to the rank) for every instance. This type of existence result comes with a hypothesis of monotonicity on the agents' preferences. The second problem is the algorithmic construction of a necessarily agreeable set, provided that the agents' preferences are responsive. The preferences of the agents over E are given but the preferences over 2 E are not part of the input. These two problems are addressed for strong and weak agreeability, respectively.

Strong Agreeability

We begin with an existence result for monotonic preferences followed by a constructive method for responsive preferences.

Proposition 1. For every matroid (E, I) with rank r and every set N = [n] of agents with monotonic preferences on I, there exists I ∈ I such that |I| ≤ n r n+1 and I is s-agreeable to all players.

Proof. Choose any base B of (E, I) which will be cut in n + 1 disjoint subsets S 1 , . . . , S n+1 . S i is the share of agent i ∈ N while S n+1 is a complement. Let x and y be two natural numbers satisfying

|B| = r = (n + 1)x + y with 0 ≤ y ≤ n. We impose that |S 1 | = |S 2 | = • • • = |S y | = x + 1 and |S y+1 | = • • • = |S n+1 | = x.
Modify S 1 , . . . , S n+1 as follows. While there exists ∈ N satisfying ∃J ∈ C( i∈N S i ) such that J S and |J| = |S n+1 | , do S n+1 ← S and S ← J. The process is finite because the preferences are transitive, and every replacement S ← J induces an improvement in agent 's preference for S , without deteriorating the preference of agent k for S k , ∀k ∈ N \ { }. We eventually get n + 1 disjoint sets S 1 , . . . , S n+1 such that n+1 i=1 S i ∈ I and for all ∈ N and J ∈ C( i∈N S i ), S J. The monotonicity property gives i∈N S i S J, implying that i∈N S i is s-agreeable to all agents. The size of

i∈N S i is r -|S n+1 |. Since |S i | ∈ {x, x + 1} holds for every i ∈ [n + 1]
, at any time, we get that | i∈N S i | ≤ r -x = rn+y n+1 = rn n+1 . Proposition 1 deals with monotonic preferences, which is a proper superset of responsive preferences.

Proposition 2. For every r and n, there exists an instance with rank r, a set N of n agents, and responsive preferences for which the size of every s-agreeable set is at least n r n+1 .

Proof. Consider the r-uniform matroid (E, I) such that E = {e i : (i, ) ∈ [r] × N }. For every I, I ∈ I, I I iff |I ∩ {e 1 , . . . , e r }| > |I ∩ {e 1 , . . . , e r }|, ∀ ∈ N . Thus, is responsive for all . To be s-agreeable to an agent ∈ N , I must satisfy x := |I ∩ {e 1 , . . . , e r }| ≥ r -|I|. We get that

∈N x ≥ ∈N (r -|I|) = n(r -|I|). Use ∈N x = |I| to get that (n + 1)|I| ≥ nr. Therefore, |I| ≥ n r
n+1 because |I| is an integer. Proposition 2 matches with Proposition 1, meaning that the general bound of n r n+1 is tight for strong agreeability. This bound can be informally explained: if the complement has size s, then every agent must "value" s elements of the agreeable set (see the second and third examples of a responsive preference in section 2.2). In the worst case, the agents value disjoint sets. Thus, as done in the proof of Proposition 1, the problem is to identify a base (its size is r) cut in n + 1 pieces of (almost) equal size, and only one piece can be discarded. Now, we investigate the construction of an s-agreeable set I for any number n = |N | of agents (see Algorithm 2 where r = rank(E)) when the preference of every agent over E is given. Let next : [n] → [n] be defined as next(t) = t + 1 if 1 ≤ t < n, and next(n) = 1. The idea of the algorithm is the following.

The solution is empty at the beginning (it belongs to I) and the agents add an element (the one they like the most) in a round-robin way so that the solution remains in I. The algorithm stops after the insertion of n r n+1 elements. . Each agent has inserted at least as many elements as the size of a complement. The fact that an agent t, during her turn, inserts the element e ∈ E \ I coming first in t , ensures that every element e that can be subsequently added to I, and be part of the complement, satisfies e t e . Therefore, the conditions of Observation 1 are met for every agent2 , meaning that I is s-agreeable to all agents.

Note that the proof of Theorem 2 does not exploit the fact the agents add elements to I in a round-robin way. Other orders would work, provided that each agent inserts at least as many elements as the size of a complement. However, ROUND-ROBIN will be used in section 4 to show some performance guarantees, in addition to agreeability.

Weak Agreeability

Let us first give a characterization of w-agreeable sets. Proposition 3. An independent set I is w-agreeable to an agent with preference relation iff there exists a base B such that B ⊇ I and I B \ I.

Proof. On one hand, there exists by definition J ∈ C(I) such that I J and J is maximal for inclusion. Thus, I ∪ J is a base which includes I. On the other hand, B \ I is a complement to I and it is maximal for inclusion because B is a base.

Let us quote the main theorem of [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] which is used in the proof of our next result.

Theorem 3. [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] Assume that there are n players with monotonic preferences on S. There exists a subset T ⊆ S such that |T | ≤ min m+n-1

2

, m and T is agreeable to all n players. Moreover, there exist monotonic preferences for which the bound min m+n-1 2 , m is tight.

In Theorem 3, m is the rank of the free matroid. The following theorem extends this results to any matroid of rank r. Theorem 4. Assume that there are n agents with monotonic preferences on 2 E . There exists a subset T ⊆ E such that |T | ≤ min r+n-1 2 , r and T is w-agreeable to all n agents. Moreover, there exist monotonic preferences for which the bound min r+n-1 2 , r is tight.

Proof. Take any base of the matroid, say B. Such a base can be computed with GREEDY in polynomial time (choose arbitrarily). Use Theorem 3 where S = B, and m is the rank r of the corresponding free matroid. Thus, there exists T ⊆ B such that |T | ≤ min r+n-1 2 , r and T B \ T for every agent . Now, by Proposition 3 with B and T , T is a w-agreeable set. For the tightness of the bound, the examples used for the proof of Theorem 3 remain valid since they are free matroids.

As mentioned in [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF], and it extends to the matroidal setting, it is remarkable that w-agreeability can be obtained with a set whose size is roughly half the size of a base, plus half an element per agent. Interestingly, the construction of a necessarily w-agreeable set of size min r+n-1 2 , r is possible when n = 2. In this case min r+n-1 2 , r = r+1 2 because r ≥ 1 can be assumed.

Theorem 5. For two agents and their preferences over E, there exists a polynomial-time algorithm that returns a necessarily w-agreeable set of size r+1 2 . Proof. Use GREEDY with 1 in order to construct a most preferred base {f 1 , • • • , f r } for agent 1. Afterwards, run Algorithm 33 with input {f 1 , • • • , f r } and 2 . We get two sets I and J such that I ∈ I because I ⊂ {f 1 , • • • , f r } (Property M2 of matroids), J ∈ C(I), and I ∪ J = {f 1 , . . . , f r }. For every player ∈ {1, 2}, each element f ∈ J can be paired with an element f ∈ I such that f f . The conditions of Observation 1 are met, meaning that I is w-agreeable. In both cases (r = 2k + 1 or r = 2k), I has cardinality k + 1 = r+1 2 .

Approximation for Additive Preference Relations

It is assumed in this section that the agents' preferences are additive. The valuation function of t ∈ N is denoted by ν t . Hence, ∀I, I ⊆ E, ν t (I) ≥ ν t (I ) ⇔ I t I . The representation of t is compact since it suffices to store ν t ({e}) for every e ∈ E. For the sake of simplicity, we often write ν t (e) instead of ν t ({e}).

So far, we have seen that a succinct set can be agreeable to a group of agents if the preferences are monotonic. An interesting challenge is to combine this property with another kind of guarantee on the quality of the solution.

As an illustration, consider the instance of Example 2 depicted on Figure 2. There are two agents with identical valuations for the edges. The set {(a, b), (b, c)} is valued 2, which is as large as the valuation of the unique complement (c, d). Thus, {(a, b), (b, c)} is s-agreeable but its valuation is only 20% of the optimum because the maximum valuation for a tree is 10 (achieved by {(a, b), (a,c),(c,d)} or {(b,c),(a,c),(c,d)}). A tree with maximum valuation is the best s-agreeable set (without limiting the cardinality of the set), or what the agents would choose if they were alone. Compared to {(a, b), (b, c)}, {(a, b), (a, c)} is an sagreeable set of size 2 but its valuation is 80% of the optimum. From the agents' viewpoint, {(a, b), (a, c)} is more attractive.

In addition to the notion of agreeability, we are going to use approximation which is the worst-case ratio between the valuation of a given solution and the largest valuation of a solution. Definition 8. For ρ ∈ (0, 1], a set I ∈ I is ρ-approximate for agent t if ∀B ∈ I, ν t (I) ≥ ρ ν t (B). An algorithm is ρ-approximate for agent t if its output is ρ-approximate for every instance.

Algorithm 3:

Data: A base {f 1 , • • • , f r } and 2 Result: A w-agreeable set I and a complement J

1 I ← ∅ 2 J ← ∅ 3 if r = 2k + 1 then 4 I ← {f 1 } 5 for i ← 1 to k do 6 if f 2i 2 f 2i+1 then 7 I ← I ∪ {f 2i } 8 J ← J ∪ {f 2i+1 } 9 else 10 I ← I ∪ {f 2i+1 } 11 J ← J ∪ {f 2i } 12 else 13 r = 2k 14 I ← {f 1 , f 2 } 15 for i ← 2 to k do 16 if f 2i-1 2 f 2i then 17 I ← I ∪ {f 2i-1 } 18 J ← J ∪ {f 2i } 19 else 20 I ← I ∪ {f 2i } 21 J ← J ∪ {f 2i-1 } 22 return I and J 7 1 1 2 • • • • b a d c Figure 2:
The nodes and the edges are the cities and the roads, respectively. The numbers correspond to the valuations.

By Lemma 1 we have ν 1 (e 2x+1 ) ≥ ν 1 (f 2x+2+i ) for i = 0..x -1. Summing these inequalities gives

xν 1 (e 2x+1 ) ≥ ν 1 (F 3 ) (8)
that we multiply by x+1 x to get

(x + 1)ν 1 (e 2x+1 ) ≥ (1 + 1/x)ν 1 (F 3 ) (9)
We have

xν 1 (O) ≥ (x + 1)ν 1 (F 3 ) because ν 1 (e) ≥ ν 1 (f ) for every (e, f ) ∈ O × F 3 by Lemma 1, |O| = x + 1, and |F 3 | = x. When x ≥ 2, multiply xν 1 (O) ≥ (x + 1)ν 1 (F 3 ) by x-1 x to get that (x -1)ν 1 (O) ≥ (x -1/x)ν 1 (F 3 ) (10)
By Lemma 1 we have ν 1 (e 2i+1 ) ≥ ν 1 (f 2i+1 ) for i = 0..x -1. Summing these inequalities gives

ν 1 (O) ≥ ν 1 (F 1 ) (11)
If x ≥ 2, then we can combine (7), ( 9), [START_REF] Gourvès | A matroid approach to the worst case allocation of indivisible goods[END_REF], and (11) mutiplied by x + 1 to get that [START_REF] Gale | College admissions and the stability of marriage[END_REF], and (11)

(3x + 1)ν 1 (O) ≥ (x + 1)(ν 1 (F 1 ) + ν 1 (F 2 ) + ν 1 (F 3 )) = (x + 1)ν 1 (F ). Since ν 1 (I) ≥ ν 1 (O), I is x+1 3x+1 -approximate for agent 1. If x = 1 then x+1 3x+1 = 1 2 . Combine (6),
to get that 2ν 1 (O) ≥ ν 1 (F 1 )+ν 1 (F 2 )+ν 1 (F 3 ) = ν 1 (F ). Since ν 1 (I) ≥ ν 1 (O), I is x+1
3x+1 -approximate for agent 1.

Theorem 7. ROUND-ROBIN for two agents and simple matroids is 1/3-approximate for agent 2 when r ≥ 5, and 1/r-approximate for agent 2 when r ∈ {2, 3, 4}.

Proof. Let us begin with the case r ≥ 5. We denote by G = {g 1 , . . . , g r } a most preferred base for agent 2 where

ν 2 (g 1 ) ≥ ν 2 (g 2 ) ≥ • • • ≥ ν 2 (g r ) (12)
The output of ROUND-ROBIN is I = {e 1 , . . . , e 2r/3 } and we assume that e i is inserted before e j whenever i < j. We have 2r/3 ≥ 4 because r ≥ 5. During the execution of ROUND-ROBIN, agent 2 chooses the even elements {e 2i : i = 1..x} where x ≥ 2 because 2r/3 ≥ 4.

By Lemma 1 we get that ν 2 (e 2i ) ≥ ν 2 (g j ), ∀j ≥ 2i

We have ν 2 (e 1 ) + ν 2 (e 2 ) ≥ ν 2 (g 1 ) because the matroid is simple. Indeed, either e 1 = g 1 and the inequality holds directly, or e 1 = g 1 and {e 1 , g 1 } must be independent, which means that ν 2 (e 2 ) ≥ ν 2 (g 1 ).

Use [START_REF] Gusfield | The Stable Marriage Problem: Structure and Algorithms[END_REF] to get that

3(ν 2 (e 1 ) + ν 2 (e 2 )) ≥ ν 2 (g 1 ) + ν 2 (g 2 ) + ν 2 (g 3 ) (14)
For i = 2..x -1, associate the set {g 3i-2 , g 3i-1 , g 3i } with e 2i . Since i ≥ 2 ⇔ 2i ≤ 3i -2, use ( 13) and [START_REF] Gusfield | The Stable Marriage Problem: Structure and Algorithms[END_REF]

to get that ν 2 (e 2i ) ≥ ν 2 (g 3i-2 ) ≥ ν 2 (g 3i-1 ) ≥ ν 2 (g 3i ). It follows that 3ν 2 (e 2i ) ≥ ν 2 (g 3i-2 ) + ν 2 (g 3i-1 ) + ν 2 (g 3i ) (15)
For i = x, we associate the set {g j : 3x -2 ≤ j ≤ r} with e 2x . Depending on r, the size of {g j : 3x -2 ≤ j ≤ r} is between 1 and 3. With the same arguments as above we get that From ( 14), [START_REF] Oxley | Matroid Theory[END_REF] where i = 2..x -1, and (15) we deduce that 3ν 2 (I) ≥ 3(ν 2 (e 1 ) + ν 2 (e 2 ) + ν 2 (e 4 ) + • • • + ν 2 (e 2x )) ≥ ν 2 (G), meaning that I is 1/3-approximate for agent 2 when r ≥ 5.

3ν 2 (e 2x ) ≥ 3x-2≤j≤r ν 2 (g j ) (16)
To conclude, consider the case r ∈ {2, 3, 4}. ROUND-ROBIN picks 2r/3 ≥ 2 elements. Since the matroid is simple, ROUND-ROBIN must pick the most preferred element for agent 2 (it is either the first or the second element inserted in the solution). As the maximum utility for agent 2 is at most r times the utility for the most preferred element, we deduce that ROUND-ROBIN is 1/r-approximate for agent 2.

Proposition 4. There exist instances for which the approximation ratios given in Theorems 6 and 7 are reached by ROUND-ROBIN.

Proof. The proof is made on the rank r.

Take the graphic matroid associated with the 3 node graph of Figure 3 Take the graphic matroid associated with the graph of Figure 4 (rank ≥ 5). Agent 1 has utility 1 for every edge f i , and utility 0 for any other edge. Agent 2 has utility 1 for edges g 1 , g 2 and g 3 , and utility 0 for any other edge. The most preferred base of agent 1 is {f i : i..r} and ν 1 ({f i : i..r}) = r. A most preferred base for agent 2 includes {g 1 , g 2 , g 3 }; the maximum utility for agent 2 is 3. A possible execution of ROUND-ROBIN is to select f 1 , g 1 , f 3 , g 4 , f 5 , and so on4 , until 2r/3 elements are picked. Agents 1 and 2 have value r/3 and 1 for this solution, respectively. Thus, the solution is r/3 /r-approximate for agent 1 and 1/3-approximate for agent 2.

•

• • • • • • • • f 1 f 2 f 3 f 4 f 5 f 6 f r g 1 g 2 g 3 g 4 g 5 g 6 g r
Figure 4: A graphic matroid with rank ≥ 5.

Weak Agreeability

The algorithm described in the proof of Theorem 5 cannot be used as it is because it provides a guarantee only for the first agent. For example, take a graphic matroid defined on a graph composed of two disjoint spanning trees T 1 and T 2 . Agent i ∈ {1, 2} has valuation 1 for every edge of T i , and valuation 0 for every edge of T 3-i . For this instance, the algorithm described in the proof of Theorem 5 outputs a subset of T 1 for which agent 2 has valuation 0. However agent 2 has a positive valuation for T 2 . Nevertheless, approximation results under weak agreeability can be obtained if we restrict ourselves to two agents and simple matroids. These results are based on Algorithm 4.

Algorithm 4:

Data: A matroid (E, I) with rank r, ν 1 and ν 2 Result: A w-agreeable set I 1 Run a modified version of ROUND-ROBIN where instead of stopping when the current solution has cardinality n r n+1 , a full base {e 1 , . . . , e r } is constructed where e i is inserted before e j whenever i < j 2 if r = 2 then 3 I ← {e 1 , e 2 } and J ← ∅ 4 else 5 Rename the elements of {e 1 , . . . , e r } as {f 1 , . . . , f r } in such a way that ν 1 (f i ) ≥ ν 1 (f j ) whenever i < j 6

Run Algorithm 3 with input {f 1 , . . . , f r }, and 2 such that f 2 f iff ν 2 (f ) ≥ ν 2 (f ). We get two sets I and J such that I ∈ I, J ∈ C(I), and I ∪ J = {e 1 , . . . , e r } 7 return I Note that step 1 of Algorithm 4 corresponds to an algorithm called GENERALIZED ALT-GREEDY in [START_REF] Gourvès | Approximate tradeoffs on weighted labeled matroids[END_REF]. Furthermore, the output I of Algorithm 4 is a w-agreeable set of size r+1 2 by Theorem 5.

Theorem 8. For two agents having additive preferences over the independent sets of a simple matroid, Algorithm 4 builds in polynomial time a w-agreeable set of size r+1 2 whose approximation ratios are

• • • • • • a b c d e f (1, 0) (1, 0) (1, 0) (1 -, 0) ( , ) (0, 1)
Figure 5: A graphic matroid with rank ≥ 5. The first and second coordinates are the valuation of the first and second agent for the edges, respectively. Every dotted edge is valued 0 and 1 by agents 1 and 2, respectively. edges), respectively. Agents 1 and 2 value their most preferred base 4q + 2 and 5, respectively. Algorithm 4 may take the edges: f 1 , g 1 , f 3 , g 4 , f 5 , g 6 , . . . , f r-1 , g r . The reordering with respect to ν 1 can be f 1 , f 3 , f 5 , . . . , f r-1 , g r , . . . , g 4 , g 1 . The rank being even, I consists of the first two edges {f 1 , f 3 }, plus the edge that agent 2 prefers in each pair of consecutive edges. The algorithm returns a solution which contains q + 1 edges valued 1 by agent 1 and one edge valued 1 by agent 2 which are {f 1 , f 3 , f 7 , . . . , f 4q-1 } and {g 1 }, respectively. Thus, the solution is q+1 4q+2 -approximate for agent 1 and 1/5-approximate for agent 2.

Conclusion and Future works

This article is devoted to the existence and computation of succinct agreeable sets under additional matroidal constraints. An s-agreeable set of cardinality nr n+1 always exists if the agents' preferences are monotonic, and no better (worst case) bound on the cardinality can be found unless it applies to a special case. When the agents have responsive preferences, an s-agreeable set of cardinality nr n+1 can be efficiently computed with ROUND-ROBIN.

A w-agreeable set of cardinality r+n-1 2 always exists if the agents preferences are monotonic, and no better (worst case) bound on the cardinality can be found unless it applies to a special case. When there are two agents with responsive preferences, a w-agreeable of cardinality r+1 2 can be efficiently computed with Algorithm 4.

Here, n r n+1 and r+n-1 2 are worst case bounds. There exist instances for which our algorithms fail to return an agreeable set of smallest cardinality. A future direction would be to design algorithms which output (strong or weak) agreeable sets of smallest cardinality. This was recently shown as a computationally difficult task, even when the difficulty coming from the representation of , ∀ ∈ N , is put aside [START_REF] Manurangsi | Computing an approximately optimal agreeable set of items[END_REF]. However, an agreeable set of approximately optimal size5 can be computed efficiently if the matroid is free [START_REF] Manurangsi | Computing an approximately optimal agreeable set of items[END_REF]. Thus, is it possible to efficiently compute (strong or weak) agreeable sets of approximately minimum size?

Given the preference of every agent over E, can we extend Theorem 5 and produce a succinct wagreeable set for more than two agents? The case of three agents is resolved in [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] where a polynomial number of queries to preference oracle can be made in order to partially elicit the agents' preferences.

We have shown that for two agents with additive preferences, agreeability and approximation can be combined. An interesting question is whether the approximation ratios of Tables 1 and 2 can be improved. Preliminary answers for s-agreeability can be provided when r ∈ {2, 3, 4}. For r = 2, consider the partitional matroid such that E = {e 1 , e 2 , e 3 , e 4 }, and I = {I ⊆ E : |I ∩ {e 1 , e 2 }| ≤ 2}. Suppose agent i ∈ {1, 2} has utility 1 for e i and e i+2 , and utility 0 for the other elements. The optimal utility is 2 for both agents. No algorithm can outperform ROUND-ROBIN because no feasible solution of cardinality 2•2 3 = 2 is better than 1/2-approximate for both agents. For r ∈ {3, 4}, similar arguments can be used with the instances of Figure 3 (rank 3 and 4).

Another question is whether approximately good agreeable sets for more than two agents can be computed. We believe that there is room for positive results if every group of k elements is independent, where k is an upper bound on the number of agents. Matroids having this property are said to be k-simple [START_REF] Gourvès | Approximate tradeoffs on weighted labeled matroids[END_REF].

Figure 1 :

 1 Figure 1: Each node is a big city and each edge is a possible highway.

Figure 1 .

 1 If T = {(a, b), (b, d)} then C can contain at most one edge in {(a, e), (b, e), (d, e)} (dotted edges) and at most one edge in {(a, c), (b, c), (d, c)} (dashed edges).

for all E ∈ 2 E

 2 and e, e such that e e , e ∈ E \ E, and e ∈ E. Let us give three examples of responsive preference relations: (i) In an additive preference relation , for every e ∈ E, {e} has a non-negative valuation ν({e}) ∈ R. Moreover, ν(∅) = 0 and for every non-empty I ⊆ E, ν(I) = e∈I ν({e}). Then, for I, I ⊆ E, we have I I if ν(I) > ν(I ). A given ordering on E is assumed in the following two definitions. Furthermore, for I, I ⊆ E such that |I| = |I | and I = I , I lexicographically dominates I if the smallest element of I \ I is smaller than the smallest element of I \ I, where an ordering on E is assumed. (ii) For I, I ⊆ E, we have I I if one of the following two conditions holds: -|I| > |I |; -|I| = |I | and I lexicographically dominates I . (iii) For I, I ⊆ E, we have I I if one of the following three conditions holds (e is a given element of E and denotes the symmetric difference): e ∈ I \ I ; e / ∈ I I and |I| > |I |; e / ∈ I I , and |I| = |I | and I lexicographically dominates I .

Theorem 1 .

 1 GREEDY (Algorithm 1) solves the most preferred base problem for all responsive preference relation consistent with . Proof. Let B = {e 1 , . . . , e r } be the output of GREEDY, and B * = {e * 1 , . . . , e * r } is a most preferred base. Suppose w.l.o.g. that e i e j and e * i e * j for all 1 ≤ i < j ≤ r. If e i e * i for every i ∈ [r], then B B * (Observation 1); B is a most preferred base. Otherwise, let k be the smallest index such that e k e * k . By M3, there exists e ∈ {e * 1 . . . , e * k } \ {e 1 . . . , e k-1 } such that {e 1 . . . , e k-1 } + e ∈ I. Since e e * k e k , we get a contradiction with the construction of B.

Algorithm 1 : 5 B

 15 GREEDY Data: (E, I) and Result: A base B 1 Let E = {e 1 , . . . , e m } such that e i e i+1 , ∀i ∈ {1, ..., m -1} 2 B ← ∅ 3 for i = 1 to m do 4 if B + e i ∈ I then ← B + e i 6 return B Definition 5. The complement set of I ∈ I is C(I) := {J ⊆ E \ I : I ∪ J ∈ I}. Every J ∈ C(I) is a complement of I.Thus, |I| + |J| ≤ r holds for every J ∈ C(I). Moreover, all the complements of I that are maximal for inclusion have the same size: r -|I|.

Algorithm 2 : 4 Find 5 I ← I + e 6 t

 2456 ROUND-ROBIN Data: A matroid (E, I) with rank r, for every ∈ N Result: An s-agreeable set I ∈ I 1 t ← 1 2 I ← ∅ 3 while |I| < n r n+1 do e ∈ E \ I such that I + e ∈ I, break ties by choosing the element coming first in t ← next(t) 7 return I Theorem 2. ROUND-ROBIN returns a necessarily s-agreeable set of size n r n+1 . Proof. At the end of the algorithm's execution, I has size n r n+1 whereas any complement J ∈ C(I) has size r n+1

Figure 3 :

 3 Figure 3: Three graphic matroids with rank 2, 3 and 4, respectively. The first and second coordinates are the valuation of the first and second agent for the edges, respectively.

  (rank 2). The most preferred bases of agent 1 and 2 are {(a, b), (b, c)} and {(a, c), (b, c)}, respectively. They both have value 2 for it. A possible execution of ROUND-ROBIN is to select (a, b) and then (a, c). This solution contains n r n+1 elements (r = n = 2). It is 1/2-approximate for both agents. Take the graphic matroid associated with the 4 node graph of Figure 3 (rank 3). The most preferred bases of agent 1 and 2 are {(a, b), (c, d), (a, d)} and {(a, c), (c, b), (b, d)}, respectively. They both have value 3 for it. A possible execution of ROUND-ROBIN is to select (a, b) and then (b, c). This solution contains n r n+1 elements (r = 3 and n = 2). It is 1/3-approximate for both agents. Take the graphic matroid associated with the 5 node graph of Figure 3 (rank 4). The most preferred base of agent 1 and 2 are {(a, e), (e, b), (b, d), (c, d)} and {(e, b), (a, b), (b, c), (b, d)}, respectively. They both have value 4 for it. A possible execution of ROUND-ROBIN is to select (a, e), (a, b), and then (a, c). This solution contains n r n+1 elements (r = 4 and n = 2). It is 1/2-approximate for agent 1 and 1/4-approximate for agent 2.

A matching saturates a set if it is incident to all its elements.

Note that the definition of a necessarily s-agreeable set applies to responsive preferences.

The algorithm, inspired of[START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF] Theorem 1], takes pairs of consecutives elements of {f1, . . . , fr} and keeps the one preferred by the second agent. The objective is that both agents prefer the elements that are kept to the elements that are discarded.

Note that if g2 or g3 is added after f3, then a cycle would be created.

The approximation ratio is O(m ln ln m/ ln m) where m is the number of items, and no polynomial-time o(m/ ln m)approximate algorithm exists.

rank r of the matroid 2 3 4 r ≥ 5 approximation ratio for agent 1 1/2 1/3 1/2 r/3 /r approximation ratio for agent 2 1/2 1/3 1/4 1/3

Table 1: The approximation ratios of ROUND-ROBIN where r/3 /r ≥ 1/3.

When the matroid is free, every agreeable set is also 1/2-approximate for every agent [START_REF] Suksompong | Assigning a small agreeable set of indivisible items to multiple players[END_REF]. We are going to study the question of the approximation ratio for a larger class of matroids.

When the rank of the matroid is strictly smaller than the number of agents, the following example illustrates that there are instances without any ρ-approximate solution (disregarding the agreeability).

Example 3. Consider the b-uniform matroid such that E = {e 1 , . . . , e m } and 1 ≤ b < n ≤ m. For any agent ∈ N , ν (e k ) = 1 if k = , and ν (e k ) = 0 otherwise. Since b < n, every solution T has an agent t such that e t / ∈ T , whereas a solution containing e t exists.

Even when there are only two agents, the following example illustrates that there are instances with rank larger than 2 but without any ρ-approximate solution. Examples 3 and 4 illustrate that, as opposed to the case of a free matroid, no algorithm can be ρapproximate for every instance. However, we shall see that there is room for interesting approximation results if we consider two agents and simple matroids. A matroid is simple if every pair of elements is independent [START_REF] Oxley | Matroid Theory[END_REF]. For example, the graphic matroid associated with a simple graph (there is at most one edge between two nodes) is a simple matroid. A b-uniform matroid is simple if b ≥ 2.

We are going to analyze ROUND-ROBIN for s-agreeability and another algorithm for w-agreeability (Algorithm 4), and see that they have approximation ratios which are lower bounded by constants. Matroids of rank 1 are ignored since we restrict ourselves to simple matroids.

Strong Agreeability

We shall see with Theorems 6 and 7 that ROUND-ROBIN combines two nice properties in simple matroids for two agents: it produces a strong agreeable set and this set is a constant approximation for both agents. The approximation ratios are given in Table 1.

The following lemma will be often used in the following proofs.

Lemma 1. Let (E, I) be a matroid with rank r, {f 1 , . . . , f r } a most preferred base of (E, I) for some agent i such that

Proof. By property M3 of matroids, an element of {f 1 , . . . , f |E|+1 } can be added to E. Since f |E|+1 is the element of smallest value in {f 1 , . . . , f |E|+1 }, we get that

Theorem 6. ROUND-ROBIN for two agents is r/3 /r-approximate for agent 1.

Proof. In this proof F = {f 1 , . . . , f r } denotes a most preferred base for agent 1 where

The output of ROUND-ROBIN is I = {e 1 , . . . , e 2r/3 } and we assume that e i is inserted before e j whenever i < j. We will consider three cases: r = 3x, r = 3x -1, and r = 3x + 1.

Suppose r = 3x. In this case r/3 /r = 1/3, and I contains 2r/3 = 2x elements. During the execution of ROUND-ROBIN, agent 1 chooses the odd elements {e 2i+1 : i = 0..x -1} where e 2x-1 is the last element inserted by agent 1.

Fix some i ≥ 0. Agent 1 inserts e 2i+1 when the current solution is {e 1 , . . . , e 2i }. By Lemma 1 we get that

Associate with each e 2i+1 the set

In other words, I is 1/3-approximate for agent 1.

Suppose r = 3x -1. In this case r/3 /r = x 3x-1 , and I contains 2r/3 = 2x elements. Agent 1 chooses the odd elements {e 2i+1 : i = 0..x -1} of I. One can partition F in three sets:

Since ν 1 (e 2i+1 ) ≥ ν 1 (f 2i+2 ) for i = 0..x -1 by Lemma 1, we deduce that

Since ν 1 (e 2i+1 ) ≥ ν 1 (f j ) for i = 0..x -1 and 2x + 1 ≤ j ≤ 3x -1 by Lemma 1, we deduce that (x -1)ν 1 (e 2i+1 ) ≥ ν 1 (F 3 ) and then

Combine (3) multiplied by x, (4) multiplied by x, and (5), to get that (3x -1)ν 1 ({e

In other words, I is x 3x-1 -approximate for agent 1. Suppose r = 3x + 1. In this case r/3 /r = x+1 3x+1 , and I contains 2r/3 = 2x + 1 elements. Agent 1 chooses the odd elements {e 2i+1 : i = 0..x} of I. Let O denote {e 2i+1 : i = 0..x}.

One can partition F in three sets:

.x}, and

By Lemma 1 we have ν 1 (e 2i+1 ) ≥ ν 1 (f 2i+2 ) for i = 0..x -1. Summing these inequalities gives

that we multiply by x + 1 to get

odd even rank r of the matroid 2 3 4 r ≥ 5 r = 4q + 2 ≥ 6 or r = 4(q + 1) ≥ 8 approximation ratio for agent 1 1/2 1/3 1/2 1/4 (q + 1)/(4q + 2) approximation ratio for agent 2 1/2 1/3 1/4 1/5 1/5

Table 2: Reachable approximation ratios for w-agreeable solution of size r+1 2 .

given Table 2.

Proof. Suppose for the moment that r ≥ 5. A base {e 1 , . . . , e r } is constructed in Algorithm 4 (step 1). Agent 1 and 2 have inserted the elements with odd and even index, respectively. When r ≥ 5, there are four cases: r ∈ {4q + 1, 4q + 2, 4q + 3, 4q + 4} where q is a positive integer. The elements of {e 1 , . . . , e r } are renamed as {f 1 , . . . , f r } such that ν 1 (f

If r is even then f 1 and f 2 are kept, while the remaining elements are paired as follows: (f 3 , f 4 ), (f 5 , f 6 ), and so on. The element with maximum valuation ν 2 is kept in each of these pairs. If r is odd then f 1 is kept and the remaining elements are paired as follows: (f 2 , f 3 ), (f 4 , f 5 ), and so on. The element with maximum valuation ν 2 is kept in each of these pairs. The output of Algorithm 4 is I.

From the viewpoint of agent 1, the elements put in I are, in the worst case, f 1 , f 2 , f 4 , f 6 , . . . when r is even, and f 1 , f 3 , f 5 , . . . when r is odd. Observe that ν 1 (f 1 ) ≥ ν 1 (e 1 ), and ν 1 (f i ) ≥ ν 1 (e 2i-1 ) for i ∈ {2, . . . , r/2 } because in each odd round of ROUND-ROBIN, agent 1 selects the element with largest valuation ν 1 that can be inserted in the current solution. Thus, from the viewpoint of agent 1, the elements that are kept are, in the worst case, e 1 , e 3 , e 7 , e 11 , . . . when r is even, and e 1 , e 5 , e 9 , . . . when r is odd. More precisely, the sequence is e 1 , e 3 , e 7 , e 11 , . . . , e 4q+3 when r = 4(q + 1), e 1 , e 3 , e 7 , e 11 , . . . , e 4q-1 when r = 4q + 2, and e 1 , e 5 , e 9 , e 13 , . . . , e 4q+1 when r ∈ {4q + 1, 4q + 3}.

Let A * = {a 1 , . . . , a r } be a most preferred base for agent 1 where ν 1 (a 1 ) ≥ ν 1 (a 2 ) ≥ . . . ≥ ν 1 (a r ). We know from Lemma 1 that ν 1 (e i ) ≥ ν 1 (a i ) holds when i is odd. It follows that ν 1 (I) ≥ ν 1 ({a 1 , a 3 , a 7 , a 11 , . . . , a 4q+3 }) when r = 4(q + 1), (17) ν 1 (I) ≥ ν 1 ({a 1 , a 3 , a 7 , a 11 , . . . , a 4q-1 }) when r = 4q + 2, and (18) ν 1 (I) ≥ ν 1 ({a 1 , a 5 , a 9 , a 13 , . . . , a 4q+1 }) when r ∈ {4q + 1, 4q + 3}.

(19) Suppose r = 4(q + 1) for some integer q ≥ 1. Consider the set

For i = 0..q -1, use ν 1 (a 1 ) ≥ ν 1 (a 4i+6 ) to get that

Use ν 1 (a 4q+3 ) ≥ ν 1 (a 4q+4 ) to obtain

Use ν 1 (a 1 ) ≥ ν 1 (a 2 ) to obtain

Combine Inequalities (20) to (23) to obtain

Use Inequalities ( 17) and ( 24) to get that (4q+2)ν 1 (I) ≥ (q+1)ν 1 (A * ). In other words, I is (q+1)/(4q+2)approximate for agent 1 when r = 4(q + 1). Suppose r = 4q + 2 for some integer q ≥ 1. Consider the set A 2 = {a 1 } ∪ {a 4i+3 : 0 ≤ i ≤ q -1}. In this case, Inequalities (20), (21), and (23) hold. Combine them to obtain

Use Inequalities ( 18) and ( 25) to get that (4q + 2)ν 1 (I) ≥ (q + 1)ν 1 (A * ). In other words, I is (q + 1)/(4q + 2)-approximate for agent 1 when r = 4q + 2.

Suppose r ∈ {4q + 1, 4q + 3} for some integer q ≥ 1. Consider the set

Sum Inequality (26) for i = 0..q to get 4ν

Inequalities ( 19) and ( 27) give 4ν 1 (I) ≥ ν 1 (A * ), which means that I is 1/4-approximate for agent 1 when r ∈ {4q + 1, 4q + 3}. Note that r ∈ {4q + 1, 4q + 3} is equivalent to r odd and r ≥ 5.

Now we take the viewpoint of agent 2 who has inserted the elements with even indexes in the base {e 1 , . . . , e r }. By construction ν 2 (e 2 ) ≥ ν 2 (e 4 ) ≥ ν 2 (e 6 ), and so on. Observe that the element of {e 1 , . . . , e r } with maximum valuation ν 2 belongs to the output of Algorithm 4. Therefore, e 2 , or e 1 if ν 2 (e 1 ) > ν 2 (e 2 ), must belong to I. One cannot guarantee that e 4 belongs to I because e 4 can be paired with e 2 . In that case only e 2 is kept. However, e 4 and e 6 cannot be both paired with e 2 , meaning that I must contain an element valued at least ν 2 (e 6 ). Using this argument repeatedly, I must contain an element valued at least ν 2 (e 4i+2 ) for i = 1.. r-2 4 .

Consider the set

For i ∈ {1, . . . , r-2 4 }, deduce from ν 2 (b 4i+2 ) ≥ ν 2 (b j ) for 4i + 2 ≤ j ≤ max(4i + 5, r) that

Combine Inequalities (31) and (32) to get that 5ν 2 (b 1 ) + 4

The lefthand part being upper bounded by 5ν 2 (B 1 ), we obtain

Use Inequalities (30) and (33) to obtain 5ν 2 (I) ≥ ν 2 (B), i.e. I is 1/5-approximate for agent 2.

Different approximation ratios are reached by Algorithm 4 when r ∈ {3, 4}. When r = 3, the solution is of size 2 and it contains the most preferred element of each agent. Therefore, is 1/3-approximate for both agents by Lemma 1. When r = 4, the solution is of size 3. It contains the first and third preferred element of agent 1, and the most preferred element of agent 2. Therefore, it is 1/2-approximate for agent 1 and 1/4-approximate for agent 2 by Lemma 1.

The case r = 2 corresponds to step 3 of Algorithm 4. Both agents have inserted their most preferred element. Thus, the solution is 1/2-approximate for both agents because the matroid is simple. Proposition 5. There exist instances for which the approximation ratios given in Theorem 8 are reached by Algorithm 4.

Proof. For r ∈ {2, 3, 4}, use the instances depicted on Figure 3.

For r = 5, take the graphic matroid associated with the graph of Figure 5. A most preferred base for agent 1 consists of the edges {(a, b), (b, f ), (f, e), (b, c), (c, d)} (plain edges). A most preferred base for agent 2 consists of the edges {(a, f ), (a, e), (b, e), (e, c), (e, d)} (dotted edges). Agents 1 and 2 value their most preferred base 4 and 5, respectively. Algorithm 4 may take the edges: (a, b), (a, e), (e, f ), (e, c), (c, d). The reordering with respect to ν 1 can be (a, b), (e, f ), (c, d), (e, c), (a, e). The rank being odd, I consists of (a, b), the edge that agent 2 prefers between (e, f ) and (c, d), that is (c, d), and one edge out of {(e, c), (a, e)}, say (e, c). Therefore, ν 1 (I) = ν 2 (I) = 1 + . When → 0, I is 1/4-approximate for agent 1 and 1/5-approximate for agent 2.

Examples with r > 5 and r odd can be derived from the graph of Figure 5. Indeed, add two new edges valued (0, 0) between one node, say a, and two new nodes. This operation increases the rank by two units (r remains odd) and it can be done as many times as necessary. For this extended instance, the previous paragraph indicates that Algorithm 4 can output a solution which is 1/4-approximate for agent 1 and 1/5-approximate for agent 2.

For r even and r ≥ 6, take the graphic matroid associated with the graph of Figure 4. The rank can be singly even (r = 4q + 2) or doubly even (r = 4(q + 1)), which defines a parameter q is each case. Agent 1 has value 1 for every edge f i such that 1 ≤ i ≤ 4q + 2 and her value for the other edges is 0. In particular, when r = 4(q + 1), agent 1 has value 0 for the edges f 4q+3 and f 4q+4 . Agent 2 has value 1 for every edge g i such that 1 ≤ i ≤ 5 and her value for the other edges is 0. A most preferred base for agents 1 and 2 consists of the edges {f 1 , . . . , f r } (plain edges) and the edges {g 1 , . . . , g r } (dotted


Imed-Eddine Benrabah

Yves Brechet

Gary Purdy

Christopher Hutchinson

Hatem Zurob

On the origin of the barrier in the bainite phase transformation

The experimental lengthening kinetics of bainitic ferrite in steels have been consistently shown in the literature to be slower than those predicted using the diffusional Zener-Hillert model. Reconciliation of the experimental and calculated kinetics has required the introduction of a 'barrier energy' which until now has not had a clear physical meaning. A modified diffusional growth model based on the Zener-Hillert model for plate-like ferrite growth is introduced here which contains a physics-based barrier energy. The model assumes diffusion controlled growth and takes into account a barrier energy arising from interfacial disconnections motion and their interaction with defects in the matrix. The model is able to successfully describe the C-curve growth rate of Widmanstätten ferrite and bainitic ferrite in a wide range of steels.

, and others arguing in favor of a diffusional process controlled by carbon

diffusion [8][9][10][11]. In both approaches, it is necessary to introduce an energy barrier, in order to reproduce the experimental results (e.g. carbon content in austenite or T0' limit) [START_REF] Bhadeshia | Bainite in Steels: Transformations, Microstructure and Properties[END_REF]10]. The goal of this contribution is to examine the origin of this barrier energy.

For the purpose of this contribution, we consider the diffusional approach for describing the growth of Widmanstätten ferrite and bainitic ferrite. The growth of plate-like ferrite proceeds through the movement of disconnections at the ferrite/austenite interface [12][13][14]. The movement of disconnection is responsible for both the structural change (fcc to bcc) and the shape change (e.g. surface relief) that take place. The transformation rate is controlled by the rate at which the disconnections move and this is ultimately controlled by the rate of carbon diffusion at the disconnections. Following Howe and Hirth [13], such a transformation can be described as a diffusional-displacive transformation. This description is not unique to the growth of plate-like ferrite/bainite. Plate-like (or acicular) morphologies are also observed in other alloys, such as Ag-Cd [15], Zr-Nb [16] and Ti-based alloys [17]. In the Ti-Cr system, it has been shown that diffusional plate-like transformations proceed by the motion of transformation disconnections/structural ledges and at the same time demonstrate tent-shaped surface relief [17][18][19][20].

Several attempts have been made to describe ferrite plate lengthening kinetics under the assumption of carbon diffusion controlled growth [10,[21][22][23]. The Hillert-Zener [9] equation was used by several authors to describe the plate lengthening rates in low alloyed steels. Hillert was the first to highlight that the experimental rates were sometimes slower than the calculated rates [24]. Kaufman et al. [25] also reported slower experimental growth rates compared to the diffusion controlled theory predictions and attributed these discrepancies to uncertainties the interfacial energy used in the Hillert-Zener equation [24,26]. Improvements were later made to the diffusional growth equation by Trivedi et al. [27] but these didn't change the general picture of slower experimental kinetics compared to the calculations. Leach et al [10]. have recently suggested modifications to the Hillert-Zener equation to reduce some of the approximations and proposed the introduction of a 'barrier energy' to reconcile the differences between the measured and the calculated growth rates. The authors suggest that the barrier energy increases with carbon content. The physical origin of this barrier energy was not discussed.

In the present contribution, a model is proposed to describe the austenite decomposition to plate-like products at temperatures above Ms. These products involve both Widmanstätten ferrite and bainitic ferrite. The model takes into account both long range diffusion of carbon and disconnection motion to describe the lengthening of plate-like ferrite in steels. A physical interpretation of the barrier energy is proposed and calculations demonstrate that this can reconcile the previously observed differences between the calculated and experimental growth rates.

The present model is based on the classic Zener-Hillert equation [9], where the plate-shaped ferrite lengthening rate is controlled by carbon diffusion in the austenite and can be expressed as:

𝑣 𝑚𝑎𝑥 = 𝐷 𝐿 𝑥 γ/α -𝑥 0 𝑥 0 -𝑥 α/γ ( 1 )
where 𝑥 0 is the carbon mole fraction in the bulk, 𝑥 γ/α is the carbon mole fraction at the austenite side of the interface and 𝑥 α/γ is the carbon mole fraction at the ferrite side of the interface. 𝐷 is the carbon diffusion coefficient in austenite and 𝐿 is the diffusion distance, assumed to be proportional to the curvature radius 𝑟 of the growing needle, 𝐿 = 𝑎𝑟. Hillert evaluated the 𝑎 parameter to 2.

One of the uncertain parameters is the carbon diffusion coefficient in austenite. Trivedi et al. [27] suggested using an effective diffusion coefficient calculated as an average over the diffusion profile:

𝐷 𝑒𝑓𝑓 = 1 𝑥 γ/α -𝑥 0 ∫ 𝐷(𝑥) 𝑥 γ/α 𝑥 0 ( 2 )
We adopt the suggestion of Trivedi et al. and consider an effective diffusion coefficient calculated, over an effective distance of diffusion 𝐿, as shown by Eq. ( 3) :

𝐷 𝑒𝑓𝑓 = 1 𝑥 γ/α -𝑥 𝐿 ∫ 𝐷(𝑥) 𝑥 γ/α 𝑥 𝐿 ( 3 )
where 𝑥 𝐿 is the carbon mole fraction at the diffusion distance L from the γ/α interface.

To solve Eq. ( 1) and calculate the interface velocity, one must define the interface conditions that govern the transformation. A local energy balance at the interface (γ/α) is used, Eq. ( 4) :

𝛥𝐺 𝑚 𝑐ℎ𝑒𝑚 = 𝛥𝐺 𝑚 𝑆𝐷 + 𝛥𝐺 𝑚 𝑓𝑟𝑖𝑐 + 𝛥𝐺 𝑚 𝐺𝑇 + 𝛥𝐺 𝑚 𝑚𝑒𝑐 4 ( 4 )
Δ𝐺 𝑚 𝑐ℎ𝑒𝑚 is the chemical driving force acting over the interface, Δ𝐺 𝑚 𝑆𝐷 is the dissipated energy due to solute drag, Δ𝐺 𝑚 𝑓𝑟𝑖𝑐 is the energy dissipated due to the fcc-bcc structural rearrangement, Δ𝐺 𝑚 𝐺𝑇 is the curvature energy and Δ𝐺 𝑚 𝑚𝑒𝑐 is a mechanical 'barrier' energy to be discussed below.

We assume the interface mobility is large enough for the dissipated energy due to interface friction to be negligible. The experimental interface velocities are slow enough that this dissipation calculated using any of the estimates for the intrinsic mobility lead to a negligible dissipation due to friction. The solute drag energy is also considered small enough to be neglected. It should be noted that this assumption is only valid in low alloyed steels. In its present form, the model can not be used to explain the bay observed in the TTT diagrams for steels containing Cr and Mo. The chemical driving force is calculated using the proposed expression by Hutchinson et al. [28]:

Δ𝐺 𝑚 𝑐ℎ𝑒𝑚 = ∑ { (𝑢 𝑋 α + 𝑢 𝑋 γ ) 2 (μ 𝑋 γ,𝑖 -μ 𝑋 α,𝑖 )} 𝑋 + (𝑢 𝐹𝑒 α + 𝑢 𝐹𝑒 γ ) 2 (μ 𝐹𝑒 γ,𝑖 -μ 𝐹𝑒 α,𝑖 ) ( 5 )
Where 𝑢 𝐹𝑒 = 𝑥 𝐹𝑒

1-𝑥 𝐶

and 𝑢 𝑋 = 𝑥 𝑋

1-𝑥 𝐶

are the molar fractions of Fe and X elements at the austenite and ferrite interface sides, respectively. In principle, complete carbon partitioning does not necessarily take place during the transformation. For simplicity, this initial treatment will assume that carbon is in equilibrium across the interface (i.e. μ 𝐶 γ = μ 𝐶 α ) and the U fractions of iron and the substitutional elements are assumed unchanged across the interface. The present model takes into account the effect of the substitutional elements on the plate-like growth kinetics through their effects in Eq. ( 5). The thermodynamic parameters are evaluated using the TCFE9 database of Thermo-Calc software [29].

The capillarity effect is expressed using the Gibbs Thomson energy (Δ𝐺 𝑚 𝐺𝑇 ) using Eq. ( 6) :

Δ𝐺 𝑚 𝐺𝑇 = 𝑉 𝑚 σ γ/α r ( 6 )
where 𝑉 𝑚 is the molar volume of ferrite and σ γ/α is the interfacial energy.

As suggested in the introduction, the diffusional-displacive plate-like growth proceeds by the motion of transformation disconnections [13,14]. During interface migration, these disconnections interact with the defects (e.g. dislocations) in the matrix, causing an opposing force to interface migration. The opposing force depends on the dislocation density present in the matrix as well as the different obstacles that can hinder disconnections movement. To account for these processes, a mechanical 'barrier' energy is expressed as a function of the internal back stress caused by the interaction between the moving disconnections and the surrounding obstacles (Figure 1). The back stress, σ ̂, describes the minimum stress which is required to activate disconnection motion at the interface. The available driving force for transformation should be sufficient to overcome the opposing energy due to the back stress. The back stress σ ̂ exerts a force per unit length of 𝑚 𝑠 σ ̂𝑏𝑠 on each disconnection, where ms is the Schmid factor and bs is the magnitude of the Burgers vector of the disconnection. The disconnection density per unit surface length is 1/Λ , where Λ is the spacing between disconnections. This results in an opposing force per unit area of 𝑚 𝑠 σ ̂ 𝑏 Λ , which amounts to an energy per unit volume to be subtracted from the driving force available for the transformation. This mechanical barrier energy is expressed using Eq. ( 7) :

Δ𝐺 𝑚 𝑚𝑒𝑐 = 𝑉 𝑚 σ ̂ 𝑏 𝑠 Λ 𝑚 𝑠 ( 7 )
where 𝜎 ̂ is the internal back stress due to disconnection-defect interaction, 𝑚 𝑠 is the Schmid factor, 𝑏 𝑠 is the magnitude of the Burgers vector of the disconnection, and Λ is the average spacing mobile disconnections. [30].

Figure 1 : Schematic representation of the austenite (γ) -ferrite (α) interface during plate-like ferrite lengthening, showing the interaction between the interface disconnections and the surrounding obstacles in the austenite matrix

The internal back stress 𝜎 ̂ is assumed to originate from both disconnection-dislocation interactions as well as disconnection-solute interactions. No distinction is made between mobile and immobile dislocations, and the back stress is estimated using the Taylor equation [START_REF] Krausz | Unified Constitutive Laws of Plastic Deformation[END_REF][START_REF] Taylor | [END_REF] :

σ ̂= α𝑀μ𝑏√ρ + σ 𝑆𝑆 ( 8 )
Where 𝑀 is the Taylor factor (𝑀= 3 for austenite), 𝜇 is the shear modulus estimated as a function of temperature from [33], 𝛼 is a constant of the order of 0.15 for austenite and 𝜎 𝑆𝑆 is the solid solution hardening expressed as [34] :

𝜎 𝑆𝑆 = (1 -0.
Where 𝑇 𝐶 is the transformation temperature and 𝑤 𝑋 is the weight fraction of element X at the austenite/ferrite interface.

The model introduced above is now used to predict Widmanstätten and bainitic ferrite growth kinetics as a function of temperature, using the physically-based barrier described by Eq.( 7). The values of the parameters used in the model are summarized in Table 1. The mechanical 'barrier' energy (Eq.( 7) represents an opposing energy for the plate-like ferrite transformation. The magnitude of this energy increases with decreasing temperature due to the increase of the solid solution strengthening term (𝜎 𝑆𝑆 ) (Eq. ( 9). In the proposed approach, the barrier energy has a clear physical meaning -it originates from the interaction between the moving disconnections at the interface with the obstacles in the matrix (dislocations and solute elements).

Figure 2 compares the experimental lengthening rates of plate-shaped ferrite as a function of temperature for different binary Fe-C (2-a to 2-d) and low alloyed steels (2-e and 2-f), with the model predictions using the classic Zener-Hillert approach (i.e. model without barrier) as well as our proposed approach (i.e. model with barrier) described above that includes a physically-based barrier energy (Eq.( 7)). Figure 2 demonstrates that the classic Zener-Hillert approach overestimates the experimental growth kinetics, and this is consistent with previous reports [9,10,36]. The addition of a barrier energy represented here by the mechanical energy (Eq.( 7) provides a much better description of the measured growth kinetics as a function of temperature for the different alloy compositions. [36,37], b) Fe-0.7C [36], c) Fe-0.91C [38], d) Fe-1.43C [38], e) Fe-0.59C-0.56Mn-0.25Si [38] and f) Fe-0.81C-0.23Mn-0.26Si (wt.%) [37].

The mechanical 'barrier' energy described using Eq. ( 7), ( 8) and ( 9) is independent of the bulk carbon composition. This is because the solid solution term (Eq. 9) is calculated using the compositions at the austenite interface, which is independent of the bulk carbon composition when assuming that carbon is at equilibrium across the interface. However, the 'barrier' energy does depend on temperature. Figure 3 shows an example of the barrier energy evolution as a function of temperature for three alloys: Fe-0.5C, Fe-0.7C and Fe-0.59C-0.56Mn-0.25Si (wt.%). For the three cases, the barrier energy decreases with increasing temperature and it is similar for the three cases. The effect of the substitutional elements is negligible here due to the low content in the studied alloys (Fe-0.59C-0.5Mn-0.2Si wt.%). At higher solute content, the carbon interface contents can be affected, and thus the 'barrier' energy will be different.

Figure 2 :

 2 Figure 2 : Comparison between measured lengthening rates of plate-like ferrite in different steels and the calculated ones using the classical Zener-Hillert model (solid lines) as well as the present model (dashed lines). a) Fe-0.5C[36,37], b) Fe-0.7C[36], c) Fe-0.91C[38], d) Fe-1.43C[38], e) Fe-0.59C-

Figure 3 :

 3 Figure 3 : The barrier energy evolution as a function of temperature for three steels, Fe-0.5C, Fe-0.7C and Fe-0.59C-0.56Mn-0.2Si (wt.%).

Table 1 :

 1 Summary of the different parameters used in the present calculations. 𝒎 𝒔 𝛔 𝛄/𝛂 (𝑱. 𝒎 𝟐 ) 𝑽 𝒎 (𝐦 𝟑 . 𝐦𝐨𝐥 -𝟏 )

	Variable	𝛒 (𝒎 -𝟐 )	𝚲 (𝐦)	𝒃 𝒔 (m)
	Value	10 13 [35] 1.5 × 10 -9 [13] 2.0 × 10 -9 [13]	0.5	0.23 [10]	7.09 × 10 -6

Acknowledgements

HZ acknowledges the support of the Natural Science and Engineering Research Council of Canada. The authors are grateful to JD Embury for valuable discussions.

𝑊𝐵𝑠 (°𝐶) = 850 -206𝐶 -78𝑀𝑛 -33𝑁𝑖 -70𝐶𝑟 -75𝑀𝑜 -61𝑆𝑖 ( 11 ) The carbon effect on the WBs temperature is well captured by the present calculations. On the other hand, except for nickel, the effect of the other solutes (Mn, Mo, Cr and Si) on the WBs temperature is underestimated by the present calculations. One possible explanation may be related to the solute drag effect which was neglected in the present study. This effect is mainly operative at high temperatures, where solute diffusion becomes comparable to the interface velocity.

In summary, the kinetics of plate-like ferrite growth in steels is examined in the context of carbon diffusion being the rate-controlling process. The classic Zener-Hillert model is used with interfacial conditions governed by an energy balance between the chemical free energy acting over the interface, the Gibbs-Thomson energy to account for the curvature effect and a new physically-based 'mechanical barrier energy' to describe the effect of defects in the matrix on interface motion.

The mechanical barrier energy introduced here provides a physical basis for the barrier introduced by Leach et al. [36] in the Zener-Hillert model to explain the discrepancies between the measured and calculated growth rates using the diffusion based theory. The barrier comes from the interaction between the moving disconnections at the interface with the existing defects in the matrix such as dislocations and solute elements. Since the interaction is located at the interface disconnections, the relevant pinning force is computed using the local chemical composition.

Appendix : Parametric sensitivity of the 'barrier' energy (Supplementary materials)

There is some uncertainty in the values of the parameters used to calculate the barrier energy in Eq.( 7) (such as the dislocation density in austenite and the disconnections spacing Λ). For this reason, a sensitivity analysis of the calculated ferrite lengthening as a function of these parameters was undertaken as shown in Figure A1. The alloy Fe-0.5wt%. was chosen for illustration. Increasing the dislocation density by an order of magnitude has limited effect in the present case. The disconnection spacing was varied between 1 nm and 2 nm and the results show a considerable effect of this parameter on the calculate growth kinetics at low temperatures. It is clear that a detailed investigation of this parameter (as well as the Burgers vector of the disconnections) will aid in the refinement of the model.