Weak Monotonicity Suffices for Truthfulness on Convex Domains Michael Saks ∗ Dept. of Mathematics Rutgers University 110 Frelinghuysen Road Piscataway, NJ, 08854 saks@math.rutgers.edu Lan Yu † Dept. of Computer Science Rutgers University 110 Frelinghuysen Road Piscataway, NJ, 08854 lanyu@paul.rutgers.edu ABSTRACT Weak monotonicity is a simple necessary condition for a social choice function to be implementable by a truthful mechanism. Roberts [10] showed that it is sufficient for all social choice functions whose domain is unrestricted. Lavi, Mu"alem and Nisan [6] proved the sufficiency of weak monotonicity for functions over order-based domains and Gui, Muller and Vohra [5] proved sufficiency for order-based domains with range constraints and for domains defined by other special types of linear inequality constraints. Here we show the more general result, conjectured by Lavi, Mu"alem and Nisan [6], that weak monotonicity is sufficient for functions defined on any convex domain. Categories and Subject Descriptors J.4 [Social and Behavioral Sciences]: Economics; K.4.4 [Computers and Society]: Electronic Commerce-payment schemes General Terms Theory, Economics 1. INTRODUCTION Social choice theory centers around the general problem of selecting a single outcome out of a set A of alternative outcomes based on the individual preferences of a set P of players. A method for aggregating player preferences to select one outcome is called a social choice function. In this paper we assume that the range A is finite and that each player"s preference is expressed by a valuation function which assigns to each possible outcome a real number representing the benefit the player derives from that outcome. The ensemble of player valuation functions is viewed as a valuation matrix with rows indexed by players and columns by outcomes. A major difficulty connected with social choice functions is that players can not be required to tell the truth about their preferences. Since each player seeks to maximize his own benefit, he may find it in his interest to misrepresent his valuation function. An important approach for dealing with this problem is to augment a given social choice function with a payment function, which assigns to each player a (positive or negative) payment as a function of all of the individual preferences. By carefully choosing the payment function, one can hope to entice each player to tell the truth. A social choice function augmented with a payment function is called a mechanism 1 and the mechanism is said to implement the social choice function. A mechanism is truthful (or to be strategyproof or to have a dominant strategy) if each player"s best strategy, knowing the preferences of the others, is always to declare his own true preferences. A social choice function is truthfully implementable, or truthful if it has a truthful implementation. (The property of truthful implementability is sometimes called dominant strategy incentive compatibility). This framework leads naturally to the question: which social choice functions are truthful? This question is of the following general type: given a class of functions (here, social choice functions) and a property that holds for some of them (here, truthfulness), characterize the property. The definition of the property itself provides a characterization, so what more is needed? Here are some useful notions of characterization: • Recognition algorithm. Give an algorithm which, given an appropriate representation of a function in the class, determines whether the function has the property. • Parametric representation. Give an explicit parametrized family of functions and show that each function in the 1 The usual definition of mechanism is more general than this (see [8] Chapter 23.C or [9]); the mechanisms we consider here are usually called direct revelation mechanisms. 286 family has the property, and that every function with the property is in the family. A third notion applies in the case of hereditary properties of functions. A function g is a subfunction of function f, or f contains g, if g is obtained by restricting the domain of f. A property P of functions is hereditary if it is preserved under taking subfunctions. Truthfulness is easily seen to be hereditary. • Sets of obstructions. For a hereditary property P, a function g that does not have the property is an obstruction to the property in the sense that any function containing g doesn"t have the property. An obstruction is minimal if every proper subfunction has the property. A set of obstructions is complete if every function that does not have the property contains one of them as a subfunction. The set of all functions that don"t satisfy P is a complete (but trivial and uninteresting) set of obstructions; one seeks a set of small (ideally, minimal) obstructions. We are not aware of any work on recognition algorithms for the property of truthfulness, but there are significant results concerning parametric representations and obstruction characterizations of truthfulness. It turns out that the domain of the function, i.e., the set of allowed valuation matrices, is crucial. For functions with unrestricted domain, i.e., whose domain is the set of all real matrices, there are very good characterizations of truthfulness. For general domains, however, the picture is far from complete. Typically, the domains of social choice functions are specified by a system of constraints. For example, an order constraint requires that one specified entry in some row be larger than another in the same row, a range constraint places an upper or lower bound on an entry, and a zero constraint forces an entry to be 0. These are all examples of linear inequality constraints on the matrix entries. Building on work of Roberts [10], Lavi, Mu"alem and Nisan [6] defined a condition called weak monotonicity (WMON). (Independently, in the context of multi-unit auctions, Bikhchandani, Chatterji and Sen [3] identified the same condition and called it nondecreasing in marginal utilities (NDMU).) The definition of W-MON can be formulated in terms of obstructions: for some specified simple set F of functions each having domains of size 2, a function satisfies W-MON if it contains no function from F. The functions in F are not truthful, and therefore W-MON is a necessary condition for truthfulness. Lavi, Mu"alem and Nisan [6] showed that W-MON is also sufficient for truthfulness for social choice functions whose domain is order-based, i.e., defined by order constraints and zero constraints, and Gui, Muller and Vohra [5] extended this to other domains. The domain constraints considered in both papers are special cases of linear inequality constraints, and it is natural to ask whether W-MON is sufficient for any domain defined by such constraints. Lavi, Mu"alem and Nisan [6] conjectured that W-MON suffices for convex domains. The main result of this paper is an affirmative answer to this conjecture: Theorem 1. For any social choice function having convex domain and finite range, weak monotonicity is necessary and sufficient for truthfulness. Using the interpretation of weak monotonicity in terms of obstructions each having domain size 2, this provides a complete set of minimal obstructions for truthfulness within the class of social choice functions with convex domains. The two hypotheses on the social choice function, that the domain is convex and that the range is finite, can not be omitted as is shown by the examples given in section 7. 1.1 Related Work There is a simple and natural parametrized set of truthful social choice functions called affine maximizers. Roberts [10] showed that for functions with unrestricted domain, every truthful function is an affine maximizer, thus providing a parametrized representation for truthful functions with unrestricted domain. There are many known examples of truthful functions over restricted domains that are not affine maximizers (see [1], [2], [4], [6] and [7]). Each of these examples has a special structure and it seems plausible that there might be some mild restrictions on the class of all social choice functions such that all truthful functions obeying these restrictions are affine maximizers. Lavi, Mu"alem and Nisan [6] obtained a result in this direction by showing that for order-based domains, under certain technical assumptions, every truthful social choice function is almost an affine maximizer. There are a number of results about truthfulness that can be viewed as providing obstruction characterizations, although the notion of obstruction is not explicitly discussed. For a player i, a set of valuation matrices is said to be i-local if all of the matrices in the set are identical except for row i. Call a social choice function i-local if its domain is ilocal and call it local if it is i-local for some i. The following easily proved fact is used extensively in the literature: Proposition 2. The social choice function f is truthful if and only if every local subfunction of f is truthful. This implies that the set of all local non-truthful functions comprises a complete set of obstructions for truthfulness. This set is much smaller than the set of all non-truthful functions, but is still far from a minimal set of obstructions. Rochet [11], Rozenshtrom [12] and Gui, Muller and Vohra [5] identified a necessary and sufficient condition for truthfulness (see lemma 3 below) called the nonnegative cycle property. This condition can be viewed as providing a minimal complete set of non-truthful functions. As is required by proposition 2, each function in the set is local. Furthermore it is one-to-one. In particular its domain has size at most the number of possible outcomes |A|. As this complete set of obstructions consists of minimal non-truthful functions, this provides the optimal obstruction characterization of non-truthful functions within the class of all social choice functions. But by restricting attention to interesting subclasses of social choice functions, one may hope to get simpler sets of obstructions for truthfulness within that class. The condition of weak monotonicity mentioned earlier can be defined by a set of obstructions, each of which is a local function of domain size exactly 2. Thus the results of Lavi, Mu"alem and Nisan [6], and of Gui, Muller and Vohra [5] give a very simple set of obstructions for truthfulness within certain subclasses of social choice functions. Theorem 1 extends these results to a much larger subclass of functions. 287 1.2 Weak Monotonicity and the Nonnegative Cycle Property By proposition 2, a function is truthful if and only if each of its local subfunctions is truthful. Therefore, to get a set of obstructions for truthfulness, it suffices to obtain such a set for local functions. The domain of an i-local function consists of matrices that are fixed on all rows but row i. Fix such a function f and let D ⊆ RA be the set of allowed choices for row i. Since f depends only on row i and row i is chosen from D, we can view f as a function from D to A. Therefore, f is a social choice function having one player; we refer to such a function as a single player function. Associated to any single player function f with domain D we define an edge-weighted directed graph Hf whose vertex set is the image of f. For convenience, we assume that f is surjective and so this image is A. For each a, b ∈ A, x ∈ f−1 (a) there is an edge ex(a, b) from a to b with weight x(a) − x(b). The weight of a set of edges is just the sum of the weights of the edges. We say that f satisfies: • the nonnegative cycle property if every directed cycle has nonnegative weight. • the nonnegative two-cycle property if every directed cycle between two vertices has nonnegative weight. We say a local function g satisfies nonnegative cycle property/nonnegative two-cycle property if its associated single player function f does. The graph Hf has a possibly infinite number of edges between any two vertices. We define Gf to be the edgeweighted directed graph with exactly one edge from a to b, whose weight δab is the infimum (possibly −∞) of all of the edge weights ex(a, b) for x ∈ f−1 (a). It is easy to see that Hf has the nonnegative cycle property/nonnegative two-cycle property if and only if Gf does. Gf is called the outcome graph of f. The weak monotonicity property mentioned earlier can be defined for arbitrary social choice functions by the condition that every local subfunction satisfies the nonnegative two-cycle property. The following result was obtained by Rochet [11] in a slightly different form and rediscovered by Rozenshtrom [12] and Gui, Muller and Vohra [5]: Lemma 3. A local social choice function is truthful if and only if it has the nonnegative cycle property. Thus a social choice function is truthful if and only if every local subfunction satisfies the nonnegative cycle property. In light of this, theorem 1 follows from: Theorem 4. For any surjective single player function f : D −→ A where D is a convex subset of RA and A is finite, the nonnegative two-cycle property implies the nonnegative cycle property. This is the result we will prove. 1.3 Overview of the Proof of Theorem 4 Let D ⊆ RA be convex and let f : D −→ A be a single player function such that Gf has no negative two-cycles. We want to conclude that Gf has no negative cycles. For two vertices a, b, let δ∗ ab denote the minimum weight of any path from a to b. Clearly δ∗ ab ≤ δab. Our proof shows that the δ∗ -weight of every cycle is exactly 0, from which theorem 4 follows. There seems to be no direct way to compute δ∗ and so we proceed indirectly. Based on geometric considerations, we identify a subset of paths in Gf called admissible paths and a subset of admissible paths called straight paths. We prove that for any two outcomes a, b, there is a straight path from a to b (lemma 8 and corollary 10), and all straight paths from a to b have the same weight, which we denote ρab (theorem 12). We show that ρab ≤ δab (lemma 14) and that the ρ-weight of every cycle is 0. The key step to this proof is showing that the ρ-weight of every directed triangle is 0 (lemma 17). It turns out that ρ is equal to δ∗ (corollary 20), although this equality is not needed in the proof of theorem 4. To expand on the above summary, we give the definitions of an admissible path and a straight path. These are somewhat technical and rely on the geometry of f. We first observe that, without loss of generality, we can assume that D is (topologically) closed (section 2). In section 3, for each a ∈ A, we enlarge the set f−1 (a) to a closed convex set Da ⊆ D in such a way that for a, b ∈ A with a = b, Da and Db have disjoint interiors. We define an admissible path to be a sequence of outcomes (a1, . . . , ak) such that each of the sets Ij = Daj ∩ Daj+1 is nonempty (section 4). An admissible path is straight if there is a straight line that meets one point from each of the sets I1, . . . , Ik−1 in order (section 5). Finally, we mention how the hypotheses of convex domain and finite range are used in the proof. Both hypotheses are needed to show: (1) the existence of a straight path from a to b for all a, b (lemma 8). (2) that the ρ-weight of a directed triangle is 0 (lemma 17). The convex domain hypothesis is also needed for the convexity of the sets Da (section 3). The finite range hypothesis is also needed to reduce theorem 4 to the case that D is closed (section 2) and to prove that every straight path from a to b has the same δ-weight (theorem 12). 2. REDUCTION TO CLOSED DOMAIN We first reduce the theorem to the case that D is closed. Write DC for the closure of D. Since A is finite, DC = ∪a∈A(f−1 (a))C . Thus for each v ∈ DC − D, there is an a = a(v) ∈ A such that v ∈ (f−1 (a))C . Extend f to the function g on DC by defining g(v) = a(v) for v ∈ DC − D and g(v) = f(v) for v ∈ D. It is easy to check that δab(g) = δab(f) for all a, b ∈ A and therefore it suffices to show that the nonnegative two-cycle property for g implies the nonnegative cycle property for g. Henceforth we assume D is convex and closed. 3. A DISSECTION OF THE DOMAIN In this section, we construct a family of closed convex sets {Da : a ∈ A} with disjoint interiors whose union is D and satisfying f−1 (a) ⊆ Da for each a ∈ A. Let Ra = {v : ∀b ∈ A, v(a) − v(b) ≥ δab}. Ra is a closed polyhedron containing f−1 (a). The next proposition implies that any two of these polyhedra intersect only on their boundary. Proposition 5. Let a, b ∈ A. If v ∈ Ra ∩Rb then v(a)− v(b) = δab = −δba. 288 Da Db Dc Dd De v w x y z u p Figure 1: A 2-dimensional domain with 5 outcomes. Proof. v ∈ Ra implies v(a) − v(b) ≥ δab and v ∈ Rb implies v(b)−v(a) ≥ δba which, by the nonnegative two-cycle property, implies v(a) − v(b) ≤ δab. Thus v(a) − v(b) = δab and by symmetry v(b) − v(a) = δba. Finally, we restrict the collection of sets {Ra : a ∈ A} to the domain D by defining Da = Ra ∩ D for each a ∈ A. Clearly, Da is closed and convex, and contains f−1 (a). Therefore S a∈A Da = D. Also, by proposition 5, any point v in Da ∩ Db satisfies v(a) − v(b) = δab = −δba. 4. PATHS AND D-SEQUENCES A path of size k is a sequence −→a = (a1, . . . , ak) with each ai ∈ A (possibly with repetition). We call −→a an (a1, ak)path. For a path −→a , we write |−→a | for the size of −→a . −→a is simple if the ai"s are distinct. For b, c ∈ A we write Pbc for the set of (b, c)-paths and SPbc for the set of simple (b, c)-paths. The δ-weight of path −→a is defined by δ(−→a ) = k−1X i=1 δaiai+1 . A D-sequence of order k is a sequence −→u = (u0, . . . , uk) with each ui ∈ D (possibly with repetition). We call −→u a (u0, uk)-sequence. For a D-sequence −→u , we write ord(u) for the order of −→u . For v, w ∈ D we write Svw for the set of (v, w)-sequences. A compatible pair is a pair (−→a , −→u ) where −→a is a path and −→u is a D-sequence satisfying ord(−→u ) = |−→a | and for each i ∈ [k], both ui−1 and ui belong to Dai . We write C(−→a ) for the set of D-sequences −→u that are compatible with −→a . We say that −→a is admissible if C(−→a ) is nonempty. For −→u ∈ C(−→a ) we define ∆−→a (−→u ) = |−→a |−1 X i=1 (ui(ai) − ui(ai+1)). For v, w ∈ D and b, c ∈ A, we define Cvw bc to be the set of compatible pairs (−→a , −→u ) such that −→a ∈ Pbc and −→u ∈ Svw . To illustrate these definitions, figure 1 gives the dissection of a domain, a 2-dimensional plane, into five regions Da, Db, Dc, Dd, De. D-sequence (v, w, x, y, z) is compatible with both path (a, b, c, e) and path (a, b, d, e); D-sequence (v, w, u, y, z) is compatible with a unique path (a, b, d, e). D-sequence (x, w, p, y, z) is compatible with a unique path (b, a, d, e). Hence (a, b, c, e), (a, b, d, e) and (b, a, d, e) are admissible paths. However, path (a, c, d) or path (b, e) is not admissible. Proposition 6. For any compatible pair (−→a , −→u ), ∆−→a (−→u ) = δ(−→a ). Proof. Let k = ord(−→u ) = |−→a |. By the definition of a compatible pair, ui ∈ Dai ∩ Dai+1 for i ∈ [k − 1]. ui(ai) − ui(ai+1) = δaiai+1 from proposition 5. Therefore, ∆−→a (−→u ) = k−1X i=1 (ui(ai) − ui(ai+1)) = k−1X i=1 δaiai+1 = δ(−→a ). Lemma 7. Let b, c ∈ A and let −→a , −→a ∈ Pbc. If C(−→a ) ∩ C(−→a ) = ∅ then δ(−→a ) = δ(−→a ). Proof. Let −→u be a D-sequence in C(−→a ) ∩ C(−→a ). By proposition 6, δ(−→a ) = ∆−→a (−→u ) and δ(−→a ) = ∆−→a (−→u ), it suffices to show ∆−→a (−→u ) = ∆−→a (−→u ). Let k = ord(−→u ) = |−→a | = |−→a |. Since ∆−→a (−→u ) = k−1X i=1 (ui(ai) − ui(ai+1)) = u1(a1) + k−1X i=2 (ui(ai) − ui−1(ai)) − uk−1(ak) = u1(b) + k−1X i=2 (ui(ai) − ui−1(ai)) − uk−1(c), ∆−→a (−→u ) − ∆−→a (−→u ) = k−1X i=2 ((ui(ai) − ui−1(ai)) − (ui(ai) − ui−1(ai))) = k−1X i=2 ((ui(ai) − ui(ai)) − (ui−1(ai) − ui−1(ai))). Noticing both ui−1 and ui belong to Dai ∩ Dai , we have by proposition 5 ui−1(ai) − ui−1(ai) = δaiai = ui(ai) − ui(ai). Hence ∆−→a (−→u ) − ∆−→a (−→u ) = 0. 5. LINEAR D-SEQUENCES AND STRAIGHT PATHS For v, w ∈ D we write vw for the (closed) line segment joining v and w. A D-sequence −→u of order k is linear provided that there is a sequence of real numbers 0 = λ0 ≤ λ1 ≤ . . . ≤ λk = 1 such that ui = (1 − λi)u0 + λiuk. In particular, each ui belongs to u0uk. For v, w ∈ D we write Lvw for the set of linear (v, w)-sequences. For b, c ∈ A and v, w ∈ D we write LCvw bc for the set of compatible pairs (−→a , −→u ) such that −→a ∈ Pbc and −→u ∈ Lvw . For a path −→a , we write L(−→a ) for the set of linear sequences compatible with −→a . We say that −→a is straight if L(−→a ) = ∅. For example, in figure 1, D-sequence (v, w, x, y, z) is linear while (v, w, u, y, z), (x, w, p, y, z), and (x, v, w, y, z) are not. Hence path (a, b, c, e) and (a, b, d, e) are both straight. However, path (b, a, d, e) is not straight. 289 Lemma 8. Let b, c ∈ A and v ∈ Db, w ∈ Dc. There is a simple path −→a and D-sequence −→u such that (−→a , −→u ) ∈ LCvw bc . Furthermore, for any such path −→a , δ(−→a ) ≤ v(b) − v(c). Proof. By the convexity of D, any sequence of points on vw is a D-sequence. If b = c, singleton path −→a = (b) and D-sequence −→u = (v, w) are obviously compatible. δ(−→a ) = 0 = v(b) − v(c). So assume b = c. If Db ∩Dc ∩vw = ∅, we pick an arbitrary x from this set and let −→a = (b, c) ∈ SPbc, −→u = (v, x, w) ∈ Lvw . Again it is easy to check the compatibility of (−→a , −→u ). Since v ∈ Db, v(b) − v(c) ≥ δbc = δ(−→a ). For the remaining case b = c and Db ∩Dc ∩vw = ∅, notice v = w otherwise v = w ∈ Db ∩ Dc ∩ vw. So we can define λx for every point x on vw to be the unique number in [0, 1] such that x = (1 − λx)v + λxw. For convenience, we write x ≤ y for λx ≤ λy. Let Ia = Da ∩ vw for each a ∈ A. Since D = ∪a∈ADa, we have vw = ∪a∈AIa. Moreover, by the convexity of Da and vw, Ia is a (possibly trivial) closed interval. We begin by considering the case that Ib and Ic are each a single point, that is, Ib = {v} and Ic = {w}. Let S be a minimal subset of A satisfying ∪s∈SIs = vw. For each s ∈ S, Is is maximal, i.e., not contained in any other It, for t ∈ S. In particular, the intervals {Is : s ∈ S} have all left endpoints distinct and all right endpoints distinct and the order of the left endpoints is the same as that of the right endpoints. Let k = |S| + 2 and index S as a2, . . . , ak−1 in the order defined by the right endpoints. Denote the interval Iai by [li, ri]. Thus l2 < l3 < . . . < lk−1, r2 < r3 < . . . < rk−1 and the fact that these intervals cover vw implies l2 = v, rk−1 = w and for all 2 ≤ i ≤ k − 2, li+1 ≤ ri which further implies li < ri. Now we define the path −→a = (a1, a2, . . . , ak−1, ak) with a1 = b, ak = c and a2, a3, . . . , ak−1 as above. Define the linear D-sequence −→u = (u0, u1, . . . , uk) by u0 = u1 = v, uk = w and for 2 ≤ i ≤ k−1, ui = ri. It follows immediately that (−→a , −→u ) ∈ LCvw bc . Neither b nor c is in S since lb = rb and lc = rc. Thus −→a is simple. Finally to show δ(−→a ) ≤ v(b) − v(c), we note v(b) − v(c) = v(a1) − v(ak) = k−1X i=1 (v(ai) − v(ai+1)) and δ(−→a ) = ∆−→a (−→u ) = k−1X i=1 (ui(ai) − ui(ai+1)) = v(a1) − v(a2) + k−1X i=2 (ri(ai) − ri(ai+1)). For two outcomes d, e ∈ A, let us define fde(z) = z(d)−z(e) for all z ∈ D. It suffices to show faiai+1 (ri) ≤ faiai+1 (v) for 2 ≤ i ≤ k − 1. Fact 9. For d, e ∈ A, fde(z) is a linear function of z. Furthermore, if x ∈ Dd and y ∈ De with x = y, then fde(x) = x(d) − x(e) ≥ δde ≥ −δed ≥ −(y(e) − y(d)) = fde(y). Therefore fde(z) is monotonically nonincreasing along the line ←→ xy as z moves in the direction from x to y. Applying this fact with d = ai, e = ai+1, x = li and y = ri gives the desired conclusion. This completes the proof for the case that Ib = {v} and Ic = {w}. For general Ib, Ic, rb < lc otherwise Db ∩ Dc ∩ vw = Ib ∩ Ic = ∅. Let v = rb and w = lc. Clearly we can apply the above conclusion to v ∈ Db, w ∈ Dc and get a compatible pair (−→a , −→u ) ∈ LCv w bc with −→a simple and δ(−→a ) ≤ v (b) − v (c). Define the linear D-sequence −→u by u0 = v, uk = w and ui = ui for i ∈ [k − 1]. (−→a , −→u ) ∈ LCvw bc is evident. Moreover, applying the above fact with d = b, e = c, x = v and y = w, we get v(b) − v(c) ≥ v (b) − v (c) ≥ δ(−→a ). Corollary 10. For any b, c ∈ A there is a straight (b, c)path. The main result of this section (theorem 12) says that for any b, c ∈ A, every straight (b, c)-path has the same δ-weight. To prove this, we first fix v ∈ Db and w ∈ Dc and show (lemma 11) that every straight (b, c)-path compatible with some linear (v, w)-sequence has the same δ-weight ρbc(v, w). We then show in theorem 12 that ρbc(v, w) is the same for all choices of v ∈ Db and w ∈ Dc. Lemma 11. For b, c ∈ A, there is a function ρbc : Db × Dc −→ R satisfying that for any (−→a , −→u ) ∈ LCvw bc , δ(−→a ) = ρbc(v, w). Proof. Let (−→a , −→u ), (−→a , −→u ) ∈ LCvw bc . It suffices to show δ(−→a ) = δ(−→a ). To do this we construct a linear (v, w)-sequence −→u and paths −→a ∗ , −→a ∗∗ ∈ Pbc, both compatible with −→u , satisfying δ(−→a ∗ ) = δ(−→a ) and δ(−→a ∗∗ ) = δ(−→a ). Lemma 7 implies δ(−→a ∗ ) = δ(−→a ∗∗ ), which will complete the proof. Let |−→a | = ord(−→u ) = k and |−→a | = ord(−→u ) = l. We select −→u to be any linear (v, w)-sequence (u0, u1, . . . , ut) such that −→u and −→u are both subsequences of −→u , i.e., there are indices 0 = i0 < i1 < · · · < ik = t and 0 = j0 < j1 < · · · < jl = t such that −→u = (ui0 , ui1 , . . . , uik ) and −→u = (uj0 , uj1 , . . . , ujl ). We now construct a (b, c)-path −→a ∗ compatible with −→u such that δ(−→a ∗ ) = δ(−→a ). (An analogous construction gives −→a ∗∗ compatible with −→u such that δ(−→a ∗∗ ) = δ(−→a ).) This will complete the proof. −→a ∗ is defined as follows: for 1 ≤ j ≤ t, a∗ j = ar where r is the unique index satisfying ir−1 < j ≤ ir. Since both uir−1 = ur−1 and uir = ur belong to Dar , uj ∈ Dar for ir−1 ≤ j ≤ ir by the convexity of Dar . The compatibility of (−→a ∗ , −→u ) follows immediately. Clearly, a∗ 1 = a1 = b and a∗ t = ak = c, so −→a ∗ ∈ Pbc. Furthermore, as δa∗ j a∗ j+1 = δarar = 0 for each r ∈ [k], ir−1 < j < ir, δ(−→a ∗ ) = k−1X r=1 δa∗ ir a∗ ir+1 = k−1X r=1 δarar+1 = δ(−→a ). We are now ready for the main theorem of the section: Theorem 12. ρbc is a constant map on Db × Dc. Thus for any b, c ∈ A, every straight (b, c)-path has the same δweight. Proof. For a path −→a , (v, w) is compatible with −→a if there is a linear (v, w)-sequence compatible with −→a . We write CP(−→a ) for the set of pairs (v, w) compatible with −→a . ρbc is constant on CP(−→a ) because for each (v, w) ∈ CP(−→a ), ρbc(v, w) = δ(−→a ). By lemma 8, we also haveS −→a ∈SPbc CP(−→a ) = Db ×Dc. Since A is finite, SPbc, the set of simple paths from b to c, is finite as well. 290 Next we prove that for any path −→a , CP(−→a ) is closed. Let ((vn , wn ) : n ∈ N) be a convergent sequence in CP(−→a ) and let (v, w) be the limit. We want to show that (v, w) ∈ CP(−→a ). For each n ∈ N, since (vn , wn ) ∈ CP(−→a ), there is a linear (vn , wn )-sequence un compatible with −→a , i.e., there are 0 = λn 0 ≤ λn 1 ≤ . . . ≤ λn k = 1 (k = |−→a |) such that un j = (1 − λn j )vn + λn j wn (j = 0, 1, . . . , k). Since for each n, λn = (λn 0 , λn 1 , . . . , λn k ) belongs to the closed bounded set [0, 1]k+1 we can choose an infinite subset I ⊆ N such that the sequence (λn : n ∈ I) converges. Let λ = (λ0, λ1, . . . , λk) be the limit. Clearly 0 = λ0 ≤ λ1 ≤ · · · ≤ λk = 1. Define the linear (v, w)-sequence −→u by uj = (1 − λj )v + λj w (j = 0, 1, . . . , k). Then for each j ∈ {0, . . . , k}, uj is the limit of the sequence (un j : n ∈ I). For j > 0, each un j belongs to the closed set Daj , so uj ∈ Daj . Similarly, for j < k each un j belongs to the closed set Daj+1 , so uj ∈ Daj+1 . Hence (−→a , −→u ) is compatible, implying (v, w) ∈ CP(−→a ). Now we have Db × Dc covered by finitely many closed subsets on each of them ρbc is a constant. Suppose for contradiction that there are (v, w), (v , w ) ∈ Db × Dc such that ρbc(v, w) = ρbc(v , w ). L = {((1 − λ)v + λv , (1 − λ)w + λw ) : λ ∈ [0, 1]} is a line segment in Db ×Dc by the convexity of Db, Dc. Let L1 = {(x, y) ∈ L : ρbc(x, y) = ρbc(v, w)} and L2 = L − L1. Clearly (v, w) ∈ L1, (v , w ) ∈ L2. Let P = {−→a ∈ SPbc : δ(−→a ) = ρbc(v, w)}. L1 = `S −→a ∈P CP(−→a ) ´ ∩ L, L2 = S −→a ∈SPbc−P CP(−→a ) ∩ L are closed by the finiteness of P. This is a contradiction, since it is well known (and easy to prove) that a line segment can not be expressed as the disjoint union of two nonempty closed sets. Summarizing corollary 10, lemma 11 and theorem 12, we have Corollary 13. For any b, c ∈ A, there is a real number ρbc with the property that (1) There is at least one straight (b, c)-path of δ-weight ρbc and (2) Every straight (b, c)-path has δ-weight ρbc. 6. PROOF OF THEOREM 4 Lemma 14. ρbc ≤ δbc for all b, c ∈ A. Proof. For contradiction, suppose ρbc − δbc = > 0. By the definition of δbc, there exists v ∈ f−1 (b) ⊆ Db with v(b) − v(c) < δbc + = ρbc. Pick an arbitrary w ∈ Dc. By lemma 8, there is a compatible pair (−→a , −→u ) ∈ LCvw bc with δ(−→a ) ≤ v(b) − v(c). Since −→a is a straight (b, c)-path, ρbc = δ(−→a ) ≤ v(b) − v(c), leading to a contradiction. Define another edge-weighted complete directed graph Gf on vertex set A where the weight of arc (a, b) is ρab. Immediately from lemma 14, the weight of every directed cycle in Gf is bounded below by its weight in Gf . To prove theorem 4, it suffices to show the zero cycle property of Gf , i.e., every directed cycle has weight zero. We begin by considering two-cycles. Lemma 15. ρbc + ρcb = 0 for all b, c ∈ A. Proof. Let −→a be a straight (b, c)-path compatible with linear sequence −→u . let −→a be the reverse of −→a and −→u the reverse of −→u . Obviously, (−→a , −→u ) is compatible as well and thus −→a is a straight (c, b)-path. Therefore, ρbc + ρcb = δ(−→a ) + δ(−→a ) = k−1X i=1 δaiai+1 + k−1X i=1 δai+1ai = k−1X i=1 (δaiai+1 + δai+1ai ) = 0, where the final equality uses proposition 5. Next, for three cycles, we first consider those compatible with linear triples. Lemma 16. If there are collinear points u ∈ Da, v ∈ Db, w ∈ Dc (a, b, c ∈ A), ρab + ρbc + ρca = 0. Proof. First, we prove for the case where v is between u and w. From lemma 8, there are compatible pairs (−→a , −→u ) ∈ LCuv ab , (−→a , −→u ) ∈ LCvw bc . Let |−→a | = ord(−→u ) = k and |−→a | = ord(−→u ) = l. We paste −→a and −→a together as −→a = (a = a1, a2, . . . , ak−1, ak, a1 , . . . , al = c), −→u and −→u as −→u = (u = u0, u1, . . . , uk = v = u0 , u1 , . . . , ul = w). Clearly (−→a , −→u ) ∈ LCuw ac and δ(−→a ) = k−1X i=1 δaiai+1 + δak a1 + l−1X i=1 δai ai+1 = δ(−→a ) + δbb + δ(−→a ) = δ(−→a ) + δ(−→a ). Therefore, ρac = δ(−→a ) = δ(−→a ) + δ(−→a ) = ρab + ρbc. Moreover, ρac = −ρca by lemma 15, so we get ρab + ρbc + ρca = 0. Now suppose w is between u and v. By the above argument, we have ρac + ρcb + ρba = 0 and by lemma 15, ρab + ρbc + ρca = −ρba − ρcb − ρac = 0. The case that u is between v and w is similar. Now we are ready for the zero three-cycle property: Lemma 17. ρab + ρbc + ρca = 0 for all a, b, c ∈ A. Proof. Let S = {(a, b, c) : ρab + ρbc + ρca = 0} and for contradiction, suppose S = ∅. S is finite. For each a ∈ A, choose va ∈ Da arbitrarily and let T be the convex hull of {va : a ∈ A}. For each (a, b, c) ∈ S, let Rabc = Da × Db × Dc ∩ T3 . Clearly, each Rabc is nonempty and compact. Moreover, by lemma 16, no (u, v, w) ∈ Rabc is collinear. Define f : D3 → R by f(u, v, w) = |v−u|+|w−v|+|u−w|. For (a, b, c) ∈ S, the restriction of f to the compact set Rabc attains a minimum m(a, b, c) at some point (u, v, w) ∈ Rabc by the continuity of f, i.e., there exists a triangle ∆uvw of minimum perimeter within T with u ∈ Da, v ∈ Db, w ∈ Dc. Choose (a∗ , b∗ , c∗ ) ∈ S so that m(a∗ , b∗ , c∗ ) is minimum and let (u∗ , v∗ , w∗ ) ∈ Ra∗b∗c∗ be a triple achieving it. Pick an arbitrary point p in the interior of ∆u∗ v∗ w∗ . By the convexity of domain D, there is d ∈ A such that p ∈ Dd. 291 Consider triangles ∆u∗ pw∗ , ∆w∗ pv∗ and ∆v∗ pu∗ . Since each of them has perimeter less than that of ∆u∗ v∗ w∗ and all three triangles are contained in T, by the minimality of ∆u∗ v∗ w∗ , (a∗ , d, c∗ ), (c∗ , d, b∗ ), (b∗ , d, a∗ ) ∈ S. Thus ρa∗d + ρdc∗ + ρc∗a∗ = 0, ρc∗d + ρdb∗ + ρb∗c∗ = 0, ρb∗d + ρda∗ + ρa∗b∗ = 0. Summing up the three equalities, (ρa∗d + ρdc∗ + ρc∗d + ρdb∗ + ρb∗d + ρda∗ ) +(ρc∗a∗ + ρb∗c∗ + ρa∗b∗ ) = 0, which yields a contradiction ρa∗b∗ + ρb∗c∗ + ρc∗a∗ = 0. With the zero two-cycle and three-cycle properties, the zero cycle property of Gf is immediate. As noted earlier, this completes the proof of theorem 4. Theorem 18. Every directed cycle of Gf has weight zero. Proof. Clearly, zero two-cycle and three-cycle properties imply triangle equality ρab +ρbc = ρac for all a, b, c ∈ A. For a directed cycle C = a1a2 . . . aka1, by inductively applying triangle equality, we have Pk−1 i=1 ρaiai+1 = ρa1ak . Therefore, the weight of C is k−1X i=1 ρaiai+1 + ρaka1 = ρa1ak + ρaka1 = 0. As final remarks, we note that our result implies the following strengthenings of theorem 12: Corollary 19. For any b, c ∈ A, every admissible (b, c)path has the same δ-weight ρbc. Proof. First notice that for any b, c ∈ A, if Db ∩Dc = ∅, δbc = ρbc. To see this, pick v ∈ Db ∩ Dc arbitrarily. Obviously, path −→a = (b, c) is compatible with linear sequence −→u = (v, v, v) and is thus a straight (b, c)-path. Hence ρbc = δ(−→a ) = δbc. Now for any b, c ∈ A and any (b, c)-path −→a with C(−→a ) = ∅, let −→u ∈ C(−→a ). Since ui ∈ Dai ∩ Dai+1 for i ∈ [|−→a | − 1], δ(−→a ) = |−→a |−1 X i=1 δaiai+1 = |−→a |−1 X i=1 ρaiai+1 , which by theorem 18, = −ρa|−→a |a1 = ρa1a|−→a | = ρbc. Corollary 20. For any b, c ∈ A, ρbc is equal to δ∗ bc, the minimum δ-weight over all (b, c)-paths. Proof. Clearly ρbc ≥ δ∗ bc by corollary 13. On the other hand, for every (b, c)-path −→a = (b = a1, a2, . . . , ak = c), by lemma 14, δ(−→a ) = k−1X i=1 δaiai+1 ≥ k−1X i=1 ρaiai+1 , which by theorem 18, = −ρaka1 = ρa1ak = ρbc. Hence ρbc ≤ δ∗ bc, which completes the proof. 7. COUNTEREXAMPLES TO STRONGER FORMS OF THEOREM 4 Theorem 4 applies to social choice functions with convex domain and finite range. We now show that neither of these hypotheses can be omitted. Our examples are single player functions. The first example illustrates that convexity can not be omitted. We present an untruthful single player social choice function with three outcomes a, b, c satisfying W-MON on a path-connected but non-convex domain. The domain is the boundary of a triangle whose vertices are x = (0, 1, −1), y = (−1, 0, 1) and z = (1, −1, 0). x and the open line segment zx is assigned outcome a, y and the open line segment xy is assigned outcome b, and z and the open line segment yz is assigned outcome c. Clearly, δab = −δba = δbc = −δcb = δca = −δac = −1, W-MON (the nonnegative twocycle property) holds. Since there is a negative cycle δab + δbc + δca = −3, by lemma 3, this is not a truthful choice function. We now show that the hypothesis of finite range can not be omitted. We construct a family of single player social choice functions each having a convex domain and an infinite number of outcomes, and satisfying weak monotonicity but not truthfulness. Our examples will be specified by a positive integer n and an n × n matrix M satisfying the following properties: (1) M is non-singular. (2) M is positive semidefinite. (3) There are distinct i1, i2, . . . , ik ∈ [n] satisfying k−1X j=1 (M(ij, ij) − M(ij , ij+1)) + (M(ik, ik) − M(ik, i1)) < 0. Here is an example matrix with n = 3 and (i1, i2, i3) = (1, 2, 3): 0 @ 0 1 −1 −1 0 1 1 −1 0 1 A Let e1, e2, . . . , en denote the standard basis of Rn . Let Sn denote the convex hull of {e1, e2 . . . , en}, which is the set of vectors in Rn with nonnegative coordinates that sum to 1. The range of our social choice function will be the set Sn and the domain D will be indexed by Sn, that is D = {yλ : λ ∈ Sn}, where yλ is defined below. The function f maps yλ to λ. Next we specify yλ. By definition, D must be a set of functions from Sn to R. For λ ∈ Sn, the domain element yλ : Sn −→ R is defined by yλ(α) = λT Mα. The nonsingularity of M guarantees that yλ = yµ for λ = µ ∈ Sn. It is easy to see that D is a convex subset of the set of all functions from Sn to R. The outcome graph Gf is an infinite graph whose vertex set is the outcome set A = Sn. For outcomes λ, µ ∈ A, the edge weight δλµ is equal to δλµ = inf{v(λ) − v(µ) : f(v) = λ} = yλ(λ) − yλ(µ) = λT Mλ − λT Mµ = λT M(λ − µ). We claim that Gf satisfies the nonnegative two-cycle property (W-MON) but has a negative cycle (and hence is not truthful). For outcomes λ, µ ∈ A, δλµ +δµλ = λT M(λ−µ)+µT M(µ−λ) = (λ−µ)T M(λ−µ), 292 which is nonnegative since M is positive semidefinite. Hence the nonnegative two-cycle property holds. Next we show that Gf has a negative cycle. Let i1, i2, . . . , ik be a sequence of indices satisfying property 3 of M. We claim ei1 ei2 . . . eik ei1 is a negative cycle. Since δeiej = eT i M(ei − ej) = M(i, i) − M(i, j) for any i, j ∈ [k], the weight of the cycle k−1X j=1 δeij eij+1 + δeik ei1 = k−1X j=1 (M(ij , ij ) − M(ij, ij+1)) + (M(ik, ik) − M(ik, i1)) < 0, which completes the proof. Finally, we point out that the third property imposed on the matrix M has the following interpretation. Let R(M) = {r1, r2, . . . , rn} be the set of row vectors of M and let hM be the single player social choice function with domain R(M) and range {1, 2, . . . , n} mapping ri to i. Property 3 is equivalent to the condition that the outcome graph GhM has a negative cycle. By lemma 3, this is equivalent to the condition that hM is untruthful. 8. FUTURE WORK As stated in the introduction, the goal underlying the work in this paper is to obtain useful and general characterizations of truthfulness. Let us say that a set D of P × A real valuation matrices is a WM-domain if any social choice function on D satisfying weak monotonicity is truthful. In this paper, we showed that for finite A, any convex D is a WM-domain. Typically, the domains of social choice functions considered in mechanism design are convex, but there are interesting examples with non-convex domains, e.g., combinatorial auctions with unknown single-minded bidders. It is intriguing to find the most general conditions under which a set D of real matrices is a WM-domain. We believe that convexity is the main part of the story, i.e., a WM-domain is, after excluding some exceptional cases, essentially a convex set. Turning to parametric representations, let us say a set D of P × A matrices is an AM-domain if any truthful social choice function with domain D is an affine maximizer. Roberts" theorem says that the unrestricted domain is an AM-domain. What are the most general conditions under which a set D of real matrices is an AM-domain? Acknowledgments We thank Ron Lavi for helpful discussions and the two anonymous referees for helpful comments. 9. REFERENCES [1] A. Archer and E. Tardos. Truthful mechanisms for one-parameter agents. In IEEE Symposium on Foundations of Computer Science, pages 482-491, 2001. [2] Y. Bartal, R. Gonen, and N. Nisan. Incentive compatible multi unit combinatorial auctions. In TARK "03: Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, pages 72-87. ACM Press, 2003. [3] S. Bikhchandani, S. Chatterjee, and A. Sen. Incentive compatibility in multi-unit auctions. Technical report, UCLA Department of Economics, Dec. 2004. [4] A. Goldberg, J. Hartline, A. Karlin, M. Saks and A. Wright. Competitive Auctions, 2004. [5] H. Gui, R. Muller, and R. Vohra. Dominant strategy mechanisms with multidimensional types. Technical Report 047, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization, 2004. available at http://ideas.repec.org/p/dgr/umamet/2004047.html. [6] R. Lavi, A. Mu"alem, and N. Nisan. Towards a characterization of truthful combinatorial auctions. In FOCS "03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, page 574. IEEE Computer Society, 2003. [7] D. Lehmann, L. O"Callaghan, and Y. Shoham. Truth revelation in approximately efficient combinatorial auctions. J. ACM, 49(5):577-602, 2002. [8] A. Mas-Colell, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995. [9] N. Nisan. Algorithms for selfish agents. Lecture Notes in Computer Science, 1563:1-15, 1999. [10] K. Roberts. The characterization of implementable choice rules. Aggregation and Revelation of Preferences, J-J. Laffont (ed.), North Holland Publishing Company. [11] J.-C. Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16:191-200, 1987. [12] I. Rozenshtrom. Dominant strategy implementation with quasi-linear preferences. Master"s thesis, Dept. of Economics, The Hebrew University, Jerusalem, Israel, 1999. 293
social choice function weak monotonicity convex domain truthful implementation recognition algorithm nonnegative cycle property truthfulness affine maximizer dominant strategy mechanism design strategyproof truthful
individual preference non-truthful function