# pareto_optimal_allocation_under_uncertain_preferences__6b536eeb.pdf

Pareto Optimal Allocation under Uncertain Preferences

Haris Aziz Data61, CSIRO and UNSW Sydney, Australia haris.aziz@data61.csiro.au

Ronald de Haan University of Amsterdam Amsterdam, the Netherlands R.de Haan@uva.nl

Baharak Rastegari University of Bristol Bristol, UK baharak.rastegari@bristol.ac.uk

The assignment problem is one of the most wellstudied settings in social choice, matching, and discrete allocation. We consider this problem with the additional feature that agents preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under two natural uncertainty models: (1) the lottery model in which each agent has an independent probability distribution over linear orders and (2) the joint probability model that involves a joint probability distribution over preference proﬁles. For both of these models, we present a number of algorithmic and complexity results highlighting the diﬀerence and similarities in the complexity of the two models.

1 Introduction

Multi-agent resource allocation and dealing with uncertainty are two big topics in AI. In this paper we examine optimal allocation of resources under uncertain preferences. When preferences of agents are aggregated to identify a desirable social outcome, Pareto optimality is a minimal requirement. Pareto optimality stipulates that there should not be another outcome that is at least as good for all agents and better for at least one agent. We take Pareto optimality as a central concern and consider a richer version of the classical assignment problem where the twist is that agents may express uncertainty in their preferences. The assignment problem is a fundamental setting in which n agents express preferences over n items and each agent is to be allocated one item. The setting is a classical one in discrete allocation. Its axiomatic and computational aspects have been well-studied [Abdulkadiro glu and S onmez, 1999; Abraham et al., 2005; Aziz et al., 2015; 2016b; Bogomolnaia and Moulin, 2001; G ardenfors, 1973; Svensson, 1994;

1999]. Our motivation for studying assignment with uncertain preferences is that agents preferences may not be completely known because of lack of information or communication. In some settings, eliciting preferences from agents may be costly, so a central planner may want to only obtain, and provide a recommendation based on, a subset of the complete orders [Rastegari et al., 2013; 2014; Drummond and Boutilier, 2014]. Another possible motivation is that agents are in fact virtual or bidding agents who are each representing a group of real agents and the virtual agent s probabilistic preferences simply represent the composition of preferences of the real agents it represents. Our work is inspired by the recent work of Aziz et al. [2016a] who examined the stable marriage problem under uncertain preferences. Uncertainty in preferences has already been studied in voting [Hazon et al., 2012]. Similarly, in auction theory, it is standard to examine Bayesian settings in which there is probability distribution over the types of the agents. Although computational aspects of Pareto optimal outcomes have been intensely studied in various settings such as assignment, matching, housing markets, and committee voting [Abraham et al., 2005; Aziz and de Keijzer, 2012; Aziz et al., 2015; 2016c; Erdil and Ergin, 2015; Krysta et al., 2014; Manlove, 2013; Saban and Sethuraman, 2013], there has not been much work on Pareto optimality under uncertain preferences. In the presence of uncertainty, one can relax the goal of computing a Pareto optimal outcome and focus on computing outcomes that have the highest probability of being Pareto optimal. We will abbreviate Pareto optimal as PO. If an assignment is Pareto optimal with probability one, we will call it certainly PO. We consider the following uncertainty models:

Lottery Model: For each agent, we are given a probability distribution over linear preferences.

Joint Probability Model: A probability distribution over linear preference proﬁles is speciﬁed.

The most natural computational problems that we will consider are as follows.

PO-Probability: what is the probability that a given assignment is PO?

A preference proﬁle speciﬁes (deterministic) preferences of each agent over items.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Assignment With Highest PO-Probability: compute an assignment with the highest probability of being PO.

We also consider problems simpler than PO-Probability:

Is PO-Probability Non-Zero: for a given assignment, is its probability of being PO non-zero?

Is PO-Probability One: for a given assignment, is its probability of being PO one?

We also consider a problem connected to Assignment With Highest PO-Probability: Exists Certainly PO-Assignment asks whether there exists an assignment that is PO with probability one. Note that Exists Possibly PO-Assignment the problem of checking whether there exists some PO assignment with non-zero probability is trivial for all uncertainty models in which the induced certainly preferred relation is acyclic. An agent certainly prefers an item to another if the preference is with probability 1. The reason for the triviality is that the certainly preferred relation can be completed in a way so that it is transitive, and then for the completed deterministic preferences there exists at least one PO assignment. Note that the product of the independent uncertain preferences in the lottery model results in a probability distribution over preference proﬁles and hence can be represented in the joint probability model. However, the change in representation can result in a blowup. Thus whereas the joint probability model is more general than the lottery model, it is not as compact. In view of this, complexity results for one model do not directly carry over to results for the other model. We say that a given uncertainty model is independent if any uncertain preference proﬁle L under the model can be written as a product of uncertain preferences La for all agents a, where all La s are independent [Aziz et al., 2016a]. Note that the lottery model is independent but the joint probability model is not.

Contributions We initiate the ﬁrst study of computational aspects of Pareto optimal allocation under uncertain preferences. We show that for both the lottery model and the joint probability model, Exists Certainly PO-Assignment is NPcomplete. We also prove that Assignment With Highest POProbability is NP-hard for both models. In view of these results, we see that as we move from deterministic preferences to uncertain preferences, the complexity of computing Pareto optimal assignments jumps signiﬁcantly. On the other hand, we show that for a general class of independent uncertainty models, both problems Is PO-Probability Non Zero and Is PO-Probability One can be solved in linear time. Whereas PO-Probability is polynomial-time solvable for the joint probability model, we prove that the problem is #Pcomplete for the lottery model. This problem becomes polynomial-time solvable for the lottery model if there is a constant number of uncertain agents. Moreover, we show that the problem PO-Probability for the lottery model can be solved in ﬁxed-parameter tractable time when parameterized by the number of uncertain agents. Our results are summarized in Table 1.

2 Preliminaries

The setting we consider is the assignment problem which is a triple (N, O, ) where N is the set of n agents {1, . . . , n}, O = {o1, . . . , on} is the set of n items, and = ( 1, . . . , n) is a preference proﬁle that speciﬁes complete, asymmetric, and transitive preferences i of each agent i over O. We write o i o if o i o or o = o. We will denote by R(O) the set of all complete and transitive relations over the set of items O. We will denote by S the preference proﬁle of agents in the set S N. An assignment is an allocation of items to agents, represented as an n n matrix [p(i)(oj)]1 i n,1 j n such that for all i N, and o j O, p(i)(oj) {0, 1}; for all i {1, . . . , n}, P j N p(i)(oj) = 1 ; and for all j {1, . . . , n}, P i N p(i)(oj) = 1. The aforementioned constraints ensure that each item is allocated wholly (items are indivisible), each agent is allocated exactly one item, and each item is allocated to exactly one agent. An agent i gets item o j if and only if p(i)(oj) = 1. Each row p(i) = (p(i)(o1), . . . , p(i)(on)) represents the allocation of agent i. With an abuse of notation we write p(i) = oj if p(i)(oj) = 1 for some item oj, and p(i) = otherwise. We always assume that every agent prefers any item to , i.e. to being allocated no item. An assignment p is Pareto optimal if there does not exist another assignment q such that q(i) i p(i) for all i N and q(i) i p(i) for some i N. If such an assignment q exists, then we say that q Pareto dominates p. We ﬁrst note a couple of well-known characterisations of Pareto optimal assignments. The characterisations give rise to linear-time algorithms for computing and verifying Pareto optimal assignments in settings with deterministic preferences. An assignment p admits a trading cycle o0, i0, o1, i1, . . . , ok 1, ik 1, o0 if for all j {0, . . . , k 1} we have p(ij)(o j) = 1 and oj+1 mod k i j o j. Intuitively, each agent i j in the trading cycle prefers the next item oj+1 (o0 if j = k 1) to his assigned item o j. Thus, the existence of a trading cycle implies that there is a set of agents who all beneﬁt from trading their assigned items among themselves.

Fact 1 (Folklore) An assignment is Pareto optimal if and only if it does not admit a trading cycle.

We will also use the following characterization of Pareto optimal discrete assignments [Abdulkadiro glu and S onmez, 1998] that is deﬁned with respect to outcomes of serial dictatorship. Serial dictatorship is a straightforward greedy assignment mechanism that is speciﬁed with respect to a permutation π over N. The mechanism takes each agent in turn, according to the permutation π, and allocates him the most preferred item on his preference list that has not been allocated yet. We will denote by S D(N, O, , π) the outcome of applying serial dictatorship with respect to permutation π over assignment problem (N, O, ).

Fact 2 (Abdulkadiro glu and S onmez [1998]) An assignment is Pareto optimal if and only if it is an outcome of serial dictatorship.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Lottery Joint Probability Model Model Problems

PO-Probability #P-complete (Thm 8) but in FPT w.r.t. parameter: in P (Thm 2) # uncertain agents (Thm 9)

Is PO-Probability Non-Zero in P (Thm 5) in P (Thm 2) Is PO-Probability One in P (Thm 4) in P (Thm 2)

Exists Possibly PO-Assignment in P (trivially) in P (trivially)

Exists Certainly PO-Assignment NP-complete (Thm 6) NP-complete (Thm 3)

Assignment With Highest PO-Prob NP-hard (Cor 3) NP-hard (Cor 2)

Table 1: Summary of results.

Fact 2 also follows from Proposition 1 of Brams and King [2005]. The facts above show that when preferences are deterministic, a Pareto optimal assignment can be computed and veriﬁed easily [Abraham et al., 2005]. In this paper we focus on ﬁnding and verifying Pareto optimal assignments in settings where agents have uncertain preferences.

Example 1 Consider the following assignment problem in which agent 1 has uncertain preferences in the lottery model.

1 : a, b, c (0.6) 2 : b, a, c b, a, c (0.4) 3 : c, b, a

The same uncertain preferences can be also represented in the joint probability model with a probability distribution over two preference proﬁles. Consider the assignment q in which 1 gets a, 2 gets b, and 3 gets c. The probability of this assignment being PO is 1. This can be veriﬁed by considering each of the two possible preference proﬁles, and testing that no other assignment Pareto dominates q under either of them. On the other hand, the assignment p in which 1 gets b, 2 gets a, and 3 gets c has 0.4 probability of being PO. This is because p is not PO if the ﬁrst possible preference list of agent 1 is realized, i.e., if a 1 b 1 c. To see this, notice that p admits a trading cycle b, 1, a, 2, b , implying that 1 and 2 prefer to trade their items and be both better oﬀ. If 1 and 2 trade their assigned items, we get assignment q. Assignment q Pareto dominates assignment p when the ﬁrst possible preference list of agent 1 is realized. Assignment p is PO if the second possible preference list of agent 2 is realized, i.e., if b 1 a 1 c. Note that p is the outcome of applying serial dictatorship with respect to permutation π = 1, 2, 3: (1) the ﬁrst agent in the permutation, agent 1, is allocated his most preferred item, item b, (2) agent 2 is allocated his most proﬀered available item, that is a, as b has been already allocated to 1, (3) agent 3 is allocated his most preferred available item, that is c.

3 Joint Probability Model We ﬁrst observe that PO-Probability can be solved easily for the joint probability model.

Theorem 2 For the joint probability model, PO-Probability can be solved in polynomial time.

Proof: The probability that a given assignment p is PO is equivalent to the total probability weight of the preference proﬁles for which p is PO. This can be calculated as follows. For each preference proﬁle, we test (in polynomial time) whether p is PO. We then add the probabilities of those proﬁles for which p is PO. The sum of the probabilities is the probability that the assignment p is PO.

Corollary 1 For the joint probability model, Is PO-Probability Non-Zero and Is PO-Probability One can be solved in polynomial time.

What about Exists Certainly PO-Assignment? This problem is equivalent to checking whether the sets of PO assignments associated with each possible preference proﬁle have a non-empty intersection. We show that this problem is NPcomplete even when the probability distribution is over two linear preference proﬁles. We reduce from the NP-complete problem Serial Dictatorship Feasibility that is deﬁned as follows: check whether there exists a permutation of agents for which serial dictatorship gives a particular item o to a particular agent i [Saban and Sethuraman, 2015]. For linear preference proﬁles, the set of Pareto optimal allocations are characterized by those that can be achieved via some serial dictatorship. Thus it follows that the following problem is also NP-complete: check whether there exists a Pareto optimal allocation in which a speciﬁed agent i gets a speciﬁed item o.

Theorem 3 For the joint probability model, Exists Certainly PO-Assignment is NP-complete even when the probability distribution is over two linear preference proﬁles.

Proof: Exists Certainly PO-Assignment is in NP because it can be checked in polynomial time whether a given assignment is certainly PO or not (Theorem 2). To prove NP-hardness, we reduce from Serial Dictatorship Feasibility problem. Let (N, O, , i, o) be an instance of

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

this problem. We construct a joint probability over two preference proﬁles. One of the proﬁles is the same as . In the other preference proﬁle , agent i has o as the most preferred item and has the same order of preference over all other items as in i. Each agent j N \ {i}, on the other hand, has o as the least preferred item and has the same order of preference over all other items as in j. Our ﬁrst observation is that an assignment is PO under proﬁle only if i receives o in it (Observation 1). We now prove that we have a yes instance of Serial Dictatorship Feasibility if and only if our constructed joint probability instance admits a certainly PO assignment. Since Serial Dictatorship Feasibility is NP-complete, this will entail that Exists Certainly PO-Assignment is NP-complete.

Assume that there exists a certainly PO assignment p. Then, p must be PO under implying that, by Observation 1, i receives o in p. Assignment p must also be PO under proﬁle which implies that there exists an assignment (i.e. p) that is PO under proﬁle and in which i receives o. In light of Fact 2, this implies that there exists a serial dictatorship the outcome of which under proﬁle is p. Hence, we have a yes instance of Serial Dictatorship Feasibility.

Now consider the case when we have a yes instance of Serial Dictatorship Feasibility. This means that there is a permutation π under which i gets o when serial dictatorship is run. Let us call this assignment by p. Due to Fact 2, p is PO under preference proﬁle . So it only remains to show that p is PO under . Due to Fact 2, it is suﬃcient to prove that for proﬁle , there exists a corresponding permutation of agents under which the outcome of serial dictatorship is p. In fact, we show that S D(N, O, , π) = p. That is, the outcome of applying serial dictatorship with permutation π is p even if the preference proﬁle is instead of . This proof is by induction on the rounds of serial dictatorship and by showing that at the end of any given round, all agents whose turn has already come up are assigned the same items as in p. Detailed proof is removed due to shortage of space. Thus p is PO under both possibly realizable preference proﬁles.

Corollary 2 For the joint probability model, Assignment With Highest PO-Prob is NP-hard.

Proof: We show that an algorithm to solve Assignment With Highest PO-Prob can be used to solve the NP-complete problem Exists Certainly PO-Assignment with only a polynomial increase in the running time. An algorithm for Assignment With Highest PO-Prob can compute an assignment p with the highest probability of being PO. By Corollary 1, it can be checked in polynomial time whether p is PO with probability one or not. If p is PO with probability one, then we know that we have a yes instance of Exists Certainly PO-Assignment. Otherwise, we have a no instance of Exists Certainly PO-Assignment.

4 Lottery Model Recall that a given uncertainty model is independent if any uncertain preference proﬁle L under the model can be writ-

ten as a product of uncertain preferences La for all agents a, where all La s are independent. We ﬁrst deﬁne the certainly preferred relation certain i for agent i. We write b certain i c if and only if agent i prefers b over c with probability 1.

Theorem 4 For any independent uncertainty model, Is POProbability One can be solved in polynomial time.

Proof sketch: Given an assignment p, we create a trading cycle graph G with agents and items as vertices. Each item points to its owner agent and each agent i points to any item o such that p(i) certain i o. We show that p is PO with probability one if and only if G does not contain a cycle.

Since the lottery model is an independent uncertainty model, Theorem 4 applies to it. Next we prove that for the lottery uncertainty model, Is PO-Probability Non-Zero can be solved in polynomial time.

Theorem 5 For the lottery model, Is PO-Probability Non Zero can be solved in polynomial time.

Proof: Consider an assignment p for which we want to check whether it is PO with non-zero probability. We use the following algorithm that builds a permutation of agents π such that serial dictatorship produces p given π, if and only if p is PO with non-zero probability. To start with, we initialize the set of remaining items to O, the remaining agents to N, and the permutation of the agents π to an empty list. We then repeat the following procedure until no more items are left, or the procedure returns no.

Check if there exists some agent i such that p(i) is the most preferred available item of i in at least one of his preference lists.

If no such agent exists, return no. Otherwise, if such an i exists, give agent i item p(i), append i to the permutation π, remove i from the set of remaining agents, and remove p(i) from the set of available items. Let i denote the preference of agent i that has p(i) as the most preferred remaining item (if more than one of such preferences exists, select one arbitrarily).

It is easy to verify that if the algorithm returns π, then S D(N, O, , π) = p. It remains to show that if the algorithm returns no, then p is PO with zero probability. Consider the ﬁrst point in the algorithm where for no agent i we have p(i) as the most preferred available item of i in at least one of his preference lists. This means that no remaining agent gets his most preferred item (for any preference list) among the available items. Therefore, for each realization of the preference proﬁles, each of the remaining agents is interested in, and points to, another item held by another agent among the remaining agents. This implies the existence of a trading cycle for each realization of the preference proﬁles, where some remaining agents can exchange items among themselves to get a more preferred item than in p. Thus p is PO with probability zero.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

In contrast to the positive results above, the problem of checking whether there exists an assignment that is PO with probability one is NP-complete. The proof is very similar to the proof of Theorem 3 and is hence removed. Note that Theorem 3 does not directly imply the following claim and an independent argument, albeit similar one, is required.

Theorem 6 For the lottery model, Exists Certainly POAssignment is NP-complete.

Corollary 3 For the lottery model, Assignment With Highest PO-Prob is NP-hard.

We now turn to the problem of computing the probability that a given assignment is PO. We ﬁrst present a polynomialtime solution for a restricted setting, and then show that POProbability is #P-complete for the lottery model in general.

Theorem 7 For the lottery model, if the number of uncertain agents is constant, then PO-Probability is polynomial-time solvable.

Proof: Let p be a given assignment. Let constant k denote the number of uncertain agents, and let the maximum number of preferences for any uncertain agent be ℓ. Therefore, the maximum number of preference proﬁles that are realizable is ℓk which is still polynomial in the input since k = O(1). For each possible preference proﬁle , it is easy to compute the probability that occurs by simply computing the product of the probabilities of the preferences chosen for the uncertain agents. In this way, we can reduce PO-Probability for the lottery model to PO-Probability for the joint probability model which can be solved in polynomial time (Theorem 2).

Theorem 8 For the lottery model, PO-Probability is #Pcomplete, even when restricted to the case where each agent has at most two possible preferences.

Proof sketch: It is straightforward to show that POProbability is in #P. We show #P-hardness by reducing from the #P-complete problem Monotone-#2SAT that is deﬁned as follows: count the number of satisfying assignments for a 2CNF formula that contains no negation [Valiant, 1979]. Let ϕ be a monotone 2CNF formula with clauses c1, . . . , cm and variables x1, . . . , xn. We construct an instance of POProbability as follows. Consider agents 1, . . . , n and items o1, . . . , on, and take the assignment p where p(i) = oi. We construct the preferences of the agents as follows. Take an arbitrary agent i. Consider the set {j1, . . . , ju} of indices j such that the clause (xi xj) occurs in ϕ. (W.l.o.g. this set {j1, . . . , ju} is non-empty.) Suppose that j1 < j2 < < ju, in order to ﬁx an (arbitrary) order over these indices. With probability 1

2, agent i has oi at the top of his preference list, followed by the rest of the items in arbitrary order. With probability 1

2, agent i has the following preference: oj1 i i oju i oi i , where the remaining items appear in arbitrary order after oi. This way, the possible preference proﬁles correspond oneto-one to the possible truth assignments over x1, . . . , xn.

Namely, taking the preference oi i for agent i corresponds to setting xi to 1, and taking the other preference for agent i corresponds to setting xi to 0. Moreover, each possible preference proﬁle occurs with probability 1/2n. We show that the number of satisfying assignments for ϕ is equal to the number of preference proﬁles under which p is Pareto optimal. In particular, we can show that p is PO under a preference proﬁle if and only if the corresponding truth assignment T satisﬁes ϕ. The number of satisfying truth assignments of ϕ is then exactly equal to 2n times the probability that assignment p is Pareto optimal. Thus, PO-Probability is #P-hard, even when restricted to the case where each agent has at most two possible preferences.

We showed that when there are only a constant number of uncertain agents, we can compute the PO probability in polynomial time for the lottery model (Theorem 7). However, the order of the polynomial that upper bounds the running time of our proposed algorithm grows with the number of uncertain agents. In particular, when k is the number of uncertain agents, and ℓis the maximum number of possible preference lists for these uncertain agents, the running time of the algorithm outlined in the proof of Theorem 7 is Ω(ℓk). We improve on this result by showing that there exists a ﬁxedparameter tractable algorithm that computes the PO probability for the lottery model. That is, we provide an algorithm that runs in time f(k)nc for some computable function f and some ﬁxed constant c independent of k, where n denotes the input size. In other words, we show that the parameterized problem k-PO-Probability, where the parameter is the number of uncertain agents, is ﬁxed-parameter tractable for the lottery model.

Theorem 9 For the lottery model, k-PO-Probability can be solved in ﬁxed-parameter tractable time.

Proof: Take an arbitrary instance of the problem k-POProbability, consisting of agents 1, . . . , n, items o1, . . . , on, and an assignment σ. W.l.o.g. assume that the assignment gives each agent i item oi, and that the uncertain agents are agents 1, . . . , k. For each uncertain agent i, let i,1, . . . , i,ui denote the diﬀerent possible preferences for agent i. Additionally, assume w.l.o.g. that for each of the uncertain agents 1, . . . , k, each of the possible preferences for these agents occurs with probability ℓ/d where the numerator ℓcan vary between diﬀerent agents and diﬀerent possible preferences, but where the denominator d is common among all agents and all possible preferences. In other words, all probabilities mentioned in the instance are rational numbers that share a common denominator d. If this were not the case, we could straightforwardly transform the instance in polynomial time to an equivalent instance that does satisfy this property. Also, assume w.l.o.g. that σ admits no trading cycle that involves only certain agents. If this were the case, then σ is PO with probability zero, and we can ﬁlter out such trivial instances using the result of Theorem 5. We now show how to compute the probability that σ is PO in ﬁxed-parameter tractable time. Our computation will proceed in three stages:

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

(1) We construct a directed graph G with O(ku2k2) vertices, where the edges are weighted. Here u denotes the maximum number of possible preferences for any uncertain agent.

(2) We count the number of homomorphisms f of a directed path P2k+2 of length 2k + 2 to this graph G, where each homomorphism is counted multiple times according to (the product of) the weights on the edges in f(P2k+2). This can be done in polynomial time using an extension of a known algorithm [Flum and Grohe, 2004; 2006].

(3) We divide the weighted total number of homomorphisms of P2k+2 to G by the number dk to obtain the probability that the given assignment σ is PO.

We begin with stage (1), and we construct the weighted, directed graph G. Let Π = {o1, . . . , ok}2 be the set of all possible pairs (oi, o j) of items among o1, . . . , ok. We deﬁne the set V of vertices of G as follows. First, we deﬁne an auxiliary set V : V = {1, . . . , k + 1} {(i, i, j) | i [k], j [ui]}. Then, we deﬁne the set V of vertices as follows: V = {s, t} {(v , Π ) | v V , Π Π}. That is, the graph G has vertices s and t, and 2k2

copies of each element in V (one for each Π Π). Intuitively, the vertices s and t will act as source and target for each homomorphism of P2k+2 to G. The sets Π Π will be intuitively used to memorize the trading paths (i.e., paths in the trading cycle graph) that result from particular choices of the preference lists i,j chosen for the agents 1, . . . , k. That is, each (oi, oj) Π corresponds to a path from oi to oj in the directed graph with vertices o1, . . . , on where there is an edge from oi to oi if and only if agent i prefers item oi to item oi . We construct the set E of (weighted and directed) edges as follows.

We add an edge with weight 1 from s to (1, ).

For each i [k], j [ui], and Π Π, we add an edge from (i, Π ) to (i, i,j, Π ). This edge has weight ℓ, where the possible preference list i,j for agent i occurs with probability ℓ/d.

For each i [k], j [ui], and Π Π, we add an edge with weight 1 from (i, i, j, Π ) to the vertex (i + 1, Π ), where the set Π (with Π Π Π) consists of all pairs (oi , oi ) for which there is a path from oi to oi in the trading cycle graph, constructed using i,j and Π . To construct Π , consider the following graph GΠ , i,j. The vertices of this graph are o1, . . . , on. For each pair (oi , oi ) of vertices among ok+1, . . . , on, there is an edge from oi to oi if and only if agent j prefers item oi to item oi . Moreover, for each (oi , oi ) Π , we add an edge from oi to oi . Finally, for each agent oi among ok+1, . . . , on, we add an edge from oi to oi if and only if oi i,j oi. We then let Π Π be the set of all pairs (oi , oi ) such that there is a path from oi to oi in GΠ , i, j. Clearly, Π Π Π.

For each Π Π such that (oi, oi) < Π for all i [k], we add an edge with weight 1 from (k + 1, Π ) to t.

Using this construction, we can show that the choices 1,j1 , . . . , k, jk of preferences for the agents 1, . . . , k that make the

assignment Pareto optimal are in one-to-one correspondence with the homomorphisms f from P2k+2 to G. (Due to space reasons, we omit a formal proof of this claim.) We count each such homomorphism f in a weighted fashion as follows this is phase (2). Take a homomorphism f from P2k+2 to G. Its weight in the grand total is the product of the weights for each edge in f(P2k+2). The only edges in f(P2k+2) that have weight > 1 are edges from (i, Π ) to (i, i, j, Π ). Such an edge has weight ℓ, where the probability that i, j occurs is ℓ/d. Then, the total weighted sum of all homomorphisms is equal to p dk, where p is the probability that the given assignment is Pareto optimal. Therefore, in order to compute p, we only need to take the weighted sum of all homomorphisms, and divide it by dk this is phase (3). All that remains is to argue how we can compute the weighted sum of all homomorphisms f from P2k+2 to G in polynomial time. We can do this by extending a known polynomial-time algorithm to count the number of homomorphisms of a graph whose treewidth is bounded by a ﬁxed constant into another graph [Flum and Grohe, 2006, Theorem 14.7]. Since paths have treewidth 1, counting the number of homomorphisms from a path to another graph can be done in polynomial time using this algorithm. This algorithm uses a dynamic programming approach to count the number of homomorphisms. This dynamic programming technique can straightforwardly be extended to take into account the weights of the homomorphisms. (We omit a detailed description of the extended algorithm.) This concludes our description of the ﬁxed-parameter tractable algorithm that solves k-PO-Probability for the lottery model.

An additional interesting problem that one might consider is to decide, given two assignments, which one has a higher probability of being PO. We conjecture that this problem is PP-complete for the lottery model.

5 Conclusions

Computing Pareto optimal outcomes is an active line of research in economics and computer science. We see that as we move from deterministic preferences to uncertain preferences, the complexity of computing Pareto optimal outcomes jumps signiﬁcantly even though the input for problems we study may not be compact. The computational hardness results carry over to more complex models in which there may be more items than agents, agents may have capacities, and items may have copies. For future work, we have started looking into other uncertainty models of compact indiﬀerence and pairwise [Aziz et al., 2016a]. An orthogonal but equally interesting direction will be to consider other fairness, stability, or eﬃciency desiderata.

Acknowledgments

We are grateful to the anonymous IJCAI reviewers for their helpful comments. Haris Aziz is supported by a Julius Career Award. Ronald de Haan is supported by the Austrian Science Fund (FWF), projects P26200 and J4047.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

References [Abdulkadiro glu and S onmez, 1998] Atila Abdulkadiro glu and Tayfun S onmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689 701, 1998. [Abdulkadiro glu and S onmez, 1999] Atila Abdulkadiro glu and Tayfun S onmez. House allocation with existing tenants. Journal of Economic Theory, 88(2):233 260, 1999. [Abraham et al., 2005] David J. Abraham, Katar ına Cechl arov a, David F. Manlove, and Kurt Mehlhorn. Pareto optimality in house allocation problems. In Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC), volume 3341 of Lecture Notes in Computer Science (LNCS), pages 1163 1175, 2005. [Aziz and de Keijzer, 2012] Haris Aziz and Bart de Keijzer. Housing markets with indiﬀerences: a tale of two mechanisms. In Proceedings of the 26th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 1249 1255, 2012. [Aziz et al., 2015] Haris Aziz, Simon Mackenzie, Lirong Xia, and Chun Ye. Ex post eﬃciency of random assignments. In Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1639 1640, 2015. [Aziz et al., 2016a] Haris Aziz, P eter Bir o, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. Stable matching with uncertain linear preferences. In Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT), pages 195 206, 2016. [Aziz et al., 2016b] Haris Aziz, P eter Bir o, J erˆome Lang, Julien Lesca, and J erˆome Monnot. Optimal reallocation under additive and ordinal preferences. In Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 402 410, 2016. [Aziz et al., 2016c] Haris Aziz, J erˆome Lang, and J erˆome Monnot. Computing Pareto Optimal Committees. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 60 66, 2016. [Bogomolnaia and Moulin, 2001] Anna Bogomolnaia and Herv e Moulin. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295 328, 2001. [Brams and King, 2005] Steven J. Brams and Daniel L. King. Eﬃcient fair division: Help the worst oﬀor avoid envy? Rationality and Society, 17(4):387 421, 2005. [Drummond and Boutilier, 2014] Joanna Drummond and Craig Boutilier. Preference elicitation and interview minimization in stable matchings. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence (AAAI), pages 645 653. AAAI Press, 2014. [Erdil and Ergin, 2015] Aytek Erdil and Haluk Ergin. Twosided matching with indiﬀerences. June 2015. [Flum and Grohe, 2004] J org Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing, 33(4):892 922, 2004.

[Flum and Grohe, 2006] J org Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. Springer-Verlag, 2006. [G ardenfors, 1973] Peter G ardenfors. Assignment problem based on ordinal preferences. Management Science, 20:331 340, 1973. [Hazon et al., 2012] Noam Hazon, Yonatan Aumann, Sarit Kraus, and Michael Wooldridge. On the evaluation of election outcomes under uncertainty. Artiﬁcial Intelligence, 189:1 18, 2012. [Krysta et al., 2014] Piotr Krysta, David Manlove, Baharak Rastegari, and Jinshan Zhang. Size versus truthfulness in the house allocation problem. In Proceedings of the 15th ACM Conference on Economics and Computation (ACMEC), pages 453 470. ACM Press, 2014. [Manlove, 2013] David Manlove. Algorithmics of Matching Under Preferences. World Scientiﬁc Publishing Company, 2013. [Rastegari et al., 2013] Baharak Rastegari, Anne Condon, Nicole Immorlica, and Kevin Leyton-Brown. Two-sided matching with partial information. In Proceedings of the 14th ACM Conference on Electronic Commerce (ACMEC), pages 733 750. ACM Press, 2013. [Rastegari et al., 2014] Baharak Rastegari, Anne Condon, Nicole Immorlica, Robert Irving, and Kevin Leyton Brown. Reasoning about optimal stable matchings under partial information. In Proceedings of the 15th ACM Conference on Economics and Computation (ACM-EC), pages 431 448. ACM Press, 2014. [Saban and Sethuraman, 2013] Daniela Saban and Jay Sethuraman. House allocation with indiﬀerences: a generalization and a uniﬁed view. In Proceedings of the 14th ACM Conference on Electronic Commerce (ACM-EC), pages 803 820. ACM Press, 2013. [Saban and Sethuraman, 2015] Daniela Saban and Jay Sethuraman. The complexity of computing the random priority allocation matrix. Mathematics of Operations Research, 40(4):1005 1014, 2015. [Svensson, 1994] Lars-Gunnar Svensson. Queue allocation of indivisible goods. Social Choice and Welfare, 11:323 330, 1994. [Svensson, 1999] Lars-Gunnar Svensson. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16(4):557 567, 1999. [Valiant, 1979] Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410 421, 1979.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)