Diodato Ferraioli
email: ferraioli@dis.uniroma1.it

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

Jérôme Monnot
email: jerome.monnot@dauphine.fr

On Regular and Approximately Fair Allocations of Indivisible Goods

Keywords: J.4 [Computer Applications]: Social and Behavioral Sciences -Economics; I.2.11 [ Distributed Artificial Intelligence]: Multiagent Systems Algorithms, Economics, Theory Computational social choice, Fairness, Approximation

An active stream of research is devoted to the design of polynomial approximation algorithms for the fair allocation of indivisible goods. Central to this field is the MaxMin Allocation problem, for which there is a significant gap between known approximation and inapproximability results. Closing this gap is a stimulating challenge.

To this end, we consider a regular version of MaxMin Allocation where each agent must receive exactly k goods, for a given integer k. We call this problem k-division. The analysis of this problem allows us to highlight two interesting features of the classical MaxMin Allocation problem. First, we show a close connection of the problem with matroid theory. This connection provides us an exact algorithm for a special case of k-division and a 1/k-approximation algorithm for general inputs. Moreover, we show that the difficulty of the MaxMin Allocation may be caught by an apparently simpler problem, namely the k-division problem in which an agent's utility for a single good can only take one value out of three.

INTRODUCTION

The problem of fairly allocating a given set of items to a given set of agents is very old, and it is treated in many fields including political science, economics (social science in particular) and, more recently, theoretical computer science. Numerous variants of the problem exist. Are the items goods or chores? Are they divisible (e.g. lands) or indivisible (e.g. jobs)? Is it possible to make monetary compensations? Even for the notion of fairness, the context leads to distinct, and still significant, formulations. For example, one can require that no agent finds her share less valuable than the share of another one; this is commonly known as envy-freeness. However, it is sometimes possible to satisfy a criterion of fairness and make a poor utilization of the resources at the same time. Hence, efficiency comes naturally into play.

Several concepts which capture efficiency and fairness at the same time have been defined. Here we focus on one of these, known as maxmin, whose goal is to maximize the welfare of the least happy agent. The typical problem concerning the maxmin concept has been named MaxMin allocation [START_REF] Bezáková | Allocating indivisible goods[END_REF][START_REF] Golovin | Max-min fair allocation of indivisible goods[END_REF][START_REF] Bansal | The Santa Claus problem[END_REF]. Here, we are given a set A of n agents, a set R of m indivisible resources and a binary relation E ⊆ A × R where (i, r) ∈ E means that resource r is available to agent i. There are non-negative utilities ui(r) for each i ∈ A and r ∈ R such that (i, r) ∈ E. A feasible solution is an allocation of the resources R = (R1, . . . , Rn) where Ri are the resources received by agent i, such that Ri ∩ Rj = ∅ and (i, Ri) = {(i, r) : r ∈ Ri} ⊆ E for each 1 ≤ i, j ≤ n. The goal is to maximize u(R) = mini∈A ui(Ri) where ui(Ri) is defined as r∈R i ui(r) (some variants in which ui(Ri) is not additive have been also studied; see e.g. [START_REF] Golovin | Max-min fair allocation of indivisible goods[END_REF]). A lot of work has been devoted to the MaxMin allocation problem (see the related work section). It is indeed known that the problem is hard to solve and several approximation algorithms have been proposed. Nevertheless, a large gap exists between the best inapproximability bound and the approximation ratio of the best known approximation algorithm.

In order to gain insight on the nature of this gap, we consider a special restriction of the MaxMin allocation problem. Specifically, we consider a set A of n agents, a set R of kn indivisible resources and a binary relation E ⊆ A × R. Moreover, each agent i ∈ A has a non negative utility ui(r) for resource r ∈ R which is available to her. We want to find an allocation of the resources R = (R1, . . . , Rn) such that |Ri| = k, Ri ∩ Rj = ∅, (i, Ri) ⊆ E for each 1 ≤ i, j ≤ n. The goal is to maximize u(R) = mini∈A ui(Ri) where ui(Ri) is defined as above. Hence, this problem, that we name as the k-division problem, is just constraining MaxMin Allocation to assign exactly k items per agent. 1 1 Note that this constraint has a severe effect on the role of the binary relation E. Indeed, for the MaxMin Allocation problem, any instance with E ⊂ A × R can be reduced to an equivalent instance (A, R, E , (u)i∈A) for which the relation E is complete (that is each resource is Even if this restricted problem has been introduced for getting an insight in the original problem, it turns out to be interesting on its own. Indeed, giving to each agent a fixed number of items is a basic additional notion of fairness. One can think of n kids making a joint celebration of their birthday. Their presents are gift-wrapped and it is preferable that the number of parcels, which is a kid's first estimation, is exactly the same for everyone. Another example comes from program committees: here reviewers are usually asked to express preferences about the papers they prefer to review and there are constraints on the possible assignments (e.g., a reviewer cannot have a close connection with the assigned paper's authors). Nevertheless, the committee must assign the same number of papers to any reviewer and this assignment should be fair with respect to the expressed preferences. This application also motivates a limitation of our problem to the case in which utility may assume only few values: indeed, preferences are usually expressed through forms allowing only a limited set of inputs.

Related work. The literature on social welfare optimization in multi-agent resource allocation with fairness constraints is vast and we refer the interested reader to the survey by Nguyen et al. [START_REF] Nguyen | A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation[END_REF]. Here we focus on the previous work about approximation algorithms for the MaxMin Allocation problem, where an algorithm is ρ-approximate if AP X(I)/OP T (I) ≥ ρ holds for any instance I (AP X(I) and OP T (I) being the values returned by the approximation and the optimal algorithms, respectively).

Bezáková and Dani consider the MaxMin allocation problem in which m indivisible goods are distributed to n agents [START_REF] Bezáková | Allocating indivisible goods[END_REF]. They give two deterministic approximation algorithms with a priori incomparable ratios. The first one is matching-based and it has a ratio of 1/ (m -n + 1). The second consists of modeling the problem with an integer linear program (ILP). An appropriate rounding of the optimum of the relaxed ILP provides an approximate solution. The approximation ratio is the optimal value of the relaxed ILP minus the largest value an agent can have for a single item.

On the negative side, Bezáková and Dani show that, following a reduction of 3-Matching, no ρ-approximation algorithm with ρ > 1 2 exists, unless P=NP [START_REF] Bezáková | Allocating indivisible goods[END_REF]. This means that the problem is computationally hard, and even a polynomial algorithm that produces a solution arbitrarily close to the optimum is unlikely. A similar result, with a different reduction, is given independently by Golovin [START_REF] Golovin | Max-min fair allocation of indivisible goods[END_REF]. Two other 1 2 -inapproximability results for a restricted case where each item has a nonzero value for at most two agents exist [START_REF] Chakrabarty | On Allocating Goods to Maximize Fairness[END_REF][START_REF] Bateni | MaxMin allocation via degree lower-bounded arborescences[END_REF].

Golovin [START_REF] Golovin | Max-min fair allocation of indivisible goods[END_REF] proposes an algorithm that builds an allocation for which a 1 -1/p fraction of the agents has utility at least a p -1 fraction of the optimum. Bansal and Sviridenko [START_REF] Bansal | The Santa Claus problem[END_REF] study a restricted case in which ui(r) ∈ {0, pr}. They provide an LP relaxation, referred to as configuraavailable to each agent) simply by setting utility zero for each (i, r) ∈ E \ E. This equivalence does not hold in the k-division problem. To see this, consider two agents A = {1, 2}, four resources r1, . . . , r4 (so, k = 2) and

E = {(1, r1), (1, r2), (2, r2), (2, r3), (2, r4)}. Let u1(r1) = u2(r2) = M > 2 while u1(r2) = u2(r3) = u2(r4) = 1.
There is a unique feasible allocation, namely R = (R1, R2) with R1 = {r1, r2} and R2 = {r3, r4}, of value u(R) = 2. If we complete this instance as described above, then the instance

R * = (R * 1 , R * 2 ) with R * 1 = {r1, r3} and R * 2 = {r2, r4} becomes feasible. But u(R * ) = M > u(R).
tion LP, from which they derive an approximation algorithm with factor Ω(log log log n/ log log n). An even more restricted case, called "Big goods/Small goods", is shown Ω(1/ √ n)-approximable in [START_REF] Golovin | Max-min fair allocation of indivisible goods[END_REF]. Khot and Ponnuswami [START_REF] Khot | Approximation Algorithms for the Max-Min Allocation Problem[END_REF] and Asadpour and Saberi [START_REF] Asadpour | An Approximation Algorithm for Max-Min Fair Allocation of Indivisible Goods[END_REF] provide approximation algorithms for the general MaxMin Allocation problem with ratios (2n -1) -1 and Ω 1/ √ n log 3 n , respectively. Note that these algorithms improve on the original 1 m-n+1 bound only for m sufficiently large. The last developments are due to Chakrabarty et al. [START_REF] Chakrabarty | On Allocating Goods to Maximize Fairness[END_REF] who give a quasi-polynomial Ω(1/n )-approximation algorithm, for any ≤ log log m log m .

Our contribution. The analysis of k-division highlights interesting features of the MaxMin allocation problem. First, we show there exists a close connection between the problem and matroid theory (also in [START_REF] Gourvès | A Matroid Approach to the Worst Case Allocation of Indivisible Goods[END_REF], matroid theory is linked to the allocation of indivisible goods with the aim to build solutions with worst case guarantees for agents). Indeed, we depart from previous techniques (e.g. linear programming) and, drawing on matroid theory, we propose an approximation algorithm with ratio 1/k.

Next, we investigate instances in which the agents' utilities for the items can take a limited number of values. In particular, we provide an exact algorithm for the k-division problem in which an agent's utility for a resource can only take two values. This algorithm will be useful also for improving the approximation ratio for instances in which the agent's utility can take more than two values. These improved ratios turns out to be far from being tight, even for only three utility values. However, we highlight that closing the approximation gap for this apparently simple problem may be a breakthrough shading a completely new light on the long-standing gap in the approximation ratio of the MaxMin allocation problem.

PRELIMINARY RESULTS

Checking if an instance (A, R, E, (ui)i∈A) of the k-division problem contains a feasible solution can be done in polynomial time. Indeed, the problem is equivalent to finding a flow of value kn in the network G = (V, E) such that the set of vertices V contains a source vertex s, a target vertex t, a vertex vi for each agent i ∈ A and a vertex wr for each resource r ∈ R, and the set of edges E contains an edge (s, vi) for each i ∈ A, an edge (vi, wr) for each (i, r) ∈ E, and an edge (wr, t) for each r ∈ R, each of capacity one.

Moreover, finding the max-min allocation among the feasible ones can be done in polynomial time if k = 1. Indeed, the problem is equivalent to finding the bottleneck weighted matching in a bipartite graph B = ((A, R), E) where the edge (i, r) weights ui(r). Unfortunately, next theorem shows that it is not possible to extend this result to higher k. Theorem 1. For any k ≥ 2, the k-division problem is strongly NP-complete even if E is complete and there is B ≥ 0 such that for every resource r ∈ R, i∈A ui(r) = B.

Proof. For k = 2, we reduce the 2-numerical matching with target sums (2NMTS in short) problem. The inputs of 2NMTS is a sequence a1, . . . , an of n positive integers with n i=1 ai = n(n + 1) and 1 ≤ ai ≤ 2n for i = 1, . . . , n. We want to decide if there are two permutations f and g of the integers {1, . . . , n} such that f (i) + g(i) = ai for i = 1, . . . , n. 2NMTS is strongly NP-complete [START_REF] Yu | Minimizing Makespan in a Two-Machine Flow Shop with Delays and Unit-Time Operations is NP-Hard[END_REF].

Consider an instance (ai)i of 2NMTS. We build an instance (A, R, (ui)i∈A) of the 2-division problem as follows: there are n agents A = {1, . . . , n} and 2n resources R = {rj, r j : j = 1, . . . , n}. For j = 1, . . . , n, the utility of agent i ∈ A for resources rj, r j ∈ R is given by ui(rj) = ui(r j ) = n + j -a i 2 . This construction can be done within polynomial time. In particular, the utilities are polynomially bounded, since 0 < ui(r) < 2n for every r ∈ R and every i ∈ A.

We claim that a1, . . . , an is a yes-instance for the 2NMTS problem if and only if there is an allocation of the resources R = (R1, . . . , Rn) with |Ri| = 2 such that u(R) ≥ 2n.

Clearly, if there are two permutations f and g of {1, . . . , n} such that f (i) + g(i) = ai for i = 1, . . . , n, then by setting Ri = {r f (i) , r g(i) } for i = 1, . . . , n, we obtain an allocation R = (R1, . . . , Rn), with |Ri| = 2, such that ui(Ri) = 2n + f (i) + g(i) -ai = 2n for any agent i. Hence, u(R) ≥ 2n.

Conversely, let R = (R1, . . . , Rn) with |Ri| = 2 be an allocation of the resources such that u(R) ≥ 2n. Since ui(rj) = ui(r j ) for any i, j ∈ {1, . . . , n} we can assume without loss of generality that in any allocation R = (R 1 , . . . , R n ), any agent takes a resource from {r1, . . . , rn} and a resource from {r 1 , . . . , r n }, i.e., for any i ∈ {1, . . . , n}, |R i ∩{r1, . . . , rn}| = 1 and |R i ∩ {r 1 , . . . , r n }| = 1. Thus, given R, we define f (i) as the index of the unique element in Ri ∩ {r1, . . . , rn} and g(i) as the index of the unique element in Ri ∩ {r 1 , . . . , r n }, i.e. f (i) = j for j such that rj ∈ Ri ∩ {r1, . . . , rn} and g(i) = j for j such that r j ∈ Ri ∩ {r 1 , . . . , r n }. Observe that, since a resource is assigned to exactly one agent, the functions f and g are partitions. Moreover, we can rewrite the utility of agent i for R as ui(Ri

) = 2n + f (i) + g(i) -ai. Since n i=1 ai = n(n + 1), it follows that i∈A ui(Ri) = i∈A (2n + f (i) + g(i) -ai) = n 2 . Thus, 2n ≤ u(R) ≤ 1 n n i=1 ui(Ri) = 2n, that is u(R) = 2n
and, consequently, ui(Ri) = 2n for each i ∈ A. It follows that f (i) + g(i) = ai for i = 1, . . . , n, and thus a1, . . . , an is a yes-instance.

For k ≥ 3, the proof is similar. In fact, we add a set R of (k -2)n new resources and we set ui(r ) = 3n for each agent i ∈ A and for each new resources r ∈ R . It is then easy to see that a1, . . . , an is a yes-instance for 2NMTS if and only if there exists an allocation R = (R1, . . . , Rn) of R ∪ R such that |Ri| = k and u(R) ≥ 2n + 3(k -2)n.

MATROIDS & K-DIVISION

In this section we show an interesting relationship existing between the k-division problem and matroid theory.

Matroid theory.

A matroid M = (X, F) consists of a finite set of n elements X and a collection F of subsets of X such that: (i) ∅ ∈ F; (ii) if F2 ⊆ F1 and F1 ∈ F, then F2 ∈ F; (iii) for every pair F1, F2 ∈ F such that |F1| < |F2|, there exists e ∈ F2 \ F1 such that F1 ∪ {e} ∈ F.
The elements of F are called independent sets. We refer the interested reader to [START_REF] Oxley | Matroid Theory[END_REF] for more details on matroid theory.

For an example of matroid, consider an undirected graph G = (V, E) and consider M = (X, F) such that X = E and the independent sets represent all possible forests (acyclic sets of edges) of G. Observe that the graph G ∅ = (V, ∅) is a forest and, hence, ∅ ∈ F. Moreover, if the graph G1 = (V, F1) is a forest, then for each F2 ⊆ F1 the graph G2 = (V, F2) is also a forest and hence F2 ∈ F. Finally, if both G1 = (V, F1) and G2 = (V, F2) are forests and |F1| < |F2|, then G2 has fewer connected components; hence we have that there is a component C ⊆ V in G2 that corresponds to two or more components of G1; then, along any path in C such that the endpoints belong to different components of G1, there must be an edge e ∈ F2 whose endpoints are in different components; thus adding this edge to F1 produces a forest with more edges and hence also condition (iii) above is satisfied. Then, we can conclude that M is a matroid, that is usually called the graphic matroid of G.

Other useful examples are the partition and the laminar matroids. (E, F) is a partition matroid if given non negative integers b1, . . . , b and disjoint sets E1, . . . , E , we have

E = ∪ i=1 Ei and F = {F ⊆ E : |F ∩ Ei| ≤ bi, i = 1, . . . , }.
(E, L) is a laminar matroid if, given non negative integers b1, . . . , b and sets E1, . . . , E such that for any pair i, j, one of the following three cases occurs:

Ei ⊆ Ej, Ej ⊆ Ei or Ei ∩ Ej = ∅, we have E = ∪ i=1 Ei and L = {L ⊆ E : |L ∩ Ei| ≤ bi, i = 1, . . . , }.
Note that the partition matroid is a special case of the laminar matroid.

Several optimization problems have been considered for matroids. A classical problem consists of computing, given an assignment of weights w(e) ∈ R + to each element e ∈ X, a base B ∈ F that maximizes e∈B w(e). It is known that this problem can be solved by an algorithm polynomial in |E| [START_REF] Oxley | Matroid Theory[END_REF]. Another optimization problem considers matroids M1 = (X, F1) and M2 = (X, F2) defined over the same set of elements X and an assignment of weights w(e) ∈ R + to each element e ∈ X, and consists in finding the set F of maximum weight in F1 ∩ F2. Even this problem is known to be solvable in time polynomial in |E| [START_REF] Oxley | Matroid Theory[END_REF]. k-division as the intersection of two matroids. Now we model k-division as an optimization problem on matroids.

For an instance (A, R, E, (ui)i∈A) of the k-division problem, we can denote by Ai ⊆ R the relations that state which resources are available to agent i, i.e. Ai = {(i, r) ∈ E} for every i ∈ A. Similarly, we denote by Rj the relations that state to which agents the resource j is available, i.e. Rj = {(a, j) ∈ E} for every j ∈ R. It is not difficult to see that both (A1, . . . , An) and (R1, . . . , R kn ) form a partition of E. We can then consider two partition matroids M1 = (E, F1) and M2 = (E, F2) such that

F1 = {F ⊆ E : |F ∩ Ai| ≤ k, i ∈ A} and F2 = {F ⊆ E : |F ∩ Rj| ≤ 1, j ∈ R}.
Then it is straightforward to see that (A, R, E, (u)i∈A) admits a feasible solution (i.e. exactly k resources are allocated to every agent) if there exists a set F of size kn in the intersection of these matroids, i.e. F ∈ F1 ∩ F2. Indeed, from the first matroid we know that an agent gets at most k resources; from the second matroid we know that a resource is allocated to at most one agent.

Note that, since it is possible to compute the maximal intersection of two matroids in polynomial time, this gives an alternative way for checking in polynomial time if an instance of k-division admits at least one feasible allocation. We next show that modeling the problem with matroids allows us to achieve new interesting results. For the sake of presentation, from now on, we always suppose that the given instances admit at least one feasible allocation.

k-division with two utilities. Consider the restriction of the k-division problem in which an agent's utility for a resource can only take two values υ1 or υ2, with 0 ≤ υ1 < υ2.

Matroid theory allows us to solve this problem.

Theorem 2. There exists a polynomial time algorithm that solves the k-division problem when the agent's utility assumes only values υ1 or υ2, with 0 ≤ υ1 < υ2.

Proof. Let (A, R, E, (ui)i∈A) be an instance of the problem and let us denote by u * the utility of the least happy agent. We have that there exists a unique integer b such that u * = bυ1 + (k -b)υ2. Thus, in order to guarantee that the utility of the least happy agent is at least u * , it is sufficient to guarantee that every agent receives k resources, and for at most b of them the utility is υ1.

Remember the definition of Ai given above. For every agent i, we consider A 1 i ⊆ Ai that contains any element (i, r) ∈ Ai such that ui(r) = υ1. Then, for each b = 0, . . . , k we can define a laminar matroid

M b 1 = (E, F 1)
where

F 1 = {F ⊆ E : |F ∩ A 1 i | ≤ b, |F ∩ Ai| ≤ k, i ∈ A}.
Then any agent receives k resources, and for at most b of them the utility is υ1 if and only if the intersection between M b 1 and the matroid M2 defined above is not empty (and this can be checked in polynomial time). By iterating on b ∈ {0, . . . , k}, we then find an allocation where the utility of the least happy agent is u * .

Note that the k-division problem cannot be solved, even for only two utility values, by the approach of allocating every item to the agent who likes it the most, that instead works in similar but not equivalent settings [START_REF] Bouveret | Allocation of indivisible goods: a general model and some complexity results[END_REF].

Approximating the k-division problem. Matroid theory turns out to help to design also approximate algorithms.

Theorem 3. For any k ≥ 1, there exists a polynomial time algorithm that 1 k -approximates the k-division problem. Proof. Let (A, R, E, (ui)i∈A) be an instance of the problem. We denote by U the set of all possible utilities an agent can have for a single resource. Note that there are at most

n 2 k such distinct values, thus |U | ≤ n 2 k.
Remember the definition of Ai for each agent i ∈ A and of Rj for each resource j ∈ R. Moreover, for every agent i and w ∈ U, let A w i = {(i, r) ∈ Ai : ui(r) < w}. We clearly have A w i ⊆ Ai. Then, given w ∈ U, we can define the laminar matroid M w 1 = (E, F w 1 ) where

F w 1 = {F ⊆ E : |F ∩ A w i | ≤ k -1, |F ∩ Ai| ≤ k, i ∈ A}.
As previously stated, we can find in polynomial time the independent set Iw of maximum cardinality in the intersection of M w 1 and M2 defined above. Observe that if |Iw| = kn then the instance of k-division admits a feasible allocation, i.e. each agent gets k resources, and for at least one of these, her utility is at least w.

Let w be the largest value in U such that |I w | = kn. One can find w and the corresponding independent set I w by an exhaustive search in U. Since every step is polynomial and the number of steps is polynomial, so is the whole algorithm.

Thus, we are only left with proving that I w is a 1/kapproximate solution. Let R * = (R * 1 , . . . , R * n ) be an optimal allocation. Denote by p the least happy agent, i.e. up(R * p ) ≤ ui(R * i ) for all i. Let w = up(R * p )/k. Every agent i has at least one resource r in R * i such that ui(r) ≥ w , otherwise ui(R * i ) < kw = up(R * p ). Since w may not belong to U, let us define w as min{w ∈ U : w ≥ w }. We have that every agent i has at least one resource r in R * i such that ui(r) ≥ w ≥ w and w ∈ U . Thus in F w 1 ∩ F2 there is an independent set I w of cardinality |kn|. Then the returned solution has value at least w ≥ w ≥ w ≥ up(R * p )/k = u(R * )/k where R * is the optimal allocation. We now show how the above algorithm works.

Example 1. Let (A, R, E, (u)i∈A) be an instance of 2division such that |A| = n, |R| = 2n and E is complete, i.e. (i, r) ∈ E for each agent i ∈ A and resource r ∈ R. We assume n is even. We partition the set of resources R in quadruples of resources (r 1 i , r 2 i , r 3 i , r 4 i ) for i = 1, . . . , n 2 . As for the utility functions, for agents i = 1, . . . , n 2 , we set ui(r 1 i ) = 1, ui(r 2 i ) = 1 and ui(r) = 0 for any other resource r ∈ R; for agents i = n 2 + 1, . . . , n, we set ui(r 3 i-n/2 ) = 2, ui(r 2 i-n/2 ) = 1 and ui(r) = 0 for any other resource r ∈ R. The optimal assignment is then R * = (R * i )i=1,...,n where

R * i = (r 1 i , r 2 i ) for each i = 1, . . . , n 2 , whereas for i = n 2 + 1, . . . , n, we have R * i = (r 3 i-n/2 , r 4 i-n/2
). Note that each agent obtains at least utility 2, so u(R * ) = 2.

As for the approximation algorithm described above, U = {0, 1, 2}. Since a feasible solution exists, it costs at least 0.

The algorithm then checks if there is an assignment in which each agent receives exactly two resources and for at least one of these her utility is at least 1. Since such an assignment exists (e.g., R * ), then the test must be successful.

Next, the same work is done with the last element in U. Unluckily, no assignment such that each agent receives at least one resource for which her utility is at least 2 exists (for agents i = 1, . . . , n 2 no resource has utility at least 2). Thus the largest value in U for which the test has been successful is 1 and hence the approximation algorithm returns an allocation with at least this value, that is a 1 kapproximation of the optimal solution.

THE THREE UTILITY CASE

One can wonder if the algorithms presented in the previous section and based on the relation between the k-division problem and matroid theory are optimal. In this section, we try to answer this question. It is interesting to note that this "tentative" answer highlights an interesting relation between a long-standing problem about the MaxMin Allocation problem and the apparently more simple problem of k-division in which the agent's utility for an item can only take one value out of three. These values are denoted by υ1, υ2 and υ3 and they satisfy 0 ≤ υ1 < υ2 < υ3.

Inapproximability with three utilities. We start by showing that Theorem 2 is tight. That is, the restriction to two distinct utilities is necessary if one seeks a polynomial algorithm (unless P = P N ). Actually, we show an even stronger result: there is no polynomial algorithm that ρ-approximate the k-division problem in which the agents' utilities take only three values, for some constant ρ which depends on (υ1, υ2, υ3). The proof of this result resembles a similar one given in [START_REF] Bezáková | Allocating indivisible goods[END_REF]. However, we give here a full exposition because it involves peculiarities that are not present in [START_REF] Bezáková | Allocating indivisible goods[END_REF]. Moreover, the insight provided by this proof will be useful later. Theorem 4. For any k ≥ 2, ε > 0 and three values, 0 ≤ υ1 < υ2 < υ3, unless P=NP, there is no polynomial time algorithm that (ρ + ε)-approximate the k-division problem with three distinct utility values, where

ρ = υ2 + (k -1)υ1 min{2υ2, υ1 + υ3} + (k -2)υ1
.

The theorem holds even if E is complete.

Proof. We give a gap-introducing reduction of the 3-Dimensional Matching (3DM in short) problem. An instance of 3DM consists of a subset C = {e1, . . . , en} ⊆ X × Y × Z of n triples, where X, Y, Z are 3 pairwise disjoint sets of size with X = {x1, . . . , x }, Y = {y1, . . . , y } and Z = {z1, . . . , z }. A matching is a subset M ⊆ C such that no two elements in M agree in any coordinate. The goal of 3DM is to decide if there exists a perfect matching M on C, that is, a matching of size . This problem is known to be NP-complete (problem [SP1] in [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]).

Let (C, X, Y, Z) be an instance of 3DM. For i = 1, . . . , , let Mi be the indices of the triples for which the third coordinate corresponds to zi, i.e. Mi represents the set {j ∈ {1, . . . , n} : ∃x ∈ X, y ∈ Y s.t. ej = (x, y, zi) ∈ C}.

Note that (Mi) i∈{1,..., } is a partition of {1, . . . , n}.

We build an instance of the k-division problem as follows. There are n agents A = {1, . . . , n} (one per triple in C) and kn resources partitioned in three blocks BR1, BR2 and

BR3. BR1 = BR X 1 ∪ BR Y 1 with BR X 1 = {r X 1 , . . . , r X } and BR Y 1 = {r Y 1 , . . . , r Y } corresponding to the elements of X and Y , respectively. BR2 = ∪ i=1 BR i 2 where BR i 2 is a set of |Mi| -1 new resources. BR3 consists of (k -1)n -dummy resources. Observe that |BR1| = 2 , |BR2| = i=1 |BR i 2 | = n -.
Hence, the instance has kn resources, as desired. We suppose that E is complete, and for any agent i ∈ A, we set: for r

X j ∈ BR X 1 , ui(r X j ) = υ2 if ei = (xj, y, z) ∈ C
for some y ∈ Y , z ∈ Z, and ui(r X j ) = υ1 otherwise; for r Y j ∈ BR Y 1 , ui(r Y j ) = υ2 if ei = (x, yj, z) ∈ C for some x ∈ X, z ∈ Z, and ui(r Y j ) = υ1 otherwise; for r ∈ BR2, ui(r) = υ3 if r ∈ BR j 2 and i ∈ Mj for some j ∈ {1, . . . , }, and ui(r) = υ1 otherwise; for r ∈ BR3, ui(r) = υ1. Thus, the utilities can only take values in {υ1, υ2, υ3} as desired.

We claim that there exists a subset J ⊆ {1, . . . , n} with |J| = such that MJ = {ej : j ∈ J} is a perfect matching if and only if there is an allocation R = (R1, . . . , Rn) such that |Ri| = k and ui(Ri) ≥ min{2υ2, υ1 + υ3} + (k -2)υ1 for each i = 1, . . . , n.

Suppose there is J ⊆ {1, . . . , n} with|J| = such that MJ = {ej : j ∈ J} is a perfect matching (thus (C, X, Y, Z) is a yes-instance of 3DM). We build R = (R1, . . . , Rn) as follows. For j ∈ J, Rj contains resources r X p and r Y q such that ej = (xp, yq, z) for some z ∈ Z and k -2 dummy resources. The set Rj of resources assigned to an agent j / ∈ J contains one resource from BR i 2 where i is such that j ∈ Mi and k -1 resources from BR3. It is not hard to check that this assignment is feasible and that each agent takes either two resources that she values υ2 plus k -2 resources valued υ1, or one resource valued υ3 plus k -1 resources valued υ1. Thus, u(R) = min{2υ2, υ1 + υ3} + (k -2)υ1.

Conversely, consider an allocation R = (R1, . . . , Rn) with |Ri| = k, i = 1, . . . , n, such that u(R) ≥ min{2υ2, υ1 + υ3} + (k-2)υ1. Observe that R must allocate at most k-1 dummy resources per agent, since they are valued υ1. Similarly, if R allocates exactly k -1 dummy resources to an agent i, then agent i must have utility υ3 for her remaining resource. Since the only resources valued υ3 are the resources in BR2, it follows that at most |BR2| = n -agents receive k -1 dummy resources. Moreover, note that R must allocate to an agent i at least k -2 dummy resources. Indeed, since there are |BR3| = (k -1)n -dummy resources, if an agent receives at most k-3 of these resources, it must be necessary either to assign k -1 dummy resources to more than nagents, or to assign k dummy resources to some agent, in both cases a contradiction. A similar contradiction is reached if the number of agents that can receive k-2 dummy resources is less than .

Thus, we showed that there are at least agents with k -2 dummy resources but at most n -agents with k -1 of these resources and no agent with a different number of these resources. Hence there exists a set J ⊂ {1, . . . , n}, with |J| = , such that Ri for i / ∈ J contains k -1 resources that she values υ1 and one resource valued υ3. For i ∈ J, Ri contains k -2 resources valued υ1 and two resources valued at least υ2. Since all resources in BR2 are used by the agents not in J, each agent i ∈ J must take her two non-dummy resources from BR1. Let us say that these resources are r X p and r Y q . Since agent i values both of them υ2, it must be the case that ei = (xp, yq, z) for some z ∈ Z.

We finally show that given two triples e j = (x , y , z ) and e j = (x , y , z ) with j , j ∈ J, j = j , it must be z = z . For the sake of contradiction, suppose z = z for some pair of triples. Then, there exists zj ∈ Z such that zj / ∈ ZJ , where ZJ = {z ∈ Z : ∃x ∈ X, y ∈ Y, j ∈ J s.t. ej = (x, y, z)}. Now let us focus on the set of agents in Mj : for all but one of these agents we can assign a resource from BR j 2 . For the remaining agent, no resource from BR j 2 is available (since

|BR j 2 | = |Mj | -1)
, and this is the case also for the resources of BR1 (by assumption). However, this agent has value υ1 for any other resource. Then, her utility must be kυ1, a contradiction.

Thus, MJ = {ej : j ∈ J} is a perfect matching and then (C, X, Y, Z) is a yes-instance of 3DM. This proves that it is NP-hard to distinguish if u(R) ≥ min{2υ2, υ1 + υ3} + (k -2)υ1 or u(R) < min{2υ2, υ1 + υ3} + (k -2)υ1. By observing that the last condition is equivalent to u(R) ≤ υ2 +(k-1)υ1, the desired inapproximability result is obtained.

Observe that the approximation ratio tends, as expected, to one when υ1 is close to υ2 or when υ2 is close to υ3. On the other hand, the above approximation ratio is always lowerbounded by 1 2 , with the worst-case obtained when υ1 = 0 and 2υ2 ≤ υ3. Hence, we have the following corollary.

Corollary 1. For any k ≥ 2 and ε > 0, unless P=NP, there is no polynomial time algorithm that 1 2 +ε-approximates the k-division problem, even if E is complete and there are only three distinct utility values.

More accurate approximation with three utilities. Theorem 4 highlights that the approximation algorithm given in Theorem 3 may not be tight even if the agents' utilities can only take three values. For this reason, we propose a new algorithm that exploits this restriction to possibly achieve better approximations. This algorithm repeatedly uses the existence of a polynomial algorithm for the k-division problem when the agents' utilities can only take two values. Theorem 5. For any k ≥ 2, there exists a polynomial time algorithm that ρ-approximates to the k-division prob-lem when the agents' utilities assume only values υ1, υ2 and υ3, with 0 ≤ υ1 < υ2 < υ3, where

ρ = υ 2 +(k-1)υ 1 kυ 2 , if 2υ2 ≤ υ1 + υ3; υ 1 +(k-1)υ 2 υ 1 +(k-1)υ 3 , otherwise.
Proof. Consider an instance I = (A, R, E, (u)i∈A) of the problem. Our approximation algorithm mainly merges two consecutive utilities in different ways and solves the resulting instances using the algorithm described in Theorem 2.

Specifically, we build three instances of the k-division problem in which the agents' utilities just take two values, namely I = (A, R, E, (u )i∈A), I = (A, R, E, (u )i∈A) and I = (A, R, E , (u)i∈A), where u , u and E are defined as follows: concerning u , for any agent i ∈ A and any resource r ∈ R such that (i, r) ∈ E, we set u i (r) = υ1 if ui(r) = υ1 and u i (r) = υ2 otherwise; as for u , for any agent i ∈ A and any resource r ∈ R such that (i, r) ∈ E, we set u i (r) = υ3 if ui(r) = υ3 and u i (r) = υ1 otherwise; finally, we have that E discards for any agent the resources she values υ1, i.e., E = {(i, r) ∈ E : ui(r) > υ1}. Note that instance I may not contain any feasible solution (i.e., some agent may receive less than k resources) but we have previously highlighted that this case can be checked in polynomial time. Our algorithm is then the following: Now we evaluate the approximation ratio of this algorithm. Let R * = (R * 1 , . . . , R * n ) be an optimal allocation for instance I with value opt. The utility of agent i in the assignment R * is ui(R * i ) = aiυ1 + biυ2 + ciυ3, for ai, bi, ci ∈ {0, . . . , k} such that ai + bi + ci = k. Observe that if opt = kυ1, then any feasible solution is optimal and so will be also the solution returned by Algorithm 1. Thus, from now on we consider opt > kυ1.

Let us first focus on the case 2υ2 ≤ υ1 + υ3. If opt ≥ (k -1)υ3 + υ2, then we must have ai = 0 for each agent i ∈ A. Hence, R * is feasible and optimal also for instance I . Thus, Algorithm 1 finds the optimal solution.

Since 2υ2 ≤ υ1 + υ3, the largest value that opt can take below

(k -1)υ3 +υ2 is opt = (k -1)υ3 +υ1. If 2υ2 = υ1 +υ3 (ie, 2υ2 < υ1 + υ3) we must have ci ≥ k -1 for each agent i ∈ A. Indeed, opt = (k -1)υ3 + υ1 > (k -2)υ3 + 2υ2. Hence, if by contradiction c i ≤ k -2 for some agent i ∈ A, then opt ≤ u i (R * ) ≤ (k -2)υ3 + 2υ2. Thus, u i (R * i ) = ciυ3 + (k -ci)υ1 = ci(υ3 -υ1) + kυ1 ≥ (k -1)υ3 + υ1 = opt for each i ∈ A. Then u (R * ) = u(R *
) and thus the optimal assignment for I returned by our algorithm is exactly R * .

Thus, we are interested in the behavior of our algorithm when kυ1 < opt ≤ (k -2)υ3 + 2υ2, that is equivalent to say that opt ∈ [(k -1)υ1 + υ2, (k -2)υ3 + 2υ2]. We split this interval in the subintervals S1 = [(k -1)υ1 + υ2, kυ2] and Sj = [(j -1)υ3 + (k + 1 -j)υ1, (j -1)υ3 + (k + 1 -j)υ2] for j = 2, . . . , k -1. Note that the subintervals Sj are not decreasing. They may not be disjoint, but opt ∈ ∪ k-1 j=1 Sj, since υ3 + (k -1)υ1 is less than or equal to the smallest value above kυ2 and, similarly, jυ3 + (k -j)υ1 is less than or equal to the smallest value above (j -1)υ3 + (k + 1 -j)υ2 for j = 2, . . . , k -2. Now, suppose that opt ∈ S1. Consider the solution R produced on instance I . Since u i (r) ≤ ui(r), we have u(R ) ≥ u (R ). Since u (R ) is optimal for I , then u (R ) ≥ u (R * ). Now, we evaluate R * in instance I . Since opt ≥ (k -1)υ1 + υ2, we have that ai ≤ k -1 for any i ∈ A. Thus,

u i (R * i ) = aiυ1 + (k -ai)υ2 = kυ1 + (k -ai)(υ2 -υ1) ≥ (k -1)υ1 + υ2 for any i ∈ A. Thus, u (R * ) ≥ (k -1)υ1 + υ2.
From opt ≤ kυ2, we then get

u(R ) ≥ u (R ) ≥ u (R * ) ≥ (k -1)υ1 + υ2 ≥ (k -1)υ1 + υ2 kυ2 opt.
Then our algorithm (k-1)υ 1 +υ 2 kυ 2

-approximates the optimum. Suppose instead that opt ∈ Sj for some j = 2, . . . , k -1 and opt / ∈ Sj-1 (this is possible since the sets Sj are not decreasing). Consider the solution R produced on the instance I . Since u i (r) ≤ ui(r), we deduce that u(R ) ≥ u (R ). By construction, u (R ) is optimal for I , thus u (R ) ≥ u (R * ). Now, we evaluate solution R * in the instance I . Since opt ≥ (j -1)υ3 + (k + 1 -j)υ1 (by opt ∈ Sj) and opt > (j -2)υ3 + (k + 2 -j)υ2 (by opt / ∈ Sj-1), we deduce that ci ≥ j -1 for any agent i ∈ A. Hence,

u i (R * i ) = (k-ci)υ1 +ciυ3 = ci(υ3 -υ1)+kυ1 ≥ (j -1)υ3 +(k+1-j)υ1 for every i ∈ A. Thus, u (R * ) ≥ (j -1)υ3 + (k + 1 -j)υ1. Then, since opt ≤ (j -1)υ3 + (k + 1 -j)υ2, we have u(R ) ≥ u (R ) ≥ u (R * ) ≥ (j -1)υ3 + (k + 1 -j)υ1 ≥ (j -1)υ3 + (k + 1 -j)υ1 (j -1)υ3 + (k + 1 -j)υ2 opt ≥ (j -1)υ2 + (k + 1 -j)υ1 kυ2 opt,
where the last inequality follows from the mapping being increasing in υ3 and υ3 > υ2. Now, since (j -1)υ2 ≥ υ2 + (j -2)υ1 (since j ≥ 2) we obtain that our algorithm returns at least an (k-1)υ 1 +υ 2 kυ 2 -approximation to the optimum. Now consider the case 2υ2 > υ1 + υ3. If opt ≥ (k -2)υ3 + 2υ2, then we must have ai = 0 for each agent i ∈ A. Hence, R * is feasible and optimal also for instance I . Thus, Algorithm 1 finds the optimal solution.

As a consequence, we are interested in the behavior of our algorithm when kυ1 < opt

< (k -2)υ3 + 2υ2, that is equivalent to say that opt ∈ [(k -1)υ1 + υ2, (k -1)υ3 + υ1] because (k -2)υ3 +2υ2 > (k -1)υ3 +υ1 > (k -2)υ3 +υ2 +υ1.
We split this interval in the subintervals Sj = [(k -j)υ1 + jυ2, (k -j)υ1 + jυ3] for j = 1, . . . , k -1. As previously, the sets Sj are not decreasing and opt ∈ ∪ k-1 j=1 Sj. Suppose that opt ∈ Sj for some j = 1, . . . , k-1 and opt / ∈ Sj-1 (this is possible since the sets Sj are not decreasing). Consider solution R produced on instance I . Since u i (r) ≤ ui(r), we deduce that u(R ) ≥ u (R ). By construction, u (R ) is optimal for I , thus u (R ) ≥ u (R * ). Now, we evaluate solution R * in the instance I . Since opt ≥ (kj)υ1 + jυ2 (by opt ∈ Sj) and opt > (k + 1 -j)υ1 + (j -1)υ3 (by opt / ∈ Sj-1 if j > 1 and by hypothesis otherwise), we deduce that ai ≤ k-j for each agent i ∈ A. Hence,

u i (R * i ) = aiυ1 + (k -ai)υ2 = kυ1 + (k -ai)(υ2 -υ1) ≥ (k -j)υ1 + jυ1
for any i ∈ A. Thus, u (R * ) ≥ (k -j)υ1 + jυ2. Then, since 3υ2. Hence, R has to allocate to agent i each resource in BR i 3 except a resource r that she values υ2. Note that this resource r is valued υ1 by any other agent. Thus, any agent receiving this resource should compensate it with a resource that she values υ3. It follows then, by a pigeon-hole-principle argument, that there will be an agent j unable to compensate and, consequently, uj(Rj) < v, a contradiction.

We say that an approximation algorithm for k-division is a meta-search algorithm if: (i) a subset V of size polynomial in the input consisting of possible allocation values is considered; (ii) for each v ∈ V one tests if a feasible allocation of value at least v exists; (iii) the allocation corresponding to the largest v for which the test is successful is returned. Note that the two approximation algorithms presented in this work are meta-search algorithms. This is immediate for the algorithm given in Theorem 3; for Algorithm 1, any test corresponds to running the algorithm described in Theorem 2 and evaluating the returned solution for I.

Then, we obtain the following corollary to Theorem 6.

Corollary 2. For any k ≥ 2 and ε > 0, unless P=NP, there is no meta-search algorithm that (ρ + ε)-approximates the k-division problem with three distinct utilities, where ρ = υ2 + (k -1)υ1 kυ2 .

Proof. A meta-search algorithm with a better approximation ratio contradicts Theorem 6. Indeed, there must exist υ2 + (k -1)υ1 < v ≤ kυ2 for which it is able to check if there exists a feasible allocation of cost at least v. Otherwise, given an instance of k-division with opt = kυ2, the algorithm can only return an instance with cost υ2 + (k -1)υ1, failing to improve the approximation ratio. Thus, Algorithm 1 is optimal in its class of algorithms, that is it gives the best possible approximation ratio among the ones allowed for a meta-search algorithm. But can we do better? Which kind of algorithms we should consider for trying to improve the approximation ratio?

Note that Theorem 6 states that no algorithm is able to decide if there exists an allocation of value v for some 2υ2 + (k -2)υ1 ≤ v ≤ kυ2 for any input. However, there may exist a polynomial algorithm A that takes this decision for only many input. For example, an algorithm A may be able to decide if there exists an allocation of value v when the input is an instance whose optimal value is greater than v but unable to decide this for any instance whose optimal value is v. Such an algorithm would allow to improve the approximation ratio to min υ 2 +(k-1)υ 1 v , v kυ 2 > 1/k. So the question becomes: does Algorithm A exist? Unfortunately, the answer to this question appears related to the long standing gap between 1 2 and 1 m-n+1 regarding the approximation ratio of the MaxMin Allocation problem for sufficiently small values of m. Indeed, the latter problem can be easily reduced to k-division for k = m -n + 1 by adding sufficiently many dummy resources. Thus, by showing that A does not exist it follows that, even with only three utility values, MaxMin Allocation cannot be approximated within a better ratio than υ 2 +(m-n)υ 1 (m-n+1)υ 2 ≥ 1 m-n+1 , matching the best known approximation algorithm for this problem. On the other side, if Algorithm A exists, this will shade a new and probably definitive light on the MaxMin Allocation problem, since also for this problem any known algorithm is a meta-search algorithm. Thus, this apparently simpler problem, namely k-division with only three utility values, may catch the entire difficulty in closing this longstanding problem about MaxMin Allocation.

CONCLUSION & OPEN PROBLEMS

The analysis of the k-division problem provided us with several insights in the problem of MaxMin Allocation.

First, we devised an interesting connection between the maxmin objective and matroid theory. We showed how this connection allows to design exact or approximate algorithms for the k-division problem. It would be interesting to understand at which extent matroids can help in the agenda of tightening the approximation ratios for these problems.

Then, we showed that the difficulty in closing the approximability gap of MaxMin Allocation may be caught by an apparently simpler problem. Can this simplicity help us to close or at least to tighten this gap?

We also take a step in this direction, by ruling out the possibility to improve the approximation ratio through a meta-search algorithm. Thus, it is natural to ask whether there exists an algorithm that does not belong to this class.

Algorithm 1

 1 Approximation algorithm for 3 utilities Require: A, R, E, (u)i∈A with |A| = n and |R| = kn. 1: if I admits feasible solutions then 2: Solve I and let R be the returned solution. 3: end if 4: Solve I and evaluate the returned solution R in I. 5: Solve I and evaluate the returned solution R in I. 6: return The best solution among R , R and R .

opt ≤ (k -j)υ1 + jυ3, we have

where the last inequality follows from the mapping being decreasing in j and j ≤ k -1. That is, our algorithm υ 1 +(k-1)υ 2 υ 1 +(k-1)υ 3 -approximates the optimum. Let us give an example of how the algorithm works.

Example 2. Consider the instance of the problem described in Example 1. This instance uses exactly three distinct utilities: 0, 1 and 2.

By applying Algorithm 1 to this instance, we first observe that there is no feasible solution in I , i.e. no solution in which each agent receives exactly two resources that she values 1 or 2. Indeed, there are only 2 +(n-) = n+ < 2n of these resources.

As for I , we observe that allocation

2 + 1, . . . , n has value u (R ) = 1 and it is optimal for I . Indeed, as stated above, for any feasible allocation R = (Ri)i=1,...,n there is at least one agent i who gets at least one resource valued 0. Hence, u (R) ≤ u (R ). Thus, allocation R can be returned at step 4 of Algorithm 1 and its value in

Let us finally consider instance I . We observe that al-

) for i = n 2 + 1, . . . , n has value u (R ) = 0 and it is optimal for I . Indeed, for each feasible allocation R = (Ri)i=1,...,n there is at least one agent i who does not get any resource valued 2 (e.g., each agent j = 1, . . . , n 2 values a resource at most 1). Thus, for any allocation there is at least one agent i such that u i (Ri) = 0. and, hence, u (R) = 0 = u (R ). Then, allocation R , whose valuation in I is u(R ) = 0, can be returned at step 5 of Algorithm 1.

Since our algorithm returns the allocation that has the best valuation in I among R , R and, if defined, R , in our example it will return R of value 1, that is an

At this point some remarks should be made. Observe that when k = 2, the approximation ratio of Algorithm 1 matches the bounds given in Theorem 4. For any k ≥ 2 and 2υ2 ≤ υ1 +υ3, the approximation ratio is larger than 1 k , with the worst case achieved when υ1 = 0. Note that 1/k is the approximation ratio given in Theorem 3. On the other side, if 2υ2 > υ1 + υ3, then υ 1 +(k-1)υ 2 υ 1 +(k-1)υ 3 is strictly larger than 1 2 . This is noteworthy because Corollary 1 states that it is not possible to provide such a guarantee for all instances.

It is also interesting to note that the approximation ratio of Algorithm 1 tends to 1 when υ2 is close to υ1 or to υ3. This is expected, since in this case we are close to the two-utility case which can be solved in polynomial time (Theorem 2).

However, it may look surprising that the approximation ratio of Algorithm 1 does not depend on υ3 when 2υ2 ≤ υ1 + υ3. Similarly, we have that in the opposite case, the approximation ratio in practice depends only on υ2 and υ3. However, these observations can be easily explained: if 2υ2 ≤ υ1 + υ3, then v3 -v2 ≥ v2 -v1, i.e. υ2 cannot be close to υ3 more than how much it is close to v1. Thus it is the distance between υ1 and υ2 that measures the gap from having only two utility values. Similarly, if 2υ2 > υ1 + υ3, then v3 -v2 < v2 -v1, so now the gap from having only two utility values should be measured by the distance between υ2 and υ3. Note that in the lower bound given in Theorem 4 we observe the same dichotomy: if 2υ2 ≤ υ1 + υ3, then the bound does not depend on υ3, whereas if 2υ2 > υ1 +υ3, then the bound depends in practice only on υ2 and υ3.

We also observe that the idea exploited in Algorithm 1, that is merging two utilities and solve the corresponding "rounded" instances, can be extended to the case of more than three different utilities (at the cost of making the analysis of the algorithm more complex). However we skip this extension since the three-utility case has already interesting connections with long-standing problems in the area.

Closing the gap? The MaxMin Allocation obstacle.

Unfortunately, the algorithm described in Theorem 5 does not match the inapproximability result given in Theorem 4. Indeed, if for 2υ2 > υ1 + υ3 the upper and the lower bounds almost match, for the opposite case they diverge since the lower bound is never worse than one half, whereas the upper bound tends to 1 k . For this reason, we assume from now on that 2υ2 ≤ υ1 + υ3 and we wonder if we can improve the corresponding approximation ratio. The next theorem suggests that this may not be possible. Theorem 6. For any k ≥ 2 and any v satisfying 2υ2 + (k -2)υ1 ≤ v ≤ kυ2, unless P=NP, there is no polynomial time algorithm that can decide if the k-division problem with three distinct utility values admits a feasible allocation R such that u(R) ≥ v.

Proof. We assume without loss of generality that v = aυ1 + bυ2 + cυ3 for a, b, c ∈ {0, . . . , k} such that a + b + c = k. We distinguish two cases depending on whether v = 2υ2 + L or not, where L = aLυ1 + bLυ2 + cLυ3 for aL, bL, cL ∈ {0, . . . , k -2} such that aL + bL + cL = k -2.

If v = 2υ2 + L, then we apply exactly the same reduction as in the proof of Theorem 4, except that now we partition the set BR3 of dummy items in n + 1 subsets BR i 3 , for i = 0, . . . , n. Each set BR i 3 for i = 1, . . . , n contains bL + cL resources, whereas the set BR 0 3 contains any remaining resource. Moreover, for each agent i ∈ A we set utilities for resources in BR i 3 so that for bL of these resources we have ui(r) = υ2 and for cL of these resources we have ui(r) = υ3. The utility of agent i for any other resource remains the same as stated in the reduction of Theorem 4.

By mimicking the proof of Theorem 4, we then have that an instance (C, X, Y, Z) of 3DM has a perfect matching if and only if the instance the k-division problem with three distinct utility values resulting from the reduction admits a feasible allocation R such that u(R) ≥ v.

If v cannot be written as 2υ2 + L, then we let v be the smallest value above v such that v = 2υ2 + L . We now consider exactly the same reduction as above with v in place of v. This proves that an instance (C, X, Y, Z) of 3DM has a perfect matching if and only if the instance the k-division problem with three distinct utility values resulting from the reduction admits a feasible allocation R with u(R) ≥ v .

Therefore the theorem follows by showing that u(R) ≥ v implies u(R) ≥ v . Indeed, suppose for the sake of contradiction that u(R) ≥ v but there is an agent i such that ui(Ri) = v. It is not hard to check that v = v -2υ1 -υ3 +


F Al

B Maury

F Al Reda

Interpretation of Finite Volume discretization schemes for the Fokker Planck equation as gradient flows for the discrete Wasserstein distance

Keywords: Gradient flows, Wasserstein distance, Finites Volumes discretization, Fokker-Planck equation, Heat equation, Resistive Network, Markov Kernel AMS Subject Classification: 60J60, 94C15, 35K05, 35K08, 65N08, 60J27, 60J28

This paper establishes a link between some space discretization strategies of the Finite Volume type for the Fokker-Planck equation in general meshes (Voronoï tesselations) and gradient flows on the underlying networks of cells, in the framework of discrete Wasserstein distances on graphs recently proposed by Maas [6].

Introduction

We aim here at identifying gradient flow structures in some space-discretization schemes of the Fokker-Planck equation on general meshes, in the spirit of the approaches proposed recently in [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF][START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF] for cartesian discretizations. Since the core of the paper consists in building links between macroscopic notions / properties and their discrete counterparts, in a context where two reference measures are present (uniform Lebesgue measure and stationary measure associated to an attractive potential), let us start by fixing some principles in terms of notation. Probability measures will be denoted by the letter p (we shall use the same letter to denote their density with respect to the underlying Lebesgue measure, or its discrete counterpart), stationary measures (with respect to some evolution process) by π, and relative densities with respect to π by ρ. All discrete notions will be singled out by a tilda sign, e.g. p, π, etc ... The space variable will be denoted by r, while x and y will be used to denote discrete vertices.

Since the seminal work of Jordan, Kinderlehrer and Otto [START_REF] Jordan | The variational formulation of the Fokker-Planck equation[END_REF] in 1998, it is known that the Fokker-Planck (FP) equation in a domain Ω:

∂ t p -∆p -∇ • (p∇Φ) = 0,
with appropriate no-flux boundary conditions, can be interpreted in the Wasserstein space as the gradient flow for

H(p) = Ω p log p π dr   = Ω ρ log (ρ) dπ with ρ = p/π   ,
that is the relative entropy with respect to the stationary measure π = e -Φ , up to a normalization constant. This property is schematized in the diagram below (see Fig. 1, blocks A -B -C, on the top), and we refer the reader to [START_REF] Ambrosio | Gradient flows-In Metric Spaces and in the Space of Probability Measures[END_REF][START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF] for a thorough description of the underlying theory. At the discrete level, a similar framework has been proposed in [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF][START_REF] Mielke | A gradient structure for reaction-diffusion systems and for energy-driftdiffusion systems[END_REF]. The euclidean domain is replaced by a network N , defined by its (finite) set of vertices V and a Markovian kernel (K(x, y)) x,y∈V , with K(x, y) ≥ 0 , y∈V K(x, y) = 1 ∀x ∈ V.

The stationary measure is denoted by π, it verifies π = t K π. It is unique as soon as K is irreducible, i.e. ∀ x, y ∈ V there exists a path (x 0 = x, x 1 , x 2 , . . . , x m = y) such that K(x, x 1 ) × K(x 1 , x 2 ) × . . . × K(x m-1 , y) > 0, and then π(x) > 0 for all x ∈ V . We say that K is reversible if π(x)K(x, y) = K(y, x) π(y) for all x, y in V (detailed balance equation). The discrete counterpart of the FP equation is the heat flow equation

∂ t ρ + (I -K) ρ = 0, ( 1
)
where ρ is the density of a probability measure p on V with respect to π. Note that the straight discrete counterpart of FP equation would be an equation of the measure p itself, with K replaced by t K, and p(x) = 1, but we shall follow [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF] in favoring densities with respect to π, i.e. densities ρ verifying ρ(x) π(x) = 1. It has been established in [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF] that [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF], for an appropriate metric W 2 which is the discrete counterpart of the standard Wasserstein distance, is a gradient flow of the discrete relative entropy

H( ρ) = x∈V ρ(x) log( ρ(x)) π(x) (2)
Fokker Planck equation

Gradient flow

Gradient flow

Wasserstein dist. in P(Ω)

W2(p0, p1) 2 = with ∂tpt + ∇ • (pt∇ψt) = 0. inf pt,ψt 1 0 Ω |∇ψt| 2 dpt

Relative entropy

Relative entropy with respect to with respect to the stationary measure the stationary measure

dρ/dt + (I -K)ρ = 0 dp/dt + (I -t K)p = 0 ∂tp -∆p -∇ • (p∇Φ) = 0 or ∂tρ -1 π ∇ • (π∇ρ) = 0 with t K π = π, ρ = p/π. with π = e -Φ , ρ = p/π. H(p) = p log(p/π) dx H(ρ) = x∈V ρ(x) log(ρ(x))π(x). Gromov Hausdorff convergence convergence convergence Space disc. quadrature π = e -Φ .

A B C

Fig. 1. Continuous setting versus discrete setting with respect to the Wasserstein-like metric W 2 (see Section 2 for detailed definitions).This discrete setting is also schematized in Fig. 1 (blocks à -B -C, on the bottom). Although it was not the original purpose in [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF], a connection can be made between the two settings by means of discretization strategies. As detailed in the next section, an euclidean domain Ω can be partitionned into cells (e.g. Voronoï cells associated to a collection of points in the domain, see Fig. 2). Now consider the network associated to those cells (one may consider that the vertices are the centroids of the cells). To any measure µ on Ω one can associate a discrete measure that is, for each vertex associated to cell K, the measure µ(K). As detailed in [START_REF] Gigli | Gromov-Hausdorff convergence of discrete transportation metrics[END_REF], a link can be made between the Wasserstein distance on the euclidean domain and the discrete Wasserstein distance on the network, at least in the case of a regular decomposition (cartesian grid). This link will be described more precisely in the next section, it is indicated by the arrow 2 in Fig. 1 that relates blocks B and B. Besides, integrating any function of the density at the continuous level has a discrete counterpart (we are especially interested in entropy-like functionals), it consists in summing up the corresponding values for the discrete densities built as described above. This approach can be seen as a quadrature formula to compute the approximation of an integral, for which convergence properties can be expected as the cell decomposition is refined. It is indicated by the arrow 3 in Fig. 1 that relates blocks C and C.

The core of the present article is an attempt toward closing the diagram by expliciting the link between blocks A and à (arrow 1). More precisely, we aim at showing that, in the context of Finite Volume methods, some space discretization strategies of the FP equation lead to Ordinary Differential Equation that are consistent with the gradient flow structure on the underlying network. Note that this interpretation of Finite Volume discretization schemes as gradient flows has already been addressed in two recent papers. In [START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF], the authors use this gradient flow structure to characterize the long time behavior of discrete solutions to a fourth order equation. In [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF], a finite volume scheme is studied in the discrete Wasserstein setting, and a new type of convergence proof is proposed in this context. In both cited papers, the space discretization is regular (i.e. 1-dimensional for the second one, and d-dimensional with a cartesian grid for the first one). We aim here at showing that an extension to non regular space-discretization is not out of reach. In particular, we show that Finite Volume discretization strategies for very general meshes lead to problems that can be interpreted as gradient flows for a discrete Wasserstein-like metric, with a functional that can be seen as an approximation of its continuous counterpart. Let us make it clear, though, that no discrete-to-continuous convergence result is known for the Wasserstein distance for non regular meshes.

The outline of the paper is as follows. In Section 2 we recall the main obtained result on the FP equation and its gradient flow formulation, we define the Wasserstein-like distance of Maas and state his first result in terms of gradient flows using this distance. Then we describe the Gromov-Hausdorff convergence in the special case of the d-dimensional torus and show the convergence of the discrete relative entropy H to its continuous counterpart H. Section 3 proposes a Finite Volume discretization of the FP equation in space and the analysis of the Markov chain deduced from this discretization and seen as an ODE in time. We show that this ODE is the gradient flow of the discrete relative entropy H and we finalize the paper with some conclusives remarks and perspectives.

N Ω Fig. 2. From the Euclidean domain to the associated network

Preliminaries

We describe in this section with some details the constitutives blocks of the diagram presented in Fig. 1.

Blocks A-B-C: Fokker Planck equation as a gradient flow, continuous setting

Let us first recall some basic facts on the Wassertein space of measures and gradient flows therein (we refer to [START_REF] Villani | Optimal transport, old and new[END_REF][START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF][START_REF] Ambrosio | Gradient flows-In Metric Spaces and in the Space of Probability Measures[END_REF] for a detailed presentation of these considerations). Let Ω be a bounded domain. For any two measures p 0 and p 1 in P(Ω), the (quadratic) Wasserstein distance between them is defined by

W 2 (p 0 , p 1 ) 2 = inf γ∈Π Ω×Ω r ′ -r 2 dγ(r, r ′ ),
where Π is the subset of P(Ω × Ω) for all those γ with marginals p 0 and p 1 , respectively, i.e.

Ω×Ω ϕ(r) dγ(r, r ′ ) = Ω ϕ(r) dp 0 (r) , Ω×Ω ψ(r ′ ) dγ(r, r ′ ) = Ω ψ(r ′ ) dp 0 (r ′ )
for any continuous functions ϕ and ψ.

An alternative formulation has been proposed by Benamou-Brenier [START_REF] Benamou | A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem[END_REF], it consists in writing the squared Wasserstein distance as follows (we consider here a convex domain):

W 2 (p 0 , p 1 ) 2 = inf pt,ψt    1 0 Ω |∇ψ t (r)| 2 p t (r) dx dt    , ( 3
)
where the infimum runs over curves (p t ) t∈[0,1] in P(Ω) that join p 0 and p 1 in the following way (transport of p t by ∇ψ t ):

∂ t p t + ∇ • (p t ∇ψ t ) = 0. (4)
Now we aim at defining a notion of gradient for a functional H that is consistent with the Wasserstein framework. The more appropriate notion is that of Fréchet subdifferential in a Wasserstein sense, that can be defined for a wide class of functionals, with very weak smoothness assumptions (see e.g. [START_REF] Ambrosio | Gradient flows-In Metric Spaces and in the Space of Probability Measures[END_REF]). Since this notion does not have any natural counterpart at the discrete level, we shall focus here on a more restrictive definition of the gradient: Definition 2.1. Let H : P(Ω) → R be a functional. We shall say that H admits a gradient w ∈ L 2 p at p ∈ P(Ω), and then write

grad H(p) = w,
if, for every measure path t → p t defined in a neighborhood of 0 and satisfying:

∂p t ∂t + ∇ • (p t v t ) = 0 , p 0 = p ,
where v t is a L 2 vector field, it holds that d dt H(p t )| t=0 = lim t→0 H(p t ) -H(p 0 ) t = Ω v 0 • w dp.
We may now define the notion of gradient flow in this setting:

Definition 2.2. The probability measure path t → p t is said to be a gradient flow for a functional H if p t verifies (in the distributional sense)

∂ t p t + ∇ • (p t u t ) = 0 , u t = -grad H(p t ) for a.e. t,
where the gradient is defined according to Def. 2.1.

Let us consider the case where H reads

H(p) = Ω f (r) dp(r) + Ω g(p(r)) dr,
where f and g are regular functions. Then the transport velocity u t can be identified as

u t = -∇f -∇ g ′ (p t ) . ( 5
)
Now consider the Fokker-Planck equation on a domain Ω:

     ∂p ∂t -∆p -∇.(p∇Φ) = 0, in Ω ∂p ∂n -p ∂Φ ∂n = 0, on ∂Ω. ( 6
)
and the relative entropy functional:

H(p) = Ω p(r) log p(r) π(r) dr = - Ω log(π(r)) dp(r) + Ω p(r) log(p(r)) dr. ( 7
)
We obtain from ( 5)

u t = -∇f -∇ g ′ (p t ) = ∇π π -∇(1 + log(p t )) = -∇Φ - ∇p t p t ,
which identifies the FP equation ( 6) as a gradient flow in the Wasserstein sense for the relative entropy functional [START_REF] Mielke | A gradient structure for reaction-diffusion systems and for energy-driftdiffusion systems[END_REF]. We refer again to [START_REF] Ambrosio | Gradient flows-In Metric Spaces and in the Space of Probability Measures[END_REF][START_REF] Santambrogio | Optimal transport for applied mathematicians[END_REF] for a thorough presentation of these facts.

Blocks à -B -C: Discrete setting Let V be a finite set.

Definition 2.3. We say that (K(x, y)) x,y∈V is an irreducible and reversible Markov kernel on V × V if K satisfies:

1. K(x, y) ≥ 0 ∀x, y ∈ V , y∈V K(x, y) = 1 ∀x ∈ V.
2. The irreducibility condition: Let (K(x,y)) x,y∈V be as in the definition. We denote by π the unique stationary measure of K, such that

K(x, y) ≥ 0 ∀x, y ∈ V , y∈V K(x, y) = 1 ∀ x ∈ V. 3. The reversibility condition: π(x)K(x, y) = K(y, x) π(y) ∀ x, y ∈ V,
π(x) = y∈V K(y, x) π(y) i.e. π = t K π , π(x) > 0 ∀x ∈ V , x∈V π(x) = 1.
We define the associated set of probability densities on V by

D(V ) = ρ ∈ (R + ) V , x∈V ρ(x) π(x) = 1 .
Following [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF], we define the discrete gradient, the discrete divergence and the two scalar products with respect to a fixed ρ ∈ D(V ) and π resp., as follows:

-Discrete gradient: For a function ψ : V → R, we define its discrete gradient

∇ ψ : V × V → R by ∇ ψ(x, y) = ψ(y) -ψ(x) ∀x, y ∈ V × V.
-Discrete divergence: For a discrete field u :

V ×V → R, we define its discrete divergence ∇ • u : V → R by ( ∇ • u)(x) = 1 2 y∈V ( u(x, y) -u(y, x))K(x, y) ∀x ∈ V.
Note that for an anti-symmetric field u, i.e. u(x, y) =u(y, x), the discrete divergence reads:

( ∇ • u)(x) = y∈V ( u(x, y))K(x, y) ∀x ∈ V.
-Scalar product with respect to π: For ψ, φ : V → R, we define their scalar product with respect to π by

ψ, φ π = x∈V ψ(x) φ(x) π(x).
-Scalar product with respect to ρ: For u, v : V × V → R, we define their scalar product with respect to ρ by u, v ρ = 1 2

x,y∈V u(x, y) v(x, y)K(x, y)θ( ρ(x), ρ(y)) π(x),

where θ(•, •) is defined by ( 9), and we denote by u ρ the associated norm:

u ρ = u, u ρ .
Note that the latter is a discrete counterpart of the norm of a velocity field in L 2 p , with p = ρπ.

We denote by ., . 1 the scalar product with respect to the density ρ = 1 defined by: ρ(x) = 1, ∀x ∈ V . We can easily check that the integration by parts formula holds in the following sense:

∇ ψ, u 1 = -ψ, ∇ • u π .
The definition of the discrete transportation metric is inspired by the Benamou-Brenier formulation, it translates Eq. ( 4) at the discrete level. It is defined as (see [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF][START_REF] Chow | Fokker-Planck equations for a free energy functional or Markov process on a graph[END_REF][START_REF] Mielke | A gradient structure for reaction-diffusion systems and for energy-driftdiffusion systems[END_REF]): Definition 2.4. For ρ 0 , ρ 1 ∈ D(V ) we set:

W 2 ( ρ 0 , ρ 1 ) 2 = inf ρt, ψt    1 2 1 0 x,y∈V ψ t (y) -ψ t (x) 2 K(x, y)θ( ρ t (x), ρ t (y)) π(x) dt   
where the infimum runs over all piecewise C 1 curves ρ t : [0, 1] → D(V ) and all piecewise continuous ψ t : [0, 1] → R V satisfying:

d ρ t dt (x) + y∈V ψ t (y) -ψ t (x) K(x, y)θ( ρ t (x), ρ t (y)) = 0 ∀x ∈ V ( 8
)
where:

θ(α, β) = 1 0 α 1-t β t dt =    β -α log(β) -log(α) , if α = β α, if α = β (9)
is the logarithmic mean of α and β.

Using the definitions of the discrete gradient and the discrete divergence, W 2 can also be formulated as follows (see [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF], Lemma 3.5):

W 2 ( ρ 0 , ρ 1 ) 2 = inf ρt, ψt    1 0 ∇ ψ t 2 ρt dt   
where the infimum runs over all piecewise C 1 curves ( ρ t ) t∈[0,1] joining ρ 0 and ρ 1 in D(V ) according to

d ρ t dt (x) + ∇ • (Θ( ρ t ) • ∇ ψ)(x) = 0, ∀x ∈ V ( 10
)
where Θ( ρ t ) : V × V → R is defined by: Θ( ρ t )(x, y) = θ( ρ t (x), ρ t (y)) and • denotes the entrywise product of two matrices. The Wasserstein gradient of a functional may now be defined following [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF], Prop. 4.2. Definition 2.5. Let H : D(V ) → R be a functional. We shall say that H admits a gradient w ∈ R V ×V at ρ ∈ D(V ), and then write grad H( ρ) = w, if, for any measure path t → ρ t on D(V ) defined in a neighborhood of 0, with

d ρ t dt + ∇ • (Θ( ρ t ) • v t ) = 0 , ρ 0 = ρ, it holds that d dt H( ρ t )| t=0 = w, v 0 ρ .
After computing the gradient of a functional H, we can write its gradient flow equation in D(V ).

Definition 2.6. Let H : D(V ) → R be a functional and grad H be its gradient according to Def (2.5). We define the discrete gradient flow equation of H by:

d ρ dt (x) -∇ • (Θ( ρ) • grad H( ρ))(x) = 0 ∀x ∈ V.
Like in the continuous setting, the gradient (in the previous sense) of a certain class of functionals can be computed explicitly.

Proposition 2.7. Let H be a generalized entropy functional :

H : ρ ∈ D(V ) -→ H( ρ) = x∈V f (x) ρ(x) π(x) + x∈V g( ρ(x)) π(x) ∈ R
where f, g are differentiable function, f, r : (0, 1) → R. Then

grad H( ρ) = ∇f + ∇g ′ • ρ).
Proof. It is a straightforward application of the definitions above

d dt H( ρ t )| t=0 = x∈V (f (x) + g ′ ( ρ t (x))) d ρ t dt (x) π(x)| t=0 = - x∈V (f (x) + g ′ ( ρ t (x))) ∇ • (Θ( ρ t ) • v t )(x) π(x)| t=0 = -f + g ′ • ρ, ∇ • (Θ( ρ) • ṽ0 ) π = ∇(f + g ′ • ρ), Θ( ρ) • ṽ0 1 = ∇f + ∇g ′ • ρ, ṽ0
ρ which concludes the proof.

Heat flow equation as gradient flow of the discrete entropy

Note that the heat flow equation

d ρ dt + (I -K) ρ = 0, ( 11
)
where K = (K(x, y)) x,y is the Markov matrix, can also be written

d ρ dt (x) -∇ • (∇ ρ)(x) = 0 ∀x ∈ V.
We may now identify the heat flow equation with the gradient flow for the relative entropy.

Theorem 2.8. The gradient flow in D(V ) (according to Def (2.6)) of the discrete relative entropy

H( ρ) = x∈V ρ(x) log( ρ(x)) π(x)
is the heat flow equation [START_REF] Gigli | Gromov-Hausdorff convergence of discrete transportation metrics[END_REF].

Proof. For a detailed proof, we refer the reader to [START_REF] Maas | Gradient flows of the relative entropy for finite Markov chains[END_REF], Theorem 1.2. From Proposition 2.7, we have that grad

H( ρ) = ∇(1 + log( ρ)) = ∇(log( ρ))
for g( ρ) = ρ log ρ and f = 0, and the discrete gradient flow equation of H is:

d ρ dt (x) -∇ • (Θ( ρ) • ∇(log( ρ)))(x) = 0 ∀x ∈ V.

Link B -B (arrow 2): Link between continuous and discrete Wasserstein metrics

A first result of convergence of the discrete transportation metric was proven in [START_REF] Gigli | Gromov-Hausdorff convergence of discrete transportation metrics[END_REF] (Theorem 3.15). We consider the space P(T d ) of all the probability measures on the ddimensional torus T d = R d /Z d endowed with the L 2 -Wasserstein metric and the d-dimensional periodic lattice T d n = (Z/nZ) d and endow the space of probability densities D(T d n ) with the renormalised discrete transportation metric W 2,n = W 2 /n √ 2d where the Markov kernel K is the one of a simple random walk (uniform transition probabilities) and whose stationary measure δ is the uniform measure on T d n . In this special case of δ, we can identify probability measures on T d n with their probability densities with respect to δ. So we consider that

P(T d n ) ≡ D(T d n ).
The convergence result is established in the sense of Gromov-Hausdorff that is defined by: Definition 2.9. A sequence of compact metric spaces (X n , d n ) is said to converge in the sense of Gromov-Hausdorff to a compact metric space (X , d), if there exists a sequence of maps f n : X → X n which are: -ǫ n -isometric, i.e., for all x, y ∈ X ,

|d n (f n (x), f n (y)) -d(x, y)| ≤ ǫ n -ǫ n -surjective, i.e., for all x n ∈ X n there exists x ∈ X with d(f n (x), x n ) ≤ ǫ n
for some sequence ǫ n → 0. Now we are ready to state the convergence theorem of the discrete metrics W 2,n : Theorem 2.10. The metric spaces (P(

T d n ), W 2,n ) converge to (P(T d ), W 2 ) in the sense of Gromov-Hausdorff as n → ∞.
Remark 2.11. An informal convergence result can be done for a general stationary measure by discretizing the continuous FP equation with the scheme described in Section 3 and writing the corresponding discrete distance which looks almost like a discretization of the continuous Wasserstein distance.

Link C -C (arrow 3): Quadrature for the entropy functionnal

In order to strenghen the relation between the discrete setting and the continuous one, we are going to show the convergence of the discrete relative entropy to its continuous counterpart ( C -→ C in the Diagram of Fig. 1). We consider a collection of n points V in Ω, and construct a partition (K x ) x of the domain which is relative to V , i.e. each cell K x of the partition contains one point of V (which is x) and:

Ω = x∈V K x , K x ∩ K y = ∅ ∀x, y ∈ V.
Let h be the diameter of the partition K x , i.e. h = max x∈V diam(K x ). For any probability measure p in P(Ω), we define its discrete counterpart by:

p(x) = Kx p(r) dr, ∀x ∈ V, p ∈ P(V ) (12)
and then we define its discrete density by:

ρ(x) = p(x) π(x) , ∀x ∈ V, ρ ∈ D(V ).
Proposition 2.12. Let p, π be two C 1 (Ω) densities with respect to the Lebesgue measure, bounded from below and above, i.e. ∃ m, M > 0 such that 0 < m ≤ p, π ≤ M , and p h , π h be their discrete counterpart defined according to [START_REF] Eymard | The finite volume method[END_REF].

We denote by ρ h the discrete density of p h with respect to π h . Then, the discrete relative entropy:

H h ( ρ h ) = x∈V h ρ h (x) log( ρ h (x)) π h (x)
converges to the continuous relative entropy:

H(p) = Ω p(r) log p(r) π(

r) dr

when h → 0, at the first order in h.

Proof. We substract the continuous and the discrete quantities:

H(p) -H( ρ h ) = x∈V   Kx p(r) log p(r) π(r) dr -p(x) log p(x) π(x)   = x∈V Kx p(r) log p(r) π(r) -log p(x) π(x) dr ≤ x∈V Kx p(r)C p(r) π(r) - p(x) π(x) dr
where C is a Lipchitz constant for log on [ m M , M m ]. Then, by straightforward computations using the boundedness from below and above of the measureswe can bound the substraction by C ′ × h where C ′ is a constant depending on m, M and C.

Discretization of the Fokker-Planck equation

We re-write the Fokker-Planck system by replacing ∇Φ by -∇π/π in the first equation, we get:

∂p ∂t -∇ • ∇p -p ∇π π = 0, or equivalently: ∂p ∂t -∇ • (π∇ p π ) = 0 (13)

Finite volume discretization

Let V be a collection of points in Ω, and let (K x ) x be the associated Voronoi tesselation. We denote by N the dual network of the space discretization (two vertices are connected whenever the corresponding cells are adjacent). Then we discretize in space the FP equation (in its form ( 13)) by a Finite Volume scheme (see e.g. [START_REF] Eymard | The finite volume method[END_REF]). By integrating the equation on K x , we get: (this approximation is inspired from [START_REF] Mielke | Geodesic convexity of the relative entropy in reversible Markov chains[END_REF] and was used in [START_REF] Disser | On gradient structures for Markov chains and the passage to Wasserstein gradient flows[END_REF] for the 1-dimensional case) and we get the final form of the semi-discretized equation:

d p dt (x
d dt p(x) = y∼x |Γ x,y | |x -y| θ( π(x), π(y)) p(y) π(y) - p(x) π(x)
Or equivalently:

d dt p(x) = y∼x |Γ xy | |x -y| θ( π(x), π(y)) p(y) π(y) - y∼x |Γ xy | |x -y| θ( π(x), π(y)) p(x) π(x) (14)
(i) K(x, y) = Q(x, y)/q max ≥ 0 for x = y, K(x, x) = (q maxq x )/q max ≥ 0, and

y∈V K(x, y) = y∼x Q(x, y) q max + q max -q x q max = y∼x Q(x, y) q max + 1 - y∼x Q(x, y) q max = 1.
(ii) K(x, y) = 0 for x ∼ y and the network is strongly connected, we deduce that K is irreducible and then has a unique stationary measure.

(iii) π satisfies the detailed balance equation for all x, y ∈ V :

π(x)K(x, y) = π(x) Q(x, y) q max = π(x) q max |Γ xy |θ( π(x), π(y)) |x -y| π(x) = π(y) q max |Γ xy |θ( π(x), π(y)) |x -y| π(y) = π(y) Q(y, x) q max = π(y)K(y, x)
so K is reversible, and we have:

y∈V π(y)K(y, x) = y∈V π(x)K(x, y) = π(x)
which proves that π is the unique stationary measure of K.

By definition of K, we have that

1 q max Q = (K -I),
so that the solution to (16), that is the space-discretized solution, is the solution to the heat flow equation

d dt ρ + (I -K) ρ = 0,
up to an affine time renormalization. Now recall that the continuous FP equation is the gradient flow in the Wasserstein sense (see Def(2.1)) for the relative entropy [START_REF] Mielke | A gradient structure for reaction-diffusion systems and for energy-driftdiffusion systems[END_REF]. We have the following discrete counterpart of this property for the Finite Volume discretization scheme (16), that is a direct consequence of the previous developments: Proposition 3.2. The space discretized scheme (16) is a gradient flow for the discrete relative entropy (2), up to an affine time renormalization, with respect to the discrete Wasserstein distance W 2 (see Def 2.4).

Conclusives remarks, perspectives

We described in this paper how some space discretization Finite Volume schemes, possibly on unstructured meshes, can be proved to be deeply respectfull of the underlying gradient flow structure. Given a PDE that is the Wasserstein gradient flow of some functionnal, the ODE resulting from space discretization can be identified as a gradient flow for a discrete functionnal that is an approximation of the continuous one, in the Wasserstein space of measures defined on the underlying network, the vertices of which are the finite volume cells. This overall consistency with respect to Wasserstein metric, that is expressed by Fig. 1, can be used to improve the numerical analysis of a scheme, e.g. by charaterizing its long-time behaviour (as in [START_REF] Maas | Long-time behavior of a finite volume discretization for a fourth order diffusion equation[END_REF] in the case of a cartesian mesh). Note that the approach is currently limited to the semi-discretized scheme. Let us add that the considered scheme treats the advection in a diffusive manner, and as such it is intrinsically of the centered type, so that stability issues can be expected. In particular, an Euler Explicit scheme is likely to lead to unconditionnal unstability. Implicit time-stepping may, in the contrary, provide some stability. Note that Implicit Euler time-stepping applied to (16) leads to a problem that is formally very similar to the so-called JKO scheme applied at the discrete level to compute the gradient flow. Implicit schemes are then likely to recover some properties of the JKO one .

Let us finally stress that the diagram of Fig. 1 is not fully realized. Indeed, the arrow 2 between blocks B and B ′ , which expresses a link between the Wasserstein distance in a domain, and the discrete Wasserstein distance on the network obtained by space discretization, is not covered by a full theory. The only known convergence results ( [START_REF] Gigli | Gromov-Hausdorff convergence of discrete transportation metrics[END_REF]) concern cartesian grids, in the case without potential. In the presence of a non-constant potential, the framework that has been presented may appear puzzling, because the discrete Wasserstein distance involves the stationnary measure (non uniform in general), which depends on the potential Φ, whereas its continuous counterpart pertains to the flat domain, and therefore does not depend on Φ. This apparent paradox is due to the fact that, at the discrete level, the distance W 2 is defined for densities with respect to the stationary measure π. Comparing both distances would amount to consider two probabilties p 0 and p 1 , compute their discrete counterparts p 0 and p 1 , together with π, then ρ 0 = p 0 / π, ρ 1 = p 1 / π, and finally estimate W 2 ( ρ 0 , ρ 1 ), and check that the latter converges to W 2 (p 0 , p 1 ) when the discretization is refined. Although not covered by any theoretical result, and in spite of the fact that W 2 "sees" the measure π, while W 2 does not, such a property can be expected, because π is involved twice in the discretization process : firstly by computation of ρ from p, and then, in a hidden way, through the definition of W 2 . One can check in very simple situations that both effect tend to compensate each other, i.e. the dependence of W 2 ( ρ 0 , ρ 1 ) upon π asymptotically vanishes. It can also be seen in the very definition of the distance itself: each time π(x) is involved, it is multiplied by a quantity of the type θ( ρ(x), ρ(y)), where x and y are connected. In the context of Finite Volume schemes, when the discretization is refined, x and y get closer, so that this quantity is asymptotically close to ρ(x), and finally the real dependence is upon p(x), which does no longer depend on the stationnary measure. As for non cartesian meshes, the analogy that we established advocate for a convergence of the discrete Wasserstein metric toward the continuous one, but it remains to be rigorously proven.

Fig. 3 .

 3 Fig. 3. Voronoi cells with the used notations

  )is the outward normal to K x , Γ xy = K x ∩ K y , n xy = n x | Γxy and y ∼ x means that y is a neighbor of x, y = x.

			∂Kx	π∇	p π	n x dσ =	d p dt	(x) -	Γxy y∼x	π∇	p π	n xy dσ = 0
	where n x We approximate
	Γxy	π∇	p π	n xy dσ by	|Γ xy | |x -y|	θ( π(x), π(y))	p(y) π(y)	-	p(x) π(x)

Acknowledgment:

The authors would like to thank F. Santambrogio for interesting discussions and suggestions. Both authors are partially supported by ANR Project Isotace (ANR-12-MONU-0013).

which can be seen as an evolution equation on the network N .

Semi-discretized equation written with probability densities:

An equivalent semi-discretized equation of ( 14) is written with the probability densities ρ with respect to π, i.e. ρ(x) = p(x) π(x):

Now, equation ( 15) can be written

with

on the network N . Equation ( 16) is not exactly of the heat flow type [START_REF] Gigli | Gromov-Hausdorff convergence of discrete transportation metrics[END_REF], since Q is not of the form K -I, where K would be a stochastic matrix. Yet, as pointed out in [START_REF] Erbar | Gradient flow structures for discrete porous medium equations[END_REF], a connection can be made between the two settings: For a matrix Q as above, we set q x = y∼x Q(x, y) and q max = max x q x .

We then define the matrix K as follows:

Proposition 3.1. The matrix K resulting from the space discretization of the FP equation (13) as described above is an irreducible and reversible Markov Kernel that admits π as stationary measure.

Proof. The matrix K has the following properties: