1 Introduction
We study social choice mechanisms that aggregate individual preferences and select one among a finite set of alternatives. Our interest is in the existence of strategyproof social choice mechanisms under general, non quasilinear utility functions. In the classical voting problem without money, the seminal GibbardSatterthwaite theorem (Gibbard, 1973; Satterthwaite, 1975) states that if agents’ preferences can be any ordering over the alternatives, the only deterministic, onto (i.e. every alternative can be selected) and strategyproof mechanisms for three or more alternatives are dictatorial. On the other hand, with the introduction of monetary transfers and quasilinear utilities, the VickreyClarkeGroves (VCG) mechanism (Vickrey, 1961; Clarke, 1971; Groves, 1973) maximizes social welfare in dominant strategies, and can be generalized to implement any affine maximizer of agents’ values (Roberts, 1979; Krishna and Perry, 1998).
However, quasilinearity is a strong assumption, violated for example in domains with budget constraints and problems with lack of liquidity (Cramton, 1997) or with wealth effect and riskaversion (Pratt, 1992). Non quasilinearity can also arise as a result of the timing of payments coupled with temporal preferences (Frederick et al., 2002), when payments are contingent on agents’ actions and the presence of payments affects decisions and thus the likelihood of contingencies (Ma et al., 2016b, c), and in the context of illiquid currencies such as pointsbased allocation schemes (Kash et al., 2007).
To the best of our knowledge, few papers considered social choice mechanisms with monetary transfers and non quasilinear utilities.^{1}^{1}1A preliminary, short version of this paper (Ma et al., 2016a) proved a special case of the impossibility result for two agents and the richest non quasilinear utility domain, with additional assumptions of unanimity and neutrality. The proof techniques are different, and this preliminary version does not make use of the generalized Roberts theorem. The main result of this paper is a tight characterization of the maximal utility domain, which we name the largest parallel domain, where there exist nondictatorial mechanisms that are strategyproof, onto, deterministic, individually rational and satisfy no subsidy (i.e. no positive transfers from the mechanism to the agents). These properties are those of the VCG mechanism in quasilinear utility domains. As a special case, we prove that for utility domains that contain all quasilinear types but do not reside within the largest parallel domain, the only mechanisms satisfying the above conditions must be dictatorial. The proofs make use of a generalized Roberts’ theorem, which we extended to non quasilinear utility domains with suitable properties. We also provide a negative result for a broader class of mechanisms: by allowing richer utility domains that still differ very slightly from quasilinearity, we establish the impossibility of nondictatorial mechanisms even without requiring individual rationality or no subsidy.
A key observation is that the critical property of agents’ utilities that enables nondictatorial mechanisms is not the linear dependency on payments. We say the utility functions of an agent is of parallel type if for any two alternatives and , within the range of interest, no matter how much the agent is charged for , to achieve the same utility, the additional amount she is willing to pay for stays the same. Quasilinear utility functions have this property, but there can also be non quasilinear parallel types. Intuitively, a type being parallel requires that regardless of which alternative is selected, the agent’s marginal cost for money is the same as long as she has the same utility level— the tradeoff with money depends on how happy the agent is, not how much she is paying. A domain where all types are parallel is called a parallel domain, and the largest parallel domain is the set of all parallel types.
The rest of the paper is organized as follows. After a brief discussion of related work, we provide in Section 2 a formal definition of parallel domains. We prove a positive result in Section 3, that within the parallel domains, the family of generalized weighted VCG mechanisms are strategyproof, onto, deterministic, individually rational (IR), and satisfy no subsidy. In Section 4, we generalize Roberts’ Theorem (Roberts, 1979) to parallel domains, and prove that when the differences in agents’ willingness to pay for different alternatives are unrestricted, maximizers of affine functions of the willingness to pay are the only implementable choice rules amongst mechanisms with these properties. With this characterization, we prove in Section 5 our main result— that when agents have types outside of the parallel domain, the only mechanisms that are strategyproof, onto, deterministic, individually rational, and satisfy no subsidy must be fixedprice dictatorships, i.e. there exists a dictator who chooses her favorite alternative given fixed prices associated with each alternative. We also develop a negative result for a broader class of mechanisms: by allowing utility domains that are slightly richer in their non quasilinearity, we show that individual rationality and no subsidy can be relaxed, while the impossibility of nondictatorial mechanisms can still be established. We give in Section 5.1, for example, an impossibility result for a twoslopes domain, when the utility function of each agent for each alternative is linear, with the slope taking one of two possible values. Proofs omitted from the body of the paper are provided in Appendix A.
1.1 Related Work
In social choice without monetary payments, the classical GibbardSatterthwaite theorem has been extended to more restricted preference domains, including the saturated domains (Kalai et al., 1979), linked domains (Aswal et al., 2003), circular domains (Sato, 2010), and weakly connected domains (Pramanik, 2015). Domains for which there are positive results have also been extensively studied, see Black’s majority rule (Black, 1948), Moulin’s median voting schemes and generalizations (Moulin, 1980; Nehring and Puppe, 2007) and results on graphs with metric spaces (Barbera, 2001; Schummer and Vohra, 2002; Dokow et al., 2012).
For social choice with payments and quasilinear utilities, Roberts (1979) showed that with three or more alternatives, when the values can take any real numbers, positive association of differences is necessary and sufficient for strategyproof implementation, and that the only implementable choice rules are affine maximizers of agent values. Such choice rules can be implemented by weighted VCG mechanisms (Krishna and Perry, 1998). Characterizations of strategyproof implementations have also been developed for mechanism design problems in specific domains (Myerson, 1981; Rochet, 1987; Lavi et al., 2003; Bikhchandani et al., 2006; Saks and Yu, 2005).
One approach to mechanism design without quasilinearity is to assume that the functional form of agent utility functions is known to the designer, for example auctions public budget constraints (Dobzinski et al., 2012), or auctions with known risk preferences (Maskin and Riley, 1984). In contrast, we assume that the functional form of agent utility functions are private. For private non quasilinear utilities, under suitable richness of type space, Kazumura et al. (2017) prove a “taxation principle” style characterization and a “revenue uniqueness” result of truthful mechanisms, and show various applications to problems other than social choice, e.g. single item allocation. The existence of truthful and nondictatorial social choice mechanisms is not discussed.
For the assignment problem with unit demand, the minimum Walrasianequilibrium mechanism is known to be truthful (Demange and Gale, 1985; Alaei et al., 2010; Aggarwal et al., 2009; Dütting et al., 2009; Morimoto and Serizawa, 2015), even for any general nonincreasing utility function in payment. On the other hand, truthfulness cannot be achieved together with Paretoefficiency for allocation problems in which agents may demand more than one unit of good, or when agents have multidimensional type spaces (Kazumura and Serizawa, 2016; Dobzinski et al., 2012; Baisa, 2016). We do not impose Paretoefficiency (PE) in proving our impossibility results.^{2}^{2}2With PE, however, we prove a similar dictatorship result, which in comparison to our main results, requires weaker assumptions on agents utility domains. See Theorem 5 in Appendix B. Randomized mechanisms for bilateral trade (Garratt and Pycia, 2014) and revenueoptimal auctions in very simple settings (Baisa, 2017; Che et al., 2012; Pai and Vohra, 2014) have also been studied in the context of private budget constraints. We focus here on social choice rather than assignment or allocation problems, settings for which there is more structure on agents’ preferences and also indifference toward outcomes where an agent’s own assignments are the same.
2 Preliminaries
Denote as the set of agents and as the set of alternatives. A social choice mechanism accepts reports from agents as input, selects a single alternative , and may also determine payments. A mechanism is onto if for any alternative , there exists a preference profile for which is selected. A mechanism is dominantstrategy incentive compatible (DSIC) if no agent can gain by reporting false preferences.
We allow monetary transfers, and the utility of an agent may depend both on the selected alternative and her assigned payment. Denote as the utility of agent if alternative is selected and she needs to pay . determines agent ’s type and is her private information. Denote as a type profile, and as the type profile of agents except for agent .
Denote the utility of alternative to agent at zero payment as , which we call the value of alternative to agent . Let and be a most and a least preferred alternative at zero payment. A utility profile is quasilinear if for all , and . In this case, the values fully determine the type profile. Let the quasilinear domain be the set of all quasilinear types of a single agent where the ’s can take any value in , and let be the set of all quasilinear type profiles.
We consider non quasilinear utilities such that for all and all ,

is continuous and strictly decreasing in ,

.
Property (S1) guarantees that agents strictly prefer to make smaller payments. Property (S2) means that every agent prefers the worst alternative at zero payment to any alternative at some very large payment. Denote the general non quasilinear utility domain as the set of all types of an agent satisfying (S1) and (S2), and let be the general non quasilinear utility domain for a set of agents.
A social choice mechanism on type domain is composed of a choice rule and a payment rule . Thus if the reported type profile is , the choice made is , and the utility of agent is . A mechanism is DSIC if and only if, for any agent , any type of agent , and any reported profile from other agents , agent cannot gain by misreporting any type :
(1) 
A mechanism is individually rational (IR) if and only if, by truthfully participating in the mechanism, regardless of the reports made by the other agents, no agent can be worse off than having their worst alternative at zero payment selected and not making any payment.^{3}^{3}3For a mechanism where IR is violated, an agent may benefit from not participating. See Section 5 for more discussions on voluntary participation. Assuming for all and , may take any nonnegative value, for DSIC mechanisms, this definition of IR is equivalent to requiring that the utility of any truthful agent is nonnegative. That is, ,
(2) 
We are interested in mechanisms with the following set of properties.

Dominantstrategy incentive compatible

Deterministic

Onto

Individually rational

No subsidy
Ontoness only requires that all alternatives will be selected given some type profile, but does not require all payment schedules are achievable. No subsidy requires that the mechanism does not make positive transfers to the agents.
Before continuing, we review a wellknown characterization of deterministic DSIC mechanisms. We say that a mechanism is agentindependent if an agent’s payment is independent of her report, conditioned on a particular alternative being selected; i.e. fixing the type profile of the rest of the agents , , . Given an agentindependent mechanism and any , if there exists s.t. , let the agentindependent price be the payment pays when is selected: , which depends only on . Otherwise, if for all , let . An agentindependent mechanism is also agentmaximizing if given the agentindependent prices , the alternative selected by the mechanism maximizes the utilities of all agents simultaneously, i.e. , s.t. for all , and . The properties of agentindependence and agentmaximization are necessary and sufficient for deterministic DSIC mechanisms with quasilinear utilities (Vohra, 2011), and this equivalence can be easily generalized to general utilities that strictly decrease with payment.
A dictatorship in socialchoice without money identifies an agent as the dictator, and always selects her favorite alternative. We generalize this concept for social choice with money as follows:
Definition 1 (Fixed Price Dictatorship).
Under a fixed price dictatorship, there exists a dictator and fixed prices . Given any type profile , one of the dictator’s favorite alternatives under these prices is selected, i.e. , and the dictator pays .
2.1 Parallel Domains
Given any type of an agent , for each alternative , we define the willingness to pay as the payment for at which the agent is indifferent between getting at this payment, and getting her least preferred alternative at zero payment:
(3) 
See Figure 1. is the maximum amount the agent can be charged if alternative is selected, without violating IR. always holds, and (S1)(S2) imply that for all , exists, and .
Definition 2 (Parallel Domain).
A utility domain for an agent is a parallel domain if for all ,
(4) 
See Figure 1. We call a a parallel type if (4) is satisfied. For a parallel type , for s.t. , for any utility level , we have
(5) 
In words, the differences in the payments on and in order to achieve is a constant that does not depend on , i.e. the additional amount an agent is willing to pay for over does not depend on how much the agent is charged for .^{4}^{4}4There is no requirement on the shape of the utility functions below the utility level , or where the payments are negative, since utilities in these ranges are irreverent to the incentive properties of mechanisms that are IR and satisfy no subsidy. This also implies that the shape of the utility function of the least preferred alternative is irrelevant, and that when there are only two alternatives the general non quasilinear domain is parallel.^{5}^{5}5Abstracting away the cardinal utility to an agent for an outcome, and modeling instead the prices at which one alternative is more preferable than another, a type being parallel then requires that in the range of interest, for any pair of alternatives , which one is more preferable depends only on the difference in the prices . For an agent with parallel type, her marginal cost for money is the same as long as she has the same utility level, regardless of which alternative is selected. Intuitively, the tradeoff with money depends on how happy the agent is, not how much she is paying. For example, while paying for a better alternative, an agent with this kind of wealth effect would care less about money at the same payment amount than compared to a weaker alternative.
Denote as the largest parallel domain (i.e. the set of all parallel types), and . The quasilinear domain is a parallel domain, where for all and for all . Another special case of the parallel domain is the linear parallel domain, where for every , there exists s.t. and all , (so the quasilinear domain is a special case when ). For these two domains, the “vertical” distances between the utility curves also stay the same (which need not be the case for a general parallel domain), and the utility functions are horizontal translations of each other everywhere.
A utility domain for an agent is said to have unrestricted willingness to pay if for any
dimensional nonnegative vector with at least one zero entry, there exists
s.t. the willingness to pay according to is equal to this vector elementwise (at least one zero entry is required since an agent always has zero willingness to pay for ). Formally, for which s.t. , there exists s.t. for all .^{6}^{6}6There are multiple (actually, infinite number of) types in with the same vector of willingness to pay, and we only require at least one of them to be included. We call a parallel domain with unrestricted willingness to pay an unrestricted parallel domain. In particular, is an example of an unrestricted parallel domain. A utility domain is an unrestricted parallel utility domain if each of the is unrestricted and parallel.We now prove two lemmas.
Lemma 1.
Let be a DSIC and deterministic social choice mechanism on a utility domain with unrestricted willingness to pay. The mechanism satisfies (P4) IR and (P5) No subsidy if and only if and , the agentindependent prices satisfy:

for all alternatives ,

there exists an alternative s.t. .
Thus, the agentindependent prices any agent faces under a mechanism satisfying (P1)(P5) must be standard, i.e. the minimum price among all alternatives is zero. We leave the proof of the lemma to Appendix A.1.
Lemma 2.
For any parallel type and any standard prices :

s.t. and ,

.
Proof.
We first prove part (i). Assume w.l.o.g that . We know from the monotonicity of and the definition of parallel domain (4) that
For part (ii), observe that if the price for at least one of the alternatives is zero, the highest utility at the given prices among all alternatives is at least . Therefore, for any alternative s.t. , the alternative cannot be agentmaximizing. Among the alternatives s.t. , the agentmaximizing alternative(s) coincides with the maximizer(s) of , according to part (i). ∎
Thus, in a parallel domain, the agentmaximizing alternative given standard prices is the maximizer of the difference between the willingness to pay and the price: . As a result, the willingness to pay serves similar roles as values in the quasilinear domain, and it is this connection that enables us to generalize Roberts’ theorem to unrestricted parallel domains.
3 The Generalized Weighted VCG Mechanism
We prove in this section a positive result, that in parallel domains, the generalized weighted VCG mechanisms implement in dominant strategy any affine maximizer of willingness to pay: for nonnegative weights , and real constants .
Definition 3 (Generalized Weighted VCG).
The generalized weighted VCG mechanism, parametrized by nonnegative weights and real constants , collects a type profile from agents, and computes the willingness to pay . It is defined as

Choice rule: , breaking ties arbitrarily, independent to agents’ reports.

Payment rule: for s.t. ; for s.t. :
(6) where .
Theorem 1.
With type domain , any nonnegative coefficients and any real constants , the generalized weighted VCG mechanism is DISC, IR and does not make positive transfers to the agents.
Proof.
We first consider an agent s.t. . Given , we can check that for any agent reports s.t. , agent ’s agentindependent payment would be
(7) 
For agent s.t. , and coincide. No matter what agent reports, is always selected and she does not pay anything, thus
(8) 
Since is the maximizer of , all agentindependent prices are nonnegative. Moreover, has the minimum price among all alternatives, which is exactly zero: . By Lemma 1, we know that the prices are standard, and the mechanism satisfies (P4) IR and (P5) No subsidy if it is DSIC. What is left to prove is choosing at such agentindependent prices is agentmaximizing for all agents, which implies DSIC. From Lemma 2 we know that we only need to prove is the maximizer of for all agents. This is immediate for agents with . For an agent with , for any alternative , we have
thus indeed maximizes . ∎
Note that when , we have for all , , and maximizing an affine function of the willingness to pay is equivalent to maximizing the same affine function of the values. Thus, this mechanism coincides with the weighted VCG mechanisms when utilities are quasilinear. Ontoness is satisfied if for at least one agent and when the utility domain is unrestricted.
4 Generalizing Roberts’ Theorem
With quasilinear utilities, Roberts (1979) showed that with three or more alternatives, if each agent’s value for each alternative can be any real number, the choice rule of any social choice mechanism that is (P1) DISC, (P2) deterministic and (P3) onto must be a maximizer of some affine function of agents’ values. With two additional conditions, (P4) IR and (P5) No subsidy, we generalize Roberts’ theorem to the unrestricted parallel domains.
Theorem 2 (Roberts’ Theorem on Parallel Domains).
With three or more alternatives and an unrestricted parallel utility domain , for every social choice mechanism satisfying (P1)(P5), there exist nonnegative weights (not all equal to zero) and real constants such that for all ,
We prove in Lemma 3 that the weak monotonicity condition defined in terms of willingness to pay (which is eqivalent to the WMon condition in terms of values (Bikhchandani et al., 2006) when utilities are quasilinear, see Definition 4) is a necessary condition of incentive compatibility. Following the same steps as in the first proof of Roberts’ theorem presented in Lavi et al. (2009) while treating willingness to pay as “values” in the proof, we conclude that affine maximizers of the willingness to pay are the only implementable choice rules (see Appendix A.2 for the details). The coefficients cannot be all zero in order to satisfy (P3) Ontoness.
Regarding the requirements on the utility domain: in the proof of Robert’s theorem (Lavi et al., 2009), the values can take any real numbers, whereas the willingness to pay for a non quasilinear type takes nonnegative values and one of them has to be exactly zero. This does not prevent us from generalizing the proof, since what is necessary is that the differences in the values for all can be any real numbers. We get this from the unrestricted parallel domain.
Definition 4 (Weak Monotonicity).
Let be a utility domain. A choice rule satisfies weak monotonicity (WMon) if for all and all ,
In words, WMon in a parallel domain means that if alternative is selected under and alternative is selected under , the additional willingness to pay for comparing with according to , i.e. , must be at least as big as the additional willingness to pay for comparing with according to : . This is a generalization of the WMon condition in terms of values as defined in (Bikhchandani et al., 2006), and the two are equivalent when utilities are quasilinear, in which case holds for all .
Lemma 3.
With any parallel utility domain , every social choice mechanism satisfying (P1), (P2), (P4) and (P5) must satisfy WMon.
Proof.
Consider two types , and a social choice mechanism s.t. and . We know from agentmaximization and Lemma 2 that facing prices , alternative must be a maximizer of according to , and alternative must be a maximizer of according to . Thus, and must hold. Adding both sides of the two inequalities we get . ∎
5 Impossibility results
We now state the main result in this paper.
Theorem 3 (Dictatorship).
With at least three alternatives and a utility domain s.t.

for each , contains an unrestricted parallel domain,

for at least agents, ,
the only social choice mechanisms that satisfy (P1)(P5) are fixed price dictatorships.
The quasilinear domain is unrestricted and parallel, thus a special case of the theorem can be stated as: on any utility domain containing , if the utility domains of at least agents contain nonparallel types, the only mechanisms satisfying (P1)(P5) are fixed price dictatorships. We provide here an outline of the proof and leave the full version to Appendix A.3.
Given any mechanism with (P1)(P5) on a utility domain satisfying (C1) and (C2), we prove that the restriction of the mechanism on the parallel subspace must also satisfy (P1)(P5). Theorem 2 then implies that on , the choice rule must be the maximizer of some affine function of agents’ willingness to pay. Fixing the choice rule, agentindependence and agentmaximization determine the agentindependent prices up to a constant (when there is no tie), and the requirement that prices being standard fully pins down as (7) and (8) for all and any s.t. is parallel for all . Theorem 2 requires that there exists at least one agent with a nonzero coefficient . If the number of agents for whom is more than one, for at least one of them. Assume w.l.o.g. that and . Fixing some parallel type profile of the rest of the agents , are not yet pinned down by the above mentioned characterization since is not parallel. We prove that no agentindependent price guarantees that an alternative that is agentmaximizing for all agents always exists for all economies where . This contradicts DSIC.
Now we know that there exists exactly one agent (say ) with a nonzero coefficient. This implies that when the reported profile is parallel (i.e. ), the outcome of the mechanism must be determined according to a fixed price dictatorship. By induction on the number of agents whose type is not parallel, we then prove that for any , the outcome must also be determined by the same fixed price dictatorship.
On the Tightness of the Negative Result
That the utility domain contains an unrestricted parallel domain is necessary for Theorem 2. If the number of agents that has a type outside of the parallel domain is smaller than , there are at least two agents whose types are always parallel. The generalized weighted VCG mechanism with only for these agents would satisfy all (P1)(P5), and still would not be a dictatorship.
Regarding the properties (P1)(P5), the mechanism being (P1) DSIC and (P2) deterministic are trivially necessary. (P3) ontoness is required, since if some alternatives are never selected, the number of alternatives can be effectively reduced to two, in which case all types satisfying (S1) and (S2) are parallel, thus even for the most general , any generalized weighted VCG mechanism with coefficients not all zero satisfies (P1)(P5).
The conditions on the utility domain (C1) and (C2) in the statement of Theorem 3 require only a small deviation from quasilinearity or the parallel domain. As an example, with and , the type domain and for any (e.g. as illustrated in Figure 2) satisfies both (C1) and (C2). Assuming only (C1) and (C2), truthful mechanisms that violate one or both of (P4) and (P5) may still exist. For the above described utility domain, the mechanism which always adds 1 to agent 2’s payment but otherwise functions exactly as a generalized weighted VCG mechanism satisfies (P1)(P3) and (P5). More detailed discussions are provided in Appendix A.4, and we present an alternative impossibility result assuming only (P1)(P3) in Section 5.1.
On the Fixed Price Dictatorship
In a fixed price dictatorship, the dictator may still be asked to make some nonzero payments. It is clear that such a mechanism is DSIC, and when the prices that the dictator faces are standard, it is also IR and never pays the agents. In order to replace the fixedprice dictatorship in Theorem 3 with full dictatorship, i.e. the dictator chooses her favorite alternative free of charge, we can impose another condition, voluntary participation (VP), which means any agent can choose to walk away from the mechanism and accept the alternative decided by the rest of the agents without having to make any payment. If the dictator is charged a positive fixed price for some alternative , and is still the dictator’s favorite choice under the fixed prices, then when is selected by the subeconomy without the dictator (which should be the case for some given ontoness), the dictator would have the incentive to walk away, in which case will be selected and the dictator pays . This contradicts VP.
VP is stronger than IR. To see this, note that IR requires that for every agent at least one of the prices is weakly below the agent’s willingness to pay. On the other hand, VP requires that the mechanism is well defined for any economy of agents and satisfy the same properties, moreover, each agent must face a zeroprice for the alternative that would be selected in the subeconomy without her.
Regarding the payments from the rest of the agents— when the dictator strictly prefers a single alternative (i.e. , ), the rest of the agents do not make any payment: for all . In the degenerate case where , i.e. the dictator is indifferent toward multiple best alternatives, some or all the rest of the agents may be charged a nonzero payment to break ties among the dictator’s favorite alternatives (e.g., we could run a generalized VCG mechanism between two alternatives that are tied from the dictator’s perspective), and this may still satisfy (P1)(P5). See Appendix A.3.
5.1 Relaxing IR and No Subsidy
We show in the rest of the section that with more richness in non quasilinearity (e.g. with the linear domain with two slopes defined below), the dictatorship result remains given only (P1)(P3).
Definition 5 (Linear Domain with Two Slopes).
is a linear domain with two slopes if there exists , s.t. for all , , either for all or for all .
We say a linear domain with two slopes is unrestricted if for each , the values can be any real numbers, and the slopes of utility functions for different alternatives can be any combination of and .
Theorem 4.
With at least three alternatives and a utility domain s.t. for each , contains an unrestricted linear domain with two slopes, a social choice mechanism satisfying (P1)(P3) must be a fixed price dictatorship.
Intuitively, each contains as a subdomain an unrestricted linear parallel domain (e.g. the set of s.t. for all and all ), which is a special case of a strictly parallel domain. For strictly parallel domains, with only (P1)(P3), we can generalize Roberts’ Theorem, and still determine the agentindependent prices up to a constant. We then prove that if more than one agent has a positive coefficient in the choice rule, the induced agentindependent prices will result in contradictions when an agent’s utility domain consists of utility functions with mixed slopes. Then we can prove by induction that the only agent with a positive coefficient must be a fixed price dictator. See Appendix A.4.1 for the full proof.
The theorem still holds if , for all . Moreover, we would reach the same result if the ’s and ’s are known to the mechanism designer. Since the ’s and the ’s can be arbitrarily close, this theorem shows that very slight disturbances on the slopes of agents’ utility functions is sufficient to rule out the existence of truthful nondictatorial mechanisms.
6 Conclusions
The existence of truthful and nondictatorial social choice mechanisms strongly depends on whether monetary transfers are allowed. The seminal GibbardSatterthwaite theorem proves that without payments, the only truthful and onto mechanisms are dictatorial, whereas for the (rather restrictive) quasilinear utility domain, any affine maximizer of agent values can be implemented if payments are allowed. We study social choice with payments and general utilities, distinguish types being parallel as the central property of quasilinearity for DSIC mechanisms to exist, generalize (with additional conditions IR and No subsidy) Roberts’ theorem to parallel domains with unrestricted willingness to pay, and provide a tight characterization of the largest parallel domain. Within the largest parallel domain, the generalized weighted VCG mechanisms implement any affine maximizer of agents’ willingness to pay, and satisfy DSIC, onto, deterministic, IR and do not make payments to agents. Adding any nonparallel type to an unrestricted parallel domain, the only mechanisms with the above properties are dictatorial. We also discuss utility domains that are richer in their non quasilinearity but still deviate very slightly from the quasilinear domain, for which individual rationality and no subsidy can be relaxed and the dictatorship result remains.
References
 Aggarwal et al. (2009) Gagan Aggarwal, S Muthukrishnan, Dávid Pál, and Martin Pál. General auction mechanism for search advertising. In Proceedings of the 18th international conference on World wide web, pages 241–250. ACM, 2009.
 Alaei et al. (2010) Saeed Alaei, K Jain, and A Malekian. Competitive Equilibria in Two Sided Matching Markets with Nontransferable Utilities. arXiv:1006.4696, 10(2):34–36, 2010. URL http://arxiv.org/abs/1006.4696.
 Aswal et al. (2003) Navin Aswal, Shurojit Chatterji, and Arunava Sen. Dictatorial domains. Economic Theory, 22(1):45–62, 2003.
 Baisa (2016) Brian Baisa. Efficient multiunit auctions for normal goods. SSRN 2824921, 2016.
 Baisa (2017) Brian Baisa. Auction design without quasilinear preferences. Theoretical Economics, 12(1):53–78, 2017.
 Barbera (2001) Salvador Barbera. An introduction to strategyproof social choice functions. Social Choice and Welfare, 18(4):619–653, 2001.
 Bikhchandani et al. (2006) Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu’alem, Noam Nisan, and Arunava Sen. Weak monotonicity characterizes deterministic dominantstrategy implementation. Econometrica, 74(4):1109–1132, 2006.
 Black (1948) Duncan Black. On the rationale of group decisionmaking. The Journal of Political Economy, pages 23–34, 1948.
 Che et al. (2012) YeonKoo Che, Ian Gale, and Jinwoo Kim. Assigning resources to budgetconstrained agents. The Review of Economic Studies, page rds025, 2012.
 Clarke (1971) Edward H Clarke. Multipart pricing of public goods. Public choice, 11(1):17–33, 1971.
 Cramton (1997) Peter Cramton. The fcc spectrum auctions: An early assessment. Journal of Economics & Management Strategy, 6(3):431–495, 1997.
 Demange and Gale (1985) Gabrielle Demange and David Gale. The strategy structure of twosided matching markets. Econometrica: Journal of the Econometric Society, pages 873–888, 1985.
 Dobzinski et al. (2012) Shahar Dobzinski, Ron Lavi, and Noam Nisan. Multiunit auctions with budget limits. Games and Economic Behavior, 74(2):486–503, 2012.
 Dokow et al. (2012) Elad Dokow, Michal Feldman, Reshef Meir, and Ilan Nehama. Mechanism design on discrete lines and cycles. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 423–440. ACM, 2012.
 Dütting et al. (2009) Paul Dütting, Monika Henzinger, and Ingmar Weber. Bidder optimal assignments for general utilities. In International Workshop on Internet and Network Economics, pages 575–582. Springer, 2009.
 Frederick et al. (2002) Shane Frederick, George Loewenstein, and T O’donoghue. Time discounting and time preference: A critical review. Journal of Economic Literature, 40(2):351–401, 2002. URL http://www.jstor.org/stable/2698382.
 Garratt and Pycia (2014) Rod Garratt and Marek Pycia. Efficient bilateral trade. Working paper, available at SSRN 2444279, 2014.
 Gibbard (1973) Allan Gibbard. Manipulation of voting schemes: a general result. Econometrica: journal of the Econometric Society, pages 587–601, 1973.
 Groves (1973) Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617–631, 1973.
 Kalai et al. (1979) Ehud Kalai, Eitan Muller, and Mark A Satterthwaite. Social welfare functions when preferences are convex, strictly monotonic, and continuous. Public Choice, 34(1):87–97, 1979.
 Kash et al. (2007) Ian A Kash, Eric J Friedman, and Joseph Y Halpern. Optimizing scrip systems: Efficiency, crashes, hoarders, and altruists. In Proceedings of the 8th ACM conference on Electronic commerce, pages 305–315. ACM, 2007.
 Kazumura and Serizawa (2016) Tomoya Kazumura and Shigehiro Serizawa. Efficiency and strategyproofness in object assignment problems with multidemand preferences. Social Choice and Welfare, 47(3):633–663, 2016.
 Kazumura et al. (2017) Tomoya Kazumura, Debasis Mishra, and Shigehiro Serizawa. Mechanism design without quasilinearity. ISER Discussion paper No. 1005, available at SSRN 2982971, 2017.
 Krishna and Perry (1998) Vijay Krishna and Motty Perry. Efficient mechanism design. Technical report, 1998.
 Lavi et al. (2003) Ron Lavi, Ahuva Mu’Alem, and Noam Nisan. Towards a characterization of truthful combinatorial auctions. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 574–583. IEEE, 2003.
 Lavi et al. (2009) Ron Lavi, Ahuva Mu’alem, and Noam Nisan. Two simplified proofs for roberts’ theorem. Social Choice and Welfare, 32(3):407–423, 2009.

Ma et al. (2016a)
Hongyao Ma, Reshef Meir, and David C. Parkes.
Social Choice for Agents with General Utilities.
In
Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16)
, 2016a.  Ma et al. (2016b) Hongyao Ma, Reshef Meir, David C. Parkes, and James Zou. Contingent payment mechanisms to maximize resource utilization. arXiv preprint arXiv:1607.06511, 2016b.
 Ma et al. (2016c) Hongyao Ma, Valentin Robu, Na Li, and David C. Parkes. Incentivizing Reliability in DemandSide Response. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16), 2016c.
 Maskin and Riley (1984) Eric Maskin and John Riley. Optimal auctions with risk averse buyers. Econometrica: Journal of the Econometric Society, pages 1473–1518, 1984.
 Morimoto and Serizawa (2015) Shuhei Morimoto and Shigehiro Serizawa. Strategyproofness and efficiency with nonquasilinear preferences: A characterization of minimum price walrasian rule. Theoretical Economics, 10(2):445–487, 2015.
 Moulin (1980) Hervé Moulin. On strategyproofness and single peakedness. Public Choice, 35(4):437–455, 1980.
 Myerson (1981) Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58–73, 1981.
 Nehring and Puppe (2007) Klaus Nehring and Clemens Puppe. The structure of strategyproof social choice  part i: General characterization and possibility results on median spaces. Journal of Economic Theory, 135(1):269–305, 2007.
 Pai and Vohra (2014) Mallesh M Pai and Rakesh Vohra. Optimal auctions with financially constrained buyers. Journal of Economic Theory, 150:383–425, 2014.
 Pramanik (2015) Anup Pramanik. Further results on dictatorial domains. Social Choice and Welfare, 45(2):379–398, 2015.
 Pratt (1992) John W Pratt. Risk aversion in the small and in the large. In Foundations of Insurance Economics, pages 83–98. Springer, 1992.
 Roberts (1979) Kevin Roberts. The characterization of implementable choice rules. Aggregation and revelation of preferences, 12(2):321–348, 1979.
 Rochet (1987) JeanCharles Rochet. A necessary and sufficient condition for rationalizability in a quasilinear context. Journal of mathematical Economics, 16(2):191–200, 1987.
 Saks and Yu (2005) Michael Saks and Lan Yu. Weak monotonicity suffices for truthfulness on convex domains. In Proceedings of the 6th ACM conference on Electronic commerce, pages 286–293. ACM, 2005.
 Sato (2010) Shin Sato. Circular domains. Review of Economic Design, 14(34):331–342, 2010.
 Satterthwaite (1975) Mark Allen Satterthwaite. Strategyproofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187–217, 1975.
 Schummer and Vohra (2002) James Schummer and Rakesh V Vohra. Strategyproof location on a network. Journal of Economic Theory, 104(2):405–428, 2002.
 Vickrey (1961) William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8–37, 1961.

Vohra (2011)
Rakesh V Vohra.
Mechanism design: a linear programming approach
, volume 47. Cambridge University Press, 2011.
Appendix A Proofs
a.1 Proof of Lemma 1
See 1
Proof.
We first prove parts (i) and (ii) given (P4) and (P5). Assume part (i) does not hold, that there exists and s.t. . Consider s.t. . In any agentmaximizing mechanism, the agent is guaranteed utility at least , which is not possible without the mechanism making a positive payment to the agent, and this violates (P5). Now we only need to prove that it cannot be the case that for all . This is obvious, since if otherwise, there exists for whom for all thus , in which case (P4) is violated.
We now prove the other direction. Given part (i), it is obvious that no matter which alternative is selected, the transfer from any agent to the mechanism is nonnegative thus (P5) holds. Given (ii), we know that the agent’s minimum possible utility under an agentmaximizing mechanism is , which is at least , thus (P4) holds. ∎
a.2 Proof of Theorem 2
See 2
We had proved in Lemma 3 that WMon is a necessary condition for (P1)(P5) if the utility domain is unrestricted and parallel. We provide here a few more steps where the details differ slightly for values and willingness to pay, following the first proof presented in Lavi et al. (2009), however, the high level ideas are the same.
Definition 6 (Positive Association of Differences).
A social choice function on a parallel domain satisfies positive association of differences
(PAD) if: for all
and in , if and for all and all , then it must be the case that , as well.Lemma 4 (Ic Pad).
A social choice mechanism on an unrestricted parallel domain with (P1), (P2), (P4) and (P5) satisfies PAD.
Proof.
By Lemma 3, must satisfy WMon. Let be type profiles such that and for all and all . We need to show that . Denote . We know . Assume for some , we show by contradiction that must also hold. By induction, this implies that .
Assume that there exists and s.t. but . Since all players except player have the same type in and in , we get by WMon that , which contradicts the PAD assumption on and . Thus, must hold. This completes the proof of the induction step. ∎
We now prove the result analogous to Claim 1 in Lavi et al. (2009).
Claim 1.
Assume a choice rule on an unrestricted parallel domain satisfies PAD. Fix type profiles s.t. . If holds for all for some , then .
Proof.
We follow the same proof as in Lavi et al. (2009), and prove this claim by contradiction. The construction differs slightly from the original proof since the willingness to pay is always normalized s.t. the an agent’s smallest willingness to pay among all alternatives is zero.
Suppose by contradiction that . For each , denote . We know that for all , and in addition, . Consider s.t. for all ,
and for s.t. ,
Then, let be the normalized version of , i.e.
Comments
There are no comments yet.