Anna Bogomolnaia

Hervé Moulin

Haris Aziz

Steve Brams

Eric Budish

Ariel Procaccia

Richard Stong

Guarantees in Fair Division: general or monotone preferences

To divide a "manna" Ω of private items (commodities, workloads, land, time intervals) between n agents, the worst case measure of fairness is the welfare guaranteed to each agent, irrespective of others' preferences. If the manna is non atomic and utilities are continuous (not necessarily monotone or convex), we can guarantee the min-Max utility: that of our agent's best share in her worst partition of the manna; and implement it by Kuhn's generalisation of Divide and Choose. The larger Maxmin utility -of her worst share in her best partition -cannot be guaranteed, even for two agents.

If for all agents more manna is better than less (or less is better than more), our Bid & Choose rules implement guarantees between minMax and Maxmin by letting agents bid for the smallest (or largest) size of a share they find acceptable.

Introduction and the punchlines

The fair division of a common property manna -resources privately consumed -is a complicated problem if its joint owners have heterogenous preferences over the manna. A coarse yet important benchmark is the welfare Guarantee a division rule offers to each participant: this is the highest welfare that a given agent can secure in this rule, irrespective of the preferences of other agents, even if our agent is clueless about the latter and assumes the worst. The more an agent is risk averse and the less she knows about others' preferences, the more this worst case benchmark matters to her.

Our goal is to throw some light on the feasible Guarantees in the very general class of non atomic fair division problems: small changes in the size of a share result in small utility changes (a continuity property explained below). Our model places no other restrictions on the structure of preferences and corresponding utilities, or their direction: the manna may contain some desirable parts (money, tasty cake, valuable commodities), some not (unpleasant tasks, financial liabilities, burnt parts of the cake that must still be eaten [START_REF] Segal-Halevi | Fairly Dividing a Cake after Some Parts Were Burnt in the Oven[END_REF]); agents may disagree over which parts are good or bad; utilities can be single-peaked over some parts (teaching loads, volunteering time, shares of a risky project), single-dipped on others, etc.. Assume that the manna Ω and the domain D of potential preferences are common knowledge, and define a Fair Guarantee as a mapping (u i , n) → Γ(u i ; n) selecting for each preference in D, described for clarity as a utility function u i , and each number n of joint owners, a utility level. The mapping is fair because it ignores agent i's identity, and it must be feasible: for any profile (u i ) n i=1 of utilities in D n there exists a partition (S i ) n i=1 of Ω such that u i (S i ) ≥ Γ(u i ; n) for all i.

Given the division problem (Ω, D) we ask what are the best (highest) Fair Guarantees? and what mechanism implements1 them?

Observe first that any Fair Guarantee Γ(u; n) is bounded above by the utility, denoted Maxmin(u; n), of the worst share for u in the best n-partition of the manna. For all u ∈ D and n we have

Γ(u; n) ≤ Maxmin(u; n) = max Π=(S i ) n i=1 min 1≤i≤n u(S i ) (1)
where the maximum (that may not be achieved exactly) bears on all n-partitions Π = (S i ) n i=1 of Ω. This follows by feasibility of Γ(u; n): at the unanimous profile where u i = u for all i there is a partition Π such that u(S i ) ≥ Γ(u; n) for all i, hence Γ(u; n) ≤ min 1≤i≤n u(S i ) ≤ Maxmin(u; n).

Therefore if (u, n) → Maxmin(u; n) is itself a Fair Guarantee (it is fair, but the issue is feasibility), it is the best possible one and answers the first of the two general questions above. This happens in two well known and much discussed families of fair division problems.

In the cake-cutting model due to Steinhaus ([35]) the manna Ω is a measurable space endowed with a non atomic measure, and utilities are additive measures, absolutely continuous with respect to the base measure. Additivity of u implies Maxmin(u; n) ≤ 1 n u(Ω); this is in fact an equality because the cake can be partitioned in n shares of equal utility. Agent i's share S i is Proportionally Fair if u i (S i ) ≥ 1 n u i (Ω): this is feasible for all agents at any preference profile (u i ) n i=1 , therefore Proportional Fairness offers the best possible Guarantee in this model, and is the weakest and least controversial test of fairness throughout the cake-cutting literature ( [START_REF] Brams | Fair Division: From Cake-Cutting to Dispute Resolution[END_REF] and [START_REF] Robertson | Cake Cutting Algorithms: Be Fair If You Can[END_REF]).

In the microeconomic model of fair division the manna is a bundle ω ∈ R K + of K divisible and non disposable items, and D is the set of convex and continuous preferences over [0, ω] (not necessarily monotonic). It is feasible to give an equal share 1 n ω to every agent, so that Γ es (u; n) = u( 1 n ω) is a feasible Guarantee. In D the inequality Maxmin(u; n) ≤ u( 1n ω) is also true. 2 Therefore the optimal Guarantee is Γ es , aka the Equal Split lower bound

u i (z i ) ≥ u( 1 n ω) (where z i is i's share of ω).
Here too it is the starting point of the discussion of fairness (see e. g., [START_REF] Thomson | The theory of fair allocation[END_REF] and [START_REF] Moulin | Fair Division in the Internet Age[END_REF]).

As soon as we drop either additivity in the former model, or convexity in the latter one, the Maxmin benchmark is not a Fair Guarantee any more: already in some two person problems no division of the manna yields at least Maxmin(u i ; 2) for both i = 1, 2. In a simple example Ann and Bob share 10 units of a single non disposable divisible item (e.g., time spent in a given activity). Ann's preferences are single-peaked (hence convex), while Bob's are single-dipped (see Figure 1 ):

u A (x) = x(12 -x) ; u B (x) = x(x -6) for 0 ≤ x ≤ 10
2 Pick a hyperplane H supporting the upper contour of u at 1 n ω; the lower contour of u at 1 n ω contains one closed half-space cut by H, and every division of ω as ω = n 1 z i includes at least one z j in that half-space.

Compute

Maxmin(u

A ) = 35 at Π 1 = {5, 5} ; Maxmin(u B ) = 0 at Π 2 = {0, 10}
If Bob's share is worth at least Maxmin(u B ) then Ann gets either the whole manna or at most 4 units: so her utility is at most 32 and we see that (Maxmin(u A ), Maxmin(u B )) is not feasible.

A second critical benchmark utility is minMax(u; n), the utility of the best share for u in the worst possible n-partition of Ω:

minMax(u; n) = min Π=(S i ) n i=1 max 1≤i≤n u(S i )
where as before the minimum bears on all n-partitions of Ω.

Our first main result, Theorem 1 in Section 4, says that in any non atomic problem, the mapping u → minMax(u; n) is a Fair Guarantee; in particular minMax(u; n) ≤ Maxmin(u; n) for all u ∈ D and n (by ( 1)). Moreover the minMax Guarantee is implemented by Kuhn's little known n-person generalisation of Divide and Choose ( [START_REF] Kuhn | On games of fair division, Essays in Mathematical Economics in Honour of Oskar Morgenstern[END_REF]), denoted here D&C n .

The result is clear in two person problems, where ordinary Divide and Choose clearly guarantees her Maxmin to the Divider and his Minmax to the Chooser. For instance in the example above Ann would Divide as Π 1 = {5, 5} and Bob would get utility -5, exactly his minMax(u B ; 2); while Bob would Divide as Π 2 = {0, 10}, and Ann would Choose 10, thus achieving minMax(u A ; 2) = 20.

In three persons problems D&C 3 works as follows. The Divider Ann offers a 3-partition Π = {S 1 , S 2 , S 3 } where all shares are of equal value to her; Bob accepts all shares worth at least minMax(u B ; 3), and Charles all those worth least minMax(u C ; 3). If Bob and Charles can each be assigned a share they accept, we do so and Ann gets the last piece. 3 If both accept a single share in Π, the same one, we give one of the remaining shares S k to Ann (it does not matter which one) and then run D&C 2 between Bob and Charles for Ω S k (it does not matter who Divides or Chooses).

The n-person division rule D&C n proceeds similarly in at most n -1 steps of Division and Acceptance between a shrinking set of agents sharing a shrinking manna. Its only subtlety is a simple combinatorial matching step (Lemma 2 in Section 4) after each partitioning of the remaining manna.

The hard step in proving Theorem 1 is Lemma 1 in Subsection 3.2, stating that in each round of D&C n the current Divider can find an equipartition: a partition of the remaining manna where all shares are equally valuable to this Divider. Because we only assume that he manna is measurable and endowed with a non atomic measure, and that utilities are continuous in that measure, the proof of Lemma 1 requires advanced tools in algebraic geometry: this the object of the companion paper [START_REF] Avvakumov | Equipartition of an interval[END_REF], see the discussion in Subsection 3.2.

Our second main result, Theorem 2 in Subsection 5.2, focuses on non atomic problems where preferences are also co-monotone: that is, increasing if enlarging a share cannot make it worse and we speak of a good manna; or decreasing if the opposite holds and we have a bad manna. Either restriction on preferences opens the door to a new family of division rules significantly simpler than D&C n and implementing a higher Guarantee than the minMax. These rules are inspired by the well known family of Moving Knife (MK n ) rules (Dubins and Spanier [START_REF] Dubins | How to cut a cake fairly[END_REF]) that we recall first.

Assume the manna is good: a knife cuts continuously an increasing share of the cake; agents can stop the knife at any time; the first agent who does gets the share cut so far. Repeat between the remaining agents and manna. For a bad manna, agents can drop at any time and the last one to drop gets the share cut so far.

A Moving Knife (MK) rule chooses a single arbitrary path for the knife, which tightly restricts the range of individual shares and partitions, hence can result in a very inefficient allocation. We introduce a large family of rules in the same spirit as MK but with all partitions in their range, that we call the Bid & Choose (B&C n ) rules. Each rule is defined by fixing a benchmark additive measure of the shares, diversely interpreted as their size, their market price, etc.. If the manna is good a bid b i by agent i is the smallest measure of a share that i finds acceptable: the smallest bidder i * chooses freely a share of measure at most b i * , then we repeat between the remaining agents and manna. For a bad manna the bid b i is the largest size of a share that i finds acceptable, and the largest bidder i * picks any share of size at least b i * .

Theorem 2 in Section 5 shows that all B&C n rules, as well as all MK n rules implement a Guarantee between the minMax and Maxmin level.

A handful of examples in Subsection 5.3 show that the B&C n Guarantee improves substantially the minMax Guarantee in the microeconomic model of fair division. There the Equal Split Guarantee is the Maxmin benchmark (the best possible) for agents with convex preferences, while for agents with "concave" preferences (convex lower contours) Equal Split is the minMax Guarantee, which the B&C n Guarantee improves significantly.

Throughout the paper we speak of implementation in the very simple sense adopted by most of the cake cutting literature (e. g., [START_REF] Brams | Fair Division: From Cake-Cutting to Dispute Resolution[END_REF]), and formalized in the general collective decision context as implementation in "protective equilibrium" (Barbera and Dutta [START_REF] Barbera | Implementability via protective equilibria[END_REF]). A rule implements (guarantees) a certain utility level γ means this: no matter what her preferences, each agent has a strategy that depends also upon Ω, n and D, such that whatever other agents do the utility of her share is no less than γ. Moreover the "guaranteeing strategy" is essentially unique.

Relevant literature

The two welfare levels Maxmin and minMax are key to our results. In the atomic model where the manna is a set of indivisible items, they are introduced by Budish ( [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF]) and Bouveret and Lemaitre ( [START_REF] Bouveret | Characterizing conflicts in fair division of indivisiblegoods using a scale of criteria[END_REF]) respectively . If utilities are additive in that model, the basic inequality of our non atomic model is reversed:

Maxmin(u; n) ≤ 1 n u(Ω) ≤ minMax(u; n)
and minMax(u; n) is obviously not a feasible Guarantee. It took a couple of years and many brain cells to check that the Maxmin lower bound may not be feasible either for three or more agents ( [START_REF] Procaccia | Fair Enough: Guaranteeing Approximate Maximin Shares[END_REF]), though this happens in rare instances of the model ( [START_REF] Kurokawa | When can the maximin share guarantee be guaranteed?[END_REF]). 4 Our paper is the first systematic discussion of these two bounds in the non atomic model of cake division. Kuhn's 1967 n person generalisation of Divide and Choose ( [START_REF] Kuhn | On games of fair division, Essays in Mathematical Economics in Honour of Oskar Morgenstern[END_REF]) promptly implements the minMax guarantee in our model: Theorem 1. Except for a recent discussion in [START_REF] Aigner-Horev | Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division[END_REF] for additive utilities, D&C n has not received much attention, a situation which our paper may help to correct. In particular, unlike the Diminishing Share ( [35]) Moving Knife ( [START_REF] Dubins | How to cut a cake fairly[END_REF]), and Bid and Choose rules, it is very well suited to divide mixed manna, i. e., containing subjectively good and bad parts, as when we divide the assets and liabilities of a dissolving partnership. Introduced in [START_REF] Bogomolnaia | Competitive division of a mixed manna[END_REF] and [START_REF] Bogomolnaia | Dividing Bads under Additive Utilities[END_REF] for the competitive fair division of commodities in the microeconomic model, the mixed manna model is discussed by [START_REF] Segal-Halevi | Fairly Dividing a Cake after Some Parts Were Burnt in the Oven[END_REF] for a general cake, and by [START_REF] Aziz | Fair allocation of combinations of indivisible goods and chores[END_REF] for indivisible items.

Privacy preservation is a growing concern in a world of ever expanding information flows. The D&C n rule stands out for its informational parsimony: each Divider only reports a partition with the understanding that she is indifferent between the two shares she just cut, and Choosers only only accept a subset of these shares. If the manna is mixed, no one is asked to explain which parts they view as good or bad: for instance if we divide tasks, I may not want others to know which tasks I am actually happy to perform, or which ones are very painful to me.

The "cuts" selected by Dividers and "queries" answered by Choosers require only a modest cognitive effort: no one needs to form complete preference relations over all shares of the cake. Taking this feature to heart, a large literature in the cake cutting model evaluates the informational complexity of various mechanisms by the number of "cuts" and "queries" they involve: see [START_REF] Brams | Fair Division: From Cake-Cutting to Dispute Resolution[END_REF] or [START_REF] Robertson | Cake Cutting Algorithms: Be Fair If You Can[END_REF], and more recently [START_REF] Cseh | The complexity of cake cutting with unequal shares[END_REF] and [START_REF] Crew | Disproportionate division[END_REF]. This line of research goes beyond the test of Proportional Guarantee, and find cuts and queries division rules more complex than D&C n reaching an Envy-free division of the cake. The algorithms in Brams and Taylor ( [START_REF] Brams | An envy-free cake division protocol[END_REF]), and more recently Aziz and McKenzie ([6]), do exactly this when utilities are additive and non atomic; but because they involve an astronomical number of cuts and queries they are of no practical interest and squarely contradict informational parsimony. See ( [START_REF] Branzei | A note on envy-free cake cutting with polynomial valuations[END_REF], [START_REF] Kurokawa | How to Cut a Cake Before the Party Ends[END_REF]) for some fine tuning of these general facts.

The "equipartition" Lemma (Subsection 3.2) is critical to the proof of Theorem 1, and proved in [START_REF] Avvakumov | Equipartition of an interval[END_REF] by algebraic geometry techniques. These, or subtle variants of Sperner's Lemma, demonstrate the existence of an Envyfree division under very general preferences, where which share I like best in a given partition can depend upon the partition itself, not just upon my own share: Stromquist's ( [START_REF] Stromquist | How to cut a cake fairly[END_REF]) and Woodall's ( [START_REF] Woodall | Dividing a cake fairly[END_REF]) seminal insights are considerably strenghtened by the recent results in [START_REF] Su | Rental harmony: Sperner's lemma in fair division[END_REF], [START_REF] Segal-Halevi | Fairly Dividing a Cake after Some Parts Were Burnt in the Oven[END_REF], [START_REF] Meunier | Envy-free cake division without assuming the players prefer nonempty pieces, forthcoming[END_REF] and [START_REF] Avvakumov | Envy-free Division under Mapping Degree[END_REF]. However all these results assume that, either all agents (weakly) prefer any non empty share to the empty share, or all weakly prefer the empty share to any non empty one: this rules out a mixed manna.

We noted earlier that the concept of unanimity utility (the common efficient utility level in the economy where everyone has the same preferences) leads to the Equal Split Guarantee when we divide private goods and preferences are convex (see Footnote 2). When applied to fair division problems involving production, it defines some compelling Fair Guarantees as well as some meaningful upper bounds on individual welfare: [START_REF] Moulin | Welfare Bounds in the Cooperative Production Problem[END_REF], [START_REF] Moulin | All Sorry to Disagree: a General Principle for the Provision of Non-rival Goods[END_REF].

3 Non atomic fair division

Basic definitions

The manna Ω is a bounded measurable set in an euclidian space, endowed with the Lebesgue measure |•|, and such that |Ω| > 0. A share S is a possibly empty measurable subset of Ω, and B is the set of all shares. A n-partition of Ω is a n-tuple of shares Π = (S i ) n i=1 such that ∪ n i=1 S i = Ω and |S i ∩ S j | = 0 for all i = j; and P n (Ω) is the set of all partitions of Ω. We define similarly an n-partition of S for any share S ∈ B, and write their set as P n (S).

If S ⊗ T = (S ∪ T ) (S ∩ T ) is the symmetric difference of shares, recall that δ(S, T ) = |S ⊗ T | is a pseudo-metric on B (a metric except that δ(S, T ) = 0 iff S and T differ by a set of measure zero).

A utility function u is a mapping from B into R such that u(∅) = 0 and u is continuous for the pseudo-metric δ and bounded. So u does not distinguish between two shares at pseudo-distance zero (equal up to a set of measure zero): for instance u(S) = 0 if |S| = 0. Also if the sequence |S t | converges to zero in t, so does u(S t ). We write D(Ω) for this domain of utility functions.

So a non atomic division problem consists of (Ω, B, (u i ) n i=1 ∈ D(Ω) n ). Several subdomains of D(Ω) play a role below:

• additive utilities: u ∈ Add(Ω) iff u(S) = S f (x)dx for all S, where f is bounded and measurable in Ω;

• monotone increasing:

u ∈ M + (Ω) iff S ⊂ T =⇒ u(S) ≤ u(T ) for all S, T ; • monotone decreasing: u ∈ M -(Ω) iff S ⊂ T =⇒ u(S) ≥ u(T ) for all S, T ;
• separable: u ∈ S(Ω) iff there is a finite set A, a partition (C a ) a∈A ∈ P |A| (Ω) of Ω, and a continuous function

v from R A + into R, such that u(S) = v((|S ∩ C a |) a∈A ) for all S ∈ B.
The separable domain S(Ω) captures the standard microeconomic fair division model: A is a set of divisible commodities, the manna is the bundle ω ∈ R A + such that ω a = |C a | for all a, a share S i gives to agent i the amount z ia = |S i ∩ C a | of commodity a, and the partition Π = (S i ) n i=1 corresponds to the division of the manna as ω = n 1 z i . In the general non atomic division problem, the set of shares B is not compact for the pseudo-metric δ. It follows that when we maximize or minimize utilities over shares, or look for a partition achieving a benchmark utility minMax or Maxmin, we cannot claim the existence of an exact solution to the program: the minMax is not a true minimum, only an infimum, and Maxmin is only a supremum, not a true maximum. As this will cause no confusion, we stick to the min and Max notation throughout.

However in the microeconomic model, the set of shares and of partitions are both compact so for this important set of problems (where all our examples live) the min and Max notation are strictly justified.

One can also specialise the general model by imposing constraints on the set of feasible shares. The most important instance is the familiar interval model, where the manna is Ω = [0, 1] and a share must be an interval, so an n-partition is made of n adjacent intervals. Other instances assume Ω is a polytope, and shares are polytopes of a certain type: e.g. triangles or tetrahedrons ( [START_REF] Segal-Halevi | Fair and square: Cake-cutting in two dimensions[END_REF]). And sometimes shares must be connected subsets of Ω ([8], [START_REF] Aumann | The Efficiency of Fair Division with Connected Pieces, International Workshop on Internet and Network Economics WINE[END_REF]).

The Divide and Choose n rules, as well as our Bid and Choose n rules, do not work in these models5 , so our Theorems 1 and 2 do not apply. But the interval model is still useful here in a technical sense: the proof of the critical Lemma 1 in Subsection 3.2 starts by projecting the general problem onto an interval model and proving existence of an equipartition there.

Equipartitions

Definition 1 An n-equipartition of the share T ∈ B for utility u ∈ D(T ) is a partition Π e = (S i ) n i=1 ∈ P n (T ) such that u(S i ) = u(S j ) for all i, j ∈ {1, • • • , n}; we write u(Π e ) for this common value, and EP n (T ; u) for the set of these n-equipartitions.

It is clear that EP

n (S; u) is non empty if u is additive: if B[S]
is the subset of shares included in S, Lyapunov Theorem implies that the range u(B[S]) is convex, so it contains 1 n u(S); then we replace n by n -1 and repeat the argument on the remaining share.

The same is true if u is monotone (u ∈ M ± (Ω)), and the proof, outlined in Remark 1 below, is fairly simple. That of our next statement is much harder.

Lemma 1 ([4])

Fix a share S ∈ B and a utility u ∈ D(Ω). The set EP n (S; u) of nequipartitions of S at u is non empty.

Proof. The Theorem in [START_REF] Avvakumov | Equipartition of an interval[END_REF] proves Lemma 1 for the interval model (which, as mentioned above, is not a special case of our model). Fix a real valued function f on the set of intervals [a, b] ⊂ [0, 1], continuous in the standard topology and such that f (a, a) = 0 for all a ∈ [0, 1]. Then there exist

n subintervals [0 = x 0 , x 1 ], [x 1 , x 2 ], • • • , [x n-1 , x n = 1] of [0, 1] forming an equipartition of f : f (x i-1 , x i ) is constant for i = 1, • • • , n.
Start now from a share S in the statement of Lemma 1 and pick a moving knife through S, i. e., a path κ :

[0, 1] ∋ t → K(t) ∈ B from K(0) = ∅ to K(1) = S,
continuous for the pseudo-metric δ on B and weakly inclusion increasing:

0 ≤ t < t ′ ≤ 1 =⇒ K(t) ⊆ K(t ′ )
(in Subsection 5.1 moving knifes must be strictly inclusion increasing). Then the function

f (a, b) = u(K(b) K(a))
is as in the previous paragraph, and an f -equipartition ([x i-1 , x i ]) n i=1 of [0, 1] yields the desired u-equipartition (K(x i ) K(x i-1 )) n i=1 of S. Remark 1 It is easy to prove Lemma 1 if we assume that the sign of u is constant: all shares are weakly preferred to the empty share, or all are weakly worse. Assume the former and use as above a moving knife to project S onto [0, 1], where a n-partition is identified with a point in the simplex of dimension n -1. Then apply the Knaster-Kuratowski-Mazurkiewicz Lemma to the sets Q i of partitions of the interval where the i-th interval gives the lowest utility: each Q i is closed, contains the i-th face of the simplex, and their union covers it entirely. Thus these sets intersect.

One can also invoke the stronger results in [START_REF] Stromquist | How to cut a cake fairly[END_REF] and [START_REF] Su | Rental harmony: Sperner's lemma in fair division[END_REF] showing the existence of an Envy-free partition under this assumption. But recall that a key feature in the division of a mixed manna is that the sign of u is not constant across shares.

Two utility benchmarks

Definition 2 Fix n, the manna (Ω, B) and u ∈ D(Ω):

minMax(u; n) = min Π∈Pn(Ω) max 1≤i≤n u(S i ) ; Maxmin(u; n) = max Π∈Pn(Ω) min 1≤i≤n u(S i ) (2)
Recall that minMax is the utility agent u can achieve by having first pick in the worst possible n-partition of Ω, and Maxmin by having last pick in the best possible n-partition of Ω.

Proposition 1 i) If u ∈ Add(Ω) then minMax(u; n) = Maxmin(u; n) = 1 n u(Ω) ii) If u ∈ M ± (Ω) minMax(u; n) = min Π e ∈EPn(Ω;u) u(Π e ) ; Maxmin(u; n) = max Π e ∈EPn(Ω;u) u(Π e ) (3) iii) If u ∈ D(Ω) minMax(u; n) ≤ min Π e ∈EPn(Ω;u) u(Π e ) ≤ max Π e ∈EPn(Ω;u) u(Π e ) ≤ Maxmin(u; n) (4)
Proof Statement iii) If Π e is an n-equipartition, u(Π e ) is the utility of its best share, hence minMax(u; n) ≤ u(Π e ); proving the other inequality in (4) is just as easy. Statement i) By additivity of u, for any n-partition Π we have max i u(P i ) ≥

1 n u(Ω) implying minMax(u; n) ≥ 1
n u(Ω); we check symmetrically 1 n u(Ω) ≥ Maxmin(u; n), and the conclusion follows by comparing these inequalities to those in (4). Statement ii) Assume u ∈ M + (Ω); the proof for M -(Ω) is identical. The continuity and monotonicity of u imply: if S, T are two disjoints shares such that u(S) > u(T ), we can trim part of S and add it to T to get two disjoint shares with equal utility in between u(S) and u(T ). Expanding this argument, if S 1 , • • • , S k and T are disjoint shares such that

u(S 1 ) = u(S 2 ) = • • • = u(S k ) > u(T )
we can simultaneously trim S 1 , • • • , S k keeping them of equal utility and add the trimming to T , so that the resulting k + 1 shares are all equally good and their common utility is between the two utilities above. Iterating this process, we see that if Π = (S i ) n i=1 ∈ P n (Ω) is such that max 1≤i≤n u(S i ) > min 1≤i≤n u(S j ), we can construct an equipartition Π e ∈ EP n (Ω; u) such that

max 1≤i≤n u(S i ) > u(Π e ) > min 1≤j≤n u(S j )
Now fix ε > 0, arbitrarily small, pick Π = (S i ) n i=1 ∈ P n (Ω) such that min 1≤j≤n u(S j ) ≥ Maxmin(u; n)ε, and assume that Π is not an equipartition. By the argument above we can find Π e ∈ EP n (Ω; u) such that u(Π e ) > min 1≤j≤n u(S j ), therefore Π e too is an ε-approximation of Maxmin(u; n), and the right-hand inequality in (3) follows. The proof of the left-hand inequality is similar.

In the general domain D(Ω), the partitions achieving the Maxmin and minMax utilities are not necessarily equipartitions. In the microeconomic example of Section 1, Ann has single-peaked preferences and her minMax is achieved by the all-or-nothing partition {∅, Ω}; Bob has single-dipped preferences and the same partition delivers his Maxmin; but {∅, Ω} is not an equipartition for either utility.

Remark 2: In the interval model with a monotone utility u, it is easy to check that any two n-equipartitions have the same utility and in turn this implies minMax(u; n) = Maxmin(u; n): hence this is the best Fair Guarantee. The numerical example above can be viewed as an instance of the interval model where the two agents are indifferent between [0, x] and [1x, 1] for all x: so only the inequality (4) holds true in the general (non monotone) interval model.

Fair Guarantees

Definition 3 Fix the manna (Ω, B) and a subdomain D * , D * ⊆ D(Ω). A Fair Guarantee in D * is a mapping Γ : u → Γ(u; n) such that for any profile

(u i ) n i=1 ∈ (D * ) n there exists Π = (S i ) n i=1 ∈ P n (Ω) such that u i (S i ) ≥ Γ(u i ; n) for all i.
In Section 1 we observed, by looking at unanimity profiles, that Maxmin(•; n) is an upper bound for any Fair Guarantee: inequality (1). We also mentioned two subdomains where Maxmin(•; n) itself is a (hence the optimal) Fair Guarantee: the additive domain Add(Ω) and the subdomain of the separable one S(Ω) where preferences are also convex. Finally we used the Ann and Bob microeconomic example with a single commodity to show that Maxmin(•; n) is not a Fair Guarantee in D(Ω), even for n = 2 and a one dimensional manna.

Before proving in the next Section that minMax(•; n) is a Fair Guarantee in the whole domain D(Ω) we construct a microeconomic problem with two divisible items and two agents u 1 and u 2 where minMax(u i ; 2) = 0 < 1 = Maxmin(u i ; 2) for i = 1, 2 and (minMax(u 1 ), minMax(u 2 )) is weakly Pareto optimal This implies that for any Fair Guarantee Γ, at least one of Γ(u 1 ; 2) = 0 and Γ(u 2 ; 2) = 0 must hold. In words, for some problems, no Fair Guarantee can reduce the gap from minMax to Maxmin for both agents. 6The manna is ω = (1, 1) and we a share as z = (x, y). Both utilities are symmetric in x, y: u i (x, y) = u i (y, x) so it is enough to define them for x ≤ y:

u 1 (z) = 0 if x ≤ 1 2 ≤ y u 1 (z) = 1 -2y if x ≤ y ≤ 1 2 u 1 (z) = 2x -1 if 1 2 ≤ x ≤ y u 2 (z) = 0 if x ≤ y ≤ 1 2 or 1 2 ≤ x ≤ y u 2 (z) = 2y -1 if 1 2 ≤ y ≤ 1 -x u 2 (z) = 1 -2x if 1 2 ≤ 1 -x ≤ y
The range of both utilities is [0, 1]. Agent 1's utility u 1 (z 1 ) is null in the NW and SE quadrant of the box [0, 1] 2 with center at ( 1 2 , 1 2 ); it is strictly positive in the SW and NE quadrants except on the lines x = 1 2 and y = 1 2 . Agent 2's utility u 2 (z 2 ) is symetrically null in the SW and NE quadrants, and strictly positive in the NW and SE quadrants except on the same two lines. Therefore for any division (1, 1) = z 1 + z 2 of the manna we have u

1 (z 1 ) • u 2 (z 2 ) = 0: there is no feasible division s. t. u i (z i ) > 0 for i = 1, 2.
The partition {(0, 0), (1, 1)} achieves Maxmin(u 1 ) = 1 and minMax(u 2 ) = 0; the partition {(0, 1), (1, 0)} achieves Maxmin(u 2 ) = 1 and minMax(u 1 ) = 0.

The Divide & Choose n rule

Start by a combinatorial observation. Let G be a bilateral graph between the sets M of agents and R of shares: interpret (m, r) ∈ G as agent m likes share r. We say that the subset M of agents are properly matched to the subset R of shares if | M | = | R|, agents in M are each matched (one-to-one) to a share they like in R, and no one outside M likes any share in R.

Lemma 2. Assume |M| = |R|, each agent in M likes at least one object in R and some agent i * likes all objects in R. Then there is a (non empty) largest set M * of properly matchable agents containing i * : if M is properly matched to R, then M ⊆ M * .

Proof. We apply the Gallai-Edmonds decomposition of a bipartite graph: see e.g. [START_REF] Lovasz | Matching Theory[END_REF] Chap 3 (or Lemma 1 in [START_REF] Bogomolnaia | Random matching under divhotomous preferences[END_REF]). If M can be matched with R this is a proper match and the statement holds true. If M and R cannot be matched, then we can uniquely partition M as (M + , M * ) and R as (R + , R * ) such that: 1. |M + | > |R + |, the agents in M + do not like any object in R * , and they compete for the over-demanded objects in R + : every subset of R + is liked by a strictly larger subset of agents in M + ; 2. |M * | < |R * | and the agents in M * can be matched with some subset of R * .

By the general Gallai-Edmonds result, M + and R * are non empty. Here M * is non empty as well because it contains the special agent i * . Every match of M * to a subset of R * is proper. Finally suppose M is properly matched to R and M = M ∩ M + is non empty. Then M is matched to some subset R of R + but R is liked by more agents in M + than there are in M , therefore the match is not proper: contradiction. So M does not intersect M + as was to be proved.

Definition 4: the D&C n rule. Fix the manna (Ω, B) and the ordered set of agents N = {1, • • • , n}, each with a utility in D(Ω).

Step 1. Agent 1 proposes a partition Π 1 ∈ P n (Ω); all other agents report which shares in Π 1 they like (at least one). In the resulting bipartite graph between N and the shares in Π 1 , where agent 1 likes all the shares, we use Lemma 2 to match properly the largest possible set of agents N 1 (it contains agent 1) with some set of shares R; if N 1 = N we are done, otherwise we go to

Step 2. Repeat with the remaining manna Ω 2 and agents in N N 1 . Ask the first agent in the exogenous ordering to propose a partition Π 2 ∈ P n-|N 1 | (Ω 2 ), while others report which of these new shares they like. And so on.

At least one agent, the Divider, is served in each step, thus the algorithm just described takes at most n -1 steps. But the algorithm matches as many agents as possible, so as to minimize information disclosure, and typically takes fewer steps.

There is some flexibility in the Definition of the rule: although the set of agents matched in each step is unambiguous, we have typically several choices for the set R of shares to assign in each step, and multiple ways to assign these to the agents.

Our first main result is that minMax is a Fair Guarantee, implemented by the D&C n rule in the full domain D(Ω).

Theorem 1

Fix the manna (Ω, B) and n. i) In the D&C n rule, an agent with utility u ∈ D(Ω) guarantees the minMax(u; n) utility level by 1) when called to divide, proposing an equipartition Π e ∈ EP m (S; u) of the remaining share S of manna among the m remaining agents, and 2) when reporting shares he likes, accepting all shares, and only those, not worse than minMax(u; n) (the minMax level in the initial problem). ii) Moreover the first Divider (and no one else) guarantees her Maxmin utility by proposing her Maxmin partition in Step 1. Other agents cannot guarantee more than their minMax utility.

Proof. Statement i). Consider agent u using the strategy in the statement. At a step where he must report which shares he likes among those offered at that step, he can for sure find one worth at least minMax(u; n): all shares previously assigned are worth to him strictly less than minMax(u; n), and together with the freshly cut shares they form a partition in P n (Ω); in any partition at least one share is worth minMax(u; n) or more.

At a step where our agent is called to cut, he proposes to the remaining agents an m-equipartition Π e ∈ EP m (S; u) of the remaining manna S. To check the inequality u(Π e ) ≥ minMax(u; n) note that Π e together with the previously assigned shares is a partition of Ω in which the old shares are worth strictly less than minMax(u; n). 7Statement ii). This is clear for the first Divider. Fix now an agent i with utility u and check that if he is not the first Divider, for certain moves of the other agents, agent u gets exactly his minMax utility. Pick a partition Π ∈ P n (Ω) achieving minMax(u; n) (as usual, the existence assumption is without loss). Suppose that the first Divider, who is not agent i, offers Π, and all agents other than i (including the Divider) find all shares acceptable: then a full match is feasible (i must accept at least one share) so i's share cannot be worth more than minMax(u; n).

Bid and Choose and Moving Knives for good or bad manna

We now assume that the manna is unanimously good, u ∈ M + (Ω), or unanimously bad, u ∈ M -(Ω). Because u(∅) = 0, for all S we have u(S) ≥ 0 in the former case and u(S) ≤ 0 in the latter. Recall that in these two domains, the minMax (resp. Maxmin) utility is the smallest (resp. largest) equipartition utility: property (3) in Proposition 1.

We check first that the profile of Maxmin utility levels still may not be feasible, even in the simple microeconomic model (corresponding to the separable domain S(Ω) in Subsection 3.1). We have one unit each of two divisible goods,ω = (1, 1), to be shared between two agents. The first agent has Leontief preferences u 1 (z) = min{x, y} so his worst case partition is Π = {(1, 0), (0, 1)} and his best one is the equal split partition Π ′ = { 1 2 ω, 1 2 ω}: minMax(u 1 ; 2) = 0 < 1 2 = Maxmin(u 1 ; 2). Agent 2 has anti-Leontief preferences: u 2 (z) = max{x, y}. For her the equal split partition Π ′ is the worst and the best one is Π: minMax(u 2 ; 2) = 1 2 < 1 = Maxmin(u 2 ; 2). Clearly the profile of Maxmin utilities ( 12 , 1) is not feasible, while D&C 2 implements ( 1 2 , 1 2 ) and (0, 1), depending on who is the Divider. We show that the minMax guarantee is always improved, at least weakly, by the large family of Bid and Choose (B&C n ) rules, inspired by the familiar Moving Knives (MK n ) rules ( [START_REF] Dubins | How to cut a cake fairly[END_REF]).

MK κ n and B&C θ n rules

A moving knife through the manna (Ω,

B, | • |) is a path κ : [0, 1] ∋ t → K(t) ∈ B from K(0) = ∅ to K(1)
= Ω, continuous for the pseudo-metric δ on B and strictly inclusion increasing:

0 ≤ t < t ′ ≤ 1 =⇒ K(t) ⊂ K(t ′ ) and |K(t ′ ) K(t)| > 0
The moving knife κ arranges shares of increasing value to all participants along the specific path of the knife. An example is K(t) = B(t) ∩ Ω, where t → B(t) is a path of balls with a fixed center and radius growing from 0 to 1, so that B(1) contains Ω. Moving knifes can take many other shapes, for instance hyperplanes.

Our Bid and Choose rules offer more choices than Moving Knives to the agents, with the help of a benchmark measure θ of the shares, chosen by the rule designer: θ is a positive σ-additive measure on (Ω, B), normalised to θ(Ω) = 1. It is absolutely continuous w.r.t. the Lebesgue measure | • | and vice versa: the density of θ w.r.t. | • | is strictly positive. In particular θ is strictly inclusion increasing:

∀S, T ∈ B : S ⊂ T and |T S| > 0 ⇒ θ(S) < θ(T )
In applications θ can evaluate for instance the market value, physical size, or weight of a share.

Fixing a moving knife κ and a measure θ, we define in parallel the Moving Knife (MK κ n ) and the Bid and Choose (B&C θ n ) rules. In both cases a clock t runs from t = 0 to t = 1.

Definition 5 the MK κ n and B&C θ n rules with increasing utilities Step 1. The first agent i 1 to stop the clock, at t 1 , gets the share K(t 1 ) in MK κ n , or in B&C θ n chooses any share in Ω s.t. θ(S) = t 1 , say S i 1 , and leaves; Step k: Whoever stops the clock first at t k gets the share

K(t k ) K(t k-1 ) in MK κ n , or in B&C θ n chooses any share in Ω ∪ k-1 1 S i ℓ s.t. θ(S) = t k -t k-1
, say S i k , and leaves; In Step n -1 the single remaining agent who did not stop the clock takes the remaining share Ω K(t n-1 ) or Ω ∪ n-1 1 S i ℓ . Definition 5 * with decreasing utilities In each step all agents must choose a time to "drop", and the last agent i 1 who drops, at t 1 , gets K(t 1 ) in MK κ n , or in B&C θ n chooses S i 1 s.t. θ(S i 1 ) = t 1 . The other steps are similarly adjusted.

Breaking ties between agents stopping the clock (or dropping) at the same time is the only indeterminacy in these rules, much less severe than in D&C n , where we serve at each step an unambiguous set of agents, but there are typically several ways to match them properly.

Up to tie-breaking, B&C θ n and MK κ n are anonymous (do not discriminates between agents) but not neutral (do discriminate between shares), while D&C n is neutral but not anonymous.

In MK κ n the share of an agent takes the form K(t) K(t ′ ) so it covers a set of dimension 2 (and feasible partitions move in a set of dimension n -1). By contrast every partition in P m (Ω) is feasible under the B&C θ n rule. To check this fix Π = (S i ) n i=1 and assume first |S i | > 0 for all i. Consider n agents deciding (cooperatively) to achieve Π. By the strict monotonicity of θ the sequence t i = θ(∪ i j=1 S j ) increases strictly therefore they can stop the clock (or drop) at these successive times and choose the corresponding shares in Π. If there are shares of measure zero they can all be distributed at time 0.

On the other hand in B&C θ n all but one agent must pick a share under constraints, thus revealing more information than in MK κ n . Loosely speaking, B&C θ n is informationally comparable to D&C n . Remark 3. We can also implement the Guarantees described in the next Subsection by alternative static versions of MK κ n and B&C θ n where agents bid all at once for potential stopping times; we do not discuss these rules for the sake of brevity.

B&C θ and MK κ Guarantees

We fix an increasing utility u ∈ M + (Ω). The results are identical, and identically phrased, for a bad manna u ∈ M -(Ω). See also Remark 4 at the end of this Subsection.

Define the triangle T = {(t 1 , t 2 )|0 ≤ t 1 ≤ t 2 ≤ 1} in R 2 + and the set Υ(n) of increasing sequences τ = (t k ) 0≤k≤n in [0, 1] s.t.

t 0 = 0 ≤ t 1 ≤ • • • ≤ t n-1 ≤ 1 = t n
For a moving knife κ, utilities of the shares in MK κ n are described by the function u κ on T :

u κ (t 1 , t 2 ) = u(K(t 2 ) K(t 1
)) for all (t 1 , t 2 ) ∈ T For a measure θ, the corresponding definition in B&C θ is the indirect utility u θ : u θ (t 1 , t 2 ) = min

T :θ(T )=t 1 max S:S∩T =∅;θ(S)=t 2 -t 1 u(S) for all (t 1 , t 2 ) ∈ T (5)
Both u κ and u θ decrease (weakly) in t 1 and increase (weakly) in t 2 . We show below that the Guarantees Γ k and Γ θ implemented by MK κ n and B&C θ n respectively are computed as

Γ α (u; n) = max τ ∈Υ(n) min 0≤k≤n-1
u α (t k ; t k+1 ) where α is κ or θ

For instance in MK κ 2 with two agents, write τ κ for the (not necessarily unique) position of the knife making our agent indifferent between the share K(τ κ ) and its complement. Then Γ κ (u; 2) = max

0≤t 1 ≤1 min{u(K(t 1 )), u(Ω K(t 1 )) = u(K(τ κ )) = u(Ω K(τ κ )
In B&C θ 2 the bid τ θ makes the best share of size τ θ as good as the worst share of size 1τ θ :

Γ θ (u; 2) = max 0≤t 1 ≤1 min{ max θ(S)=t 1 u(S), min θ(S)=t 1 u(Ω S)} = max θ(S)=τ θ u(S) = min θ(S)=τ θ u(Ω S) (7) Lemma 4
i) The utility u κ and the indirect utility u θ are continuous. Both the minimum and maximum in [START_REF] Aziz | Fair allocation of combinations of indivisible goods and chores[END_REF] are achieved.

ii) The maximum of problem (6) (for both rules) is achieved at some τ ∈ Υ(n) where the sequence t k increases in k, all the u α (t k ; t k+1 ) are equal, and this common utility is the optimal value of [START_REF] Aziz | A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents[END_REF].

Proof in the Appendix.

Theorem 2 Fix the manna (Ω, B), the number of agents n, and a utility u ∈ M + (Ω). i) With the MK κ n rule, an agent guarantees the utility Γ κ (u; n) by committing to stop the knife at t k κ if exactly k -1 other agents have been served before; ii) With the B&C θ n rule, she guarantees Γ θ (u; n) by stopping the clock at t k θ if exactly k -1 other agents have been served before; and choosing then the best available share of size

t k -t k-1 . iii) minMax(u; n) ≤ Γ α (u; n) ≤ Maxmin(u; n) where α is κ or θ. Proof. Statement i) and iii) for MK κ n . Recall the equipartition Π = (K(t k κ ) K(t k-1 κ )) n 1 has u(Π) = Γ κ (u; n). Thus (3) in Proposition 1 implies the inequalities iii).
Next if the knife has been stopped k -1 times before our agent is served, the last stop occured at or before t k-1 κ therefore if she does stop the knife at t k κ (and wins the possible tie break) her share is at least K(t k κ ) K(t k-1 κ ). If she never gets to stop the knife, the last stop is at or before t n-1

It is easy to check that no agent can secure more utility than Γ κ n in MK κ n or Γ θ n in B&C θ n . Remark 4. The minMax Guarantee and Maxmin upper bound for u ∈ M ε (Ω) and -u ∈ M -ε (Ω), where ε = ±, are related: minMax(-u; n) = -Maxmin(u; n). With two agents the Guarantees Γ κ (u; 2) and Γ θ (u; 2) are similarly antisymmetric:

Γ α (-u; 2) = -Γ α (u; 2) where α is κ or θ (8)
This is clear for Γ κ and we check it for Γ θ by means of the change of variable S → S ′ = Ω S:

Γ θ (-u; 2) = -min 0≤t 1 ≤1 max{ min θ(S)=t 1 u(S), max θ(S)=t 1 u(Ω S)} = -min 0≤t 1 ≤1 max{ min θ(S ′ )=1-t 1 u(Ω S ′ ), max θ(S ′ )=1-t 1 u(S ′ )} = -min 0≤t ′ ≤1 max{ max θ(S ′ )=t ′ u(S ′ ), min θ(S ′ )=t ′ u(Ω S ′
)} and the claim follows because if two continuous functions t → f (t) and t → g(t) intersect in [0, 1] and one increases while the other decreases, then min 0≤t≤1 max{f (t), g(t)} = max 0≤t≤1 min{f (t), g(t}.

The identity (8) generalises to n ≥ 3 for the MK κ Guarantee, but not for the B&C θ one.

Microeconomic fair division

We must divide a good manna ω ∈ R K + in n shares z i ∈ R K + . Utilities u ∈ M + (ω) are continuous and weakly increasing on [0, ω].

A Moving Knife is a continuous increasing path t → K(t) from 0 to ω:

a natural choice is K(t) = tω, 0 ≤ t ≤ 1: the corresponding Guarantee Γ κ (u; n) = u( 1 n ω) is the Equal Split utility Γ es (u; n) = u( 1 n ω). A positive, additive measure θ defining B&C θ is a "price" θ(z) = p • z, p ∈ R K + {0}
, so we write the corresponding Guarantee as Γ p .

Recall from Section 1 that if an agent's preferences are convex her Equal Split utility equals her Maxmin utility, the upper bound on all Fair Guarantees ((1)), in particular it is weakly larger than the B&C p guarantee for any p. The converse inequality holds for "concave preferences".

Lemma 5 i) If the upper contours of the utility

u ∈ M + (ω) are convex, then Γ p (u; n) ≤ u( 1 n ω) = Maxmin(u; n). ii) If the lower contours of the utility u ∈ M + (ω) are convex, then minMax(u; n) = u( 1 n ω) ≤ Γ p (u; n).
The equality in statement i) was proven in Section 1. A symmetrical argument gives statement ii).

We turn to a handful of numerical examples where K = 2, ω = (1, 1), and p • z = 1 2 (x + y). Shares are z = (x, y), utilities are 1-homogenous and normalised so that u(ω) = 10. We compute our three Guarantees: Bid and Choose Γ p , Equal Split, and minMax, and compare them to the Maxmin upper bound.

The first three utilities (Leontief, Cobb Douglas and CES) define convex preferences, the last two define "concave preferences" (represented by quadratic and "anti-Leontief" utilities).

Our first table assumes two agents, n = 2, and illustrates Lemma 5. An agent with convex (resp. concave) preferences gets a better Guarantee under Equal Split (resp. Bid and Choose): The equal split partition delivers the Maxmin utility for the first four preferences, and the minMax utilities for the last three. The equipartition Π = {(1, 0), (0, 1)} gives similarly the minMax utilities of the first four, and the Maxmin ones for the last three.

u(x, y) minMax(u; 2) Γ p (u; 2) u(
To compute Γ p (u; 2) we know from (7) that the optimal bid t 1 (denoted t for simplicity) solves max This equality implies 0 ≤ t ≤ 1 2 . If u represents convex preferences symmetric in the two goods, u(x, y) is maximal under 1 2 (x + y) ≤ t at x = y = t, and minimal under x + y ≥ 2(1t) at x = 1, y = 1 -2t. So we must solve u(t, t) = u(1, 1 -2t): see Figure 2.

If u represents concave symmetric preferences its maximum under 1 2 (x + y) ≤ t is at x = 0, y = 2t, and its minimum under x + y ≥ 2(1t) at x = y = 1t, so we solve u(0, 2t) = u(1t, 1t): see Figure 3.

We compute finally the same Guarantees with three agents:

u(x, y) minMax(u; 3) Γ p (u; 3) u( The minMax equipartition for u = 5 2 ( √ x + √ y) 2 and the Maxmin equipartition for u ′ = 5 2(x 2 + y 2 ) have the same form Π = {(x, 0), (0, x), (1x, 1x)}: in the former case we find x = 4 5 and minMax(u; 3) = 2, in the latter we get x = 2 -√ 2 and Maxmin(u ′ ; 3) = 10( √ 2 -1). Lemma 5 and the partition Π ′ = {(1, 0), (0, 1 2 ), (0, 1 2 )} fill the remaining values of minMax and Maxmin.

To compute Γ p (u; 3) we know by Lemma 4 that the three terms in (6) are equal. They are u p (0, t 1 ) = max1 2 (x+y)≤t 1 u(x, y) u p (t 1 , t 2 ) = min 1 2 (x 1 +y 1 )≤t 1 max 1 2 (x+y)≤t 2 -t 1 and (x 1 +x,y 1 +y)≤(1,1) u(x, y) u p (t 2 , 1) = min1 2 (x 2 +y 2 )≤t 2 u(1x 2 , 1y 2 ) Clearly t 1 ≤ 1 3 (as t 2t 1 < 1 3 < t 1 and 1t 2 < 1 3 < t 1 are both impossible). Therefore u p (0, t 1 ) = u p (t 1 , t 2 ) is achieved by t 2 = 2t 1 (the constraint (x 1 + x, y 1 + y) ≤ (1, 1) does not bind). Writing t = t 1 = t 2t 1 it remains to solve max When u represents convex preferences symmetric in the two goods, the minimum on the right-hand side is achieved by (x, y) = (1 -4t, 1) so we solve u(t, t) = u(1 -4t, 1). See Figure 4.

If u represents concave symmetric preferences, the minimum on the righthand side is achieved by (x, y) = (1 -2t, 1 -2t) so we solve u(2t, 0) = u(1 -2t, 1 -2t). See Figure 5.

Concluding comments

Comparing B&C n versus D&C n rules The exogenous ordering of the agents greatly affects the outcome of D&C n , whereas B&C n treats the agents symmetrically. On the other hand the choice of the benchmark measure in B&C n is exogenous, which allows much, perhaps too much flexibility to the designer.

In D&C n the dividing agent may have many different strategies guaranteeing her minMax utility. By contrast in B&C n the solution to programs [START_REF] Barbera | Implementability via protective equilibria[END_REF] and ( 6) is often unique. Multiple choices and the resulting indeterminacy of the outcome may be appealing for the sake of privacy preservation, less so from the implementation viewpoint.

Two challenging open questions 1). Fix the manna (Ω, B) as in Theorem 1, and each of the n agents with his own utility in D(Ω). As mentioned in Section 2 and Subsection 3.2, Stromquist ( [START_REF] Stromquist | How to cut a cake fairly[END_REF]) showed that an Envy-free partition of Ω exists if all utilities are non negative for all shares. Without the sign assumption on utilities, Avvakumov and Karasev ( [START_REF] Avvakumov | Envy-free Division under Mapping Degree[END_REF]) prove existence of an Envy-free partition if n is a power of a prime number. Whether this remains true for all n is still an open question.

2) If the utilities vary in a domain U(Ω) where the Maxmin utility is not feasible, we would like to describe the family of undominated Fair Guarantees u → Γ(u; n). For instance in the microeconomic domain M + (ω) of Subsection 5.3, the Equal Split Guarantee is clearly undominated. We conjecture that in the domains M ± (Ω) the B&C Guarantees Γ θ (Subsection 5.2) are undominated as well.

7 Appendix: proof of Lemma 4 1). First statement. Recall that we can replace in definition (5) the equalities like θ(T ) = t 1 with inequalities θ(T ) ≤ t 1 . We check first that the correspondence t → {S ∈ B|θ(S) ≤ t} is continuous. Upper hemi continuity follows by the continuity of θ. For lower hemi continuity pick a sequence t n converging to t and S ∈ B s.t. θ(S) ≤ t. If t n has a decreasing subsequence, we set S n = S so that θ(S n ) ≤ t n and S n converges to S. If t n has an increasing subsequence we construct an inclusion increasing sequence S m converging to S and s.t. |S m | < |S| for all m: because θ increases strictly, so does the

1 2 (x 2 +y 2 )≤2t u( 1 -x 2 , 1 -y 2 ) = min 1 2

 11211 (x+y)≥1-2t u(x, y)

In the simple sense of implementation described in the last paragraph of this section.

Maybe more than one such assignment is feasible; any choice implements the target Guarantee, which is all we need.

If the manna is atomic and utilities are not necessarily additive, it is easy to construct examples showing that all six orderings of M axmin, minM ax, and 1 n u(Ω) are possible.

For instance in the interval model, the first divider can find an equipartition made of adjacent intervals (by our Lermma 1), but the next agent called to divide is typically left with disconnected intervals.

Divide and Choose implements the utility profile (minM ax(u i ; 2), M axmin(u j ; 2)): this gap can be closed for one agent.

After Step 1 an agent can secure his M axmin utility for the smaller manna S among m agents, but this may be below the M axmin utility in the initial problem.

sequence θ(S m ) converging to θ(S), therefore we can pick subsequences S p of S m and t p of t n s.t. θ(S p ) ≤ t p , as desired.

Next we apply the Maximum Theorem twice. The first one to show that the function (T,

2). Second statement. For simplicity we assume n = 3, the general proof is entirely similar. Fixing u and t 1 there is some t 2 such that u θ (t 1 ; t 2 ) = u θ (t 2 ; 1). This is because of the monotonicity properties of u θ and of the inequalities u θ (t 1 ; t 1 ) = 0 ≤ u θ (t 1 ; 1) and u θ (t 1 ; 1) ≥ 0 = u θ (1; 1). This common value is unique (though t 2 may not be) and defines a function g(t 1 ) = u θ (t 1 ; t 2 ) = u θ (t 2 ; 1). It is easy to check from the continuity and monotonicity properties of u θ that g is weakly decreasing and continuous. Then we find in the same way t 1 s.t. g(t 1 ) = u θ (0; t 1 ).

Check finally that if

* ; and so on until we reach a contradiction with the fact that both τ and τ * are in Υ(n).

Finally, the optimal sequence t k increases in k, strictly if u is not everywhere zero because u(t, t) = 0 for all t.


Daniel Massart

Alfonso Sorrentino

Differentiability of Mather's average action and integrability on closed surfaces

In this article we study the differentiability of Mather's β-function on closed surfaces and its relation to the integrability of the system.

Dans cet article nous étudions la différentiabilité de la fonction β de Mather sur surfaces et ses conséquences sur l'intégrabilité du système.

Introduction

In the study of Tonelli Lagrangian and Hamiltonian systems, a central role in understanding the dynamical and topological properties of the action-minimizing sets (also called Mather and Aubry sets), is played by the so-called Mather's average action (sometimes referred to as β-function or effective Lagrangian), with particular attention to its differentiability and nondifferentiability properties. Roughly speaking, this is a convex superlinear function on the first homology group of the base manifold, which represents the minimal action of invariant probability measures within a prescribed homology class, or rotation vector (see [START_REF] Arnaud | Fibrés de Green et régularité des graphes C 0 -Lagrangiens invariants par un flot de Tonelli[END_REF] for a more precise definition). Understanding whether or not this function is differentiable, or even smoother, and what are the implications of its regularity to the dynamics of the system is a formidable problem, which is still far from being completely understood. Examples of Lagrangians admitting a smooth β-function are easy to construct. Trivially, if the base manifold M is such that dim H 1 (M ; R) = 0 then β is a function defined on a single point and it is therefore smooth. Furthermore, if dim H 1 (M ; R) = 1 then a result by M. Dias Carneiro [START_REF] Carneiro | On minimizing measures of the action of autonomous Lagrangians[END_REF] allows one to conclude that β is differentiable everywhere, except possibly at the origin. As soon as dim H 1 (M ; R) ≥ 2 the situation becomes definitely less clear and the smoothness of β becomes a more "untypical" phenomenon. Nevertheless, it is still possible to find some interesting examples in which it is smooth. For instance, let H : T * T n -→ R be a completely integrable (in the sense of Liouville) Tonelli Hamiltonian system, given by H(x, p) = h(p), and consider the associated Lagrangian L(x, v) = ℓ(v) on TT n . It is easy to check that in this case, up to identifying H 1 (T n ; R) with R n , one has β(h) = ℓ(h) and therefore β is as smooth as the Lagrangian and the Hamiltonian are. One can weaken the assumption on the completely integrability of the system and consider C 0 -integrable systems, i.e., Hamiltonian systems that admit a foliation of the phase space by disjoint invariant continuous Lagrangian graphs, one for each possible cohomology class (see Definition 1). It is then possible to prove that in this case the associated β function is C 1 (see Lemma 2). These observations arise the following question: with the exception of the mentioned trivial cases, does the regularity of β imply the integrability of the system?

In this article we address the above problem in the case of Tonelli Lagrangians on closed surfaces, not necessarily orientable. We prove the following.

Main Results. Let M be a closed surface and L : TM -→ R a Tonelli Lagrangian.

(i) If M is not the sphere, the projective plane, the Klein bottle or the torus, then β cannot be

C 1 on H 1 (M, R) [Proposition 3].
(ii) If M is the sphere, the projective plane or the Klein bottle, then the Lagrangian cannot be

C 0 -integrable [Proposition 4]. (iii) If M is the torus, then β is C 1 if and only if the system is C 0 -integrable [Theorem 1].
Moreover in Corollary 1 we shall deduce several information on the dynamics of C 0 -integrable systems and in section 3.1 we discuss the case of mechanical Lagrangians on the two-torus and show that in this case: β is C 1 if and only if the system is the geodesic flow associated to a flat metric on T 2 [Proposition 6].

Acknowledgements. The authors are particularly grateful to Victor Bangert, Patrick Bernard, and Albert Fathi for several useful discussions. This work has been partially funded by the ANR project "Hamilton-Jacobi et théorie KAM faible". A.S. also wishes to acknowledge the support of Fondation Sciences Mathématiques de Paris.

Mather's average action and Aubry-Mather theory

Let us start by recalling some basic facts about Mather's theory for Tonelli Lagrangians. Let M be a compact and connected smooth n-dimensional manifold without boundary. Denote by TM its tangent bundle and T * M the cotangent one and denote points in TM and T * M respectively by (x, v) and (x, p). We shall also assume that the cotangent bundle T * M is equipped with the canonical symplectic structure, which we shall denote ω. A Tonelli Lagrangian is a C 2 function L : TM → R, which is strictly convex and uniformly superlinear in the fibers; in particular this Lagrangian defines a flow on TM , known as Euler-Lagrange flow Φ L t , whose integral curves are solutions of d dt ∂L ∂v (x, v) = ∂L ∂x (x, v). Let M(L) be the space of compactly supported probability measures on TM invariant under the Euler-Lagrange flow of L. To every µ ∈ M(L), we may associate its average action

A L (µ) = TM L dµ .
It is quite easy to check that since µ is invariant under the Euler-Lagrange flow, then for each f ∈ C 1 (M ) we have df (x) • v dµ = 0. Therefore we can define a linear functional

H 1 (M ; R) -→ R c -→ TM η c (x) • v dµ ,
where η c is any closed 1-form on M whose cohomology class is c. By duality, there exists

ρ(µ) ∈ H 1 (M ; R) such that TM η c (x) • v dµ = c, ρ(µ) ∀ c ∈ H 1 (M ; R)
(the bracket on the right-hand side denotes the canonical pairing between cohomology and homology). We call ρ(µ) the rotation vector of µ. It is possible to show [START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF] that the map ρ : M(L) -→ H 1 (M ; R) is surjective and hence there exist invariant probability measures with any given rotation vector. Let us consider the minimal value of the average action A L over the set of probability measures with rotation vector h (this minimum exists because of the lower semicontinuity of the action functional):

β : H 1 (M ; R) -→ R h -→ min µ∈M(L): ρ(µ)=h A L (µ) . (1)
This function β is what is generally known as Mather's β-function. A measure µ ∈ M(L) realizing such a minimum amongst all invariant probability measures with the same rotation vector, i.e., A L (µ) = β(ρ(µ)), is called an action minimizing measure with rotation vector ρ(µ). The β-function is convex, and therefore one can consider its conjugate function (given by Fenchel's duality) α : H 1 (M ; R) -→ R defined by

α(c) := max h∈H1(M ;R) ( c, h -β(h)) = -min h∈H1(M ;R) (β(h) -c, h ) = = -min µ∈M(L) (A L (µ) -c, ρ(µ) ) = -min µ∈M(L) A L-ηc (µ),
where η c is any smooth closed 1-form on M with cohomology class c. Observe that the modified Lagrangian Lη c (η c can be also seen as a function on TM :

η c (x, v) := η c (x) • v) is still of
Tonelli type and has the same Euler-Lagrange flow as L (it follows easily from the closedness of η c ). Nevertheless, invariant probability measures that minimize the action functional A L-ηc change according to the chosen cohomology class. A measure µ ∈ M(L) realizing the minimum of A L-ηc (withouth any constraint on the rotation vector) is called c-action minimizing. This leads to the definition of a first important family of invariant subsets of TM :

• for a homology class h ∈ H 1 (M ; R), we define the Mather set of rotation vector h as:

M h := {supp µ : µ is action minimizing with rotation vector h} ;

• for a cohomology class c ∈ H 1 (M ; R), we define the Mather set of cohomology class c as:

M c := {supp µ : µ is c -action minimizing} .
The relation between these sets is described in the following lemma. To state it, let us recall that, like any convex function on a finite-dimensional space, Mather's β function admits a subderivative at any point h ∈ H 1 (M ; R), i.e., we can find c ∈ H 1 (M ; R) such that

∀h ′ ∈ H 1 (M ; R), β(h ′ ) -β(h) ≥ c, h ′ -h .
As it is usually done, we denote by ∂β(h) the set of c ∈ H 1 (M ; R) which are subderivatives of β at h, that is, the set of c's which satisfy the above inequality (this set is also called the Legendre transform of h). By Fenchel's duality, we have

c ∈ ∂β(h) ⇐⇒ c, h = α(c) + β(h).
(

) 2
Lemma 1. Let h, c be respectively an arbitrary homology class in H 1 (M ; R) and an arbitrary cohomology class in H 1 (M ; R). We have

(1) M h ∩ M c = ∅ ⇐⇒ (2) M h ⊆ M c ⇐⇒ (3) c ∈ ∂β(h) .
Proof. The implication (2) =⇒ ( 1) is trivial. Let us prove that (1) =⇒ ( 3). If M h ∩ M c = ∅, then there exists a c-minimizing invariant measure µ with rotation vector h. Let η c be a closed 1-form with [η c ] = c. From the definitions of α, β and rotation vector:

-α(c) = TM (L -η c ) dµ = TM L dµ -c, h = β(h) -c, h ;
since β and α are convex conjugated, then c is a subderivative of β at h. Finally, in order to show (3) =⇒ ( 2), let us prove that any action minimizing measure with rotation vector h is c-minimizing. In fact, if c ∈ ∂β(h) then β(h) = c, hα(c); therefore for any action minimizing measure µ with ρ(µ) = h and for any η c as above:

-α(c) = β(h) -c, h = TM (L -η c ) dµ.
This proves that µ is c-action minimizing and it concludes the proof.

Remark 1. One can also find a relation between the Mather sets corresponding to different cohomology classes, in terms of the strictly convexity of the α-function or, better, the lack thereof. The regions where α is not strictly convex are called flats: for instance the Legendre transform of α at c, denoted ∂α(c), which is the set of homology classes for which equality (2) holds, is an example of flat. It is possible to check that if two cohomology classes are in the relative interior of the same flat F of α, then their Mather sets coincide (see [START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF][START_REF] Massart | On Aubry sets and Mather's action functional[END_REF]). We denote by M(F ) the common Mather set to all the cohomologies in the relative interior of F .

In addition to the Mather sets, one can also construct another interesting family of compact invariant sets. We define the Aubry set A c of cohomology class c by looking at a special kind of global minimizers:

we say (x, v) ∈ T M lies in A c if there exists a sequence of C 1 curves γ n : [0, T n ] -→ M , such that • γ n (0) = γ n (T n ) = x for all n
• γn (0) and γn (T n ) tend to v as n tends to infinity

• T n goes to infinity with n • Tn 0 (L -η c + α(c))(γ n (t), γn (t)
) dt tends to 0 as n tends to infinity.

One can prove [START_REF] Mather | Variational construction of connecting orbits[END_REF][START_REF] Fathi | The Weak KAM theorem in Lagrangian dynamics[END_REF] that if (x, v) ∈ A c , then the curve γ(t) := πΦ L t , where π : TM -→ M denotes the canonical projection, is a c-global minimizer, that is, it minimizes on any compact time interval the action of Lη c , among all curves with the same endpoints and time length (see [START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF]); observe, however, that not all c-global minimizers can be obtained in this way. These action-minimizing sets that we have just defined, are such that M c ⊆ A c for all c ∈ H 1 (M ; R) and moreover one of their most important features is that they are graphs over M (Mather's graph theorem [START_REF] Mather | Action minimizing invariant measures for positive definite Lagrangian systems[END_REF][START_REF] Mather | Variational construction of connecting orbits[END_REF]), i.e., the projection along the fibers π| A c (L) is injective and its inverse π| A c (L)

-1 : π A c (L) -→ A c (L) is Lipschitz.
Hereafter we shall denote by M h , M c and A c the corresponding projected sets.

Another interesting characterization of the Aubry set is provided by weak KAM theory [START_REF] Fathi | The Weak KAM theorem in Lagrangian dynamics[END_REF], in terms of critical subsolutions of Hamilton-Jacobi equation or, in a more geometric way, in terms of some special Lipschitz Lagrangian graphs. Let us consider the Hamiltonian system associated to our Tonelli Lagrangian. In fact, if one considers the Legendre transform associated to L, i.e., the diffeomorphism

L L : TM -→ T * M defined by L L (x, v) = (x, ∂L ∂v (x, v)), then it is possible to introduce a Hamiltonian system H : T * M → R, where H(x, p) = sup v∈TxM ( p, v - L(x, v)).
It is easy to check that H is also C 2 , strictly convex and uniformly superlinear in each fiber: H is also said to be Tonelli (or sometimes optical). Recall that the flow Φ H t on T * M associated to this Hamiltonian, known as the Hamiltonian flow of H, is conjugated -via the Legendre transform -to the Euler-Lagrange flow of L. Therefore one can define the analogue of the Mather and Aubry sets in the cotangent space, simply considering M * c := L L M c and A * c := L L A c . These sets still satisfy all the properties mentioned above, including the graph theorem. Moreover, they will be contained in the energy level {H(x, p) = α(c)}, where α : H 1 (M ; R) -→ R is exactly Mather's α-function introduced before. Using the results in [START_REF] Fathi | The Weak KAM theorem in Lagrangian dynamics[END_REF] it is possible to obtain a nice characterization of the Aubry set. As above, let η c be a closed 1-form with cohomology class c; we shall say that u ∈ C 1,1 (M ) is an η c -critical subsolution if it satisfies H(x, η c + d x u) ≤ α(c) for all x ∈ M . The existence of such functions has been showed by P. Bernard [START_REF] Bernard | Existence of C 1,1 critical subsolutions of the Hamilton-Jacobi equation on compact manifolds[END_REF]. If one denotes by S ηc the set of η c -critical subsolutions, then:

A * c = u∈Sη c {(x, η c (x) + d x u) : x ∈ M } . (3)
This set does not depend on the particular choice of η c , but only on its cohomology class.

Observe that since in (T * M, ω) there is a 1-1 correspondence between Lagrangian graphs and closed 1-forms, then we can interpret the graphs of these critical subsolutions as Lipschitz Lagrangian graphs in T * M and the Aubry set may be seen as their non-removable intersection.

Main results

In this section we prove the main results stated in the introduction. Let M be a closed surface, not necessarily orientable, L : TM -→ R a Tonelli Lagrangian on M and H : T * M -→ R the associated Hamiltonian.

Let us recall that a homology class h is said to be k-irrational, if k is the dimension of the smallest subspace of H 1 (M ; R) generated by integer classes and containing h. In particular, 1-irrational means "on a line with rational slope", while completely irrational stands for dim H 1 (M ; R)-irrational. Moreover, a homology h is said to be singular if its Legendre transform ∂β(h) is a singular flat, i.e., its Mather set M(∂β(h)) -see Remark 1 -contains fixed points. Observe that the set of singular classes, unless it is empty, contains the zero class and is compact.

For h ∈ H 1 (M ; R)\{0}, we define the maximal radial flat R h of β containing h as the largest subset of the half-line {th : t ∈ [0, +∞[} containing h (not necessarily in its relative interior) in restriction to which β is affine. The possibility of radial flats is the most obvious difference between the β functions of Riemannian metrics [START_REF] Massart | Stable norms of surfaces: local structure of the unit ball of rational directions[END_REF][START_REF] Balacheff | Stable norms of non-orientable surfaces[END_REF] and those of general Lagrangians. An instance of radial flat is found for instance in [START_REF] Carneiro | On the minimal action function of autonomous Lagrangians associated to magnetic fields[END_REF]. We define the Mather set M(R h ) as the union of the supports of all action minimizing measures with rotation vector th, for th ∈ R h .

Let h be a homology class. Assume h is 1-irrational. Then for all t such that th ∈ R h , th is also 1-irrational and ∂β(th) = ∂β(h) (see [START_REF] Massart | Aubry sets vs Mather sets in two degrees of freedom[END_REF]Lemma 17]). In particular, R h is contained in a flat of β. So Mather's Graph Theorem and [16, Lemma C.3] combine to say that M(R h ) is a union of pairwise disjoint periodic orbits, or fixed points, γ i , i ∈ I where I is some set, not necessarily finite.

We shall start with the following proposition, which generalizes a result by Bangert [START_REF] Bangert | Geodesic rays, Busemann functions and monotone twist maps[END_REF] and Mather [START_REF] Mather | Differentiability of the minimal average action as a function of the rotation number[END_REF] for twist maps and geodesic flows on the two-torus.

Proposition 1. Let L be a Tonelli Lagrangian on a closed surface M and let h ∈ H 1 (M ; R) be a non-singular 1-irrational homology class. Then, β is differentiable at h if and only if [=⇒] Since β is differentiable at h, let us denote c h := ∂β(h). From [START_REF] Massart | Aubry sets vs Mather sets in two degrees of freedom[END_REF]Theorem 3] it follows that M(R h ) = M c h = A c h and it is a union of periodic orbits. From this, one can deduce that:

M(R h ) = M . In that case, M(R h ) = M is foliated by closed extremals. Proof. [⇐=] Since M(R h ) = M , then β is differentiable at h. In fact, suppose that c, c ′ ∈ ∂β(h); then M(R h ) ⊆ M c and M(R h ) ⊆ M c ′ (
• for all c ′ = c h , M c h ∩ M c ′ = ∅; otherwise, M(R h ) ∩ M c ′ = ∅
and this would imply that c ′ ∈ ∂β(h) (Lemma 1), contradicting the differentiability of β at h.

• α is strictly convex at c h : it is an easy consequence of the disjointness of M c h from the other Mather sets and Remark 1.

In order to complete the proof, we need to show that A c h = M . If this were not true, then, there would exist an open region Γ in the complement of the A c h , whose boundary consists of two (minimizing) periodic orbits. Γ would be homologically non trivial, therefore one could find a closed non-exact 1-form on M whose support is disjoint from A c h . From [15, Theorem 1] (see [START_REF] Massart | Differentiability of Mather's beta function in low dimensions[END_REF]Theorem 2] for the non-orientable case), this would imply that c h is contained in the interior of a non-trivial flat of α, contradicting the strict convexity of α at c h . Remark 2. Observe that the above result is not true if h is singular. Indeed, take a vector field X on a closed surface Σ 2 of genus 2, which consists of periodic orbits, except for a singular graph with two fixed points and four hetero/homoclinic orbits between the two fixed points (see figure 1). One can embed it into the Euler-Lagrange flow of a Tonelli Lagrangian, given by L X (x, v) = 1 2 v -X(x) 2

x . It is possible to show (see for instance [START_REF] Fathi | Ludovic Rifford On the Hausdorff dimension of the Mather quotient[END_REF]) that Graph(X) is invariant and that in this case A 0 = Graph(X); therefore, the projected Aubry set A 0 is the whole surface Σ 2 , so β is differentiable at all homology classes in ∂α(0) (see [START_REF] Massart | On Aubry sets and Mather's action functional[END_REF]Theorem 1]). However, A 0 = Σ 2 is not foliated by closed extremals. For the sake of completeness, let us also recall that: Proposition 2. β is always differentiable at completely irrational homology classes.

It follows from [START_REF] Massart | On Aubry sets and Mather's action functional[END_REF]Corollary 3] (see [START_REF] Massart | Differentiability of Mather's beta function in low dimensions[END_REF]Theorem 2] for the non-orientable case).

Let us now recall the definition of C 0 -integrability (see also [START_REF] Arnaud | Fibrés de Green et régularité des graphes C 0 -Lagrangiens invariants par un flot de Tonelli[END_REF]). Definition 1. A Tonelli Hamiltonian H : T * M -→ R is said to be C 0 -integrable, if there exists a foliation of T * M made by invariant Lipschitz Lagrangian graphs, one for each cohomology class.

Lemma 2. Let M be a compact manifold of any dimension, L : TM -→ R a Tonelli Lagrangian and

H : T * M -→ R the associated Hamiltonian. If H is C 0 -integrable, then β is C 1 .
Proof. Suppose that H is C 0 -integrable. This means that the cotangent space T * M is foliated by disjoint invariant Lipschitz Lagrangian graphs. Let us denote by Λ c the invariant Lagrangian graph of such a foliation, corresponding to the cohomology class c. It is easy to check that each Λ c is the graph of a solution of Hamilton-Jacobi equation H(x, η c + du) = α(c), where η c is a closed 1-form on M with cohomology class c, and therefore from weak KAM theory [START_REF] Fathi | The Weak KAM theorem in Lagrangian dynamics[END_REF] it follows that for each c ∈ H 1 (M ; R) the Aubry set

A * c ⊆ Λ c . If for some h ∈ H 1 (M ; R) there exist c = c ′ such that c, c ′ ∈ ∂β(h), then M h ⊆ M c ∩ M c ′ (Lemma 1). But this implies that M c ∩ M c ′ = 0 and therefore Λ c ∩ Λ c ′ ⊇ A * c ∩ A * c ′ = 0,
which contradicts the disjointness of the Lagrangian graphs forming the foliation. Hence, β must be differentiable everywhere. on a closed, orientable surface M , the flats of β are contained in isotropic subspaces of H 1 (M ; R) with respect to the intersection symplectic form on H 1 (M ; R). In particular, when M = T 2 , all flats are radial. Lemma 4. Let L : TT 2 -→ R be a Tonelli Lagrangian. Assume that β is C 1 everywhere. Then zero is (possibly) the only singular class, and for every 1-irrational, nonzero homology class h, M h = T 2 , and M h is foliated by periodic orbits with the same homology class and minimal period.

Proof. First note that if a non-zero class h is singular, then the Mather set of R h contains a fixed point, so R h contains the homology of the Dirac measure on the fixed point, which is zero. This contradicts Proposition 3, which says that R h = {h}. Now take a non-zero, 1-irrational homology class h; so h is non-singular and by Proposition 1, M(R h ) = T 2 and M(R h ) is foliated by periodic orbits. Since R h = {h} by Proposition 3, we have M h = T 2 . It is well known that all leaves of a foliation of the two-torus by homologically non trivial closed curves are homologous. So there exists h 0 ∈ H 1 (T 2 ; Z) such that the projection to T 2 of any orbit contained in M h is homologous to h 0 . Besides, for each x ∈ T 2 , let T (x) be the minimal period of the periodic orbit γ x in M h through x. The homology class of the probability measure carried by γ x is T -1 h 0 . Now the fact that there are no non-trivial radial flats of β implies that T (x) is independent of x. Proposition 4. The torus is the only closed surface which admits a C 0 -integrable Hamiltonian.

Proof. First, no Hamiltonian on the sphere can be C 0 -integrable. Indeed, any Lagrangian graph is exact since the sphere is simply connected, and any two exact Lagrangian graphs intersect, because any C 1 function on the sphere has critical points.

Likewise, no Hamiltonian on the projective plane can be C 0 -integrable, for its lift to the sphere would be C 0 -integrable.

For the Klein bottle K, we need to work a little bit more. For each x ∈ K, let us define

F x : H 1 (K; R) ≃ R -→ T * x K ≃ R 2 c -→ Λ c (x),
where Λ c , for c ∈ H 1 (K; R), are the Lagrangian graphs foliating T * K. It is easy to check that F x is continuous and injective (as it follows from the disjointness of the Λ c 's). Moreover, if the Hamiltonian is C 0 -integrable, the map F x is surjective. Now there is no such thing as a continuous bijection from R to R 2 , so there is no C 0 -integrable Hamiltonian on the Klein bottle.

The same argument can be used for any surface with first Betti number > 2.

Finally, no Hamiltonian on the connected sum of three projective planes (first Betti number equal to 2) can be C 0 -integrable, for it would lift to a C 0 -integrable Hamiltonian on a surface of genus two. Theorem 1. Let L : TT 2 -→ R be a Tonelli Lagrangian on the two-torus. Then, β is C 1 if and only if the system is C 0 -integrable.

Proof.

[⇐=] It follows from Lemma 2. [=⇒] For each homology class h, let us denote c h := ∂β(h). If h is non-singular and 1-irrational, then Λ c h := A * c h is an invariant Lipschitz Lagrangian graph of cohomology class c h , which is foliated by periodic orbits of homology h.

Observe that such cohomology classes c h are dense in H 1 (M ; R). Indeed, 1-irrational nonsingular homology classes are dense in H 1 (M ; R) because 1-irrational homology classes are dense in H 1 (M ; R) and, by Lemma 4, zero is the only possibly singular one. On the other hand, since β is differentiable, the Legendre transform is a homeomorphism from H 1 (M ; R) to H 1 (M ; R).

Using the semicontinuity of the Aubry set in dimension 2 (see [START_REF] Bernard | On the Conley decomposition of Mather sets[END_REF]), we can deduce that for each c ∈ H 1 (M ; R) the Aubry set A * c projects over the whole manifold and therefore it is still an invariant Lipschitz Lagrangian graph, which we shall denote Λ c . Observe that all these Λ c 's are disjoint. This is a straightforward consequence of the differentiability of β. In fact if for some c = c ′ we had that Λ c ∩ Λ c ′ = 0, then M c ∩ M c ′ = 0; but this would contradict the differentiability of β at some homology class. It only remains to prove that the union is the whole T * M . Observe that for each c ∈ H 1 (M ; R), Λ c is the graph of the unique solution of the Hamilton-Jacobi equation H(x, η c + du c ) = α(c), where u c ∈ C 1,1 (M ) and η c a closed 1-form on M with cohomology class c. For each x 0 ∈ M , let us define

F x0 : H 1 (M ; R) ≃ R 2 -→ T * x0 M ≃ R 2 c -→ η c + d x0 u c .
It is easy to check that F x0 is continuous (actually locally Lipschitz); moreover, it is injective (as it follows from the disjointness of the Λ c 's). Therefore, F x0 (R 2) is open [START_REF] Luitzen | Zur invarianz des n-dimensionalen Gebiets[END_REF]. Using Ascoli-Arzelà's theorem, one can show that this image is also closed. In fact, let y k = F x0 (c k ) be a sequence in T *

x M converging to some y 0 . Since each family of classical solutions of Hamilton-Jacobi on which the α-function (i.e., the energy) is bounded gives rise to a family of functions with uniformly bounded Lipschitz constants, then there exist ũ ∈ C 1,1 (M ) and c ∈ H 1 (M ; R), such that c k + du c k → c + dũ uniformly. From the continuity of the α-function, it follows that H(x, c + d x ũ) = α(c). Since Λ c is the unique invariant Lagrangian graph with cohomology c (essentially because it coincides with the Aubry set, see [START_REF] Fathi | The Weak KAM theorem in Lagrangian dynamics[END_REF]), then Λ c = {(x, c + d x ũ : x ∈ M } and therefore y

0 = c + d x0 ũ = F x0 (c) ∈ F x0 (R 2 )
. This shows that F x0 (R 2 ) is also closed and therefore it is all of R 2 . Since this holds for all x 0 ∈ M , it follows that ∪ c Λ c = T * M .

We can deduce more information about the dynamics on a C 0 -integrable system. Corollary 1. Let H : T * M -→ R be a C 0 -integrable Hamiltonian on a two-dimensional closed manifold M . Then, M is diffeomorphic to T 2 . Moreover:

(i) for each 1-irrational homology class h, there exists an invariant Lagrangian graph foliated by periodic orbits with the same homology and minimal period;

(ii) for each completely irrational homology class, there exist an invariant Lagrangian graph on which the motion is conjugated to an irrational rotation on the torus or to a Denjoy type homeomorphism;

(iii) there exists a dense G δ set of (co)homology classes, for which the motion on the corresponding invariant torus is conjugated to a rotation;

(iv) as for the 0-homology class, there exists a C 1 invariant torus Λ c(0) = {(x, ∂L ∂v (x, 0) : x ∈ T 2 } consisting of fixed points.

Proof. If H is C 0 integrable, then β is C 1 (Lemma 2). By Proposition 4, M is diffeomorphic to the 2-torus.

(i) It is a consequence of Lemma 4. (ii) Let h be a completely irrational homology class and let c h = ∂β(h). We shall follow the discussions in [8, p. 1084] (see also [21, p. 66 et seqq.] for more technical details). The Hamiltonian flow on Λ c h induces a flow on T 2 without fixed points or closed trajectories. Thus, one can construct a non-contractible closed curve Γ, which is transverse to the flow. Using an argument à la Poincaré-Bendixon, it follows that all trajectories starting on Γ must return to it. Hence, one can define a continuous map from a compact subset of Γ to itself, which is order preserving and with irrational rotation number. Therefore, it is either conjugate to an irrational rotation or a Denjoy type homeomorphism. (iii) From ii), it is sufficient to show that the set of homology classes for which the Mather set projects over the whole torus is a dense G δ set; in fact if this is the case, the flow cannot be conjugated to a Denjoy type homeomorphism. Let us start by observing that this set is clearly dense since it contains all 1-irrational homology classes. The fact that it is also G δ follows from [START_REF] Fathi | Existence de difféomorphismes minimaux[END_REF]Corollaire 4.5], in which it is proven that the set of strictly ergodic flows on a compact set is G δ in the C 0 topology. One could also observe that since our Lagrangian is C 0 -integrable, by [1, Théorème 3], there is a dense G δ of cohomology classes with a C 2 weak KAM solution; and by a recent result of Fathi [START_REF] Fathi | RIMS meeting: Viscosity solutions of differential equations and related topics[END_REF], when the flow is of Denjoy type, there cannot be a C 2 weak KAM solution. (iv) Since the union of the Aubry sets foliates all the phase space, then any point (x, 0) will be contained in some Aubry set and therefore, using [START_REF] Fathi | Ludovic Rifford On the Hausdorff dimension of the Mather quotient[END_REF]Proposition 3.2], it follows that it is a fixed point of the Euler-Lagrange flow. Hence, the Dirac-measure δ (x,0) is invariant and action minimizing (since its support is contained in some Aubry set); clearly, such a measure has rotation vector equal to 0. Therefore, M 0 ⊇ T 2 × {0} and from the graph property it follows that they coincide. Then, Λ c(0) := A * c(0) = (x, ∂L ∂v (x, 0) : x ∈ T 2 , which is at least C 1 .

Remark 3. Although we believe that the motions on all invariant Lagrangian tori must be conjugated to rotations, we have not been able to show more than iii). It is not clear to us whether it is possible or not that a Denjoy type homeomorphism is embedded into a C 0integrable Hamiltonian system.

The case of mechanical Lagrangians

Recall that a mechanical Lagrangian is of the form L(x, v) = 1/2 g x (v, v) + f (x), where g is a Riemannian metric and f is a C 2 function on T 2 . In this case we can bridge the gap between C 0 -integrability and complete integrability (in the sense of Liouville), using Burago and Ivanov's theorem on metrics without conjugate points [START_REF] Burago | Riemannian tori without conjugate points are flat[END_REF].

Proposition 5. Let L be a C 0 -integrable mechanical Lagrangian on an n-dimensional torus. Then the potential f is identically zero and the metric g is flat. In particular, L is completely integrable. Proposition 6. Let L be a mechanical Lagrangian on an 2-dimensional torus, whose β-function is C 1 . Then the potential f is identically zero and the metric g is flat. In particular, L is completely integrable.

First we need the following lemma (see also [START_REF] Sorrentino | On the total disconnectedness of the quotient Aubry set[END_REF]Lemma 1]).

  Lemma 1). From the graph property of the Mather and Aubry sets it follows that M c = M c ′ and A c = A c ′ . In particular, if L L : TM -→ T * M denotes the Legendre transform associated to L, then A * c = L L ( A c ) and A * c ′ = L L ( A c ′ ) are invariant Lipschitz Lagrangian graphs and since they coincide, they must have the same cohomology class, i.e., c = c ′ .

Figure 1 :

 1 Figure 1: An example of singular Aubry set.

We can now prove the main results stated in the Section 1. Lemma 3. Let M be a closed surface other than the sphere, the projective plane, the Klein bottle or the torus, and let L : TM -→ R be a Tonelli Lagrangian. Then, β is not differentiable at any 1-irrational non-singular homology class.

Proof. If β is differentiable at some non-singular 1-irrational homology class, from Proposition 1 it follows that the Mather set corresponding to such a class projects over the whole manifold and consists of periodic orbits. But this leads to a contradiction, since it implies the existence of a fixed-point-free vector field on M .

When β is C 1 everywhere, we can improve on Proposition 1, by ruling out radial flats of β. Proposition 3. Let L be an autonomous Tonelli Lagrangian on the two-torus such that β is differentiable at every point of H 1 (T 2 ; R). Then for all h ∈ H 1 (T 2 ; R) \ {0}, we have R h = {h}. In particular, β is strictly convex.

Proof. First case:

Replacing, if we have to, h with an extremal point of R h , which is also 1-irrational, we may assume that R h = [λh, h] for some 0 ≤ λ ≤ 1. We want to prove that λ = 1. Pick:

• (x, v) ∈ TT 2 such that the probability measure carried by the orbit φ t (x, v) has homology λh,

• a sequence of real numbers t n ≥ 1 such that t n converge to 1

Then by Proposition 1, since β is differentiable at t n h, which is 1-irrational, we have M cn = M ; thus for every n there exists a v n ∈ T x M such that (x, v n ) ∈ M cn , and moreover the orbit φ t (x, v n ) is periodic. By semicontinuity of the Aubry set and by the Graph Theorem, v n converges to v when n goes to infinity (in fact c n converges to c := ∂β(R h )). Let T and T n be the minimal periods of φ t (x, v) and φ t (x, v n ), respectively. If (x, v) is a fixed point we just set T := +∞. We now prove that lim inf T n ≥ T . Indeed, if some subsequence T n k := T k converged to T ′ < T , we would have φ T ′ (x, v) = (x, v), contradicting the minimality of T . If (x, v) is a fixed point, we have v = 0, so v n converges to zero, so T n tends to infinity. Let h 0 ∈ H 1 (T 2 ; Z) be a generator of Rh ∩ H 1 (T 2 ; Z) such that the probability measures carried by the orbits φ t (x, v) and φ t (x, v n ) have homologies T -1 h 0 = λh and T -1 n h 0 , respectively. Now if λ < 1, since lim inf T n ≥ T , for n large enough there would exist a c n -minimizing measure with homology in [λh, h). This means that the radial flats R h and R tnh overlap, in other words, t n h ∈ R h . This contradicts the fact that R h = [λh, h], hence λ = 1.

Second case: h is 2-irrational, that is, completely irrational. Then any action minimizing measure with rotation vector h is supported on a lamination of the torus without closed leaves. Any such lamination is uniquely ergodic, in particular h is not contained in any non-trivial flat of β, radial or not, regardless of the Lagrangian.

The statement about the differentiability of β implying its strict convexity is now just a consequence of the fact, observed by M. Dias Carneiro in [START_REF] Carneiro | On minimizing measures of the action of autonomous Lagrangians[END_REF], that for an autonomous Lagrangian Lemma 5. Let

• M be a closed manifold of any dimension

• L be an autonomous Tonelli Lagrangian on M , such that L(x, v) = L(x, -v) for all (x, v) in T M .

Then, the Aubry set A 0 consists of fixed points of the Euler-Lagrange flow.

Proof. Take (x, v) ∈ A 0 . Then, by [START_REF] Fathi | The Weak KAM theorem in Lagrangian dynamics[END_REF] there exists a sequence of

Then, since L is symmetrical, Tn 0 (L(δ n , δn ) + α(0))dt -→ 0 as n -→ +∞, which proves that (x, -v) ∈ A 0 (L). Therefore, by Mather's Graph Theorem, v = 0, so (x, v) lies in the zero section of T M . Now, by [13, Proposition 3.2], for any Lagrangian, the intersection of A 0 with the zero section of T M consists of fixed points of the Euler-Lagrange flow. This proves the lemma. Now let us assume that the Lagrangian is mechanical. Then, the only fixed points of the Euler-Lagrange flow are the critical points of the potential f , and the only minimizing fixed points are the minima of f . So if f is not constant, the Lagrangian cannot be C 0 -integrable. Furthermore, since the Lagrangian is C 0 -integrable, every orbit is minimizing, in particular, there are no conjugate points. So by Burago and Ivanov's proof of the Hopf Conjecture [START_REF] Burago | Riemannian tori without conjugate points are flat[END_REF], the metric g is flat. This proves Proposition 5. Proposition 6 is now just a consequence of Theorem 1.