Social Choice for Agents with General Utilities

1 Introduction

Since its foundation, researchers interested in multi-agent AI have studied social choice mechanisms as a way to achieve coordinated decision-making. For example, social choice mechanisms were studied in the context of automated negotiation [Rosenschein and Zlotkin, 1994; Ephrati and Rosenschein, 1996] and for distributed, rational decision making [Sandholm, 1999].

A typical concern is that the mechanism be truthful, meaning that the optimal behavior for each agent is to make a truthful report about its private input (i.e., its preferences on outcomes.) When discussing truthful mechanisms, a sharp distinction is typically made based on whether the mechanism is allowed to use monetary transfers or not.

In the classical voting problem without money, the seminal Gibbard-Satterthwaite theorem [Gibbard, 1973; Satterthwaite, 1975] states that the only deterministic and truthful mechanisms for three candidates or more are dictatorial. This is true even if there are only two voters. On the other hand, the introduction of monetary transfers enables a value-maximizing, truthful mechanism known as the Clarke pivot rule, or VCG mechanism [Clarke, 1971; Groves, 1973;

David C. Parkes Harvard University parkes@eecs.harvard.edu

Green and Laffont, 1979]. The mechanism collects cardinal utilities from agents, selects the alternative with the highest total bids and charges each agent the amount by which she affected the outcome. See Conitzer [2010] for a broader comparison of voting and auction mechanisms.

Due to its generality and the wide range of applications, the VCG mechanism has become one of the most common and powerful tools in mechanism design [Nisan, 2007]. One major drawback of VCG is that it relies very strongly on the assumption that agents' utilities are quasi-linear (QL), i.e. of the form ua(z) = va - z for alternative a and payment z. 1

Non-QL utilities have gained much attention in recent years, both in AI and in economics. We provide some examples, demonstrating how these can arise in the context of group decisions and voting:

1. The use of contingent payments that depend on future decisions, such as a fine for agents who fail to use an item or show up for a meeting, transform QL utilities to ones that are convex in payment, since the amount of fine influences probability of follow through [Ma et al., 2015]. 2
2. The time of a payment may depend on the selected alternative; e.g., deciding how and when to implement a project may affect the payment schedule. Together with temporal inconsistency, the utility from early alternatives will decrease more quickly as payment increases [Frederick et al., 2002].
3. Agents may have hard or soft budget constraints in the context of automated bidding systems [Borgs et al., 2005].

In this paper, we consider agents that have arbitrary utility functions (that are strictly decreasing with payment), and ask whether there exists a mechanism for aggregating preferences that is truthful (i.e, dominant-strategy incentive compatible), individually rational, unanimous, and never pays the agents. In other words, we ask if VCG or similar mechanisms can be extended to domains where utilities are non quasi-linear.

Contribution: Ourmain result is analogous to theGibbardSatterthwaite impossibility theorem for general non-quasi linear domains (except it is restricted to two agents and unanimous rules) :

1 Indeed, for quasi-linear utility, and a rich enough value domain, any truthful mechanism has a structure that we can think of as "weighted VCG" [Roberts, 1979].

2 Such fines are used for example to deter amateur soccer teams from failing to show up for scheduled matches (see rule 19, http: //www.footiefives.com/?q=node/394).

Theorem (Informal). The only social choice mechanism for two voters with general decreasing utility functions that is truthful, unanimous, and never pays the agents, is dictatorial.

If the designer also requires neutrality and anonymity, both of which are satisfied by the VCG mechanism, we show that such a mechanism exists if and only if the type space satisfies a parallel domain property, where for each agent, the gaps between the willingness to pay for different alternatives are constant.

Since the disruptive papers of Gibbard and Satterthwaite, researchers in AI and computational social choice have contributed a plethora of tools and techniques to mitigate and override their negative results, including computational complexity [Conitzer and Sandholm, 2002; Hemaspaandra et al., 2007], uncertainty [Walsh, 2007; Conitzer et al., 2011], iterative voting mechanisms [Meir et al., 2010; Rabinovich et al., 2015], commitments [Xia and Conitzer, 2010], automated mechanism design [Sandholm et al., 2007; Jurca et al., 2009] and more. Given that our main result is negative, we believe that it is worth exploring how these kinds of techniques can be applied to the more general social choice problem that we present in this paper.

2 Preliminaries

Let N = ¶1↪ 2↪ ▷ ▷ ▷ ↪ n♦ be a set of agents and A = ¶a↪ b↪ ▷ ▷ ▷ ↪m♦ be a set of alternatives. We denote the set of all linear orders (permutations) over A by ⇡(A). For a vector y = (y1↪ y2↪ ▷ ▷ ▷ ↪ yn) we denote by y-i the partial vector with all entries except yi.

A social choice mechanism f accepts reports from agents as input, then outputs a single winner a 2 A and possibly payments that each agent should pay or receive. In classic voting, where monetary transfers are not allowed, it is assumed that the input is an ordinal preference profile P = (≻i)i2N, where ≻i2 ⇡(A), and agent i prefers j to j 0 if j ≻i j 0 . A social choice mechanism (a.k.a. a voting rule) is a function f : ⇡(A)n ! A from profiles to a single winner.

f is anonymous if the outcome is independent of the names of the agents, and neutral if the outcome is independent of the names of the alternatives. f is unanimous if alternative j is selected as long as j is the favorite alternative of all agents.

Since agents are assumed to be self-interested, and their preferences are private information, they may report strategically in order to achieve a more preferred outcome. A mechanism is dominant-strategy incentive compatible (DSIC, sometimes called strategyproof or truthful), if no agent can gain by reporting false preferences.

f is a dictatorship if there exists an agent i s.t. her favorite alternative is always selected. The Gibbard-Satterthwaite Theorem [Gibbard, 1973; Satterthwaite, 1975] states that for any m ≥ 3↪ n ≥ 2, the only voting rules that are DSIC and unanimous are dictatorial.

2.1 Social Choice withMonetary Transfers

We next move to a more general framework, where mechanisms are allowed to make monetary transfers and the utility of an agent may depend both on the selected alternative and her assigned payment. Denote ui↪j(z) as the utility of agent i if alternative j is selected and she needs to pay z. We require that ui↪j(z) is a continuous and strictly decreasing function of the payment z, 3 with ui↪j(0) ≥ 0 and ui↪j(1)  0, 8i↪ j. We refer to ui = (ui↪1↪ ▷ ▷ ▷ ↪ ui↪m) as agent i's type, and to u = (u1↪ ▷ ▷ ▷ ↪ un) as a type profile.

Denote the utility of alternative j to agent i at zero payment as vi↪j = ui↪j(0), which we call the "value." As is common in social choice, vi↪j 6= vi↪j 0 for all i for all j↪ j 0 . We thus retain notation j ≻i j 0 to denote that vi↪j > vi↪j 0 . Let ¯ji , argmaxj2A vi↪j and j i , argminj2A vi↪j be the most and least preferred alternative at zero payments for agent i.

Let U0 be the set of all utility functions (satisfying our technical properties), and U0 = U n 0 be the set of all profiles. Let U = U n be the set of utility profiles that we work with. U is quasi-linear if 8ui 2 U, ui↪j(z) = vi↪j-z↪ 8j 2 A↪ 8z 2 R. Let UQL be the set of QL utility profiles where agent values are non-negative.

Thus a social choice mechanism on type space U is composed of a choice rule x : U ! A and a payment rule t = (t1(u)↪ ▷ ▷ ▷ ↪ tn(u)) : U ! Rn . Thus if the choice made is x(u) = j then each agent i gains ui↪j(ti(u)).

The definitions of Anonymity and Neutrality naturally extend to mechanisms with payments. A mechanism (x↪ t) is DSIC if for any type ui 2 U of any agent i 2 N and any reported profile from other agents ˆu-i 2 U n-1 , agent i cannot gain by misreporting any false type ˆui 2 U:

A mechanism satisfies unanimity if when all agents agree on which alternative is the best at zero-payment, this alternative is selected and all payments are zero. We are especially interested in mechanisms that hold following set of conditions:

A1. Dominant-strategy incentive compatible (DSIC)

A2. No payments from the mechanism to agents

A3. Deterministic (unless breaking ties)

A4. Unanimous

A5. Anonymous A6. Neutral A7. Individually Rational (IR)

Requirements A1, A2, and A7 are standard in mechanism design, whereas A3-A6 are typically required in social choice. 4

2.2 Agent-Independent Prices

The structure of DSIC mechanisms with payments is well known (see [Nisan, 2007] for an overview). In particular, every DSIC mechanism must be agent independent and agent maximizing.

3 In voting without money ui↪j(z) is a constant.

4 We require the mechanism to be deterministic unless there are multiple alternatives that are simultaneously agent-maximizing for every agent. Only in this case can the mechanism break ties at random. Allowing randomization among outcomes among which agents may have strict preferences, and for the special case of two alternatives, a majority vote without payments and with random tiebreaking satisfies all of the requirements A1-A7.

Lemma 1 (Agent Independence). For any DSIC social choice mechanism (x↪ t), 8i 2 N, 8ui, 8u0i , 8u-i, if x(ui↪ u-i) = x(u0i ↪ u-i), then ti(ui↪ u-i) = ti(u0i ↪ u-i).

Intuitively, fixing the report u-i of the other agents, an agent i cannot affect her own payment without affecting the chosen alternative. Otherwise, an agent with type ui has an incentive to report the type u0i or vice versa.

Given u-i, if there exists ui 2 U s.t. x(ui↪ u-i) = j, then let the agent-independent prices be the payment i pays when j is selected: ti↪j(u-i) , ti(ui↪ u-i), which depends only on u-i. Otherwise, let ti↪j(u-i) ,1.

Lemma 2 (Agent Maximization). For any DSIC social choice mechanism (x↪ t), 8u 2 U, there must exist j ⇤ 2 A s.t. x(u) = j ⇤ and j ⇤ 2 argmaxj2A ui↪j(ti↪j(u-i))↪ 8i 2 N, i.e. the selected alternative must be simultaneously agent maximizing under the agent-independent prices for all agents.

It is easy to see that if agent-maximization does not hold there would be useful deviations. Further, any mechanism that meets both requirements is DSIC: an agent cannot affect her price for any particular alternative, and at the given prices (fixed by reports of others), she has no incentive to report in a way that results in a different alternative being selected. Therefore, a social choice mechanism is DSIC if and only if it can be stated in the following form:

• ÷ Compute agent-independent prices ti↪j(u-i) for each agent i and each alternative j.
• ÷ Choose an alternative j ⇤ 2 argmaxj2A ui↪j(ti↪j), and charge each agent ti(u) = ti↪j ⇤(u-i).

As an example, a simple mechanism that always chooses alternative a and collects no payment sets ti↪a = 0 and ti↪j = 1, for all j 6= a, for all i 2 N. It is easy to see that these payments are agent-independent and choosing a is the agent-maximizing allocation for all agents. For simplicity of notation, we drop the argument and denote ti↪j , ti↪j(u-i) when there is no ambiguity here onwards.

VCG mechanism. The Vickrey-Clarke-Groves (VCG) mechanism is defined for QL utilities and computes the valuemaximizing outcome, collecting from each agent the negative externality that she imposes on the rest of the agents. With QL utilities, all the information on an agent's type is conveyed in her values vi↪j. Thus, in the context of social-choice, VCG asks for a bid from each agent for each alternative, selects the alternative that has the maximum total bid value, and charges each agent the amount by which she is "pivotal" (meaning the amount of her bid that is important in causing this alternative to be selected.)

Mechanism 1: VCG Mechanism (QL Utilities)

In the case of ties, i.e. two alternatives with the same total bid, we can break ties randomly. The mechanism is deterministic in cases other than random tie-breaking.

For QL utilities, the VCG mechanism satisfies all properties A1-A7 (see [Nisan, 2007]). In particular, it is a dominant strategy for agents to bid their true values on each alternative b⇤i↪j = vi↪j. Observe that for any v-i, there exists types vi with very large vi↪j such that alternative j would be selected. Denote j ⇤-i = argmaxj2A Pi0 6=i vi↪j. For each alternative j 2 A, the agent-independent prices are of the form ti↪j(v-i) = Pi0 6=i vi0 ↪j ⇤-i - Pi0 6=i vi0 ↪j. It is easy to verify that the welfare-maximizing alternative j ⇤ is agentmaximizing for all agents.

Dictatorship. A dictator mechanism is defined by identifying a particular agent i⇤ 2 N and defining x to select alternative j to maximize vi⇤ ↪j, with all payments set to 0 (i.e. ti⇤(u) ⌘ 0). A dictatorship trivially satisfies all of our required properties except anonymity. For the dictator, ti⇤(u) is always zero thus ti⇤ ↪j(u-i⇤) = 0 always holds for all j regardless of the reports from the others u-i⇤. Let j ⇤ = ¯ji⇤ be the dictator's favorite alternative. In order for all other agents to always prefer alternative j ⇤ at their corresponding prices, we must have ti↪j ⇤ = 0 and ti↪j = 1 for all j 6= j ⇤ , for all i 6= i⇤ . These payments are agent-independent, and alternative j ⇤ is agent-maximizing for all agents.

3 Impossibility under General Utilities

We show that for general non-QL utility space U0 with two agents and at least three alternatives, the only mechanism satisfying A1-A4 must be a dictatorship. We focus w.l.o.g. on the true types as the inputs of the mechanism since we study DSIC mechanisms.

Let j (k) i be the kth favorite alternative for agent i at zero payment, i.e. vi↪j (1) > vi↪j (2) > ▷ ▷ ▷ vi↪j (m) . t-i↪j (k)(ui) denotes the price the other agent -i faces for the alternative that i ranks at place k, which is a function of only agent i's type ui due to agent independence. For a particular social choice mechanism, we define two subsets of the type space U I i ↪ U II i ✓ U0 as:

• ÷ U I i = ¶ui 2 U0 ♣ t-i↪j (2) i (ui) = 0♦
• ÷ U II i = ¶ui 2 U0 ♣ t-i↪j (k) i (ui) =1↪ 8k ≥ 3♦

U I i (utilities of the first type) is the collection of i's types that set a zero price for the other agent on i's second favourite alternative. U II i (utilities of the second type) is the collection of i's types s.t. all but the first two favourite alternatives for i are never selected for any u-i. We first prove that any agent type must belong to at least one of these two collections.

Lemma 3. In any mechanism satisfying A1-A4 for the nonQL utility space U0 with two agents, then one of ui 2 U I i and ui 2 U II i must hold for any agent i and any ui 2 U0.

Proof. Assume otherwise, there exists an agent i and a type ui 2 U0 s.t. ui ◁2 U I i and ui ◁2 U II i . W.l.o.g. we assume that 9u1 2 U0 s.t. a ≻1 b ≻1 c ≻1 · · · ≻1 m, t2↪b(u1) > 0

and t2↪j(u1) < 1 for some j 6= a↪ b. Consider for now that j = c, and the same argument can be repeated for all j 6= a↪ b.

With all possible types in U0, we can find u2 of agent 2 as shown in Figure 1 s.t. b ≻2 c ≻2 a and u2↪c(t2↪c) > u2↪b(t2↪b) > v2↪j↪ 8j 6= b↪ c, assuming t2↪b > 0 and t2↪c < 1.

We know from unanimity that t1↪b = 0 must hold, since if agent 1 reports b as her favorite alternative, b must be selected and her payment must be zero. Therefore we have 8j 6= a↪ b, u1↪j(t1↪j)  v1↪j < v1↪b = u1↪b(t1↪b), and the only possible agent-maximizing alternatives for agent 1 are a or b.

However, it is easy to see that the agent-maximizing alternative for agent 2 is c, thus there does not exist an alternative that is agent-maximizing for both agents. Contradiction.

The placement of agent i's type into U II 1 or U II 2 depends only on the mechanism and ui, and not on the report of the other agent. Say that an agent i is a dictator for alternative j, if ¯ji = j ) x(u) = j, and ti↪j(u-i) = 0 for all u-i 2 U0. Next, we show that if there exists ui 2 U I i , the other agent must be a dictator for j (2) i , the second favorite alternative of agent i.

Lemma 4. In any mechanism satisfying A1-A4 for the nonQL utility space U0 with two agents, if there exists a type ui 2 U I i with j = j (2) i , then agent -i is a dictator for j.

Proof. Assume w.l.o.g that there exists a type u2 2 U I 2 s.t. b ≻2 a ≻2 j for all j 6= a↪ b. We show that agent 1 is a dictator for alternative a. We proceed in steps:

Claim 1: For u1 2 U0 s.t. ¯j1 = a and j (2) 1 = b, we have u1 2 U II 1 . Assume otherwise, so that both u1 and u2 belong to U I and t1↪a = t2↪b = 0. We know from unanimity that t2↪a = t1↪b = 0. Under these prices, u1↪a(t1↪a) = v1↪a > v1↪b = u1↪b(t1↪b) and u2↪a(t2↪a) = v2↪a < v2↪b = u2↪b(t2↪b), and the agent-maximizing alternatives are different. A contradiction.

Claim 2: For u2 2 U0 s.t. c ≻2 a ≻2 j for j 6= a↪ c and c 6= b, we have u2 2 U I 2 . Assume otherwise, u2 ◁2 U I 2 . This implies t1↪j (2) 2 (u2) = t1↪a(u2) 6= 0 thus t1↪a(u2) > 0 since no payment is made to the agents. We can find a type u1 2 U0 as shown in Figure 2 s.t. a ≻1 b ≻1 j for all j 6= a↪ b, but u1↪a(t1↪a) < v1↪c. From unanimity, we have t2↪a = 0, and thus the agent maximizing alternative for agent 2 must be a or c. Further, we know from Claim 1 that u1 2 U II 1 thus t2↪c = 1 so alternative a must be selected. However, again from unanimity we know t1↪c = 0 thus u1↪a(t1↪a) < v1↪c = u1↪c(t1↪c). A contradiction.

Claim 3: 8u1 2 U0 s.t. ¯j1 = a, we have u1 2 U II 1 . With some u2 2 U I 2 s.t. b ≻2 a ≻2 j for j 6= a↪ b, we showed in Claim 1 that for u1 s.t. ¯j1 = a and j (2) 1 = b, u1 2 U II 1 . We know from Claim 2 that for all c 6= a↪ b, there exists u2 2 U I 2 s.t. c ≻2 a ≻2 j for j 6= a↪ c. Repeating the same argument as in Claim 1, we know that for all c 6= a↪ b, ¯j1 = a and j (2) 1 = c implies u1 2 U II 1 . Combining this with Claim 1, we know 8u1 2 U0 s.t. ¯j1 = a, u1 2 U II 1 .

Claim 4: For u2 2 U0 s.t. j (2) 2 = a, we have u2 2 U I 2 . In Claim 2, we showed that for u2 s.t. ¯j2 = c 6= b and j (2) 2 = a, u2 2 U I 2 . What is left to show is that u2 2 U I 2 for u2 s.t. ¯j2 = b and j (2) 2 = a. This follows by repeating the argument in Claim 2, observing that Claim 1 is generalized to u1 with ¯j1 = a and any j (2) 1 .

Claim 5: For all u1 2 U0 s.t. ¯j1 = a, we have t2↪j(u1) = 1 for all j 6= a. We know from Claim 3 that t2↪j = 1 for all j 6= a↪ j (2) 1 , and left to show is t2↪j (2) 1 =1. Denote j (2) 1 = b w.l.o.g. and assume for contradiction that t2↪b < 1. There exists u2 of agent 2 s.t. b ≻2 a ≻ j for all j 6= a↪ b and u2↪b(t2↪b) > v2↪a. We know from Claim 4 that t1↪a = 0, thus a is agent-maximizing for agent 1 and must be selected. However, agent 2 strictly prefers b to a at the current prices, thus this is a contradiction and t2↪b(u1) =1must hold.

Claim 6: 8u2 2 U0, we have t1↪a(u2) = 0. Assume otherwise, such that there exists u2 s.t. t1↪a(u2) > 0. We can find a type u1 of agent 1 such that a ≻1 j and u1↪a(t1↪a) < v1↪j for all j 6= a. From unanimity, we know t1↪¯j2 = 0 thus u1↪a(t1↪a) < v1↪¯j2 = u1↪¯j2 (t1↪¯j2 ). This shows that a is not the agent-maximizing alternative for agent 1, however from Claim 5 alternative a must be selected. A contradiction.

Thus we know that agent 1 never pays for alternative a, and a is selected as long as it is agent 1's most preferred alternative. This implies that agent 1 is a dictator for a.

Theorem 1. With two agents and at least three alternatives, the only social choice mechanism for the non-QL utility space U0 satisfying A1-A4 must be a dictatorship.

Proof. We proceed in steps:

Step 1: It is not possible that U I 1 = U I 2 = U0. Otherwise, consider any profile where a ≻1 b ≻1 ▷ ▷ ▷ ; b ≻2 a ≻2 ▷ ▷ ▷, we get a contradiction to agent maximizing with the same arguments as in Claim 1 of the proof of Lemma 4.

Step 2: It is not possible that U II 1 = U II 2 = U0. This is obvious if the number of alternatives is at least 4 since there would be type profiles where all alternatives are eliminated. Assume there are three alternatives and U II 1 = U II 2 = U0.

We know from Claim 1 that there must be some type of some agent that is not in U I ; thus, we assume w.l.o.g 9u2 ◁2 U I 2 and we name the alternatives s.t. c ≻2 b ≻2 a.

We know from the assumptions that t1↪b > 0. Consider the type u1 as shown in Figure 3 (we do not need to specify u2 exactly), i.e. for which u1↪b(t1↪b) < v1↪c. Since u1 2 U II 1 , u2 2 U II 2 , the only alternative that has not been rejected is b. However, t1↪c = 0 by unanimity thus u1↪c(t1↪c) = v1↪c > u1↪b(t1↪b). This contradicts agent-maximization, thus U II 1 = U II 2 = U0 cannot hold.

Step 3: By Step 2, the premise of Lemma 4 holds for some i 2 ¶1↪ 2♦ and some alternative. Thus w.l.o.g. agent 1 is a dictator for a, and t1↪a = 0 for all u2 2 U.

Step 4: For any alternative j 6= a, consider the type u2 s.t. j is ranked second and a is ranked last: j (2) 2 = j and j (m) 2 = a. Since t1↪a(u2) = 0 < 1must hold, u2 ◁2 U II 2 thus u2 2 U I 2 by Lemma 3. Again by Lemma 4 we know that agent 1 is the dictator for alternative j.

Therefore agent 1 is the dictator for all alternatives.

We know that the VCG mechanism meets all our requirements A1-A7 for QL utilities. Theorem 1 shows that once we allow arbitrary decreasing utility functions, then even minimal requirements A1-A4 lead to an impossibility result. A natural question is whether a positive result is available for a smaller set of non-QL utilities. Our impossibility result holds as long as we allow utility functions that are sufficiently "shallow." For example, all decreasing linear functions. In the remainder of the paper we explore the implications of more restricted utilities.

4 FromQuasi-Linear to Parallel Utilities

We now define the concept of a parallel domain for utilities. A type profile in a parallel domain is one in which, for each agent, the horizontal distances between the utility curves of different alternatives are constant, whenever the utility curves are above the value of the least preferred alternative.

We present a direct mechanism that satisfies A1-A7 for parallel domains, and prove an impossibility result for type spaces that are not parallel.

Definition 1 (Parallel Domain). A type space U ⇢ U0 is a parallel domain if for all u 2 U, for all i 2 N, for all j↪ j 0 2 A s.t. vi↪j > vi↪j 0 ,

In other words, 8w↪ 2 [vi↪j i ↪ vi↪j 0 ], u-1 i↪j (w) - u-1 i↪j 0(w) is a constant that does not depend on w, i.e. the additional amount an agent is willing to pay for j 0 over j does not depend on how much the agent is charged for j. There is no requirement on the shape of the curves ui↪j below vi↪j i . Denote Uk ✓ U0 as the largest parallel domain.

The QL space UQL is a parallel domain. A type space in which all first m- 1 utility curves of each agent are parallel (but not necessarily parallel to the utility curves of other agents) is also a parallel domain, which we call "linear parallel." For these two spaces, the vertical distances between the utility curves also stay the same, but this does not hold for general parallel domains. Finally, when there are only two alternatives, U0 is trivially a parallel domain.

We now introduce a direct mechanism that satisfies A1A7 for any number of agents and any number of alternatives if the type space is a parallel domain: U ✓ Uk. Given a type profile u 2 U, denote the "maximum willingness to pay" pi↪j as the amount at which agent i is indifferent between getting alternative j and getting the worst alternative for free: pi↪j = u-1 i↪j (vi↪j i ) = u-1 i↪j (minj 02A vi↪j 0 ).

Mechanism 2: Direct mechanism for parallel domains

Theorem 2. The direct mechanism satisfies A1-A7 for parallel domains, for any number of voters and alternatives.

Proof. A2, A3 and A5-A7 are easy to see. For A4, the willingness to pay is aligned with values at zero payment for parallel domains and argmaxpi↪j = ¯ji. If 9j ⇤ = ¯ji for all i, ti↪j ⇤ = 0 for all i and the mechanism satisfies unanimity.

What is left to check is DSIC. We can check that the prices are of the form ti↪j(ˆu-i) = maxj 0 Pi0 6=i pi0 ↪j 0 - Pi0 6=i pi0 ↪j and are agent independent by construction, thus we only need to show x(ˆu) = j ⇤ = argmaxj2A Pi2N pi↪j is simultaneously agent maximizing for every agent. Denote j ⇤-i = argmaxj2A Pi0 6=i pi0 ↪j. Observe that for parallel domains:

(ii) 8j↪ j 0 s.t. j ≻i j 0 , we have pi↪j -pi↪j 0 = u-1 i↪j (vi↪j 0 )

Also, we know from the payment rule that ti↪j ⇤  pi↪j ⇤. We need to discuss the following cases:

Case 1: j ⇤ = j i i.e. the worse alternative is selected. Since pi↪j ⇤ = pi↪j i = 0, we must have ti↪j ⇤ = 0 since ti↪j ⇤  pi↪j ⇤. Also from pi↪j ⇤ = 0, j ⇤ = j ⇤-i must hold. For any j 6= j ⇤ , the price agent i faces ti↪j = Pi0 6=i pi↪j ⇤-i - Pi0 6=i pi↪j = Pi0 pi0 ↪j ⇤ -pi↪j ⇤ - Pi0 pi0 ↪j + pi↪j = (Pi0 pi0 ↪j ⇤ - Pi0 pi0 ↪j) + pi↪j ≥ pi↪j. This implies ui↪j ⇤(ti↪j ⇤) = ui↪j i (0) = vi↪j i = ui↪j(pi↪j) ≥ ui↪j(ti↪j), and j ⇤ is the agent maximizing alternative.

Case 2: j ⇤ 6= j i . First, we know from ti↪j ⇤  pi↪j ⇤ that ui↪j ⇤(ti↪j ⇤) ≥ ui↪j ⇤(pi↪j ⇤) = vi↪j i = ui↪j i (0) ≥ ui↪j i (ti↪j i ). What is left to show is that for j 6= j i , ui↪j ⇤(ti↪j ⇤) ≥ ui↪j(ti↪j). Observe:

We consider the following two cases:

Case 2.1 j ⇤ ≺i j. We know from (ii) that pi↪j - pi↪j ⇤ = u-1 i↪j (vi↪j ⇤), thus ti↪j ⇤ - ti↪j  pi↪j ⇤ - pi↪j = -u-1 i↪j (vi↪j ⇤) ) ti↪j ≥ ti↪j ⇤ + u-1 i↪j (vi↪j ⇤). Since ti↪j ⇤  pi↪j ⇤ = u-1 i↪j ⇤(vi↪j i ), we know from the property of parallel domain that ui↪j(ti↪j)  ui↪j(ti↪j ⇤ + u-1 i↪j (vi↪j ⇤)) = ui↪j ⇤(ti↪j ⇤). Case 2.2 j ⇤ ≻i j. We know that pi↪j ⇤ - pi↪j = u-1 i↪j ⇤ (vi↪j ) therefore ti↪j ⇤  u-1 i↪j ⇤(vi↪j)+ti↪j . If ti↪j > pi↪j , we know that ui↪j(ti↪j) < vi↪j = ti↪j ⇤(pi↪j ⇤)  ui↪j ⇤(ti↪j ⇤) since ti↪j ⇤  pi↪j ⇤ . If ti↪j  pi↪j , we know from the property of parallel domain that ui↪j ⇤(ti↪j ⇤) ≥ ui↪j ⇤(u-1 i↪j ⇤ (vi↪j ) + ti↪j ) = ui↪j (ti↪j ).

Combining all above cases, we have showed that j ⇤ is agentmaximizing for all agents. This completes the proof.

Remark: It is evident from the description of the mechanism that there is an equivalent indirect mechanism, where each agent i only reports a "bid" pi↪j for each j 2 A.

4.1 Parallel Domains are Tight

We present the characterization of agent-independent prices for two agents in any mechanism under A1-A7, and show that the parallel domain is the largest type space in which such a mechanism exists. The details of the proofs are omitted due to the space limit.

Lemma 5 (Necessary Conditions for Agent-independent Prices). Consider two agents with types u1 and u2. Under any social choice mechanism satisfying A1-A7, the agent independent prices for the other agent -i determined by agent i's report t-i↪j(ui) must satisfy

i.e. for each alternative j, the other agent pays the amount that agent i needs to pay for ¯ji such that agent i is indifferent between getting ¯ji at this amount, and getting j for free.

Theorem 3. With two agents and at least three alternatives, under any type space U s.t. UQL ⇢ U and U 6⇢ Uk, there is no social choice mechanism satisfying assumptions A1-A7.

Proof sketch for m= 3. Assume w.l.o.g that there exists a type u1 of agent 1 s.t. a ≻1 b ≻1 c that is non-parallel. There must exists some z  u-1 1↪b (v1↪c) s.t. u1↪b(z) 6= u1↪a(z + u-1 1↪a (v1↪b)), as shown in Figure 5(a). Suppose u2↪b is more steep, as in the figure. We construct agent 2 with QL utilities c ≻2 b ≻2 a, s.t. agent 2 selects b but just barely. Thus the price she sets on a, due to the milder slope, results in agent 1 selecting a, in contradiction to agent-maximizing.

5 Conclusions

This paper has introduced the study of general social choice with non-QL utilities. We showed that without additional assumptions on the shape of agents' utility functions, any truthful social choice mechanism for three alternatives or more (under mild requirements) is dictatorial. While our proof only applies for two voters, we believe that the result holds for any number of voters, and leave it as an open question.

We have also provided a tight answer to the question of how restricted utility functions must be in order for VCGlike mechanisms to work, showing that the QL domain can be somewhat extended to parallel domain, but no further.

Because utilities are likely to go beyond the parallel domain in most realistic applications, we argue that future work should relax the DSIC requirement, and see whether weaker incentive guarantees can be attained for example by factoring considerations of computational intractability on agent reasoning, or through behvioral models [Meir et al., 2014].

Acknowledgments

This work is supported in part by a grant from the FLI, from the SEAS TomKat fund, and from NSF grant CCF-1301976.