Charles Lumet

Sylvain Bouveret

Michel Lemaître

Fair Division of Indivisible Goods under Risk

We consider the problem of fairly allocating a set of m indivisible objects to n agents having additive preferences over them. In this paper we propose an extension of this classical problem, where each object can possibly be in bad condition (e.g broken), in which case its actual value is zero. We assume that the central authority in charge of allocating the objects does not know beforehand the objects conditions, but only has probabilistic information. The aim of this work is to propose a formal model of this problem, to adapt some classical fairness criteria to this extended setting, and to introduce several approaches to compute optimal allocations for small instances as well as sub-optimal good allocations for real-world inspired allocation problems of realistic size.

INTRODUCTION

The problem of allocating a set of indivisible objects to a set of agents arises in a wide range of applications including auctions, divorce settlements, frequency allocation, airport traffic management, scheduling, courses allocation, multiagent resource allocation and resourcesharing in general. In such problems, one usually needs to find fair solutions, where fairness refers to the need for compromises between the agents often conflicting preferences for the objects.

In most fair division problems, it is assumed that objects conditions are perfectly known when agents value them. However, it often happens that the actual value or utility of an object for an agent is only discovered after the allocation has been decided. As a toy example, let the objects be bottles of wine to be shared amongst a set of agents. The wine in each bottle can be corked, but this is not known before opening (which happens only after the bottles have been allocated). How can this uncertainty, which also arises in numerous variants of the aforementioned real-world problems, be taken into account ? In this paper we present a simple variant of the multiagent resource allocation problem (see e.g. [START_REF] Chevaleyre | Issues in multiagent resource allocation[END_REF] for a survey on this topic) in which the decision-maker has probabilistic information about the objects conditions, conditions which affect agent utilities.

Uncertainty (or, more precisely, risk) issues in collective decision making have been studied before, as in the microeconomical works by Myerson [START_REF] Myerson | Utilitarianism, egalitarianism, and the timing effect in social choice problems[END_REF] and more recently Gajdos and Tallon [START_REF] Gajdos | Fairness under uncertainty[END_REF]. However, these works focus on continuous allocation spaces (divisible "objects") and leave aside computational issues. Risk management in (combinatorial) auctions has also been studied (for example in [START_REF] Holland | Robust solutions for combinatorial auctions[END_REF]), more precisely the influence of potential bid withdrawals in terms of loss of total revenue for the auctioneer; but to the best of our knowledge, fairness issues are not considered. Finally, uncertainty in vote (which is another kind of collective decision problem) has been investigated in some recent papers. Yet, in most of these, uncertainty stands for the incomplete knowledge of the decider about the agents' preferences (see e.g. [START_REF] Bachrach | Probabilistic possible winner determination[END_REF]). One notable exception is the work by Lu and Boutilier [START_REF] Lu | The unavailable candidate model : A decisiontheoretic view of social choice[END_REF] which deals with a voting problem where each candidate may withdraw from the election.

In this article, three main assumptions are made. (i) The allocation is centralized, that is, it is decided and computed by a central benevolent authority, according to the agents' preferences. (ii) Each object can only be in two possible conditions: good or bad. The actual condition of an object is only known with a given probability when the allocation is decided, but is known for sure after the objects have been allocated. (iii) The agents have (subjective) additive utility preferences over the objects.

Even though this framework seems restrictive, we claim that it is worth studying it because first, additivity is very natural as soon as preferences over sets of objects have to be represented in a compact way (e.g, the well-known Santa-Claus fair division problem [START_REF] Bansal | The santa claus problem[END_REF] is based on additive preferences); second, in many real-world problems, uncertainty can be defined "object-wise" and thus can be naturally modeled as we do; lastly, as we will see, our framework raises non trivial computational issues, despite its apparent simplicity.

This article is structured as follows. In Section 2, we describe our framework for fair division of indivisible objects under risk. In Section 3 we propose some extensions of classical fairness criteria based on collective utility functions and on fair share guarantee and explore their theoretical properties. Finally, we propose in Section 4 some practical methods to compute optimal and approximated fair allocations and we give some experimental results.

MODEL

In the following, we use lower case bold font to represent vectors and upper case bold font to represent matrices.

A finite set of indivisible objects O = {1, . . . , m} must be allocated by a central authority to a finite set of agents A = {1, . . . , n}. An allocation is a vector of shares π = π1, . . . , πn where πi ⊆ O, and j ∈ πi if and only if object j has been given to agent i. The set of feasible allocations is F = {π, i = i ′ ⇒ πi ∩ π i ′ = ∅} (an object cannot be given to more than one agent). We further denote by π0 = O \ i∈A πi the set of non allocated objects, if any.

Each object can be either in good or bad condition. The objects' conditions are known only after the allocation has been made, but the decision-maker is nevertheless given probabilistic information: a vector p ∈ [0; 1] m maps each object j to its probability pj to be in good condition; these probabilities are assumed to be independent. Let S = 2 m be the set of the possible states of nature, and good(s) the set of objects in good condition when state of nature s happens. We thus have ∀s ∈ S, Pr(s) = j∈good(s) pj j / ∈good(s) (1pj). The agents' preferences for the objects are numerically expressed by weights: wi,j ∈ R + represents the utility of object j in good condition for agent i. A weight of zero means that the agent is not interested in the object. For the agent i, the individual utility of the allocation π if the state of nature s happens is defined as ui(π, s) def = j∈good(s)∩π i wi,j. In other words, we assume that agents have additive preferences over the objects: an agent individual utility for an allocation and a state of nature is given by the sum of the weights of the objects in good condition received by said agent and each object in bad condition brings no extra utility.

To sum up, an instance of our problem is given by a tuple P = (A, O, p, W), where A = {1, . . . , n} is a set of agents, O = {1, . . . , m} is a set of objects, p ∈ [0; 1] m expresses the probability for each object to be in good condition, and W is the n-lines m-columns matrix of weights given to the objects by the agents.

Example 1 Table 1 shows an instance of our problem, with the probabilities of each possible state of nature (line [START_REF] Bachrach | Probabilistic possible winner determination[END_REF]) and utility profiles associated with a given allocation (lines ( 3) and ( 4)).

3 FAIRNESS CRITERIA UNDER RISK

Ex-post vs ex-ante collective utilities

A classical way to define the quality of an allocation is to aggregate the agents' individual utilities with a commutative and increasing collective utility function (CUF) G : (R + ) n → R + , which measures social welfare. A general survey on CUF can be found in [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF].

In this paper, we will focus on the following ones:

• utilitarian and egalitarian CUF:

G u def = and G e def = min; • Nash CUF: G n def = ; • Ordered Weighted Averages (OWAs) [21]: G ω (u) def = n i=1 ωiu ↑ i , where n i=1 ωi = 1, ωi ≥ 0 ∀i, and u ↑ is a permutation of u s.t. u ↑ 1 ≤ • • • ≤ u ↑ n ; • Sums of Powers 4 (SPs) [17]: G p (u) def = sign(p) n
i=1 u p i for p = 0, and G 0 (u) def = n i=1 log(ui). OWAs and SPs provide two families of compromises between the utilitarian and egalitarian CUF: the first one can be represented 5 by G (1/n,1/n,...,1/n) or G 1 and the second one by G (1,0,...,0) or G p , with p → -∞ (more precisely, this last aggregation function represents the leximin preorder, which refines the egalitarian CUF). Moreover, the Nash CUF can be represented by G 0 . We must also note that most of these operators only make sense if the individual utilities are normalized (in our case, imposing j∈O wi,j = j∈O w i ′ ,j ∀i, i ′ is a reasonable way to do it -see e.g [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF] for other normalization methods). In the following we will write Gi∈Aui for G(u).

Since the actual state of nature is unknown before the allocation is chosen, utilities must be aggregated in all different possible states of nature. For this purpose we use the expected utility -other choices are possible, such as the min (pessimistic) or max (optimistic) operators, but we stand here on the most natural way of doing this aggregation. Depending on whether aggregation is first made over agents and then over states of nature or the other way around, we obtain two different functions [START_REF] Harsanyi | Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility[END_REF][START_REF] Myerson | Utilitarianism, egalitarianism, and the timing effect in social choice problems[END_REF]: acu : F → R + , defined in (1), is called ex-ante collective utility and pcu :

F → R + , defined in (2) is called ex-post collective utility. ∀π ∈ F , acu(π) def = Gi∈A s∈S Pr(s) • ui(π, s) (1)
∀π ∈ F , pcu(π)

def = s∈S Pr(s) • (Gi∈Aui(π, s)) (2)
Defining some expected weights wi,j def = pjwi,j, Proposition 1 shows that the ex-ante collective utility can be written as the collective utility of a risk-free equivalent instance (proof is easy thus omitted).

Proposition 1 Let ũi(π) def =
j∈π i wi,j be the expected utility of agent i for the allocation π. Then ∀π ∈ F, acu(π) = Gi∈A ũi(π).

Properties of ex-post and ex-ante utilities

We might wonder if we can find any relation between ex-ante and expost collective utilities. Actually, the following (in)equalities follow immediately from the definition of convexity, linearity, concavity:

Proposition 2 Let G be a CUF. Then ∀π, pcu(π) ≤ acu(π) (resp. ≥, =) if and only if G is concave (resp. convex, linear).
This proposition shows that determining whether the ex-post utility is greater than the ex-ante utility comes down to analyzing the concavity of the collective utility function, which is not completely straightforward for standard operators. We will give here several results about the classical CUF that favor equity in the solution, more formally, on those that promote Pigou-Dalton transfers [START_REF] Dalton | The measurement of the inequality of incomes[END_REF][START_REF] Pigou | Wealth and Welfare[END_REF], that is, utility transfers from wealthier agents to poorer ones.

Definition 1 (Pigou-Dalton transfer) Let u and u ′ be two utility vectors. u ′ is obtained by a Pigou-Dalton transfer from u if and only if one can find a couple of distinct agents (i1, i2), i1 = i2 such that (i) the sum of their utilities remains unchanged:

ui 1 +ui 2 = u ′ i 1 +u ′ i 2 (ii) inequalities decrease: |u ′ i 1 -u ′ i 2 | < |ui 1 -ui 2 | (iii) other agents utilities remain unchanged: ∀i ∈ A \ {i1, i2}, ui = u ′ i .
A CUF is said to reduce inequalities if for all u, u ′ , G(u ′ ) ≥ G(u) as soon as u ′ is obtained by Pigou-Dalton transfer from u. Note that this property is also called Schur-concavity in the theory of majorization (see e.g [START_REF] Marshall | Inequalities: Theory of Majorization And Its Applications[END_REF]).

We will now show that reducing inequalities entails concavity for a general set of CUF, namely the separable ones (see e.g [START_REF] Moulin | Axioms of Cooperative Decision Making[END_REF]).

Definition 2 (Separability) A CUF G is said to be separable if and only if it exists an increasing function

g : R + → R + s.t., for each utility vector u ∈ R + n , G(u) = n i=1 g(ui).
Proposition 3 Let G be a separable CUF reducing inequalities. Then, G is concave, that is, the following inequality stands:

∀π ∈ F , pcu(π) ≤ acu(π) (3)
The proof of this proposition follows rather directly from Jensen's inequality. Now, even if a wide range of CUF are separable (for example the sums of powers), it is not the case for the OWA. However, it appears that any OWA reducing inequalities is concave :

Proposition 4 Let G ω be an OWA reducing inequalities. Then G ω is concave, that is, Inequality (3) also stands.
We prove this using two lemmas (the proof of Lemma 1 is easy, thus omitted due to lack of space).

Lemma 1 G ω reduces inequalities if and only if

ω1 ≥ • • • ≥ ωn.
Lemma 2 Let u = (u1, . . . , un) a vector, σ a permutation of {1, . . . n} s.t. ∀i < j,u σ(i) ≤ u σ(j) , and ω a vector of sorted weights: Proof We can prove the result by induction on n. The base case (n = 1) is immediate: σ is the identity and the sum equals 0. Suppose that the lemma is true for every vector u and ω of dimension n -1. Let u and ω be two vectors of dimension n satisfying the conditions of Lemma 2, and let σ be a permutation sorting the components of u. Let t = σ -1 (n) (thus n = σ(t)). The following inequalities stand: ωt ≥ ωn(4) and u σ(t) = un ≤ u σ(n) [START_REF] Broome | Uncertainty and fairness[END_REF].

ω1 ≥ ω2 ≥ • • • ≥ ωn. Then n i=1 (ω σ(i) -ωi)u σ(i) ≥ 0.
Focusing on the sum components that contain t and n, we obtain:

(ω σ(t) -ωt)u σ(t) + (ω σ(n) -ωn)u σ(n) = (ω σ(n) -ωt)u σ(n) + (ωt -ωn)(u σ(n) -un)
≥0 (from inequalities (4) and ( 5)) [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF] Now let σ ′ be the permutation of {1, . . . , n -1} defined by:

σ ′ : i → σ(n) if i = t σ(i) otherwise
We can prove, by using Equation ( 6), definition of σ, and induction hypothesis:

n i=1 (ω σ(i) -ωi)u σ(i) ≥ n-1 i=1 (ω σ ′ (i) -ωi)u σ ′ (i) ≥ 0,
which proves the hypothesis at rank n, and completes the proof.

Proof (Proposition 4)

Let G ω be an OWA that reduces inequalities. By Lemma 1, ω1 ≥ ω2 ≥ • • • ≥ ωn. Let π be an allocation, and as in Proposition 1, ũi(π) = s∈S Pr(s)ui(π, s) agent i's expected utility. Suppose w.l.o.g that ũ1(π) ≤ ũ2(π) ≤ • • • ≤ ũn(π) (we can permute the agents if it is not the case). For all s ∈ S let σs be a permutation such that ∀i < i ′ , u σs(i) (π, s) ≤ u σs(i ′ ) (π, s). We have acu(π) = n i=1 s∈S Pr(s)ωiui(π, s), and pcu(π) = n i=1 s∈S Pr(s)ωiu σs(i) (π, s). Thus:

acu(π) -pcu(π) = s∈S Pr(s) × n i=1 ((ω σs(i) -ωi) • u σs(i) (π, s)
Applying Lemma 2 on vectors u(π, s) and ω, and on permutation σs, one obtains immediately acu(π)pcu(π) ≥ 0.

We can notice that Propositions 3 and 4 immediately entail that the inequality pcu ≤ acu holds for the egalitarian and utilitarian CUF (actually pcu = acu in the utilitarian case).

The Nash CUF case kind of lies in-between: if we stick to the original definition (G = ), the inequality pcu ≤ acu does not hold. Consider for example the two vectors x = (1, 1) and y = (3, 3). We have 0.5×(1×1+3×3) = 5 ≥ (0.5×(1+3))×(0.5×(1+3)) = 4, which proves this CUF is not concave (it can be shown that it is not convex either). Yet, if we consider the representation of the Nash CUF as a SP operator G 0 , we have proved earlier its concavity, and thus the inequality pcu ≤ acu holds. This example shows that the latter property is not inherent to a social welfare ordering, but rather to its chosen numerical representation.

Fair share guarantee under risk

The optimization of CUF focuses on the search for the best allocations (for a particular meaning of what "best" is), which can be very demanding. Another approach is to look for allocations that satisfy a given decision criterion. One prominent approach, defended by [START_REF] Steinhaus | The problem of fair division[END_REF], is based on the fair share principle which is defined as follows in a risk-free setting:

Definition 3 An allocation π satisfies the fair share test if and only if for all i, ui(π) ≥ 1/n m j=1 wi,j. The fair share test is also known as proportionality principle, since it is based on the fact that each agent considers that she is entitled to at least 1/n of what she considers to be the total value of the resource to share. One appealing property of this test is its independence on the individual utility scales, so there is no need to bother about normalization of individual utilities.

The fair share test can be extended in several ways to risk. The ex-ante fair share test is a straightforward extension: Definition 4 An allocation π satisfies the ex-ante fair share test if and only if for all i, ũi(π) ≥ 1/n m j=1 wi,j. In other words, ensuring ex-ante fair share means that each agent is considered happy as soon as she gets at least her entitlement of expected utility. Now, applying the same argument to define ex-post fair share leads to the following criterion: an allocation passes the ex-post fair share test if and only if it passes the fair share test in every state of the world. As soon as for a given state (may it have the tiniest non zero probability) an agent only gets objects in bad state, while the other ones are in good state, the allocation will not pass the test. Hence, for most instances, no allocation will pass the test, which argues in favor of a less demanding criterion. A possibility is to maximize the probability to satisfy fair share, instead of trying to ensure it in each state of the world.

Definition 5

The ex-post probability of fair share of a given allocation π is defined as follows:

ϕ p (π) def = s∈S Pr(s) min i∈A (ϕi(π, s)), with ϕi(π, s) = 1 if ui(π, s) ≥ 1/n j∈good(s) wi,j, 0 otherwise.
The value ϕi(π, s) indicates whether agent i has her fair share in state s. The use of operator min comes from the definition of fair share test which is satisfied only if all the agents have their fair share.

We can notice that since ϕi(π, s) is a numerical value, depending on a pair (agent, state), we can use it exactly the same way we used individual utilities. Therefore, since we have defined an ex-post probability of fair share, we can also define the ex-ante version of this criterion 6 : Definition 6 The ex-ante probability of fair share of a given allocation π is defined as follows:

ϕ a (π) def = min i∈A s∈S
Pr(s)ϕi(π, s).

We might wonder if there are some links between the definition of ex-ante probability of fair share (Definition 6) and the ex-ante fair share test (Definition 4). It turns out that even if (ϕ a = 1) entails passing the ex-ante fair share test, passing the ex-ante fair share test does not guarantee a higher value of ϕ a : Proposition 5 For all allocation π, (ϕ a (π) = 1) ⇒ π satisfies the ex-ante fair share test. However, for any pair (π, π ′ ), (π ′ satisfies the ex-ante fair share test and π does not) ⇒ ϕ a (π ′ ) > ϕ a (π).

Proof Let π be such that ϕ a (π) = 1. By Definition 6, ∀(i, s), ϕi(π, s) = 1, which entails ui(π, s) ≥ 1/n j∈good(s) wi,j. Then, ũi(π) = s∈S Pr(s)ui(π, s) ≥ s∈S Pr(s) × 1/n j∈good(s) wi,j = 1/n m j=1 wi,j, which proves the first implication. Now consider the following example:

W = j1 j2 i1 899 101 i2 991 9 p = 0.1, 0.9 π = {j2}, {j1} π ′ = {j1}, {j2}
We have ϕ a (π ′ ) = ϕ a (π) = 0.19. π passes the ex-ante fair-share test, but π ′ does not.

The following result comes directly from the concavity of min:

Proposition 6 For each π ∈ F, we have ϕ p (π) ≤ ϕ a (π).

Note also that both ϕ a and ϕ p are bounded above by 1, ϕ a = 1 ⇔ ϕ p = 1. It corresponds to the case where the fair share test is verified in each state of the world.

Finally, it can be noticed that in the risk-free case there is an interesting correlation between egalitarianism and fair share: if the set of allocations passing the fair share test is non empty, every optimal allocation will pass it. We will show that it is still the case for ex-ante fair share test and egalitarianism, but not for ϕ p and egalitarianism: maximizing ex-post egalitarian CUF may lead to sub-optimal allocations concerning ex-post probability of fair share. Proposition 7 Let (A, O, p, W) be an instance of the allocation problem, where the weight matrix is normalized in expectation (i.e ∀i, i ′ , j∈O wi,j = j∈O wi ′ ,j ). If the set of allocations passing the ex-ante fair share test is non empty, then all the ex-ante egalitarian optimal allocations will pass it. However, the intersection between the set of ex-post egalitarian optimal allocations and the set of allocations maximizing ϕ p may be empty.

Proof The proof concerning the ex-ante case is a direct extension of the result in the risk-free setting. Concerning the ex-post case, we can consider the following instance and allocations :

W = j1 j2 j3 i1 6 2 2 i2 4 1 5 p = 0.9, 0.5, 0.4 π = {j1, j2}, {j3} π ′ = {j1}, {j2, j3}
It can be proved that π ′ is the only one ex-post egalitarian optimal allocation. We have pcu(π) = 1.84, ϕ p (π) = 0.41, pcu(π ′ ) = 2.25 and ϕ p (π ′ ) = 0.39, which gives the counterexample needed.

COMPUTING FAIR ALLOCATIONS

In this section, we will introduce several approaches to compute fair allocations. Here, "fairness" will be interpreted in the sense of egalitarianism. Moreover, we will focus on ex-post egalitarianism, because (i) the choice of ex-post egalitarianism has been advocated by several authors, among which Adler and Sanchirico [START_REF] Adler | Inequality and uncertainty: Theory and legal applications[END_REF], Broome [START_REF] Broome | Uncertainty and fairness[END_REF], and Fleurbaey [START_REF] Fleurbaey | Assessing risky social situations[END_REF] and (ii) there is a very natural interpretation of the ex-post approach, as the decision a Bayesian decision-maker would naturally take if she were paid after uncertainty has been resolved, according to the (certain) collective utility of her decision.

Experimental setting

To test our algorithms, we will focus on a particular class of realworld problems, time-sharing problems, in which the use of a common resource, owned by several agents, has to be divided in time.

Managing a constellation of Earth observing satellites owned by several countries [START_REF] Lemaître | Exploiting a common property resource under a fairness constraint: a case study[END_REF], or planning the use of a telescope shared between world astronomers, are two examples of this class of problems.

In such problems, the agents' interests in using the resource might vary in time: for example, a country representative might be more interested to use an Earth observing satellite when it is located right above her country than when it is above the ocean. Moreover, the actual utility received by an agent for using the facility at a given time slot might depend on exogenous conditions which are not known beforehand : it could be for example the weather conditions which can seriously affect the quality of the satellite's observations.

Assuming that time is divided into a finite number of indivisible and non sharable time slots, the framework introduced in Section 2 is general enough to encompass this class of problems. Real-world instances of this kind share two typical features: (i) the agents' preferences are somewhat but not completely similar, that is, some objects will be fervently desired by all the agents, whereas some can be of interest for only one agent. (ii) contiguous time slots are strongly linked, which entails that they will likely share similar interest or probability of good condition 7 .

Algorithms introduced in this article are implemented using Java and run on random instances reproducing the features of aforementioned real-world problems (with normalized weights). Note that real-world instances typically involve a small number of agents (between 2 and 5) and a large number of objects (about 100).

Exact algorithms

Computing ex-post utility Before trying to compute an optimal allocation, we must be able to compute the collective utility for any given allocation. A naive algorithm for computing the ex-post collective utility, directly applying (2), would require the computation of the collective utility in each possible state (i.e each column in Table 1), that is, the enumeration of an exponential number of values. For this reason we strongly suspect that computing the ex-post egalitarian collective utility of a given allocation is #P-complete (which would mean that computing an optimal allocation is even harder). However, the precise complexity of this problem remains open.

The algorithm we use improves a naive branching algorithm for computing the ex-post collective utility of an allocation by using the fact that as soon as all the objects allocated to an agent are in bad condition, the utility of this agent is zero, and so is the collective utility, whatever conditions the remaining objects are in. In order to quickly "eliminate" such states of nature, whose enumeration is unnecessary, the algorithm browses the states of nature by fixing first the state of objects allocated to agents whose share contains few objects. Computing optimal ex-post allocations The optimization problem is tackled with a branch-and-bound algorithm. A basic upper bound acu(π) can be defined for each (partial) allocation π as the ex-ante utility of a (unfeasible) allocation which would allocate to all the agents the set π0 of objects that are currently not allocated: acu(π) def = mini∈A( j∈π i wi,j + j∈π 0 wi,j). acu only gives a rough approximation of pcu. We can provide a better upper bound by using a function which lies between pcu and acu. The idea is to compute utility in an ex-ante manner for a subset Oea of objects, and in an ex-post manner for the other ones (those in Oep = O \ Oea). In other words, we use mixed individual utilities:

mui(π, s, Oea) def = j∈Oep∩good(s) j∈π i wi,j + j∈Oea j∈π i wi,j (7)
The mixed collective utility is then defined as the ex-post collective utility from mixed individual utilities, i.e by replacing ui(π, s) by mui(π, s, Oea) in Equation 2. We have the following proposition:

Proposition 8 For each concave CUF G, ∀π ∈ F , ∀Oea ⊆ O, pcu(π) ≤ mcu(π, Oea) ≤ acu(π). Moreover, if G = min then 0 ≤ mcu(π, Oea) -pcu(π) ≤ j∈Oea p j pjw a(j)j
, where p j def = 1pj, and a(j) is the agent receiving j.

The proof is omitted due to lack of space. This proposition implies that (i) we can use mcu(π, Oea) as an upper bound of pcu(π), and (ii) if G = min this bound is tighter if Oea is built for an allocation π with objects minimizing pjpjw a(j)j .

We can also notice that the mixed utility only depends on the condition of objects in Oep. Hence, the number of states in the main summation of mcu is halved for each object added inside Oea, property of which algorithms will take profit.

As said earlier, our optimization algorithm is based on a branchand-bound approach, where nodes in the search space are the successive objects to allocate, and branches are the agents receiving them. Our algorithm is tailored for our fair division problem as follows. (i) We use the upper bound function acu to prune branches of the search tree during its exploration. (ii) We use dynamic heuristics: when selecting a new object to be allocated, the one preferred by the currently poorest (in expected utility) agent is chosen among those still left ; each object will be firstly allocated to this poorest agent. (iii) Since the computation of mcu is too time-consuming to be used as an efficient pruning mechanism, we use this bound with profit as a last possible cut when a complete allocation has been found, to avoid an unnecessary (and costly) ex-post collective utility computation. The size of Oea has been empirically fixed to m/3, which seems to be a good compromise between precision and computation time for the instances we tackle, and the objects to put in Oea are chosen according to Proposition 8. Results Table 2 shows the results for two versions of the branchand-bound algorithm: (a) only uses acu as an upper bound (i), where (b) also involves dynamic heuristics (ii) and mcu (iii). The results show the efficiency of the latter, in which, among other, mixed collective utility dramatically reduces the number of ex-post collective utility computations.

Sub-optimal algorithms

As we can see e.g in Table 2, even with the improvements introduced, we remain unable to solve a majority of instances with 3 agents and 26 objects within 30 seconds with our exact algorithm (it typically requires between 5 and 10 minutes for this instance size). Moreover, even if we did not prove it formally, it is very likely that the mere computation of the ex-post egalitarian utility of a given allocation will be out-of-reach for more than a few dozens of objects, because of the exponential number of states of nature. The only reasonable way of solving instances of realistic size thus seems to use sub-optimal algorithms, for both the computation of a good allocation and the evaluation of the ex-post utility.

We can notice however that if we stick to the egalitarian ex-post criterion, we will be unable to evaluate the quality of the solutions, since exact computation of an optimal solution is out of reach. To overcome this issue and give a rough idea of how good our solutions are, we chose to switch our criterion to the probability of fair share ϕ p (Definition 5), because this criterion has an obvious upper bound (ϕ p ≤ 1), and thus conveys in itself an information about the quality of the solution.

Estimating ex-post criterion The approximate computations are made according to the Monte-Carlo method : since browsing all the states of nature to get an exact result is impossible, we select a given number q of random states (according to their actual probability of occurrence) and check in each of them if the fair share is guaranteed.

Let X be a random variable, which takes its values in S according to the probability Pr(X = s) = Pr(s). For a given π ∈ F , let φ(X) = mini∈A ϕi(π, X), which is an unbiased estimator of ϕ p (π). The Monte-Carlo method produces q independent draws, i.e. a sample of values φ1, φ2, .., φq. A better estimator (with a smaller variance) of ϕ p (π) is then defined by φ′ = 1/q q k=1 φk . Now, given a probability α, we can use the central limit theorem to give a confidence interval around which we have a probability 1α to find the actual value of ϕ p :

Pr[| φ′ -ϕ p | ≥ C(α)] ≤ α, with C(α) = F (α) Var( φ) q ( 8
)
where F is the cumulative density function of a normal distribution of expectation E( φ) and of standard deviation σ( φ), and where Var( φ) is the variance of φ. Computing Var( φ) requires browsing all the states of nature: thus, we use the samples we have to estimate it, which is common practice in statistics theory. Then, Equation ( 8) directly gives a confidence interval for our Monte-Carlo estimation.

Computing fair allocations Our algorithm follows the "Heuristic-Biased Stochastic Sampling" paradigm [START_REF] Bresina | Heuristic-Biased Stochastic Sampling[END_REF]. Complete allocations are built object by object, using the same heuristics as for the exact algorithms (see Section 4.2), but with a random bias, so that the search space is partially explored in the vicinity of the pure heuristics. When a complete allocation π has been built, an estimation of ϕ p (π) is made, with q1 draws, in order to decide whether the allocation will be stored or not. A fixed number nbS of such promising allocations is stored within the course of the algorithm; if an allocation is betteras far as this first approximate computation can tell -than the worst currently stored, it is saved. As soon as a total of nbC allocations have been generated this way, a more precise estimation is made for each of the nbS stored allocations using q2 draws (q2 ≫ q1), and only the best one is kept. The building of allocations then continues, until a given time has elapsed. Parameters values have been chosen after some preliminary experiments, and give good results for the typical case n = 3, m = 100. Results The approximate algorithm is tested on 100 instances, for a duration of 120 seconds each. Figure 1 illustrates the evolution of the best solution found, throughout the execution of the algorithm. Table 3 shows the data about the precision of this method. .0014 .0016 .0011 .0004 Table 3. Estimation quality for n = 3, averaged over 100 instances.

As we can see in Table 3, on small instances the estimated variance is very close from the exact one. Regarding instances of realistic size, not only Figure 1 shows that our stochastic greedy approach quickly finds allocations whose estimated probability of fair share is very close to 1, but also Table 3 clearly indicates that this estimation is very likely to be close to the exact value. What experiments also show (but which does not appear in Figure 1 or Table 3) is that combining storage with two different numbers of draws (q1 and q2) allows for a quicker convergence than a simple greedy algorithm with q2 draws, with a more precise confidence interval than an algorithm with q1 draws.

In summary, these results clearly show that combining Monte-Carlo draws with our stochastic greedy algorithms can be used to solve efficiently real-world instances by providing (i) very good allocations in a short amount of time and (ii) precise estimates of ϕ p .

CONCLUSION

In this paper we have introduced a formal model of the problem of fairly allocating a set of indivisible objects (goods, time-slots ...) when the conditions (and hence the utility for agents) of these objects are subject to uncertainty, as well as algorithms to solve it. As pointed for a long time by economists, in such a problem involving uncertainty, two points of view can be taken in order to socially measure the possible allocations: either consider the social welfare derived from expected individual utilities (ex-ante approach), or consider the expected social welfare (ex-post approach). When fairness is a concern, many arguments are in favour of the last one.

We have investigated several properties of ex-ante and ex-post criteria, and introduced exact and sub-optimal algorithms to find allocations that maximize the ex-post egalitarian collective utility, or maximize the ex-post probability of fair share. As we have seen, the complexity makes the exact computation unfeasible in practice. However, we have managed to solve real-size instances with a remarkable level of precision by combining a stochastic greedy algorithm with Monte-Carlo estimations.

Worthwhile possible extensions of this work include the study of other fairness criteria, such as the maximin fair share, introduced in [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF], which suits well to indivisible goods but requires solving numerous fair share subproblems. We also plan on designing other approximate evaluation methods to use in the stochastic greedy algorithm.

Figure 1 .

 1 Figure 1. Evolution in time of the value of φ′ during execution of the stochastic greedy algorithm, averaged over 100 instances, for n = 3, m = 100, with q 1 = 200, q 2 = 5 × 10 5 , nb S = 10 and nb C = 50.

  φ, q = 200 .1702 .1904 .1141 .0200 estimated variance of φ, q = 10 5.1692 .1916 .0353 .0115 C(1%), q = 200 .0445 .0493 .1146 .0193 C(1%), q = 5 × 10 5

Table 1 .

 1 Utility profile and ex-ante and ex-post utility computation for a problem with 2 agents, 4 objects, probabilities p = 0.8, 0.8, 0.5, 0.2 , weights w 1 = 10, 2, 4, 7 and w 2 = 3, 8, 4, 10 , allocation π = {1, 4}, {2, 3} , G = min. Here, pcu(π) = 4.66 and acu(π) = 8.4 (see Section 3.1).

	(1)	good(s)	∅	{1}	{2}	{3}	{4}	{1, 2} {1, 3} . . . {2, 3, 4} {1, 2, 3, 4}	expected
	(2)	Pr(s)	0.016 0.064 0.064 0.016 0.004 0.256	0.064 . . .	0.016	0.064	utility
	(3)	u1(π, s)	0	10	0	0	7	10	10	. . .	7	17	9.4
	(4)	u2(π, s)	0	0	8	4	0	8	4	. . .	12	12	8.4
	(5)	collective utility	0	0	0	0	0	8	4	. . .	7	12	4.66 P P P P P P 8.4

Table 2 .

 2 Exact resolution. Number of instances solved in 30 seconds (over 100 random instances) for different number of agents and objects.

	n	m	(a)	(b)	n	m	(a)	(b)
	2	≤ 15	100 100	3	≤ 11	100 100
	2	20	0	100	3	16	0	97
	2	25	0	60	3	21	0	48
	2	30	0	1	3	26	0	7

Onera Toulouse, France, email: charles.lumet@onera.fr

Grenoble INP -LIG, France, email: sylvain.bouveret@imag.fr

Formerly Onera Toulouse, email: lmtr@club-internet.fr

Note that this family corresponds (up to a p th -root) to the family of rootpower quasi-arithmetic means studied e.g. in multicriteria decision aid[START_REF] Marichal | Aggregation Operators for Multicriteria Decision Aid[END_REF].

[START_REF] Broome | Uncertainty and fairness[END_REF] f represents g means formally that ∀(x, y), f (x) ≤ f (y) ⇔ g(x) ≤ g(y).

Also note that we could replace the min operator with another one (for example ), which would lead to other criteria, like ex-ante or ex-post quantities of fair share for example.

Note that for the sake of simplicity, we stick to the probabilistic independence hypothesis, but we could also think of relaxing it and assume that probability variables of contiguous time slots are in fact dependent.