Pareto Optimal Allocation under Uncertain Preferences

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;

Ronald de Haan

University of Amsterdam Amsterdam, the Netherlands R.deHaan@uva.nl

Baharak Rastegari

University of Bristol Bristol, UK

baharak.rastegari@bristol.ac.uk

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 profiles � is specified.

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 profile specifies (deterministic) preferences of each agent over items.

• � AssignmentWithHighestPO-Probability: compute an assignment with the highest probability of being PO.

We also consider problems simpler than PO-Probability:

• � IsPO-ProbabilityNon-Zero: for a given assignment, is its probability of being PO non-zero?
• � IsPO-ProbabilityOne: for a given assignment, is its probability of being PO one?

We also consider a problem connected to AssignmentWithHighestPO-Probability: ExistsCertainlyPO-Assignment asks whether there exists an assignment that is PO with probability one. Note that ExistsPossiblyPO-Assignmentthe 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 profiles 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 profile 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 first study of computational aspects of Pareto optimal allocation under uncertain preferences. We show that for both the lottery model and the joint probability model, ExistsCertainlyPO-Assignment is NPcomplete. We also prove that AssignmentWithHighestPOProbability 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 significantly. On the other hand, we show that for a general class of independent uncertainty models, both problems IsPO-ProbabilityNonZero and IsPO-ProbabilityOne 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 fixed-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 f1; : : : ; ng, O = fo1; : : : ; ong is the set of n items, and �= (�1; : : : ; �n) is a preference profile that specifies complete, asymmetric, and transitive preferences �i of each agent i over O. We write o %i o 0 if o �i o 0 or o 0 = 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 profile of agents in the set S � N.

An assignment is an allocation of items to agents, represented as an n � n matrix [p(i)(o j)]1�i�n;1� j�n such that for all i 2 N, and oj 2 O, p(i)(oj) 2 f0; 1g; for all i 2 f1; : : : ; ng, P j2N p(i)(oj) = 1 ; and for all j 2 f1; : : : ; ng, P i2N 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 oj 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 2 N and q(i) �i p(i) for some i 2 N. If such an assignment q exists, then we say that q Pareto dominates p.

We first 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 ho0; i0; o1; i1; : : : ; ok�1; ik�1; o0i if for all j 2 f0; : : : ; k � 1g we have p(i j)(oj) = 1 and oj+1 mod k �i j oj. Intuitively, each agent i j in the trading cycle prefers the next item oj+1 (o0 if j = k � 1) to his assigned item oj. Thus, the existence of a trading cycle implies that there is a set of agents who all benefit 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 defined with respect to outcomes of serial dictatorship. Serial dictatorship is a straightforward greedy assignment mechanism that is specified 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 SD(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.

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 verified easily [Abraham et al., 2005]. In this paper we focus on finding 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 profiles.

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 verified by considering each of the two possible preference profiles, 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 first 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 hb; 1; a; 2; bi, 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 first 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 first 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 ProbabilityModel

We first 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 profiles for which p is PO. This can be calculated as follows. For each preference profile, we test (in polynomial time) whether p is PO. We then add the probabilities of those profiles 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, IsPO-ProbabilityNon-Zero and IsPO-ProbabilityOne can be solved in polynomial time.

What about ExistsCertainlyPO-Assignment? This problem is equivalent to checking whether the sets of PO assignments associated with each possible preference profile have a non-empty intersection. We show that this problem is NPcomplete even when the probability distribution is over two linear preference profiles.

We reduce from the NP-complete problem SerialDictatorshipFeasibility that is defined 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 profiles, 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 specified agent i gets a specified item o.

Theorem 3 For the joint probability model, ExistsCertainlyPO-Assignment is NP-complete even when the probability distribution is over two linear preference profiles.

Proof: ExistsCertainlyPO-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 SerialDictatorshipFeasibility problem. Let (N;O; �; i; o) be an instance of this problem. We construct a joint probability over two preference profiles. One of the profiles is the same as �. In the other preference profile � 0 , 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 2 N n fig, 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 first observation is that an assignment is PO under profile � 0 only if i receives o in it (Observation 1). We now prove that we have a yes instance of SerialDictatorshipFeasibility if and only if our constructed joint probability instance admits a certainly PO assignment. Since SerialDictatorshipFeasibility is NP-complete, this will entail that ExistsCertainlyPO-Assignment is NP-complete.

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

Now consider the case when we have a yes instance of SerialDictatorshipFeasibility. 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 profile �. So it only remains to show that p is PO under � 0 . Due to Fact 2, it is su�cient to prove that for profile � 0 , there exists a corresponding permutation of agents under which the outcome of serial dictatorship is p.

In fact, we show that SD(N;O; � 0 ; �) = p. That is, the outcome of applying serial dictatorship with permutation � is p even if the preference profile is � 0 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 profiles. �

Corollary 2 For the joint probability model, AssignmentWithHighestPO-Prob is NP-hard.

Proof: We show that an algorithm to solve AssignmentWithHighestPO-Prob can be used to solve the NP-complete problem ExistsCertainlyPO-Assignment with only a polynomial increase in the running time. An algorithm for AssignmentWithHighestPO-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 ExistsCertainlyPO-Assignment. Otherwise, we have a no instance of ExistsCertainlyPO-Assignment. �

4 LotteryModel

Recall that a given uncertainty model is independent if any uncertain preference profile L under the model can be written as a product of uncertain preferences La for all agents a, where all La's are independent.

We first define 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, IsPOProbabilityOne 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, IsPO-ProbabilityNon-Zero can be solved in polynomial time.

Theorem 5 For the lottery model, IsPO-ProbabilityNonZero 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 SD(N;O; �; �) = p. It remains to show that if the algorithm returns no, then p is PO with zero probability. Consider the first 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 profiles, 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 profiles, 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. �

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, ExistsCertainlyPOAssignment is NP-complete.

Corollary 3 For the lottery model, AssignmentWithHighestPO-Prob is NP-hard.

We now turn to the problem of computing the probability that a given assignment is PO. We first 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 profiles that are realizable is ' k which is still polynomial in the input since k = O(1). For each possible preference profile �, 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 defined 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 f j1; : : : ; jug of indices j such that the clause (xi _ xj) occurs in '. (W.l.o.g. this set f j1; : : : ; jug is non-empty.) Suppose that j1 < j2 < � � � < ju, in order to fix 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 profiles 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 profile occurs with probability 1=2 n .

We show that the number of satisfying assignments for ' is equal to the number of preference profiles under which p is Pareto optimal. In particular, we can show that p is PO under a preference profile if and only if the corresponding truth assignment T satisfies '.

The number of satisfying truth assignments of ' is then exactly equal to 2 n 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 fixedparameter tractable algorithm that computes the PO probability for the lottery model. That is, we provide an algorithm that runs in time f (k)n c for some computable function f and some fixed 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 fixed-parameter tractable for the lottery model.

Theorem 9 For the lottery model, k-PO-Probability can be solved in fixed-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 filter out such trivial instances using the result of Theorem 5.

We now show how to compute the probability that � is PO in fixed-parameter tractable time. Our computation will proceed in three stages:

1. We construct a directed graph G with O(ku2 k 2 ) 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 d k to obtain the probability that the given assignment � is PO.

We begin with stage (1), and we construct the weighted, directed graph G. Let � = fo1; : : : ; okg 2 be the set of all possible pairs (oi; o j) of items among o1; : : : ; ok. We define the set V of vertices of G as follows. First, we define an auxiliary set V 0 : V 0 = f1; : : : ; k + 1g [ f(i; �i; j) j i 2 [k]; j 2 [ui]g: Then, we define the set V of vertices as follows: V = fs; tg[f(v 0 ; � 0 ) j v 0 2 V 0 ; � 0 � �g: That is, the graph G has vertices s and t, and 2 k 2 copies of each element in V 0 (one for each � 0 � �). Intuitively, the vertices s and t will act as source and target for each homomorphism of P2k+2 to G.

The sets � 0 � � 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) 2 � 0 corresponds to a path from oi to oj in the directed graph with vertices o1; : : : ; on where there is an edge from oi 0 to oi 00 if and only if agent i 0 prefers item oi 00 to item oi 0 .

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 2 [k], j 2 [ui], and � 0 � �, we add an edge from (i; � 0 ) to (i; �i; j; � 0 ). This edge has weight ', where the possible preference list �i; j for agent i occurs with probability '=d.
• � For each i 2 [k], j 2 [ui], and � 0 � �, we add an edge
• with weight 1 from (i; �i; j; � 0 ) to the vertex (i + 1; � 00 ), where the set � 00 (with � 0 � � 00 � �) consists of all pairs (oi 0 ; oi 00 ) for which there is a path from oi 0 to oi 00 in the 'trading cycle graph,' constructed using �i; j and � 0 . To construct � 00 , consider the following graph G� 0 ;�i; j . The vertices of this graph are o1; : : : ; on. For each pair (oi 0 ; oi 00 ) of vertices among ok+1; : : : ; on, there is an edge from oi 0 to oi 00 if and only if agent j prefers item oi 00 to item oi 0 . Moreover, for each (oi 0 ; oi 00 ) 2 � 0 , we add an edge from oi 0 to oi 00 . Finally, for each agent oi 0 among ok+1; : : : ; on, we add an edge from oi to oi 0 if and only if oi 0 �i; j oi. We then let � 00 � � be the set of all pairs (oi 0 ; oi 00 ) such that there is a path from oi 0 to oi 00 in G� 0 ;�i; j . Clearly, � 0 � � 00 � �.
• � For each � 0 � � such that (oi; oi) < � 0 for all i 2 [k], we add an edge with weight 1 from (k + 1; � 0 ) 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; � 0 ) to (i; �i; j; � 0 ). 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 � d k , 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 d k -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 fixed 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 fixed-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 significantly 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.