Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 116-121.
© 2016 International Joint Conferences on Artificial Intelligence
Abstract
Two important requirements when aggregating the preferences of multiple agents are that the outcome should be economically efficient and the aggregation mechanism should not be manipulable. In this paper, we provide a computer-aided proof of a sweeping impossibility using these two conditions for randomized aggregation mechanisms. More precisely, we show that every efficient aggregation mechanism can be manipulated for all expected utility representations of the agents' preferences. This settles a conjecture by Aziz et al. [2013b] and strengthens a number of existing theorems, including statements that were shown within the special domain of assignment. Our proof is obtained by formulating the claim as a satisfiability problem over predicates from real-valued arithmetic, which is then checked using an SMT (satisfiability modulo theories) solver. To the best of our knowledge, this is the first application of SMT solvers in computational social choice.
- [Aziz et al., 2013a] H. Aziz, F. Brandt, and M. Brill. The computational complexity of random serial dictatorship. Economics Letters, 121(3):341-345, 2013.
- [Aziz et al., 2013b] H. Aziz, F. Brandt, and M. Brill. On the tradeoff between economic efficiency and strategyproof- ness in randomized social choice. In Proc. of 12th AAMAS Conference, pages 455-462.
- IFAAMAS, 2013.
- [Aziz et al., 2014] H. Aziz, F. Brandl, and F. Brandt. On the incompatibility of efficiency and strategyproofness in ran- domized social choice. In Proc. of 28th AAAI Conference, pages 545-551. AAAI Press, 2014.
- [Aziz et al., 2015] H. Aziz, F. Brandl, and F. Brandt. Uni- versal Pareto dominance and welfare for plausible utility functions. Journal of Mathematical Economics, 60:123- 133, 2015.
- [Barrett et al., 2010] C. Barrett, A. Stump, and C. Tinelli. The SMT-LIB Standard: Version 2.0. In Proc. of 8th In- ternational Workshop on Satisfiability Modulo Theories, 2010.
- [Barrett et al., 2013] C. Barrett, M. Deters, L. de Moura, A. Oliveras, and A. Stump. 6 years of SMT-COMP. Jour- nal of Automated Reasoning, 50(3):243-277, 2013.
- [Bogomolnaia and Moulin, 2001] A. Bogomolnaia and H. Moulin. A new solution to the random assignment problem. Journal of Economic Theory, 100(2):295-328, 2001.
- [Brandl et al., 2015] F. Brandl, F. Brandt, C. Geist, and J. Hofbauer. Strategic abstention based on preference ex- tensions: Positive results and computer-generated impos- sibilities. In Proc. of 24th IJCAI, pages 18-24. AAAI Press, 2015. IJCAI
- [Brandl et al., 2016a] F. Brandl, F. Brandt, and C. Geist. Proving the incompatibility of efficiency and strat- egyproofness via SMT solving. Technical report, http://arxiv.org/abs/1604.05692, 2016. Link
- [Brandl et al., 2016b] F. Brandl, F. Brandt, and W. Suksom- pong. The impossibility of extending random dictatorship to weak preferences. Economics Letters, 141:44-47, 2016.
- [Brandt and Geist, 2016] F. Brandt and C. Geist. Finding strategyproof social choice functions via SAT solving. Journal of Artificial Intelligence Research, 55:565-602, 2016.
- [Brandt et al., 2016] F. Brandt, C. Geist, and D. Peters. Op- timal bounds for the no-show paradox via SAT solving. In Proc. of 15th AAMAS Conference, pages 314-322.
- [Cimatti et al., 2013] A. Cimatti, A. Griggio, B. Schaafsma, and R. Sebastiani. The MathSAT5 SMT Solver. In Pro- ceedings of TACAS, volume 7795 of LNCS, pages 93-107.
- [de Moura and Bjørner, 2008] L. de Moura and N. Bjørner. Z3: An efficient SMT solver. In Proceedings of TACAS, volume 7795 of LNCS, pages 337-340. Springer, 2008.
- [Dutta et al., 2007] B. Dutta, H. Peters, and A. Sen. Strategy-proof cardinal decision schemes. Social Choice and Welfare, 28(1):163-179, 2007.
- [Gale, 1987] D. Gale. College course assignments and opti- mal lotteries, 1987. Mimeo.
- [Geist and Endriss, 2011] C. Geist and U. Endriss. Auto- mated search for impossibility theorems in social choice theory: Ranking sets of objects. Journal of Artificial Intel- ligence Research, 40:143-174, 2011.
- [Gibbard, 1973] A. Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587-601, 1973.
- [Gibbard, 1977] A. Gibbard. Manipulation of schemes that mix voting with chance. Econometrica, 45(3):665-681, 1977.
- [Katta and Sethuraman, 2006] A.-K. Katta and J. Sethura- man. A solution to the random assignment problem on the full preference domain. Journal of Economic Theory, 131(1):231-250, 2006.
- [McLennan, 2002] A. McLennan. Ordinal efficiency and the polyhedral separating hyperplane theorem. Journal of Economic Theory, 105(2):435-449, 2002.
- [Postlewaite and Schmeidler, 1986] A. Postlewaite and D. Schmeidler. Strategic behaviour and a notion of ex ante efficiency in a voting model. Social Choice and Welfare, 3(1):37-49, 1986.
- [Sato, 2013] S. Sato. Strategy-proofness and the reluctance to make large lies: the case of weak orders. Social Choice and Welfare, 40(2):479-494, 2013.
- [Satterthwaite, 1975] M. A. Satterthwaite. Strategy- proofness and Arrow's conditions: Existence and corre- spondence theorems for voting procedures and social wel- fare functions. Journal of Economic Theory, 10(2):187- 217, 1975.
- [Tang and Lin, 2009] P. Tang and F. Lin. Computer-aided proofs of Arrow's and other impossibility theorems. Ar- tificial Intelligence, 173(11):1041-1053, 2009.
- [Zhou, 1990] L. Zhou. On a conjecture by Gale about one- sided matching problems. Journal of Economic Theory, 52(1):123-135, 1990.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Models and results from microeconomic theory, in particular from game theory and social choice, have proven to be very valuable when reasoning about computational multiagent systems. Two fundamental notions in this context are efficiency-no agent can be made better off without making another one worse off-and strategyproofness-no agent can obtain a more preferred outcome by manipulating his preferences. Gibbard [1973] and Satterthwaite [1975] have shown that every strategyproof social choice function is either dictatorial or imposing. Hence, strategyproofness can only be achieved at the cost of discriminating among the agents or among the alternatives. One natural possibility to restore fairness, which is particularly popular in computer science, is to allow for randomization. Functions that map a profile of individual preferences to a probability distribution over alternatives (a so-called lottery) are known as social decision schemes (SDSs).
Generalizing his previous result, Gibbard [1977] proved that the only strategyproof and ex post efficient social decision schemes are randomizations over dictatorships. Gibbard's notion of strategyproofness requires that no agent is better off by manipulating his preferences for some expected utility representation of the agents' ordinal preferences. This condition is quite demanding because an SDS may be deemed manipulable just because it can be manipulated for a contrived and highly unlikely utility representation. In this paper, we adopt a weaker notion of strategyproofness, first used by Postlewaite and Schmeidler [1986] and popularized by Bogomolnaia and Moulin [2001]. This notion requires that no agent should be better off by manipulating his preferences for all expected utility representations of the agents' preferences. At the same time, we use a stronger notion of efficiency than Gibbard [1977]. This notion is defined in analogy to our notion of strategyproofness and requires that no agent can be made better off for all utility representations of the agents' preferences, without making another one worse off for some utility representation. This type of efficiency was introduced by Bogomolnaia and Moulin [2001] and is also known as ordinal efficiency or SD-efficiency where SD stands for stochastic dominance.
Our main result establishes that no anonymous and neutral SDS satisfies efficiency and strategyproofness. This settles a conjecture by Aziz et al. [2013b] and generalizes theorems by Aziz et al. [2013b], Aziz et al. [2014], and Brandl et al. [2016b]. It also strengthens related statements by Zhou [1990], Bogomolnaia and Moulin [2001], and Katta and Sethuraman [2006], which were shown within the special domain of assignment.
Our proof of this theorem heavily relies on computer-aided solving techniques. Some of these have already been applied in computational social choice, where, due to the rigorous axiomatic foundation, computer-aided theorem proving appears to be a particularly promising line of research. Perhaps the best known result in this context stems from Tang and Lin [2009], who reduce well-known impossibility results, such as Arrow's theorem, to finite instances, which can then be checked by a Boolean satisfiability (SAT) solver. Their work has sparked a number of contributions which, besides using this general idea for more complex settings or axioms, focus on proving novel results [Geist and Endriss, 2011; Brandl et al., 2015; Brandt et al., 2016; Brandt and Geist, 2016].
In this paper, we go beyond the SAT-based techniques of previous contributions by designing an SMT (satisfiability modulo theories) encoding that captures axioms for randomized social choice. SMT can be viewed as an enriched form of the satisfiability problem (SAT) where Boolean variables are replaced by statements from a theory, such as specific data types or arithmetics. Similar to SAT, there is a range of SMT solvers developed by an active community that runs annual competitions [Barrett et al., 2013]. Typically, SMT solvers are used as backends for verification tasks such as the verification of software. To capture axioms about lotteries, we use the theory of (quantifier-free) linear real arithmetic. Solving this version of SMT can be seen as an extension to linear programming in which arbitrary Boolean operators are allowed to connect (in-)equalities.
We follow the idea of Brandt and Geist [2016] and extract a minimal unsatisfiable set (MUS) of constraints in order to verify our result. Despite its relatively complex 94 (nontrivial) constraints, the MUS enables manual and computeraided verification of the encoding, and, hence, releases any need to verify our program for generating it.
2 The Model
Let A be a finite set of m alternatives and N = ¶1↪ ▷ ▷ ▷ ↪ n♦ a set of agents. A (weak) preference relation is a complete and transitive binary relation on A. The preference relation reported by agent i is denoted by %i, and the set of all preference relations by R. In accordance with conventional notation, we write ≻i for the strict part of %i, i.e., x ≻i y if x %i y but not y %i x, and ⇠i for the indifference part of %i, i.e., x ⇠i y if x %i y and y %i x. A preference relation %i is linear if x ≻i y or y ≻i x for all distinct alternatives x↪ y 2 A. We will compactly represent a preference relation as a comma-separated list with all alternatives among which an agent is indifferent placed in a set. For example, x ≻i y ⇠i z is represented by %i : x↪ ¶y↪ z♦▷ A preference profile R = (%1↪ ▷ ▷ ▷ ↪%n) is an n-tuple containing a preference relation %i for each agent i 2 N. The set of all preference profiles is thus given by RN . For a given R 2 RN and % 2 R, Ri7!% denotes a preference profile identical to R except that %i is replaced with %, i.e., Ri7!% = R ∩ ¶(i↪ %i )♦ [ ¶(i↪ %)♦.
2.1 Social Decision Schemes
Our central objects of study are social decision schemes: functions that map a preference profile to a lottery (or probability distribution) over the alternatives. The set of all lotteries over A is denoted by ∆(A), i.e., ∆(A) = ¶p 2 RA≥0 : Px2A p(x) = 1♦, where p(x) is the probability that p assigns to x. Then, formally, a social decision scheme (SDS) is a function f : RN ! ∆(A). By supp(p) we denote the support of a lottery p 2 ∆(A), i.e., the set of all alternatives to which p assigns positive probability. Two common minimal fairness conditions for SDSs are anonymity and neutrality, i.e., symmetry with respect to agents and alternatives, respectively. Formally, anonymity requires that f(R) = f(R ◦ σ) for all R 2 RN and permutations σ : N ! N over agents. Neutrality, on the other hand, is defined via permutations over alternatives. An SDS f is neutral if f(R)(x) = f(⇡(R))(⇡(x)) for all R 2 RN , permutations ⇡ : A ! A, and x 2 A. 1
2.2 Efficiency and Strategyproofness
Many important properties of SDSs, such as efficiency and strategyproofness, require us to reason about the preferences that agents have over lotteries. This is commonly achieved by assuming that in a preference profile R every agent i, in addition to this preference relation %i, is equipped with a von Neumann-Morgenstern (vNM) utility function uRi : A ! R. By definition, a utility function uRi has to be consistent with the ordinal preferences, i.e., for all x↪ y 2 A, uRi (x) ≥ uRi (y) iff x %i y. A utility representation u then associates with each preference profile R an n-tuple (uR1 ↪ ▷ ▷ ▷ ↪ uRn ) of such utility functions. Whenever the preference profile R is clear from the context, the superscript will be omitted and we write ui instead of the more cumbersome uRi .
Given a utility function ui, agent i prefers lottery p to lottery q iff the expected utility for p is at least as high as that of q. With slight abuse of notation the domain of utility functions can be extended in the canonical way to ∆(A) by letting
It is straightforward to define efficiency and strategyproofness using expected utility. For a given utility representation u and a preference profile R, a lottery p u-(Pareto-)dominates another lottery q if
An SDS f is u-efficient if it never returns u-dominated lotteries, i.e., for all R 2 RN , f(R) is not u-dominated. The notion of u-strategyproofness can be defined analogously: for a given utility representation u, an SDS can be u-manipulated if there are R 2 RN , i 2 N, and % 2 R such that
An SDS is u-strategyproof if it cannot be u-manipulated.
The assumption that the vNM utility functions of all agents (and thus their complete preferences over lotteries) are known is quite unrealistic. Often even the agents themselves are uncertain about their preferences over lotteries and only know their ordinal preferences over alternatives. 2 A natural way to model this uncertainty is to leave the utility functions unspecified and instead quantify over all utility functions that are consistent with the agents' ordinal preferences. This model leads to much weaker notions of efficiency and strategyproofness.
1⇡(R) is the preference profile obtained from ⇡ by replacing %i with %⇡i for every i 2 N, where ⇡(x) %⇡i ⇡(y) if and only if x %i y.
2 When assuming that all agents possess vNM utility functions, these utility functions could be taken as inputs for the aggregation function. Such aggregation functions are called cardinal decision schemes (see, e.g., [Dutta et al., 2007]). In addition to the fact that concrete vNM utility functions are typically unavailable, their representation may require infinite space.
Definition 1. An SDS is efficient if it never returns a lottery that is u-dominated for all utility representations u.
As mentioned in the introduction, this notion of efficiency is also known as ordinal efficiency or SD-efficiency (see, e.g., [Bogomolnaia and Moulin, 2001; Aziz et al., 2014; 2015]). The relationship to stochastic dominance will be discussed in more detail in Section 4.2.
Example 1. For illustration consider A = ¶a↪ b↪ c↪ d♦ and the preference profile R = (%1↪ ▷ ▷ ▷ ↪ %4),
Observe that the lottery 7◁24 a+7◁24 b+5◁24 c+5◁24 d, which is returned by the well-known SDS random serial dictatorship (RSD), is u-dominated by 1◁2 a + 1◁2 b for every utility representation u. Hence, any SDS that returns this lottery for the profile R would not be efficient. On the other hand, the lottery 1◁2 a + 1◁2 b is not u-dominated, which can, for instance, be checked via linear programming (see Lemma 4).
We can also define a weak notion of strategyproofness in analogy to our notion of efficiency.
Definition 2. An SDS is strategyproof if it cannot be umanipulated for all utility representations u.
Alternatively, there is a stronger version of strategyproofness by Gibbard [1977], in which an SDS should not be umanipulable for some utility representation u.
For more information concerning the relationship between sets of possible utility functions and preference extensions, such as stochastic dominance, the reader is referred to Aziz et al. [2015].
3 The Result
Our main result shows that efficiency and strategyproofness are incompatible with basic fairness properties. Aziz et al. [2013b] raised the question whether there exists an anonymous, efficient, and strategyproof SDS. When additionally requiring neutrality, we can answer this question in the negative.
Theorem1. If m≥ 4 and n ≥ 4, there is no anonymous and neutral SDS that satisfies efficiency and strategyproofness.
The proof of Theorem 1, which heavily relies on computeraided solving techniques, is discussed in Section 4. Let us first discuss the independence of the axioms and relate the result to existing theorems. RSD satisfies all axioms except efficiency; another SDS known as maximal lotteries satisfies all axioms except strategyproofness (cf. [Aziz et al., 2013b]). Serial dictatorship, the deterministic version of RSD, satisfies neutrality, efficiency, and strategyproofness but violates anonymity. It is unknown whether Theorem 1 still holds when dropping the assumption of neutrality. Our proof, however, only requires a technical weakening of neutrality (cf. Section 4.1).
3.1 Related Results for Social Choice
Our result generalizes several existing results and is closely related to a number of results in subdomains of social choice.
Aziz et al. [2013b] proved a weak version of Theorem 1 for the rather restricted class of majoritarian SDSs, i.e., SDSs whose outcome may only depend on the pairwise majority relation. This statement has later been generalized by Aziz et al. [2014] to all SDSs whose outcome only depends on the weighted majority relation. More recently, Brandl et al. [2016b] have shown that while random dictatorship is efficient and strategyproof on the domain of linear preferences, it cannot be extended to the full domain of weak preferences without violating at least one of these properties. Their theorem, which also assumes anonymity and neutrality, is a direct consequence of Theorem 1. Other impossibility results have been obtained for stronger notions of efficiency and strategyproofness, which weakens the corresponding statements [Aziz et al., 2014].
3.2 Related Results for Assignment
A subdomain of social choice that has been thoroughly studied in the literature is the assignment (aka house allocation or two-sided matching with one-sided preferences) domain. An assignment problem can be associated with a social choice problem by letting the set of alternatives be the set of deterministic allocations and postulating that agents are indifferent among all allocations in which they receive the same object (see, e.g., [Aziz et al., 2013a]). 3 Thus, impossibility results for the assignment setting can be interpreted as impossibility results for the social choice setting because they even hold in a smaller domain.
In the following we discuss impossibility results in the assignment domain which, if interpreted for the social choice domain, can be seen as weaker versions of Theorem 1 because they are based on stronger notions of efficiency or strategyproofness or require additional properties. In a very influential paper, Bogomolnaia and Moulin [2001] have shown that no randomized assignment mechanism satisfies both efficiency and a strong notion of strategyproofness while treating all agents equally. The underlying notion of strategyproofness is identical to the one used by Gibbard [1977] and prescribes that the SDS cannot be u-manipulated for some utility representation u. The result by Bogomolnaia and Moulin even holds when preferences over objects are linear. (Nevertheless, when transferred to the social choice domain, the preferences over allocations will contain ties.) In a related paper, Katta and Sethuraman [2006] proved that no assignment mechanism satisfies efficiency, strategyproofness, and envy-freeness for the full domain of preferences.
Settling a conjecture by Gale [1987], Zhou [1990] showed that no cardinal assignment mechanism satisfies u-efficiency and u-strategyproofness while treating all agents equally. 4 The relationship between Zhou's result and Theorem 1 is not obvious because Zhou's theorem concerns cardinal mechanisms, i.e., functions that take a utility profile rather than a preference profile as input. However, every cardinal assignment mechanism can be associated with an ordinal assignment mechanism. Hence, Theorem 1 implies that there is no anonymous, neutral, u-efficient, and u-strategyproof cardinal decision scheme.
3 Note that this transformation turns assignment problems with linear preferences over k objects into social choice problems with non-linear preferences over k! allocations.
4 The theorem by Zhou only requires that agents with the same utility function receive the same amount of utility but not necessarily the same assignment. Gale's original conjecture assumed equal treatment of equals.
4 Proving the Result
In this section, we first reduce the statement of Theorem 1 to the case of m = 4 and n = 4, which we then prove via SMT solving. We present an encoding for any finite instance of Theorem 1 as an SMT problem in the logic of (quantifierfree) linear real arithmetic (QF LRA). For compatibility with different SMT solvers our encoding adheres to the SMT-LIB standard [Barrett et al., 2010]. In total, we are going to design the following four types of SMT constraints: lottery definitions (Lottery), the orbit condition which models a part of neutrality (Orbit), strategyproofness (SP), and efficiency (Efficiency). Other conditions such as anonymity are taken care of by the representation of preference profiles.
We then, first, apply an SMT solver to show that this set of constraints for the case of m = 4 and n = 4 is unsatisfiable, i.e., no SDS f with the desired properties exists. Second, we explain how the output of the solver can be used to obtain a human-verifiable proof of this result.
But let us start with the reduction lemma before we turn to the concrete encoding in the following subsections.
Lemma 1. If there is an anonymous and neutral SDS f that satisfies efficiency and strategyproofness for ♣A♣ = m alternatives and ♣N♣ = n agents then we can also find an SDS f 0 defined for m0 m alternatives and n0 n agents that satisfies the same properties.
Proof. Let f be an anonymous and neutral SDS that satisfies efficiency and strategyproofness for m alternatives and n agents. We define a projection f 0 of f onto A0 ✓ A↪ ♣A0 ♣ = m0 m and N 0 = ¶1↪ 2↪ ▷ ▷ ▷ ↪ n0 ♦ ✓ N↪ n0 n that satisfies all required properties:
For every preference profile R0 on A0 and N 0 , let f 0 (R0 ) = f(R), where R is defined by the following conditions:
Informally, by (1) agents in N 0 have the same preferences over alternatives from A0 in R and R0 . Moreover, by (2) they like every alternative in A0 strictly better than every alternative not in A0 and by (3) they are indifferent between all alternatives not in A0 . Finally, by (4) all agents in N ∩ N 0 are completely indifferent. With these conditions, R is uniquely specified given R0 , and only lotteries p with supp(p) ✓ A0 are efficient in R. Thus, f 0 is well-defined and it is left to show that f 0 inherits the relevant properties from f. The SDS f 0 is anonymous since f is anonymous and agents in N can only differ by their preferences over A0 . Neutrality follows as f is neutral and all agents are indifferent between all alternatives not in A0 . Efficiency is satisfied by f 0 since f is efficient and the same set of lotteries is efficient in R and R0 . Finally, f 0 is strategyproof because f is strategyproof and the outcomes of f 0 under the two profiles R0 and (R0 )i7!%0 are equal to the outcomes of f under the two (extended) profiles R and Ri7!%, respectively.
4.1 Framework, Anonymity, and Neutrality
For a given number of agents n and set of alternatives A, we encode an arbitrary SDS f : RN ! ∆(A) by a set of real-valued variables pR↪x with R 2 RN and x 2 A. Each pR↪x then represents the probability with which alternative x is selected for profile R, i.e., pR↪x = f(R)(x).
This encoding of lotteries leads to the first simple constraints for our SMT encoding, which ensure that for each preference profile R the corresponding variables pR↪x, x 2 A indeed encode a lottery:
We are now going to argue that, in conjunction with anonymity and neutrality (see Section 2), it suffices to consider these constraints for a subset of preference profiles. This is because, in contrast to the other axioms, we directly incorporate anonymity and neutrality into the structure of the encoding rather than formulating them as actual constraints. Similar to the construction involving canonical tournament representations by Brandt and Geist [2016], we model anonymity and neutrality by computing for each preference profile R 2 RN a canonical representation Rc 2 RN with respect to these properties. In this representation, two preference profiles R and R0 are equal (i.e., Rc = R0c ) iff one can be transformed into the other by renaming the agents and alternatives. Equivalently, Rc = R0c iff, for every anonymous and neutral SDS f, the lotteries f(R) and f(R0 ) are equal (modulo the renaming of the alternatives).
The SMT constraints and SMT variables are then instantiated only for these canonical representations RNc ✓ RN . Apart from enabling an encoding of anonymous and neutral SDSs without any explicit reference to permutations, this also offers a substantial performance gain compared to considering the full domain RN of (non-anonymous and non-neutral) preference profiles.
Technically, we compute the canonical representation Rc as follows: Let R = (%1↪ ▷ ▷ ▷ ↪%n) 2 RN be a preference profile. First, we identify R with a function r : R ! N, which we call anonymous preference profile, and which counts the number of agents with a certain preference relation, i.e., r(%) = ♣¶i 2 N ♣ %i = %♦♣, thereby ignoring the identity of the agents. This representation fully captures anonymity.
To additionally enforce neutrality, we had to resort to a computationally demanding, naive solution: given r, we compute all anonymous preference profiles ⇡(r) that can be achieved via a permutation ⇡ : A ! A, and, among those profiles, choose the one ⇡lexmin(r) with lexicographically minimal values (for some fixed ordering of preference relations). For the canonical representation Rc we then pick any preference profile R 2 RN which agrees with ⇡lexmin(r), for instance, by again using the same fixed ordering of preference relations. Fortunately, this approach is still feasible for the small numbers of alternatives with which we are dealing.
While this representation of preference profiles does not completely capture neutrality-the orbit condition (see [Brandt and Geist, 2016]) is missing-this weaker version suffices to prove the impossibility. In favor of simpler proofs we, however, include the simple constraints corresponding to a randomized version of the orbit condition.
In our context, an orbit O of a preference profile R is an equivalence class of alternatives. Two alternatives x↪ y 2 A are considered equivalent if ⇡(x) = y for some permutation ⇡ : A ! A that maps the anonymous preference profile associated with R to itself (i.e., ⇡ is an automorphism of the anonymous preference profile). In such a situation, every anonymous and neutral SDS has to assign equal probabilities to x and y. We hence require that, for each orbit O 2 OR of a (canonical) profile R, the probabilities pR↪x are equal for all alternatives x 2 O. As an SMT constraint, this reads
for all R 2 RNc , O 2 OR, and x↪ y 2 O.
Example 2. Consider the anonymous preference profile r based on R from Example 1 and the permutation
As ⇡(r) = r (and since no other non-trivial permutation has this property) the set of orbits of R is OR = ¶¶a↪ b♦↪ ¶c↪ d♦♦.
4.2 Stochastic Dominance
In order to avoid quantifying over utility functions, we leverage well-known representations of efficiency and strategyproofness via stochastic dominance (SD) (cf. [Bogomolnaia and Moulin, 2001; McLennan, 2002; Aziz et al., 2015]). A lottery p stochastically dominates a lottery q for an agent i (short: p %SD i q) if for every alternative x, lottery p is at least as likely as lottery q to yield an alternative at least as good as x. Formally,
When p %SD i q and not q %SD i p we write p ≻SD i q. As an example, consider the preference relation %i : a↪ b↪ c. We then have that
while 2◁3 a + 1◁3 c and b are incomparable according to stochastic dominance.
Lemma 2. A lottery p SD-dominates another lottery q for an agent i iff u%i i (p) ≥ u%i i (q) for every utility function u%i i . As a consequence,
- an SDS f is efficient iff, for all R 2 RN , there is no lottery p such that p %SD i f(R) for all i 2 N and p ≻SD i f(R) for some i 2 N, and
- an SDS f is manipulable iff there exist a preference profile R, an agent i, and a preference relation % such that f (Ri7!%) ≻SD i f(R).
In words, Lemma 2 shows that an SDS f is efficient if and only if f(R) is Pareto-efficient with respect to stochastic dominance for all preference profiles R. Secondly, f is manipulable if and only if some agent can misrepresent his preferences to obtain a lottery that he prefers to the lottery obtained by sincere voting with respect to stochastic dominance.
Encoding Strategyproofness
Starting from the above equivalence, encoding strategyproofness as an SMT constraint is now a much simpler task. For each (canonical) preference profile R 2 RNc , agent i 2 N, and preference relation % 2 R, we encode that the manipulated outcome f(Ri7!%) is not SD-preferred to the truthful outcome f(R) by agent i:
where ⇡Ri7!% c stands for a permutation of alternatives that (together with a potential renaming of alternatives) leads from Ri7!% to (Ri7!%)c. The inequality (⇤) can be replaced by the equality (⇤⇤) since the case of at least one strict inequality is captured by the corresponding disjunctive condition one line above.
Encoding Efficiency
While Lemma 2 helps to formulate efficiency as an SMT axiom it is not yet sufficient since a quantification over the set of all lotteries ∆(A) remains. In order to get rid of this quantifier, we apply two lemmas by Aziz et al. [2015]. The first lemma states that efficiency of a lottery only depends on its support. The second lemma shows that deciding whether a lottery is efficient reduces to solving a linear program; for this statement we include a (slightly simplified) proof in favor of a self-contained presentation.
Lemma 3 (Aziz et al., 2015). A lottery p 2 ∆(A) is efficient iff every lottery p0 2 ∆(A) with supp(p0 ) ✓ supp(p) is efficient.
Lemma 4 (Aziz et al., 2015). Whether a lottery p 2 ∆(A) is efficient for a given preference profile R can be computed in polynomial time by solving a linear program.
Proof. Given the equivalence from Lemma 2, a lottery p is easily seen to be efficient iff the optimal objective value of the following linear program is zero (since then there is no lottery q that SD-dominates p):
Recall that an SDS is efficient if it never returns a dominated lottery. By Lemma 3, this is equivalent to never returning a lottery with inefficient support. To capture this, we encode, for each (canonical) preference profile R 2 RNc , that the probability for at least one alternative in every (inclusionminimal) inefficient support IR ✓ A is zero:
4.3 Restricted Domains
Since RSD (cf. Section 3) is known to satisfy both strategyproofness as well as efficiency for up to 3 alternatives, a search for an impossibility has to start at m = 4 alternatives. For n = 3 agents, the encoding is solved as satisfiable; for n = 4, an encoding of the full domain, unfortunately, becomes prohibitively large. Hence, for m = 4 and n = 4, one has to carefully optimize the domain under consideration, on the one hand, to include a sufficient number of profiles for a successful proof, and, on the other hand, not to include too many profiles, which would prevent the solver from terminating within a reasonable amount of time.
The following incremental strategy was found to be successful. We start with a specific profile R, from which we only consider sequences of potential manipulations as long as (in each step) the manipulated individual preferences are not too distinct from the truthful preferences. To this end, we measure the magnitude of manipulations by the Kendall tau distance ⌧ , which counts pairwise disagreements between Ri and R0i (see also [Sato, 2013]). A change in the individual preferences of an agent will be called a k-manipulation if ⌧(Ri↪R0i ) k. Then, for example, strategically swapping two alternatives is a 2-manipulation, and breaking or introducing a tie between two alternatives is a 1-manipulation.
On the domain which starts from the preference profile R from Example 1 and allows sequences of (1↪ 2↪ 1↪ 2)- manipulations, we were able to prove the result within a few minutes of running-time. 5,6 On similar, but smaller domains (e.g., (1↪ 2↪ 2)) the axioms are still compatible.
5 The SMT solver MathSAT [Cimatti et al., 2013] terminates quickly within less than 3 minutes with the suggested competition settings, whereas z3 [de Moura and Bjørner, 2008] requires some additional configuration, but then also supports core extraction within the same time frame.
6 Showing the result on this domain implies a slightly stronger
4.4 Verification of Correctness
For verification of the result, one would ideally construct a human-readable proof from the output of the SMT solver. While the approach described by Brandt and Geist [2016] for SAT solving-of finding a minimal unsatisfiable set (MUS) of constraints, i.e., an inclusion-minimal set of constraints such that this set is still unsatisfiable-is theoretically also applicable to SMT solving, it is less clear how these "proof ingredients" have to be combined. 7 The proof object that z3 can produce, which also contains information of how the MUS constraints have to be combined, unfortunately, is too long and complicated for humans to parse.
Hence two aspects of our approach still deserve verification: the correctness of the constraints in the MUS and the unsatisfiability of the MUS. In addition to manual inspection of the constraints and some sanity-checks, 8 we have certified in Isabelle/HOL that all constraints logically follow from the original axioms presented in Section 2. This also releases any need to verify our program for generating the constraints. The unsatisfiability of the MUS, on the other hand, has been verified by the solvers CVC4, MathSAT, Yices2, z3, and even by the Isabelle/HOL kernel.
Furthermore, based on the MUS, a proof of Theorem 1 which no longer relies on SMT solving has been created in Isabelle/HOL. This proof, however, is tedious to verify by hand since it is rather large (more than 500 lines of code) and offers little insight.
5 Conclusion
In this paper, we have leveraged computer-aided solving techniques to prove a sweeping impossibility for randomized aggregation mechanisms.
It seems unlikely that this proof would have been found without the help of computers because manual proofs of significantly weaker statements already turned out to be quite complex. Nevertheless, now that the theorem has been established, our computer-aided methods may guide the search for related, perhaps even stronger statements that allow for more intuitive proofs and provide more insights.
Generally speaking, we believe that SMT solving is applicable to a wide range of problems in randomized social choice. In particular, extending our result to the special domain of assignment (see Section 3.2) is desirable as this would strengthen a number of existing theorems. Other interesting questions are whether the impossibility still holds when weakening strategyproofness even further to BDstrategyproofness (see, e.g., [Aziz et al., 2014]) or when omitting neutrality.
statement where strategyproofness only applies to "small" lies (of at most Kendall tau distance 2).
7 Here we have an MUS of 94 constraints, not counting the (trivial) lottery definitions. This MUS, annotated with e.g., the 47 required canonical preference profiles, is available as part of an arXiv version of this paper [Brandl et al., 2016a].
8 Such as running solvers on multiple variants of the encoding which represent known theorems. This way, we reproduced (amongst others) the results by Bogomolnaia and Moulin [2001] and Katta and Sethuraman [2006], as well as the possibility result for m < 4.
6 Acknowledgments
This material is based upon work supported by the Deutsche Forschungsgemeinschaft under grants BR 2312/7-2 and BR 2312/10-1 and the TUM Institute for Advanced Study through a Hans Fischer Senior Fellowship. The authors also thank Manuel Eberl for the extensive verification work in Isabelle/HOL, Alberto Griggio and Mohammad Mehdi Pourhashem Kallehbasti for guidance on how to most effectively use MathSAT and z3, respectively, and three anonymous reviewers for their helpful comments.
@inproceedings{ijcai2016p24,
title = {Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving},
author = {Brandl, Florian and Brandt, Felix and Geist, Christian},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {116--121},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/24},
}
TY - CPAPER TI - Proving the Incompatibility of Efficiency and Strategyproofness via SMT Solving AU - Brandl, Florian AU - Brandt, Felix AU - Geist, Christian T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 116 EP - 121 UR - https://ijcai.org/proceedings/2016/24 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: