Negotiation-Range Mechanisms: Exploring the Limits of Truthful Efficient Markets Yair Bartal ∗ School of Computer Science and Engineering The Hebrew University of Jerusalem, Israel yair@cs.huji.ac.il Rica Gonen School of Computer Science and Engineering The Hebrew University of Jerusalem, Israel rgonen@cs.huji.ac.il Pierfrancesco La Mura Leipzig Graduate School of Management Leipzig, Germany plamura@hhl.de ABSTRACT This paper introduces a new class of mechanisms based on negotiation between market participants. This model allows us to circumvent Myerson and Satterthwaite"s impossibility result and present a bilateral market mechanism that is efficient, individually rational, incentive compatible and budget balanced in the single-unit heterogeneous setting. The underlying scheme makes this combination of desirable qualities possible by reporting a price range for each buyer-seller pair that defines a zone of possible agreements, while the final price is left open for negotiation. Categories and Subject Descriptors J.4 [Social and Behavioral Sciences]: Economics; K.4.4 [Computers and Society]: Electronic Commerce-payment schemes General Terms Algorithms, Economics, Theory 1. INTRODUCTION In this paper we introduce the concept of negotiation based mechanisms in the context of the theory of efficient truthful markets. A market consists of multiple buyers and sellers who wish to exchange goods. The market"s main objective is to produce an allocation of sellers" goods to buyers as to maximize the total gain from trade. A commonly studied model of participant behavior is taken from the field of economic mechanism design [3, 4, 11]. In this model each player has a private valuation function that assigns real values to each possible allocation. The algorithm motivates players to participate truthfully by handing payments to them. The mechanism in an exchange collects buyer bids and seller bids and clears the exchange by computing:(i) a set of trades, and (ii) the payments made and received by players. In designing a mechanism to compute trades and payments we must consider the bidding strategies of self-interested players, i.e. rational players that follow expected-utility maximizing strategies. We set allocative efficiency as our primary goal. That is the mechanism must compute a set of trades that maximizes gain from trade. In addition we require individual rationality (IR) so that all players have positive expected utility to participate, budget balance (BB) so that the exchange does not run at a loss, and incentive compatibility (IC) so that reporting the truth is a dominant strategy for each player. Unfortunately, Myerson and Satterthwaite"s (1983) well known result demonstrates that in bilateral trade it is impossible to simultaneously achieve perfect efficiency, BB, and IR using an IC mechanism [10]. A unique approach to overcome Myerson and Satterthwaite"s impossibility result was attempted by Parkes, Kalagnanam and Eso [12]. This result designs both a regular and a combinatorial bilateral trade mechanism (which imposes BB and IR) that approximates truth revelation and allocation efficiency. In this paper we circumvent Myerson and Satterthwaite"s impossibility result by introducing a new model of negotiationrange markets. A negotiation-range mechanism does not produce payment prices for the market participants. Rather, is assigns each buyer-seller pair a price range, called Zone Of Possible Agreements (ZOPA). The buyer is provided with the high end of the range and the seller with the low end of the range. This allows the trading parties to engage in negotiation over the final price with guarantee that the deal is beneficial for both of them. The negotiation process is not considered part of the mechanism but left up to the interested parties, or to some external mechanism to perform. In effect a negotiation-range mechanism operates as a mediator between the market participants, offering them the grounds to be able to finalize the terms of the trade by themselves. This concept is natural to many real-world market environments such as the real estate market. 1 We focus on the single-unit heterogeneous setting: n sellers offer one unique good each by placing sealed bids specifying their willingness to sell, and m buyers, interested in buying a single good each, placing sealed bids specifying their willingness to pay for each good they may be interested in. Our main result is a single-unit heterogeneous bilateral trade negotiation-range mechanism (ZOPAS) that is efficient, individually rational, incentive compatible and budget balanced. Our result does not contradict Myerson and Satterthwaite"s important theorem. Myerson-Satterthwaite"s proof relies on a theorem assuring that in two different efficient IC markets; if the sellers have the same upper bound utility then they will receive the same prices in each market and if the buyers have the same lower bound utility then they will receive the same prices in each market. Our single-unit heterogeneous mechanism bypasses Myerson and Satterthwaite"s theorem by producing a price range, defined by a seller"s floor and a buyer"s ceiling, for each pair of matched players. In our market mechanism the seller"s upper bound utility may be the same while the seller"s floor is different and the buyer"s lower bound utility may be the same while the buyer"s ceiling is different. Moreover, the final price is not fixed by the mechanism at all. Instead, it is determined by an independent negotiation between the buyer and seller. More specifically, in a negotiation-range mechanism, the range of prices each matched pair is given is resolved by a negotiation stage where a final price is determined. This negotiation stage is crucial for our mechanism to be IC. Intuitively, a negotiation range mechanism is incentive compatible if truth telling promises the best ZOPA from the point of view of the player in question. That is, he would tell the truth if this strategy maximizes the upper and lower bounds on his utility as expressed by the ZOPA boundaries. Yet, when carefully examined it turns out that it is impossible (by [10]) that this goal will always hold. This is simply because such a mechanism could be easily modified to determine final prices for the players (e.g. by taking the average of the range"s boundaries). Here, the negotiation stage come into play. We show that if the above utility maximizing condition does not hold then it is the case that the player cannot influence the negotiation bound that is assigned to his deal partner no matter what value he declares. This means that the only thing that he may achieve by reporting a false valuation is modifying his own negotiation bound, something that he could alternatively achieve by reporting his true valuation and incorporating the effect of the modified negotiation bound into his negotiation strategy. This eliminates the benefit of reporting false valuations and allows our mechanism to compute the optimal gain from trade according to the players" true values. The problem of computing the optimal allocation which maximizes gain from trade can be conceptualized as the problem of finding the maximum weighted matching in a weighted bipartite graph connecting buyers and sellers, where each edge in the graph is assigned a weight equal to the difference between the respective buyer bid and seller bid. It is well known that this problem can be solved efficiently in polynomial time. VCG IC payment schemes [2, 7, 13] support efficient and IR bilateral trade but not simultaneously BB. Our particular approach adapts the VCG payment scheme to achieve budget balance. The philosophy of the VCG payment schemes in bilateral trade is that the buyer pays the seller"s opportunity cost of not selling the good to another buyer and not keeping the good to herself. The seller is paid in addition to the buyer"s price a compensation for the damage the mechanism did to the seller by not extracting the buyer"s full bid. Our philosophy is a bit different: The seller is paid at least her opportunity cost of not selling the good to another buyer and not keeping the good for herself. The buyer pays at most his alternate seller"s opportunity cost of not selling the good to another buyer and not keeping the alternate good for herself. The rest of this paper is organized as follows. In Section 2 we describe our model and definitions. In section 3 we present the single-unit heterogeneous negotiation-range mechanism and show that it is efficient, IR, IC and BB. Finally, we conclude with a discussion in Section 4. 2. NEGOTIATION MARKETS PRELIMINARIES Let Π denote the set of players, N the set of n selling players, and M the set of m buying players, where Π = N ∪ M. Let Ψ = {1, ..., t} denote the set of goods. Let Ti ∈ {−1, 0, 1}t denote an exchange vector for a trade, such that player i buys goods {A ∈ Ψ|Ti (A) = 1} and sells goods {A ∈ Ψ|Ti (A) = −1}. Let T = (T1, ..., T|Π|) denote the complete trade between all players. We view T as describing the allocation of goods by the mechanism to the buyers and sellers. In the single-unit heterogeneous setting every good belongs to specific seller, and every buyer is interested in buying one good. The buyer may bid for several or all goods. At the end of the auction every good is either assigned to one of the buyers who bid for it or kept unsold by the seller. It is convenient to assume the sets of buyers and sellers are disjoint (though it is not required), i.e. N ∩ M = ∅. Each seller i is associated with exactly one good Ai, for which she has true valuation ci which expresses the price at which it is beneficial for her to sell the good. If the seller reports a false valuation at an attempt to improve the auction results for her, this valuation is denoted ˆci. A buyer has a valuation vector describing his valuation for each of the goods according to their owner. Specifically, vj(k) denotes buyer j"s valuation for good Ak. Similarly, if he reports a false valuation it is denoted ˆvj(k). If buyer j is matched by the mechanism with seller i then Ti(Ai) = −1 and Tj(Ai) = 1. Notice, that in our setting for every k = i, Ti(Ak) = 0 and Tj(Ai) = 0 and also for every z = j, Tz(Ai) = 0. For a matched buyer j - seller i pair, the gain from trade on the deal is defined as vj(i) − ci. Given and allocation T, the gain from trade associated with T is V = j∈M,i∈N (vj(i) − ci) · Tj(Ai). Let T∗ denote the optimal allocation which maximizes the gain from trade, computed according to the players" true valuations. Let V ∗ denote the optimal gain from trade associated with this allocation. When players" report false valuations we use ˆT∗ and ˆV ∗ to denote the optimal allocation and gain from trade, respectively, when computed according to the reported valuations. 2 We are interested in the design of negotiation-range mechanisms. In contrast to a standard auction mechanism where the buyer and seller are provided with the prices they should pay, the goal of a negotiation-range mechanism is to provide the player"s with a range of prices within which they can negotiate the final terms of the deal by themselves. The mechanism would provide the buyer with the upper bound on the range and the seller with the lower bound on the range. This gives each of them a promise that it will be beneficial for them to close the deal, but does not provide information about the other player"s terms of negotiation. Definition 1. Negotiation Range: Zone Of Possible Agreements, ZOPA, between a matched buyer and seller. The ZOPA is a range, (L, H), 0 ≤ L ≤ H, where H is an upper bound (ceiling) price for the buyer and L is a lower bound (floor) price for the seller. Definition 2. Negotiation-Range Mechanism: A mechanism that computes a ZOPA, (L, H), for each matched buyer and seller in T∗ , and provides the buyer with the upper bound H and the seller with the lower bound L. The basic assumption is that participants in the auction are self-interested players. That is their main goal is to maximize their expected utility. The utility for a buyer who does not participate in the trade is 0. If he does win some good, his utility is the surplus between his valuation for that good and the price he pays. For a seller, if she keeps the good unsold, her utility is just her valuation of the good, and the surplus is 0. If she gets to sell it, her utility is the price she is paid for it, and the surplus is the difference between this price and her valuation. Since negotiation-range mechanisms assign bounds on the range of prices rather than the final price, it is useful to define the upper and lower bounds on the player"s utilities defined by the range"s limits. Definition 3. Consider a buyer j - seller i pair matched by a negotiation-range mechanism and let (L, H) be their associated negotiation range. • The buyer"s top utility is: vj(i) − L, and the buyer"s bottom utility is vj(i) − H. • The seller"s top utility is H, with surplus H − ci, and the seller"s bottom utility is L, with surplus L − ci. 3. THE SINGLE-UNIT HETEROGENEOUS MECHANISM (ZOPAS) 3.1 Description of the Mechanism ZOPAS is a negotiation-range mechanism, it finds the optimal allocation T∗ and uses it to define a ZOPA for each buyer-seller pair. The first stage in applying the mechanism is for the buyers and sellers to submit their sealed bids. The mechanism then allocates buyers to sellers by computing the allocation T ∗ , which results in the optimal gain from trade V ∗ , and defines a ZOPA for each buyer-seller pair. Finally, buyers and sellers use the ZOPA to negotiate a final price. Computing T∗ involves solving the maximum weighted bipartite matching problem for the complete bipartite graph Kn,m constructed by placing the buyers on one side of the Find the optimal allocation T ∗ Compute the maximum weighted bipartite matching for the bipartite graph of buyers and sellers, and edge weights equal to the gain from trade. Calculate Sellers" Floors For every buyer j, allocated good Ai Find the optimal allocation (T−j)∗ Li = vj(i) + (V−j)∗ − V ∗ Calculate Buyers" Ceilings For every buyer j, allocated good Ai Find the optimal allocation (T −i )∗ Find the optimal allocation (T −i −j )∗ Hj = vj(i) + (V −i −j )∗ − (V −i )∗ Negotiation Phase For every buyer j and every seller i of good Ai Report to seller i her floor Li and identify her matched buyer j Report to buyer j his ceiling Hj and identify his matched seller i i, j negotiate the good"s final price Figure 1: The ZOPAS mechanism graph, the seller on another and giving the edge between buyer j and seller i weight equal to vj(i) − ci. The maximum weighted matching problem in solvable in polynomial time (e.g., using the Hungarian Method). This results in a matching between buyers and sellers that maximizes gain from trade. The next step is to compute for each buyer-seller pair a seller"s floor, which provides the lower bound of the ZOPA for this pair, and assigns it to the seller. A seller"s floor is computed by calculating the difference between the total gain from trade when the buyer is excluded and the total gain from trade of the other participants when the buyer is included (the VCG principle). Let (T−j)∗ denote the gain from trade of the optimal allocation when buyer j"s bids are discarded. Denote by (V−j)∗ the total gain from trade in the allocation (T−j)∗ . Definition 4. Seller Floor: The lowest price the seller should expect to receive, communicated to the seller by the mechanism. The seller floor for player i who was matched with buyer j on good Ai, i.e., Tj(Ai) = 1, is computed as: Li = vj(i) + (V−j)∗ − V ∗ . The seller is instructed not to accept less than this price from her matched buyer. Next, the mechanism computes for each buyer-seller pair a buyer ceiling, which provides the upper bound of the ZOPA for this pair, and assigns it to the buyer. Each buyer"s ceiling is computed by removing the buyer"s matched seller and calculating the difference between the total gain from trade when the buyer is excluded and the total gain from trade of the other participants when the 3 buyer is included. Let (T−i )∗ denote the gain from trade of the optimal allocation when seller i is removed from the trade. Denote by (V −i )∗ the total gain from trade in the allocation (T−i )∗ . Let (T−i −j )∗ denote the gain from trade of the optimal allocation when seller i is removed from the trade and buyer j"s bids are discarded. Denote by (V −i −j )∗ the total gain from trade in the allocation (T −i −j )∗ . Definition 5. Buyer Ceiling: The highest price the seller should expect to pay, communicated to the buyer by the mechanism. The buyer ceiling for player j who was matched with seller i on good Ai, i.e., Tj(Ai) = 1, is computed as: Hj = vj(i) + (V −i −j )∗ − (V −i )∗ . The buyer is instructed not to pay more than this price to his matched seller. Once the negotiation range lower bound and upper bound are computed for every matched pair, the mechanism reports the lower bound price to the seller and the upper bound price to the buyer. At this point each buyer-seller pair negotiates on the final price and concludes the deal. A schematic description the ZOPAS mechanism is given in Figure 3.1. 3.2 Analysis of the Mechanism In this section we analyze the properties of the ZOPAS mechanism. Theorem 1. The ZOPAS market negotiation-range mechanism is an incentive-compatible bilateral trade mechanism that is efficient, individually rational and budget balanced. Clearly ZOPAS is an efficient polynomial time mechanism. Let us show it satisfies the rest of the properties in the theorem. Claim 1. ZOPAS is individually rational, i.e., the mechanism maintains nonnegative utility surplus for all participants. Proof. If a participant does not trade in the optimal allocation then his utility surplus is zero by definition. Consider a pair of buyer j and seller i which are matched in the optimal allocation T ∗ . Then the buyer"s utility is at least vj(i) − Hj. Recall that Hj = vj(i) + (V −i −j )∗ − (V −i )∗ , so that vj(i) − Hj = (V −i )∗ − (V −i −j )∗ . Since the optimal gain from trade which includes j is higher than that which does not, we have that the utility is nonnegative: vj(i) − Hj ≥ 0. Now, consider the seller i. Her utility surplus is at least Li − ci. Recall that Li = vj(i) + (V−j)∗ − V ∗ . If we removed from the optimal allocation T ∗ the contribution of the buyer j - seller i pair, we are left with an allocation which excludes j, and has value V ∗ − (vj(i) − ci). This implies that (V−j)∗ ≥ V ∗ − vj(i) + ci, which implies that Li − ci ≥ 0. The fact that ZOPAS is a budget-balanced mechanism follows from the following lemma which ensures the validity of the negotiation range, i.e., that every seller"s floor is below her matched buyer"s ceiling. This ensures that they can close the deal at a final price which lies in this range. Lemma 1. For every buyer j- seller i pair matched by the mechanism: Li ≤ Hj. Proof. Recall that Li = vj(i) + (V−j)∗ − V ∗ and Hj = vj(i)+(V −i −j )∗ −(V −i )∗ . To prove that Li ≤ Hj it is enough to show that (V −i )∗ + (V−j)∗ ≤ V ∗ + (V −i −j )∗ . (1) The proof of (1) is based on a method which we apply several times in our analysis. We start with the allocations (T−i )∗ and (T−j)∗ which together have value equal to (V −i )∗ + (V−j)∗ . We now use them to create a pair of new valid allocations, by using the same pairs that were matched in the original allocations. This means that the sum of values of the new allocations is the same as the original pair of allocations. We also require that one of the new allocations does not include buyer j or seller i. This means that the sum of values of these new allocations is at most V ∗ + (V −i −j )∗ , which proves (1). Let G be the bipartite graph where the nodes on one side of G represent the buyers and the nodes on the other side represent the sellers, and edge weights represent the gain from trade for the particular pair. The different allocations represent bipartite matchings in G. It will be convenient for the sake of our argument to think of the edges that belong to each of the matchings as being colored with a specific color representing this matching. Assign color 1 to the edges in the matching (T −i )∗ and assign color 2 to the edges in the matching (T−j)∗ . We claim that these edges can be recolored using colors 3 and 4 so that the new coloring represents allocations T (represented by color 3) and (T−i −j ) (represented by color 4). This implies the that inequality (1) holds. Figure 2 illustrates the graph G and the colorings of the different matchings. Define an alternating path P starting at j. Let S1 be the seller matched to j in (T −i )∗ (if none exists then P is empty). Let B1 be the buyer matched to S1 in (T−j)∗ , S2 be the seller matched to B1 in (T−i )∗ , B2 be the buyer matched to S2 in (T−j)∗ , and so on. This defines an alternating path P, starting at j, whose edges" colors alternate between colors 1 and 2 (starting with 1). This path ends either in a seller who is not matched in (T−j)∗ or in a buyer who is not matched in (T−i )∗ . Since all sellers in this path are matched in (T−i )∗ , we have that seller i does not belong to P. This ensures that edges in P may be colored by alternating colors 3 and 4 (starting with 3). Since except for the first edge, all others do not involve i or j and thus may be colored 4 and be part of an allocation (T −i −j ) . We are left to recolor the edges that do not belong to P. Since none of these edges includes j we have that the edges that were colored 1, which are part of (T −i )∗ , may now be colored 4, and be included in the allocation (T −i −j ) . It is also clear that the edges that were colored 2, which are part of (T−j)∗ , may now be colored 3, and be included in the allocation T . This completes the proof of the lemma. 3.3 Incentive Compatibility The basic requirement in mechanism design is for an exchange mechanism to be incentive compatible. This means that its payment structure enforces that truth-telling is the players" weakly dominant strategy, that is that the strategy by which the player is stating his true valuation results 4 ... jS1 S2 B1 S3 B2 B3S4 S5 B4 S6 B5 S8 B7 S7 B6 ... Figure 2: Alternating path argument for Lemma 1 (Validity of the Negotiation Range) and Claim 2 (part of Buyer"s IC proof) Colors Bidders 1 32 4 UnmatchedMatched Figure 3: Key to Figure 2 in bigger or equal utility as any other strategy. The utility surplus is defined as the absolute difference between the player"s bid and his price. Negotiation-range mechanisms assign bounds on the range of prices rather than the final price and therefore the player"s valuation only influences the minimum and maximum bounds on his utility. For a buyer the minimum (bottom) utility would be based on the top of the negotiation range (ceiling), and the maximum (top) utility would be based on the bottom of the negotiation range (floor). For a seller it"s the other way around. Therefore the basic natural requirement from negotiation-range mechanisms would be that stating the player"s true valuation results in both the higher bottom utility and higher top utility for the player, compared with other strategies. Unfortunately, this requirement is still too strong and it is impossible (by [10]) that this will always hold. Therefore we slightly relax it as follows: we require this holds when the false valuation based strategy changes the player"s allocation. When the allocation stays unchanged we require instead that the player would not be able to change his matched player"s bound (e.g. a buyer cannot change the seller"s floor). This means that the only thing he can influence is his own bound, something that he can alternatively achieve through means of negotiation. The following formally summarizes our incentive compatibility requirements from the negotiation-range mechanism. Buyer"s incentive compatibility: • Let j be a buyer matched with seller i by the mechanism according to valuation vj and the negotiationrange assigned is (Li, Hj). Assume that when the mechanism is applied according to valuation ˆvj, seller k = i is matched with j and the negotiation-range assigned is (ˆLk, ˆHj). Then vj(i) − Hj ≥ vj(k) − ˆHj. (2) vj(i) − Li ≥ vj(k) − ˆLk. (3) • Let j be a buyer not matched by the mechanism according to valuation vj. Assume that when the mechanism is applied according to valuation ˆvj, seller k = i is matched with j and the negotiation-range assigned is (ˆLk, ˆHj). Then vj(k) − ˆHj ≤ vj(k) − ˆLk ≤ 0. (4) • Let j be a buyer matched with seller i by the mechanism according to valuation vj and let the assigned bottom of the negotiation range (seller"s floor) be Li. Assume that when the mechanism is applied according to valuation ˆvj, the matching between i and j remains unchanged and let the assigned bottom of the negotiation range (seller"s floor) be ˆLi. Then, ˆLi = Li. (5) Notice that the first inequality of (4) always holds for a valid negotiation range mechanism (Lemma 1). Seller"s incentive compatibility: • Let i be a seller not matched by the mechanism according to valuation ci. Assume that when the mechanism 5 is applied according to valuation ˆci, buyer z = j is matched with i and the negotiation-range assigned is (ˆLi, ˆHz). Then ˆLi − ci ≤ ˆHz − ci ≤ 0. (6) • Let i be a buyer matched with buyer j by the mechanism according to valuation ci and let the assigned top of the negotiation range (buyer"s ceiling) be Hj. Assume that when the mechanism is applied according to valuation ˆci, the matching between i and j remains unchanged and let the assigned top of the negotiation range (buyer"s ceiling) be ˆHj. Then, ˆHj = Hj. (7) Notice that the first inequality of (6) always holds for a valid negotiation range mechanism (Lemma 1). Observe that in the case of sellers in our setting, the case expressed by requirement (6) is the only case in which the seller may change the allocation to her benefit. In particular, it is not possible for seller i who is matched in T ∗ to change her buyer by reporting a false valuation. This fact simply follows from the observation that reducing the seller"s valuation increases the gain from trade for the current allocation by at least as much than any other allocation, whereas increasing the seller"s valuation decreases the gain from trade for the current allocation by exactly the same amount as any other allocation in which it is matched. Therefore, the only case the optimal allocation may change is when in the new allocation i is not matched in which case her utility surplus is 0. Theorem 2. ZOPAS is an incentive compatible negotiationrange mechanism. Proof. We begin with the incentive compatibility for buyers. Consider a buyer j who is matched with seller i according to his true valuation v. Consider that j is reporting instead a false valuation ˆv which results in a different allocation in which j is matched with seller k = i. The following claim shows that a buyer j which changed his allocation due to a false declaration of his valuation cannot improve his top utility. Claim 2. Let j be a buyer matched to seller i in T ∗ , and let k = i be the seller matched to j in ˆT∗ . Then, vj(i) − Hj ≥ vj(k) − ˆHj. (8) Proof. Recall that Hj = vj(i) + (V −i −j )∗ − (V −i )∗ and ˆHj = ˆvj(k) + ( ˆV −k −j )∗ − ( ˆV −k )∗ . Therefore, vj(i) − Hj = (V −i )∗ − (V −i −j )∗ and vj(k) − ˆHj = vj(k) − ˆvj(k) + ( ˆV −k )∗ − ( ˆV −k −j )∗ . It follows that in order to prove (8) we need to show ( ˆV −k )∗ + (V −i −j )∗ ≤ (V −i )∗ + ( ˆV −k −j )∗ + ˆvj(k) − vj(k). (9) Consider first the case were j is matched to i in ( ˆT−k )∗ . If we remove this pair and instead match j with k we obtain a matching which excludes i, if the gain from trade on the new pair is taken according to the true valuation then we get ( ˆV −k )∗ − (ˆvj(i) − ci) + (vj(k) − ck) ≤ (V −i )∗ . Now, since the optimal allocation ˆT∗ matches j with k rather than with i we have that (V −i −j )∗ + (ˆvj(i) − ci) ≤ ˆV ∗ = ( ˆV −k −j )∗ + (ˆvj(k) − ck), where we have used that ( ˆV −i −j )∗ = (V −i −j )∗ since these allocations exclude j. Adding up these two inequalities implies (9) in this case. It is left to prove (9) when j is not matched to i in ( ˆT−k )∗ . In fact, in this case we prove the stronger inequality ( ˆV −k )∗ + (V −i −j )∗ ≤ (V −i )∗ + ( ˆV −k −j )∗ . (10) It is easy to see that (10) indeed implies (9) since it follows from the fact that k is assigned to j in ˆT∗ that ˆvj(k) ≥ vj(k). The proof of (10) works as follows. We start with the allocations ( ˆT−k )∗ and (T−i −j )∗ which together have value equal to ( ˆV −k )∗ + (V −i −j )∗ . We now use them to create a pair of new valid allocations, by using the same pairs that were matched in the original allocations. This means that the sum of values of the new allocations is the same as the original pair of allocations. We also require that one of the new allocations does not include seller i and is based on the true valuation v, while the other allocation does not include buyer j or seller k and is based on the false valuation ˆv. This means that the sum of values of these new allocations is at most (V −i )∗ + ( ˆV −k −j )∗ , which proves (10). Let G be the bipartite graph where the nodes on one side of G represent the buyers and the nodes on the other side represent the sellers, and edge weights represent the gain from trade for the particular pair. The different allocations represent bipartite matchings in G. It will be convenient for the sake of our argument to think of the edges that belong to each of the matchings as being colored with a specific color representing this matching. Assign color 1 to the edges in the matching ( ˆT−k )∗ and assign color 2 to the edges in the matching (T −i −j )∗ . We claim that these edges can be recolored using colors 3 and 4 so that the new coloring represents allocations (T −i ) (represented by color 3) and ( ˆT−k −j ) (represented by color 4). This implies the that inequality (10) holds. Figure 2 illustrates the graph G and the colorings of the different matchings. Define an alternating path P starting at j. Let S1 = i be the seller matched to j in ( ˆT−k )∗ (if none exists then P is empty). Let B1 be the buyer matched to S1 in (T−i −j )∗ , S2 be the seller matched to B1 in ( ˆT−k )∗ , B2 be the buyer matched to S2 in (T−i −j )∗ , and so on. This defines an alternating path P, starting at j, whose edges" colors alternate between colors 1 and 2 (starting with 1). This path ends either in a seller who is not matched in (T −i −j )∗ or in a buyer who is not matched in ( ˆT−k )∗ . Since all sellers in this path are matched in ( ˆT−k )∗ , we have that seller k does not belong to P. Since in this case S1 = i and the rest of the sellers in P are matched in (T−i −j )∗ we have that seller i as well does not belong to P. This ensures that edges in P may be colored by alternating colors 3 and 4 (starting with 3). Since S1 = i, we may use color 3 for the first edge and thus assign it to the allocation (T−i ) . All other edges, do not involve i, j or k and thus may be either colored 4 and be part of an allocation ( ˆT−k −j ) or colored 3 and be part of an allocation (T−i ) , in an alternating fashion. We are left to recolor the edges that do not belong to P. Since none of these edges includes j we have that the edges 6 that were colored 1, which are part of ( ˆT−k )∗ , may now be colored 4, and be included in the allocation ( ˆT−k −j ) . It is also clear that the edges that were colored 2, which are part of (T−i −j )∗ , may now be colored 3, and be included in the allocation (T−i ) . This completes the proof of (10) and the claim. The following claim shows that a buyer j which changed his allocation due to a false declaration of his valuation cannot improve his bottom utility. The proof is basically the standard VCG argument. Claim 3. Let j be a buyer matched to seller i in T ∗ , and k = i be the seller matched to j in ˆT∗ . Then, vj(i) − Li ≥ vj(k) − ˆLk. (11) Proof. Recall that Li = vj(i) + (V−j)∗ − V ∗ , and ˆLk = ˆvj(k) + ( ˆV−j)∗ − ˆV ∗ = ˆvj(k) + (V−j)∗ − ˆV ∗ . Therefore, vj(i) − Li = V ∗ − (V−j)∗ and vj(k) − ˆLk = vj(k) − ˆvj(k) + ˆV ∗ − (V−j)∗ . It follows that in order to prove (11) we need to show V ∗ ≥ vj(k) − ˆvj(k) + ˆV ∗ . (12) The scenario of this claim occurs when j understates his value for Ai or overstated his value for Ak. Consider these two cases: • ˆvj(k) > vj(k): Since Ak was allocated to j in the allocation ˆT∗ we have that using the allocation of ˆT∗ according to the true valuation gives an allocation of value U satisfying ˆV ∗ − ˆvj(k) + vj(k) ≤ U ≤ V ∗ . • ˆvj(k) = vj(k) and ˆvj(i) < vj(i): In this case (12) reduces to V ∗ ≥ ˆV ∗ . Since j is not allocated i in ˆT∗ we have that ˆT∗ is an allocation that uses only true valuations. From the optimality of T ∗ we conclude that V ∗ ≥ ˆV ∗ . Another case in which a buyer may try to improve his utility is when he does not win any good by stating his true valuation. He may give a false valuation under which he wins some good. The following claim shows that doing this is not beneficial to him. Claim 4. Let j be a buyer not matched in T ∗ , and assume seller k is matched to j in ˆT∗ . Then, vj(k) − ˆLk ≤ 0. Proof. The scenario of this claim occurs if j did not buy in the truth-telling allocation and overstates his value for Ak, ˆvj(k) > vj(k) in his false valuation. Recall that ˆLk = ˆvj(k) + ( ˆV−j)∗ − ˆV ∗ . Thus we need to show that 0 ≥ vj(k) − ˆvj(k) + ˆV ∗ − (V−j)∗ . Since j is not allocated in T∗ then (V−j)∗ = V ∗ . Since j is allocated Ak in ˆT∗ we have that using the allocation of ˆT∗ according to the true valuation gives an allocation of value U satisfying ˆV ∗ − ˆvj(k) + vj(k) ≤ U ≤ V ∗ . Thus we can conclude that 0 ≥ vj(k) − ˆvj(k) + ˆV ∗ − (V−j)∗ . Finally, the following claim ensures that a buyer cannot influence the floor bound of the ZOPA for the good he wins. Claim 5. Let j be a buyer matched to seller i in T ∗ , and assume that ˆT∗ = T∗ , then ˆLi = Li. Proof. Recall that Li = vj(i) + (V−j)∗ − V ∗ , and ˆLi = ˆvj(i) + ( ˆV−j)∗ − ˆV ∗ = ˆvj(i) + (V−j)∗ − ˆV ∗ . Therefore we need to show that ˆV ∗ = V ∗ + ˆvj(i) − vj(i). Since j is allocated Ai in T∗ , we have that using the allocation of T∗ according to the false valuation gives an allocation of value U satisfying V ∗ − vj(i) + ˆvj(i) ≤ U ≤ ˆV ∗ . Similarly since j is allocated Ai in ˆT∗ , we have that using the allocation of ˆT∗ according to the true valuation gives an allocation of value U satisfying ˆV ∗ − ˆvj(i)+vj(i) ≤ U ≤ V ∗ , which together with the previous inequality completes the proof. This completes the analysis of the buyer"s incentive compatibility. We now turn to prove the seller"s incentive compatibility properties of our mechanism. The following claim handles the case where a seller that was not matched in T ∗ falsely understates her valuation such that she gets matched n ˆT∗ . Claim 6. Let i be a seller not matched in T ∗ , and assume buyer z is matched to i in ˆT∗ . Then, ˆHz − ci ≤ 0. Proof. Recall that ˆHz = vz(i) + ( ˆV −i −z )∗ − ( ˆV −i )∗ . Since i is not matched in T ∗ and ( ˆT−i )∗ involves only true valuations we have that ( ˆV −i )∗ = V ∗ . Since i is matched with z in ˆT∗ it can be obtained by adding the buyer z - seller i pair to ( ˆT−i −z)∗ . It follows that ˆV ∗ = ( ˆV −i −z )∗ + vz(i) − ˆci. Thus, we have that ˆHz = ˆV ∗ + ˆci − V ∗ . Now, since i is matched in ˆT∗ , using this allocation according to the true valuation gives an allocation of value U satisfying ˆV ∗ + ˆci − ci ≤ U ≤ V ∗ . Therefore ˆHz −ci = ˆV ∗ +ˆci −V ∗ −ci ≤ 0. Finally, the following simple claim ensures that a seller cannot influence the ceiling bound of the ZOPA for the good she sells. Claim 7. Let i be a seller matched to buyer j in T ∗ , and assume that ˆT∗ = T∗ , then ˆHj = Hj. Proof. Since ( ˆV −i −j )∗ = (V −i −j )∗ and ( ˆV −i )∗ = (V −i )∗ it follows that ˆHj = vj(i)+( ˆV −i −j )∗ −( ˆV −i )∗ = vj(i)+(V −i −j )∗ −(V −i )∗ = Hj. 4. CONCLUSIONS AND EXTENSIONS In this paper we suggest a way to deal with the impossibility of producing mechanisms which are efficient, individually rational, incentive compatible and budget balanced. To this aim we introduce the concept of negotiation-range mechanisms which avoid the problem by leaving the final determination of prices to a negotiation between the buyer and seller. The goal of the mechanism is to provide the initial range (ZOPA) for negotiation in a way that it will be beneficial for the participants to close the proposed deals. We present a negotiation range mechanism that is efficient, individually rational, incentive compatible and budget balanced. The ZOPA produced by our mechanism is based 7 on a natural adaptation of the VCG payment scheme in a way that promises valid negotiation ranges which permit a budget balanced allocation. The basic question that we aimed to tackle seems very exciting: which properties can we expect a market mechanism to achieve ? Are there different market models and requirements from the mechanisms that are more feasible than classic mechanism design goals ? In the context of our negotiation-range model, is natural to further study negotiation based mechanisms in more general settings. A natural extension is that of a combinatorial market. Unfortunately, finding the optimal allocation in a combinatorial setting is NP-hard, and thus the problem of maintaining BB is compounded by the problem of maintaining IC when efficiency is approximated [1, 5, 6, 9, 11]. Applying the approach in this paper to develop negotiationrange mechanisms for combinatorial markets, even in restricted settings, seems a promising direction for research. 5. REFERENCES [1] Y. Bartal, R. Gonen, and N. Nisan. Incentive Compatible Multi-Unit Combinatorial Auctions. Proceeding of 9th TARK 2003, pp. 72-87, June 2003. [2] E. H. Clarke. Multipart Pricing of Public Goods. In journal Public Choice 1971, volume 2, pages 17-33. [3] J.Feigenbaum, C. Papadimitriou, and S. Shenker. Sharing the Cost of Multicast Transmissions. Journal of Computer and System Sciences, 63(1),2001. [4] A. Fiat, A. Goldberg, J. Hartline, and A. Karlin. Competitive Generalized Auctions. Proceeding of 34th ACM Symposium on Theory of Computing,2002. [5] R. Gonen, and D. Lehmann. Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics. Proceeding of ACM Conference on Electronic Commerce EC"00, pages 13-20, October 2000. [6] R. Gonen, and D. Lehmann. Linear Programming helps solving Large Multi-unit Combinatorial Auctions. In Proceeding of INFORMS 2001, November, 2001. [7] T. Groves. Incentives in teams. In journal Econometrica 1973, volume 41, pages 617-631. [8] R. Lavi, A. Mu"alem and N. Nisan. Towards a Characterization of Truthful Combinatorial Auctions. Proceeding of 44th Annual IEEE Symposium on Foundations of Computer Science,2003. [9] D. Lehmann, L. I. O"Callaghan, and Y. Shoham. Truth revelation in rapid, approximately efficient combinatorial auctions. In Proceedings of the First ACM Conference on Electronic Commerce, pages 96-102, November 1999. [10] R. Myerson, M. Satterthwaite. Efficient Mechanisms for Bilateral Trading. Journal of Economic Theory, 28, pages 265-81, 1983. [11] N. Nisan and A. Ronen. Algorithmic Mechanism Design. In Proceeding of 31th ACM Symposium on Theory of Computing, 1999. [12] D.C. Parkes, J. Kalagnanam, and M. Eso. Achieving Budget-Balance with Vickrey-Based Payment Schemes in Exchanges. Proceeding of 17th International Joint Conference on Artificial Intelligence, pages 1161-1168, 2001. [13] W. Vickrey. Counterspeculation, Auctions and Competitive Sealed Tenders. In Journal of Finance 1961, volume 16, pages 8-37. 8
buyer and seller individual rationality incentive compatibility impossibility result utility mechanism design
efficient truthful market negotiation based mechanism good exchange negotiationrange market negotiation-range mechanism real-world market environment zone of possible agreement possible agreement zone efficient market