Undecidability in Epistemic Planning

1 Introduction

Social choice theory is one of the main pillars of microeconomic theory which helps understand and devise methods to aggregate preferences of multiple agents. Although the field is sometimes viewed through a restricted lens of voting theory, social choice theory is broad enough to include various well-studied multi-agent settings including resource allocation, matchings, and coalition formation. The main setting in social choice concerns a set of alternatives A, a set of agents N, and each agent in N expresses preferences over A. Based on the preferences of the agents, an alternative is chosen according to some social choice function.

Two of the most fundamental criteria of social choice functions are Pareto e�ciency and strategyproofness. An outcome is Pareto e�cient if there is no other outcome that all agents weakly prefer the latter outcome and at least one agent strictly prefers. Strategyproofness captures the idea that no agent should have an incentive to misreport his preferences to get a more preferred outcome. Pareto optimality has been termed "the most important tool of normative economic analysis" [Moulin, 2003]. Similarly, seeking strategyproof mechanisms in di�erent domains is a long-standing project within microeconomics. In this regard, a central result is that no non-trivial deterministic resolute social choice function satisfying a weaker property than Pareto optimality is strategyproof [Gibbard, 1973; Satterthwaite, 1975]. Here, we use the standard notion of strategyproofness due to Gibbard, i.e., there are no vNM utilities consistent with an agent's preference profile such that when an agent misreports his preferences, he can increase his expected utility.

In this paper, we focus on randomized social choice functions - also called social decision schemes [see e.g., Gibbard, 1977; Barber`a, 1979b]. A social decision scheme (SDS) is a function which takes a preference profile and returns a lottery over A based on the preference profile. A probabilistic approach to social choice has various virtues. Randomization is one of the most common ways to regain ex ante fairness. Consider two agents having opposite preferences over two alternatives. Selecting an alternative with equal probability seems to be the fair course of action. SDSs are especially important when agents want to decide on sharing a divisible resource like time or space. In this case, the probability which an alternative gets from the lottery can be interpreted as the proportion of time or space the agents decide to allot to some alternative [Example 3.6, Moulin, 2003]. Social decision schemes have another motivation that the probability of each alternative can also be used as a suggestion for the proportional representation of the alternative in representative democracy or seat allocation of a parliament [Tullock, 1967]. Non-deterministic voting rules have been used in history, for example, in Ancient Greece and Renaissance Italy [see, e.g., Stone, 2011; Walsh and Xia, 2012]. SDSs are not only a topic of recent research in political science [see, e.g., Stone, 2011] but also in computer science [e.g., Conitzer and Sandholm, 2006; Procaccia, 2010]. In view of the negative strategyproofness results regarding deterministic social choice functions, it is also natural to consider social decision schemes.

In this paper, we propose a new social decision scheme called MR (Maximal Recursive) which satisfies a number of desirable properties pertaining to economic e�ciency, strategyproofness, and e�cient computability. The rule is based on using (generalized) plurality scores of the alternatives and the idea of inclusion minimal subsets to recursively adjust the probability weights of the alternatives. We will show that MR is an interesting generalization of the well-studied random dictatorship rule and has some favourable properties in comparison to RSD (random serial dictatorship) rule which is a well-known generalization of random dictatorship.

2 Seeking e�ciency and strategyproofness

For social decision schemes, ex post e�ciency is a minimal requirement of e�ciency in the sense that no Pareto dominated alternative gets non-zero probability. Gibbard [1977] proved that for social choice settings where agents express strict preferences over alternatives, there exist no ex post e�- cient and strategyproof decision schemes other than RD (random dictatorship). � In RD, an agent is chosen randomly as the dictator who then has the privilege to select his unique maximally preferred alternative. If one requires anonymity so that the rule does not depend on the names of the agents, then we obtain the unique RD which gives equal probability to each agent being the dictator. The resulting rule simply chooses an alternative in proportion to its plurality score. This rule has a number of merits. In political science, it is generally referred to as lottery voting [see e.g., Saunders, 2010; Stone, 2011]. The probability which each alternative achieves is proportional to the voting weight it gets in Tullock's method for representative democracy where alternatives are considered representatives of the voters [Potthof and Brams, 1998].

Although much of work in the voting literature assumes that agents have strict preferences over alternatives, it is natural to consider domains where agents may express indi�erences among alternatives. The indi�erence could be because an agent does not have enough information to decide which alternative is better or it could simply be the case that the agent values both alternatives equally. In fact, in many important domains of social choice such as resource allocation and matching, ties are unavoidable because agents are indifferent among all outcomes in which their allocation or match is the same [e.g., S¨onmez and ¨Unver, 2011; Bouveret and Lang, 2008]. If agents express indi�erences over (pure) alternatives, then RD needs to be reformulated so that ex post e�ciency is satisfied. In the literature there is a well-known generalization of RD called RSD (random serial dictatorship) for the domain with indi�erences. RSD uniformly randomizes over n! lotteries - one for each permutation � over N. A lottery for a particular � is computed as follows. Agent �(1) chooses the set of maximally preferred alternatives from A, �(2) chooses the maximally preferred alternatives from the refined set and so on so until a final subset of A is left. Then, the uniform lottery over the alternatives the final refined set is chosen as the lottery corresponding to a given permutation �. RSD is well-established in resource allocation and especially in the restricted domain of social choice called the assignment problem [see e.g., Svensson, 1994; Abdulkadiro˘glu and S¨onmez, 1998; Bogomolnaia and Moulin, 2001]. y For social choice settings with indi�erences, RSD is strategyproof in the Gibbard sense and it is also ex post e�cient.

� SDSs that assign probabilities to alternatives in proportion to their Borda or Copeland scores [see e.g., Barber`a, 1979a; Conitzer and Sandholm, 2006; Procaccia, 2010] are strategyproof but they are not ex post e�cient.

y In his original paper, Gibbard [1977] already gave a partial description of RSD in which a dictator chooses his maximally preferred alternatives and then his 'henchman' refined the set further. In the resource allocation literature, RSD is also referred to as RP (random priority) [see e.g., Bogomolnaia and Moulin, 2001]..

Despite the central position of RSD as the natural extension of RD to the general domain, RSD is not without some criticism. Critiques of RSD include e�ciency losses [Aziz et al., 2013b; Bogomolnaia and Moulin, 2001] and computational overhead. Although RSD is a well-established mechanism, Bogomolnaia and Moulin [2001] demonstrated that RSD suffers from unambiguous e�ciency losses even in the restricted social choice domain of assignment problems. In particular, it does not satisfy SD-e�ciency (stochastic dominance e�- ciency) - an e�ciency notion that is stronger than ex post e�ciency. Although RSD can be used e�ciently to randomly return a single alternative, it is computationally demanding to analyze since computing exactly the probability of an alternative being chosen requires enumerating jNj! permutations: no polynomial-time algorithm is known. In fact, recently, computing the lottery returned by RSD has been shown to be #Pcomplete to compute [Aziz et al., 2013a] which implies that there exists no polynomial-time algorithm unless a statement even stronger than P=NP holds. In light of these issues, we are motivated to find some other generalization of RD that is computationally e�cient to handle and fares better than RSD in terms of e�ciency. We present a new generalization of random dictatorship for indi�erences, namely the Maximal Recursive (MR) rule.

In order to analyze MR, we undertake a more nuanced investigation of social decision schemes by considering strategyproofness (abbreviated as SP) and e�ciency with respect to di�erent lottery extensions just like in [Aziz et al., 2013b; Cho, 2012]. A lottery extension specifies how preferences over alternatives are extended to preferences over lotteries. We consider three lottery extensions: SD (stochastic dominance), DL (downward lexicographic) and DL 1 (downward lexicographic one). All of these lottery extensions define relations on lotteries. One lottery stochastically dominates another if for all utility representations consistent with the ordinal preferences, the former yields as much utility as the latter [see, e.g., Cho, 2012]. As the name suggests DL is based on lexicographic comparisons. DL is a refinement of the SD lottery extension. DL is also a refinement of DL 1 -a lottery extension in which lotteries are compared only with respect to the probability assigned to the maximally preferred alternatives. DL 1 is a natural preference relation and models situations in which an agents wants to maximize the probability of his most preferred alternatives. Maximizing the probability of the most preferred alternative has been examined before [see e.g., Conitzer et al., 2007].

Our main contribution is proposing the Maximal Recursive (MR) Rule and showing that MR satisfies various desirable axiomatic properties. MR is computationally-e�cient, ex post e�cient and also DL 1 -e�cient. In fact for many instances, it returns an SD-e�cient lottery even though RSD returns a lottery that is not SD-e�cient. On the other hand, MR satisfies DL-strategyproofness-a weaker notion of strategyproofness than the one satisfied by RSD. MR applies to any setting in which agents have preferences over outcomes and these preferences need to be aggregated into a probability distribution over the outcomes. Our results are summarized in the following central theorem.

Theorem 1 MR is

• (i) single-valued, anonymous, neutral and monotonic;
• (ii) computable in polynomial time;
• (iii) equivalent to RD for strict preferences and hence both SD-SP and SD-e�cient for strict preferences;
• (iv) DL-SP (and hence weak SD-SP) but not SD-SP;
• (v) ex post e�cient and also DL 1 -e�cient;
• (vi) SD-SP and SD-e�cient for dichotomous preferences;
• (vii) SD-e�cient for some instances for which RSD is not SD-e�cient.

The statement is proved in a series of propositions. Before we proceed, the main concepts are defined and then MR is presented.

3 Preliminaries

Social choice and lotteries. Consider the social choice setting in which there is set of agents N = f1; : : : ; ng, a set of alternatives A = fa1; : : : ; amg and a preference profile R = (R1; : : : ; Rn) such that each Ri is a complete and transitive relation over A. We have a Ri b denote that agent i values alternative a at least as much as alternative b and write Pi for the strict part of Ri, that is, a Pi b if a Ri b but not b Ri a. Ii denotes i's indi�erence relation, that is, a Ii b if both a Ri b and b Ri a. Whenever all Ri are antisymmetric, we say that agents have strict preferences. For any S � A, we will denote by maxRi (S ) the alternatives in S that are maximally preferred by i. The relation Ri results in equivalence classes E 1 i ; E 2 i ; : : : ; E ki i for some ki such that a Pi a 0 for a 2 E l i and a 0 2 E l 0 i for l < l 0 . Often, we will use equivalent classes to represent the preference relation of an agent as a preference list

For example, we will denote the preference a Ii b Pi c by following list

An agent's preferences are dichotomous, if he partitions the alternatives into two equivalence classes E 1 i and E 2 i , i.e., ki = 2. An agent's preferences are strict if he is not indi�erent between any alternatives, i.e., ki = m.

Let �(A) denote the set of all lotteries (or probability distributions) over A. The support of a lottery p 2 �(A), denoted by supp(p), is the set of all alternatives to which p assigns a positive probability, i.e., supp(p) = fx 2 A j p(x) > 0g: We will represent a lottery in the following way

where pj is the probability of alternative aj for j 2 f1; : : : ;mg.

Lottery extensions. In order to reason about the outcomes of social decision schemes, we need to reason about how how agents compare lotteries. A lottery extension maps preferences over alternatives to (possibly incomplete) preferences over lotteries. Given Ri over A, one can extend Ri to R e i over

�(A) where R e i is a relation between lotteries based on lottery extension e. We now define particular lottery extensions including the standard extensions SD (stochastic dominance) and DL (downward lexicographic) [see e.g., Bogomolnaia and Moulin, 2001; Schulman and Vazirani, 2012; Abdulkadiro˘glu and S¨onmez, 2003; Cho, 2012]. We also consider an extension DL 1 which is coarser than DL. For a lottery p and A 0 � A, we will denote P a2A 0 p(a) by p(A 0 ). Consider two lotteries p; q 2 �(A). Then, the SD lottery extension is defined as follows.

Next we define the DL lottery extension. Let l 2 f1; : : : kig be the smallest integer such that p(E l i ) , q(E l i ). Then,

If there exists no integer l 2 f1; : : : kg such that p(E l i ) , q(E l i ) then p I DL i q.

Finally, we define the lottery extension DL 1 .

It is clear that p R SD i q =) p R DL i q i.e., DL is a refinement of SD. Also DL is a refinement of DL 1 .

To clarify the di�erences between the three lottery extensions, we provide the following example.

Example 2 For A = fa; b; c; dg, consider lotteries p and q over A: p = [a : 0:4; b : 0:1; c : 0:5; d : 0] and q = [a : 0:4; b : 0:3; c : 0; d : 0:3]: Then for an agent i with preferences a Pi b Pi c Pi d, his preferences between the lotteries p and q are as follows: q Pi DL p; p Ii DL 1 q; and :(p Pi SD q) and :(q Pi SD p).

E�ciency and strategyproofness based on lottery extensions. Based on a lottery extension, one can define an appropriate notion of e�ciency and strategyproofness. For a lottery extension e, lottery p is e-e�cient if there exists no lottery q such that q R e i p for all i 2 N and q P e i p for some i 2 N. An SDS which always returns an e-e�cient lottery is termed e-e�cient. A standard e�ciency notion that cannot be phrased in terms of lottery extensions is ex post e�ciency also known as Pareto-optimality. A lottery is ex post e�cient if it is a lottery over Pareto optimal alternatives.

Fact 2 DL-e�ciency =) SD-e�ciency =) ex post efficiency. Also SD-e�ciency =) weak SD-e�ciency, and DL-e�ciency =) DL 1 -e�ciency.

An SDS ' is weak e-SP if for every preference profile R, there exists no R 0 i for some agent i 2 N such that '(R 0 i ; R�i) P e i '(Ri; R�i). An SDS ' is e-SP if for every preference profile R, and every R 0 i for all i 2 N, '(Ri; R�i) R e i '(R 0 i ; R�i). For a complete lottery extension such as DL or DL 1 , SP and the weak notion of SP coincide. This is not the case for SD for which SD-SP is strictly stronger than weak SD-SP.

Note that SD-SP is equivalent to strategyproofness in the Gibbard sense.

We also present a formal definition of RSD. Let � N be the set of permutations over N and �(i) be the i-th agent in permutation � 2 � N . Then,

where

�uniform(B) is the uniform lottery over the given set B, and maxRi (A 0 ) is the set of alternatives in A 0 maximally preferred by agent i.

4 Maximal Recursive Rule

We now present the Maximal Recursive (MR) rule. MR relies on the concept of IMS (inclusion minimal subsets). For S � A, let A1; : : : ; Am 0 be subsets of S . Let I(A1; : : : ; Am 0 ) be the set of non-empty intersection of elements of some subset of fA1; : : : ; Am 0 g.

Then, the inclusion minimal subsets of S � A with respect to (A1; : : : ; Am 0 ) are defined as follows.

Example 3 Consider the sets A1 = fa; b; c; dg, A2 = fa; bg, A3 = fd; e; f g, A4 = f f g. Then, IMS (A1; : : : ; A4) = ffa; bg; fdg; f f gg:

Inclusion minimal subsets can be computed e�ciently.

Lemma 1 The set IMS (A1; : : : ; Am 0 ) can be computed in polynomial time.

Proof sketch: First, note that any two elements in IMS (A1; : : : ; Am 0 ) must be disjoint. The algorithm is as follows. If the intersection of A1; : : : ; Am 0 is nonempty then return it. Else, find greedily an element X of IMS (A1; : : : ; Am 0 ) and return fXg [ IMS (fAi : Ai n X , ;g). Element X is found in the following greedy way. X is set to A1 and for i = 2 to m 0 , if X \ Ai , ;, then X is set to X \ Ai. The running time is O(jAj 3 m 0 ). �

Now that we have defined IMS , we are ready to present MR. MR is summarized as Algorithm 1 which calls a subroutine (Algorithm 2) and computes a lottery p such that p(a) is the probability of a 2 A. We will denote by s 1 (a; S; R)

Algorithm 1 MR

Input: (A; N; R)

Call MR-subroutine(A; 1; (A; N; R)) to compute p(a) for each a 2 A.

return [a1 : p(a1); : : : ; am : p(am)]

Algorithm 2 MR-subroutine

Input: (S; v; (A; N; R))

• 1 if maxRi (S ) = S for all i 2 N then
• 2 p(a) = v=jS j for all a 2 S
• 3 else
• 4 T(i; S; R) � fa : a 2 argmaxa2maxRi (S ) s 1 (a; S; R)g for all i 2 N
• 5 t(i; a; R) � 1=jT(i; S; R)j if a 2 T(i; S; R) & zero otherwise for all i 2 N & a 2 S
• 6 �(a) � P i2N t(i; a; R) for all a 2 S
• 7 p(a; R) � v(�(a; R))=jNj for all a 2 S
• 8 fS 1; : : : ; S kg � IMS (maxR1 (S ) \ supp(p); : : : ; maxRn (S ) \ supp(p))
• 9 for each S j 2 fS 1; : : : ; S kg do
• 10 return MR-subroutine(S j; p(S j); (A; N; R))
• 11 end for
• 12 end if

the generalized plurality score of a according to R when the alternative set and the preference profile is restricted to S .

In MR, the probability weight of a set of alternatives is recursively redistributed over disjoint subsets of the alternatives. MR starts with the set of all alternatives for which the probability weight of one is to be redistributed. In MR-subroutine, S is a subset of A, and v is the total probability weight of S that is to be redistributed among the elements of S . In the first call of MR-subroutine, S = A and v = 1. Each agent i selects T(i; S; R) the set of his most preferred alternatives from within the set S with the maximum generalized plurality score with respect to R. Each i 2 N uniformly divides a total score of one among some of the most favoured alternatives in S : each i 2 N gives 1=jT(i; S; R)j to each element of T(i; S; R). Based on these contributions of scores, each alternative a gets a total score �(a; R) which is then normalized by the sum of the total scores of all alternatives. The resultant fraction �(a; R)= P aj2A �(aj; R) = �(a; R)=jNj is the fraction of probability weight v which alternative a gets. The intersections of T(i; S; R) for each i 2 N result in minimal intersecting sets each with a total weight equaling the sum of the weights of alternatives in the intersecting sets. The process is recursively repeated until the maximal elements of each set for each agent equal the set itself.

The algorithm gives rise to a recursion tree in which the root is labelled by A and is at depth zero. Each node is labeled by a subset of A. At any depth of the tree, the sets of the nodes of the tree are disjoint. Consider the leaves L1; : : : ; Lk. Then S i2f1;:::;kg Li = supp(p). Also note that a 2 S for some node labeled S , then a is in each ancestor of S . Consider any node labeled S , and consider a child S 0 of S such that a; a 0 2 S 0 . Then, for each agent i, a 2 maxRi (S ) () a 0 2 maxRi (S ).

Note that we start the whole set A at depth 0. At depth k, the amount of weight put on the first k equivalence classes is fully set for each agent i.e., it will not change.

Proposition 1 MR is single-valued and runs in polynomial time.

In each depth of the recursion tree, a lottery is maintained. In each depth there are at most jAj function calls to the MRsubroutine, each taking time O(jAj 3 n). The depth of the recursion tree can be at most jAj. Hence the total time taken is polynomial in the input. A unique lottery is returned in the end.

It can easily be seen that MR does not depend on the identities of the agents and alternatives but only on the preference profile. MR is also monotonic i.e., if an alternative is reinforced, then its probability cannot decrease.

Proposition 2 MR is anonymous, neutral, and monotonic.

Just like RSD, MR is a proper extension of the anonymous random dictator rule.

Proposition 3 MR is an RD rule for strict preferences and is therefore SD-SP and SD-e�cient for strict preferences.

5 E�ciency

Ex post e�ciency is a minimal e�ciency requirement for social decision schemes. We show that MR is ex post e�cient.

Proposition 4 MR is ex post e�cient.

Proof Sketch: Let p be the lottery returned by MR. Consider an alternative a such that a is Pareto dominated by b. Without loss of generality, assume that b is Pareto optimal. We will show that a gets zero probability. If a is a maximally preferred alternative for some agent, then so is b. If a 2 S 1 for some S 1 2 fS 1; : : : ; S lg for the sets in depth one, then b 2 S 1 . By the same argument, if a 2 S k � S k�1 � � � � � S 1 , then b 2 S k � S k�1 � � � � � S 1 where S k is the set containing a and b at recursion depth k. Finally, since b Pareto dominates a, there exists some i 2 N such that b Pi a. Hence, there exists some k 0 < jAj such that a < S k 0 � S k 0 �1 � � � � � S 1 and b 2 S k 0 � S k 0 �1 � � � � � S 1 . Therefore a Pareto dominated alternative gets probability zero. Hence MR is ex post e�cient. �

MR is also DL 1 -e�cient.

Proposition 5 MR is DL 1 -e�cient.

Proof Sketch: If p is the MR lottery, we show that there exists no q , p such that q(E 1 i (A); Ri) � p(E 1 i (A); Ri) for all i 2 N and q(E 1 i (A); Ri) > p(E 1 i (A); Ri) for some i 2 N. For the sake of contradiction, let us assume that p is not DL 1 -e�cient and let the agent who gets a strict improvement be i. Since for each agent j 2 N, q(E 1 j (A); Ri) � p(E 1 j (A); Ri), it must be the case that there exist some alternative a 0 such that p(a 0 ) > 0 and a 0 is not in any of the sets of IMS (maxR1 (A); : : : ;maxRn (A)). Since p(a 0 ) > 0, the latter condition does not hold because a 0 2 fa : a 2 argmaxa2maxRj (N) s 1 (a; N; R)g for some j 2 N. �

Corollary 1 For dichotomous preferences, MR is DLe�cient and hence SD-e�cient.

On a number of instances, MR fares much better than RSD from the point of view of economic e�ciency.

Proposition 6 There exist instances for which the MR lottery is SD-e�cient but the RSD lottery is neither SD-e�cient nor DL 1 -e�cient.

Proof: Consider the following preference profile presented first in [Aziz et al., 2013b].

1 : fa; cg; fbg; fdg 2 : fb; dg; fag; fcg 3 : fag; fdg; fb; cg 4 : fbg; fcg; fa; dg

The outcome of RSD is [a : 5=12; b : 5=12; c : 1=12; d : 1=12] which is SD dominated by the MR outcome [a : 6=12; b : 6=12; c : 0; d : 0]. �

Proposition 7 There exist instances with indi�erences for which the MR lottery is the same as the RSD lottery and the lottery is not SD-e�cient.

Proof: Consider the following preference profile.

1 : fa1g; fag; fdg; fb; cg 2 : fa1g; fbg; fcg; fa; dg 3 : fa; cg; fa1; b; dg 4 : fb; dg; fa1; a; cg

Then, the MR outcome as well as the RSD outcome is [a1 : 1=2; a : 1=8; b : 1=8; c : 1=8; d : 1=8]. The outcome is not SD-e�cient since it is SD dominated by [a1 : 1=2; a : 1=4; b : 1=4. �

6 Strategyproofness

In this section we examine the strategyproofness aspects of MR. We show that MR is DL-SP and hence weak SD-SP.

Proposition 8 MR is DL-SP.

Proof Sketch: We show that at each depth in the recursion tree starting from depth 0, and for each set S � A corresponding to the node in the recursion tree, each agent i 2 N has no incentive other than to express maxRi (S ) as the maximally preferred alternatives in S . We will denote by MR(A 0 ; (Ri; R�i)) the sum of probability weight of alternatives in A 0 with respect to the lottery returned by MR on preference profile (Ri; R�i). Note that in MR, for any set S � A and any i 2 N, once the probability weight for maxRi (S ) has been fixed, it cannot decrease.

Let us assume that agent i expresses preferences R 0 i , Ri. We show that MR(maxRi (S ); (R 00 i ; R�i)) � MR(maxRi (S ); (R 0 i ; R�i)) if R 00 i is such that maxR 00 i (S ) = maxR 0 i (S ) [ maxRi (S ) for all S � A or if R 00 i is such that maxR 00 i (S ) = maxR 0 i (S )\maxRi (S ) for all S � A. Note that the only sets S that matter are the IMS sets encountered during the MR algorithm.

Consider the preference profile R 00 i such that maxR 00 i (S ) = maxR 0 i (S ) [ maxRi (S ) for all S � A. For all a 2 maxRi (S ), if a 2 maxR 0 i (S ), then a 2 maxR 00 i (S ). For any agent j , i, if a 2 T( j; S; (R 0 i ; R�i)), then it must be the case that a 2 T( j; S; (R 00 i ; R�i)). Thus, P a2maxRi (S ) t( j; a; (R 0 i ; R�i) � P a2maxRi (S ) t( j; a; (R 00 i ; R�i) for all j 2 N. Hence, MR(maxRi (S ); (R 00 i ; R�i)) � MR(maxRi (S ); (R 0 i ; R�i)).

Consider the preference profile R 00 i such that maxR 00 i (S ) = maxR 0 i (S ) \ maxRi (S ) for all S � A. Thus, P a2maxRi (S ) t( j; a; (R 0 i ; R�i) � P a2maxRi (S ) t( j; a; (R 00 i ; R�i) for all j 2 N. Hence, MR(maxRi (S ); (R 00 i ; R�i)) � MR(maxRi (S ); (R 0 i ; R�i)).

Since DL preferences are strict and complete, any preference R 0 i that yields a di�erent lottery will be strictly less preferred by agent i. �

Corollary 2 MR is weak SD-SP and weak DL 1 -SP.

Corollary 3 MR is SD-SP for dichotomous preferences.

In other words, an agent cannot misreport his preferences to get an unambiguous improvement in expected utility or to maximize the probability of his most preferred alternatives. Whereas MR is DL-SP, it is not SD-SP like RSD.

Proposition 9 MR is not SD-SP.

Proof: Consider the following preference profile.

1 : fa1g; fa2g; fa3g 2 : fa1g; fa2g; fa3g 3 : fa2; a3g; fa1g 4 : fa2; a3g; fa1g 5 : fa3g; fa2g; fa1g

Then MR returns the lottery [a1 : 2=5; a2 : 0=5; a3 : 3=5]. If agent 1 submits the preferences R 0 1 : fa1; a2g; fa3g, then, the MR lottery is [a1 : 1=5; a2 : 2=5; a3 : 2=5]. Therefore it is not the case that MR(R1; R�1) R S D 1 MR(R 0 1 ; R�1). �

7 Discussion

Table 1: Properties satisfied by RSD and MR.

We presented a new social decision scheme called MR as an alternative to RSD. We showed that MR has both computational and e�ciency advantages over RSD.

MR also fares well against other social decision schemes. Recently strict maximal lotteries [Kreweras, 1965; Fishburn, 1984] have been proposed as an alternative to RSD [Aziz et al., 2013b]. However, strict maximal lotteries are not even weak SD-SP for strict preferences and they are P-complete to compute (hence at least as computationally hard as linear programming). On the other hand, maximal lotteries are attractive from an e�ciency point of view since they are SDe�cient. It will be interesting to see whether there is a way to modify MR so that it maintains its strategic properties but additionally satisfies SD-e�ciency. Just like MR, another weak SD-SP rule is Condorcet which gives probability 1 to a Condorcet winner or else gives uniform probability to all the alternatives [Theorem 1, Postlewaite and Schmeidler, 1986]. However the Condorcet social decision scheme is not ex post e�cient.

Some interesting questions still remain to be answered. For example, does there exist an anonymous non-RD rule that is both weak SD-SP and ex post e�cient? Does there exist an anonymous rule that is both DL-e�cient and DL-SP? Finally, most of the research on strategyproofness and e�ciency concepts based on lottery extensions has been conducted in the restricted domain of assignments problems. The same framework, when applied to the general domain of social choice, will open up new research frontiers.

Acknowledgements

This material is based upon work supported by the Australian Government's Department of Broadband, Communications and the Digital Economy, the Australian Research Council, and the Asian O�ce of Aerospace Research and Development through grant AOARD-124056. The author would like acknowledge the useful feedback of Markus Brill, Nick Mattei, and the anonymous referees. He also thanks Markus Brill and Felix Brandt for a number of insightful discussions on the topic.