# pareto_optimal_allocation_under_compact_uncertain_preferences__8391caf2.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Pareto Optimal Allocation under Compact Uncertain Preferences

Haris Aziz UNSW Sydney and Data61 Sydney, Australia haziz@cse.unsw.edu.au

Peter Biro Hungarian Academy of Sciences Budapest, Hungary birop@econ.core.hu

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

Baharak Rastegari University of Southampton, UK b.rastegari@soton.ac.uk

The assignment problem is one of the most well-studied settings in multi-agent resource allocation. Aziz, de Haan, and Rastegari (2017) considered this problem with the additional feature that agents preferences involve uncertainty. In particular, they considered two uncertainty models neither of which is necessarily compact. In this paper, we focus on three uncertain preferences models whose size is polynomial in the number of agents and items. We consider several interesting computational questions with regard to Pareto optimal assignments. We also present some general characterization and algorithmic results that apply to large classes of uncertainty models.

1 Introduction Multi-agent resource allocation is a widely applicable topic within multi-agent systems. One of the most fundamental setting in this domain is the so called assignment problem: n agents express preferences over n items and these items are then allocated among the agents in a suitable manner (Abdulkadiroˇglu and S onmez 1999; Aziz et al. 2016b; Bogomolnaia and Moulin 2001; Cechl arov a et al. 2015; G ardenfors 1973; Svensson 1994; 1999). When making such an allocation, a social designer may consider several goals to identify a desirable allocation. One widely-used goal, that is considered by economists as the most fundamental requirement for any reasonable solution, is that the allocation should be Pareto optimal, i.e., there should not be another allocation in which each agent is weakly better off and at least one agent is strictly better off. Pareto optimality is easy to achieve in classical allocation settings via sequential allocation or other matching algorithms. However, the problem may become more challenging when there is some uncertainty in the agents preferences. Aziz, de Haan, and Rastegari (Aziz et al. 2017b) initiated a computational study of Pareto optimality under uncertain preferences. They discussed several reasons to consider uncertain preferences including lack of information or communication; cost of eliciting further information; a record of changing or mixed choices in the past, or the fact that the agents are in fact virtual or bidding agents who represent the composition of preferences of the real agents they represent. Another

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

possible reason for uncertain preferences could be that agents preferences over items may be based on several criteria, and that given each individual criterion they may have certain preferences over items, but they may not be perfectly clear on how much weight to assign to each criterion (Miyazaki and Okamoto 2017). Uncertainty in preferences has already been studied in voting (Dopazo and Mart ınez-C espedes 2017; Hazon et al. 2012) and stable matching (Aziz et al. 2016a; 2017a; Miyazaki and Okamoto 2017; Chen et al. 2018). Similarly, in auction theory, it is standard to examine Bayesian settings in which there is probability distribution over the types of the agents. In the context of Pareto optimal allocation, Aziz et al. (2017b) considered two uncertain preferences models that are not necessarily compact. In this paper, we signiﬁcantly extend their study by considering further compact and natural uncertain preferences models and examining their computational aspects. An uncertain preference model is compact if it can be represented in space polynomial in the number of agents and items. If an assignment is PO (Pareto optimal) with probability one, we will call it certainly PO. If it is PO with non-zero probability, we call it possibly PO. We consider the following compact uncertainty models:

Compact Indifference Model: Each agent reports a single weak preference list that allows for ties. Each complete linear order extension of this weak order is assumed to be equally likely.

Pairwise Model: Each agent reports independent pairwise probabilities over pairs of items. If i prefers item o over item o with probability p, then she prefers o over o with probability 1 p.

Ranking Model: Each agent reports probabilities for each item being in each rank. The input for each agent can be viewed as a bistochastic matrix, i.e, the sum of probabilities of items being in a given rank is 1, and the sum of

This can be viewed as a House Allocation problem with Ties (HRT), where any preference list obtained by breaking ties arbitrarily is possible, and all possible preferences have the same likelihood of being realized. Under a linear preference ordering, the most preferred item is ranked 1st, the second most preferred item is ranked 2nd, and so on, with the least preferred item being ranked nth.

probabilities of an item being in one of the n ranks is 1 as well.

A preference proﬁle speciﬁes preferences of each agent over items. Previous work (Aziz et al. 2017b) on Pareto optimal allocation had considered the following models: Lottery Model (for each agent, we are given a probability distribution over linear preferences) and Joint Probability Model (a probability distribution over linear preference proﬁles is speciﬁed). Note that, as opposed to the three compact models we consider, the Lottery and Joint Probability models representations can be exponentially large. We consider six problems proposed by Aziz et al. (2017b). The two most natural computational problems are:

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

ASSIGNMENTWITHHIGHESTPO-PROBABILITY: compute an assignment with the highest probability of being PO.

We consider simpler problems than PO-PROBABILITY:

ISPO-PROBABILITYNON-ZERO: for a given assignment, is the probability of being PO non-zero?

ISPO-PROBABILITYONE: for a given assignment, is the probability of being PO one? We also consider two problems connected to ASSIGNMENTWITHHIGHESTPO-PROBABILITY:

EXISTSCERTAINLYPO-ASSIGNMENT asks whether there exists an assignment that has probability one for being PO

EXISTSPOSSIBLYPO-ASSIGNMENT asks whether there exists an assignment that is PO with non-zero probability.

Note that the latter problem is trivial for all uncertainty models in which the induced certainly preferred relation is acyclic (Aziz et al. 2017b). An agent certainly prefers an item o to o if she prefers o to o with probability 1. 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. All the ﬁve uncertainty models except the joint probability model are independent.

Contributions In this paper, we signiﬁcantly extend the work initiated on Pareto optimal allocation under uncertain preferences in two ways: (i) we present several general insights and results that apply to large classes of uncertainty models, and (ii) we present a comprehensive set of results for three compact uncertainty models that have not been considered in the context of Pareto optimal allocation. Our technical results are summarized in Table 1. Note that our most interesting technical results are computational hardness results which therefore carry over to any settings in which an agent may ﬁnd certain items unacceptable and/or an agent may be genuinely indifferent between two or more items. Our algorithmic results for the compact indifference and pairwise models also extend to the setting in which agents are allowed to declare some items unacceptable, as well as the setting in which there are unequal number of items and agents.

To see this, note that the proof in Aziz et al 2017b (Theorem 1) and our proofs for Theorems 2 and 3 go through without any change for these two generalizations. Extending the ranking model to capture either of these two generalizations is, on the other hand, not straightforward. This is because we heavily use the assumption that the uncertainty matrix is bistochastic when deﬁning various concepts for the ranking model.

Compact Pairwise Ranking Problems indifference Probability

PO-PROBABILITY #P-complete #P-complete #P-complete

ISPO-PROBABILITYNON-ZERO in P in P in P ISPO-PROBABILITYONE in P in P in P

EXISTSPOSSIBLYPO-ASSIGNMENT in P NP-complete in P (always exists) (always exists)

EXISTSCERTAINLYPO-ASSIGNMENT NP-complete NP-complete NP-complete

ASSIGNMENTWITHHIGHESTPO-PROB NP-hard NP-hard NP-hard

Table 1: Summary of results.

Discussion of the Models The compact indifference model explains scenarios where an agent may express indifference between some items because she does not have sufﬁcient knowledge about their differences. The model is neutral to the relative ordering of these items and assumes that all linear orders consistent with the weak preferences are equiprobable. The model was considered by Aziz et al. (2016a) in the context of the two-sided marriage problem and with stability as the main concern. Although the model is quite restrictive, our hardness results for the model underline the fact that even uncertainty in restrictive models can lead to intractability. The pairwise uncertainty model is well-studied in social sciences, in particular psychology, where people are asked to make repeated pairwise comparisons between different items or experiences. The model was formally studied in a related but different setting of the two-sided marriage problem (Aziz et al. 2017a), where the focus was on stability rather than Pareto optimality. The model is applicable to scenarios where the system has a record of similar pairwise choices and uses that record to ﬁnd an outcome that has a high probability of being Pareto optimal. The ranking model appeals to the idea that agents often ascribe ranks to items but they may not always be sure about the exact rank of each item (see e.g., Dopazo and Mart ınez C espedes 2017; Mazurek 2017). This notable approach to fuzzy rankings is applicable to scenarios where the system has a record of past ranking information and uses that fuzzy or aggregate record to ﬁnd an outcome that has a high probability of being Pareto optimal. Any compact indifference preference proﬁle can be represented by a lottery preference proﬁle albeit with possibly an exponential blowup. In Section 6 we will discuss how the ranking model has connections with the lottery model. In both the compact indifference model and the ranking model, we assume that the underlying preferences of agents are linear orders. Hence the certainly preferred part of the relation is acyclic under these two models. In the pairwise probability model, however, we do not assume that comparisons are transitive and even allow agents to have cycles

in their certainly preferred relations. Cyclic and intransitive preferences may happen in practice, e.g., when an agent is a virtual agent representing the preferences of a group of agents or a committee, or when agents valuation functions over alternatives are complex and multidimensional.

2 Preliminaries

An instance of the (deterministic) assignment problem is a triple (N, O, ) where N is the set of n agents {1, . . . , n}, O = {o1, . . . , on} is the set of items, and the preference proﬁle = ( 1, . . . , n) speciﬁes complete and asymmetric preferences i of each agent i over O. In the classical assignment problem, agents preferences are also assumed to be transitive, hence resulting in linearly ordered preferences. Let S denote the preference proﬁle of agents in the set S N. An assignment is an allocation of items to agents such that each agent is allocated a unique item. We will represent assignments by a permutation over O so that an item in the i-th position in the permutation is given to agent i. For example, We refer by abc the assignment in which agent 1 gets a, agent 2 gets b and agent 3 gets c. For a given assignment ω, let ω(i) denote the item allocated to agent i. An assignment ω is PO (Pareto optimal) if there exists no other assignment µ such that µ(j) j ω(j) for some agent j and µ(i) = ω(i) or µ(i) i ω(i) for all agents i. If such an assignment µ exists, then we say that µ Pareto dominates ω. In this work, we allow agents to express uncertainty in their preferences and consider three uncertainty models. For each agent i we deﬁne the certainly preferred relation cert i . We write b cert i c if and only if agent i prefers b over c with probability 1. Checking b cert i c is straightforward in the pairwise and compact indifference model. We will show in Section 6 that for the ranking model it can be checked in polynomial time whether b cert i c. An agent i possibly prefers an item b to item c if and only if i prefers b over c with nonzero probability. Given an agent i, a subset of items O O, and an item a O , we say that a is a possibly most preferred item for i among the items in O if there is a deterministic preference compatible with the uncertain preferences in which a is certainly preferred over other items in O . Checking whether a is a possibly most preferred item in O is straightforward in the pairwise and compact indifference model. We will show in Section 6 that this problem can be solved in polynomial time for the ranking model as well.

3 General Results

We ﬁrst note a well-known characterizations of PO assignments in deterministic settings. For any assignment ω, the corresponding trading graph is a graph on vertex set N O, in which each item points to its owner and each agent points to items more preferred that her allocated item. The assignment ω admits a (trading) cycle o0, i0, o1, i1, . . . , ok 1, ik 1, o0 if for all j {0, . . . , k 1} we have that oj = ω(ij) and oj+1 mod k ij oj. The following fact is well-known: an assignment is PO if and only if its corresponding trading graph does not admit a cycle (Abraham et al. 2004).

The trading cycle approach described above can be extended in two different ways when considering uncertain preferences: (1) each agent can point to items that are certainly more preferred to her current item, or (2) each agent can point to items that are possibly more preferred to her current item. Note that computing the certainly preferred relation directly gives us the possibly preferred relation. Aziz et al. (2017b) used approach (2) and characterized certainly PO assignments as those whose trading graph corresponding to possibly preferred part of the relation does not admit a cycle. They then used the characterization to prove the following theorem.

Theorem 1 (Aziz et al. (2017b)) For any independent uncertainty model in which the certainly preferred relation can be derived in polynomial time, ISPO-PROBABILITYONE can be solved in polynomial time.

All the three compact models we consider are independent and, as remarked in Section 2, the certainly preferred relation can be derived in polynomial time in all three of them. Therefore, as a corollary, we get the following statement.

Corollary 1 For the compact indifference, pairwise, and the ranking uncertainty models, ISPO-PROBABILITYONE can be solved in polynomial time.

Analogous to the characterization of certainly PO assignments (Aziz et al. 2017b), one may presume that an assignment is possibly PO if and only if the trading graph corresponding to certainly preferred part of the relation does not admit a cycle. However, it can be shown that the latter condition is necessary but not sufﬁcient for possible Pareto optimality. Next, we present a characterization of possibly PO assignments. We do this by ﬁrst presenting a classic characterization of PO assignments for deterministic and linear preferences (Abdulkadiroˇglu and S onmez 1998) that is deﬁned with respect to the outcomes of serial dictatorship. Serial Dictatorship (SD) is an assignment mechanism that is speciﬁed with respect to a permutation π over N: each agent is considered in the order stipulated by the permutation, and is allocated the item she most prefers among those that have 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 1 (Abdulkadiroˇglu and S onmez (1998)) An assignment is PO if and only if it is an outcome of serial dictatorship.

In the literature, SD is deﬁned for linearly ordered preferences. We noted earlier that under pairwise preferences, we allow agents to have cycles in their preferences; e.g., an agent may certainly prefer b to c, c to d, and d to b. There is nothing to prevent one from running SD on deterministic pairwise preferences. However, when an agent s turn arrives she may not ﬁnd an item she most prefers, due to the existence of a cycle, in which case SD must abort without any solution. It is thus easy to see that the if direction of Fact 1 applies

to pairwise preferences as well. We can show that the other direction too applies, though this is not immediately obvious. We present the following general theorem that applies to any uncertainty model and is a general characterization of possibly PO assignments. This theorem is an immediate consequence of Fact 1 if all realizable deterministic preferences are linear. We are providing a detailed proof to cover the case in which cycles may be present in deterministic preferences. Thus the theorem implies that Fact 1 applies to any deterministic, including pairwise, preferences.

Theorem 2 For any uncertainty model, an assignment ω is possibly PO if and only if there is some permutation π and some preference proﬁle that has non-zero probability under which when serial dictatorship is applied with respect to π, each agent in her turn gets item ω(i).

Proof: ( =) Follows from the if direction of Fact 1 that applies to any deterministic preferences. If for some deterministic preference proﬁle that has non-zero probability we have that ω = SD(N, O, , π), then ω is possibly PO. (= ) Since ω is possibly PO, it is PO with respect to some realizable deterministic proﬁle . We show that ω = SD(N, O, , π) for some permutation of agents π. Take any partial allocation ω ω that allocates to a subset of agents S N; that is, ω (i) = ω(i) for all i S. Denote the items that are allocated in ω by O . (Note that ω and hence S and O can be empty sets.) We claim that there exists some agent i N \ S such that, with respect to , ω(i) is the most preferred item of agent i among the set of items O \ O (note that, by the deﬁnition of ω and O , ω(i) is in O \ O ). Suppose for a contradiction that there exists no such an agent. Therefore, every agent j N \ S is interested in, and in the corresponding trading graph points to, an item (or more) that is held (according to ω) by another agent in N \ S. This implies the existence of a trading cycle where some agents in N \ S can exchange items among themselves to get a more preferred item than in ω, implying that ω is not PO with respect to the deterministic proﬁle , a contradiction. Therefore, we have established that starting with ω = , we can obtain ω by iteratively ﬁnding an agent who has not been allocated yet and, according to , has ω(i) as her most preferred item among the unallocated ones. Such an agent always exists as proved above. Let the order in which the agents are chosen be π. It is easy to verify that ω = SD(N, O, , π).

We call an uncertainty model reasonable if, for any subset of items O O and any agent i N, it can be checked in polynomial time whether o O is a possibly most preferred item for i among items in O . It is easy to verify that the lottery, compact indifference, and the pairwise models are all reasonable. Although it is not obvious, we will show in Section 6 that the ranking model is reasonable as well. Next, we present another general result that applies to a large class of uncertainty models.

Theorem 3 For any independent and reasonable uncertainty model, ISPO-PROBABILITYNON-ZERO can be solved in polynomial time.

Proof: Consider an assignment ω that we want to check whether it is possibly PO. We use the following algorithm that builds a permutation of agents π such that serial dictatorship produces ω given π, if and only if ω is possibly PO. 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 ω(i) is a possibly most preferred items for i amongst the available items. If no such agent exists, return no. Otherwise, if such an i exists, append i to the permutation π, remove i from the set of remaining agents, and remove ω(i) from the set of available items. Let i denote a preference of agent i that has ω(i) as the most preferred remaining item. It is easy to verify that if the algorithm returns π, then SD(N, O, , π) = ω. It can be shown that if the algorithm returns no, then ω is PO with zero probability. Consider the ﬁrst point in the algorithm where for no agent i we have ω(i) as a possibly most preferred available item for i. This means that no remaining agent gets her most preferred item (for any possible deterministic preferences) 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 ω. Thus ω is PO with probability zero.

We note that the theorem above generalizes Theorem 5 from (Aziz et al. 2017b) that only applies to the lottery model. It also gives us the following corollary.

Corollary 2 For the compact indifference, pairwise, and the ranking uncertainty models, ISPO-PROBABILITYNONZERO can be solved in polynomial time.

4 Compact Indifference Model Any compact indifference preference proﬁle admits a possibly PO assignment that can be computed as follows: break the ties arbitrarily and then run SD. What about the existence of certainly PO assignments? Although the compact indifference model is one of the most restricted and structured uncertainty models we consider, EXISTCERTAINLYPOASSIGNMENT is NP-complete for this model. To prove this, and several other claims in the paper, we reduce from the NP-complete problem SERIALDICTATORSHIPFEASIBILITY (Saban and Sethuraman 2015) that is deﬁned as follows: given an instance of the assignment problem (N, O, ), an agent i and an item o O, does there exists a permutation of agents for which SD awards o to i?

Theorem 4 For the compact indifference uncertainty model, EXISTCERTAINLYPO-ASSIGNMENT is NP-complete.

Proof: EXISTSCERTAINLYPO-ASSIGNMENT is in NP because it can be checked in polynomial time whether a given assignment is certainly PO or not (Theorem 1).

To prove NP-hardness, we reduce from SERIALDICTATORSHIPFEASIBILITY. Let (N, O, , i, o) be an instance of this problem with n agents and n items. W.l.o.g., suppose that i = 1. We construct an instance (N , O , ) of the compact indifference uncertainty model as follows. Let o , o be fresh items not appearing in O, let O = O {o , o }, and let N = N {1 , n + 1}. Let O1, o denote the set of items that agent 1 prefers over item o with respect to 1 i.e., those items oℓsuch that oℓ 1 o. Moreover, let O1, o denote the set of items that agent 1 likes less than item o i.e., O1, o = O \ ({o} O1, o). Also, for each 1 < j n, let j1, . . . , jn be the indices of items such that oj1 j j ojn. We deﬁne the preferences of the agents in N over the items in O as follows, where items in round brackets are tied.

Agent 1: (O1, o {o }) 1 o 1 (O1, o {o }). Agent 1 : (O1, o {o }) 1 o 1 (O1, o {o }). Agents 1 < j n: oj1 j j ojn j (o , o ) Agent n + 1: (O ).

We claim that there is a permutation π of the agents in N under which agent i = 1 gets item o when serial dictatorship is run on (N, O, ) if and only if there is an assignment that is certainly PO for (N , O , ).

Corollary 3 For the compact indifference uncertainty model, ASSIGNMENTWITHHIGHESTPO-PROB is NP-hard.

Theorem 5 For the compact indifference uncertainty model, PO-PROBABILITY is #P-complete.

Proof: It is straightforward to show that PO-PROBABILITY is in #P. We show #P-hardness by reducing from the #Pcomplete 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 PO-PROBABILITY as follows. Consider agents 1, . . . , 2n, and items o1, . . . , o2n and take the assignment ω where ω(i) = oi for all 1 i 2n. Agents preferences are constructed as follows. Take an arbitrary 1 i n. Consider the set {j1, . . . , ju} of indices j such that the clause (xi xj) occurs in ϕ. Suppose that j1 < j2 < < ju, in order to ﬁx an (arbitrary) order over these indices. Then agent i has the following preference: (on+i, oi) i , where the remaining items appear in arbitrary order. Moreover, agent n + i has the following preference: oj1 n+i n+i oju n+i on+i n+i , where the remaining items appear in arbitrary order. Note that agents n + 1, . . . , 2n have certain preferences. The instantiations of linear preferences to uncertain agents 1, . . . , n correspond one-to-one to truth assignments to variables x1, . . . , xn: for each 1 i n, setting the preference of agent i to oi i on+i i corresponds to setting xi to true, and setting agent i s preference to on+i i oi i corresponds to setting xi to false.

We show that a truth assignment α to the variables x1, . . . , xn satisﬁes ϕ if and only if the corresponding proﬁle of linear preferences for the agents 1, . . . , 2n leads the assignment ω to be PO. ( ) Suppose that α satisﬁes ϕ. We show that the assignment ω admits no trading cycle under the proﬁle corresponding to α. Suppose, to derive a contradiction, that ω admits a trading cycle. By construction of the preferences of the agents, any trading cycle must involve the sequence oi, i, on+i, n + i, oj, j, on+j, n + j . That is, agent i must prefer on+i over oi, agent j must prefer on+j over oj, and agent n + i must prefer oj over on+i. The former two statements are the case if and only if α sets both xi and xj to false. The latter statement is the case if and only if (xi xj) is a clause of ϕ. This is a contradiction to our assumption that α satisﬁes ϕ. Thus, we can conclude that ω is PO under the proﬁle corresponding to α. ( ) Conversely, suppose that α does not satisfy ϕ. That is, there is a clause (xi xj) of ϕ such that α sets both xi and xj to false. We show that the assignment ω admits a trading cycle under the proﬁle corresponding to α. Since α sets xi and xj to false, we know that on+i i oi and on+j j oj. Moreover, since (xi xj) is a clause of ϕ, we know that oj n+i on+i and oi n+j on+j. Thus, oi, i, on+i, n + i, oj, j, on+j, n + j is a trading cycle under this preference proﬁle, and hence ω is not PO. Each possible preference proﬁle occurs with probability 2 n. The number of satisfying truth assignments ϕ is then exactly equal to 2n times the probability that assignment ω is PO. Thus, PO-PROBABILITY is #P-hard.

5 Pairwise Model A possibly PO assignment exists for the pairwise model, if the certainly preferred relation of each agent is acyclic: one can derive a possible linear order consistent with the certainly preferred relation and then run serial dictatorship. In the presence of cycles, however, there is no guarantee that an instance admits a possibly PO assignment.

Theorem 6 Under the pairwise uncertainty model, if the certainly preferred relation is cyclic, then there may not exist a possibly PO assignment.

Proof: We prove this by showing that the following example with three agents and three items does not admit a possibly PO assignment. The pairwise preferences for the agents 1, 2 and 3 over the items a, b and c are as depicted. All the three agents have the same certainly preferred relations.

1 : a cert 1 c, c cert 1 b, b cert 1 a

2 : a cert 2 c, c cert 2 b, b cert 2 a

3 : a cert 3 c, c cert 3 b, b cert 3 a

Take assignment abc. It is not PO because it is Pareto dominated by bca. By symmetry no other assignment is PO as well.

We next show, with an argument similar to that of the proof of Theorem 3 in (Aziz et al. 2017b), that the problem

of checking whether a PO assignment exists is NP-complete under pairwise preferences even in the absence of uncertainty.

Theorem 7 Given an instance of the assignment problem with deterministic pairwise preferences, the problem of deciding if a PO assignment exists is NP-complete.

Proof: Under deterministic preferences, possibly PO and certainly PO coincide. The problem is in NP because it can be checked in polynomial time whether a given assignment is certainly PO (Corollary 1). To prove NP-hardness we reduce from SERIALDICTATORSHIPFEASIBILITY. Let (N, O, , i, o) be an instance of this problem with n agents and n items. We construct an instance (N , O , ) of deterministic pairwise preferences as follows. Let o , o be fresh items not appearing in O, let O = O {o , o }, and let N = N {n + 1, n + 2}. Intuitively, the (linear) preference cert i is obtained from i by replacing o with o o o . The preference cert j for each j N \ {i} is obtained from j by replacing o with the cycle o o o o. Finally, the preferences cert n+1 and cert n+2 are constructed by having the cycle o o o o on the top, followed by the items in O \ {o} (in arbitrary order). Formally:

For agent i:

For each pair of items o1, o2 such that o {o1, o2}, let o1 cert i o2 if and only if o1 i o2. Let o cert i o , o cert i o and o cert i o . For each item o1 O \ {o}, let o1 cert i o, o1 cert i o , and o1 cert i o if and only if o1 i o. For each item o1 O \ {o}, let o cert i o1, o cert i o1, and o cert i o1 if and only if o i o1. For each agent j N \ {i}:

For each pair of items o1, o2 such that o {o1, o2}, let o1 cert j o2 if and only if o1 j o2.

Let o cert j o , o cert j o and o cert j o.

For each item o1 O \ {o}, let o1 cert j o, o1 cert j o , and o1 cert j o if and only if o1 j o.

For each item o1 O \ {o}, let o cert j o1, o cert j o1, and o cert j o1 if and only if o j o1.

For both agents j {n + 1, n + 2}:

For each pair of items oℓ, oℓ O \{o}, let oℓ cert j oℓ if and only if ℓ> ℓ . For each item oℓ O \ {o}, let o cert j oℓ, o cert j oℓ, and o cert j oℓ.

Let o cert j o , o cert j o and o cert j o.

We claim that there is a permutation π under which agent i gets item o when serial dictatorship is run on (N, O, ) if and only if there is an assignment that is PO for (N , O , ). ( ) Suppose that there is a permutation π under which agent i gets item o when serial dictatorship is run on (N, O, ) (resulting in assignment ω). Construct the permutation π for agents N obtained from π by placing

the agents n + 1, n + 2 directly after agent i. Then Gen SD(N , O , cert, π ) returns the assignment p = p {n + 1 7 o , n + 2 7 o }. This assignment p is PO. ( ) Suppose that there is an assignment p for (N , O , cert) that is PO. By Theorem 2, we know that there exists a permutation π of the agents in N such that executing Gen-SD with this permutation on (N , O , cert) yields p . Let π = (π0, i, π1), i.e., π0 is the sequence of agents appearing in π before agent i, and π1 is the sequence of agents appearing in π after agent i. By construction of cert, we know that o is picked before o and o , because o and o are dominated in every preference order whenever o has not yet been picked. Moreover, we know that agent i must pick item o, because whenever o, o , o have not yet been picked, item o is dominated in every preference order except agent i s. Thus, after the agents in π0 have picked the unique undominated remaining item in their preference order, all items that agent i prefers to item o (in i) have been picked. Note that agents n + 1 and n + 2 are not in π0 since, as long as item o is not picked, both of these agents are confused. Thus, (π0, i) can be extended (by appending the rest of agents in N in arbitrary order) to a permutation π under which agent i gets item o when serial dictatorship is run on (N, O, ) with π .

Since possibly PO and certainly PO assignments coincide with PO assignments for deterministic pairwise preferences, we get the following corollary.

Corollary 4 For the pairwise uncertainty model, EXISTSPOSSIBLYPO-ASSIGNMENT and EXISTSCERTAINLYPOASSIGNMENT are NP-complete even if pairwise preferences are all deterministic.

The proof of Theorem 7 exploits the fact that certainly preferred relations can be cyclic under the pairwise uncertainty model. What if we disallow cycles in certainly preferred relations? Our next result shows that checking whether a certainly PO assignment exists is NP-complete for instances of pairwise uncertainty model, even if the certainly preferred part of the preferences is acyclic.

Theorem 8 For the pairwise uncertainty model, EXISTSCERTAINLYPO-ASSIGNMENT is NP-complete even if the certainly preferred part of the preferences is acyclic.

As a corollary, for the pairwise model, ASSIGNMENTWITHHIGHESTPO-PROB is NP-hard even if the certainly preferred part of the preferences is acyclic.

Theorem 9 For the pairwise uncertainty model, POPROBABILITY is #P-complete.

Proof: It is straightforward to show that PO-PROBABILITY is in #P. Hardness for #P can be shown by following the reduction used in the proof of Theorem 5. In this reduction, each agent either has a certain linear preference, or a preference where they are indifferent between their two most preferred items (and have a certain linear preference over all other items). These preferences can straightforwardly be

expressed in the pairwise model, hence PO-PROBABILITY is #P-hard under this model as well.

6 Ranking Model In the ranking model, each agent i reports a bistochastic matrix Mi of size n n. The rows of the matrix correspond to indices of items and the columns to the rank of the items. Note that if the matrix is a permutation matrix (with only 0-1 entries), then the ranking model degenerates to a linear preference. We say that a permutation matrix P is consistent with a bistochastic matrix Q if for each Pij = 1, we have that Qij > 0. We say that a linear preference i is consistent with a ranking preference if the permutation matrix representing i is consistent with the ranking preference matrix. For any ranking preference matrix Mi for agent i, we will also consider a corresponding consistency graph which is a bipartite graph (O R, E) where R = {1, . . . , n} is the set of possible ranks and (o, r) E if i expresses non-zero probability for o to be in rank r. By Birkhoff s theorem (Lov asz and Plummer 2009), any bistochastic matrix can be represented as a convex combination of at most quadratic number of permutation matrices. Hence, a ranking preference proﬁle can always be represented as a lottery preference proﬁle. This representation is not necessarily unique; that is, a ranking preference proﬁle may have several or possibly even exponentially many lottery preference proﬁle representation. Due to this reason, it is not clear whether the PO probability of a matching is well-deﬁned under the ranking model. In view of this we clarify the deﬁnitions of possibly PO and certainly PO that we are using for the ranking model. We say that an assignment is certainly PO under the ranking model if it is certainly PO for all lottery preference proﬁles that represent the ranking preference proﬁle. Likewise, we say that an assignment is possibly PO under the ranking model if it is possibly PO for some lottery preference proﬁle that represents the ranking preference proﬁle. Next, we argue that Corollaries 1 and 2 regarding ISPO-PROBABILITYONE and ISPO-PROBABILITYNONZERO hold under the ranking model by showing that possibly preferred (and hence certainly preferred ) and possibly most preferred item in a set can be checked in polynomial time. Given a ranking preference proﬁle , we say that b cert i c if b i c in each linear preference proﬁle that is in the support of some lottery preference proﬁle that represents . Note that a linear preference is in the support of some lottery preference that represents a ranking preference if and only if the linear preference is consistent with the ranking preference. The negation of b cert i c holds if there exist j, k [n] such that j < k and there is a linear preference consistent with the ranking preferences in which b gets rank k and c gets rank j. The relation b cert i c can be tested by checking whether there exist j, k [n] such that j < k and the consistency graph corresponding to the ranking preferences admits a perfect matching in which (b, k) and (c, j) are part of the matching. Given a ranking preference proﬁle , we say that a is a possibly most preferred item of agent i among a set of items O , if there is a linear preference consistent with in which a is the most preferred item in set O . The latter can be checked

in polynomial time as follows. For each possible rank j for item a, we construct a corresponding graph Gj = (O R, E) which is derived from the consistency graph by removing all edges involving a except (a, j), as well as removing all edges (o , k) where o O \ {a} and k j. Then a is a possibly most preferred item of i in O if and only if there exists a perfect matching for some Gj. Any ranking preference proﬁle admits a possibly PO assignment that can be computed by ﬁnding a linear preference proﬁle consistent with the ranking preference proﬁle and then running serial dictatorship.

Theorem 10 For the ranking uncertainty model, a possibly PO assignment always exists and can be computed in polynomial time.

On the other hand, just like the pairwise and the compact indifference models, EXISTSCERTAINLYPO-ASSIGNMENT is NP-complete under the ranking model. The proof is an adaptation of a result by Aziz et al. (2017b, Theorem 6).

Theorem 11 For the ranking uncertainty model, EXISTSCERTAINLYPO-ASSIGNMENT is NP-complete.

Next we show that PO-PROBABILITY is #P-complete for instances for which PO probability is well deﬁned due to the existence of a unique lottery model representation.

Theorem 12 For the ranking uncertainty model, POPROBABILITY is #P-complete.

Proof: It is straightforward to show that PO-PROBABILITY is in #P. Hardness for #P can be shown by using the reduction used in the proof of Theorem 5. In this reduction, each agents either has a certain linear preference, or a preference where they are indifferent between their two most preferred items (and have a certain linear preference over all other items). These preferences can straightforwardly be expressed in the ranking model. Thus, for the ranking model, PO-PROBABILITY is #P-hard as well.

7 Conclusions

We presented some general characterization and algorithmic results that apply to large classes of uncertainty models. We then extended the study to three uncertainty models that are especially compact (at most polynomial in the number of agents and items). For the pairwise model, it will be interesting to see if hardness results still hold if we impose stronger types of stochastic transitivity properties (Fishburn 1973). Another interesting direction is considering ex ante Pareto optimality with respect to plausible utility functions (Aziz et al. 2015). We observe that most of our computational results are similar for the three compact models we consider. One interesting contrast is that EXISTSPOSSIBLYPO-ASSIGNMENT is polynomial-time solvable for the Compact Indifference model and the Ranking model whereas it is NP-complete for the Pairwise model.

Acknowledgments

We are grateful to the anonymous reviewers for their helpful comments. Haris Aziz is supported by a Scientia Fellowship. P eter Bir o is supported by the Hungarian Academy of Sciences under its Momentum Programme (LP2016-3/2018) and Cooperation of Excellences Grant (KEP-6/2018), and by the Hungarian Scientiﬁc Research Fund OTKA (no. K129086). Ronald de Haan is supported by the Austrian Science Fund (FWF), project J4047.

Abdulkadiroˇglu, A.; and S onmez, T. 1998. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, 66(3):689 701. Abdulkadiroˇglu, A.; and S onmez, T. 1999. House allocation with existing tenants. Journal of Economic Theory, 88:233 260. Abraham, D. J.; Cechl arov a, K.; Manlove, D. F.; and Mehlhorn, K. 2004. Pareto optimality in house allocation problems. In Proceedings of ISAAC 04: the 15th Annual International Symposium on Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages 3 15. Springer. Aziz, H.; Brandl, F.; and Brandt, F. 2015. Universal Pareto dominance and welfare for plausible utility functions. Journal of Mathematical Economics, 60:123 133. Aziz, H.; Bir o, P.; Gaspers, S.; de Haan, R.; Mattei, N.; and Rastegari, B. 2016. Stable matching with uncertain linear preferences. In Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT), pages 195 206. Aziz, H.; Bir o, P.; Lang, J.; Lesca, J.; and Monnot, J. 2016. 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. Aziz, H.; Bir o, P.; Fleiner, T.; Gaspers, S.; de Haan, R.; Mattei, N.; and Rastegari, B. 2017. Stable matching with uncertain pairwise preferences. In Proceedings of the 16th Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 344 352. Aziz, H.; de Haan, R.; and Rastegari, B. 2017. Pareto optimal allocation under uncertain preferences. In Proceedings of the 26th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 1472 1474.

Bogomolnaia A.; and Moulin, H. 2001. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295 328.

Cechl arov a, K.; Eirinakis, P.; Fleiner, T.; Magos, D.; Manlove ,D. F. ; Mourtos, I.; Oceˇl akov a, E.; and Rastegari, B. 2015. Pareto optimal matchings in many-to-many markets with ties. In Proceedings of the 8th International Symposium on Algorithmic Game Theory (SAGT), Lecture Notes in Computer Science (LNCS), pages 27 39. Springer-Verlag. Chen, J.; Niedermeier, R.; and Skowron, P. 2018. Stable marriage with multi-modal preferences. In Proceedings of

the 19th Proceedings of the ACM Conference on Electronic Commerce (EC), pages 269 286. Dopazo, E.; and Mart ınez-C espedes, M. L. 2017. Rank aggregation methods dealing with ordinal uncertain preferences. Expert Systems with Applications, 78(C):103 109, July. Fishburn, P. C. 1973. Binary choice probabilities: on the varieties of stochastic transitivity. Journal of Mathematical Psychology, 10:327 352. G ardenfors, P. . 1973. Assignment problem based on ordinal preferences. Management Science, 20:331 340. Hazon, N.; Aumann, Y.; Kraus, S.; and Wooldridge, M. 2012 On the evaluation of election outcomes under uncertainty. Artiﬁcial Intelligence, 189:1 18.

Lov asz, L.; and Plummer, M. D. 2009. Matching Theory. AMS Chelsea Publishing. Mazurek, J. 2017. Fuzzy rankings: Properties and applications. Co RR, abs/1703.05201. Miyazaki, S.; and Okamoto, K. 2017. Jointly stable matchings. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1 56:12. Schloss Dagstuhl Leibniz-Zentrum fuer Informatik. Saban, D.; and Sethuraman, J. 2015. The complexity of computing the random priority allocation matrix. Mathematics of Operations Research, 40(4):1005 1014. Svensson, L.-G. 1994. Queue allocation of indivisible goods. Social Choice and Welfare, 11:323 330 Svensson, L.-G. 1999. Strategy-proof allocation of indivisible goods. Social Choice and Welfare, 16:557 567. Valiant, L. G. 1979. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410 421.