A General Elicitation-Free Protocol for Allocating Indivisible Goods

1 Introduction

Approaches to fair division, and more generally resource allocation, can be classified according to four dichotomies [Chevaleyre et al., 2006]: (a) divisible vs. indivisible objects; (b) centralized vs. decentralized approaches; (c) revenue efficiency vs. fairness criteria; (d) allowing money transfers or not. (a), (c) and (d) are self-explanatory. As for (b), in centralized approaches, the agents communicate their preferences to some central authority, which computes the optimal allocation, according to some optimality criterion; in decentralized approaches, agents interact with each other (possibly with the help of a central authority), through actions that reveal only a part of their preferences. A typical class of decentralized approaches of this type is the class of cake cutting procedures (e.g., [Robertson and Webb, 1998; Brams and Taylor, 1996]), which are typically designed for the allocation of divisible goods; Centralized approaches have two drawbacks: (a) the elicitation process and the winner determination algorithm can be very expensive; (b) the agents have to reveal their full preferences, which they might be reluctant to do.

J´erˆome Lang

LAMSADE

Universit´e Paris-Dauphine lang@lamsade.dauphine.fr

Although many centralized approaches to allocating indivisible goods have been proposed, decentralized approaches are much less frequent, up to a few exceptions such as [Brams et al., 2011] who adapt a cake-cutting protocol to the allocation of indivisible goods, and [Chevaleyre et al., 2010], who study negotiation-based protocols for allocating indivisible objects in a distributed way.

Here we study a much simpler decentralized protocol for allocating indivisible objects, which is used in a variety of daily situations. We have p indivisible objects to allocate to n agents. The central authority defines a sequence of agents of length p. Every time an agent is designated, she picks one object out of those that remain. For instance, if n = 3 and p = 5, the sequence 12332 means that agent 1 picks an object first; then 2 picks an object; then 3 picks two objects; and 2 takes the last object. The central authority has to find the best sequence, according to some criterion. For instance, if we want to be fair, π = 12332 seems better than π′ = 12321, because in π, agent 1, who receives only one object, is compensated by the fact that she ends up with his preferred object. This process is arguably very natural. Brams and Taylor [Brams and Taylor, 2000] give it some attention, by studying particular sequences, namely strict alternation, where two agents pick objects in alternation, and balanced alternation (for two agents) consisting of sequences of the form 1221, 12212112 etc. However they do not justify these sequences by optimality arguments. In fact, we do not know of any work on the definition and computation of optimal sequences.

To make this formal, we need to define a (generic) model, as follows: (i) agents have additive utilities (the value of a subset of objects is the sum of the values of its elements); (ii) a scoring function maps the rank of an object in a preference relation to its utility value - the agents may have different rankings, but this scoring function is the same for all agents; (iii) we have a probability distribution on the possible collections of rankings (or profiles); we focus on two prototypical models: full independence (all profiles are equally probable, hence the rankings of two different agents are independent), and full correlation (agents have identical preferences). (i), (ii) and (iii) suffice to determine the expected utility of an agent for a given sequence. Finally, (iv) we have a social welfare function F aggregating the utilities of the agents; we will focus on F = + (utilitarianism) and F = min (egalitarianism). We then look for a sequence optimizing the expected social welfare.

The general model is defined in Section 2. In Section 3 we address the computation of the optimal sequence under various instances of the model. In Section 4 we consider strategical issues. We show that if agents have identical preferences, the process is strategyproof. In the general case, we show that an agent who knows the preferences of other agents can find in polynomial time whether she has a strategy for getting a given set of objects, and that if the scoring function is lexicographic, then computing an optimal strategy is polynomial. 1 .

2 The general model

2.1 Preferences

We have a set of p indivisible objects O = {o1, . . . , op} and a set of agents {1, . . . , n}. We assume that each agent i has a (hidden) additive utility function ui over objects: for any object o, ui(o) is the value that agent i gives to object o, and for any A ⊆ O, ui(A) = ∑o∈A u(o) (and u(∅) = 0). Therefore, we assume that agents have no preferential dependencies between objects. The preference relation ⪰i induced by ui is defined by A ⪰i B if and only if ui(A) ≥ ui(B). The strict preference ≻i associated with ⪰i is defined as usual by A ≻ B if A ⪰ B and not B ⪰ A.

Now, because the allocation process does not involve any elicitation stage, the central authority will never know the agent's utilities. Instead, it can only observe a small part of it, by seeing an agent picking a given objet at a given stage. Now, the central assumption of this paper is that we consider a utility model where any rank in {1, . . . , k} is mapped to a utility value via a scoring function.

Definition 1 A scoring function is a non-increasing function g from {1, . . . , p} to R+: if i ≤ j then g(i) ≥ g(j).

We focus on three prototypical scoring functions:

• Borda: for any k, gB(k) = p-k +1.
• lexicographic: for any k, gL(k) = 2p-k .
• QI (quasi-indifferent): for any k, gI(k) = 1+ε.(p-k), where ε ≪ 1.

We denote by ranki(o) ∈ {1, . . . , p} the rank of object o in the preference relation of agent i. g(i) denotes the value that an agent gives to her ith preferred object: thus, fixing the scoring function to g amounts to assume that ui(o) = g(ranki(o)), for any agent i and any object o.

The choice of a scoring function depends on the application domain. In a domain where the number of objects received is of primary importance QI is reasonable. On the other extremity, if agents are likely to have huge discrepancies in the way they value objects, the lexicographic model is more realist. Between both, the Borda model (named after the Borda voting rule) assumes that the value agents give to objects decreases linearly between two consecutive ranks. The choice of a scoring function for a specific domain may be guided by some learning process (one may even think of giving different scoring functions to agents according to their type).

1 Due to space restrictions, most proofs are omitted. Complete proofs and detailed examples can be found at http:// recherche.noiraudes.net/en/sequences.php

A profile R consists in a collection of rankings, one for each agent: R = 〈≻1, . . . , ≻n〉.

2.2 Uncertainty over profiles

First, we assume that for a given agent, all possible rankings are equally probable. Next, we have to specify whether the events "agent i having ranking Ri" and "agent j having ranking Rj" are independent or not. For this we focus on two prototypical models which lie at both extremities of the spectrum: one where these events are independent and one where they are fully correlated.

Full independence (FI) For any agent i, all possible rankings on O are equiprobable and the rankings of different agents are independent: Pr(R) = 1 (p!)n for every profile R = 〈≻1, . . . , ≻n〉.

Full correlation (FC) The agents rank the objects in the same way: ≻1= . . . =≻n. This assumption (also considered in [Brams and Fishburn, 2002]) makes sense if the agents are similar enough so that the value of an object can be considered objective. We will see later that this assumption is equivalent to focusing on the worst case, as it gives the worse possible utility to the agents; hence we don't need to define a probability distribution in this case (for the sake of defining the model completely, we may further assume that all profiles of the form R = 〈≻, . . . ,≻〉 are equiprobable, hence have probability 1 p! each; but the results do not depend on this).

We could have a more general model, with some intermediate correlation between the rankings (e.g., for some constant α ∈ [ 12 , 1], Pr(o ≻i o′ | o ≻j o′ ) = α) of which (FI) and (FC) are particular cases; we will not develop it here.

2.3 Policies

At each stage of the process, a designated agent picks an object (supposedly, her preferred object among those that remain), following a policy that assigns an agent to each stage. Formally, a policy is a function π : llbracket1, prrbracket → N. We simply denote a policy by enumerating the agents picking an object at time 1, 2, . . . , p. For instance, if n = 3 and p = 7, the policy defined by π(1) = 2, π(2) = 1, π(3) = 1, π(4) = 2, π(5) = 3, π(6) = 3, π(7) = 3 is denoted by 2112333.

Given a policy π and a profile R = 〈≻1, . . . , ≻n〉, for every agent i, we denote by sπi,k (R) her current share right after stage k. For every i, sπi,k (R) is defined inductively as follows:

• sπi,0 (R) = ∅
• sπi,k (R) = sπi,k-1 (R) if π(k) ̸= i, and sπi,k (R) = sπi,k-1 (R) ∪ {max≻i (o ∈ Oπ k-1 (R))} otherwise,

where Oπ k (R) = ⋃i sπi,k (R) denotes the set of objects already allocated according to π right after stage k, and Oπ k (R) = O \ Oπ k (R) the remaining objects.

Finally, let ui(π,R) = ui(sπi,p (R)) be the utility of agent i at the end of the process, that is, the value of her share according to the scoring function:

Finally, sπ1,5 = {o1}, sπ2,5 = {o2, o4}, and sπ3,5 = {o3, o5}. The utilities of the three agents are the following, depending on the choice made for scoring:

• Borda: u1(π) = 5; u2(π)=5+4=9; u3(π)=4+3=7.
• lexicographic: u1(π) = 16; u2(π) = 24; u3(π) = 12.
• QI: u1(π) = 1 + 4ε; u2(π) = 2 + 7ε; u3(π) = 2 + 5ε.

2.4 Expected utility and social welfare

Since the arbitrator does not know the agents' preferences, she is not able to compute their actual individual utility, but can only rely on an expected utility, given the probability distribution Pr over profiles. Given a policy π, the expected utility of agent i is defined by:

Finally, we define an aggregation function as a symmetric, non-decreasing function from (R+)n to R+.

Two typical choices for F correspond to the well-known utilitarian criterion and the Rawlsian egalitarian criterion:

• utilitarian: F(u1, . . . , un) = ∑i=1,...,n ui;
• egalitarian: F(u1, . . . , un) = mini=1,...,n ui.

Given a probability distribution Pr on profiles and an aggregation function F , the expected social welfare of policy π is defined as the aggregation of individual expected utilities:

Note that swF (π) is determined from the scoring function g, the correlation model c, and the aggregation function F.

To sum up, a sequential allocation problem is a 5-uple P = 〈N,O, g, c, F〉 where N = {1, . . . , n} is the set of agents, O = {o1, . . . , op} the set of objects, g the scoring function, c ∈ {FI, FC} the correlation function, and F the aggregation function. A policy π is optimal for P if it maximizes swF (π). Solving a sequential allocation problem consists in finding the optimal sequence once those five parameters have been fixed.

3 Computing optimal sequences

3.1 Full correlation

Recall that under the full correlation assumption, all agents have the same ranking over objects. Without loss of generality, assume this ranking is o1 ≻ o2 ≻ . . . ≻ op. Then, at stage k, the designated agent π(k) will pick object ok. Therefore, expected social welfare can be rewritten as follows.

Note that maximizing this social welfare comes down to maximizing the social welfare for the worst possible profile: let R be a profile with identical preference rankings, and R′ be any other profile. Then for any policy π and agent i, ui(π,R) ≤ ui, (π,R′ ), hence swF,FC(π) = F (u1(π, R), . . . , un(π, R)) ≤ F (u1(π, R′ ), . . . , un(π, R′ )). This is simply because: (i) obviously, at every stage i, agent π(i) will get an object she ranks in position at most i, and (ii) under full correlation, agent π(i) will actually get the object she ranks ith , which is the worst she could get.

Now we consider the three distinguished scoring functions. We start by utilitarian social welfare. We have

Note that ∑k∈llbracket1,prrbracket g(k) is a constant, which depends only on n, p, and g, but not on π. In other words:

Proposition 1 Under utilitarianism and full correlation, all policies have the same expected social welfare.

This holds for the following intuitive reason: whatever agent is designated by π at stage k, she will pick ok and receive g(k).

Therefore, under utilitarianism and full correlation, the problem is trivial. Now, we consider egalitarianism and study the following problem:

Problem 1: Sequential allocation under egalitarianism and full correlation.

Instance: A number of agents n, a number of objects p, a scoring function g, an integer K.

Question: Is there a policy π such that swmin(π) ≥K, under full correlation ?

Proposition 2 Under egalitarianism and full correlation, Problem 1 is NP-complete.

The hardness part of the proof, which is not particularly difficult, comes from a reduction from PARTITION.

We now consider the three specific scoring functions defined above.

Lexicographic scoring

It is not difficult to show that if there are at least as many objects as agents (p ≥ n), the optimal policies are those of the following form, where σ is a permutation of {1, . . . , n}: σ(1)σ(2) . . . σ(n - 1)σ(n)p-n+1 and that if there are less objects than agents (p < n), the optimal policies are those of the following form, where σ is a permutation of {1, . . . , n}: σ(1)σ(2) . . . σ(p).

In other terms, the first n1 agents choose an object in sequence, and the remaining agent picks all remaining objects.

Borda scoring

In this case, the problem is equivalent to finding a partition of {1, . . . , p} in n classes such that the sum of the integers in each class is above a threshold. This comes down to solving the following problem:

Problem 2: Sequential allocation under egalitarianism, full correlation, and Borda scoring

Instance: A number of agents n, a number of objects p, an integer K.

Question: Is there a partition of Xp = llbracket1, prrbracket into n clusters A1, . . . , An such that ∑k∈Ai k ≥ K, ∀i ≤ n?

Because the number of possible cumulated values for a given agent is polynomially bounded (namely p(p+1) 2 ), the problem can be solved by dynamic programming, where we need to fill a table of O(p × n.p2 ) cells 2 , each requiring O(n) computation time. One may however notice that this algorithm runs in polynomial space and time only if n and p are encoded in unary (hence the size of the input is n + p + log(K)). Thus:

Proposition 3 Under egalitarianism, full correlation, and Borda scoring, Problem 2 is pseudopolynomial.

QI scoring

Due to the lack of space we will not go into details. It can be shown that if m = ⌊ pn ⌋ and q = p - nm, an optimal policy is necessarily such that n-q agents receive m objects each, and receive them during the m(n-q) first rounds, while the remaining q agents receive m + 1 objects each during the remaining rounds. For example π = 1122333444 and π′ = 1221333444 are of this form. However, not all such policies are optimal (π′ is optimal whereas π is not). We can show that finding an optimal policy comes down to finding an optimal policy w.r.t. the Borda scoring for the n - q first agents and the m(n - q) first rounds.

Proposition 4 Under egalitarianism, full correlation, and QI scoring, finding an optimal policy is pseudopolynomial.

3.2 Full Independence

The full independence (FI) case is more complex. We conjecture that the problem of finding an optimal allocation policy under FI, and for any of our three specific scoring functions, is NP-hard, but we do not have a proof. Moreover, we do not even know if, for a given policy π, swF (π) can be computed in polynomial time (we conjecture it is NP-hard as well).

However, it is possible to compute an optimal policy in reasonable time for small numbers of objects using an exhaustive search algorithm: for each possible complete policy, the algorithm computes the social welfare and compares it to the best one found so far. So as to break symmetries, we only consider policies π where π(k) ≤ k (the first agent in the sequence can only be 1, the second one can be 1 or 2, and so on).

The expected utility for an agent i can computed by developing a search tree: each node is a partial assignment of the objects, and is expanded into (i) one single branch if i is the next agent to choose (she will pick her top object for sure), and (ii) #(remaining objects) branches otherwise (the current agent can possibly pick each one of the remaining objects with uniform probability). Algorithm 1 slightly improves this procedure by expanding several levels at once, if i does not appear during several successive rounds. At each step, a set X of ranks are chosen, and the problem is transformed into a problem with p - |X| objects, and a scoring function built from g, where all the values from g(X) are removed. On Line 6 of the algorithm we denote by g \ X the functions that maps k to the kth element in dom(g) \X. Here is an example of how this algorithm computes the utility of agent 1 for the sequence 12221, using the Borda scoring function. We use a compact notation for g, namely g = 12345 for g(1) = 1; . . . , g(5) = 5; note that dom(g) is the number of objects remaining to be allocated.

2 Thanks to Bruno Escoffier and Thang Nguyen Kim.

• First call: g is 54321 and the added value (Line 3) is g(1) = 5.
• Second call: g is 4321 and since 1 is not served during 3 rounds, there are (43) = 4 recursive calls (Line 7): for X = 123 (value added : 1), X = 124 (value added : 2), X = 134 (value added : 3) and X = 234 (value added : 4). The global added value is thus (4 + 3 + 2 + 1)/4 = 2.5.
• Therefore, the value returned is 7.5.

Algorithm 1: EU(π, i, g)

input : A policy π, an agent i, a scoring function g. output: Expected utility of i under the FI assumption.

• 1 if (dom(g) = ∅) ∨ (∀k, π(k) ̸= i) then return 0;
• 2 if π(1) = i then
• 3 return g(1) + EU(k ↦→ π(k + 1), i, k ↦→ g(k + 1));
• 4 λ ←min{k′ | π(k′ ) = i} - 1;
• 5 u ← 0;
• 6 for X ⊂ llbracket1, |dom(g)|rrbracket such that |X| = λ do
• 7 u ← u+ EU(k ↦→ π(k + λ), i, g \ X);

8 return u/(|X| k );

We provide an implementation of this algorithm that computes optimal policies (and their values) once the user has given n, p, g and F, and can be tested online (http:// recherche.noiraudes.net/en/sequences.php).

This implementation computes optimal policies in less than a few minutes until around 10 objects (12 objects when n = 2). Table 1 shows some results for small n and p. An intriguing result is that for the values of p and n we tested, strict alternation is an optimal strategy for F = +; we do not know whether this is true for every p and n. Also, the optimal strategy returned for p = 12, n = 2 is not a balanced alternation.

Things become much harder when p becomes larger. However, we claim that, in this case, the problem loses much of its interest. Informally, when p increases (while n is fixed) then agents receive more and more objects, and it will be more and more easy to find an optimal sequence.

Proposition 5 Let p = kn+q. Under FI and Borda scoring, any policy π of the form σ1σ2 . . . σkθ, where σ1, . . . , σk, are permutations of {1, . . . , n}, tends to an optimal allocation when p → +∞ (n being held constant) both for egalitarian and utilitarian social welfare.

Proof Assume first that p is a multiple of n. Consider the first n stages. The agent who comes first in σ1 receives p. The one who comes second receives p-1 p .p + 1p (p - 1) = p2-1 p ∼p→∞ p. The one who comes third gets also Θ(p), and so on: everyone receives p +O(p-1 ). Now, during the next n stages: the agent who comes first in σ2 gets her second preferred object if none of the n-1 agents have taken it, which happens with probability 1n-1

n + O(1). Now, in the best case, for whatever policy, the maximal utility that an agent can receive is the utility corresponding to his preferred k objects, i.e., p + . . . + p - k + 1 = p2 n +O(1). Therefore, ¯u(σ) tends to the expected utility of an optimal policy when p → ∞.

p-1 ; therefore, she gets an utility at least (1 - n-1 p-1 ) .(p - 1) = p - 1 + O (p-1 ). We check that it also applies to every other agent during the execution of σ2. During σ3, we check then that every agent receives p - 2 + O (p-1 ), and so on until σk, where everyone receives p - k + 1 + O (p-1 ). Therefore, the total utility received by any agent is at least [p + (p - 1) + . . . + (p - k + 1)] + O (p-1 ), i.e., p2

When p is not a multiple of n, the proof is analogous, noticing that the increment of utility brought by the last object picked by an agent during the last subsequence is small compared to the p2 n utility already gathered. ■

4 Strategical issues

As most collective decision mechanisms, our sequential allocation problems are generally not strategyproof. This can be seen on the very simple example with any scoring function, two agents, four objects, the preferences of 1 being abcd and those of 2 being bcda, and π = 1221. If 1 and 2 play sincerely, i.e., pick their preferred object at each stage, then the final allocation is 1 ↦→ ad, 2 ↦→ bc. However, if 1 knows 2's preferences and plays strategically, then she picks b first, then 2 picks c and d, 1 finally picks a and the allocation is 1 ↦→ ab, 2 ↦→ cd, which makes her better off.

We now address these two questions: (1) is sequential allocation strategyproof for some restricted domains? (2) when it is not, how hard is it for an agent who knows the preferences of the others to compute an optimal strategy? For both questions, the choice of the social welfare function F and of a probability distribution over profiles is irrelevant (remember that the manipulating agent knows the others' preferences).

We first show that the answer to the Question 1 is positive when the agents' rankings coincide (full correlation).

Proposition 6 When all the agents have the same preference rankings, sequential allocation is strategyproof for any scoring function and any policy π.

We now move to Question 2. Let π be a policy, and let i1, . . . , ir be the picking stages of agent 1, i.e., the stages such that π(ij) = 1, with i1 < . . . < ir. Let 〈≻2, . . . ,≻n〉 be the rankings of the other agents. A strategy for 1 is a function σ : {1, . . . , r} to O, specifying which object 1 should take at any stage where it is her turn to pick an object. σ is said to be well-defined with respect to π and 〈≻2, . . . ,≻n〉 if at any stage ir, the object σ(r) is still available (assuming that 2 to n play sincerely). Note that the allocation process (who gets what and when) is fully determined from ≻2, . . . ,≻n and a well-defined strategy σ.

A manipulation problem M consists of π, 〈≻2, . . . ,≻n〉, and a target set of objects S ⊆ O. A well-defined strategy σ is successful for M if, assuming the agents 2 to n act sincerely, σ ensures that agent 1 gets all objects in S. Solving M consists in determining whether there exists a successful strategy. Below we show that the manipulation problem can be solved in polynomial time. First, we give a simple characterization of successful strategies in problems with two agents.

Proposition 7 Let μ be the permutation of {1, . . . , p} such that ≻2= oμ(1) ≻ . . . ≻ oμ(p). For any j ≤ p, let PS(j) = #{i ≤ j|π(i) = 1} be the number of picking stages of 1 until j and Cl(j) = {oμ(i)|i ≤ j, oμ(i) ∈ S}. There exists a successful strategy for 1 iff for any j ≤ p we have PS(j) ≥ |Cl(j)|. Moreover, in this case any strategy starting by picking the objects in S according to their ranking in ≻2 (and completed so as to be well-defined) is successful.

Instead of giving a proof sketch, we show how it works on an example. Let p = 4, ≻2= o2 ≻ o4 ≻ o3 ≻ o1, π = 1221, and S = {o1, o2}. We have PS(1) = PS(2) = PS(3) = 1, PS(4) = 2. Then, Cl(1) = Cl(2) = Cl(3) = {o2} and Cl(4) = {o1, o2} - intuitively, Cl(j) represents the objects in S "claimed" by agent 2 until j, and thus that 1 will not get if she does not pick them before. Because PS(j) ≥ |Cl(j)| is satisfied for all k, the strategy σ such that σ(1) = o2; σ(2) = o1 is successful. Now, let S = {o2, o3}: PS(3) = 1 and Cl(3) = {o2, o3}, therefore there is no successful strategy.

Now, we show that a problem M with n agents can be translated into a problemM ∗ with two agents, such that there is a successful strategy in M if and only if there is a successful strategy in M ∗ . M ∗ is defined as follows: S∗ = S; the preference relation ≻∗ of agent 2 is computed by Algorithm 2, and the policy π∗ is defined by: for every i ≤ p, if π(i) = 1 then π∗ (i) = 1, and if π(i) > 1 then π∗ (i) = 2.

Let us run Algorithm 2 on an example. Let n = 3, p = 6, ≻2= o3 ≻ o1 ≻ o2 ≻ o4 ≻ o5 ≻ o6, ≻3= o2 ≻ o3 ≻ o4 ≻ o6 ≻ o5 ≻ o1, π = 123123, and S = {o1, o2}. Then π∗ = 122122 and ≻∗= o3 ≻ o2 ≻ o4 ≻ o1 ≻ o5 ≻ o6.

Proposition 8 There exists a successful strategy for 1 in M if and only if there exists a successful strategy for 1 in M ∗ .

The proof of Proposition 8 is structured in two lemmas.

Lemma 1 If there exists a successful strategy for M then there exists a successful strategy for M in which the first |S| objects picked by 1 are the objects of S.

In other words it is never harmful for 1 to start picking the objects of S; taking an object out of S instead will never help.

Given a manipulation problem and a strategy θ, we define all(P, θ) as the function mapping each i to the object picked by π(i) at round i.

Lemma 2 Let θ be a strategy for agent 1 (either for M or M ∗ ) in which the first |S| objects picked by 1 are the objects of S. Then θ is successful for M if and only if it is successful for M ∗ , and in that case, for each i, all(M, θ) = all(M ∗ , θ).

Algorithm 2: Transforms a n-agent manipulation problem into a 2-agent manipulation problem

input : 〈≻2, . . . ,≻n〉: preference rankings; O: set of objects; S ⊆ O: target subset; π: policy output: a preference relation ≻∗ on X 1 T ←O; i ← 1; ≻∗←∅; /* Initialization */ 2 repeat 3 j ← π(i) ; /* agent j is the next one to pick an object */ 4 if j ̸= 1 then /* this agent is not the manipulator */ 5 ol ← Max(≻j , T ); /* j intends to pick ol */ 6 append ol to ≻∗; 7 T ← T \ {ol}; 8 if ol ̸∈ S then 9 i ← i +1 ; /* next agent in the sequence */ /* only if 1 and j do not compete on object ol */ 10 else i ← i + 1; 11 if i = p + 1 then 12 complete ≻∗ with all T , in arbitrary order; 13 T ← ∅; 14 until T = ∅;

Proposition 8 can be easily proved using Lemmas 1 and 2.

So far we have shown that the manipulating agent can find in polynomial time a strategy, if any, to make sure she gets all objects in a target set S, assuming other agents are sincere and that she knows their preferences. We now address the following issue: given an agent 1 and her scoring function g, when can 1 find an optimal strategy in polynomial time?

We show that this is true under the lexicographic scoring function. Let 1 be the manipulator (again we assume the others act sincerely). We build the best set of objects that 1 can manage to get in a greedy way, considering the objects one after the other in decreasing order of 1's preference ranking; if we find out that 1 has a strategy to get this object together with the already secured objects, we add this object to the best set of objects she can get; otherwise, we don't, and move on to the next object. This greedy algorithm calls the previous algorithm to check whether there exists a successful strategy.

Algorithm 3: Finding the optimal strategy for agent 1

input : a policy π; a collection of preference rankings 〈≻1, ≻2, . . . , ≻n〉 output: an optimal picking strategy σ for agent 1 1 t ← number of occurrences of 1 in π; 2 S ←∅; 3 i ← 1; 4 repeat 5 if ∃σ, successful strategy for S ∪ {i}, π and 〈≻1,≻2, . . . ,≻n〉 then S ←S ∪ {i}; i ← i +1; 6 until i > p or |S| = t; 7 return σ

Proposition 9 If agent 1's utility function is lexicographic, then Algorithm 3 returns the optimal strategy for agent 1.

Proof Suppose not: there exists a strictly better strategy σ′ . Let k be the smallest index such that σ(k) ̸= σ′ (k). Since σ′ is better than σ, we have σ′ (k) ≻1 σ(k). But then 1 could have picked {oiσ(1) ,...,oiσ(k)}, thus the condition on Line 5 of Algorithm 3 would have been true, contradicting the fact that Algorithm 3 returns σ. ■

Corollary 1 Under lexicographic scoring, the optimal strategy for an agent can be computed in polynomial time.

For the Borda scoring, we conjecture that the manipulation problem is NP-hard, but we could not find a proof. We believe such a proof will be hard to find, as it might be related to problem of coalitional unweighted manipulation of voting under the Borda rule, whose complexity was an open problem until this conference.

5 Conclusion

We have defined a generic model of a very intuitive protocol for allocating indivisible goods to agents without eliciting their preferences, and studied it from the points of view of the computation of optimal sequences and the complexity of manipulation by one agent. Further work includes finding the missing complexity results for the FI case, evaluating the probability that the resulting allocation is envy-free, developing a full game-theoretic analysis of the process, and studying the opportunity to model and solve the problem as a monoor multi-objective MDP.

Acknowledgments The authors wish to thankYann Chevaleyre, David Doose, Bruno Escoffier, Laurent Gourv`es, J´erˆome Monnot and Nguyen Kim Thang for stimulating discussions about this work and an anonymous reviewer for pointing to us multiobjective MDP as a possible approach. This work has been partly supported by the project ComSoc (ANR-09-BLAN-0305-01).