Possible and Necessary Allocations via Sequential Mechanisms

1 Introduction

Efficient and fair allocation of resources is a pressing problem within society today. One important and challenging case is the fair allocation of indivisible items [Chevaleyre et al., 2006, Bouveret and Lang, 2008, Bouveret et al., 2010, Aziz et al., 2014b, Aziz, 2014]. This covers a wide range of problems including the allocation of classes to students, landing slots to airlines, players to teams, and houses to people. A simple but popular mechanism to allocate indivisible items is sequential allocation [Bouveret and Lang, 2011, Brams and Taylor, 1996, Kohler and Chandrasekaran, 1971, Levine and Stange, 2012]. In sequential allocation, agents simply take turns to pick the most preferred item that has not yet been taken. Besides its simplicity, it has a number of advantages including the fact that the mechanism can be implemented in a distributed manner and that agents do not need to submit cardinal utilities. Well-known mechanisms like serial dictatorship [Svensson, 1999] fall under the umbrella of sequential mechanisms.

The sequential allocation mechanism leaves open the particular order over the agents (the so called "policy") [Kalinowski et al., 2013a, Bouveret and Lang, 2014]. Should it be a balanced policy i.e., each agent gets the same total Lirong Xia RPI NY 12180, USA xial@cs.rpi.edu number of rounds? Or should it be recursively balanced so that agents pick items in phases, and each agent gets one round per phase? Or perhaps it would be fairer to alternate but reverse the order of the agents in successive phases: a1▷a2▷a3▷a3▷a2▷a1 . . . so that agent a1 takes the first and sixth round? This particular type of policy is used, for example, by the Harvard Business School to allocate courses to students [Budish and Cantillion, 2012] and is referred to as a balanced alternation policy. Another class of policies is strict alternation in which the same ordering is used in each round, such as a1 ▷ a2 ▷ a3 ▷ a1 ▷ a2 ▷ a3 . . . . The sets of balanced alternation and strict alternation policies are subsets of the set of recursively balanced policies which itself is a subset of the set of balanced policies.

We consider here the situation where a policy is chosen from a family of such policies. For example, at the Harvard Business School, a policy is chosen at random from the space of all balanced alternation policies. As a second example, the policy might be left to the discretion of the chair but, for fairness, it is restricted to one of the recursively balanced policies. Despite uncertainty in the policy, we might be interested in the possible or necessary outcomes. For example, can I get my three most preferred courses? Do I necessarily get my two most preferred courses? We examine the complexity of checking such questions. There are several highstake applications for these results. For example, sequential allocation is used in professional sports 'drafts' [Brams and Straffin, 1979]. The precise policy chosen from among the set of admissible policies can critically affect which teams (read agents) get which players (read items).

The problems of checking whether an agent can get some item or set of items in a policy or in all policies is closely related to the problem of 'control' of the central organizer. For example, if an agent gets an item in all feasible policies, then it means that the chair cannot ensure that the agent does not get the item. Apart from strategic motivation, the problems we consider also have a design motivation. The central designer may want to consider all feasible policies uniformly at random (as is the case in random serial dictatorship [Aziz et al., 2013, Saban and Sethuraman, 2013]) and use them to find the probability that a certain item or set of item is given to an agent. The probability can be a suggestion of time sharing of an item. The problem of checking whether an agent gets a certain item or set of items in some policy is equivalent to checking whether an agent gets a certain item or set of items with non-zero probability. Similarly, the problem of checking whether an agent gets a certain item or set of items in all policies is equivalent to checking whether an agent gets a certain item or set of items with probability one.

We let A = {a1, . . . , an} denote a set of n agents, and I denote the set of m = kn items 1 . P = (P1, . . . , Pn) is the profile of agents' preferences where each Pj is a linear order over I. Let M denote an assignment of all items to agents, that is, M : I → A. We will denote a class of policies by C. Any policy π specifies |I| rounds of the agents. An agent picks her most preferred item that has not yet been allocated in her rounds.

Example 1. Consider the setting in which A = {a1, a2}, I = {b, c, d, e}, the preferences of agent a1 are b ≻ c ≻ d ≻ e and of agent a2 are b ≻ d ≻ c ≻ e. Then for the policy a1 ▷ a2 ▷ a2 ▷ a1, agent a1 gets {b, e} whilst a2 gets {c, d}. There are four rounds divided into two phases. Agent a1 picks item e in the second phase.

We consider the following natural computational problems.

(i) POSSIBLEASSIGNMENT: Given (A, I, P,M) and policy class C, does there exist a policy in C which results in M? ; (ii) NECESSARYASSIGNMENT: Given (A, I, P,M), and policy class C, is M the result of all policies in C? ; (iii) POSSIBLEITEM: Given (A, I, P, aj, o) where aj ∈ A and o ∈ I, and policy class C, does there exist a policy in C such that agent aj gets item o? ; (iv) NECESSARYITEM: Given (A, I, P, aj, o) where aj ∈ A and o ∈ I, and policy class C, does agent aj get item o for all policies in C? ; (v) POSSIBLESET: Given (A, I, P, aj , I ′ ) where aj ∈ A and I ′ ⊆ I, and policy class C, does there exist a policy in C such that agent aj gets exactly I ′ ? ; (vi) NECESSARYSET: Given (A, I, P, aj, I ′ ) where aj ∈ A and I ′ ⊆ I, and policy class C, does agent aj get exactly I ′ for all policies in C? ; (vii) POSSIBLESUBSET: Given (A, I, P, aj , I ′ ) where aj ∈ A and I ′ ⊆ I, and policy class C, does there exist a policy in C such that agent aj gets I ′ ? ; (viii) NECESSARYSUBSET: Given

1 This is without loss of generality since we can add dummy items of zero utility to any agent.

(A, I, P, aj , I ′ ) where aj ∈ A and I ′ ⊆ I, and policy class C does agent aj get I ′ for all policies in C?

We will consider problems top-k POSSIBLESET and top-k NECESSARYSET that are restrictions of POSSIBLESET and NECESSARYSET in which the set of items I ′ is the set of top k items of the distinguished agent. When policies are chosen at random, the possible and necessary allocation problems we consider are also fundamental to understand more complex problems of computing the probability of certain allocations.

Contributions: Our contributions are two fold. First, we provide necessary and sufficient conditions for an allocation to be the outcome of balanced, recursively balanced, balanced alternation, and strict alternation policies respectively. Previously Brams and King [2005] characterized the outcomes of arbitrary policies. In a similar vein, we provide sufficient and necessary conditions for more interesting classes of policies such as recursively balanced and balanced alternation. Second, we provide a detailed analysis of the computational complexity of possible and necessary allocations under sequential policies. Table 1 summarizes our complexity results. Our NP/coNP-completeness results also imply that there exists no polynomial-time algorithm that can approximate within any factor the number of admissible policies which do or do not satisfy the target goals.

Related Work. Sequential allocation has been considered in the operations research and fair division literature (e.g. [Kohler and Chandrasekaran, 1971, Brams and Taylor, 1996]). It was popularized within the AI literature as a simple yet effective distributed mechanism [Bouveret and Lang, 2011] and has been studied in more detail subsequently [Kalinowski et al., 2013a,b, Bouveret and Lang, 2011, 2014].

The problems considered in the paper are similar in spirit to a class of control problems studied in voting theory: if it is possible to select a voting rule from the set of voting rules, can one be selected to obtain a certain outcome [Erd´elyi and Elkind, 2012]. They are also related to a class of control problems in knockout tournaments: does there exist a draw of a tournament for which a given player wins the tournament [Vu et al., 2009, Aziz et al., 2014a]. Possible and necessary winners have also been considered in voting theory [Konczak and Lang, 2005, Xia and Conitzer, 2011, Aziz et al., 2012].

When n = m, serial dictatorship is a well-known mechanism in which there is an ordering of agents and with respect to that ordering agents pick the most preferred unallocated item in their turns [Svensson, 1999]. We note that serial dictatorship for n = m is a balanced, recursively balanced and balanced alternation policy.

2 Characterizations of Outcomes of Sequential Allocation

In this section we provide necessary and sufficient conditions for a given allocation to be the outcome of a balanced policy, recursively balanced policy, or balanced alternation policy. We first define conditions on an allocation M. An allocation is Pareto optimal if there is no other allocation in which each item of each agent is replaced by at least as preferred an item and at least one item of some agent is replaced by a more preferred item.

Condition 1. M is Pareto Optimal.

Condition 2. M is balanced.

It is well-known that Condition 1 characterizes outcomes of all sequential allocation mechanisms (without constraints). Brams and King [2005] proved that an assignment is achievable via sequential allocation iff it satisfies Condition 1. The theorem of Brams and King [2005] generalized the characterization of Abdulkadiro˘glu and S¨onmez [1998] of Pareto optimal assignments as outcomes of serial dictatorships when m = n. We first observe the following simple adaptation of the characterization of Brams and King [2005] to characterize possible outcomes of balanced policies:

Remark 1. Given a profile P, an allocation M is the outcome of a balanced policy if and only if M satisfies Conditions 1 and 2.

Given a balanced allocation M, for each agent aj ∈ A and each i ≤ k, let pij denote the item that is ranked at the i-th position by agent aj among all items allocated to agent aj by M. The third condition requires that for all 1 ≤ t < s ≤ k, no agent prefers the s-th ranked item allocated to any other agent to the t-th ranked item allocated to her.

Condition 3. For all 1 ≤ t < s ≤ k and all pairs of agent aj, aj ′ , agent aj prefers ptj to psj ′ .

The next theorem states that Conditions 1 through 3 characterize outcomes of recursively balanced policies.

Theorem 1. Given a profile P, an allocation M is the outcome of a recursively balanced policy if and only if it satisfies Conditions 1, 2, and 3.

Proof. To prove the "only if" direction, clearly if M is the outcome of a recursively balanced policy then Condition 1 and 2 are satisfied. If Condition 3 is not satisfied, then there exists 1 ≤ t < s ≤ k and a pair of agents aj, aj ′ such that agent aj prefers psj ′ to ptj . We note that in the round when agent aj is about to choose ptj according to M, psj ′ is still available, because it is allocated by M in a later round. However, in this case agent aj will not choose ptj because it is not her top-ranked available item, which is a contradiction.

To prove the "if" direction, for any allocation M that satisfies the three conditions we will construct a recursively balanced policy π. For each i ≤ k = m/n, we let phase i denote the ((i-1)n+1)-th round through in-th round. It follows that for all i ≤ k, {pij : j ≤ n} are allocated in phase i. Because of Condition 3, {pij : j ≤ n} is a Pareto optimal allocation when all items in {pi′ j : i′ < i, j ≤ n} are removed. Therefore there exists an order πi over A that gives this allocation. Let π = π1 ▷ π2 ▷ · · · ▷ πk. It is not hard to verify that π is recursively balanced and M is the outcome of π.

Given a profile P and an allocation M that is the outcome of a recursively balanced policy, that is, it satisfies the three conditions as proved in Theorem 1, we construct a directed graph GM = (A,E), where the vertices are the agents, and we add the edges in the following way. For each odd i ≤ k, we add a directed edge aj ′ → aj if and only if agent aj prefers pij ′ to pij and the edge is not already in GM; for each even i ≤ k, we add a directed edge aj → aj ′ if and only if agent aj prefers pij ′ to pij and the edge is not already in GM.

Condition 4. Suppose M is the outcome of a recursively balanced policy. There is no cycle in GM.

Theorem 2. An allocation M is achievable by a balanced alternation policy if and only if satisfies Conditions 1- 4.

Proof. The "only if" direction: SupposeM is achievable by a balanced alternation policy π. Let π′ denote the suborder of π from turn 1 to turn n. Let Gπ′ = (A, E′ ) denote the directed graph where the vertices are the agents and there is an edge aj ′ → aj if and only if aj ′ ▷π′ aj. It is easy to see that Gπ′ is acyclic and complete. We claim that GM is a subgraph of Gπ′ . For the sake of contradiction suppose there is an edge aj → aj ′ in GM but not in Gπ′ . If aj → aj ′ is added to GM in an odd round i, then it means that agent j ′ prefers pij to pij ′ . Because aj → aj ′ is not in Gπ′ , aj ′ ▷π′ aj. This means that right before aj ′ choosing pij ′ inM, pij is still available, which contradicts the assumption that aj ′ chooses pij ′ inM. If aj → aj ′ is added to GM in an even round, then following a similar argument we can also derive a contradiction. Therefore, GM is a subgraph of Gπ′ , which means that GM is acyclic.

The "if" direction: Suppose the four conditions are satisfied. Because GM has no cycle, we can find a linear order π′ over A such that GM is a subgraph of Gπ′ . We next prove that M is achievable by the balanced alternation policy π whose first n rounds are π′ . For the sake of contradiction suppose this is not true and let t denote the earliest round that the allocation in π differs the allocation in M. Let aj denote the agent at the t-th tound of π, let pi′ j ′ denote the item she gets at round t in π, and let pij denote the item that she is supposed to get according to M. Due to Condition 3, i′ ≤ i. If i′ < i then agent aj ′ did not get item pi′ j ′ in a previous round, which contradicts the selection of t. Therefore i′ = i. If i is odd, then there is an edge aj ′ → aj in GM, which means that aj ′ ▷π′ aj. This means that aj ′ would have chosen pij ′ in a previous round, which is a contradiction. If i is even, then a similar contradiction can be derived. Therefore M is achievable by π.

Given a profile P and an allocation M that is the outcome of a recursively balanced policy, that is, it satisfies the three conditions as proved in Theorem 1, we construct a directed graph HM = (A,E), where the vertices are the agents, and we add the edges in the following way. For each j ≤ n and i ≤ k, we let pij denote the item that is ranked at the i-th position among all items allocated to agent j. For each i ≤ k, we add a directed edge aj ′ → aj if j prefers pij ′ to pij if the edge is not already there.

Condition 5. If M is the outcome of a recursively balanced policy, then there is no cycle in HM.

Theorem 3. An allocation M is achievable by a strict alternation policy if and only if satisfies Condition 1, 2, 3, &5.

Proof. The "only if" direction: IfM is an outcome of a recursively balanced policy but does not satisfy 5, then this means that there is a cycle in HM. Let agents ai and aj be in the cycle. This means that ai is before aj in one phase and aj is before ai in some other phase.

The "if" direction: Now assume that M is an outcome of a recursively balanced policy but is not alternating. This means that there exist at least two agents ai and aj such that ai comes before aj in one phase and aj comes before ai in some other phase. But this means that there is cycle ai → aj → ai in graph HM .

3 General Complexity Results

Before we delve into the complexity results, we observe the following reductions between various problems.

Lemma 1. Fixing the policy class to be one of {all, balanced policies, recursively balanced policies, balanced alternation policies}, there exist polynomial-time many-one reductions between the following problems: POSSIBLESET to POSSIBLESUBSET; POSSIBLEITEM to POSSIBLESUBSET; Top-k POSSIBLESET to POSSIBLESET; NECESSARYSET to NECESSARYSUBSET; NECESSARYITEM to NECESSARYSUBSET; and Top-k NECESSARYSET to NECESSARYSET.

A polynomial-time many-one reduction from problem Q to problemQ′ means that if Q is NP(coNP)-hard then Q′ is also NP(coNP)-hard, and if Q′ is in P then Q is also in P. We also note the following. For n = 2, POSSIBLEASSIGNMENT and POSSIBLESET are equivalent for any type of policies. Since n = 2, the allocation of one agent completely determines the overall assignment.

For m = n, checking whether there is a serial dictatorship under which each agent gets exactly one item and a designated agent aj gets item o is NP-complete [Theorem 2, Saban and Sethuraman, 2013]. They also proved that for m = n, checking if for all serial dictatorships, agent aj gets item o is in P. Hence, we get the following statements.

Theorem 4. POSSIBLEITEM and POSSIBLESET is NPcomplete for balanced, recursively balanced as well as balanced alternation policies.

Theorem 4 does not necessarily hold if we consider the top element or the top k elements. Therefore, we will especially consider top-k POSSIBLESET. Similarly, we get that for m = n, NECESSARYITEM and NECESSARYSET is polynomial-time solvable for balanced, recursively balanced, and balanced alternation policies.

For arbitrary policies, we first observe that POSSIBLEITEM, NECESSARYITEM and NECESSARYSET are trivial: POSSIBLEITEM always has a yes answer (just give all the turns to that agent) and NECESSARYITEM and NECESSARYSET always have a no answer (just don't give the agent any turn). Similarly, NECESSARYASSIGNMENT always has a no answer.

Theorem 5. POSSIBLEASSIGNMENT is polynomial-time solvable for arbitrary policies.

Proof. By the characterization of Brams and King [2005], all we need to do is to check whether the assignment is Pareto optimal. It can be checked in polynomial time O(|I|2 ) whether a given assignment is Pareto optimal via an extension of a result of Abraham et al. [2005].

There is also a polynomial-time algorithm for POSSIBLESET for arbitrary policies via a greedy approach.

Theorem 6. POSSIBLESET is polynomial-time solvable for arbitrary policies.

4 Balanced Policies

In contrast to arbitrary policies, POSSIBLEITEM, NECESSARYITEM, NECESSARYSET, and NECESSARYASSIGNMENT are more interesting for balanced policies since we may be restricted in allocating items to a given agent to ensure balance. Before we consider them, we get the following corollary of Remark 1.

Corollary 1. POSSIBLEASSIGNMENT for balanced assignments is in P.

Note that an assignment is achieved via all balanced policies iff the assignment is the unique balanced assignment that is Pareto optimal. This is only possible if each agent gets his top k items. Hence, we obtain the following.

Theorem 7. NECESSARYASSIGNMENT for balanced assignments is in P.

Compared to NECESSARYASSIGNMENT, the other 'necessary' problems are intractable.

Theorem 8. NECESSARYITEM and NECESSARYSUBSET for balanced policies where k is not fixed is coNP-complete.

Proof. Membership in coNP is obvious. By Lemma 1 it suffices to prove that NECESSARYITEM is coNP-hard, which we will prove by a reduction from POSSIBLEITEM for k = 1, which is NP-complete [Saban and Sethuraman, 2013]. Let (A, I, P, a1, o) denote an instance of the possible allocation problem for k = 1, where A = {a1, . . . , an}, I = {o1, . . . , on}, o ∈ I, P = (P1, . . . , Pn) is the preference profile of the n agents, and we are asked whether it is possible for agent a1 to get item o in some sequential allocation. Given (A, I, P, a1, o), we construct the following NECESSARYITEM instance.

Agents: A′ = A ∪ {an+1}.

Items: I ′ = I ∪D∪F1 ∪· · ·∪Fn, where |D| = n-1 and for each aj ∈ A, |Fj | = n-2. We have |I ′ | = (n+1)(n-1) and k = n - 1.

Preferences:

• The preferences of a1 is [F1 ≻ P1 ≻ others].
• For any j ≤ n, the preferences of aj are obtained from [Fj ≻ Pj] by replacing o by D, and then add o to the bottom position.
• The preferences for an+1 is [o ≻ others].

We are asked whether agent an+1 always gets item o.

If (A, I, P, a1, o) has a solution π, we show that the NECESSARYITEM instance is a "No" instance by considering π ▷ · · · ▷ π ︸ ︷︷ ︸ n-1 ▷an+1 ▷ · · · ▷ an+1 ︸ ︷︷ ︸ n-1 . In the first (n - 2)n

rounds all Fj's are allocated to agent aj's. In the following n rounds o is allocated to a1, which means that an+1 does not get o.

Suppose the NECESSARYITEM instance is a "No" instance and agent n + 1 does not get o in a balanced policy π′ . Because agent a2 through an rank o in their bottom position, o must be allocated to agent a1. Clearly in the first n - 2 times when agent a1 through an choose items, they will choose F1 through Fn respectively. Let π denote the order over which agents a1 through an choose items for the last time. We obtain another order π∗ over A from π by moving all agents who choose an item in D after agent a1 while keeping other orders unchanged. It is not hard to see that the outcomes of running π and π∗ are the same from the beginning until agent a1 gets o. This means that π∗ is a solution to (A, I, P, a1, o).

The problems becomes easier when k is constant or we are concerned about top k items.

Theorem 9. For any constant k, NECESSARYSET and NECESSARYSUBSET for balanced policies are in P.

Proof. W.l.o.g. given a NECESSARYSET instance (A, I, P, a1, I ′ ), if I ′ is not the top-ranked k items of agent a1 then it is a "No" instance because we can simply let agent a1 choose items in the first k rounds. When I ′ is top-ranked k items of agent a1, (A, I, P, a1, I ′ ) is a "No" instance if and only if (A, I, P, a1, o) is a "No" instance for some o ∈ I ′ , which can be checked in polynomial time by Theorem 10. A similar algorithm works for NECESSARYSUBSET.

Theorem 10. For any constant k, NECESSARYITEM for balanced policies is in P.

Proof. Given a NECESSARYITEM instance (A, I, P, a1, o), if o is ranked below the k-th position by agent a1 then we can return "No", because by letting agent a1 choose in the first k rounds she does not get item o. Suppose o is ranked at the k′ -th position by agent a1 with k′ ≤ k, the next claim provides an equivalent condition to check whether the NECESSARYITEM instance is a "No" instance.

Claim 1. Suppose o is ranked at the k′ -th position by agent a1 with k′ ≤ k, the NECESSARYITEM instance (A, I, P, a1, o) is a "No" instance if and only if there exists a balanced policy

π such that (i) agent a1 picks items in the first k′ - 1 rounds and the last k - k′ + 1 rounds, and (ii) agent a1 does not get o.

Let I ∗ denote agent a1's top k′ - 1 items. In light of the claim above, to check whether the (A, I, P, a1, o) is a "No" instance, it suffices to check for every set of k - k′ + 1 items ranked below the k′ -th position by agent a1, denoted by I ′ , whether it is possible for agent a1 to get I ∗ and I ′ by a balanced policy where agent a1 picks items in the first k′ - 1 rounds and the last k - k′ + 1 rounds. To this end, for each I ′ ⊆ I - I ∗ - {o} with |I ′ | = k - k′ + 1, we construct the following maximum flow problem FI ′ , which can be solved in polynomial-time by e.g. the Ford-Fulkerson algorithm.

• Vertices: s, t, A - {a1}, I - I ′ - I ∗ .
• Edges and weights: For each a ∈ A - {a1}, there is an edge s → a with weight k; for each a ∈ A - {a1} and c ∈ I -I ′ -I ∗ such that agent a ranks c above all items in I ′ , there is an edge a → c with weight 1; for each c ∈ I-I ′ -I ∗ , there is an edge c → t with weight 1.
• We are asked whether the maximum amount of flow from s to t is k(n - 1) (the maximum possible flow from s to t).

Claim 2. (A, I, P, a1, o) is a "No" instance if and only if there exists I ′ ⊆ I - I ∗ - {o} with |I ′ | = k - k′ + 1 such that FI ′ has a solution.

Because k is a constant, the number of I ′ we will check is a constant. Algorithm 1 solves NECESSARYITEM with balanced policies in polynomial time.

Algorithm 1: NECESSARYITEM for balanced policies.

Input: A NECESSARYITEM instance (A, I, P, aj , o). 1 if o is ranked below the k-th position by agent aj then 2 return "No". 3 end 4 Let I ∗ denote agent aj's top k′ -1 items. 5 for I ′ ⊆ I - I ∗ -{o} with |I ′ | = k -k′ +1 do 6 if F|I′| has a solution then 7 return "No" 8 end 9 end 10 return "Yes".

Theorem 11. NECESSARYSET and top-k NECESSARYSET for balanced policies are in P even when k is not fixed.

Proof. Given an instance of NECESSARYSET, if the target set is not top-k then the answer is "No" because we can simply let the agent choose k items in the first k rounds. It remains to show that top-k NECESSARYSET for balanced policies is in P. That is, given (A, I, P, a1), we can check in polynomial time whether there is a balanced policy π for which agent a1 does not get exactly her top k items.

For NECESSARYSET, suppose agent a1 does not get her top-k items under π. Let π′ denote the order obtained from π by moving all agent a1's rounds to the end while keeping the other orders unchanged. It is easy to see that agent a1 does not get her top-k items under π′ either. Therefore, NECESSARYSET is equivalent to checking whether there exists an order π where agent a1 picks item in the last k rounds so that agent a1 does not get at least one of her top-k items.

We consider an equivalent, reduced allocation instance where the agents are {a1, a2, . . . , an}, and there are k(n - 1)+1 items I ′ = (I -I ∗ ) ∪{c}, where I ∗ is agent a1's topk items. Agent aj's preferences over I ′ are obtained from Pj by replacing the first occurrence of items in I ∗ by c, and then removing all items in I ∗ while keeping the order of other items the same. We are asked whether there exists an order π where agent a1 is the last to pick and a1 picks a single item, and each other agents picks k times, so that agent a1 does not get item c. This problem can be solved by a polynomialtime algorithm based on maximum flows that is similar to the algorithm for NECESSARYITEM in Theorem 10.

5 Recursively Balanced Policies

From Theorem 1, we get the following corollary.

Corollary 2. POSSIBLEASSIGNMENT for recursively balanced policies is in P.

We also report computational results for problems other than POSSIBLEASSIGNMENT. The following algorithm works via a greedy approach.

Theorem12. NECESSARYASSIGNMENT for recursively balanced policies is in P.

The other 'necessary problems' turn out to be computationally intractable.

Theorem 13. For k ≥ 2, NECESSARYITEM, NECESSARYSET, top-k NECESSARYSET, and NECESSARYSUBSET for recursively balanced policies are coNP-complete.

On the other hand, Top-2 POSSIBLESET is easy via a reduction to maximum matching.

Theorem 14. Top-k POSSIBLESET for recursively balanced policies is in P for k = 2.

Finally, top-k-POSSIBLESET is NP-complete iff k ≥ 3.

Theorem 15. For all k ≥ 3, top-k POSSIBLESET for balanced policies is NP-complete.

6 Strict Alternation Policies

Since there are n! possible strict alternation policies, so if n is constant, then all problems can be solved in polynomial time by brute force search. Note that such an argument does not apply to recursively balanced policies. As a result of our characterization of strict alternation outcomes (Theorem 3), we get the following.

Corollary 3. POSSIBLEASSIGNMENT for strict alternation polices is in P.

We also present other computational results.

Theorem 16. NECESSARYASSIGNMENT for strict alternation polices is in P.

Theorem 17. Top-k POSSIBLESET for strict alternation policies is in P for k = 2.

For Theorem 17, the polynomial-time algorithm is similar to the algorithm for Theorem 14. The next theorems state that the remaining problems are hard to compute. Both theorems are proved by reductions from POSSIBLEITEM.

Theorem 18. For all k ≥ 3, top-k POSSIBLESET is NPcomplete for strict alternation policies.

Theorem 19. For all k ≥ 2, NECESSARYITEM, NECESSARYSET, top-k NECESSARYSET, and NECESSARYSUBSET are coNP-complete for strict alternation policies.

7 Balanced Alternation Policies

If n is constant, then all problems can be solved in polynomial time by brute force search. As a result of our characterization of balanced alternation outcomes (Theorem 2), we get the following.

Corollary 4. POSSIBLEASSIGNMENT for balanced alternation polices is in P.

NECESSARYASSIGNMENT can be solved efficiently as well.

Theorem20. NECESSARYASSIGNMENT for balanced alternation polices is in P.

We already know that for k = m/n = 1, top-k possible and necessary problems can be solved in polynomial time. The next theorems state that for any other k, they are NPcomplete for balanced alternation policies. Theorem 21 is proved by a reduction from the EXACT 3-COVER problem and Theorem 22 is proved by a reduction from the POSSIBLEITEM problem.

Theorem 21. For all k ≥ 2, top-k POSSIBLESET is NPcomplete, NECESSARYITEM is coNP-complete, and NECESSARYSUBSET is coNP-complete for balanced alternation policies.

Theorem 22. For all k ≥ 2, top-k NECESSARYSET for balanced alternation policies is coNP-complete.

8 Conclusions

We have studied sequential allocation mechanisms where the policy has not been fixed or has been fixed but not announced. We have characterized the allocations achievable with common classes of policies. We have also identified the computational complexity of identifying the possible or necessary items, set or subset of items to be allocated to an agent when using one of the policy classes. There are interesting future directions including considering other common classes of policies, as well as other properties of the outcome like the possible or necessary welfare.

Acknowledgments

We thank anonymous reviewers of AAAI-14 and IJCAI-15 and participants of MATCHUP-15 for helpful comments. Xia acknowledges NSF CAREER under award number IIS1453542 for support. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.