Dorothea Baumeister
email: baumeister@cs.uni-duesseldorf.de

Sylvain Bouveret
email: sylvain.bouveret@imag.fr

Jérôme Lang
email: lang@lamsade.dauphine.fr

Nhan-Tam Nguyen
email: nguyen@cs.uni-duesseldorf.de

• Trung

Thanh T Nguyen
email: ttnguyen.cs@gmail.com

Jörg Rothe
email: rothe@cs.uni-duesseldorf.de

Abdallah Saffidine
email: abdallahs@cse.unsw.edu.au

N.-T Nguyen

Positional Scoring-Based Allocation of Indivisible Goods

Keywords: Computational social choice, resource allocation, fair division, indivisible goods, preferences

We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of goods are additive, but that the input is ordinal: each agent reports her preferences simply by ranking single goods. Similarly to positional scoring rules in voting, a scoring vector s = (s 1 , . . . , s m ) consists of m nonincreasing, nonnegative weights, where s i is the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function such as, typically, + or min. The rule associated with s and maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation

Introduction

Fair division of divisible goods has put forth an important literature about specific procedures, either centralized [START_REF] Moulin | Cooperative Microeconomics: A Game-Theoretic Introduction[END_REF] or decentralized [START_REF] Brams | Fair Division: From Cake-Cutting to Dispute Resolution[END_REF]. Fair division of a set of indivisible goods has, perhaps surprisingly, been mainly addressed by looking for allocations that satisfy a series of properties (such as equity or envy-freeness) and less often by defining specific allocation rules (see, e.g., the book chapters by Bouveret et al 2016 andLang andRothe 2015). A notable exception is a series of papers that assume that each agent values each good by a positive number, and the utility of an agent is the sum of the values of the goods assigned to her.

We take a different path and assume that agents' preferences over items are expressed ordinally, as rankings over items, and that agents' utilities are computed using a fixed, agentindependent vector that maps ranks into scores (in the very same way as positional scoring voting rules, such as the Borda rule, proceed). This way of defining allocation rules was initiated by [START_REF] Brams | Fair division of indivisible items[END_REF], who used the "Borda" scoring vector to induce scores from ranks (associating rank 1 to m points, where m is the number of items, then rank 2 to m -1 points, and so on).

We start by generalizing Borda-optimal allocations [START_REF] Brams | Fair division of indivisible items[END_REF] to arbitrary scoring vectors and aggregation functions. Beyond Borda, the scoring vectors we consider are k-approval (the first k objects get score 1 and all others get 0), lexicographic (an item ranked in position k counts more than the sum of all objects ranked in positions k + 1 to m), and quasi-indifference (for short, QI: all objects have roughly the same score, up to small differences). As for aggregation functions , we focus on utilitarianism ( = +) and egalitarianism ( = min, as well as = leximin, which in a strict sense is not an aggregation function, though). In Section 3, we define these allocation rules (we consider both resolute rules and irresolute rules), and focus on a few particular cases. Section 4 is devoted to the study of particular properties or classes of properties, namely separability (Section 4.1), monotonicity (Section 4.2), object monotonicity (Section 4.3). While the properties of voting rules have been studied extensively, this is much less the case for fair allocation of indivisible goods. A related research is the work by [START_REF] Elkind | Properties of multiwinner voting rules[END_REF] who study the axiomatic property of multiwinner voting rules, with a focus on positional scoring rules, while the relationship between multiwinner rules and resource allocation is addressed by [START_REF] Skowron | Fully proportional representation as resource allocation: Approximability results[END_REF].

After having investigated the properties of these allocation rules, we focus on their computational properties. More precisely, we study in Section 5 the complexity of the problem of finding an optimal allocation, which shall be called Winner Determination Problem (referring to the similar problem in auctions) for a few key combinations of a scoring vector and an aggregation function, considering both decision and functional problems. [START_REF] Darmann | Maximizing Nash product social welfare in allocating indivisible goods[END_REF] also study the social welfare maximization problem. They focus on Nash social welfare, which is defined as the product of utility values and which we do not consider. It can be seen as a compromise between utilitarianism and egalitarianism.

In Section 6, we give several approximation results some of which make use of picking sequences. Section 7 gives our conclusions and discusses some open questions for future research.

Related work

Most work on the fair division of indivisible goods assumes that preferences are expressed numerically by a collection of additive value functions (that is, each agent values each good by a positive number, the utility of an agent is the sum of the values of the goods assigned to her, and the resulting allocation maximizes social welfare); in particular, the Santa Claus problem [START_REF] Bansal | The Santa Claus problem[END_REF]) considers egalitarian social welfare, which maximizes the utility of the least happy agent. There is a lot of other work that relies on preferences being expressed by additive value functions, which we do not review here (see Bouveret et al 2016 andLang andRothe 2015 for two recent reviews).

The closest works to ours are those that assume that agents rank single objects, which are possibly turned into weights via a scoring function. Works along this line are rather scarce, and are described below. [START_REF] Brams | Fair division of indivisible items[END_REF] assume that agents rank single goods and have additively separable preferences; they define a Borda-optimal allocation to be one that maximizes egalitarian social welfare, where the utility of an agent is the sum of the Borda scores of the objects assigned to her, and where the Borda score of object g i for agent j ranges from 1 (when g i is j's least preferred object) to m (when g i is j's most preferred object).

Garg et al ( 2010) define a framework for paper reviewing where agents associate a rank (from a fixed scale) with each paper, expressing their willingness to review it; then ranks are mapped into weights, the weight of a set of papers is the sum of the weights associated with the rank of each individual paper, and the optimal assignment is the one with the leximinoptimal vector of weights. [START_REF] Gardenfors | Assignment problem based on ordinal preferences[END_REF] and [START_REF] Wilson | Assignment using choice lists[END_REF] also assume that agents rank single objects and consider assignment functions that use scores induced by positions in rankings (with possible indifferences), but in a simpler setting where each agent is entitled to receive exactly one object. [START_REF] Bouveret | Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods[END_REF], [START_REF] Pruhs | Divorcing made easy[END_REF], and Aziz et al (2015a) also assume that agents rank single objects and have additively separable preferences; but unlike the aforementioned papers, they do not use scores to induce a complete ranking over sets of objects but consider all possible additive utility functions compatible with the ranking over single objects from which they derive a partial order over sets of objects. Thus the approach is cautious, but also not very decisive, as incomparabilities remain between many sets of objects. They then focus on specific properties of allocations (such as envy-freeness, Pareto optimality, or proportionality) and identify the complexity of deciding whether, for a given problem instance, there exists an allocation satisfying a given property or a given set of properties; they do not study allocation rules stricto sensu.

While in all previously mentioned work it is assumed that agents rank single objects, [START_REF] Herreiner | A simple procedure for finding equitable allocations of indivisible goods[END_REF] assume that agents should express rankings over subsets of goods, which, in the worst case, requires agents to express an exponentially large input.

One setting where it is common to use ordinal inputs is matching with preferences. More precisely, our model is connected to two subareas of matching (see, e.g., [START_REF] Manlove | Algorithmics of Matching Under Preferences[END_REF] and [START_REF] Roth | Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis[END_REF]):

it can be seen as a one-to-many two-sided matching problem, where the two sides are agents and items, and where preferences are only on one side (obviously, items don't have preferences over agents).

it can also be seen as a profile-based optimal matching problem; instead of focusing on stability, profile-based matching, outputs matchings maximizing a criterion computed from the ranks of the "partners" of the agents of each side.

However, these two two subareas of matching seem not to have been studied together: most of the work in many-to-many matching is stability-focused, and most of the work on profilebased optimal matching is about one-to-one matching. Therefore, our work can also be seen as a contribution to one-to-many two-sided matching with one-sided preferences.

Scoring Allocation Rules

Let N = {1, . . . , n} be a set of agents and G = {g 1 , . . . , g m } a set of indivisible, nonshareable goods (we will use the terms good, item, and object as synonyms). An allocation is a partition π = (π 1 , . . . , π n ) of G, where π i ⊆ G is the bundle of goods assigned to agent i. We say that allocation π gives good g i to agent j if g i ∈ π j .

In general, to compute an optimal allocation (for some notion of optimality), we would need, for every agent, her ranking over all subsets of G. As listing all (or a significant part of) the subsets of G would be unfeasible in practice, we now make a crucial assumption: agents rank only single objects. This assumption is not without loss of generality, and it has important consequences; in particular, it will not be possible for agents to express preferential dependencies between objects. Under this assumption, a singleton-based profile P = (> 1 , . . . , > n ) is a collection of n rankings (i.e., linear orders) over G, and a (singletonbased) allocation rule (respectively, an allocation correspondence) maps any profile to an allocation (respectively, a nonempty subset of allocations). For any ranking > (respectively, profile P) over G, and any subset G ⊂ G of goods, we will write >

Definition of Scoring Allocation Correspondences

We now define a family of scoring allocation correspondences that can be turned into scoring allocation rules by applying a tie-breaking mechanism (see Section 3.2), which more or less corresponds to the family of scoring rules in voting (see, e.g., the book chapters by [START_REF] Brams | Voting procedures[END_REF], Baumeister and Rothe 2015[START_REF] Zwicker | Introduction to the theory of voting[END_REF].

Definition 1 1. A scoring vector is a vector s = (s 1 , s 2 , . . . , s m ) of rational numbers such that s 1 ≥ s 2 ≥ • • • ≥ s m ≥ 0 and s 1 > 0. 2.
Given a preference ranking > over G and g ∈ G, let rank(g, >) ∈ {1, . . . , m} denote the rank of g under >. 3. The utility function over 2 G induced by ranking > on G and scoring vector s is for each bundle X ⊆ G defined by u >,s (X) = ∑ g∈X s rank(g,>) .

A strictly decreasing scoring vector s satisfies s i > s i+1 for each i < m. A scoring vector is defined for a fixed number of objects only. To deal with a variable number of objects, we introduce the notion of extended scoring vector, as a function mapping each integer m to a scoring vector s(m) of m elements. We consider the following specific extended scoring vectors:

-Borda scoring: borda = m → (m, m -1, . . . , 1),1 lexicographic scoring: lex = m → (2 m-1 , 2 m-2 , . . . , 1), quasi-indifference for some extended scoring vector s:

s-qi = m → 1 + s 1 (m) M , . . . , 1 + s m (m) M , with M m • max{s 1 (m), . . . , s m (m)} = m • s 1 (m)
, where M is an arbitrary large integer. k-approval: k-app = m → (1, . . . , 1, 0, . . . , 0), where the first k entries are ones and all remaining entries are zero.

In the following, we will often abuse notation and use scoring vectors and extended scoring vectors interchangeably, and omit the parameter m when the context is clear. Note that quasi-indifference makes sense for settings where all agents should get the same number of objects (plus/minus one). One concrete example of quasi-indifference scoring vector is the one proposed by [START_REF] Bouveret | A general elicitation-free protocol for allocating indivisible goods[END_REF],

ε-qi = (1 + (m -1)ε, 1 + (m -2)ε, . . . , 1) , where ε 1.
In this paper, we will also consider borda-qi, which is formally defined as follows:

borda

-qi = 1 + m M , 1 + m -1 M , . . . , 1 + 1 M , where M > m 2 .
Example 1 Let G = {a, b, c} be a set of three goods and consider the following preference profile for two agents:

(a > 1 b > 1 c, b > 2 c > 2 a).
Let π be the allocation ({a}, {b, c}). For the Borda scoring vector, agent 1's bundle {a} has value 3 and agent 2's bundle {b, c} has value 3 + 2 = 5. Note that in the following, we will often omit stating "> i " explicitly in preference profiles, and we will also omit curly brackets and commas in allocations: (a > 1 b > 1 c, b > 2 c > 2 a) will thus be written (abc, bca), and ({a}, {b, c}) will be written (a, bc).

It is important to note that we do not claim that the numbers obtained in Example 1 for Borda scoring actually coincide, or even are close to, the agents' actual utilities (although, in some specific domains, scoring vectors could perhaps be learned from experimental data). But this is the price to pay for defining rules from an ordinal input. This trade-off is very common in voting theory: the well-studied family of scoring rules in voting theory (including the Borda rule) proceeds exactly the same way; voters rank alternatives, and the ranks are then mapped to scores; the winning alternatives are those that maximize the sum of scores. If we aim at maximizing actual social welfare, then we have to elicit the voters' (numerical) utilities rather than just asking them to rank objects.

Instead of imposing an artificial scoring function, other approaches have been proposed to tackle this problem of dealing with ordinal preferences over objects in fair division of indivisible goods. [START_REF] Budish | The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes[END_REF] proposes to resort to competition: building on the well-known notion of Competitive Equilibrium from Equal Incomes (see, e.g., the book by [START_REF] Moulin | Cooperative Microeconomics: A Game-Theoretic Introduction[END_REF], he introduces, among others, the concept of Approximate-CEEI. Here, the central authority just fixes a vector of prices and lets the agents clear the market by themselves according to their own (ordinal) perception of the value of the items. Along the same line of ideas, he also introduces the notions of maximin share and envy-freeness up to one good to reconcile proportionality and envy-freeness with indivisible goods. All these notions have in common the fact that they are purely ordinal and do not rely on an interpersonal comparison of preferences. Note that several authors try to link this approach with the social welfare maximization problem. [START_REF] Brams | Efficient fair division-help the worst off or avoid envy?[END_REF], for instance, show the relative incompatibility between envy-freeness and egalitarian optimization (when they discuss whether one should rather "help the worst off or avoid envy"). [START_REF] Bouveret | Characterizing conflicts in fair division of indivisible goods using a scale of criteria[END_REF] also discuss the link between egalitarian optimization and several ordinal properties like maximin share and proportionality. Finally, in a very recent paper, [START_REF] Caragiannis | The unreasonable fairness of maximum Nash welfare[END_REF] show unexpected links between the optimization of Nash social welfare and the ordinal notions of maximin share and envy-freeness up to one good.

As noted by [START_REF] Budish | The multi-unit assignment problem: Theory and evidence from course allocation at Harvard[END_REF], beyond relying on purely ordinal criteria, another approach -used, e.g., by Harvard Business School -is to replace the one-shot competitive market by sequential competition, as in (deterministic or random) picking sequences. Once again, full elicitation of individual utilities is not needed here, and the presumed rationality of the individual choices at each round ensures efficiency of the overall allocation protocol. We discuss the virtues of this kind of protocols in Section 6, where we use them as a way to approximate the optimal social welfare.

Clearly, there are pros and cons to all approaches. In the purely ordinal approaches aforementioned, good solutions are often supposed to emerge from the agents' competition. The fairness of the solution comes from the constraints imposed by the benevolent arbitrator to the protocol (balanced picking sequence, vector of prices, etc.). However, this approach comes at a price, namely, at the loss of social welfare incurred (see Section 6). In our framework, we optimize social welfare but impose somewhat artificial individual utilities that may or may not be far away from the agents' actual utilities. However, [START_REF] Caragiannis | Voting almost maximizes social welfare despite limited communication[END_REF] analyze this ordinal-cardinal trade-off in voting and show that the induced distortion is generally quite low. Let us point out, as has been noted by a reviewer of the conference version of this paper, that this approach can also be seen as optimizing the external perception of fairness or welfare. Finally, we also point out that our approach has the same advantages as all scoring rules in voting (e.g., the Borda rule), namely, their conceptual simplicity. This feature is crucial in practical contexts where an allocation rule has to be understood by the users to be accepted.

The individual utilities are then aggregated using a monotonic, symmetric aggregation function that is to be maximized. The three we will use here are among the most obvious ones: utilitarianism (sum) and two versions of egalitarianism (min and leximin). Leximin refers to the (strict) lexicographic preorder over utility vectors whose components have been preordered nondecreasingly. Intuitively, a leximin-optimal utility vector maximizes the utility of the worst-off agent, then of the second worst-off agent, and so on. Formally, for a utility vector x = (x 1 , . . . , x n ), let x = (x 1 , . . . , x n ) denote some vector that results from x by rearranging the components of x nondecreasingly. Given another utility vector y and y's nondecreasingly sorted variant y , define x < leximin y if and only if there is some i, 0 ≤ i < n, such that x j = y j for all j, 1 ≤ j ≤ i, and x i+1 < y i+1 , and x ≤ leximin y means x < leximin y or x = y . Let leximin denote the maximum on a set of utility vectors according to ≤ leximin . For each scoring vector s, define three allocation correspondences:

F s,+ (P) = argmax π ∑ 1≤i≤n u > i ,s (π i ),
F s,leximin (P) = argmax π < leximin (u > 1 ,s (π 1 ), . . . , u > n ,s (π n )),
where P = (> 1 , . . . , > n ) is a profile and π = (π 1 , . . . , π n ) an allocation, and argmax π < leximin denotes the set of allocations with leximin-optimal utility vectors. Whenever we write F s, , we mean any one of F s,+ , F s,min , and F s,leximin .

Example 2 For n = 3 agents and m = 4 goods, G = {a, b, c, d}, let

P = (c > 1 b > 1 a > 1 d, c > 2 a > 2 b > 2 d, b > 3 d > 3 c > 3 a) = (cbad, cabd, bdca).
Then F (4,3,2,1),leximin (P) = {(c, ad, b)}.

Tie-Breaking

Similarly as in voting theory, an allocation rule is defined as the composition of an allocation correspondence and a tie-breaking mechanism, which breaks ties between allocations. One particular type of deterministic tie-breaking mechanism consists in defining it from a linear order over all allocations,2 or, when N and G are not both fixed, a collection of linear orders > T N,G (which we still denote by > T ) for all possible sets of agents and goods, N and G. We write π ≥ T π for (π > T π or π = π ). As in voting, if the output of a correspondence F(P) is not a singleton, then the top-priority allocation in F(P) is selected:

F T (P) = (max > T •F)(P) = max > T (F(P)).
We do not make any assumption as to how this tie-breaking relation is defined; our results hold independently of that.

One may also wonder whether it is possible to define an anonymous tie-breaking mechanism, as is common in voting. Formally, a tie-breaking mechanism > T is anonymous if and only if for any permutation σ over N and any pair of allocations (π, π ) over agents N and objects G, we have π > T π ⇔ σ (π) > T σ (π ), where σ (π) denotes the version of π where all shares have been permuted according to σ . In fact, the answer is negative (we omit the easy proof): There is no deterministic anonymous tie-breaking mechanism.

Properties of Scoring Allocation Rules

The properties we study in the paper are primarily defined for deterministic rules. Some of them will be immediately applicable to correspondences in general, and in that case we will also discuss whether or not they hold for correspondences. However, others do not generalize in a straightforward way to correspondences.3 For these properties, we will leave the study of whether they hold for scoring resource allocation correspondences for further research.

Separability

Slightly reformulating [START_REF] Thomson | Consistency and its converse: An introduction[END_REF], an allocation rule is consistent (we prefer to choose the terminology "separable") if for any allocation problem and any allocation π selected by the rule, the allocation rule chooses the same allocation regardless of whether π is restricted to a subgroup of agents and subset of goods or when reapplying the rule to a "reduced problem" obtained by imagining the departure of any subgroup of the agents with their share. As the definition generalizes easily to allocation correspondences, we define it for both.

Definition 2 For any profile P = (> 1 , . . . , > n ) over a set G, any allocation π = (π 1 , . . . , π n ), and any partition of the set of agents into two sets, N 1 and N 2 (i.e., N 1 ∪ N 2 = {1, . . . , n} and N 1 ∩ N 2 = / 0), let G j = i∈N j π i be the set of objects received in π by the agents in N j , for j ∈ {1, 2}.

1. An allocation rule F satisfies separability if for each P and π,

F(P N 1 ,G 1 ) = π 1 and F(P N 2 ,G 2 ) = π 2
, where π j denotes the restriction of π to N j and G j . 2. An allocation correspondence F satisfies separability if for each P and π, π ∈ F(P) if and only if

π 1 ∈ F(P N 1 ,G 1 ) and π 2 ∈ F(P N 2 ,G 2 ).
Unfortunately, it looks like almost all our rules violate separability. We give a counterexample that works for many choices of (s, ).

Example 3 For m = 9 goods and n = 3 agents, let ∈ {+, min, leximin} and let s be a strictly decreasing scoring vector. Consider the preference profile P = (adc f hgbei, beahgcd f i, c f abidegh).

F s, (P) consists of the unique allocation π = (adh, beg, c f i) for ∈ {min, leximin}, and F s,+ (P) consists of the unique allocation π = (ad, begh, c f i).

The restriction of P to the set {1, 2} of agents and the set {a, b, d, e, g, h} of goods is P = (adhgbe, beahgd).

For ∈ {min, leximin}, F s, (P ) consists of the unique allocation (adg, beh) = (adh, beg), and F s,+ (P ) consists of the unique allocation (adgh, be) = (ad, begh).

We conjecture that (perhaps under mild conditions on s and ), no positional scoring allocation rule is separable.

As the following example illustrates, not even the allocation correspondences F plurality, , ∈ {+, min, leximin}, are separable, where plurality denotes the scoring vector (1, 0, . . . , 0).

Example 4 Consider the preference profile P = (abc, abc, cba) of three goods and three agents. Then the allocation π = (a, / 0, bc) is in F plurality, , for each ∈ {+, min, leximin}. For min and leximin, this is the case because s 2 = 0 under plurality. Now consider the restriction of P to agents 2 and 3 and goods b and c. Then ( / 0, bc) / ∈ F plurality, = {(b, c)}, ∈ {+, min, leximin}.

Monotonicity

The monotonicity properties below state that if an agent ranks a received good higher, all else being equal, then this agent does not lose this good (monotonicity) or still receives the same bundle (global monotonicity).

Definition 3 1. An allocation rule F is monotonic if for every profile P, agent i, and good g, if F(P) gives g to i, then for every profile P resulting from P by agent i ranking g higher, leaving everything else (i.e., the relative ranks of all other objects in i's ranking and the rankings of all other agents) unchanged, it holds that F(P ) gives g to i. 2. F is globally monotonic if for every profile P, agent i, and good g, if F(P) gives g to i,

then for every profile P resulting from P by agent i ranking g higher, all else being equal, we have F(P ) i = F(P) i , where F(P) i = π i denotes agent i's share.

Clearly, global monotonicity implies monotonicity. These definitions extend to correspondences, but not in a unique way; therefore, we do not consider these extensions in this paper. In the following, T will refer to a tie-breaking relation as described in Section 3.2.

Theorem 1 For each scoring vector s, for each aggregation function ∈ {+, min, leximin}, and for each tie-breaking relation T , F T s, is monotonic.

PROOF. For notational convenience, we give the proof only for = +, but it extends in a straightforward way to min and leximin. Let P = (> 1 , . . . , > n ) be a profile over a set G of goods with g ∈ G and let P = (> 1 , > 2 , . . . , > n ) be a modified profile, where without loss of generality the first agent modifies her preferences such that g is ranked higher in > 1 than in > 1 , leaving everything else unchanged.

Let F T s,+ (P) = π = (π 1 , . . . , π n ) and let g ∈ π 1 . Let F T s,+ (P ) = π = (π 1 , . . . , π n ).
For a contradiction, suppose that g ∈ π 1 . For every good g = g, the rank of g in > 1 is either the same as or below the rank of g in > 1 , and since g ∈ π 1 , we have u > 1 ,s (π 1 ) ≤ u > 1 ,s (π 1 ). By monotonicity of utilitarian aggregation, this implies

u (π ) = u > 1 ,s (π 1 ) + n ∑ i=2 u > i ,s (π i ) ≤ n ∑ i=1 u > i ,s (π i ) = u(π ), ( 1
)
where u is the social welfare with respect to the modified profile P . Now, because > 1 has been obtained by moving g upwards in > 1 , we have u > 1 ,s (π 1 ) ≤ u > 1 ,s (π 1 ). Again by monotonicity of utilitarian aggregation, this implies

u (π) = u > 1 ,s (π 1 ) + n ∑ i=2 u > i ,s (π i ) ≥ n ∑ i=1 u > i ,s (π i ) = u(π). (2)
Since π ∈ F T s,+ (P) and π ∈ F T s,+ (P ), we have u(π) ≥ u(π ) and u (π ) ≥ u (π), which together with (1) and (2) implies u (π) = u(π) = u(π ) = u (π ). Now, since u(π) = u(π ) and F T s,+ (P) = π, we have π > T π . This, together with u (π) = u (π ), is in contradiction with F T s,+ (P ) = π . K

This proof does not establish global monotonicity of F T s, ; indeed, π = F T s, (P) does not imply π = F T s, (P ) in general. We have the following result.

Proposition 1 For each tie-breaking relation T , for each m ≥ 4, and for each strictly decreasing scoring vector s = (s 1 , . . . , s m ), allocation rule F T s,+ is not globally monotonic.

PROOF. We consider the following three profiles:

P = (g 1 g 2 g 3 • • • g m , g m g 1 • • • g m-1 ), P = (g 2 g 1 g 3 • • • g m , g m g 1 • • • g m-1
), and

P = (g 2 g 3 g 1 • • • g m , g m g 1 • • • g m-1
). The unique optimal allocation in F T s,+ (P) assigns object g m to agent 2 and all remaining objects to agent 1. Moving object g 2 in agent 1's linear order higher gives profile P . If F T s,+ (P ) gives g 1 to agent 2, we are done. Otherwise, moving object g 3 in agent 1's already changed linear order higher gives profile P . Then, agent 2 gets object g 1 . K

In order to show that F T s,min and F T s,leximin do not satisfy global monotonicity, the approach of computing a winning allocation and showing that this allocation is not optimal for the modified profile seems to fail. Instead, we apply a utility-bounding approach. Let OPT(P) denote the maximum egalitarian social welfare of a given preference profile P, that is,

OPT(P) = max π min 1≤i≤n {u > i ,s (π i )}.
Theorem 2 Let T be a tie-breaking relation. For each even m ≥ 4 and for each strictly decreasing scoring vector s = (s 1 , . . . , s m ), allocation rules F T s,min and F T s,leximin do not satisfy global monotonicity. This also holds for each odd m ≥ 7 provided that s additionally satisfies s 1s 2 + s 3s 4 > s m .

PROOF. Consider the following two profiles of two agents:

P = (g 1 g 2 • • • g m , g 1 g 2 • • • g m ); P = (g m g 1 • • • g m-1 , g 1 g 2 • • • g m ).
Let π = F T s,min (P) and, without loss of generality, let agent 1 be the agent that receives object g m , that is, g m ∈ π 1 . Thus, profile P is a valid change of P with respect to global monotonicity. We show that F T s,min (P ) = π. For the sake of contradiction, suppose that π = F T s,min (P ). Now we will derive an upper bound of ∑ i even s i for u > 1 ,s (π 1 ), agent 1's utility under the optimal allocation π with respect to the original preferences > 1 . We then reach a contradiction by giving another allocation where every agent realizes more utility than ∑ i even s i with respect to their original preferences.

Since π is also optimal for P , we have for i ∈ {1, 2},

u > i ,s (π i ) ≥ max π min 1≤i≤2 {u > i ,s (π i )} = OPT(P ),
where we maximize over all possible allocations π. Note that agent 2's preference is the same in P and P , i.e., > 2 = > 2 . Hence, u > 2 ,s (π 2 ) = u > 2 ,s (π 2 ). We distinguish between an even and an odd number of objects.

For even m: Since every allocation implies a lower bound for OPT(P ), consider π u where we assign in P even-numbered objects to agent 1 and odd-numbered objects to agent 2. It is clear that

u > 1 ,s (π u 1 ) = u > 2 ,s (π u 2 ) = ∑ i odd s i . Thus u > 2 ,s (π 2 ) = u > 2 ,s (π 2 ) ≥ OPT(P ) ≥ ∑ i odd s i .
Because P is a profile of identical preferences, we have the invariant

u > 1 ,s (π 1 ) + u > 2 ,s (π 2 ) = ∑ i s i
for every allocation π . Hence, we can use the lower bound for u > 2 ,s (π 2 ) to get the desired upper bound

u > 1 ,s (π 1 ) ≤ ∑ i s i -u > 2 ,s (π 2 ) ≤ ∑ i even s i .
Now we give a lower-bounding allocation π for OPT(P) where every agent gets utility more than ∑ i even s i . Assign in P the 1st (top-ranked), 5th, 9th, etc. and the 4th, 8th, 12th etc. object to agent 1. All remaining objects go to agent 2. Because

s 1 > s 2 > • • • > s m , we have u > 1 ,s (π 1 ) = s 1 + s 5 + s 9 + • • • + s m-1-2I[4|m] + s 4 + s 8 + s 12 + • • • + s m-2(1-I[4|m]) > ∑ i even s i ,
where

I[4 | m] is 1 if m is divisible
by 4, and otherwise 0. Note that we can split ∑ i even s i into s i 's, where i is a multiple of four, and into s j 's, where j is of the form 4k + 2, k ≥ 0. The former are covered by the same s i 's and the latter are covered by s j 's, where j is of the form 4k + 1, k ≥ 0. For u > 2 ,s (π 2 ), the argument is analogous if m ≥ 4. Since both agents realize more utility in π than agent 1 in π, π is not optimal for P (contradiction).

For odd m: Our lower-bounding allocation πu for OPT(P ) is similar to the above except for assigning object g m to agent 1. We need to consider only agent 2 because this agent realizes less utility: u > 2 ,s ( πu 2 ) = (∑ i odd s i )s m . Assuming (for a contradiction) that π is optimal for P as well, we have u > 2 ,s (π 2 ) ≥ (∑ i odd s i )s m , which gives u > 1 ,s (π 1 ) ≤ (∑ i even s i ) + s m . For a lower bound of OPT(P), we specify π as follows: Agent 1 always gets the 1st and 3rd object and starting with the 6th object every even-numbered object that follows. Agent 2 receives all remaining objects. Thus

u > 1 ,s ( π 1 ) = s 1 + s 3 + s 6 + s 8 + s 10 + • • • + s m-1 > ∑ i even s i + s m ,
which holds if and only if s 1 + s 3 > s 2 + s 4 + s m . For agent 2, we have

u > 2 ,s ( π 2 ) = s 2 + s 4 + s 5 + • • • + s m > ∑ i even s i + s m because of s 1 > s 2 > • • • > s m , if m ≥ 7.
It follows that π cannot be optimal for P (contradiction).

These results hold for F T s,leximin as well because we can take, without loss of generality, π = F T s,leximin (P) with g m ∈ π 1 and show in a contradiction that it is not even optimal under egalitarian social welfare in P, and hence cannot be optimal under leximin. K

Corollary 1 For each scoring vector s ∈ {borda, lex} for m ≥ 7 goods, allocation rules F T s,min and F T s,leximin do not satisfy global monotonicity. In addition, for each extended scoring vector s satisfying s 1 (m) > s 2 (m) > • • • > s m (m) for even m ≥ 4, allocation rules F T s-qi,min and F T s-qi,leximin do not satisfy global monotonicity either.

Object and Duplication Monotonicity

Object monotonicity is a dynamic property where additional goods are to be distributed. This means that when new objects are added, no agent is worse off afterwards. In order to define this notion, since some properties need comparability of bundles of goods, we lift agent i's linear order > i to a strict partial order i over 2 G by requiring monotonicity (A ⊃ B =⇒ A i B) and pairwise dominance (for all A ⊆ G {x, y}, A ∪ {x} i A ∪ {y} if x > i y). For strict partial orders we then follow the approach taken by [START_REF] Brams | Efficient fair division-help the worst off or avoid envy?[END_REF], [START_REF] Brams | Fair division of indivisible items[END_REF], and [START_REF] Bouveret | Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods[END_REF]: We distinguish between properties holding possibly (i.e., for some completion of the partial preferences) and necessarily (i.e., for all completions).

Definition 4 Let be a strict partial order over 2 G . We say A is possibly preferred to B (denoted by A pos B) if there exists a linear order * refining such that A * B. Analogously, A is necessarily preferred to B (denoted by A nec B) if for all linear orders * refining , we have A * B. Allowing indifference, we extend pos to pos and nec to nec . Now, we are ready to define possible and necessary object monotonicity. These properties are defined for deterministic rules only.

Definition 5 Let G be a set of goods. An allocation rule F satisfies possible object monotonicity if for each profile P = (> 1 , . . . , > n ) over G, for each profile P = (> 1 , . . . , > n ) that is obtained from P by adding one more good to G such that P is the restriction of P to G, and for each agent i, we have F(P ) i pos i F(P) i .

Note that we can add any number of goods for allocation rules that satisfy possible object monotonicity by repeated application of Definition 5. Interestingly, F T s,+ fails to satisfy object monotonicity in general. Actually, it only satisfies it for two agents and with a tie-breaking relation satisfying what we will call "object separability." Formally, a tiebreaking relation > T is object-separable if for any pair of allocations (π, π ), we have

π > T π ⇔ (π 1 , . . . , π i-1 , π i ∪ {g}, π i+1 , . . . , π n ) > T (π 1 , . . . , π i-1 , π i ∪ {g}, π i+1 , . . . , π n ) for any i and g ∈ i π i .
Proposition 2 Let s be a strictly decreasing scoring vector. For each object-separable tiebreaking relation T F T s,+ satisfies possible object monotonicity for n = 2 agents, yet does not do so for all n ≥ 3. PROOF. We first give a counterexample for n = 3 agents; it extends easily to more agents. Let m = 5 goods be given initially, G = {a, b, c, d, e}, and let P = (abcde, bcdea, abcde) be a preference profile. As F s,+ (P) = {(a, bcde, / 0), ( / 0, bcde, a)}, without loss of generality, let F T s,+ (P) = (a, bcde, / 0). Now, add two more goods, f and g, to G and let P = (abcde f g, bcd f gea, f gabcde) be the resulting new profile. We have F T s,+ (P ) = (ae, bcd, f g), and we see that F T s,+ (P ) 2 pos 2 F T s,+ (P) 2 . For n = 2, let P be a two-agent profile, and P a new one obtained by adding one more good g. As a notation, let rank Q > i (g j ) denote the rank of g j under > i with respect to profile Q ∈ {P, P }. Let F T s,+ (P) = ( π 1 , π 2 ) and F T s,+ (P ) = ( π 1 , π 2 ). Suppose that rank P > 1 (g) = rank P > 2 (g). Then it is easy to see that for each object g j = g, sign(rank P > 1 (g j )rank P > 2 (g j )) = sign(rank P > 1 (g j )rank P > 2 (g j )), which means that π ∈ F s,+ (P) if and only if (π 1 ∪ {g}, π 2 ) ∈ F s,+ (P ) and (π 1 , π 2 ∪ {g})} ∈ F s,+ (P ). Now let π ∈ F s,+ (P) {F T s,+ (P)}. Then we have π > T π. Since T is object-separable, we have

( π 1 ∪ {g}, π 2 ) > T (π 1 ∪ {g}, π 2 ) and ( π 1 , π 2 ∪ {g}) > T (π 1 , π 2 ∪ {g}). Hence, π can neither be (π 1 ∪ {g}, π 2 ) nor (π 1 , π 2 ∪ {g}). Therefore, π is either ( π 1 ∪ {g}, π 2 ) or ( π 1 , π 2 ∪ {g}).
In both cases, both agents are necessarily better off with their new share.

Now suppose that rank P > 1 (g) = rank P > 2 (g) -we can assume, without loss of generality, that rank P > 1 (g) > rank P > 2 (g) = k. It is easy to see that g and every object in π 2 that has rank less than k will be added to π 2 . This implies that, no matter whether agent 2 gets more goods with rank greater than k, we have π 2 pos 2 π 2 . We now prove that π 1 ⊇ π 1 . First, it is obvious that π 1 contains all objects belonging to π 1 that are ranked above g.

To prove that π 1 also contains all objects belonging to π 1 that are ranked strictly below g, we will first observe that for all such objects g * , rank P > 1 (g * ) ≤ rank P > 2 (g * ). Indeed, from rank P > 2 (g * ) < rank P > 2 (g) we can deduce that

rank P > 2 (g * ) = rank P > 2 (g * ) < rank P > 2 (g) < rank P > 1 (g) < rank P > 1 (g * ).
As rank P > 1 (g * )+1 = rank P > 1 (g * ), it follows that rank P > 1 (g * ) > rank P > 2 (g * ), which contradicts the fact that g * ∈ π 1 . Therefore, rank P > 2 (g * ) > rank P > 2 (g), and this implies that

rank P > 2 (g * ) = rank P > 2 (g * ) + 1 ≥ rank P > 1 (g * ) + 1 = rank P > 1 (g * ).
Suppose that rank P > 1 (g * ) < rank P > 2 (g * ). Then obviously g * ∈ π 1 . Suppose now that rank P > 1 (g * ) = rank P > 2 (g * ), and suppose that g * ∈ π 2 . Since g * has the same rank for both agents, this means that ( π 1 ∪ {g * }, π 2 {g * }) also belongs to F s,+ (P ), and is eliminated by T . Now observe that since rank P > 1 (g * ) = rank P > 2 (g * ), we have rank P > 1 (g * ) = rank P > 2 (g * ). This basically means that ( π 1 {g * }, π 2 ∪ {g * }) also belongs to F s,+ (P), and thus that π > T ( π 1 {g * }, π 2 ∪ {g * }). Using object separability of T to successively remove all objects but g * yields ({g * }, / 0) > T ( / 0, {g * }). Now using once again object separability of T to successively add all objects according to π yields ( π 1 ∪ {g * }, π 2 {g * }) > T π . A contradiction, proving that g * ∈ π 1 , which in turn completes the proof. K Proposition 3 For each tie-breaking relation T and for each strictly decreasing scoring vector s, F T s,min and F T s,leximin do not satisfy possible object monotonicity.

PROOF. For m = 5 goods and n = 2 agents, consider the preference profile P = (abcde, deacb).

The unique winning allocation for F s,leximin (P) is π = (abc, de), with utility vector (s 1 + s 2 + s 3 , s 1 + s 2 ), and for F s,min (P) allocation π = (ab, cde)

with utility vector (s 1 + s 2 , s 1 + s 2 + s 4 ) is optimal as well. If the tie-breaking relation picks π, consider the following updated preference profile when adding an additional good f , P = (abc f de, deacb f )

whose unique winning allocation is (ab f , cde)

with utility vector (s 1 + s 2 + s 4 , s 1 + s 2 + s 4 ). If the tie-breaking relation picks π , consider

P = (abcde f , deac f b)
with the unique winning allocation (abc, de f )

with utility vector (s 1 + s 2 + s 3 , s 1 + s 2 + s 5 ). This completes the proof. K

After having studied monotonicity with respect to the set of objects, we will now focus on monotonicity with respect to the set of agents. This kind of monotonicity has a natural translation in terms of voting power: to give more voting power to a voter, one can just allow her to vote twice (or more). In other words: duplicating a voter will give more weight to her ballot, and thus may give her a higher chance to be heard. This property has a natural translation to the resource allocation context: informally, two agents having identical preferences will get a better share together than if they were only one participating in the allocation process. More formally: Definition 6 Let P = (> 1 , . . . , > n ) be a profile over G and P = (> 1 , . . . , > n , > n+1 ) be its extension to n + 1 agents, where > n+1 equals > n . An allocation rule F satisfies possible duplication monotonicity if F(P ) n ∪ F(P ) n+1 pos n F(P) n ; and it satisfies necessary duplication monotonicity if F(P ) n ∪ F(P ) n+1 nec n F(P) n . It turns out that several scoring allocation rules satisfy at least possible duplication, provided that we use duplication-compatible tie-breaking relations, namely, relations T that satisfy the following property. Let π and π be two allocations on (> 1 , . . . , > n , > n+1 ), where n + 1 is a duplicate of agent n as above, i.e., > n+1 equals > n . Then π > T n+1 π implies that (π 1 , . . . ,

π n ∪ π n+1 ) = (π 1 , . . . , π n ∪ π n+1 ) or (π 1 , . . . , π n ∪ π n+1 ) > T n (π 1 , . . . , π n ∪ π n+1
). An example of such a tie-breaking relation is to consider T = T lex as the lexicographic relation over the set Π of all possible allocations. For every pair of allocations, π = (π 1 , . . . , π n ) and π = (π 1 , . . . , π n ), we say π > T lex π if π i is lexicographically preferred to π i by agent i, for the smallest i ∈ {1, . . . , n} such that π i and π i are different for agent i. It is not hard to check that T lex is indeed a duplication-compatible tie-breaking relation. Given that a duplication-compatible tie-breaking relation always exists, we have the following result.

Theorem 3 Let T be a duplication-compatible tie-breaking relation. For each scoring vector s, F T s,+ satisfies possible and necessary duplication monotonicity, and F T s-qi,leximin and F T lex,leximin both satisfy possible duplication monotonicity.

PROOF. For F T s,+ , each object goes to an agent ranking it best. Every object that goes to agent n in the first profile will go to either n or n+1 in the second one (this is also guaranteed by the duplication-compatible tie-breaking relation in case of ties with other agents). n and her duplicated version will thus get exactly the same objects, hence the result.

For F T s-qi,leximin , each agent will get either m /n or m /n + 1 objects. Since 2 • m /(n+1) > m /n + 1, agent n and the duplicated agent n + 1 will receive strictly more objects than the original agent n, hence proving possible duplication monotonicity.

For F T lex,leximin , every optimal allocation satisfies that the minimum over all agents i of the rank of the first object received by i, denoted by f (i), is maximized. Moreover, if i is not among the agents whose f (i) is minimal, then agent i only receives one object (and is satisfied with it). If that happens for the original agent n, the duplicated agents n and n + 1 will together be possibly better off with their new share, since they will either receive at least one object each (if there are enough objects), or only one of them will receive the same object as original agent n (if this is not the case). If the original agent n is among the agents whose f (i) is minimal, then either it is possible to give a better object than the object associated with f (i) to one of n and n + 1 (in this case we are done), or this is not possible, in which case one of n and n + 1 will receive the object associated with f (i), and the other one, whose first object cannot be valued as high as f (i), will receive all the remaining objects (including the former ones of agent n), so both of them will be at least as satisfied as before. K

A summary of the considered scoring allocation rules and the properties they satisfy is given in Table 1. We use the symbol to indicate that some property is satisfied by some scoring allocation rule (possibly under the conditions listed next to ), the symbol to indicate that it is not (again, possibly under the conditions listed next to ), and we write a question mark whenever this is an open issue. For m ≥ 4 and strictly decreasing scoring vector. For m ≥ 4 and strictly decreasing scoring vector, or for each odd m ≥ 7 with s 1s 2 + s 3s 4 > s m .

For n = 2, object-separable tie-breaking relation, and strictly decreasing scoring vector. † For n ≥ 3 or non-object-separable tie-breaking relation. ‡ For duplication-compatible tie-breaking relation. ¶ For strictly decreasing scoring vector.

Table 1: Properties of scoring allocation rules 5 Winner Determination

In this section, we study the following question. What is the complexity of determining an optimal allocation for a given scoring vector and a given aggregation function? For a given scoring vector s and a given aggregation function F s, , where ∈ {+, min, leximin}, define the following problem concerning winner determination.

F s, -OPTIMAL-ALLOCATION (F s, -OA)

Given:

A profile P of n agents' rankings on a set G of indivisible goods and an allocation π of G. Question:

Is π in F s, (P)?

It is easy to see that F s,+ -OA is in P and both F s,min -OA and F s,leximin -OA are in coNP for every scoring vector s.

The search problem F s, -FIND-OPTIMAL-ALLOCATION (F s, -FOA) seeks to actually find an optimal allocation for a given profile of rankings on a given set of indivisible goods. Clearly, F s,+ -FOA is solvable in polynomial time for any scoring vector s: every good is simply given to an agent who ranks it best. F s,min -FOA and F s,leximin -FOA are much less easy in general. 4 We have the following easy polynomial-time upper bounds for certain restricted variants.

Proposition 4 (i) For each k, F k-app,min -FOA is solvable in polynomial time.

(ii) F s,min -FOA and F s,leximin -FOA are solvable in polynomial time for every scoring vector s if there are a constant number of goods.

F k-app,min -FOA in (i) of Proposition 4 is a special case of the problem of maximizing egalitarian social welfare with a {0, 1}-additive function, known to be solvable in polynomial time by applying a network flow algorithm [START_REF] Golovin | Max-min fair allocation of indivisible goods[END_REF]. For a constant number of goods, F s,min -FOA and F s,leximin -FOA are solvable in polynomial time because there are n m allocations.

In addition, we will study the following decision problem associated with the value of an optimal allocation. F s,+ -OPTIMAL-ALLOCATION-VALUE (F s,+ -OAV)

Given:

A profile P = (> 1 , . . . , > n ) of n agents' rankings on a set G of indivisible goods and k ∈ Q + . Question:

Is there an allocation π = (π 1 , . . . , π n ) such that ∑ 1≤i≤n u > i ,s (π i ) ≥ k?

Analogously, we define F s,min -OAV by asking for the same input whether or not

min 1≤i≤n u > i ,s (π i ) ≥ k,
and we similarly define F s,leximin -OAV where instead of a bound k in the input we have an ordered list (k 1 , . . . , k n ) of nonnegative rational numbers and we ask whether or not

(u > 1 ,s (π 1 ), . . . , u > n ,s (π n )) ≥ leximin (k 1 , . . . , k n ).
Clearly, F s,+ -OAV is in P. Since the value of a given allocation for min and leximin can be computed in polynomial time, F s,min -OAV and F s,leximin -OAV are in NP for each scoring rule s. For lexicographic scoring and quasi-indifference, these bounds are tight.

Theorem 4 F lex,min -OAV and F lex,leximin -OAV both are NP-complete.

PROOF. We only give the proof for F lex,min -OAV (since it can be easily adapted to work for F lex,leximin -OAV as well), by a reduction from the following well-known NP-complete problem (see, e.g., the book by [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]:

EXACT-COVER-BY-3-SETS (X3C)

Given:

A collection C = {C 1 , . . . ,C p } of 3-element subsets of a set X of size 3q (where q < p). Question:

Is there an exact cover of X, i.e., is there a subcollection C ⊂ C of size q such that each element of X appears in exactly one member of C ?

From a given instance (X, C ) of X3C, with C = {C 1 , . . . ,C p } a collection of 3-element subsets of X as above, we create an instance of the allocation problem as follows. We create one good g i out of each element x i from X, and a set F = { f 1 , . . . , f p-q } of pq goods, which makes a total of 2q + p goods. We create a set {1, . . . , p} of p agents. Agent i has the following preferences:

f 1 > i • • • > i f p-q > i C i > i X C i ,
where a set S in this order stands for all the goods of S in any fixed order. 5We claim that (X, C ) is a positive instance of X3C if and only if its constructed F lex,min -OAV instance has an allocation with an egalitarian collective utility greater than or equal to 2 3q-1 + 2 3q-2 + 2 3q-3 under lexicographic scoring.

(⇒) Suppose that C is a positive instance of X3C and let C be the corresponding exact cover of X. Let π be an allocation that gives to each agent i the goods corresponding to C i if C i ∈ C , and one good from F otherwise. Such an allocation π exists, since (i) the elements in C do not overlap, and (ii) there are exactly pq agents i such that C i ∈ C (and hence each such agent can receive a different f k ∈ F). It is easy to see that each agent receiving one good from F has a utility greater than 2 3q , and each agent receiving one C i has a utility equal to 2 3q-1 + 2 3q-2 + 2 3q-3 .

(⇐) Let π be an allocation of egalitarian utility at least 2 3q-1 + 2 3q-2 + 2 3q-3 . Since F = pq, at least q agents (call them "unhappy") do not receive any good from F. Suppose an unhappy agent i receives only a proper subset of the goods from C i . Then the greatest utility she can get is 2 3q-1 + 2 3q-2 + 2 3q-3 -1, if she gets her two preferred goods from C i and all the goods from X C i . Hence, for the egalitarian utility to be at least 2 3q-1 + 2 3q-2 + 2 3q-3 , each unhappy agent must get at least all the goods from C i . Since the agents' shares cannot overlap, there can only be q unhappy agents, and their shares correspond to an exact cover of X.

Since this reduction can be computed in polynomial time, the proof is complete. K Theorem 5 For each fixed ε, 0 < ε 1, F ε -qi,min -OAV and F ε -qi,leximin -OAV both are NP-complete.

PROOF. Once again, we only give the proof for F ε -qi,min -OAV, as its adaption to F ε -qi,leximin -OAV is easy. The proof is again by a reduction from the NP-complete problem X3C. Given an instance (X, C ) with C = {C 1 , . . . ,C p } and X = 3q, create the following F ε -qi,min -OAV instance. The set of objects is G = {g 1 , . . . , g 3q } ∪ D, where D = {d 1 , . . . , d 4(p-q) } is a set of dummy objects, hence G = 4pq. There are p agents, where each agent i, 1 ≤ i ≤ p, has the preference C i > X C i > D, and the bound is k = 3 + (12p -3q -6)ε.

(⇒) Suppose that (X, C ) is a positive instance of X3C and let C be an exact cover of X. Let π be an allocation that gives to each agent i the goods corresponding to C i if C i ∈ C , and otherwise four arbitrary goods from D that are still available. So π is such that pq agents receive four goods (and thus have a utility greater than 4), and q agents receive their three best goods, and hence they each have a utility of 3 + (12p -3q -6)ε.

(⇐) Let π be an allocation of egalitarian utility at least 3+(12p-3q-6)ε. By definition of QI, all agents must get at least three goods. Moreover, given the number of agents and goods, at least q "unhappy" agents must get exactly three goods (where "unhappy" is defined as in the proof of Theorem 4). Finally, given the bound, these unhappy agents must all get their three preferred goods, that is, C i for agent i. Hence, all the C i for the q unhappy agents must not overlap: this is an exact cover for (X, C ). K

An anonymous reviewer of a previous draft of this paper obtained the following result, and we are very grateful for his or her consent to include the proof.

Theorem 6 F borda,min -OAV and F borda,leximin -OAV are NP-complete.

PROOF. The construction to show NP-hardness is highly similar to the ones presented above. Again, we only show the proof for F borda,min -OAV. Let (X, C ) be a given X3C instance with C = {C 1 , . . . ,C p } and X = 3q. Pad the X3C instance so that 3q -4 = 2(pq) by appropriately adding new elements to X and forming new subsets that consist of these new elements only (this is similar to the padding employed by [START_REF] Faliszewski | The complexity of power-index comparison[END_REF]. Create objects G = {g 1 , . . . , g 3q } ∪ D, where D = {d 1 , . . . , d 2(p-q) } is a set of dummy objects. There will be p agents, one for each subset C i , with preference D > C i > X \C i . All the agents agree on their ranking of objects in D. Now, either an agent receives set C i with value 9q-3, or she receives two higher valued goods with values 6q-3-i and 3q + i, or 9q -3 in total. Thus set k = 9q -3 (consider (k, . . . , k) for F borda,leximin -OAV).

(⇒) Analogous to the proof above.

(⇐) Note that to obtain a utility of at least 9q -3 for each of the p agents, everyone needs to get at least two goods. Since there are 3q + 2(pq) = q + 2p goods, there are at least pq agents that receive only two goods. To obtain a utility of at least 9q -3 with only two goods, the lower ranked good must be placed in the first 2(pq) positions. This implies that the pq agents receiving only two goods receive those 2(pq) goods that are placed at the beginning of every preference. Then the remaining q agents must all receive the goods at positions 3q, 3q + 1, and 3q + 2 to obtain a utility of 9q -3, and this corresponds to an exact cover of X. K

Using a slight adaption of the proofs of Theorems 4 and 5, we can show that F lex,min -OA and F ε -qi,min -OA are both coNP-complete. These proofs, however, do not directly extend to the problems F lex,leximin -OA and F ε -qi,leximin -OA. Proposition 5 For s ∈ {lex, ε-qi}, F s,min -OA is coNP-complete. PROOF. For s = lex, we can use a reduction from a restricted version of the complementary of X3C, which we will call R-X3C and define as follows:

PROOF. It is enough to prove the theorem for F s,leximin -OA and F s,leximin -FOA, since every optimal allocation under leximin aggregation is also a winner under egalitarian aggregation.

To show that the F s,leximin -FOA is solvable in polynomial time for Borda and quasiindifference, consider the following algorithm. Let G = {g 1 , . . . , g m } be a set of m goods and N = {1, . . . , n} be a set of n agents. Our algorithm runs in m steps: in the jth step it computes all possible allocations that assign the first j goods to the n agents; such allocations are encoded as n-dimensional vectors and are collected in the set V j . Let V 0 be the set containing only the vector 0. In each step j, for each vector v ∈ V j-1 compute one vector v i = v + s rank(g j ,> i ) • e i for each agent i, 1 ≤ i ≤ n, where e i denotes the ith unit vector. This vector v i is then added to V j after checking for duplicates so as to avoid them. It is easy to see that V j ≤ V m for all j ≤ m.

For Borda scoring, every entry of each vector in V m is bounded above by m(m+1) /2 and thus V m is bounded by O(m 2n ). Before adding a new vector v i to V j , it can be checked in polynomial time whether there already is such a vector in V j , so duplicates can be avoided by the algorithm. Therefore, each step will take time O(m 4n ) and since we have m steps in total, the running time of the algorithm will be in O(m 4n+1 ), which is polynomial in m if n is constant.

For the quasi-indifference scoring vector, ε-qi for some ε, 0 < ε 1, every entry of each vector in V m has the form p + q • ε where p, q ∈ Z, 0 ≤ p ≤ m and 0 ≤ q ≤ m(m-1) /2, and thus V m is bounded by O(m 3n ). Hence, checking for duplicates in each step will take time O(m 6n ) and the overall complexity of the algorithm is bounded by O(m 6n+1 ), which again is polynomial in m.

Note that in the above algorithm it is always possible to store an allocation corresponding to each vector in polynomial time, and thus the algorithm can also output an optimal allocation. This solves F s,leximin -FOA (and, therefore, F s,leximin -OA as well) in polynomial time for Borda scoring and quasi-indifference. K

The proof of Theorem 7 actually shows:

Corollary 2 For each scoring vector s = (s 1 , . . . , s m ) where ∑ m i=1 s i is bounded above by a polynomial in m and for each ∈ {min, leximin}, F s, -OA and F s, -FOA are solvable in polynomial time if the number of agents is constant.

Table 2 gives an overview of the complexity results stated in this section. Note that the right column gives NP-hardness instead of NP-completeness results because F s, -FOA is a functional, not a decision problem; "NP-hardness" for a functional problem is understood as this problem "not being polynomial-time solvable unless P = NP."

Garg et al (2010) obtain complexity results that are related to ours. In particular, for two possible choices of ranks (that is, two indifference classes), finding a leximin-optimal assignment is easy. For three indifference classes the maximization problem is NP-hard. For more indifference classes, however, their hardness proof relies on the fact that indifference classes can be empty and thus their result does not extend to our setting. [START_REF] Darmann | Maximizing Nash product social welfare in allocating indivisible goods[END_REF] show that the optimal allocation value problem with respect to Nash social welfare is NP-complete for Borda and lexicographic scoring and is in P for k-approval, which is similar to our results on the min aggregation function.

Approximation

In this section, we are concerned with different types of approximation results for scoringbased allocation of indivisible goods. We first consider the problem of finding an optimal allocation for egalitarian social welfare under lexicographic scoring in Section 6.1, and will then (in Section 6.2) turn to the "price of picking-sequence elicitation-freeness," where a so-called picking sequence is a simple protocol for allocating indivisible goods without any need to elicit the agents' preferences first. This model is initially due to [START_REF] Kohler | A class of sequential games[END_REF]. Later, [START_REF] Brams | Fair Division: From Cake-Cutting to Dispute Resolution[END_REF] have studied a particular version of this protocol for specific kinds of alternating sequences, and [START_REF] Bouveret | A general elicitation-free protocol for allocating indivisible goods[END_REF] have introduced a more general formal model of this kind of protocols. More recently, Aziz et al (2015b) have investigated, in particular, the conditions under which an allocation is possibly or necessarily reachable by applying a picking sequence with a specific class of policies.

6.1 Approximation Algorithm for Finding an Optimal Allocation for Egalitarian Social Welfare under Lexicographic Scoring

As we can see in Table 2, F s, -OAV is NP-complete for many combinations of a scoring vector with an aggregation function. This raises the issue of whether we at least can find good approximations of optimal allocations in polynomial time. It turns out that this indeed is the case for F lex,min -OAV.

Proposition 6 There exists a ( 1 /2)-approximation algorithm for F lex,min -FOA.

PROOF. Let (N, G, > 1 , . . . , > n ) be an instance of the problem. Our simple algorithm works as follows. Slightly abusing notation by overloading the symbols N and G, we first construct a weighted complete bipartite graph K n,m = (N ∪ G, E), where we have a vertex i ∈ N for every agent i, a vertex g j for every good g j , and a weight function w that is defined by w(i, g j ) = s rank(g j ,> i ) , where s = lex is the lexicographic scoring vector. We create a graph G by deleting all the edges in G of weight less than 2 m-1 . If there exists a maximum matching M of G then return M . Otherwise, we replace m -1 by m -2 and repeat until we find a maximum matching. A matching M returned by the algorithm will correspond to an incomplete allocation of m goods to n agents. By assigning all remaining goods to agents greedily, we obtain a complete allocation π. We now prove that the egalitarian social welfare of π is within a factor of 1 /2 of the optimal one. Indeed, assume that π * is an optimal allocation. The collective utility of π * has the form of (2 k 1 +α 1 , . . . , 2 k n +α n ), where m -n ≤ k i ≤ m -1 and α i < 2 k i . Obviously, an allocation that has a collective utility of (2 k 1 , . . . , 2 k n ) will exactly correspond to a maximum matching of K n,m . Without loss of generality, we can assume that k n = min{k 1 , . . . , k n }. Then it is easy to see that the minimum weight edge in M must have weight 2 k n . Finally, since the egalitarian social welfare of π is at least

2 k n > 1 2 2 k n + α n = 1 2 min 2 k 1 + α 1 , . . . , 2 k n + α n ,
the proof is complete. K

The Price of Picking-Sequence Elicitation-Freeness

We now use a different approach: rather than designing a dedicated algorithm for each rule, we will study a general allocation rule -picking sequences -and investigate the price to pay for that, namely, the ratio between the value of the optimal allocation and the value of the allocation obtained by applying a picking sequence. Picking sequences are simple protocols for allocating indivisible resources without eliciting the agents' preferences first [START_REF] Kohler | A class of sequential games[END_REF][START_REF] Brams | Fair Division: From Cake-Cutting to Dispute Resolution[END_REF][START_REF] Bouveret | A general elicitation-free protocol for allocating indivisible goods[END_REF]Aziz et al 2015b). They consist of asking agents to pick objects one after the other, following a predefined sequence.

Formally, a (picking) policy is a sequence σ = σ 1 • • • σ m ∈ {1, . . . , n} m , where at each step, agent σ i picks her most preferred object among those remaining (where we assume agents to use only their sincere picking strategies). For instance, for m = 4 goods and n = 2 agents, 1221 is the sequence where agent 1 picks an object first, then agent 2 picks two objects, and 1 takes the last object. The formal definition of an allocation induced by a picking sequence and a profile, assuming that agents act according to their true preferences, can be found in the paper by [START_REF] Bouveret | A general elicitation-free protocol for allocating indivisible goods[END_REF].

An interesting question is whether using such protocols (without elicitation), or simulating them from the known preferences (after full elicitation of the agents' rankings) gives a good approximation of our scoring rules: what is the loss incurred by the application (simulated or not) of the picking sequence with respect to an optimal allocation? We give here two results for Borda scoring: one for egalitarianism, one for utilitarianism. One may wonder why we should look for such a result in the case of utilitarianism, given that there is a straightforward greedy algorithm that outputs an optimal allocation. The reason is that picking sequences (when actually used, as opposed to simulated ones) do better on one criterion: they are very cheap in communication, as agents only reveal part of their preferences by picking objects, as opposed to revealing their full preferences in the case of a centralized protocol.

As noticed above, sequential allocation rules are appealing because they require even less input from the agents than singleton-based allocation rules; however, this gain in communication comes with a loss of social welfare. To quantify this loss, we define the following measure.

Definition 7 Given a policy σ (for n agents and m objects), a scoring vector s, and an aggregation function ∈ {+, min}, the (multiplicative) price of picking-sequence elicitationfreeness of σ , denoted by MPEF s, (σ ), is the worst-case ratio in social welfare between an optimal allocation for F s, and the sequential allocation, among all profiles with m goods.

Note that we could have defined the notion of additive price of picking-sequence elicitationfreeness in the same way, but the multiplicative version seems to give results which are easier to interpret. Since we focus on s = borda only, we from now on simply write MPEF (σ ) to mean MPEF borda, (σ ).

We now give results about the quality of the outcome of balanced picking sequences

(12 • • • n) m n
, assuming that m is a multiple of n. For instance, if there are m = 6 goods and n = 3 agents, σ = 123123 is balanced. Computing the price of picking-sequence elicationfreeness is challenging. We focus on the regular policy σ n R = (1 • • • n) * , but we can get similar results for other fair policies like (1

• • • nn • • • 1) * .

Lower Bounds

A naive algorithm for computing the additive or multiplicative PEF for a given value m is simply to generate all possible profiles and for each of them compute an optimal allocation from which it is possible to deduce the loss incurred by the sequential allocation. However, the number of profiles grows exponentially in m, and computing an optimal allocation might be intractable. Still, it is possible to lower-bound the PEF for a given m by computing the incurred loss for a subset of all possible profiles. In Figure 1, we plot the best such lower bounds we could achieve experimentally for the multiplicative PEF. In the case = +, each data point corresponds to two millions profiles randomly generated (with a uniform distribution). In the case = min, for each data point, random profiles were generated until a threshold of 1,800 seconds of computation time was reached. The conclusions that can be drawn from Figure 1 is that for = +, in the worst and average cases the loss seems to tend to the neighborhood of 1. The conclusions for = min are somewhat similar, but they are less firm, as we have not been able to go as far in the number of objects as for = +.

We now give a formal lower bound for MPEF for = + and the regular policy.

Proposition 7 For m = kn objects,

MPEF + (σ n R ) ≥ 1 + mn -m -n 2 + n m 2 + mn ,
and thus we have MPEF + (σ n R ) ≥ 1 + n-1 m +Θ ( 1 /m 2 ) when m tends to +∞ with n being held constant.

PROOF. We construct a profile P = (> 1 , > 2 , . . . , > n ) where for each agent i, > i is defined so that (a) for all j and j such that j < j ≤ mi, we have g j > g j ; (b) for all k and k such that mi + 1 ≤ k < k , we have g k > g k ; and (c) for all j ≤ mi and for all k ≥ mi + 1, we have g j < g k :

1 : g m g 1 g 2 • • • g n • • • g m-1 2 : g m-1 g m g 1 g 2 • • • g m-2 . . . n -1 : g m-n+2 g m-n+3 • • • g m g 1 g 2 • • • g n-1 g n g n+1 • • • g m-n+1 n : g m-n+1 g m-n+2 • • • g m g 1 g 2 • • • g n-1 g n g n+1 • • • g m-n
In the above profile, the allocation obtained by applying the picking sequence protocol is shown as boxes; one F borda,+ -optimal allocation is indicated by stars. For each j ∈ {1, . . . , n}, object g m-j+1 is assigned to agent j in the sequential and an optimal allocation. For each j ∈ {1, . . . , m -n}, object g j is assigned to agent 1 in an optimal allocation with utility mj. However, if j ≡ i (mod n), then g j is assigned to agent i in the sequential allocation with utility mj -(i -1). Summing over all objects leads to the result. K

Upper Bounds

We now also provide formal upper bounds for MPEF for = + and = min, and the regular policy.

Proposition 8 For m = kn objects, MPEF + (σ n R ) ≤ 2 -mn mn + n , and thus MPEF + (σ n R ) ≤ 2 -1 n +Θ ( 1 /m) when m tends to +∞ with n being held constant.

PROOF. Let g ni+ j be the object picked at the (ni + j)th time step. Because σ is balanced, it is picked by agent j. Let u p (g) be the score associated to object g by player p: u p (g) = u > p ,s ({g}) = s rank(g,> p ) . The loss of social welfare associated with σ is the sum of the losses over each object g ni+ j , which can be expressed as max 0≤ j ≤n-1 u j (g ni+ j )u j (g ni+ j ).

At step ni + j, when it is agent j's turn to pick an object, the following facts hold: (a) no more than ni + j -1 objects have already been picked, so agent j will pick an object among her ni + j best objects; (b) object g ni+ j hasn't been picked by any other agent so far; therefore, g ni+ j is not among the best i objects of any agent. (a) and (b) imply (a') u j (g ni+ j ) ≥ s ni+ j = m -(ni + j) + 1 and (b') u j (g ni+ j ) ≤ s i = mi + 1. From (a') and (b') we get that the ratio of social welfare associated with object g ni+ j is upper-bounded by m-i+1 m-(ni+ j)+1 . Summing over all objects leads to the result. K

Corollary 3 For n = 2 agents and m = 2k objects,

1 + m -2 m(m + 2) ≤ MPEF + (σ 2 R ) ≤ 3 2 + 3 2m + 2 .

Conclusions and Outlook

Generalizing earlier work by [START_REF] Brams | Efficient fair division-help the worst off or avoid envy?[END_REF] and [START_REF] Brams | Fair division of indivisible items[END_REF], we have defined in this paper a family of rules for the allocation of indivisible goods to agents that are parameterized by a scoring vector and an aggregation function. We have discussed a few key properties, and for each of them we have given some positive as well as some negative results about their satisfaction by scoring allocation rules. We have also determined the complexity of computing an optimal allocation for four important scoring vectors and three central aggregation functions (see Table 2). Finally, we have given some approximation results, some of which make use of picking sequences whose main purpose it is to avoid preference elicitation.

The relatively high number of negative results should be balanced against the satisfaction of several important properties (including monotonicity) together with the simplicity of these rules. And anyway, defining allocation rules of indivisible goods from ordinal inputs on other principles does not look easy at all. On the computational side, even if winner determination is difficult for many choices of s and (except for the trivial case of = +), these rather negative results should be tempered by the fact that in most practical settings the number of agents and items is sufficiently small for the optimal allocation to be computed, even when its determination is NP-hard. Moreover, the results of Section 6 show that good approximations of optimal allocations can often be determined with a very low communication cost.

Our results are not complete: for several properties we do not have an exact characterization of the scoring allocation rules that satisfy them. Moreover, as shown in Table 2, some of our complexity results are partial. Completing these complexity results, and obtaining exact characterizations of the allocation rules that satisfy our properties is left for further research.

An issue that we did not consider here is manipulability. Clearly, almost all of our rules are manipulable; characterizing exactly the family of scoring allocation rules that are manipulable (for a characterization of strategy-proofness of scoring allocation correspondences, see the work of Nguyen et al 2015) and measuring the extent to which our rules are computationally resistant to manipulation is clearly an interesting topic for further research.

  restriction of > (respectively, P) to G . Similarly, we denote the restriction of P to any subset N ⊂ N of agents by P N and the restriction of P to any subset N ⊂ N of agents and any subset G ⊂ G of goods by P N ,G .

F

  i ,s (π i )}, and

F

Fig. 1 :

 1 Fig. 1: Top: MPEF for = +, Borda scoring, and regular policies σ 2 R , σ 3 R , σ 4 R . Bottom: MPEF for = min, Borda scoring, and regular policies σ 2 R and σ 3 R .

Proposition 9

 9 For m = kn objects, MPEF min (σ n R ) ≤ 2mnm + n mn + 2nn 2 , and thus MPEF min (σ n R ) ≤ 2 -1 n +Θ ( 1 /m) when m tends to +∞ with n being held constant.PROOF. The best allocation one could hope for would give every agent her preferred k objects, and it has social welfare∑ k i=1 (mi + 1) = ∑ k i=1 (m + 1) -∑ k i=1 i.The worst case occurs when all agents have the same preference; in this case, the least well-off agent is n, who gets the objects he ranked n, 2n, . . . , and kn, and his utility (and therefore the social welfare) is∑ k i=1 s ni = ∑ k i=1 (mni + 1) = ∑ k i=1 (m + 1)n ∑ k i=1 i.Therefore, skipping the intermediate computation steps, we haveMPEF min (σ ) ≤ ∑ k i=1 (m + 1) -∑ k i=1 i ∑ k i=1 (m + 1)n ∑ k i=1 i = 2k(m + 1)k(k + 1) 2k(m + 1)nk(k + 1) = 2 -1 n + 2n 2 -4n + 2 mn + 2nn 2 ,which concludes the proof. KCorollary 4 For n = 2 agents and m = 2k objects,

  if s is part of the input (even for two agents with identical preferences)

		OA	OAV	FOA
	F s,+	in P	in P	polynomial time
	F s,min	coNP-complete *	NP-complete *	NP-hard *
	k-app	in P	in P	polynomial time
	m ∈ O(1)	in P	in P	polynomial time
	lex or ε-qi	coNP-complete	NP-complete	NP-hard
	borda borda or ε-qi, if n ∈ O(1)	: in :::: coNP in P	NP-complete in P	NP-hard polynomial time
	F s,leximin	coNP-complete *	NP-complete *	NP-hard *
	m ∈ O(1)	in P	in P	polynomial time
	lex or ε-qi borda borda or ε-qi, if n ∈ O(1)	: in :::: coNP : in :::: coNP in P	NP-complete NP-complete in P	NP-hard NP-hard polynomial time

*

Table 2 :

 2 Overview of complexity results ( :::: wavy :::::::: underline: partial results)

Note that the Borda scoring vector in voting is usually defined as (m -1, m -2, . . . , 1, 0). Here, together with[START_REF] Brams | Fair division of indivisible items[END_REF], we define the Borda scoring vector by fixing the score of the bottom-rank object to 1, meaning that getting it is better than getting nothing. For scoring voting rules, a translation of the scoring vector has obviously no impact on winner determination (see Observation

2.2 in the work of Hemaspaandra and Hemaspaandra 2007); for scoring allocation rules, however, it does.

This choice comes with a loss of generality, as there are tie-breaking mechanisms that are not defined this way (we thank a reviewer for this remark). Also, we rule out the possibility of randomly breaking ties.

This is the case for all properties expressing that an agent prefers a set of allocations to another set of allocations (and applies, e.g., to object monotonicity); for these properties there is not a unique way of generalizing the property, unlike in voting where this is well-known, e.g., for strategy-proofness. For a study of strategy-proofness for scoring allocation correspondences, we refer to the work of[START_REF] Nguyen | Strategy-proofness of scoring allocation correspondences for indivisible goods[END_REF].

If the scoring vector s is part of the input then the problem F s, -FOA, ∈ {min, leximin}, is NP-hard (though not strongly NP-hard in the sense ofGarey and Johnson 1978, 1979), even for two agents having identical preferences, by a direct reduction from PARTITION.

Here and later, we slightly abuse notation, as X and C i will refer both to the initial sets and their corresponding sets of goods.

Acknowledgements We are grateful to the anonymous ECAI'14 and COMSOC'14 reviewers for their helpful comments. In particular, we thank the reviewer who pointed out a proof sketch of Theorem 6 for her or his consent to include the result and its proof. This work was supported in part by Deutsche Forschungsgemeinschaft under grants RO 1202/14-1, RO 1202/14-2, and RO 1202/15-1, by a project of the DAAD-PPP / PHC PROCOPE program entitled "Fair Division of Indivisible Goods: Incomplete Preferences, Communication Protocols and Computational Resistance to Strategic Behavior," by COST Action IC1205 on Computational Social Choice, by a grant for gender-sensitive universities funded by the NRW Ministry for Innovation, Science, and Research, and by Vietnam's National Foundation for Science and Technology Development (NAFOSTED Project No. 102.01-2015.33).

R-X3C

Given:

A triple (X, C , C ), where (X, C ) is an instance of X3C, and C = {C 1 , . . . ,C p } and C = {C 1 , . . . ,C q } are such that (i) for all i, C i ⊂ C i , (ii) for all i, C i = 2, and (iii) for all i = j, C i ∩C j = / 0.

Question:

Is (X, C ) a negative instance of X3C?

This problem can be proven to be coNP-complete by using a reduction from X3C. Now suppose, without loss of generality, that X q i=1 C i = {x 1 , . . . , x q }. We adapt the reduction used in the proof of Theorem 4 by constraining the preferences of the first q agents as follows: for each i ∈ {1, . . . , q}, (i) among the three objects from C i , we put those from C i in the first two positions and (ii) among the objects from X C i , we put x i in the first position. Now let π be as follows: each i ∈ {1, . . . , q} gets the two objects from C i and x i , and each agent i ∈ {q + 1, . . . , p} gets f i-q . We claim that (X, C , C ) is a positive instance of R-X3C if and only if π ∈ F s,min (P).

(⇒) For allocation π, agent i, i ∈ {1, . . . , q}, has a utility of 2 3q-1 + 2 3q-2 + 2 3q-4 . The pq remaining agents obtain even more utility. In order to realize more utility than 2 3q-1 + 2 3q-2 + 2 3q-4 agent i has to receive either C i or f j for some j ∈ {1, . . . , p -q} because of lexicographic scoring. Since (X, C ) is a negative instance, it is not possible to give q agents their corresponding C i . Thus, at least one of these agents has to receive f j . However, at least one of the remaining pq agents will then receive neither the corresponding C i nor an f j . Overall, it follows that π ∈ F s,min (P).

(⇐) Suppose (X, C , C ) is negative instance. Then (X, C ) is positive instance of X3C and there is an allocation π that gives more utility to the worst-off agent than π, contradicting the optimality of π. Hence, (X, C , C ) is a positive instance.

To prove the case of s = ε-qi, we also use a reduction from R-X3C as above, but now adapting the reduction used in the proof of Theorem 5. As above, we put into the target instance the objects of C i in the first two positions among the objects of C i , and x i in the first position of the objects of X X i . Here, the allocation π gives the two objects from C i and x i to each agent i ∈ {1, . . . , q} and four arbitrary objects d i to each agent i ∈ {q + 1, . . . , p}.

(⇒) Under π the p agents either obtain a utility of 3 + (3m -7)ε or 4 + 6ε. Every allocation that tries to improve on the utility of the worst-off agent has to give each agent at least 3 goods. Since there are 4pq goods, pq goods are remaining. As every agent can receive at most one additional good, q agents get exactly 3 goods. In order to obtain more utility than 3 + (3m -7)ε, these q agents have to receive their corresponding C i , which is impossible because (X, C ) is a negative instance.

(⇐) This direction is proven analogously to the corresponding case above (for s = lex). K

For a constant number of agents, we provide efficient algorithms for many of our problems by using induction on the number of agents for the lexicographic scoring vector and by using a dynamic programming approach for the other two cases, Borda scoring and quasiindifference.

Theorem 7 For each s ∈ {borda, ε-qi} and for each ∈ {min, leximin}, F s, -OA and F s, -FOA are solvable in polynomial time if the number of agents is constant.