Bruno Escoffier

Laurent Gourvès

Jérôme Monnot

Stefano Moretti

Cost allocation protocols for network formation on connection situations

Keywords: F.2.2 [Nonnumerical Algorithms and Problems]: Computations on discrete structures; G.2.1 [Combinatorics]: Combinatorial algorithms Algorithms, Theory Spanning tree, game theory

HAL is

INTRODUCTION

Due to economic and environmental concerns, reducing energy consumption in telecommunications is a priority, and the issue of embedding cost-awareness in the design of communication network devices and protocols using game theory has been growing at a fast rate in last years [START_REF] Tembine | Joint power control-allocation for green cognitive wireless networks using mean field theory[END_REF][START_REF] Bianzino | The green-game: striking a balance between qos and energy saving[END_REF]. In particular, game theory applied to connection situations seems to provide a powerful and realistic methodology to analyze the design of cost allocation protocols. A connection situation arises when there is a group of agents (e.g. devices of a communication network) who all want to be connected with a source 0 (e.g. a server), directly or via other agents, and where connections are costly (e.g. due to data traffic costs). Cost sharing problems on connection situations were introduced by Claus and Kleitman [START_REF] Claus | Cost allocation for a spanning tree[END_REF] and have been studied with the aid of cooperative game theory since the basic paper of Bird [START_REF] Bird | On cost allocation for a spanning tree: a game theoretic approach[END_REF]. Given a connection situation, Bird [START_REF] Bird | On cost allocation for a spanning tree: a game theoretic approach[END_REF] introduced an associated coalitional game (known as minimum cost spanning tree (mcst) game), where the players are the agents placed on the nodes and the cost incurred by a coalition is the minimal cost of connecting this coalition to the source via links between members of the coalition. Since then, many cost sharing protocols have been proposed in the literature of mcst games [START_REF] Granot | Minimum cost spanning tree games[END_REF][START_REF] Granot | On the core and nucleolus of minimum cost spanning tree games[END_REF][START_REF] Tijs | Obligation rules for minimum cost spanning tree situations and their monotonicity properties[END_REF][START_REF] Moretti | Cost Allocation Problems Arising from Connection Situations in an Interactive Cooperative Setting[END_REF][START_REF] Moretti | Cost allocation protocols for supply contract design in network situations[END_REF][START_REF] Norde | Minimum cost spanning tree games and population monotonic allocation schemes[END_REF][START_REF] Tijs | Obligation rules for minimum cost spanning tree situations and their monotonicity properties[END_REF][START_REF] Branzei | The p-value for cost sharing in minimum cost spanning tree situations[END_REF][START_REF] Moretti | Cost allocation protocols for supply contract design in network situations[END_REF][START_REF] Tijs | The bird core for minimum cost spanning tree problems revisited: monotonicity and additivity aspects[END_REF] with various desirable properties including budget balance and cost monotonicity.

Budget balance consists of satisfying both cost recovery (i.e. the cost of the service is recovered from all the players) and competitiveness (i.e. no surplus is created because if any surplus is created then a competitor can provide the service at a cheaper cost by reducing the surplus) [START_REF] Devanur | Strategyproof cost-sharing mechanisms for set cover and facility location games[END_REF].

Many papers concerning the analysis of cost allocation protocols using coalitional games have focused on cost monotonicity properties, meaning that if some connection costs go down (up), then no agents will pay more (less) (see for instance [START_REF] Dutta | Cost monotonicity, consistency and minimum cost spanning tree games[END_REF][START_REF] Tijs | Obligation rules for minimum cost spanning tree situations and their monotonicity properties[END_REF][START_REF] Branzei | Connection situations under uncertainty and cost monotonic solutions[END_REF][START_REF] Bergantiños | On some properties of cost allocation rules in minimum cost spanning tree problems[END_REF][START_REF] Bergantiños | On obligation rules for minimum cost spanning tree problems[END_REF][START_REF] Branzei | Connection situations under uncertainty and cost monotonic solutions[END_REF]). In the paper of [START_REF] Dutta | Cost monotonicity, consistency and minimum cost spanning tree games[END_REF], for instance, a particular cost monotonic protocol was studied, where cost monotonicity means that an agent i does not pay more if the cost of a link involving i decreases, nothing else changing in the network. The interest for monotonicity properties for protocols in connection situations is explained by the fact that in many real applications, connection costs may increase or decrease with time, and therefore cost allocations which are stable only in the original situation cannot guarantee the cooperation among agents also under the new conditions. This is the case, for instance, for telecommunication networks, where it may happen that at a given moment the cost of connections can increase (e.g. as a consequence of an improvement in quality and quantity of services supplied) or decrease (e.g. by improving telecommunication technologies). Another reason to analyze cost monotonicity is that it ensures that no customers are motivated to voluntary increase the cost of adjacent links, since according to a cost monotonic allocation protocol no customer will pay less. Note that this kind of considerations arise from interaction situations which are based on cooperative models, where the issue concerning the "strategic" behavior of players is somehow left to the intuition.

In parallel, since the seminal paper [START_REF] Aumann | Endogenous formation of links between players and coalitions: an application of the shapley value[END_REF], another class of related problems has been widely studied in the literature of game theory applied to networks. The basic question of such problems is to describe an endogenous process of the formation of communication links, given some underlying protocol for allocating the benefit of communication, namely the Myerson value [START_REF] Myerson | Graphs and cooperation in games[END_REF]. The paper by Aumann and Myerson [START_REF] Aumann | Endogenous formation of links between players and coalitions: an application of the shapley value[END_REF] introduced a model of link formation where links are constructed sequentially. Later, Myerson [START_REF] Myerson | Game theory: analysis of conflict[END_REF] introduced a model of link formation in strategic form where players announce simultaneously the set of players they would like to communicate with, and a link between two nodes is formed if both nodes announce to form it. As in the previous model, the payoffs of players is calculated according to the Myerson value. Later, Slikker and van den Nouweland [START_REF] Slikker | Network formation models with costs for establishing links[END_REF] introduced an extension of such models for link formation that incorporate costs of formation of communication links (see also [START_REF] Jackson | A survey of network formation models: stability and efficiency[END_REF][START_REF] Jackson | Social and economic networks[END_REF]). An interpretation of these models with costs of link formation is that players at first stage incur the costs of link formation and divide these costs in a fair manner and then, at a second stage, bargain over the division of the benefits (see also [START_REF] Slikker | Decision making and cooperation structures[END_REF]).

The objective of this paper is threefold. First, we want to integrate cost allocation protocols for connection situations with the model of network formation with communication costs. In this direction, a game in strategic form is presented where agents are placed on the nodes of a graph and the strategy of each player is to construct a single link which connects himself to another node in the network (that may be another agent or a source). Each link is costly, as in usual connection situations, and the cost of remaining disconnected from the source is larger than any finite cost that should be supported to guarantee the connection with the source. So, agents want to be connected to the source at any cost, but of course they are self-interested to save their own money. Actually, this strategic game has been already introduced in [START_REF] Gourvès | Three selfish spanning tree games[END_REF], but in that paper the authors focused on a specific cost allocation protocol for trees: the Bird rule [START_REF] Bird | On cost allocation for a spanning tree: a game theoretic approach[END_REF] assigning to each player i the cost of the link from i to the its predecessor on the unique path from the source to i (see also [START_REF] Feltkamp | Birds tree allocations revisited[END_REF][START_REF] Bergantiños | A non-cooperative approach to the cost spanning tree problem[END_REF][START_REF] Bergantiños | Optimal equilibria in the non-cooperative game associated with cost spanning tree problems[END_REF] for other strategic models applied to connection situations).

The second objective of this paper is to analyze properties for cost allocation protocols (including but not limited to the Bird one), and in particular the role of cost monotonicity and other state-dependent properties in the convergence of the best response dynamic [START_REF] Gilboa | Social stability and equilibrium[END_REF]. Contrary to the situation based on a cooperative setting, where cost monotonicity seems to interpret a condition of stability in dynamic situations [START_REF] Moretti | Cost Allocation Problems Arising from Connection Situations in an Interactive Cooperative Setting[END_REF], we show that cost monotonicity of protocols is incompatible with the optimality of associated best response dynamics.

Finally, the third and main goal of this manuscript is to answer an open question concerning the existence of a cost allocation protocol that guarantees the convergence of each best response dynamic to a network of minimum connection cost. This is not the case, for instance, of the cost allocation protocol based on the Bird rule, which allows for the possibility of Nash equilibria which do not correspond to a graph of minimum cost [START_REF] Gourvès | Three selfish spanning tree games[END_REF].

We start in the next section with a brief introduction of the main notations and the definition of the model of strategic game applied to connection situations. Section 3 focuses on the relation between cost monotonicity and the statedependent property with the property of optimality for protocols. Section 4 is devoted to two optimal protocols and to the analysis of their properties of convergence. Section 5 concludes.

PRELIMINARIES AND NOTATIONS

Let G = (V, E, w) be an undirected, connected and weighted graph on n = |V | vertices and m = |E| edges where V = {0, 1, • • • , n -1} and where each edge e ∈ E has a non negative weight w(e) ∈ R + . Node 0 is called the root (or the source) and any other node is an agent who wants to be connected to 0 either directly or via other nodes which are connected to 0. For any set of edges E ′ we denote by w(E ′ ) its total weight:

w(E ′ ) = ∑ e∈E ′ w(e).
As a notation V (.) and E(.) are two functions which designate the vertex set and edge set of their argument, respectively. The subgraph of G induced by the vertex set

V ′ ⊆ V is denoted by G[V ′ ].
We consider a strategic game form

(V \{0}, NG(1)×NG(2)× • • • × NG(n -1)
) where the strategy space NG(i) of every player i ∈ {1, • • • , n -1} is his neighborhood in the graph. When a player i plays its neighbor j then the edge (i, j) is built. A state (or strategy profile) S is a vector

(S1, S2, • • • , Sn-1) ∈ NG = NG(1)×NG(2)ו • •×NG(n-1).
In the following, S-i denotes S from which the strategy of player i was removed and (S ′ i , S-i) denotes the state S from which Si was replaced by S ′ i .

The edges built by the players and associated with S is denoted by E(S) and defined as {(i, Si)

: i = 1, • • • , n -1}.
Let S be any state. We denote by con(S) and dis(S) the players who are connected and disconnected from the source, respectively. Let CCS be the connected component of E(S) that contains the source and E(CCS) be the edges of the connected component CCS. TS = E(CCS) ∩ E(S). Note that TS is a tree, since TS is connected by construction and contains exactly |TS| + 1 vertices. Note also that con(S) is the vertex set of CCS\{0} and TS = {(i, Si) : i ∈ CCS\{0}}.

We suppose that every player wants to be connected to the source at the least possible cost. To do so the players interact with a protocol which, given the strategy profile, allocates a cost to the players. More formally, given a graph G, a cost allocation protocol (or, simply, a protocol ) is a map c : (R + ) m × NG → (R + ) n-1 , which assigns to every weight vector w ∈ (R + ) m and every state S ∈ NG a cost vector (c1(w, S), • • • , cn-1(w, S)) ∈ (R + ) n-1 (if the weight function is clear from the context and no confusion arises we simply denote it as (c1(S),

• • • , cn-1(S))).
A cost allocation protocol c such that ∑ i∈con(S) ci(S) = w(TS) for every strategy profile S is said budget balanced. This property implies that the cost of the edges in the network connected to the source is fully supported by its users. In the remaining of the paper we will focus on budget balanced protocols and the associated strategic games (V \ {0}, NG, c).

Given a protocol c, a strategy x ∈ NG(i) is a better response of player i with respect to the strategy profile S if ci(x, S-i) < ci(S). We say that x is a best response when ci(x, S-i) = min y∈N G (i) ci(y, S-i).

A state S is a Nash equilibrium of the game, if for every player i, it holds that Si is a better response of player i to S-i. For a state S and a player i, let NS(i) be the sets of strategies of player i resulting from a better response of player i, ie.,

NS(i) = {j ∈ {0, . . . , n -1} : ci(j, S-i) < ci(S)}; in particular, NS(i) ⊆ NG(i) and S is a NE iff NS(i) = ∅ for every i ∈ {1, . . . , n -1}.
A Better Response Dynamic (BRD, also called Nash dynamics) (associated with a protocol c) is a sequence of states S 0 , S 1 , . . . , such that each state S k (except S 0 ) is resulted by a better response of some player from the state S k-1 . Note that if a better response dynamic reaches a Nash equilibrium after a finite number of states, then no further changes of strategies are expected (if we assume that a player changes his strategy only if he strictly prefers a different strategy).

DYNAMICS OF PROTOCOLS

In this section we are interested in analyzing properties of cost allocation protocols in connection situations where agents are continuously prepared to improve their payoff in response to changes made by other agents. How should we design cost allocation protocols to minimize the efficiency loss caused by selfish players that are only willing to perform update leading to an immediate reduction of their individual cost shares?

A natural approach to this problem is the analysis of each BRD associated with a certain protocol. With this objective, the following properties should be considered.

Definition 1 (CONV). We say that a cost allocation protocol converges to an equilibrium iff every associated BRD reaches a Nash equilibrium. We say that a Nash equilibrium S is efficient iff the corresponding graph E(S) is a minimum cost spanning tree (mcst) (i.e. w(E(S)) equals the minimum cost over all networks connecting all nodes in V ).

Definition 2 (OPT). We say that a cost allocation protocol is optimal iff every associated BRD reaches an efficient Nash equilibrium.

Obviously the OPT property implies the CONV one. The protocol based on the Bird rule, which charges each player i in state S with the weight w(i, Si) is budget balanced, CONV but not OPT [START_REF] Gourvès | Three selfish spanning tree games[END_REF].

Consider the following property for cost allocation protocols.

Definition 3 (IMON).

We say that a cost allocation protocol is Individually Monotonic iff for every S ∈ NG, i ∈ con(S) and Ŝi ∈ NG(i)

w(i, Ŝi) ≥ w(i, Si) ⇒ ci( Ŝi, S-i) ≥ ci(S).
Looking at the motivations that justify the interest in monotonicity properties in the cooperative setting, one could erroneously argue that individual monotonicity is a good candidate property to guarantee the implementation of a network of minimum cost. However, it is easy to show that there is no cost allocation protocol which satisfies both IMON and OPT properties, implying that a large family of cost monotonic solution from the literature on minimum cost spanning tree games are not optimal in this framework [START_REF] Moretti | Cost Allocation Problems Arising from Connection Situations in an Interactive Cooperative Setting[END_REF].

Proposition 1. There is no cost allocation protocol which satisfies both IMON and OPT properties.

Proof. Suppose it exists a protocol c which is IMON and OPT. Consider the instance of Figure 1 and the suboptimal strategy profile where player 1 plays 2 while player 2 plays 0. If a player changes his strategy then his cost increases. Indeed, if player 1 plays 0 then his cost increases by IMON. Meanwhile, if player 2 plays 1 then he is not connected anymore so his cost is infinite. So this state is a Nash equilibrium but not an efficient one 1 .

Another property that is particularly valuable in the analysis of the endogenous formation of networks is the statedependent property, saying that the allocation of the cost of 1 For illustrative purposes, this proof is based on a situation with only two players; obviously, the same considerations apply to situations with more than two players. the network TS connected to the source in a state S should not depend on the edges not constructed under S. Definition 4 (SDEP). We say that a cost allocation protocol is State Dependent iff for every state S, for every weight functions w ∈ (R + ) m and w ′ ∈ (R + ) m , with w(e) = w ′ (e) for every e ∈ TS, then ci(w, S) = ci(w ′ , S) for every i ∈ con(S).

This property allows for the continuous control of the charge procedure by means of the simple observation of the edges constructed under state S, without assuming the knowledge of the weights of the links of the entire network (see for instance the class of construct and charge (CC )-rules in [START_REF] Moretti | Cost allocation protocols for supply contract design in network situations[END_REF] for a family of cost allocation protocols that meet the requirement of continuous monitoring by the agents involved). Unfortunately, also this property is incompatible with the OPT property, as it is shown by the following proposition.

Proposition 2. There is no cost allocation protocol which satisfies both SDEP and OPT properties.

Proof. By Proposition 1, it is sufficient to prove that if a cost allocation protocol satisfies SDEP and OPT properties than it is satisfies IMON property too. Suppose it does not. This means there exists S, i and Ŝi such that w(i, Ŝi) ≥ w(i, Si), and ci(w, ( Ŝi, S-i)) < ci(w, S). Take a weight function w ′ ∈ (R + ) m , where w ′ (e) = w(e) if e ∈ TS ∪ {(i, Ŝi)} or if e / ∈ E(CCS), and the cost of all the other edges with vertices in CCS is maxe∈E{w(e)} + 1. So the graph TS is the unique optimal tree with respect to w ′ . By the SDEP property, we have that ci(w ′ , ( Ŝi, S-i)) = ci(w, ( Ŝi, S-i)) < ci(w, S) = ci(w ′ , S), which yields a contradiction with the OPT property.

Therefore, in order to prosecute in our research for the OPT property, we must renounce to some interesting and well studied properties of cost allocation protocols in the cooperative setting, like obligation rules [START_REF] Tijs | Obligation rules for minimum cost spanning tree situations and their monotonicity properties[END_REF], which are cost monotonic, and CC-rules [START_REF] Moretti | Cost allocation protocols for supply contract design in network situations[END_REF], which are state-dependent. Nevertheless, next section shows that optimal budget balanced protocols exist.

TWO OPTIMAL PROTOCOLS

We assume that the edges of G satisfy w(e1) ≤ w(e2) ≤ • • • ≤ w(em). In the following, we always compute a mcst with Kruskal's algorithm applied on that edge order.

Let T *

S be the mcst built using Kruskal's algorithm on the subgraph G[con(S)]. We denote by OP TS the total weight of T * S , and by S * a state which corresponds to T * S .

We say that a player i ∈ con(S) follows T * S in S iff Si = S * i . In other words, the strategy of player i is his first neighbor in the unique path from him to the source 0 in the tree T * S .

Let ∆(S) = ∑ e∈E(CC S ) w(e) -OP TS; it is the difference between the weight of the edges built by the players connected to the source and the minimal weight for connecting these players.

We propose two protocols. Recall that the cost of a non connected player is infinite, so to define a protocole we shall define the cost of connected players (as previously noted, all the players will be connected in any Nash equilibrium).

In the first protocol, all connected players fairly share the cost of an optimal network (namely OP T S |con(S)| ) except one player, denoted by f (S), who is charged OP T S |con(S)| plus the extra cost of the current state ∆(S).

In the second protocol, all connected players who follow the optimal strategy profile T * S pay according to the Bird rule while the other connected players (who do not follow T * S ) pay what they should pay in T * S with the Bird rule plus an extra cost. We assume that this extra cost is fairly distributed, but actually the result holds for any extra cost.

Our protocols rely on a particular set of players: we define V (S) as the players of con(S) such that Si ̸ = S * i and con(S) = con(S * i , S-i). In other words, these players do not follow T * S and if they unilaterally change their strategy to follow it, then the set of connected players remains unchanged.

Lemma 1. The following properties hold for every state S:

(i) If ∃i ∈ con(S) such that Si ̸ = S * i then V (S) ̸ = ∅. (ii) If dis(S) ̸ = ∅, then ∃i ∈ dis(S) such that NG(i) ∩ (con(S) ∪ {0}) ̸ = ∅.
Proof. Let S be a state.

For (i). Take any player i ∈ con(S) such that Si ̸ = S * i . Removing the edge (i, Si) from E(CCS) provides two connected components CC0 (where the source is) and CCi (where i is). If S * i belongs to CC0 then i ∈ V (S) because con(S) = con(S * i , S-i). Otherwise S * i ∈ CCi and consider the path, in T * S , from i to the source. Denote by j the last node of CCi visited when walking from i to 0 on the path. It must be S * j ∈ CC0 and Sj ̸ = S * j (otherwise E(CCS) is not a tree). Thus j ∈ V (S).

For (ii). Assume dis(S) ̸ = ∅ and let j ∈ dis(S). Since G is connected there is a path from the source 0 to j. Let i ∈ dis(S) be the first encountered vertex of this path when we start from 0. Hence, an edge (i ′ , i) belongs to this path with i ′ ∈ (con(S) ∪ {0}).

An egalitarian protocol

Let f (S) = min V (S) be the node of V (S) with minimum index if V (S) ̸ = ∅ and f (S) = ∅ otherwise (using (i) of Lemma 1). In the protocol, f (S) is charged OP T S |con(S)| + ∆(S) while any other connected node pays OP T S |con(S)| .

Formally, we get: ci(S)

= OP T S |con(S)| for i ∈ con(S) \ {f (S)}, c f (S) (S) = OP T S |con(S)| + ∆(S) if f (S) ̸ = ∅ and ci(S) = +∞ for i ∈ dis(S).
One can observe that the total weight of E(CCS) is always covered by the connected players, i.e., the protocol is budget balanced. Consider the connection situations depicted in Figure 2. Note that on the left side, the agents are symmetric in the graph (two nodes i and j are symmetric in a graph if w(i, k) = w(j, k) for every other node k). As a consequence, there are two minimum cost spanning trees of total cost 20: {(1, 2), (0, 2)} and {(1, 2), (0, 1)}. Differently, in the connection situation on the right side, there is a unique mcst of cost 20: {(1, 2), (0, 1)}.

The strategic games associated with the protocol introduced in this section with respect to the mcst T * S = {(1, 2), (0, 1)} and the connection situations depicted in Figure 2 are shown in the following tables.

Looking at the left table, corresponding to the network depicted in Figure 2, left side, we observe that even if players 1 and 2 are symmetric, in state (0, 0) player 2 seems to be penalized (he pays more than its direct connection to the source). On the other hand, both Nash equilibria (2, 0) and (0, 1) are efficient.

Instead, in the right table, corresponding to the network in Figure 2, right side, we observe that agent 1 is better off when passing from state (2, 0) to state (0, 0), even if the weight of the link to edge (1, 2) is smaller than the weight of edge (0, 1). As expected, the protocol does not satisfy the IMON property (similarly, we may observe that neither the SDEP property holds: simply increase the cost of the edge (0, 1) from 20 to 22 in the network of Figure 2, right side, all the other costs remaining the same; we have that under the state (2, 0) the protocol would attribute 29 to player 1 and 11 to player 2).

Proposition 3. Every state corresponding to a mcst is a Nash equilibrium

Proof. Let OP T be the weight of any mcst. In a state S corresponding to a mcst, all players pay OP TS/(n -1) = OP T /(n-1) because ∆(S) = 0. Thus, no player can deviate and decrease his cost. Note that f (S) can be non empty if an optimal solution is not unique. Proposition 4. Any state S which does not correspond to a mcst is not a Nash equilibrium.

Proof. If ∆(S) = 0, then TS is a mcst on G[con(S)] and not on G. So, dis(S) ̸ = ∅; By (ii) of Lemma 1, there is a player i ∈ dis(S) which can play j ∈ con(S). Let S ′ = (S-i, j) be the state resulting of this modification. We have ci(S ′ ) < +∞ = ci(S).

If ∆(S) > 0, then the player f (S), who pays OP T S |con(S)| + ∆(S), can play S * i and pay OP T S |con(S)| .

As indicated in the previous sections, we consider the better response dynamics (BRD), a well known process which starts from any given state and, while it is possible, let one player take a better move. We say that BRD converges if it always ends.

Let Φ be a potential function which maps a state S to the vector

(|dis(S)|, |E(S * ) \ E(S)|, f (S), |NS(f (S))|)
where we recall that NS(f (S)) is the set if strategies corresponding to a better response for f (S).

A vector X ∈ N r is lexicographically smaller than another vector Y ∈ N r , denoted by X ≺ Y , if one of the following cases occurs:

• X1 < Y1 • Xi < Yi for some i ∈ {2, • • • , r} while Xj = Yj for all j < i.
Lemma 2. Let S and S ′ be two states which only differ on the strategy of one player i. If ci(S ′ ) < ci(S) then Φ(S ′ ) ≺ Φ(S).

Proof. Player i has taken a better move. Suppose i ∈ dis(S). We get that i / ∈ dis(S ′ ) and after i's deviation, the number of disconnected players can only decrease strictly, meaning that Φ(S ′ ) ≺ Φ(S). Now suppose that i ∈ con(S). It is clear that i ∈ con(S ′ ) since i takes a better move. It immediately follows that con(S) = con(S ′ ) and OP TS = OP T S ′ .

If ci(S) = OP T S

|con(S)| then there is no way for i to change his strategy and decrease his cost so we can assume that ci(S) = Theorem 1. BRD always converges after at most ∆(G)n 3 rounds where ∆(G) is the maximum degree of the graph G.

Proof. Using Lemma 2, each state S is immediately followed by another state S ′ such that Φ(S ′ ) ≺ Φ(S). Thus BRD can not run into a cycle. Since a finite number of states exists, there is at least one minimal state for ≺, meaning that BRD always converge. Now, since for any state S,

|dis(S)| ≤ n -1, |E(S * ) \ E(S)| ≤ n -1, f (S) ≤ n -1 and |NS(f (S))| ≤ ∆(G)
, and Φ(S) always decreases lexicographically when the player who deviates plays a better response, then BRD converges after at most ∆(G)(n -1) 3 rounds.

A Bird's like protocol

In this second protocol, the costs of players are given by:

• If i ∈ dis(S), then ci(S) = +∞, • If i ∈ con(S) \ V (S), then ci(S) = w(i, Si), • If i ∈ V (S), then ci(S) = w(i, S * i ) + ∆(S) | V (S)| = w(i, Si) + ∆(S)
| V (S)| where ∆(S) = w(TS)-OP T con(S) (actually here, we can take any cost function w(i, S * i )+gi(S) such that (i) gi(S) > 0 and (ii)

∑ i∈con(S) gi(S) = ∆(S).
Note that the protocol is clearly budget balanced.

Example 2. Consider again the connection situations depicted in Figure 2.

The strategic games associated with the protocol introduced in this section with respect to the mcst T * S = {(1, 2), (0, 1)} and the connection situations depicted in Figure 2 are shown in the following tables.

Looking at the left table, corresponding to the network depicted in Figure 2, left side, we observe that even if players 1 and 2 are symmetric, both Nash equilibria (2, 0) and (0, 1) are efficient and correspond to the allocation provided by the Bird rule under the network T * S , which strongly penalizes player 2 in the NE (2, 0) where the mcst {(1, 2), (0, 2)} is constructed.

Again, in the right table, corresponding to the network in Figure 2, right side, we observe that the protocol does not satisfy the IMON property, passing from state (2, 0) to state (0, 0). Proposition 5. Every state corresponding to a mcst is a Nash equilibrium Proof. Assume that it is not the case. Thus, there is an optimal state R (with w(TR) = OP T ) and another state S = (R-i, j) such that ci(S) < ci(R). Note that ∆(R) = 0 so ci(R) = w(i, Ri). ci(S) is finite so i is still connected and con(S) = V \ {0}. The spanning trees TR and TS differ only on one edge (w(i, Ri) in TR and w(i, Si) in TS) so by optimality of TR we get that w(i, Ri) ≤ w(i, Si). We have ci(R) = w(i, Ri) ≤ w(i, Si) ≤ ci(S), contradiction. Proposition 6. Any state S which does not correspond to a mcst is not a Nash equilibrium.

Proof. Assume con(S) = V since otherwise by (ii) of Lemma 1 S is clearly not a Nash equilibrium.

Hence, V (S) ̸ = ∅ by (i) of Lemma 1 (w(TS) ̸ = OP T and con(S) = V \ {0}). Then, there exists i ∈ V (S) such that (TS ∪ {(i, S * i )}) \ {(i, Si)} is a spanning tree. Consider the state S ′ = (S-i, S * i ). Now, we have i / ∈ V (S ′ ); so ci(S ′ ) = w(i, S * i ). On the other hand, i ∈ V (S) implies ci(S) = w(i, S * i ) + ∆(S) | V (S)| > w(i, S * i ) because w(TS) > OP T . Hence, ci(S ′ ) < ci(S).

In any case, S is not a NE and the result is proved.

Let Φ(S) = (|dis(S)|, | V (S)|, ∑ i∈ V (S) |ES(i)|
) be a potential function, where ES(i) = {j ∈ {0, . . . , n -1} : w(i, j) < w(i, Si)}. Lemma 3. Let S and S ′ be two states which only differ on the strategy of a player i. If ci(S ′ ) < ci(S) then Φ(S ′ ) ≺ Φ(S).

Proof. Player i has taken a better move. Suppose i ∈ dis(S). We get that i / ∈ dis(S ′ ) and after i's deviation, the number of disconnected players can only decrease strictly, meaning that Φ(S ′ ) ≺ Φ(S). Now suppose that i ∈ con(S). Obviously, con(S) = con(S ′ ). We prove that i ∈ V (S). Otherwise, i ∈ con(S) \ V (S) and then, ci(S) = w(i, Si) = w(i, S * i ). Now, if i changes its strategy, then i ∈ V (S ′ ), and ci(S ′ ) = w(i, S * i ) + ∆(S ′ ) | V (S ′ )| ≥ w(i, S * i ) = ci(S), contradiction.

Hence, i ∈ V (S) and then, ci(S) = w(i, S * i ) + ∆(S) | V (S)| . Two possibilities, either i ∈ con(S ′ ) \ V (S ′ ) or i ∈ V (S ′ ).

• If i ∈ con(S ′ ) \ V (S ′ ) = con(S) \ V (S ′ ), then | V (S ′ )| = | V (S)| -1. Hence, Φ(S ′ ) ≺ Φ(S).

• If i ∈ V (S ′ ), then ci(S ′ ) = w(i, S * i ) + ∆(S ′ ) | V (S ′ )| . Observe that V (S ′ ) = V (S). Since ci(S ′ ) < ci(S) by hypothesis, we deduce that ∆(S ′ ) < ∆(S). Thus, w(i, S ′ i ) < w(i, Si) which means |E S ′ (i)| < |ES(i)|. On the other hand, ∀j ∈ V (S) \ {i}, E S ′ (j) = ES(j).

In conclusion, ∑ j∈ V (S ′ ) |E S ′ (j)| < ∑ j∈ V (S) |ES(j)| and Φ(S ′ ) ≺ Φ(S).

In any case, Φ(S ′ ) ≺ Φ(S).

Theorem 2. BRD always converges after at most mn 2 rounds, where m is the number of edges of G.

Proof. Using Lemma 3, each state S is immediately followed by another state S ′ such that Φ(S ′ ) ≺ Φ(S). Thus BRD can not run into a cycle. Since a finite number of states exists, there is at least one minimal state for ≺, meaning that BRD always converge.

CONCLUSIONS

In this paper we have studied cost allocation protocols for connection situations in a strategic setting. We have presented a model that can be easily adapted to the model of network formation on communication graphs, and we have analyzed properties for protocols in relation the the convergence of the best reply dynamics to efficient Nash equilibria. These properties have driven our analysis to the definition of two optimal budget balanced protocols. As a consequence, the question concerning the existence of optimal protocols has been positively answered in this paper.

The method used to define our protocols might lead to the definition of many other optimal protocols, depending on the rule according to which the cost of a mcst is allocated among the players. As illustrated by numerical examples, the inherent limitations of the optimal protocols proposed in this paper is that symmetric players may be treated differently, depending on the choice of an a priori selected mcst. The question about the existence of optimal protocols which treat symmetric players in a more equitable manner remains open.

Figure 1 :

 1 Figure 1: Illustration of Proposition 1.

Figure 2 :

 2 Figure 2: Two connection situations with two agents, one with symmetric agents and two mcsts (left side) and one asymmetric agents (right side). 1\2 0 1 0 10, 30 10, 10 2 10, 10 ∞, ∞

  OP T S |con(S)| + ∆(S), implying that i = f (S). If i = f (S) deviates and plays S ′ i = S * i instead of Si then |E(S * ) \ E(S)| decreases by one unit while |dis(S)| remains unchanged; thus Φ(S ′ ) ≺ Φ(S). Now suppose that i = f (S) deviates and plays S ′ i ̸ = S * i . Then |E(S * ) \ E(S)| and |dis(S)| remain unchanged. In addition i belongs to V (S ′ ), meaning that f (S) ≥ f (S ′ ). Either f (S ′ ) < f (S), implying that Φ(S ′ ) ≺ Φ(S). Otherwise f (S ′ ) = f (S). Since i has taken a better move, ci(S) = OP T S |con(S)| + ∆(S) > OP T S ′ |con(S ′ )| + ∆(S ′ ) = ci(S ′ ) from which we deduce that ∆(S) > ∆(S ′ ) because OP TS = OP T S ′ and con(S) = con(S ′ ). Since the strategies of other players remains unchanged, it follows that N S ′ (f (S ′ )) ⊂ NS(f (S)), implying |N S ′ (f (S ′ ))| < |NS(f (S))|; thus Φ(S ′ ) ≺ Φ(S).

Corollary 1 .

 1 BRD converges after at most n 3 rounds if the players play their best response. Proof. Consider the function Ψ which maps any state S to the vector (|dis(S)|, |E(S * ) \ E(S)|, f (S)). First, observe that either a disconnected vertex chooses to be connected, or the connected vertex f (S) chooses to follow a strategy leading to a new state S ′ with f (S ′ ) ̸ = f (S) because f (S) plays a best response. Since |dis(S)|, |E(S * ) \ E(S)| and f (S) range from 0 to n -1, there are at most n 3 values for Ψ(S).

  Now, since for any state S, |dis(S)| ≤n -1, | V (S)| ≤ n -1 -|dis(S)| and ∑ j∈ V (S) |ES(j)| ≤ mS ≤ m, then BRD converges after at most m n 22 rounds.

* This work is supported by French National Agency (ANR), project COCA ANR-09-JCJC-0066-01.


Laurent Gourvès

Jérôme Monnot

Lydia Tlilane

A Matroid Approach to the Worst Case Allocation of Indivisible Goods *

. Interestingly, V n (α) is tight for some values of α, i.e. it is the best lower bound on the valuation of the least happy agent. However, it is not true for all values of α. We propose a family of functions W n such that W n (x) ≥ V n (x) for all x, and W n (x) > V n (x) for values of x where V n (x) is not tight. The new functions W n apply on a problem which generalizes the allocation of indivisible goods. It is to find a solution (base) in a matroid which is common to n agents. Our results are constructive, they are achieved by analyzing an extension of the algorithm of Markakis and Psomas.

1 Introduction [START_REF] Demko | [END_REF] 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 t n ∈ [0, 1] such that, in any case, there exists an allocation where each of the n agents has utility at least t n for his share. To be complete, t n should come with a family of instances without any feasible allocation where everyone values his share t n + (or more) for some positive .

In the context of sharing divisible goods, it is long known that t n = 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 i 1 , and utility 0 for any other item. The agents who do not receive i 1 have a global utility of 0, meaning that t n 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 t n = 1/n. Then, what is t n between these two extremal cases?

In fact, the maximum value for a single element appears to significantly influence t n , as in the pioneering work of [Hill, 1987] who defined a family of nonincreasing functions V n : [0, 1] → [0, n -1 ] for any integer n ≥ 2 (see Definition 1 and Figure 1). Following [Hill, 1987], [START_REF] Demko | [END_REF] 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 V n (α). In addition, they showed with some instances that V n 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, [START_REF] Markakis | [END_REF] have recently strengthened the results of Demko and Hill. Indeed, they show the existence of an allocation guaranteeing V n (α i ) for every agent i. Since V n is nonincreasing, V n (α i ) ≥ V n (α) holds and the vector

(V n (α i )) i∈[n] weakly Pareto dominates (V n (α)) i∈[n]
. The other contribution of Markakis and Psomas relies on the fact that, unlike the results in [Hill, 1987;[START_REF] Demko | [END_REF], the allocations are obtained with a deterministic algorithm which 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 α = max i∈[n] α i .

Interestingly, we show that V n is still valid in this generalized context and we can even improve it. We propose a family of functions W n : [0, 1] → [0, n -1 ] defined for any positive integer n (see Definition 2). We have W n (x) ≥ V n (x) for all x ∈ [0, 1], and W n (x) > V n (x) for values of x where V n (x) is not tight (see Figure 1 for illustration). Like V n , W n is piecewise linear on [0, 1] but unlike V n , W n 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 [START_REF] Markakis | [END_REF] for the generalized problem on matroids. The algorithm returns a solution (base) where every agent i has utility at least W n (α 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 W n improve on V n , 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 W n (α i ). Due to lack of space, some parts of proofs are omitted. Further results and future directions are given in Section 6.

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 [START_REF] Chevaleyre | [END_REF]. 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 [START_REF] Lipton | [END_REF] 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 [START_REF] Demko | [END_REF] on the basis of [Hill, 1987]. Recently, [START_REF] Markakis | [END_REF] 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.

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 F 2 ⊆ F 1 and F 1 ∈ F then F 2 ∈ F, (iii) for every F 1 , F 2 ∈ F where |F 1 | < |F 2 |, ∃ e ∈ F 2 \F 1 such that F 1 ∪ {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 by M/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 P 1 , . . . , P k which form a ground set P = ∪ k i=1 P i and k nonnegative integers b i (i = 1..k), the sets F ⊆ P satisfying |F ∩ P i | ≤ b i 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

P i = {i 1 , i 2 , . . . , i n } and let b i = 1 for i ∈ [m]. Taking i k 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 F 1 , F 2 ∈ F where |F 1 | < |F 2 |, suppose that F 2 = {e 1 , . . . , e |F2| } with w(e 1 ) ≥ • • • ≥ w(e |F2| ). In the con- tracted matroid M/F 1 , ∃E ⊆ F 2 \F 1 such that E is inde- pendent in M/F 1 (i.e. F 1 ∪ E ∈ F) where |E| = |F 2 | -|F 1 | and w(E) ≥ w {e |F1|+1 , . . . , e |F2| } .
Proof. By induction on k = |F 2 | -|F 1 |, we prove that there is an independent set E k satisfying the lemma.

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

We assume that Lemma 1 is true for k ≥ 1 and we show it for k

+ 1. Let F 1 , F 2 ∈ F such that |F 2 | -|F 1 | = k + 1, F 2 = {e 1 , . . . , e |F1|+k+1 } and w(e 1 ) ≥ ... ≥ w(e |F1|+k+1 ). Let F 2 = F 2 \{e |F1|+k+1 }. Using the inductive hypothesis, ∃E k ⊆ F 2 \F 1 in the contracted matroid M/F 1 such that F 1 ∪ E k ∈ F, |E k | = |F 2 | -|F 1 | = k and w(E k ) ≥ w {e |F1|+1 , . . . , e |F1|+k } . Consider the sets F 1 ∪ E k and F 2 where |F 1 ∪ E k | = |F 1 | + k and |F 2 | = |F 1 | + k + 1. From property (iii) of ma- troids, ∃e ∈ F 2 \(F 1 ∪ E k ) such that F 1 ∪ E k ∪ {e} ∈ F. In other words, E k ∪ {e} is an independent set of M/F 1 . Since w(e 1 ) ≥ • • • ≥ w(e |F1|+k+1 ) then, w(e) ≥ w(e |F1|+k+1 ). Let E k+1 = E k ∪ {e}. Hence, w(E k+1 ) ≥ w e |F1|+1 , . . . , e |F2| as claimed. 2 Algorithm 1 GREEDY Require: M = (X, F), w : X → IR + 1: Sort X = {e 1 , • • • , e |X| } such that w(e i ) ≥ w(e i+1 ), i = 1..|X| -1 2: F ← ∅ 3: for i = 1 to |X| do 4: if F ∪ {e i } ∈ F then 5: F ← F ∪ {e i } 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.

The model

We are given a matroid M = F), a set of agents N = {1, ..., n} and u i (e) ∈ IR + for every pair (i, e) ∈ N × X. Actually, u i (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 u i (X ) and defined as x∈X u i (x). As a convention, u i (∅) is equal to 0. Agent i prefers the solutions (bases) that maximize u i . 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 u i (B * i ) = 1. This normalization allows to capture the agents' relative utilities instead of their absolute utilities. If u i (B * i ) = 1 for some agent i, it suffices to replace u i (e) by u i (e)/u i (B * i ) for all e ∈ X. This is trivially done in polynomial time.

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

Following [START_REF] Demko | [END_REF], we are interested in determining a value t n such that, in any case, there exists a solution B ∈ F satisfying u i (B) ≥ t n , ∀i ∈ N . As done in [START_REF] Markakis | [END_REF], a strengthening of this result would be a vector (t i,n ) i∈N such that, in any case, there exists a solution B of the matroid with u i (B) ≥ t i,n ≥ t n , ∀i ∈ N .

Since our model extends the one in [START_REF] Demko | [END_REF][START_REF] Markakis | [END_REF], parameters α and α i play an important role in the determination of t n and (t i,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.

Technical results

Let us begin by defining the function V n of Hill. Definition 1 [Hill, 1987;[START_REF] Markakis | [END_REF] Given any integer n ≥ 2, let V n : [0, 1] → [0, n -1 ] be the unique nonincreasing function satisfying V n (x) = 1/n for x = 0, whereas for x > 0: [ [START_REF] Markakis | [END_REF] produce an allocation such that each agent i receives at least V n (α i ) which is tight in I(n, p). We define a new function W n . Definition 2 Given any integer n ≥ 1, let W n : [0, 1] → [0, n -1 ] be the function satisfying W 1 (x) = 1, ∀x ∈ [0, 1], whereas for any integer n ≥ 2, W n (x) = 1/n for x = 0 and for x > 0,

V n (x) = 1 -p(n -1)x, x ∈ I(n, p) 1 -(p+1)(n-1) (p+1)n-1 , x ∈ N I(n,
W n (x) =            0, x ∈ I (n,0) 1 -p(n -1)x, x ∈ I 1 (n,p) p(1-px) (p+1)(n-1)-1 , x ∈ I 2 (n,p) p(x+p-1) np 2 -p-n+2 , x ∈ I 3 (n,p)
where I (n,0) = 1 n-1 , 1 and for any integer p ≥ 1,

• I 1 (n,p) = p+1 p((p+1)n-1) , 1 pn-1 • I 2 (n,p) = p 2 np 3 -p 2 +p+n-2 , p+1 p((p+1)n-1) • I 3 (n,p) = 1 (p+1)n-1 , p 2 np 3 -p 2 +p+n-2 • I (n,p) = I 1 (n,p) ∪ I 2 (n,p) ∪ I 3 (n,p) =
Note that I (n,p) = I(n, p). In the following, we use only the intervals defined in Definition 2. We see that W n (x) > V n (x) for intervals I 2 (n,p) and I 3 (n,p) , and V n (x) = W n (x) elsewhere.

x W n (x)

V n (x) 1 1 2 1 3 1 2 1 3 1 5 2 5 1 4 1 5 2 3 0 n = 2 n = 3 Figure 1: W n (•) and V n (•) for n = 2 and n = 3.
The following properties can easily be proved: Property 1 Given any integers n ≥ 2 and p ≥ 1,

1. V n (x) ≤ W n (x) ≤ 1 n , ∀x ∈ [0, 1]. 2. If x ≤ p+1 p((p+1)n-1) then W n (x) ≥ p (p+1)n-1 . 3. If x ∈ I (n,p) then (p -1)x < W n (x) ≤ px.
Now, we present Algorithm 2 which constructs a base (solution) by executing THRESHOLD(N , M, (u i ) i∈N , ∅).

Algorithm 2 THRESHOLD Require: N , M = (X, F), (u i ) i∈N , B

1: for all i ∈ N do 2:

B * i ←GREEDY(M, u i ) 3:
for all e ∈ X do 4:

ũi (e) ← u i (e)/u i (B * i )

5:

end for 6:

α i ← max {e}∈F ũi (e)
7:

S i ← ∅ 8:
add in a greedy manner elements of B * i to S i by nonincreasing order of ũi until ũi (

S i ) ≥ W |N | (α i ) 9: end for 10: pick i ∈ N such that |S i | ≤ |S k |, ∀k ∈ N 11: B i ← S i 12: B ← B ∪ B i 13: if |N | = 1 then 14: return B 15: else 16: let M/B i = (X\B i , F) be the contraction of M to B i where F ∈ F iff F ∪ B i ∈ F 17: THRESHOLD(N \{i}, M/B i , (ũ k ) k∈N \{i} , B) 18: end if
THRESHOLD is an adaptation of the algorithm of [START_REF] Markakis | [END_REF] 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 = B 1 ∪• • •∪B i and the contracted matroid is M/(B 1 ∪• • •∪B i ) at the end of the i-th call. At the end of the n-th call of THRESHOLD, B = B 1 ∪ • • • ∪ B n
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/(B 1 ∪ • • • ∪ B n-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.

v 1 v 2 v 5 v 3 v 4 (u 1 (e), u 2 (e)), ∀e ∈ E (3, 1) (3, 3) (0, 2) (1, 0) (1, 2) (2, 3) Figure 2: The graph G.
During the first call of THRESHOLD, we have

B * 1 = {(v 1 , v 2 ), (v 2 , v 3 ), (v 4 , v 5 ), (v 5 , v 1 )} and B * 2 = {(v 2 , v 3 ), (v 1 , v 3 ), (v 3 , v 4 ), (v 5 , v 1 )} with u 1 (B * 1 ) = 8 and u 2 (B *
2 ) = 10 where B * i corresponds to a maximum spanning tree in (G, u i ) (for instance, by applying GREEDY or Kruskal's algorithm). The algorithm normalizes utilities u i (e) to get ũi (e) = u i (e)/u i (B * i ), ∀i ∈ {1, 2}, ∀e ∈ E. Then, α 1 = 3/8 ∈ I 3

(2,1) and α 2 = 3/10 ∈ I 1 (2,2) . So, W 2 (α 1 ) = α 1 = 3/8 and W 2 (α 2 ) = 1 -2α 2 = 4/10. Now, each agent i ∈ {1, 2} builds a forest S i by adding the heaviest edges of B * i until ũi (S i ) ≥ W 2 (α i ). We find 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 ũ2 (e) = u 2 (e)/u 2 (B * 2 ). Let B * 2 be an optimal base of the contracted matroid (G/B 1 , ũ2 ). During the second call of THRESHOLD, the algorithm finds

S 1 = {(v 1 , v 2 )} and S 2 = {(v 2 , v 3 ), (v 1 , v 3 )}. Since |S 1 | < |S 2 |, we have i = 1, B 1 = S 1 and B = B 1 . Now, let G/B 1 be the new graph obtained by contracting edge (v 1 , v 2 ) of B 1 into vertex v 1,2 as it is done in Figure 3.
B * 2 = {(v 1,2 , v 3 ), (v 3 , v 4 ), (v 5 , v 1,2 )} with ũ2 ( B *
2 ) = 7/10. Now, the utilities of agent 2 are normalized ũ2 (e)=ũ 2 (e)/ũ 2 ( 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 ũ2

( S2 )≥W 1 (α 2 )=1 is reached. So, B 2 = B * 2 and finally THRESHOLD returns B = B 1 ∪ B 2 = {(v 1 , v 2 ), (v 2 , v 3 ), (v 3 , v 4 ), (v 5 , v 1 )} where u 1 (B) = 7 ≥ W 2 (α 1 )u 1 (B * 1 ) and u 2 (B) = 8 ≥ W 2 (α 2 )u 2 (B * 2 ). Theorem 1 THRESHOLD returns a base B which satisfies u i (B) ≥ W |N | (α i )u i (B * i ) for all i ∈ N . Proof. Let n = |N | and recall that the base returned by THRESHOLD is B = B 1 ∪ • • • ∪ B n .
Actually, we will prove, by induction on n, a stronger result:

u i (B i ) ≥ W n (α i )u i (B * i ), ∀i ∈ N . Because the utili- ties are nonnegative, we conclude u i (B) ≥ u i (B i ).
For n = 1, line 8 of THRESHOLD is equivalent to applying GREEDY(M, u 1 ) to get the base

B = B 1 = B * 1 which satis- fies: ũ1 (B 1 )≥ W 1 (α 1 ) =1 because W 1 (x) = 1, ∀x ∈ [0, 1]. Thus, u 1 (B 1 ) = W 1 (α 1 )u 1 (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 , W n (α 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 W n (α 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,

B 1 = S 1 and |B 1 | ≤ |S i |, ∀i ∈ N (1)
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 THRESH-OLD (like it is done in Example 1). Hence, Ñ = N \ {1}, ũi (e) = u i (e)/u i (B * i ), M = M/B 1 = (X\B 1 , F) and B *

i is an optimal base of ( M, ũi ). Moreover for i ∈ Ñ , ũi (e) = ũi (e)/ũ i ( B * i ) for the elements e ∈ X\B 1 of M and αi = max {e}∈ F ũi (e).

The inductive hypothesis affirms that

ũi (B i ) ≥ W n-1 (α i )ũ i ( B * i ), ∀i ∈ Ñ (2)
and we want to show that

u i (B i )≥W n (α i )u i (B * i ), ∀i ∈ N or equivalently ũi (B i ) ≥ W n (α i ), ∀i ∈ N .
By construction of THRESHOLD, during the first call we have (lines 3-8):

ũi (S i ) ≥ W n (α i ), ∀i ∈ N (3)
Since B 1 = S 1 , then by (3), we get the expected result for agent 1. In addition, since the sets S i = e 1 i , . . . , e |Si| i are minimal for inclusion, we deduce:

ũi (S i \{e |Si| i }) < W n (α i ), ∀i ∈ N (4) Let k ∈ Ñ . We decompose B * k = B * 1 k ∪B * 2 k such that B *
| = |B * 1 |. Since S 1 = B 1 and S 1 ⊆ B * 1 , we have S 1 = B 1 = B * 1 so, ũ1 (S 1 ) = ũ1 (B * 1 ) = 1. By (4), ũ1 (S 1 \{e |S1| 1 }) = ũ1 (S 1 ) -ũ1 (e |S1| 1 ) = 1 - ũ1 (e |S1| 1 ) < W n (α 1 ) ≤ 1/2 so, ũ1 (e |S1| 1 ) > 1/2. Since |S 1 | = r(M) ≥ 2
and S 1 is sorted by nonincreasing order of ũ1 , we get ũ1 (S 1 ) ≥ 2ũ 1 (e |S1| 1 ) > 1 which is a contradiction. Hence, we can apply Lemma 1 for M, w = ũk , F 1 = B 1 and F 2 = B * k . We deduce that there exists

E ⊆ B * k \B 1 such that B 1 ∪ E ∈ F where |E| = |B * k | -|B 1 | = |B * 2 k | and ũk (E) ≥ ũk (B * 2 k ). E is an independent set of M = M/B 1 whereas B * k is a base of M maximum for ũk . So, ũk ( B * k ) ≥ ũk (E) ≥ ũk (B * 2 k ).
Due to the normalization, we get ũk ( B * k ) ≥ 1 -ũk (B * 1 k ). From ( 5) and the previous inequality, it holds that:

ũk ( B * k ) ≥ 1 -ũk (S k ) (6)
and by ( 2) and ( 6),

ũk (B k ) ≥ W n-1 (α k ) (1 -ũk (S k )) (7)
Now, from line 6 of THRESHOLD, we know that:

αk = max
ũk (B k ) ≥ W n-1 (α k ) (1 -p k α k ) (9)
and by ( 8),

αk ≤ α k 1 -p k α k (10) < 1 p k (n -1) -1 for α k ∈ I (n,p k ) So, either αk ∈ I 1 (n-1,p k ) or αk ≤ p k +1 p k ((p k +1)(n-1)-1) . (a) If αk ∈ I 1 (n-1,p k ) then W n-1 (α k ) = 1 -p k (n -2)α k . From (9), we deduce that ũk (B k ) ≥ (1 -p k (n -2)α k ) (1 - p k α k ).
Finally, using (10), we get that ũk (

B k ) ≥ 1 -p k (n-2)α k 1-p k α k (1-p k α k ) = 1-p k (n-1)α k ≥ W n (α k ), which can easily be checked because α k ∈ I (n,p k ) . (b) Otherwise, αk ≤ p k +1 p k ((p k +1)(n-1)-1) . Using 2. of Prop- erty 1 if n ≥ 3 or W 1 (x) = 1 if n = 2, we obtain W n-1 (α k ) ≥ p k (p k +1)(n-1)-1 . By (9), ũk (B k ) ≥ p k (p k +1)(n-1)-1 (1 -p k α k ) ≥ W n (α k ), which can easily be checked because α k ∈ I (n,p k ) . Case 2: |S k | ≥ p k + 1. Then, we prove that p k ≥ 2. By contradiction, assume p k = 1, then |S k | ≥ 2. Since, n ≥ 2, 3. of Property 1 with α k ∈ I (n,p k ) gives W n (α k ) ≤ p k α k = α k because p k = 1. Thus, agent k reaches the threshold ũk (S k ) = α k ≥ W n (α k ) just by selecting the heaviest ele- ment of B * k which is a contradiction with |S k | ≥ 2. Since |S k | ≥ p k + 1, (4) implies that W n (α k ) > ũk (S k \{e |S k | k }) ≥ ũk (e 1 k ) + (p k -1)ũ k (e p k k ) = α k + (p k -1)ũ k (e p k k ) because |S k | ≥ p k + 1
, the elements of S k are sorted by nonincreasing order of ũk and ũk (e 1 k ) = α k . From this inequality, we deduce ũk (e

|S k | k ) ≤ ũk (e p k k ) < Wn(α k )-α k p k -1 because p k ≥ 2.
Finally, by adding the last inequality of ũk (e 4), we get:

|S k | k ) to (
ũk (S k ) < p k W n (α k ) -α k p k -1 (11)
On the one hand, by ( 7) and ( 11) we have:

ũk (B k ) ≥ W n-1 (α k ) 1 - p k W n (α k ) -α k p k -1 (12)
On the other hand, by ( 8) and ( 11) we get:

αk ≤ α k (p k -1) p k -1 + α k -p k W n (α k ) (13)
Let us analyze the different cases according to the values of α k in I

(n,p k ) = I 1 (n,p k ) ∪ I 2 (n,p k ) ∪ I 3 (n,p k ) . (a): α k ∈ I 1 (n,p k ) .
Then by construction, W n (α k ) = 1p k (n -1)α k . Using (12), we obtain:

ũk (B k ) ≥ W n-1 (α k ) ((n -1)p 2 k + 1)α k -1 p k -1 (14)
On the other hand, by (13) we get: Using 2. of Property 1 if n ≥ 3 with this last inequality of αk or W 1 (x) = 1 if n = 2, we deduce that W n-1 (α k ) ≥ p k (p k +1)(n-1)-1 . Inequality (15) implies ũk (B k ) ≥ p k (1-p k α k ) (p k +1)(n-1)-1 = W n (α k ) which can easily be checked because α k ∈ I 2 (n,p k ) . (c): α k ∈ I 3 (n,p k ) . Then by construction, W n (α k ) =

αk ≤ α k (p k -1) ((n -1)p 2 k + 1)α k -1 ≤ p k + 1 p k ((p k + 1)(n -1) -1) for α k ∈ I 1 (n,p k ) Using 2. of Property 1 if n ≥ 3 with this last in- equality of αk or W 1 (x) = 1 if n = 2, we deduce: W n-1 (α k ) ≥ p k (p k +1)(n-1)-1 . Inequality (14) becomes ũk (B k ) ≥ p k (p k +1)(n-1)-1 ((n-1)p 2 k +1)α k -1 p k -1 ≥ 1 -p k (n - 1)α k = W n (α k ) which can easily be checked because α k ∈ I 1 (n,
p k (α k +p k -1) np 2
k -p k -n+2 . On the one hand, by (12),

ũk (B k ) ≥W n-1 (α k ) ((n -1)p k + n -2) np 2 k -p k -n + 2 × (α k + p k -1) (16)
On the other hand, by ( 13),

αk ≤ (np 2 k -p k -n + 2)α k ((n -1)p k + n -2)(α k + p k -1) ≤ p k + 1 p k ((p k + 1)(n -1) -1) for α k ∈ I 3 (n,p k )
Using 2. of Property 1 if n ≥ 3 with this last inequality of αk or W 1 (x) = 1 if n = 2, we deduce that W n-1 (α k ) ≥ p k (p k +1)(n-1)-1 . Inequality (16) implies ũk (B k ) ≥ p k (α k +p k -1) np 2 k -p k -n+2 = W n (α k ) which can easily be checked because α k ∈ I 3 (n,p k ) . The induction is proved and the result follows. 2

Discussion

Recall that THRESHOLD provides a solution which is a base B of a matroid with a relative utility ũi (B) ≥ W n (α 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 V n , W n is not monotonic, so it is not obvious that we may guarantee a relative utility of W n (α) 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{W 2 (α i ); W 2 (α)} for each agent i ∈ N = {1, 2}. Moreover, this latter bound can be shown tight when α ∈ I (2,1) ∪ ∪ p≥2 I 1 (2,p) ∪ I 2 (2,p) . An interesting challenge is to know if a bound of max{W n (α i ); W n (α)} 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.

Figure 3 :

 3 Figure 3: The contracted graph G/B 1 .

  p k ∈ IN * such that α k ∈ I (n,p k ) (see Definition 2). We first show that |S k | ≥ p k . By contradiction, suppose that |S k | ≤ p k -1. Then, by the definition of α k , ũk (S k ) ≤ (p k -1)α k . Using 3. of Property 1, we get (p k -1)α k < W n (α k ) which leads to a contradiction with (3). Now, we distinguish two cases: |S k | = p k and |S k | ≥ p k + 1. Case 1: |S k | = p k . Line 6 of THRESHOLD implies that ũk (S k ) ≤ p k α k . Inequality (7) becomes

  p k ) . (b): α k ∈ I 2 (n,p k ) . Then by construction, W n (α k ) = p k (1-p k α)(p k +1)(n-1)-1 . On the one hand, by (12),ũk (B k ) ≥ (p 3 k + (n -1)p k + n -2)α k (p k -1)((p k + 1)(n -1) -1) + (n -2)p 2 k -p k -n + 2 (p k -1)((p k + 1)(n -1) -1) × W n-1 (α k )(15)On the other hand, by (13),αk ≤ (p 3 k + (n -1)p k + n -2)α k (p k -1)((p k + 1)(n -1) -1) + (n -2)p 2 k -p k -n + 2 (p k -1)((p k + 1)(n -1) -1) -1 ≤ p k + 1 p k ((p k + 1)(n -1) -1)for α k ∈ I 2 (n,p k )

  Since for n ≥ 2, W n (x) ≤ 1/n ≤ 1/2 (see 1. of Property 1) and r(M) ≥ n ≥ 2, we must have |B 1 | < |B * 1 | = |B * k | (allthe bases have the same size r(M)). We can prove it by contradiction: assume |B 1

			1
	k k . It is possible contains the |B 1 | first largest elements of B * because of (1) and recalling that S k ⊆ B * k . Hence, B * 1 k ⊆ S k
	and	ũk (B * 1 k ) ≤ ũk (S k )	(5)

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence

(p+1)n-1 , 1 pn-1

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


Nicolas Boria

Jérôme Monnot

Vangelis Th Paschos
email: paschos@lamsade.dauphine.fr

Reoptimization of the max weighted P k -free subgraph problem under vertex insertion *

The reoptimization issue studied in this paper can be described as follows: given an instance I of some problem Π, an optimal solution OPT for Π in I and an instance I ′ resulting from a local perturbation of I that consists of insertions or removals of a small number of data, we wish to use OPT in order to solve Π in I ′ , either optimally or by guaranteeing an approximation ratio better than that guaranteed by an ex nihilo computation and with running time better than that needed for such a computation. In this setting we study the weighted version of max weighted P k -free subgraph. We then show, how the technique we use allows us to handle also bin packing.

Introduction

Hereditary problems in graphs, also known as maximal subgraph problems, include a wide range of classical combinatorial optimization problems, such as max weighted independent set or max weighted H-free subgraph. Most of these problems are known to be NP-hard, and even inapproximable within any constant approximation ratio unless P = NP [START_REF] Lund | The approximation of maximum subgraph problems[END_REF][START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF].

In what follows, we study approximation of such a problem, namely the maximum weight P k -free subgraph, denoted by max weighted P k -free subgraph, in the reoptimization setting, which can be described as follows: considering an instance I of a given problem Π with a known optimum OPT, and an instance I ′ which results from a local perturbation of I, can the information provided by OPT be used to solve I ′ in a more efficient way (i.e., with a lower complexity and/or with a better approximation ratio) than if this information wasn't available?

The reoptimization setting was introduced in [START_REF] Archetti | Reoptimizing the traveling salesman problem[END_REF] for metric tsp. Since then, many other optimization problems were discussed in this setting, including Steiner tree [START_REF] Bilò | Reoptimization of steiner trees[END_REF][START_REF] Böckenhauer | Reoptimization of steiner trees: Changing the terminal set[END_REF][START_REF] Böckenhauer | On the hardness of reoptimization[END_REF][START_REF] Escoffier | Simple and fast reoptimizations for the steiner tree problem[END_REF], minimum spanning tree [START_REF] Boria | Fast reoptimization for the minimum spanning tree problem[END_REF], as well as various versions of tsp [START_REF] Ausiello | Reoptimization of minimum and maximum traveling salesman's tours[END_REF][START_REF] Böckenhauer | On the approximability of tsp on local modifications of optimally solved instances[END_REF][START_REF] Böckenhauer | Reoptimization of the metric deadline TSP[END_REF]. In all cases, the goal is to propose reoptimization algorithm that outperform their deterministic counterparts in terms of complexity and/or approximation ratio. In [START_REF] Bilò | Reoptimization of weighted graph and covering problems[END_REF], the max weighted independent set problem, as well as min weighted vertex cover and min weighted set cover problems, are discussed in a similar setting up to the fact that perturbations there concerned the edge-set of the initial graph. The authors of [START_REF] Bilò | Reoptimization of weighted graph and covering problems[END_REF] manage to provide optimal approximation results (i.e., upper and lower bounds matching ones the others) under the basic assumption that the initial solution is not necessarily optimal but ρ-approximate. Finally, let us note that in [START_REF] Bilò | Reoptimization of the shortest common superstring problem[END_REF] reoptimization variants of the shortest common superstring problem are considered, where the local modifications consist of adding or removing a single string.

When one deals with hereditary problems, and I ′ results from a perturbation of the vertex set (insertion or deletion), solutions of I remain feasible in I ′ . This property is very interesting when reoptimizing hereditary problems, and makes most of them APX in the reoptimization setting. For exemple, a very simple algorithm provides a (1/2)-approximation for a whole class of hereditary problems, including max weighted independent set when a single vertex is inserted [START_REF] Ausiello | Complexity and approximation in reoptimization[END_REF]. Let us note that the unweighted versions of all these problems in this setting admit polynomial time approximation schemata. In what follows, we improve on this result by presenting algorithms designed for two specific hereditary problems, and also provide inapproximability bounds.

The paper is organized as follows: general properties regarding reoptimization and the max weighted P k -free subgraph are presented in what follows in this section, while in Section 2 we present approximation and inapproximability results under vertex insertion for max weighted P k -free subgraph. Our results are optimal (in the sense given two paragraphs above). To the best of our knowledge no such results exist in the reoptimization literature for the vertex insertion setting. In Section 3, the bin packing problem is handled.

This paper is part of a larger work [START_REF] Boria | Reoptimization of maximum weight induced hereditary subgraph problems[END_REF] devoted to the study of five maximum weight induced hereditary subgraph problems, namely, max weighted independent set, max weighted k-colorable subgraph, max weighted P k -free subgraph, max weighted split subgraph and max planar subgraph. For reasons of length limits some of the results are given without detailed proofs, the interested reader is referred to [START_REF] Boria | Reoptimization of maximum weight induced hereditary subgraph problems[END_REF] where all proofs can be found.

Before presenting properties and results regarding reoptimization problems, we will first give formal definitions of what are reoptimization problems, reoptimization instances, and approximate reoptimization algorithms: Definition 1. An optimization problem Π is given by a quadruple (I Π , Sol Π , m Π , goal(Π)) where: I Π is the set of instances of Π; given I ∈ I Π , Sol Π (I) is the set of feasible solutions of I; given I ∈ I Π , and S ∈ Sol Π (I), m Π (I, S) denotes the value of the solution S of the instance I; goal(Π) ∈ {min, max}.

A reoptimization problem RΠ is given by a pair (Π, R RΠ ) where: Π is an optimization problem as defined in Definition 1; R RΠ is a rule of modification on instances of Π, such as addition, deletion or alteration of a given amount of data; given I ∈ I Π and R RΠ , modif RΠ (I, R RΠ ) denotes the set of instances resulting from applying modification R RΠ to I; notice that modif RΠ (I, R RΠ ) ⊂ I Π .

For a given reoptimization problem RΠ(Π, R RΠ ), a reoptimization instance I RΠ of RΠ is given by a triple (I, S, I ′ ), where: I denotes an instance of Π, referred to as the initial instance; S denotes a feasible solution for Π on the initial instance I; I ′ denotes an instance of Π in modif RΠ (I, R RΠ ); I ′ is referred to as the perturbed instance. For a given instance I RΠ (I, S, I ′ ) of RΠ, the set of feasible solutions is Sol Π (I ′ ).

Definition 2. For a given reoptimization problem RΠ(Π, R RΠ ), a reoptimization algorithm A is said to be a ρ-approximation reoptimization algorithm for RΠ if and only if: (i) A returns a feasible solution on all instances I RΠ (I, S, I ′ ); (ii) A returns a ρ-approximate solution on all reoptimization instances I RΠ (I, S, I ′ ) where S is an optimal solution for I.

Note that Definition 2 is the most classical definition found in the literature, as well as the one used in this paper. However, an alternate (and more general) definition exists (used for example in [START_REF] Bilò | Reoptimization of steiner trees[END_REF][START_REF] Bilò | Reoptimization of weighted graph and covering problems[END_REF][START_REF] Böckenhauer | Reoptimization of steiner trees: Changing the terminal set[END_REF][START_REF] Böckenhauer | On the hardness of reoptimization[END_REF]), where a ρ 1 -approximation reoptimization algorithm for RΠ is supposed to ensure a ρ 1 ρ 2 -approximation on any reoptimization instance I RΠ (I, S, I ′ ) where S is a ρ 2 -approximate solution in the initial instance I.

A property P on a graph is hereditary if the following holds: if the graph satisfies P, then P is also satisfied by all its induced subgraphs. Following this definition, independence, planarity, bipartiteness are three examples of hereditary properties: in a given graph, any subset of an independent set is an independent set itself, and the same holds for planar and bipartite subgraphs. On the opposite hand, connectivity is no hereditary property since there might exist some subsets of G whose removal disconnect the graph.

We denote by hereditary problem any problem that consists of finding the maximum set of vertices (in terms of cardinality or weight) that induces a subgraph verifying a given hereditary property.

A graph is said to be P k -free if it does not contain a path on k edges. Here, P k -free means that the graph does not admit a P k as minor (and not as induced subgraph). A graph H is a minor of a graph G, if H can be obtained by a sequence of edge contractions and vertex or edge deletions. For example, a C k+1 admits a P k as minor, so, although it does not admit a P k as induced subgraph, we consider that a C k+1 is not P k -free.

Let G(V, E, w) be a vertex-weighted graph with w(v) 0, for any v ∈ V . The max weighted P k -free subgraph problem is the problem consisting, given a graph G(V, E, w), of finding a subset S of vertices such that G[S] is P k -free and maximizes w(S) = v∈S w(v). For instance, max weighted independent set is exactly the max weighted P 2 -free subgraph problem, while max weighted P 3 -free subgraph consists of finding an independent set and an induced matching of maximum total weight.

As it is proved in [START_REF] Lund | The approximation of maximum subgraph problems[END_REF] (see Theorem 1 just below) most hereditary problems (hence max weighted P k -free subgraph also) are highly inapproximable unless P = NP.

Theorem 1. ([16]

) There exists an ε ∈ (0, 1) such that max weighted P kfree subgraph cannot be approximated with ratio n -ε in polynomial time unless P = NP.

In the sequel, G p and G ′ p will denote initial and perturbed instances, while OPT p and OPT ′ p will denote optimal solutions in G p and G ′ p , respectively. For simplicity and when no confusion arises, we will omit subscript p. The function w refers to the weight function, taking a vertex, a vertex set, or a graph as input (the weight of a graph is defined as the sum of weights of its vertices). Finally, note that throughout the whole paper, the term "subgraph" will always implicitly refer to "induced subgraph".

Under vertex insertion, the inapproximability bounds of Theorem 1 is easily broken. In [START_REF] Ausiello | Complexity and approximation in reoptimization[END_REF], a very simple strategy, denoted by R1 in what follows, provides a (1/2)-approximation for any hereditary problem. This strategy consists of outputting the best solution among the newly inserted vertex and the initial optimum. Moreover, this strategy can also be applied when a constant number h of vertices is inserted: it suffices to output the best solution between an optimum in the h newly inserted vertices (that can be found in O(2 h ) through exhaustive search) and the initial optimum. The 1/2 approximation ratio is also ensured in this case [START_REF] Ausiello | Complexity and approximation in reoptimization[END_REF].

Note that an algorithm similar to R1 was proposed for knapsack in [START_REF] Archetti | Reoptimizing the 0-1 knapsack problem[END_REF]. Indeed, this problem, although not being a graph problem, it is hereditary in the sense defined above, so that returning the best solution between a newly inserted item and the initial optimum ensures a (1/2)-approximation ratio. The authors also show that any reoptimization algorithm that does not consider objects discarded by the initial optimal solution cannot have ratio better than 1/2.

max weighted P k -free subgraph

The max weighted P k -free subgraph problem discussed in this subsection refers to max weighted P k -free subgraph (with P k as forbidden minor), and not to max weighted induced P k -free subgraph (with P k as forbidden induced subgraph). Formally, given a graph G(V, E, w) and a constant k n, the max weighted P k -free subgraph problem handled in this section consists of finding a maximum-total weight set of vertices that induces a subgraph of G that is P k -free. The approximability analysis of max weighted P k -free subgraph uses the following lemma whose proof can be found in [START_REF] Boria | Reoptimization of maximum weight induced hereditary subgraph problems[END_REF].

Lemma 1. A P k -free graph can be colored with k colors in polynomial time.

Proposition 1. Under one vertex insertion, max weighted P k -free subgraph is inapproximable within ratio 2k 3k+1 + ε in polynomial time if k is odd, and inapproximable within ratio 2k 3k+2 + ε if k is even, unless P = NP.

Proof (Sketch).

The technique used for the proof can be sketched as follows.

Considering an unweighted graph H(V, E) on which one wants to solve a given hereditary problem Π, known to be inapproximable within any constant ratio, we build a reoptimization instance I p , where p denotes a vector of fixed size (i.e., independent of the size n of G; so, |p| is a fixed constant) that contains integer parameters between 1 and n. This instance is characterized by an initial graph G p (that contains H), with a known solution, and a perturbed instance G ′ p . Then, we prove that, for some specific (yet unknown) value p ′ of the parameter vector p (that is, when the value of p coincides with some unknown structural parameters of the graph, like independence number for example), an optimal solution can be easily determined in the initial graph G p ′ , and a ρ-approximate

solution S p ′ in G ′ p ′ necessarily induces a solution S p ′ [V ]
in H, that is a constant approximation for the initial problem. Considering that the vector p can take at most n |p| possible values, it is possible in polynomial time to build all instances I p , to run the polynomial ρ-approximation algorithm on all of them, and to return the best set S p * [V ] as solution for Π in H. The whole procedure is polynomial and ensures a constant-approximation for Π, which is impossible unless P = NP, so that a ρ-approximation algorithm cannot exist for the considered reoptimization version of Π, unless P = NP.

Consider now a connected graph H that has independence number α, on which one wishes to solve (or approximate) max weighted independent set problem. Transform H into a graph H k (V, E) in the following way:

each vertex v i of H is turned into a clique V i of k vertices in H k ; if (v i , v j ) belongs to H,
then all edges between vertices of cliques V i and V j are in E. Note that H k is connected as H itself is also connected. Considering that the biggest independent set in H has size α, then the same holds in H k : an independent set in G can only take one vertex in each clique V i , and it cannot take two vertices from cliques that corresponds to neighbors in H.

Following Lemma 1, any P k -free subgraph in H k can be partitioned in k independent sets, so that, denoting by OPT an optimal P k -free subgraph in H k , |OPT| kα. Moreover, denoting by IS an optimal independent set in H (that has exactly α vertices), then, in H k , the union of all cliques corresponding to vertices of IS induces a P k -free subgraph with value exactly kα, so that |OPT| = kα.

Remark 1. Following the same arguments, it holds that for any i k a P i -free subgraph in H k cannot have weight more than iα (and an optimal one has weight exactly iα).

First, suppose that k is odd. We build a weighted reoptimization instance I α,k of max weighted P k -free subgraph as follows (Figure 1 provides a representation of the general structure).

-The initial graph G α,k is obtained by adding to the graph H k a set X of vertices which consists of two cliques X 1 , and X 2 to G. Both these cliques have k vertices, each with weight kα. Clique X 1 , is divided into two subcliques X 1C and X 1N C ; X 1C has (k + 1)/2 vertices that are all connected to all vertices in V , while the other (k -1)/2 vertices of X 1N C are not connected to any vertex in V . Clique X 2 is divided in the same manner. Finally, each vertex in V receives

X1C X1NC X2C X2NC k-1 2 k+1 2 k-1 2 k+1 2 y H k Fig. 1. Reoptimization instance I α,k
weight k + 1, hence, for any 1 i k an optimal P i -free subgraph inside V has weight exactly i(k + 1)α.

-The perturbed graph G ′ α,k is obtained by adding a single vertex y to G α , with weight k(k + 1)α, that is connected to all vertices of X.

We first prove that X defines an optimum on the initial graph G α,k , so that the reoptimization instance I α,k is well defined. Then, we show that

{y}∪X 1N C ∪ X 2N C ∪ F * (where F * is an optimum in H k ) is feasible in the graph G ′ α,k , so that w(OPT ′ ) w({y} ∪X 1N C ∪X 2N C ∪F * ) = k(3k + 1)α.
This lower bound on the weight of the optimum, naturally induces a lower bound on the weight of a 2k 3k+1 + ε -approximate solution, say S α,k : w (S α,k )

2k 3k+1 + ε w(OPT ′ ) (1 + ε)2k 2 α.
We then show that any feasible solution on the subgraph induced by {y} ∪ X cannot have weight more than 2k 2 α, and this holds a fortiori for the restriction of S α,k to this subgraph, denoted by S α,k [{y} ∪ X]. Combining this fact with the expression for w(S α,k ) above, and taking into account that {{y} ∪ X, V } defines a partition of the final graph, we derive that w(S α,k

[V ]) = w(S α,k ) - w(S α,k [{y} ∪ X])
2εk 2 α. Hence, a 2k 3k+1 + ε -approximation algorithm for the reoptimization version of max weighted P k -free subgraph can be used to derive a polynomial ε-approximation algorithm for the static version of max weighted independent set, which is impossible unless P = NP.

In the same way, we present a 2k 3k+2 + ε inapproximability bound for the case where k is even. The structure of the instance is somewhat more complex, but the structure of the proof itself is similar. A full proof of both inapproximability bounds can be found in [START_REF] Boria | Reoptimization of maximum weight induced hereditary subgraph problems[END_REF].

Remark 2. The proof of Proposition 1 works also even if we assume that a ρapproximate solution is given instead of an optimal one. In this case, the bounds claimed in Proposition 1 are simply multiplied by ρ.

We now prove that ratio of Proposition 1 is tight for small values of k, namely when k 6. Consider the following hypothesis. Hypothesis 1. In polynomial time, a P k -free subgraph S can be partitioned in 3 sets S 1 , S 2 and S 3 , such that both S 1 and S 2 are P ⌈k/2⌉-1 -free, and w(S 3 ) w(S)/k if k is odd and w(S 3 ) 2w(S)/k if k is even. Proposition 2. For values of k for which Hypothesis 1 is true, max weighted P k -free subgraph problem is approximable within ratio 2k 3k+1 for odd values of k, and 2k 3k+2 for even values of k in the reoptimization setting, under one vertex insertion.

Proof. Consider a reoptimization instance I of max weighted P k -free subgraph, given by two graphs G (initial) and G ′ (perturbed) and an optimal solution OPT on the initial graph G. Graphs G and G ′ differ only by vertex y (and its incident edges) which belongs to G ′ but not to G. Classically, denoting by OPT ′ an optimal solution on G ′ , it holds that w(OPT) w(OPT ′ )w(y). Suppose that Hypothesis 1 is verified, and consider the following algorithm: partition OPT in 3 sets S 1 , S 2 and S 3 as defined in Hypothesis 1, and without loss of generality, suppose w(S 1 ) w(S 2 ); set SOL 1 = S 1 ∪ {y} and SOL 2 = OPT; return the best solution SOL between SOL 1 and SOL 2 .

First, let us prove that this algorithm returns a feasible solution: SOL 2 is trivially feasible in G ′ , and consider a path P in SOL 1 . If this path does not go through y then it cannot go through more than ⌈k/2⌉ -1 vertices (by hypothesis, S 1 is P ⌈k/2⌉-1 -free). If it does go through y, then denote by P 1 the set of vertices visited before y in P and P 2 the set of vertices visited after. Considering that both P 1 and P 2 are included in S 1 , which is supposed to be P ⌈k/2⌉-1 -free, then both

|P 1 |, |P 2 | ⌈k/2⌉ -1, so that |P | = |P 1 | + |P 2 | + 1
k, and thus SOL 1 is also P k -free.

Let r k be an integer that is equal to 1 if k is odd, and to 2 if k is even. Regarding the partitioning induced by Hypothesis 1, it holds that w(S 3 ) w(OPT ′ )w(y). Summing expressions for w(SOL 1 ) and w(SOL 2 ) with coefficients 1 and k+r k 2k respectively, one finally proves that 3k+r k 2k w(SOL) w(SOL 2 ) + k+r k 2k w(SOL 1 ) w(OPT ′ ).

r k w(OPT) k
Note once more that, as it can be seen from the proof of Proposition 2, Remark 2 always holds. Proposition 3. Hypothesis 1 holds for k 6.

Proof (Sketch).

In what follows, we suppose that the P k -free graph S to be partitioned is connected (if it is not so, then proving that the hypothesis is true for each of its connected components amounts to proving it for the whole graph). k = 1, 2. Simply set S 3 = S and S 1 , S 2 = ∅. k = 3. Split the graph in three independent sets S ′ 1 , S ′ 2 ,and S ′ 3 in polynomial time (that is possible according to Lemma 1), and w.l.o.g., suppose w(S ′ 1 ) w(S ′

2 ) w(S ′ 3 ). Finally, set S 1 = S ′ 1 , S 2 = S ′ 2 , and S 3 = S ′ 3 . k = 4. Split the graph in four independent sets from S ′ 1 to S ′ 4 in polynomial time, and w.l.o.g., suppose w(S ′ 1 ) w(S ′ 2 ) w(S ′ 3 ) w(S ′ 4 ). Finally, set S 1 = S ′ 1 , S 2 = S ′ 2 , and S 3 = S ′ 3 ∪ S ′ 4 . k = 5. This case requires a rather long and involved analysis, which could not be included in the paper due to length limits. A full proof can be found in [START_REF] Boria | Reoptimization of maximum weight induced hereditary subgraph problems[END_REF]. k = 6. In this case, Hypothesis 1 is verified if S can be partitioned in 3 P 2free subgraphs (the lightest of which will be S 3 , and the other two S 1 and S 2 ). Here, we distinguish the following four cases.

Case 1. S contains a C 6 . It is clear that S contains exactly 6 vertices, which can easily be partitioned in three P 2 -free subgraphs (2 vertices in each set of the partition).

Case 2. S contains a C 5 and no C 6 . Let S ′ denote the set of vertices that are not in C 5 . It holds that S ′ is an independent set, and that a pair of vertices that are neighbors in the C 5 cannot both have neighbors in S ′ (if one of these two properties is not verified, then there exists a P 6 in S. Thus, without making assumption on the number of chords in C 5 , the general structure of S is as described in Figure 2, with a partitioning in three P 2 -free subgraphs (represented in the figure as white, grey, and black vertices). Case 3. S contains a C 4 . We distinguish here the following two subcases. Case 3-a. S contains a C 4 but no C 5 and no C 6 , and denoting by S ′ the set of vertices that are not in the C 4 , S ′ contains at least an edge (v 1 , v 2 ). Obviously, these two vertices v 1 and v 2 cannot be connected to two different vertices of the C 4 , otherwise, S would contain a C 5 or a C 6 .

Moreover, at least one of these two vertices must be connected to a vertex of the C 4 . Indeed, taking into account that S is supposed to be connected, if none of these vertices is connected to a vertex of the C 4 , then there exists a P 6 in S.

Finally, supposing w.l.o.g that v 1 is the vertex connected to a vertex x in the C 4 , then no neighbor of x in the C 4 can be connected to any vertex of S ′ (otherwise there would exist a P 6 in S).

Hence, denoting vertices of the C 4 by x, y, z and t as in Figure 3, only vertices x and z might have neighbors in S ′ . Moreover, denoting by N ({x} ∪{z}) the neighborhood of these two vertices, it holds that this set is P 2 free, otherwise a path on 7 vertices would exist in S (the 3 vertices of the P 2 in N ({x} ∪ {z}), and the 4 vertices of the C 4 ). Thus, coloring in white the vertices of N ({x}∪{z}) as well as y and t, and in black all the other vertices of S, one gets a partition of S into two P 2 free colors. Case 3-b. S contains a C 4 but no C 5 and no C 6 , and let S ′ denote the set of vertices that are not in the C 4 , S ′ contains no edge. This case is much simpler than the previous one, considering that S ′ forms an independent set. To get a partition of S into three P 2 -free subgraphs, it suffices to consider S ′ itself as the first subset of the partition, {x} ∪ {z} as the second, and {y} ∪ {t} as the third.

Case 4. S contains no C 4 , no C 5 and no C 6 . In this case, it holds that the neighborhood N (x) of any vertex x is P 2 -free, since a P 2 (on 2 edges, and 3 vertices) in N (x) amounts to a C 4 in x ∪ N (x). Moreover, denoting by N (N (x))) = N 2 (x)) the set of neighbors of vertices in N (x), it holds that N (N (x)) is also P 2 -free, since the neighborhood of each vertex in N (x) is P 2 -free (considering what we stated above), and disjoint from one another (otherwise there would exist a C 4 in S). Naturally, the same holds for any N i (x).

Hence, in this case, the graph can be easily partitioned in 2 P 2 -free subgraphs: starting from a arbitrary vertex that is colored black, one colors its neighborhood white, then the neighborhood of its neighborhood black, etc. Considering what we proved earlier, each color defines a P 2 -free subgraph.

Finally, Hypothesis 1 is also verified when k = 6.

Reoptimization and bin packing

Given a constant B, a list L of n items L = (1, 2, . . . , n), such that, for any i = 1, . . . , n, its size a i B, and n bins each of capacity B, the bin packing problem consists of arranging the items of L in the bins without exceeding their capacity (i.e., the sum of the sizes of the items placed in every bin must not exceed B) and in such a way that a minimum number of bins is used.

We show in this section that the basic technique used before in order to get inapproximability results can be also applied on hereditary problems not necessarily defined on graphs. This is, for instance the case of bin packing. We will prove that this problem is inapproximable within approximation ratio 3/2ε, for any ε > 0, in the reoptimization setting studied in this paper. For simplicity we consider a non-normalized instance of bin packing where item i, i n has integer size a i and bins have capacity B. We also assume that, for every i, a i < B.

Suppose, ad contrario, that bin packing is approximable within approximation ratio 3/2 under items insertion and consider an instance I of the partition problem, where n + 1 items 0, 1, . . . , n with sizes a 0 , a 1 , . . . , a n are given such that, for i = 0, 1, . . . , n, a i < B and n i=0 a i = 2B, and the objective is to find a partition of the items (if any) into two subsets such that the sum of the sizes of their items is equal to B. partition is known to be NP-complete.

Assume now that items are ordered in decreasing size order (i.e., a 0 a 1 . . . a n ) and consider the list of items L = (a 1 , . . . , a n ) as instance of bin packing. Obviously, since a 0 < B and

n i=0 a i = 2B, it holds that n i=1 a i > B.
Thus, an optimal bin packing-solution for L has value greater than 1. We claim that L has a solution using 2 bins. Indeed, such a solution places the first k items in one bin, where k is the largest index such that k i=1 a i B, and the rest of the items from k + 1 to n in a second bin. Let us prove that such a solution is feasible, or equivalently, that In all, we can assume that the initial bin packing-instance is L and the optimal solution provided with is as just described.

Assume now that item 0 with size a 0 a 1 arrives. On the hypothesis of the existence of a polynomial reoptimization algorithm achieving approximation ratio 3/2ε for bin packing, if the instance I of partition is a "yes"-instance, then this algorithm would provide a solution with 2 bins, while if I is a "no"instance, the algorithm would provide a solution with at least 3 bins, deciding so in polynomial time partition.

On the other hand, bin packing is immediately approximable within 3/2 in the reoptimization setting under consideration. Given an instance L and a solution with k bins, when an element arrives, one can open a new bin in order to place it (after, eventually, a quick check that all the items cannot be placed in the same bin) guaranteeing so an approximation ratio (k +1)/k 3/2, for k 2, while the case k = 1 is trivially polynomial (just check whether n i=1 a i B, or not).

Conclusion

We have discussed the approximability of max weighted P k -free subgraph in the reoptimization setting under vertex insertion. It appears that the initial optimum (or a good initial solution) provides a very useful information when approximating the modified instances, and we presented reoptimization algorithms which take advantage of this information in the best possible way, since the approximation ratio provided is the best constant ratio achievable in polynomial time (unless P = NP). In this paper, we have proved optimal results for max weighted P k -free subgraph even if there exist 2 different weights 1 and M in the instance. We can easily prove that max weighted P k -free subgraph has a PTAS for any fixed k. Moreover, we can adapt the proofs given in the paper to produce results depending on parameter M as done in [START_REF] Bilò | Reoptimization of weighted graph and covering problems[END_REF]. Finally, in [START_REF] Böckenhauer | Knowing all optimal solutions does not help for TSP reoptimization[END_REF], the authors prove that the knowledge of all optimal solutions for free doesn't help TSP reoptimization. It is interesting to handle this question for max weighted P k -free subgraph.

,

  and thus w(S 1 ) (w(OPT)w(S 3 ))/2 k-r k 2k w(OPT), thus w(SOL 1 ) k-r k 2k w(OPT) + w(y) = k-r k 2k w(OPT ′ ) + k+r k 2k w(y). On the other hand, w(SOL 2 )

Fig. 2 .

 2 Fig. 2. Partition of P6-free graph in 3 P2-free subgraphs in Case 2

Fig. 3 .

 3 Fig. 3. Partition of P6-free graph in 2 P2-free subgraphs in Case 3-a

  Assume, ad contrario, that n i=k+1 a i > B, recall that, by the definition of k, k+1 i=1 a i > B and observe that k i=0 a i k+1 i=1 a i > B. In other words, on the hypothesis that n i=k+1 a i > B, we derive that n i=0 a i = k i=0 a i + n i=k+1 a i > B + B = 2B, a contradiction. So, the bin packing-instance L has a solution of 2 bins.

* Research supported by the French Agency for Research under the DEFIS program TODO, ANR-09-EMER-010