Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods

1 Introduction

Resource allocation deals with the distribution of scarce resources among agents, who may have different preferences over (subsets, also called bundles, of) resources. The goal is to find allocations, assignments of resources to agents, which satisfy certain criteria.

We use the model proposed by Brams and King [2005] (and followed up by Baumeister et al. [2014]) that reconciles the need of collective utility functions for interpersonal comparability with ordinal preferences, using scoring vectors to map ordinal preferences to additive utility functions. This mapping is performed as if there were the same differences in preferential intensity between resources across all agents. We assume that resources are indivisible, nonshareable, and of single-unit type, that is, they can neither be split nor belong to multiple agents simultaneously. This ordinal-preference model is motivated by the issue with cardinal preferences concerning elicitation and (to a certain extent) incomparability between two utility functions. It is far easier to ask for a ranking of (bundles of) resources than for a utility function where every resource/bundle has a numerical value. The tradeoff between ordinal and cardinal preferences has been studied by Caragiannis and Procaccia [2011] in voting, who show that the induced social welfare distortion is low.

Our main contribution is a characterization of strategyproofness of the utilitarian allocation correspondence: No agent can benefit from misreporting her true preferences if and only if the number of different values in the scoring vector is at most two or the number of occurrences of the greatest value in the scoring vector is larger than the sum of the other values' numbers of occurrences (equivalently, the second part can be restated as "the number of occurrences of the greatest value is larger than half the number of goods").

In Section 2, the model for resource allocation with ordinal preferences due to Brams and King [2005] is presented (in the notation of Baumeister et al. [2014]). Then, in Section 3, strategy-proofness under that model is studied and the main result is shown: a characterization of strategy-proofness of the utilitarian allocation correspondence. Related work is described in Section 4. At last, Section 5 gives a summary and concludes with open problems and directions of future research.

2 Scoring Allocation Correspondences

Let A = {1, . . . , n} be a set of agents and let R = {r1, . . . , rm} be a set of indivisible, nonshareable resources (or goods or objects or items) of single-unit type. An allocation of resources to agents is given by a partition p = (p1, . . . ,pn), where pi ⊆ R is the bundle of resources assigned to agent i. Agents are assumed to have (ordinal) preferences over all bundles of resources. However, to ensure feasibility in practice, instead of ranking all subsets of R, we assume agents to rank only single resources. This is a crucial assumption: While it avoids a heavy elicitation burden and allows specifying our problems compactly, agents will not be able to express

J¨org Rothe preferential dependencies between resources. Under this assumption, we consider a preference profile P = (>1, . . . ,>n) as a collection of n linear rankings over R. We now define scoring allocation correspondences, which map any such profile to a nonempty subset of allocations.

Definition 1 A scoring vector s = (s1, . . . , sm) consists of real numbers satisfying s1 ≥ · · · ≥ sm ≥ 0 and s1 > 0. For a preference ranking > over R and a resource r ∈ R, denote the rank of r under > by rank(r,>). For each bundle B ⊆ R, define the utility function over 2 R induced by the ranking > on R and the scoring vector s by u>,s(B) = �r∈B srank(r,>).

Bouveret and Lang [2011] consider the following specific scoring vectors for allocating indivisible goods:

• Borda scoring: borda = (m,m-1, . . . ,1), 1
• lexicographic scoring: lex= (2 m-1 ,2 m-2 , . . . ,1),
• quasi-indifference for some e, 0 < e ≪1: e -qi = (1 + (m - 1)e , 1 + (m - 2)e , . . . , 1).

In addition, we also consider the following scoring vector:

• k-approval: k-app = (1, . . . ,1,0, . . . ,0), where the first k entries are all ones and the remaining entries are zeros.

A monotonic, symmetric aggregation function can then be used to aggregate the individual utilities with the goal of maximizing the overall utility. Typically, one considers utilitarianism (i.e., the sum), and two versions of egalitarianism (namely, min and leximin); see, e.g., [Baumeister et al., 2014]. We restrict ourselves to utilitarian social welfare maximization: Fs(P) = argmaxp �1≤i≤n u>i,s(pi), for preference profile P = (>1, . . . , >n) and allocation p = (p1, . . . , pn). From now on we slightly abuse notation by writing u>i,s(p) instead of u>i,s(pi) to denote the utility for agent i under allocation p = (p1, . . . , pn).

3 Strategy-Proofness

Although the central authority, which collects the rankings and computes the output, knows only the agents' rankings over singletons, the manipulating agent has full knowledge of her own preferences over all sets of objects. We make the crucial assumption that the agents' (unrevealed) strict preference relations are strictly separable, 2 which justifies the fact that they each can "safely" project their preference relation over 2 R onto a preference relation over R. In addition, we assume that the (unrevealed) strict preference relations are strictly monotonic. 3 This is consistent with the common assumption of free disposal and that every good has a positive value which is in line with the fact that scoring vectors are positive.

1 The common definition of Borda scoring in voting is based on the vector (m-1,m-2, . . . ,1,0). However, we follow Brams et al. [2003] by setting the score of the bottom-rank resource to the value 1. Note that scoring vectors in voting can be shifted or scaled without changing the winner set [Hemaspaandra and Hemaspaandra, 2007]; but for scoring allocation correspondences such an operation would have an impact in general [Baumeister et al., 2014].

2≻ is strictly separable if for all X ⊆ R, X1,X2 ⊆ X, Y1,Y2 ⊆ R∖X, we have that X1 ∪Y1 ≻ X2 ∪Y1 if and only if X1 ∪Y2 ≻ X2 ∪Y2.

3≻ is strictly monotonic if for all X,Y ⊆R, if X ⊂Y then Y ≻X.

Turning now to strategy-proofness for scoring allocation correspondences Fs we have to compare sets of winning allocations that can emerge from an original profile P and a modified profile P′ . We assume that the final winning allocation is chosen by an unknown random device which assigns positive probability to each winning allocation. For this we make use of extension principles, which are common in social choice theory. An extension principle lifts a preference relation over single alternatives to a preference relation over sets of alternatives. Here, from the point of view of agent i, alternatives are possible shares, i.e., sets of objects. We consider the two classical extension principles that are due to Kelly [1977] and G¨ardenfors [1976]. 4 Note that the extension principles that we use require that agents are pessimistic: No manipulation may result in a worse outcome. Furthermore, these extension principles assume that alternatives are mutually exclusive: Only one of the alternatives among the winners is ultimately chosen. This choice is performed under complete uncertainty. However, bundles (alternatives) are not mutually exclusive in our model of manipulation. Suppose that we have two bundles A,B with A ⊂ B. Then A and B are not mutually exclusive. Nevertheless, the pessimistic manipulator can pretend that the bundles are mutually exclusive for the following reason: Even if the manipulator knows that a specific subset of a bundle is realized, e.g., in every allocation, a pessimistic manipulator will misreport her preferences only if this does not result in a worse outcome for her. Since the probabilities that govern the random device are not known, two sets of winning bundles, F(P) and F(P′ ), can have completely different probabilities attached to each bundle. For example, if F(P′ ) extends every bundle in F(P) by an additional resource and thus, in addition, may intuitively seem to be more appealing than F(P) because an additional resource is guaranteed, the best bundle (according to the manipulator's preferences) could be assigned a very low probability in F(P′ ), whereas in F(P) it could have a very high probability. This is also an argument against the use of, e.g., an injective mapping that assigns to every alternative a in F(P) an alternative b in F(P′ ) such that b is preferred to a because we assume that manipulators are pessimistic.

To define extensions, it is easier to start with a weak order ≥ associated with a strict linear order >, where x ≥ y if and only if x > y or x = y (here, "=" expresses indifference).

Definition 2 Let ≥ be a weak order over R and A,B ⊆ R. Define the Kelly extension of ≥ by A ⪰K B if and only if for all x ∈ A and y ∈ B we have x ≥ y. Define the G¨ardenfors extension of ≥ by A ⪰G B if and only if one of the following conditions holds: (a) A ⊂ B, and for all x ∈ A and y ∈ B∖A, we have x ≥ y; (b) B ⊂ A, and for all x ∈ A∖B and y ∈ B, we have x ≥ y; (c) neither A ⊂ B nor B ⊂ A, and for all x ∈ A∖B and y ∈ B∖A, we have x ≥ y. Finally, A ≻K B if and only if A ⪰K B and not B ⪰K A, and similarly for ≻G .

4 We don't explicitly consider the extension principle proposed by Fishburn [1972], which is intermediate between Kelly's and G¨ardenfors's; note that our results therefore apply to it as well.

The definitions of ⪰K and ⪰G naturally carry over from sets of resources to sets of allocations of resources.

We now define manipulation of allocation correspondences according to these extension principles as follows.

Definition 3 Let e ∈ {K,G} be an extension principle, F an allocation correspondence, P = (>1, . . . ,>n) a preference profile, P′ = (>′i ,>-i) the profile identical to P except that agent i's preference >i is changed to >′i , and let ≻i be a strictly monotonic and strictly separable preference relation over 2 R extending >i. Define F(P)i = {pi | p ∈ F(P)}.

We say that >′i is an e-manipulation for P, F, and ≻i if F(P′ )i ≻e i F(P)i. A scoring allocation correspondence F is e-manipulable by an agent i if there exist P = (>1, . . . ,>n), ≻i extending >i, and >′i such that >′i is an e-manipulation for profile P, F, and ≻i. F is e-strategy-proof if it is not emanipulable by any agent.

Clearly, for each agent i, F(P′ )i ≻K i F(P)i implies F(P′ )i ≻G i F(P)i. Therefore, Kelly-manipulability implies G¨ardenfors-manipulability; equivalently, G¨ardenfors-strategy-proofness implies Kelly-strategy-proofness. These notions have been investigated so far only for irresolute social choice functions in the context of voting (see, e.g., the papers by Brandt [2015] and Brandt and Brill [2011]). We will apply them to scoring allocation correspondences.

Note that one cannot define manipulation in terms of the agents' scores because their scores do not necessarily reflect the agents' preferences. Recall that scoring allocation correspondences merely use scores as proxies.

To summarize our model, agents have preferences over the power set of objects. However, they only submit a linear order over the objects to the scoring allocation procedure. The scoring allocation procedure uses a scoring vector to cardinalize the ordinal preferences and then optimizes social welfare with respect to the proxy utility functions. Since optimal allocations are not necessarily unique, agents lift their preferences over bundles of objects to preferences over sets of bundles of objects. These lifted preferences are used to determine whether a manipulation is successful.

The following notation will be used heavily in the proofs of this paper.

Definition 4 Ri(P) = {r ∈ R| (∃pi ∈ Fs(P)i) [r ∈ pi]} is the set of all resources that agent i gets in some allocation of Fs(P).

A resource r ∈ Ri(P) is sure in profile P for agent i if r ∈ pi for all pi ∈Fs(P)i; r is contested in P for i if it is not sure in P for i. Let Si(P) denote the set of all sure resources in P for i.

Let s = (s1, . . . , sm) be a scoring vector with k different values v1, . . . , vk with v1 > v2 > · · · > vk. Denote by ai the number of occurrences of the i-th value among v1, . . . , vk in s, that is, ai = ‖{ j | vi = s j,1 ≤ j ≤ m}‖. The set of resources that are in the i-th bin for agent j with linear order >j is defined by Ai(>j) = {r ∈ R| 1+� i-1 k=1 ak ≤ rank(r,>j) ≤ � i k=1 ak}. We omit the scoring vector in all definitions when it is clear from context.

Remark 5 Let > be a linear order on the set of resources R = {r1, . . . ,rm}, say r1 > r2 > · · · > rm. Let s be a scoring vector with k different values. We sometimes write > as

Now we show G¨ardenfors-strategy-proofness for the case of at most two different values in the scoring vector. The intuition of the proof is that swapping the positions of a highranked and a low-ranked resource always leads to a situation where the high-ranked resource is replaced by the low-ranked resource in a bundle of an optimal allocation.

Proposition 6 For at least two agents and each scoring vector s having at most two different values, Fs is G¨ardenforsstrategy-proof (and thus also Kelly-strategy-proof).

Proof. Let R be the set of resources with a,b ∈ R, and let P = (>1, . . . ,>n), n ≥ 2, be the profile where in the ranking of the last agent (the manipulator) a gets a higher score than b, that is, a >n b and we have two distinct score values, a = srank(a,>n) and b = srank(b,>n) with a > b . We distinguish the following four cases regarding the positions of resources a and b in the preferences of the remaining agents:

Case 1(a): There is some i < n with srank(a,>i) = a and there is some j < n with srank(b,>j) =a. Then a is contested for n, but agent n never receives b.

Case 1(b): There is some i < n with srank(a,>i) = a and for all j, 1 ≤ j < n, srank(b,>j) = b. Then a and b are contested for n.

Case 2(a): For all i, 1 ≤ i < n, we have srank(a,>i) = b and there is some j < n with srank(b,>j) =a. Then a is sure for n, but agent n never receives b.

Case 2(b): For all i, 1 ≤ i < n, we have srank(a,>i) = b and for all j, 1 ≤ j < n, srank(b,>j) = b. Then a is sure and b is contested for n.

Now, let P′n = (>1, . . . ,>n-1,>′n) be the modified profile where the only change is that in the ranking of the last agent the positions of resources a and b are swapped. Going through the cases with the modified profile, we see that either (1) a /∈ pn for all p ∈ Fs(P′ ) or (2) a /∈ pn for some p ∈ Fs(P′ ) and either (a) b is contested for n in P′ or (b) b is sure for n in P′ . Hence we have the above four cases 1(a), 1(b), 2(a), and 2(b). In all of them it holds that for each p ∈ Fs(P) with a ∈ pn and b /∈ pn (which exists in all cases), there is some p ′ ∈ Fs(P′ ) with p ′n = (pn ∖{a})∪{b}. By strict separability of ≻n and since a >n b, pn ≻n p ′n follows. Now we show that we can use the sets pn and p ′n in all cases of the G¨ardenfors extension:

Case I: Fs(P′ )n ⊂Fs(P)n. This is Case 1(b). It holds that p ′n is in Fs(P′ )n and pn is in Fs(P)n ∖Fs(P′ )n because of b /∈ pn but b ∈ p ′′ n is true for all p ′′ n ∈Fs(P′ )n.

Case II: Fs(P)n ⊂Fs(P′ )n. This is Case 2(a). It holds that pn is in Fs(P)n and p ′n is in Fs(P′ )n ∖Fs(P)n because of b ∈ p ′n but b /∈ p ′′ n is true for all p ′′ n ∈Fs(P)n.

Case III: Neither Fs(P′ )n ⊂ Fs(P)n nor Fs(P)n ⊂ Fs(P′ )n. These are Cases 1(a) and 2(b). For both of them, pn is in Fs(P)n∖Fs(P′ )n and p ′n is in Fs(P′ )n∖Fs(P)n with the same arguments as above.

Thus it is not true that Fs(P′n)n ≻G n Fs(P)n. Since this argument analogously works for all agents, Fs is not Gmanipulable by any agent, which means it is G¨ardenforsstrategy-proof. q The idea of the next result is that if there are at least three different values and the first bin is not large enough, then all resources in the first bin of some agent fit into lower ranked bins of some other agent. This can be used to "shift" resources into the right bins.

Proposition 7 Let s be a scoring vector with k ≥ 3 different values satisfying a1 ≤ � k i=2 ai. Then Fs is K-manipulable.

Proof. The goal is to construct profiles showing that Fs is K-manipulable by some agent. Let R = {r1, . . . , rm} be the set of resources. We distinguish the following two cases.

Case 1: a1 = � k i=2 ai. Let profile P consist of two linear orders, where agent 2 is the manipulator:

We have S2(P) = {ra1+1, ra1+2, . . . , rm}. Because none of the resources in A1(>1) are assigned to agent 2, S2(P) is the only bundle that agent 2 receives in an allocation. The manipulator's goal is to receive an additional resource without losing one of her sure resources. This can be achieved by swapping resource ra1+a2+1 with resource r1 in >2. Resource r1 becomes contested because r1 is in the first bin for both agents. But resource ra1+a2+1 is still sure for agent 2 in profile P′ because there are at least three different values (that is, bins), and resource ra1+a2+1 is in the third bin of agent 1 but it is in the second bin of agent 2's manipulation. Hence, agent 2 receives either S2(P) or S2(P)∪{r1} in an allocation. We thus have a K-manipulation by agent 2 as required.

Case 2: a1 < � k i=2 ai. We construct a profile in a series of steps. The number of agents depends on the scoring vector. The linear order >1 of agent 1 is r1 >1 r2 > · · · >1 rm. First we give the manipulative linear order of agent 2. Then we show how to swap two resources in the manipulative linear order such that a sure resource for agent 2 becomes contested in the original linear order. Agent 2's manipulative preference is constructed as follows: We transform the linear order >1 by a series of swaps. The goal is to maximize the number of sure resources that agent 2 receives. Therefore, all resources in the first bin of agent 1 are swapped with resources in the second bin, the third bin, and so on until all resources of the first bin are in a worse bin. Because of a1 <� k i=2 ai that is possible. Now we consider the second bin of the transformed linear order. Again, we improve the positions of resources in worse bins by swapping them with resources in the second bin. This time, however, we have to pay attention to the fact that we do not improve the position of resources that were sent to worse bins in previous iterations. We continue this procedure until we reach the last bin or no resources are left that can be made sure for agent 2.

More formally, set >(1) =>1. Starting with j = 1, swap the resources of Aj(>( j) ) in decreasing order according to >(1) with those of Aj+1(>( j) )∖ ⋃l<j Al(>(1) ), Aj+2(>( j) )∖ ⋃l<j Al(>(1) ), and so on, until no longer possible. Call the transformed linear order >( j+1) . Continue until the transformed linear order >(k) =>′2 is obtained.

In order to transform the manipulative linear order >′2 to the original linear order >2, we look at the rightmost bin Aw(>′2 ) which contains a resource of A1(>1). We call Aw(>′2 ) the worst bin. Because a1 <� k i=2 ai holds, every resource of A1(>1) is swapped. Hence, the worst bin is at least the second bin. However, it cannot be the second bin. If it were, then a1 ≤ a2 would hold because otherwise a resource from the first bin would be swapped to at least the third bin. But if all resources of A1(>1) are swapped with resources of A2(>2), then the next iteration will swap resources that are originally from the first bin with resources of the third bin. This is true because there are at least three different values and swapping is performed in decreasing order according to >(1) . Therefore, the worst bin of agent 2 with the manipulative linear order is at least the third bin.

Looking at the resources that agent 1 has in the bin that has the same index as agent 2's worst bin, that is, in Aw(>1), there is always a resource that is sure for agent 2 but not in the first bin of agent 2 in the manipulation. Note that here we use the fact that the worst bin has to be at least the third bin; otherwise, every resource that is sure for agent 2 would have to be in the first bin. Now we show that such a resource always exists.

Pick an a ∈ Aw(>′2 )∩A1(>1). There are two possibilities how resource a came into Aw(>′2 ):

1. Series of swaps: Resource a was swapped with b which is now sure for agent 2. Because there was at least one preceding swap involving resource a, resource b cannot be in A1(>′2 ).
2. Direct swap: After the first iteration all resources from the bins that are to the left of the worst bin (except for the first bin) were swapped with the resources in the first bin of agent 1. The worst bin has not been completely filled by new resources in the first iteration: If all resources in Aw(>′2 ) are there due to a direct swap (that is, in the first iteration), then there is a bin to the right of the worst bin (otherwise, we would have a1 = � k i=2 ai, contradicting the case assumption). Then the second iteration swaps a resource from the bin that is to the right of the worst bin with a resource in the second bin. The second bin just contains resources fromA1(>1). Thus Aw(>′2 ) is not the worst bin.

If there is a resource in Aw(>′2 ) that was not swapped in the first iteration, the second iteration picks such a resource in order to swap it with a resource in the second bin, which just contains resources from A1(>1).

Thus there is a resource r ∈ S2(P′ ) with r /∈ A1(>′2 ) and r ∈ Aw(>1). Now swap r and a in >′2 . Resource a remains unavailable to agent 2 because resource r was not in the first bin of agent 2 in the manipulation. However, r becomes contested for agent 2, the first agent having r in the same bin. Call this linear order >2.

Agent 2 may still receive contested resources. By adding additional agents, we prevent that from happening. For each contested resource rc that agent 2 receives in P′ , add to profiles P and P′ a linear order >rc which results from swapping resource rc with resource r1 in >1. This is always possible because a1 < � k i=2 ai implies that agent 2's contested resources in P′ are not in A1(>1). Hence, we have a manipulation with Fs(P′ )2 = {S2(P′ )} and Fs(P)2 = {S2(P′ )∖{r}, S2(P′ )}. This completes Case 2.

Example 8 Let s = (7,7,7,5,5,5,5,5,3) be a given scoring vector (which corresponds to the second case of the proof of Proposition 7). Then the linear order >1 =>(1) of agent 1 is r1 r2 r3 | r4 r5 r6 r7 r8 | r9.

The manipulative linear order >′2 is constructed first:

Set profile I ′ = (>1,>′2 ). Then the set of sure resources for agent 2 in I ′ is S2(I ′ ) ={r4,r5,r6,r9}, the set of contested resources for agent 2 is C2(I ′ ) = {r7, r8}. Now we construct the original linear order >2 of agent 2. The worst bin is A3(>′2 ). A resource in the intersection A3(>′2 ) ∩A1(>1) is r1. The swap that brought r1 to the third bin was with r9. Swapping r1 with r9 gives >2. Set profile I = (>1,>2). Then the set of sure resources for agent 2 in the profile I is S2(I) = {r4, r5, r6}. For each contested resource in C2(I ′ ), an agent is added with the linear order >1 except for a swap of this contested resource with r1. The complete profile P′ is:

>1 : r1 r2 r3 |r4 r5 r6 r7 r8 |r9

>′2 : r4 r5 r6 |r9 r2 r3 r7 r8 |r1

>r7 : r7 r2 r3 |r4 r5 r6 r1 r8 |r9

>r8 : r8 r2 r3 |r4 r5 r6 r7 r1 |r9

and the winning set for agent 2 in profile P′ is Fs(P′ )2 = {S2(I ′ )}. The profile P is the same as P′ except for exchanging >′2 with >2. This gives the winning set Fs(P)2 = {S2(I),S2(I)∪{r9}}. Overall, the manipulation follows via Fs(P′ )2 ≻K 2 Fs(P)2.

Finally, we consider the case of scoring vectors with at least three different values and a1 >� k i=2 ai .

Due to space constraints we omit the proofs of the following lemmas.

Lemma 9 Let s be a scoring vector with k different values. For each profile P with at least two agents and for each agent j, ‖Rj(P)‖≥a1 and ‖Sj(P)‖≤� k i=2 ai .

Lemma 10 Let s be a scoring vector with k different values and R be a set of resources. For each agent j, for each strictly monotonic and strictly separable linear order ≻j on 2 R extending >j, and for each set X with ‖X‖ ≤ a1 and X ̸= A1(>j), we have A1(>j) ≻j X.

If the first bin is large, the intuition of the following result on G¨ardenfors-strategy-proofness is that the set of sure resources is small (Lemma 9), whereas the (large) first bin is preferred to every small bundle (Lemma 10).

Proposition 11 For at least two agents and each scoring vector s with k ≥ 3 different values satisfying a1 > � k i=2 ai, Fs is G¨ardenfors-strategy-proof.

Proof. Let R be the set of resources, P be a profile, P′ be the same profile as P except for a change of the manipulator's preference, let >n be the manipulator's true linear order on R, and ≻n be the manipulator's strictly monotonic and strictly separable linear order on 2 R extending >n. Consider the three relations of Fs(P)n and Fs(P′ )n according to G¨ardenfors. For each case we exhibit two sets that satisfy the membership criteria in the definition of a G¨ardenfors extension and that have the desired relation between them.

Case 1: Fs(P)n ⊂ Fs(P′ )n. In this case we find sets p ∈ Fs(P)n and p ′ ∈ Fs(P′ )n∖Fs(P)n such that p ≻n p ′ holds. Consider the following subcases with respect to the relationship between Rn(P) and Rn(P′ ):

Case 1(a): Rn(P′ ) ⊂ Rn(P). Since Fs(P)n ⊂ Fs(P′ )n implies Rn(P) ⊆Rn(P′ ), this case never occurs.

Case 1(b): Rn(P) ⊂ Rn(P′ ). The idea is that adding a resource which is in Rn(P′ ) but not in Rn(P) to the set of sure resources in P′ is sufficient for the set not to be in Fs(P)n.

Suppose that r ∈ Sn(P′ ) for all r ∈ Rn(P′ )∖Rn(P). Then Sn(P′ ) /∈ Fs(P)n is true and, by bounding the size of Sn(P′ ) with Lemma 9 and then applying Lemma 10, we have A1(>n ) ∪ Sn(P) ≻n Sn(P′ ). Now suppose that there exists r′ ∈ Rn(P′ ) ∖Rn(P) with r′ /∈ Sn(P′ ). Then we have Sn(P′ ) ∪ {r′} /∈ Fs(P)n and, by Lemmas 9 and 10 and the fact that r′ /∈ A1(>n), we have A1(>n)∪Sn(P) ≻n Sn(P′ )∪{r′ }.

Case 1(c): Rn(P) = Rn(P′ ). Let p ′ ∈ Fs(P′ )n ∖Fs(P)n. Then we have p ′ ̸= Rn(P′ ) because Rn(P) ∈ Fs(P)n. Hence, p ′ ⊂ Rn(P′ ) is true, which implies Rn(P) ≻n p ′ .

Case 1(d): Rn(P) ̸⊂ Rn(P′ ) and Rn(P′ ) ̸⊂ Rn(P). This case never occurs, as Fs(P)n ⊂ Fs(P′ )n implies Rn(P) ⊆ Rn(P′ ).

Case 2: Fs(P′ )n ⊂ Fs(P)n. Then we find sets p ∈ Fs(P)n ∖ Fs(P′ )n and p ′ ∈ Fs(P′ )n such that p ≻n p ′ .

Case 2(a): Rn(P′ ) ⊂ Rn(P). We have Rn(P) /∈ Fs(P′ )n (otherwise, Rn(P) ⊆ Rn(P′ )). Hence, Rn(P) ≻n Rn(P′ ) is enough in this case.

Case 2(b): Rn(P) ⊂ Rn(P′ ). Analogously to Case 1(a).

Case 2(c): Rn(P) = Rn(P′ ). The premises Rn(P) = Rn(P′ ) and Fs(P′ )n ⊂ Fs(P)n imply that there exists a resource r ∈ Rn(P) that is contested in P but sure in P′ . It follows that r /∈ A1(>n) is true (otherwise, r would not be sure in P′ and contested in P). Thus we have r /∈ A1(>n)∪Sn(P), and A1(>n)∪Sn(P) /∈ Fs(P′ )n holds because r is sure in P′ . By Lemmas 9 and 10, A1(>n)∪Sn(P) ≻n Sn(P′ ).

Case 2(d): Rn(P) ̸⊂ Rn(P′ ) and Rn(P′ ) ̸⊂ Rn(P). Analogously to Case 1(d).

Case 3: Fs(P)n ̸⊂Fs(P′ )n and Fs(P′ )n ̸⊂Fs(P)n. In this case we find sets p ∈ Fs(P)n ∖Fs(P′ )n and p ′ ∈ Fs(P′ )n ∖Fs(P)n such that p ≻n p ′ holds.

Case 3(a): Rn(P′ ) ⊂ Rn(P). We have Rn(P) /∈ Fs(P′ )n (otherwise, Rn(P) ⊆ Rn(P′ )). Pick a set p ′ ∈ Fs(P′ )n ∖Fs(P)n. Then p ′ ⊆Rn(P′ ) is true. This implies that Rn(P) ≻n p ′ . Case 3(b): Rn(P) ⊂Rn(P′ ). Suppose that A1(>n)∪Sn(P) /∈

Fs(P′ )n holds. Then we can argue similarly to Case 1(b).

Now we show that A1(>n)∪Sn(P) ∈ Fs(P′ )n never holds: We have Sn(P′ ) ⊂A1(>n)∪Sn(P). However, if r ∈ Sn(P′ ) is in A1(>n), then r ∈ Sn(P) holds as well. Hence Sn(P′ ) ⊆ Sn(P) is true. Together with Rn(P) ⊂ Rn(P′ ) this implies that Fs(P)n ⊂ Fs(P′ )n because each resource c ∈ (Sn(P)∖ Sn(P′ ))∪(Rn(P′ )∖Rn(P)) is contested in P′ (contradiction).

Case 3(c): Rn(P) = Rn(P′ ). Rn(P) = Rn(P′ ) together with Fs(P)n ̸⊂ Fs(P′ )n implies that there is a resource that is contested in P but sure in P′ . Similarly, there is a resource that is contested in P′ but sure in P. Overall, we have Sn(P′ ) ̸⊂ Sn(P) and Sn(P) ̸⊂ Sn(P′ ). Pick a resource r ∈ Sn(P′ )∖Sn(P). The remaining argument is analogous to Case 2(c).

Case 3(d): Rn(P) ̸⊂ Rn(P′ ) and Rn(P′ ) ̸⊂ Rn(P). We have Rn(P) /∈ Fs(P′ )n (otherwise, Rn(P) ⊆ Rn(P′ )) and argue similarly to Case 1(b). This completes the proof. q

Example 12 Let s = (8,8,8,8,8,5,5,4,2) be a scoring vector and R = {r1, . . . , r9} be the set of resources. Let P be the following profile of three agents:

>1 : r1 r2 r3 r4 r5 |r6 r7 |r8 |r9

>2 : r1 r3 r4 r5 r7 |r2 r6 |r8 |r9

>3 : r1 r2 r3 r4 r6 |r7 r9 |r8 |r5

The winning set for agent 3 consists of S3(P) = {r6r9} and C3(P) = {r1r2r3r4r8}. Now consider the following misreported linear order of agent 3:

If P′ is profile P with linear order >3 replaced by >′3 , the new winning set of agent 3 consists of S3(P′ ) = {r9} and C3(P′ ) = {r1r2r3r4r6r7r8}. Then we have Fs(P)3 ⊂ Fs(P′ )3 and R3(P) ⊂ R3(P′ ) (Case 1(b) of the proof of Proposition 11). We have R3(P′ ) \R3(P) = {r7}. Hence, S3(P′ )∪ {r7} = {r7,r9} ∈ Fs(P′ )3 and {r7,r9} /∈ Fs(P)3. It follows that A1(>3) ∪ S3(P) = {r1, r2, r3, r4, r6, r9} ≻3 {r7, r9} holds because of, e.g., r1 >3 r7.

From Propositions 6, 7, and 11, we have the main result:

Theorem 13 Let s be a scoring vector with k different values. The following three statements are equivalent: (1) Fs is Kellystrategy-proof; (2) Fs is G¨ardenfors-strategy-proof; (3) k ≤ 2 or a1 > � k i=2 ai .

Corollary 14 For s ∈ {borda, lex, e-qi}, the following three statements are equivalent: (1) Fs is Kelly-strategy-proof; (2) Fs is G¨ardenfors-strategy-proof; (3) there are no more than two resources.

Corollary 15 Fk-app is Kelly- and G¨ardenfors-strategy-proof.

4 RelatedWork

Chevaleyre et al. [2006] survey the work on multiagent resource allocation, and Nguyen et al. [2013] that on approximability of social welfare optimization (see also the work of Nguyen et al. [2014]) for cardinal preferences. Since the model that we study is inspired by scoring rules from voting, the chapter by Brams and Fishburn [2002] might serve as an introduction. A comparison of multiagent research in combinatorial auctions (which is somewhat related to fair division) and voting by Conitzer [2010] highlights the similarities between these two fields.

Brams and King [2005] assume ordinal preferences over single resources. They look at properties such as maximin, Borda maximin, and envy. Similarly, Brams et al. [2003] assume that each agent has an additively separable preference over the resources, with no side payments allowed. Optimal allocations maximize utilitarian or egalitarian social welfare, where the utility of an agent is the Borda score of the received bundle. Baumeister et al. [2014] extend this model by considering arbitrary scoring vectors and collective utility functions and study scoring allocation rules with respect to axiomatic properties. Strategy-proofness for allocation rules has been studied by, e.g., P´apai [2001], Ehlers and Klaus [2003], and Hatfield [2009].

A different model of resource allocation where agents have ordinal preferences but do not submit them to a central authority has been studied by Bouveret and Lang [2011], who have also studied the manipulation problem in this model [Bouveret and Lang, 2014].

In the context of social choice, the standard approaches for lifting preferences are due to Kelly [1977], Fishburn [1972], and G¨ardenfors [1976]. The axiomatic study of extensions was started by Kannai and Peleg [1984]. A survey is given by Barber`a et al. [2004]. The motivation of Kelly [1977] was to abandon the single-valuedness requirement in the GibbardSatterthwaite theorem [Gibbard, 1973; Satterthwaite, 1975]. A generalization of strategy-proofness is given, where the focus is on "clear-cut cases" when there is no knowledge of the final selection process. More recently, Brandt [2015] and Brandt and Brill [2011] establish necessary and sufficient conditions for strategy-proofness of irresolute social choice functions using the preference extensions due to Kelly, Fishburn, and G¨ardenfors.

5 Conclusions

We have studied resource allocation in a model where resources are indivisible, nonshareable, and of single-unit type. Agents reveal ordinal preferences over single resources only, thus crucially alleviating the elicitation burden. Allocations are complete assignments of all resources to the agents. Winner determination is facilitated through scoring vectors: The ordinal preferences are transformed into utility functions as if the agents' preferences were additively separable. Using these surrogate utility functions, allocations can be assessed with tools of resource allocation with cardinal preferences such as utilitarian social welfare.

We have studied the manipulation problem in this model. This is the question of whether agents can benefit from misreporting their preferences. Specifically, we have taken the point of view of a manipulator where we know the manipulator's strictly monotonic and strictly separable preferences over bundles of resources instead of single resources. As multiple allocations can maximize utilitarian social welfare, the manipulator's preferences are lifted to sets of bundles of resources through Kelly and G¨ardenfors extensions. We have shown that the structure of the chosen scoring vector characterizes whether the utilitarian allocation correspondence is manipulable or strategy-proof: If there are at most two different values in the scoring vector, then the utilitarian allocation correspondence is G¨ardenfors/Kelly-strategy-proof; if there are at least three different values in the scoring vector, then it is G¨ardenfors/Kelly-strategy-proof if and only if the number of occurrences of the greatest value in the scoring vector is larger than half the number of goods.

Intuitively speaking, the bottom line is that a utilitarian allocation correspondence becomes strategy-proof when there is high discrepancy between the choice of the scoring vector and strict preferences. This is consistent with the intuition that an allocation correspondence that is more oblivious to the agents' preferences should be strategy-proof.

As directions of future research we propose to investigate the complexity of winner determination in this model. Furthermore, a characterization of strategy-proofness for other social welfare measures (e.g., egalitarian social welfare) is still open. Manipulability of allocation rules as compositions of allocation correspondences with tie-breaking mechanisms would constitute an interesting research direction as well.

Acknowledgments

We thank the anonymous reviewers for helpful comments and J´erˆome Lang for interesting discussions and feedback on an earlier draft of this paper. This work was supported in part by the NRWMinistry for Innovation, Science, and Research and DFG grants RO 1202/14-1 and RO 1202/15-1.