A Social Welfare Optimal Sequential Allocation Procedure

1 Introduction

There exist a variety of mechanisms to share indivisible goods between agents without side payments [Brams and Fishburn, 2000; Herreiner and Puppe, 2002; Brams et al., 2003; Brams and Kaplan, 2004; Brams et al., 2012]. One of the simplest is simply to let the agents take turns to pick an item. This mechanism is parameterized by a policy, the order in which agents take turns. In the alternating policy, agents take turns in a fixed order, whilst in the balanced alternating policy, the order of agents reverses each round. Bouveret and Lang (2011) study a simple model of this mechanism in which agents have strict preferences over items, and utilities are additive. They conjecture that computing the expected social welfare for a given policy is NP-hard supposing all preference orderings are equally likely. Based on simulation for up to 12 items, they conjecture that the alternating policy maximizes the expected utilitarian social welfare for Borda utilities, and prove it does so asymptotically. We close both conjectures. Surprisingly, we prove that the expected utility of each agent can be computed in polynomial time for any policy and utility function. Using this result, we prove that the alternating policy maximizes the expected utilitarian social welfare for any number of items and any linear utility function including Borda. Our results provides some justification for a mechanism in use in school playgrounds around the world.

∗ Supported by the Department of Broadband, Communications and the Digital Economy, the ARC and the Asian Office of Aerospace Research and Development (AOARD-124056).

Nina Narodytska and TobyWalsh NICTA and UNSW Sydney, Australia {nina.narodytska,toby.walsh}@nicta.com.au

2 Notation

Each of the n agents has a total preference order over the p items. A profile is an n-tuple of such orders. Agents have the same utility function. An item ranked in kth position has a utility g(k). For Borda utilities, g(k) = p - k + 1. The utility of a set of items is the sum of their individual utilities. Preference orders are independent and drawn uniformly at random from all p! possibilities (full independence). Agents take turns to pick items according to a policy, a sequence π = π1 . . . πp ∈ {1, 2, . . . , n}p . At the k-th step, agent πk chooses one item from the remaining set. Without loss of generality, we suppose π1 = 1. For profile R, uR(i, π) denotes the utility gained by agent i supposing every agent always chooses the item remaining that they rank highest. We write ui(π) for the expectation of uR(i, π) over all possible profiles. We take an utilitarian standpoint, measuring social welfare by the sum of the utilities: swR(π) = ∑ni=1 uR(i, π). By linearity of expectation, sw(π) = ∑ni=1 ui(π). To help compute expectations, we need a sequence γk given by γ1 = γ2 = 1,

Asymptotically γk = √ 2k π + O ( 1 √k ) . To simplify notation, we suppose empty sums are zero and empty products are one.

3 Computing the Expected Social Welfare

Bouveret and Lang 2011 conjectured that it is NP-hard to compute the expected social welfare of a given policy as such a calculation depends on the super-exponential number of possible profiles. However, as we show now, the expected utility of each agent can be computed in just O(np2 ) time for an arbitrary utility function, and O(np) time for Borda utilities. We begin with this last case, and then extend the results to the general case. Let P n p denote the set of all policies of length p for n agents. For p ⩾ 2, we define an operator P n p → P n p-1 mapping π ↦→ ˜π, by deleting the the first entry. More precisely, ˜πi = πi+1 for i ∈ {1, . . . , p - 1}. For example, π = 1211 and ˜π = 211.

Lemma 1. For Borda scoring, n ⩾ 2 agents, p ⩾ 2 items and π ∈ P n p with π1 = 1, we have:

and these values can be computed in O(np) time.

Proof. Agent 1 picks her first item, giving her a utility of p. After that, from her perspective, it's the standard game on p - 1 items with policy ˜π, so she expects to get an utility of u1(˜π). This proves the first equation. For the other agents, it is more involved. Let i ∈ {2, . . . , n} be a fixed agent. For q ∈ {1, . . . , p}, let ai(q, π) denote the probability that under policy π agent i gets the item with utility q. Note that this probability does not depend on the utility function but only on the ranking: it is the probability that agent i gets the item of rank p - q + 1 in her preference order. By the definition of expectation,

There are three possible outcomes of the first move of agent 1 with respect to the item that has utility q for agent i. With probability (q - 1)/p, agent 1 has picked an item with utility less than q (for agent i), with probability (p-q)/p, agent 1 has picked an item with utility more than q, and with probability 1/p it was the item of utility equal to q. In the first case there are only q -2 items of utility less than q left, hence the probability for agent i to get the item of utility q is ai(q - 1, ˜π). In the second case there are still q -1 items of value less than q, hence the probability to get the item of utility q is a(q, ˜π). In the third case, the probability to get the item of utility is zero, and together we obtain

Substituting this into (1) yields

In the first sum we substitute q′ = q - 1 and this yields

The first term in the first sum and the last term in the second sum are equal to zero, so they can be omitted and we obtain

The time complexity follows immediately from the recursions.

q

Example 1. Consider two agents with Borda utilities and the policies π1 = 121212 and π2 = 111222. We compute expected utilities and expected social welfare for each of them using Lemma 1. Table 1 shows results up to two decimal places. Note that expected values computed in all examples in the paper coincide with the results obtained by the bruteforce search algorithm from [Bouveret and Lang, 2011].

Due to the linearity of Borda scoring the probabilities ai(q, π) in the proof of Lemma 1 cancel, and this will allow us to solve recursions explicitly and to prove our main result about the optimal policy for Borda scoring in Section 5.

In the general case, we can still compute the expected utilities u(i, π), and thus sw(π), but we need the probabilities ai(q, π) from the proof of Lemma 1: ai(q, π) is the probability that under policy π, agent i gets the item ranked at position p - q + 1 in her preference order. Computing these probabilities using (2) adds a factor of p to the runtime.

Lemma 2. For n ⩾ 2 agents, p ⩾ 2 items, a policy π ∈ P n p and an arbitrary scoring function g, the expected utility for agent i is

and can be computed in O(np2 ) time.

Lemma 2 allows us to resolve an open question from [Bouveret and Lang, 2011].

Corollary 1. For n agents and an arbitrary scoring utility function g, the expected utility of each agent, as well as the expected utilitarian social welfare can be computed in polynomial time.

For some special policies, the recursions in Lemma 1 can be solved explicitly. A particularly interesting policy is the strictly alternating one (denoted ALTPOLICY) π = 123 . . . n123 . . . n123 . . . n . . . .

Proposition 1. Let π be the strictly alternating policy of length p starting with 1. The expected utilities and utilitarian social welfare for two agents and Borda scoring are

Proof. A proof for the two agents case can be done by straightforward induction using the recursions from Lemma 1. For n agents we outline the proof. The full proof is given in Appendix A in the online version [Kalinowski et al., 2013a]. First, we solve the recursions for the expected utility of agent i when the number of items is p ≡ i - 1 (mod n). Using these values, we approximate the expected utility for the remaining combinations of p and i.

Example 2. Consider the policy π1 from Example 1. Using Proposition 1, we get: u1(π) = 6(6+1) 3 = 14, u2(π) = 62-1 3 + 13 γ6+1 = 11.67+2.19/3 = 12.4 and sw(π) = 26.4. These values coincide with results in Table 1.

For a fixed number n of agents, we write the number of items as p = kn + r with 0 ⩽ r < n. We call a policy π = π1 . . . πp balanced if {πin+1, . . . , πin+n} = {1, 2, . . . , n} for all i ∈ {0, . . . , k - 1} and |{πkn+1, . . . , πkn+r}| = r. For any balanced policy, the expected utility of any agent lies between that of agents 1 and n in the alternating policy. Thus every agent has expected utility p2 /(n + 1) + O(p).

4 Comparison with Other Mechanisms

We compare with two other allocation mechanisms that provide insight into the efficiency of the alternating policy. The best preference mechanism (BESTPREF) allocates each item to the agent who prefers it most breaking ties at random. The random mechanism (RANDOM) allocates items by flipping a coin for each individual item.

Proposition 2. For two agents, and Borda utilities, the expected utilitarian social welfare of BESTPREF is (p+1)(4p-1) 6 . For n agents, it is np2 n+1 + p2 + O(1).

Proof. Due to space limitations we only present a proof for two agents. The proof for n agents is again given in the online Appendix B. Let Sp be the set of all permutations of {1, 2, . . . , p}. Then the expected utilitarian social welfare is

We split the inner sum into two sums: one for all permutations a = (a1, . . . , ap) with ai ⩽ i, and one for the remaining permutations. Hence, we get

We compute the value of each inner sum separately. In the first sum each term equals i, so we have to determine the number of terms. For ai there are i possible values 1, 2, . . . , i, and for a fixed value of ai there are (p - 1)! permutations of the remaining values. So the first sum has (p - 1)!i terms of value i, hence it equals (p - 1)!i2 . The second sum contains for each j ∈ {i + 1, . . . , p} exactly (p - 1)! terms of value ai = j, hence it equals (p - 1)! ∑pj=i+1 j =

(p - 1)!(p(p + 1)/2 - i(i +1)/2). So the expected utilitarian social welfare is

Proposition 3. For n agents, and Borda utilities, the expected utilitarian social welfare of RANDOM is p(p+1) 2 .

Proof. As the probability of each agent obtaining the ith item is 1/n, the expected utilitarian social welfare is n ∑pi=1 in = p(p+1) 2 .

Table 2 summarizes the expected utilitarian social welfares for these mechanisms. Clearly, BESTPREF is an upper bound on the expected utilitarian social welfare for any allocation mechanism. As in [Bouveret and Lang, 2011], we define asymptotic optimality of a sequence of policies (π(p) )p=1,2,... where π(p) is a policy for p items by

As can be seen from the table, ALTPOLICY is an asymptotically optimal policy. By the observation in the end of the previous section the same is true for any balanced policy, and this implies Proposition 5 in [Bouveret and Lang, 2011]. However, the proof in [Bouveret and Lang, 2011] is incorrect as it implies that the expected utility is p2 /n + O(1) for every agent which contradicts our upper bound for BESTPREF. See Appendix C for a detailed discussion of the gaps in the proof. Of course, for any given p and preference orderings, ALTPOLICY may not give the maximal utilitarian social welfare possible.

Example 3. Consider two agents and six items with the following preferences: 1 > 2 > 3 > 4 > 5 > 6 and 1 > 6 > 2 > 3 > 4 > 5. The ALTPOLICY policy gives items {1, 2, 4} and {6, 3, 5} to agents 1 and 2 respectively. Hence, the total welfare is (6 + 5 + 3) + (5 + 3 + 1) = 23. Consider a policy π = 121111 which gives the following items to agents: {1, 2, 3, 4, 5} and {6}. The total welfare is now (6 + 5 + 4 + 3 + 2) + (6) = 25.

The RANDOM mechanism gives the worst expected utilitarian social welfare among the three mechanisms. Moreover, as n increases the expected utilitarian social welfare produced by RANDOM declines compared with the other two mecha-

With two agents, the expected loss using ALTPOLICY compared to BESTPREF (which requires full revelation of the preference orders) is less than p/6. In particular, with high probability ALTPOLICY yields an utilitarian social welfare very close to the upper bound.

Proposition 4. For two agents and any ε > 0, with probability at least 1 - ε, ALTPOLICY is a (1 - 1 3pε )-approximation of the optimal expected utilitarian social welfare.

Proof. Let the random variables z1 and z2 denote the utilitarian social welfare for ALTPOLICY and BESTPREF. Then z2 - z1 ⩾ 0 and for the expectations we have E(z1) = 2p2+p-1+γp 2p2+p 3 and E(z2) = 4p2+3p-1 .

3 > 6 So E(z2 - z1) < p/6, and by Markov's inequality

Writing it multiplicatively, with probability at least 1 - ε,

A similar result holds for more than two agents.

Proposition 5. For n agents, there exists a constant C such that for every ε > 0 with probability at least 1 - ε ALTPOLICY is a (1 - C pε )-approximation of the optimal expected utilitarian social welfare.

5 Optimality of the Alternating Policy

We now consider the problem of finding the policy that maximizes the expected utilitarian social welfare for Borda utilities. Bouveret and Lang 2011 stated that this is an open question, and conjectured that this problem is NP-hard. We close this problem, by proving that ALTPOLICY is in fact the optimal policy for any given p with two agents.

Theorem 1. The expected utilitarian social welfare is maximized by the alternating policy for two agents supposing Borda utilities and the full independence assumption.

Note that by linearity of expectation this implies optimality of the alternating policy for every linear scoring function g(k) = αk + β with α, β ∈ R, α ⩽ 0. In particular, the result also holds for quasi-indifferent scoring where g(k) = N + (p - k +1) for large N.

In the following let π∗ p always be the alternating policy of length p. We also recall that due to symmetry we can only consider policies that starts with 1, e.g. policy 212 is equivalent to 121. To prove Theorem 1 we need to prove that for any policy π of length p the expected utilitarian social welfare is smaller or equal to the expected utilitarian social welfare of π∗ p . That is, dswπ = sw(π)-sw(π∗ p ) ⩽ 0. We proceed in two steps. First, we describe dswπ recursively, by representing the policy π in terms of its deviations from π∗ p . Second, given the recursive description of dswπ, we prove by induction that this difference is never positive (Proposition 6). The proof is not trivial as the natural inductive approach to derive dswπ ⩽ 0 from dsw˜π ⩽ 0 does not go through. Hence, we will prove a stronger result in Theorem 2 that implies Proposition 6 and Theorem 1.

Recursive definition. To obtain a recursive definition of dswπ, we observe that any policy π can be written in terms of its deviations from ALTPOLICY policy π∗ . We explain this idea using the following example. Consider a policy π = 1121. There are two ways to extend π with a prefix to obtain policies of length 5: π′ = 11121 and π′′ = 21121 which is equivalent to π′′ = 12212. We say that π′′ = 12212 follows ALTPOLICY in extending π as its prefix is (12) which coincides with the alternation step. We say that π′ = 11121 deviates from ALTPOLICY in extending π as its prefix is (11) which does not correspond to the alternation step.

Next we define a notion of the policy tree, which is a balanced binary tree, that represents all possible policies in terms of deviations from π∗ . The main purpose of this notion is to explain intuitions behind our derivations and proofs. We start with the policy (1), which is the root of the tree. We expand a policy to the left by a prefix of length one. We can follow the strictly alternation policy by expanding (1) with prefix 2. This gives policy (21) which is equivalent to (12) due to symmetry. Alternatively, we can deviate from ALTPOLICY by expanding (1) with prefix 1. This gives policy (11). This way we obtain all policies of length 2. We can continue expanding the tree from (12) and (11) following the same procedure and keeping in mind that we break symmetries by remembering only polices that start with 1. The following example show all polices of length at most 5. By convention, given a policy π in a node of the tree we say that we follow ALTPOLICY on the left branch and deviate from ALTPOLICY on the right branch.

Example 4. Figure 1 shows a tree which represents all policies of length at most 5. A number below each policy shows the value of the expected utilitarian social welfare for this policy. As can be seen from the tree, ALTPOLICY is the optimum policy for all p. Consider, for example, π = 12212. We can obtain this by deviations from π∗ 5 (shown as the dashed path): (1) →L1 (12) →L2 (121) →R3 (1121) →L4 (12212).

Next we give a formal recursive definition of dswπ. We recall that from Lemma 1 the recursions for ALTPOLICY

For any π ∈ Pp, p ⩾ 2 we obtain a similar recursion that depends on whether π follows or deviates from π∗ in extension of ˜π at each step. In the first case, the prefix of π is (12) and in the second case the prefix is (11). So we have

We introduce notations to simplify the explanation. Using Proposition 1 we define δp = u1(π∗ p ) - u2(π∗ p ) = 13 [p + 1 + (-1)p+1γp+1 ]. We define the sets Ap = {(u1(π) - u1(π∗ p ), u2(π) - u2(π∗ p )) : π ∈ Pp} .

Note that for an element (a, b) ∈ Ap corresponding to a policy π ∈ Pp we have a + b = sw(π) - sw(π∗ p ) = dswπ. Hence, π has a higher expected utilitarian social welfare than π∗ p if and only if a + b > 0.

The recursions above provide a description of the sets Ap. We have A1 = {(0, 0)} because π∗ 1 is the only policy of length 1, and for p ⩾ 2 the set Ap consists of the elements (b, p+1 p a) and (a + δp-1, p+1 p (b - δp-1)) where (a, b) runs over Ap-1. Theorem 1 is equivalent to the following statement.

Proposition 6. Let A1 = {(0, 0)} and

for k ⩾ 2 where (a, b) ∈ Ak-1, δk = 1 3 (k + (-1)k γk ). Then a + b ⩽ 0 for all (a, b) ∈ ⋃k Ak.

Figure 2 shows the sets Ak, k = 1, . . . , 4 in the policy tree.

Proving optimality. We might try to prove Proposition 6 inductively by deriving a + b ⩽ 0 for the point (a, b) ∈ Ap corresponding to policy π from a′ + b′ ⩽ 0 for (a′ , b′ ) ∈ Ap-1 corresponding to policy ˜π. Unfortunately, the induction hypothesis is too weak as the following example shows.

Example 5. Assume (a′ , b′ ) = (-12, 11.9) ∈ A10 corresponding to some policy π ∈ P10. Let (a, b) ∈ A11 be obtained from (-12, 11.9) by deviating from π∗ 11 . With δ11 = 2.7643 we obtain a + b = -9.2357 + 9.9662 > 0. Thus (a′ , b′ ) satisfies Proposition 6 while (a, b) violates it.

To remedy this problem we would like to strengthen the proposition, for example by proving a + b ⩽ f (a, b) for all (a, b) ∈ ⋃k Ak where f is some function with f (x, y) ⩽ 0 for all (x, y). The difficulty of finding such a function is indicated by Figure 3 showing the set A10. Different markers distinguish the points arising from A9 by following π∗ from those deviating from π∗ .

The key idea of our proof is to strengthen Proposition 6 in another direction. We describe this strengthening first and then outline the induction argument. The technical details of the proof are presented in the online Appendix D. Consider a policy π that is represented by a node nπ at level k in the policy tree. Instead of requiring the inequality a + b ⩽ 0 only for the point (a, b) ∈ Ak that corresponds to policy π, we also require it for (i) all policies that lay on the path that follow only the right branches from nπ and (ii) all polices that lay on the path that starts from nπ by following the left branch once and then only follow the right branches. To formalize this idea, for k ⩾ 1 we define functions fk, gk : R2 → R2 by fk(x, y) = (y, k+2 k+1 x) and gk(x, y) = (x + δk+1, k+2 k+1 (y - δk+1)). Note that Ak+1 = fk(Ak) ∪ gk(Ak) for all k ⩾ 1, as fk encodes the case when we follow the left branch and gk - the right branch. Figure 2 illustrates this correspondence. We also consider iterated compositions of these functions. For every k ⩾ 1 let Gk0 denote the identity on R2 , i.e. Gk0(x, y) = (x, y), and for m ⩾ 1 let Gkm denote the function

Applying Gkm to the point (a, b) ∈ Ak corresponding to π ∈ Pk gives the point (a′ , b′ ) ∈ Ak+m which corresponds to the policy π′ ∈ Pk+m that is obtained from π by following the right branch m times. For all k ⩾ 1 and m ⩾ 1, we define the function Fkm = Gk+1,m-1 ◦ fk. Fkm corresponds to starting in level k, following the first left branch and then m - 1 right branches. For (x, y) ∈ Ak, Gkm(x, y) ∈ Ak+m for m ⩾ 0 and Fkm(x, y) ∈ Ak+m for m ⩾ 1. Proposition 6 is a consequence of the following theorem.

Theorem 2. Let A1 = {(0, 0)} and

for k ⩾ 1 where (x, y) ∈ Ak, δk = 1 3 (k + (-1)k γk ). Then for every k ⩾ 1 and every (x, y) ∈ Ak the following statements are true.

1. For all m⩾ 0, if (x′ , y′ ) = Gkm(x, y) then x′ + y′ ⩽ 0.

Proof sketch. We provide the full proof in the Appendix C. We give a high-level overview. We start with a few technical lemmas to derive an explicit description of functions (x′ , y′ ) = Fkm(x, y) and (x′′ , y′′ ) = Gkm(x, y). This gives us explicit expressions for the sums x′ + y′ and x′′ + y′′ in terms of x and y. Then we proceed through the induction proof. We summarize the induction step here. Suppose the statements of the theorem are already proved for all sets Al with l < k. Let (x, y) be an arbitrary element of Ak. Suppose (x, y) = fk-1(˜x, ˜ y) for some (˜x, ˜ y) ∈ Ak-1 (the case (x, y) = gk-1(˜x, ˜ y) is similar). Figure 4 shows (˜x, ˜ y) and (x, y) that is obtained from (˜x, ˜ y) by following the left branch. By the induction hypothesis, x′ + y′ ⩽ 0 whenever (x′ , y′ ) ∈ {Gk-1,m(˜x, ˜ y), Fk-1,m(˜x, ˜ y)}. The corresponding nodes are highlighted in gray in Figure 4. To complete the induction step we need to show x′ + y′ ⩽ 0 for (x′ , y′ ) ∈ {Gkm(x, y), Fkm(x, y)}. The corresponding nodes are indicated by dashed circles. The result for (x′ , y′ ) = Gkm(x, y) (gray and dashed) follows immediately as (x′ , y′ ) = Gkm(x, y) = Fk-1,m+1(˜x, ˜ y). For (x′ , y′ ) = Fkm(x, y) we first express x′ + y′ in terms of ˜x and ˜ y. Then, by induction x′′ + y′′ ⩽ 0 for (x′′ , y′′ ) = Gk-1,m-1(˜x, ˜ y).

Inverting the representation of x′′ + y′′ in terms of ˜x and ˜ y we derive a bound ˜x + ˜ y ≤ -c(m) ⩽ 0, depending on m, and this stronger bound is used to prove x′ + y′ ⩽ 0 for (x′ , y′ ) = Fkm(x, y).

The extension of Theorem 2 to n agents is not straightforward. Firstly, it requires deriving exact recursions for the expected utility for an arbitrary p. This is not trivial, as Proposition 1 only provides asymptotics. An easier extension might be to other utility functions. The alternating policy is not optimal for all scoring functions. For example, it is not optimal for the k-approval scoring function which has g(i) = 1 for i ⩽ k and 0 otherwise. However, we conjecture that ALTPOLICY is optimal for all convex scoring functions (which includes lexicographical scoring).

6 Strategic Behaviour

So far, we have supposed agents sincerely pick the most valuable item left. However, agents can sometimes improve their utility by picking less valuable items. To understand such strategic behaviour, we view this as a finite repeated game with perfect information. [Kohler and Chandrasekaran, 1971] proves that we can compute the subgame perfect Nash equilibrium for the alternating policy with two agents by simply reversing the policy and the preferences and playing the game backwards. More recently, [Kalinowski et al., 2012] prove this holds for any policy with two agents.

We will exploit such reversal symmetry. We say that a policy π is reversal symmetric if and only the reversal of π, after interchanging the agents if necessary, equals π. The policies 1212 and 1221 are reversal symmetric, but 1121 is not. The next result follows quickly by expanding and rearranging expressions for the expected utilitarian social welfare using the fact that we can compute strategic play by simply reversing the policy and profile and supposing truthful behaviour.

Theorem 3. For two agents and any utility function, any reversal symmetric policy that maximizes the expected utilitarian social welfare for truthful behaviour also maximizes the expected utilitarian social welfare for strategic behaviour.

As the alternating policy is reversal symmetric, it follows that the alternating policy is also optimal for strategic behaviour. Unfortunately, the generalisation of these results to more than two agents is complex. Indeed, for an unbounded number of agents, computing the subgame perfect Nash equilibrium becomes PSPACE-hard [Kalinowski et al., 2013b].

7 Conclusions

Supposing additive utilities, and full independence between agents, we have shown that we can compute the expected utility of a sequential allocation procedure in polynomial time for any utility function. Using this result, we have proven that the expected utilitarian social welfare for Borda utilities is maximized by the alternating policy in which two agents pick items in a fixed order. We have argued that this mechanism remains optimal when agents behave strategically. There remain open several important questions. For example, is the alternating policy optimal for more than two agents? What happens with non-additive utilities?