Achieving Budget-Balance with Vickrey-Based Payment Schemes in Exchanges

Introduction

The participants in an exchange, or agents, can submit both bids, i.e. requests to buy items for no more than a bid price, and asks, i.e. requests to sell items for at least an ask price. Exchanges allow multiple buyers to trade with multiple sellers, with aggregation across bids and asks as necessary to clear the market. An exchange might also allow agents to express logical conditions across bundles of different items; for example, an agent might want to buy "A and B", or sell "A and B, or C". Following the literature on combinatorial auctions (Rothkopf et al. 1998; de Vries & Vohra 2000) we call this a combinatorial exchange. Applications of combinatorial exchanges have been suggested to excess steel inventory procurement (Kalagnanam et al. 2000) and to supply chain coordination (Walsh et al. 2000).

The market maker in an exchange collects bids and asks and clears the exchange by computing: (i) a set of trades, and (ii) the payments made and received by agents. In designing a mechanism to compute trades and payments we must consider the bidding strategies of self-interested agents, i.e. rational agents that follow expected-utility maximizing strategies. We take as our primary goal that of allocative-efficiency: to compute a set of trades that maximize value. In addition, we require:

Copyright c #0D 2001, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.

Jayant Kalagnanam and Marta Eso

IBM T.J. Watson Research Center P.O. Box 218,

Yorktown Heights, NY 10598 jayant@us.ibm.com, martaeso@us.ibm.com

-individual-rationality (IR), or voluntary participation, such that all agents have positive expected utility to participate. - budget-balance (BB), such that the exchange does not run

• at a loss.

Another useful property is incentive-compatibility (IC), which states that truthful bidding (submitting bid and ask prices equal to an agent's value) forms a Bayesian-Nash equilibrium. In other words, every agent can maximize its expected utility by bidding its true values, given that every other agent also bids truthfully. A stronger condition is strategy-proofness, such that truthful bidding is optimal whatever the bids of other agents. Strategy-proofness is useful computationally because agents can avoid gametheoretic reasoning about other agents.

Unfortunately, the well-known result of Myerson & Satterthwaite (1983) demonstrates that no exchange can be efficient, budget-balanced (even in the average-case), and individual-rational. This impossibility result holds with or without incentive-compatibility 1 , and even in BayesianNash equilibrium. Instead, one must:

• (a) impose BB and IR, and design a fairly efficient but incentive-compatible (or perhaps strategy-proof) scheme.
• (b) impose BB and IR, and design a fairly efficient and fairly incentive-compatible scheme.

We follow (b), and design a mechanism for combinatorial exchanges (with multi-unit and regular exchanges as special cases) that promotes reasonable truth-revelation and reasonable allocative-efficiency. The mechanism computes the value-maximizing allocation given agent bids, and computes payments to reduce the utility for non-truthful bidding.

Earlier authors (Myerson & Satterthwaite 1983; McAfee 1992; Barbera & Jackson 1995) have followed approach (a), deliberately computing allocations that are inefficient for truthful bids from agents to achieve incentive-compatibility or strategy-proofness. We do not believe their schemes extend easily to combinatorial problems. Furthermore, we believe that our scheme is particularly useful with boundedrational agents with incomplete information about other agents, because such agents are unable to fully exploit the "holes" for manipulation that remain in our designs.

A Vickrey-Based Payment Scheme

Our particular approach takes the Vickrey payment scheme, and adapts it to make it budget-balanced. Without the problem of BB, Vickrey payments support an efficient, IR, and strategy-proof exchange.

1 As it must, by the revelation principle.

We interpret Vickrey payments as an assignment of discounts to agents after the exchange clears. BB is achieved so long as the market maker distributes no more than the available surplus when the exchange clears. The pricing problem is formulated as an optimization problem, to compute discounts to minimize the distance to Vickrey discounts. We derive the payment schemes that correspond to optimal solutions to a number of different distance functions.

Theoretical and experimental analysis compares the utility to an agent for misstating its value in bids and asks in each payment scheme across a suite of problem instances. The results, both theoretical and experimental, make quite a compelling argument for a simple threshold payment scheme which provides discounts to agents with payments more than a threshold distance than their Vickrey payments.

The Threshold rule increases the amount by which an agent with a large degree of manipulation freedom must adjust its bid to have a useful effect on the price it finally pays, while leaving unaffected the manipulation properties for agents with a small degree of manipulation freedom. The effect is to reduce manipulation and boost allocativeefficiency in comparison with other schemes.

Let us introduce an example problem, that we will return to later in the paper.

Example. Suppose agents 1, 2, 3, 4. Agents 1 and 2 want to sell A and B respectively, with values v 1 #28A#29 = $10 and v 2 #28B#29 = $5. Agents 3 and 4 want to buy the bundle AB, with values v 3 #28AB#29 = $51 and v 4 #28AB#29 = $40. The efficient allocation is for agents 1 and 2 to trade with agent 3, for a net increase in value of $36.

The mechanism design problem is: given bid and ask prices for A, B and AB from the agents, what trades should take place and what payments should be made and received?

Vickrey Based Surplus Distribution

The market maker in an exchange has two problems to solve: winner determination, to determine the trades executed, and pricing, to determine agent payments. A common goal in winner-determination is to compute trades that maximize surplus, the difference between bid prices and ask prices. 2 These trades implement the efficient allocation with truthful bids and asks.

The pricing problem is to determine agent payments when the exchange clears. In this section we describe an application of the Vickrey-Clarke-Groves pricing mechanism (Vickrey 1961; Clarke 1971; Groves 1973) to an exchange, which often fails BB. The presentation is for a combinatorial exchange, in which agents can bid and ask for bundles of items and express logical constraints, e.g. "exclusive-or" and "additive-or" constraints, across bids and asks. 3

2 The payment schemes presented in this paper are also applicable with any (ex ante fixed) constraint on feasible trades; e.g. any level of aggregation in matching trades, or side constraints, e.g. on the volume of trade or degree of dominance by a single agent.

3 Vickrey payments in exchanges for homogeneous items, with and without multi-unit bids can be derived as special cases (Wur-

Computing payments in a Vickrey-based exchange also requires solving a number of winner-determination problems, once without each agent that trades. Winnerdetermination is NP-hard for general combinatorial exchange problems and intractable as problems become large. However, our current focus is on the incentive properties of novel Vickrey-based payment schemes. Tractable winner-determination is not our present concern. This noted, the payment schemes proposed are immediately applicable to tractable special cases of combinatorial exchanges (see Kalagnanam et al.) Future work should explore the effect of layering our schemes on top of approximate winnerdetermination algorithms.

We first define the Vickrey payments in an exchange, and then argue that the failure of BB is quite pervasive with Vickrey payments in exchanges.

Vickrey Payments

Let L denote the set of agents and G = fA; B; C; : : : g denote the set of items. We need notation for a trade; let T l 2 f,1; 0; 1g jGj denote an indicator vector for a trade, such that agent l buys items fx j T l #28x#29 = 1; x 2 Gg and sells items fx j T l #28x#29 = ,1; x 2 Gg. Let T = #28T 1 ; : : : ; T jLj #29 denote a complete trade between all agents.

Bids and asks define a reported value, ^ v l #28T l #29 for a trade T l , comprising buys and sells. Bids indicate positive value for buying a bundle of items, while asks indicate negative value for selling a bundle of items. For example, if agent 1 submits bid #28AB; 10#29 and ask #28C; 5#29, then ^ v 1 #28#5B1; 1; 0#5D#29 = 10; ^ v 1 #28#5B0; 0; ,1#5D#29 = ,5; ^ v 1 #28#5B1; 1; ,1#5D#29 = 5. The values for other trades are constructed to be consistent with value ,1 for selling anything other than item C, zero value for buying S #1A fABg, and no additional value for buying more than bundle AB.

Let T #03 denote the value-maximizing trade, given reported values, ^ v l #28T l #29, from each agent, with total surplus V #03 = P l ^ v l #28T #03 l #29. Trades must be feasible, so that supply and demand is balanced, given a model of aggregation. Also, let #28V ,l #29 #03 denote surplus from the value-maximizing trade without bids (or asks) from agent l.

By definition, the Vickrey payment to agent l is computed as:

where V #03 ,l is the value of trade T #03 to all agents except agent l, i.e. V #03 ,l = V #03 , ^ v l #28T #03 l #29. Negative payments p vick;l #3C 0 indicate that the agent receives money from the exchange after it clears.

We can express an agent's Vickrey payment as a discount, #01 vick;l , from the payment, ^ v l #28T #03 l #29, the agent would make given its bid and ask prices; i.e. p vick;l = ^ v l #28T #03 l #29 ,#01 vick;l , where the Vickrey discount is computed as:

The Vickrey discount is always non-negative, representing smaller payments by buyers and higher payments to sellers.

man et al. 1998).

Economic Properties. Vickrey payments are IR, because V #03 #15 #28V ,l #29 #03 by a simple feasibility argument, and also strategy-proof. The proof of strategy-proofness is omitted due to lack of space, but closely follows standard Vickrey proofs, for example see Varian & MacKie-Mason (1995). However, BB will often fail in an exchange, as we show in the next section.

Vickrey Budget-Balance: Success & Failure

Now that we have defined Vickrey payments in a combinatorial exchange, let us outline some cases in which BB is achieved and some cases in which BB fails. We will see that budget-balance failure is quite pervasive with Vickrey payments in exchanges.

Standard Exchange. First, consider a standard exchange with bids and asks for single units of a homogeneous item. In this case the exchange is cleared by sorting bids in order of decreasing price and asks in order of increasing price. Bids are matched with asks while the bid price is greater than the ask price. It is well known that Vickrey payments are not BB in this environment.

Let p 0 bid denote the smallest successful bid and p ,1 bid denote the largest unsuccessful bid. Similarly, let p 0 ask denote the largest successful ask and p ,1 ask denote the smallest unsuccessful ask. In the Vickrey scheme, every winning seller receives payment p vick;sell = min#28p 0 bid ; p ,1 ask #29, whatever its own ask price, and every winning buyer pays p vick;buy = max#28p 0 ask ; p ,1 bid #29, whatever its own bid price. The following condition is required for BB:

Claim 1. Budget-balance is achieved in a simple exchange for homogeneous items and single-item bids and asks if and only if one (or more) of the following conditions hold: (1) p 0 bid = p 0 ask ; (2) p 0 bid = p ,1 bid ; (3) p 0 ask = p ,1 ask .

Proof sketch. BB holds if and only if max#28p 0 ask ; p ,1 bid #29 #15 min#28p 0 bid ; p ,1 ask #29, leading to cases: (1) p 0 ask #15 p ,1 bid and p 0 bid #14 p ,1 ask ; (2) p 0 ask #3C p ,1 bid and p 0 bid #14 p ,1 ask ; (3) p 0 ask #15 p ,1 bid and p 0 bid #3E p ,1 ask .

In other words, either one or more of the supply or demand curves must be "smooth" at the clearing point, with the first excluded bid at approximately the same bid price as the last accepted bid, or the winning bid and ask prices must precisely coincide. Thus, we cannot expect BB with Vickrey payments even in a standard (non-combinatorial) exchange except in special cases.

Combinatorial Exchange As an example of BB failure, consider that agents submit truthful bids in the earlier example; i.e. asks (A, $10), (B, $5) and bids (AB, $51), (AB, $40). V #03 = 51 , 10 , 5 = 36, #28V ,1 #29 #03 = #28V ,2 #29 #03 = 0, #28V ,3 #29 #03 = 25, and #28V ,4 #29 #03 = 36. Agent 1's Vickrey payment is -10 - (36 - 0) = -46, agent 2's is -5 - (36 - 0) = -41, agent 3's is 51 - (36 - 25) = 40. The exchange runs at a loss of $47 to the market maker.

One-Sided Vickrey-Payments First, a positive specialcase. Claim 2 gives a sufficient condition for BB in the special-case that Vickrey discounts are only allocated to agents on one-side of an exchange, i.e. to all buyers or to all sellers (but not to buyers and sellers).

We define aggregation on the sell-side as when bids from multiple buyers can be combined to match an ask from a single seller, and aggregation on the buy-side as when asks from multiple sellers can be combined to match a bid from a single buyer.

Claim 2. Budget-balance holds if Vickrey payments are implemented on one-side of an exchange, and when that side has no aggregation.

Proof sketch. Simple, just show that this BB holds for each "cluster" of trading agents, and therefore for the entire exchange.

Bilateral matching is a special-case, with no aggregation on either side; i.e. Vickrey payments are budget-balanced if implemented for at most one agent in each trade, for example with trades cleared at either the ask price (buyside strategy-proofness) or the bid price (sell-side strategyproofness). Similarly, the single-item Vickrey auction is a special case (and strategy-proof to buyers but not the seller).

The Generalized Vickrey Auction (GVA) is the VCG mechanism for a combinatorial auction, in which there is a single seller and sell-side aggregation. The GVA is BB because the buyers, but not the seller, receive Vickrey payments. The auctioneer simply collects the total payment made by the buyers and passes it on to the seller. As such the GVA is strategy-proof for buyers but not for the seller. Another problem is that the seller can sometimes receive less than her ask price. Consider a seller with an ask price of (AB, $10) and bids of (A, $8) and (B, $8) from different buyers. Each buyer receives Vickrey discount $6 and pays $2, but the seller needs at least $10.

One-to-N models We can state a general negative result for Vickrey payments to all agents (buyers and sellers) in a combinatorial auction.

Claim 3. Budget-balance fails with Vickrey payments to all agents in a combinatorial auction except in the case that no buyer requires a Vickrey discount.

Proof sketch. Simple, just show that the seller extracts all of the surplus as its Vickrey discount.

Intuitively, BB fails in this case unless the marginal value contributed by each buyer is zero, i.e. unless the surplus in the exchange is the same with any one of the buyers removed.

Budget-Balanced Payment Rules

In this section we take BB and IR as hard constraints and propose methods to distribute surplus when an exchange clears to minimize the distance between discounts and Vickrey discounts. The choice of distance function has a distributional effect on the allocation of surplus and changes the incentive-compatibility properties of the exchange. In a later section we demonstrate useful truth-revelation properties for the Vickrey-based schemes.

We do the following:

• #0F Formulate the pricing problem as a mathematical program, to minimize the distance to Vickrey payments with BB and IR as hard constraints.
• #0F Introduce possible distance functions and construct corresponding budget-balanced payment schemes.
• #0F Present a theoretical analysis of each payment scheme in a simple bidding model.

Mathematical Programming Model

We formulate the pricing problem as a linear program, to assign surplus to agents to minimize distance to Vickrey discounts. Let V #03 denote the available surplus when the exchange clears, before any discounts, and L #03 #12 L denote the set of agents that trade. Each agent may perform a number of buys and sells, depending on its bids and asks of other agents. We compute discounts #01 = #28#01 1 ; : : : ;#01 L #29 to minimize the distance L#28#01;#01 vick #29 to Vickrey discounts, for a suitable distance function L.

Constraint (BB) gives worst-case (or ex post) budgetbalance, such that the exchange never makes a net payment to agents. We might also substitute an expected surplus V #03 for V #03 and implement average-case (or ex ante) budgetbalance. Constraints (IR) ensure that truthful bids and asks are individual-rational for an agent, with a worst-case (or ex post) non-negative expected utility. Constraints (VD) ensure that no agent receives more than its Vickrey discount. 4

In addition to the standard L 2 and L 1 distance metrics, we also consider the following functions: (a) L RE #28#01;#01 vick #29 = P l #01 vick;l ,#01 l #01 vick;l , a relative error function; (b) L #05 #28#01;#01 vick #29 = Q l #01 vick;l #01 l , a product error function; (c) L RE2 #28#01;#01 vick #29 = P l #28#01 vick;l ,#01 l #29 2 #01 vick;l , a squared relative error function; (d) L WE #28#01;#01 vick #29 = P l #01 vick;l #28#01 vick;l , #01 l #29, a weighted error function. The L 1 metric provides no distributional information.

We drop agents with #01 vick;l = 0 from all models, and simply set #01 l = 0 for these agents.

Payment Rules Rather than solving problem [PP] directly, we can compute an analytic expression for the family of solutions that correspond to each distance function. Each family of solutions is a parameterized payment rule. For example, the Threshold rule, #01 l = max#280;#01 vick;l , C#29 for some parameter C #15 0, solves [PP] for the L 2 distance metric. For large C, Threshold allocates small, or no, discounts, while for C = 0 Threshold allocates Vickrey discounts.

To understand the construction of Threshold from L 2 consider the simplest case, when constraints (VD) and (IR) are not binding, and perform Lagrangian optimization. Dropping the outer square root from the L 2 metric and introducing Lagrange multiplier #15 #15 0, we have min P l #28#01 vick;l , #01 l #29 2 + #15#28 P l #01 l , V #03 #29. Now, computing first derivatives w.r.t. #01 l and setting to zero, we have ,2#28#01 vick;l ,#01 l #29+#15 = 0 for all l. 5 Solving, this equates the distance to Vickrey discounts across all agents, #01 vick;1 ,#01 1 = #01 vick;2 ,#01 2 = : : : , and with budget-balance we find #01 l = #01 vick;l , #28 P l 0 #01 vick;l 0 , V #03 #29=jL #03 j. This is the Threshold rule with parameter C = #28 P l #01 vick;l , V #03 #29=jL #03 j = #15=2.

4 The (VD) constraints are not redundant for certain distance metrics, such as the L RE #28#01#29 metric.

Table 1 tabulates the payment rules for each distance function, and also includes the Equal rule which is not Vickreybased but divides surplus equally across all agents, and the No-Discount rule (see also Figure 1). Each payment rule is parameterized with C #150, except for Fractional, which has parameter 0#14#16#14 1. The parameters that give BB in each scheme can be easily computed from Vickrey discounts and available surplus.

Example. In Table 2 we compare the paymentsmadewith each payment scheme in our simple problem. Notice that neither the Large or Small schemes provide useful guidance about how to distribute the discount across the two sellers, this depends on how the tie is broken.

Theoretical Analysis

In this section we develop simple analytic results for the amount of manipulation an agent will perform with each payment scheme. The model permits tractable analysis, and proves interesting both for the insight it provides and for the close correspondence that we find with later experimental results for combinatorial exchange problems.

We choose to analyze an exchange in which bids and asks are for single items. Later, in our experimental analysis we compare the payment schemes in combinatorial problems.

For buyers (the analysis is symmetric for sellers):

(1) Every agent l has value v l for a single item (drawn from some distribution F l #28v#29) and chooses to manipulate by

5 First-order conditions are necessary and sufficient for optimality in this problem because the Hessian is positive definite.

#12 l #15 0, and bid b l =v l ,#12 l .

(2) The maximum bid x l from another agent for the item, or ask price (whichever is higher), is uniformly distributed about v l , i.e. x l #18U#28v l ,#0E; v l +#0E#29 for some constant, #0E#3E0.

1. The average surplus available to the market maker when the exchange clears is #0B#0E per-agent, for some constant #0B #3E 0 that defines the amount of surplus.
2. In equilibrium, the market maker selects a parameter (e.g. C) for the payment scheme to achieve average-case budget-balance. Payment rules are computed before agents bid, and the parameters are known to bidding agents.

Agent l has a quasi-linear utility function, u l =v l ,p, for submitting the highest bid where p is its payment to the exchange, i.e. p = b l ,#01 l . Figure 1 illustrates each payment rule in this simple model, plotting bid price b l against adjusted price b l ,#01 l ; e.g., in Vickrey the agent pays only x for any bid b l #15 x, in Threshold the agent pays b l = x + C for b l #15 x+C, and b l for x #14 b l #3C x+C, given parameter C, etc.

For each payment scheme we determine: (a) an agent's optimal bidding strategy as a function of the parameters of the rule, e.g. C or #16; and (b) the equilibrium parameterization of the rule, e.g. value for C, that leads to budget-balance given that agents follow this optimal bidding strategy. The analysis leads to a relationship between the available surplus and the degree of manipulation for each payment rule (see Figure 4).

One can be critical of our assumptions. We leave undefined both the valuation distribution functions F l #28v#29 and the distribution that defines the item an individual agent values. It is quite likely that there are no F l #28v#29 that are consistent with our assumption of a uniformly distributed second-highest bid in equilibrium. In addition, we adopt average-case budget-balance and compute payment rules before agents bid, but ignore any effect that rules have on surplus via agents' bidding strategies.

However, we believe that this analysis has significant value. Its main success is that it clearly demonstrates the effect that different types of budget-balanced Vickrey-based payment rules can have on agent manipulation. We leave a full equilibrium analysis for future work.

Graphical Intuition. Manipulation has two effects on the expected utility for an agent: (i) the probability of the adjusted bid being accepted decreases, and (ii) the total utility if the bid is accepted can go up because the agent's payment might be reduced. Payment rules change (ii) but not (i), and in turn effect agents' bids and the efficiency of the exchange.

In Figure 2 we plot the utility for a particular bid, b = v,#12, as the value of the outside bid x varies, for payment schemes Vickrey, No-Discount, Threshold and Fractional. Each subplot is for a single scheme, with individual curves corresponding to different bids. 6

In the Vickrey scheme a lower bid reduces the agent's expected utility because it decreases the probability of success without increasing the utility of a successful bid. In comparison, with no discount the agent gains utility on all successful bids by the amount of deviation from truthful bidding. In the Threshold scheme a lower bid only reduces the price paid for a limited range of outside bids (closer than C to the bid price), while in the Fractional scheme a lower bid reduces the price paid on all successful bids (but by less than in the No Discount scheme).

Making our assumption about the distribution of x around an agent's value v l , we can compute the expected utility for different levels of manipulation under each scheme as the area under a particular curve in a plot like Figure 2. 7 The expected-utility maximizing bid corresponds to the curve with maximum area. In Figure 3 we plot the expected gain in utility (in comparison with truthful bidding), Eu#28#12#29,Eu#280#29, for bid b = v , #12 in each payment rule. Rule parameters are set to give BB with surplus #0B = 0:1 at optimal agent strate-

6 Although not plotted here, the curves for Equal are similar to the No-Discount case (except shifted higher in utility by a constant amount), and Large is similar to Threshold.

7 It is at this stage that an equilibrium analysis would need to use a derived expression for the distribution of x.

1

gies. Notice that the level of manipulation, #12 #03 , that maximizes the agent's gain in utility is smallest in the Threshold scheme for this value of surplus.

The results (below) show that the Large and Threshold rules perform well in this model, and lead to the following intuitive remarks about payment rules (see Figure 1):

1. A large flat section for bids close to the agent's true value is useful, i.e. with adjusted bid price independent of the agent's bid price.
2. Nowhere should the adjusted bid price be greater than the agent's bid price (for IR with truthful bidding), which constrains the line to lie to the right of the "no-discount" line.
3. It is more important to implement the flat section for values, v, far from the highest outside bid, x, than values close to the highest outside bid (i.e. Large rather than Small), because manipulation is already more risky for true values close to v than far from x. 8

It is useful to think about the "degree of manipulation freedom" available to an agent, which in this simple singlebundle model is the difference between an agent's value v and the highest outside bid x. In general, this is simply measured by the Vickrey discount to an agent that bids truthfully, i.e. the amount by which it could have reduced its bid price and still participated in the same trades. The Large and Threshold schemes are effective because they make manipulation more difficult and less useful for an agent with a large degree of manipulation freedom, while leaving the ability to manipulate of agents with a small degree of manipulation freedom unchanged. This is a good incentive strategy because it attacks the "low risk" manipulation opportunities, but leaves the "high risk" opportunities. Agents are uncertain about the bids from other agents and always run the risk of bidding too low and forfeiting a profitable trade.

Results. Table 3 summarizes the analytical results, giving an agent's optimal bidding strategy, #12 #03 , as a function of the parameter in each scheme, and the expected discount peragent given that optimal strategy. 9 We present an example derivation, for the Threshold rule, below.

8 Note that in terms of efficiency the picture is mixed. While we can stand more manipulation from agents with large values compared to x, without changing the trades that we implement, if the bids from those agents does change the final implementation the effect on efficiency is likely to be quite large.

In Figure 4 we enforce BB, computing parameters in the payment schemes to set the expected discount equal to surplus #0B#0E, and plot the equilibriummanipulation performed in each payment scheme as the amount of surplus varies. The Vickrey payment scheme can be implemented with surplus #0E=4 per-agent, so all schemes except Equal and No-Discount prevent manipulation completely for #0B #15 0:25. For smaller amounts of surplus the market maker is forced to deviate from Vickrey, and move left in Figure 4. At #0B = 0 no schemes can provide any discount, and the agent manipulates by #0E=2.

First, notice that the simple minded Equal scheme appears to have bad incentive properties. In fact, the Threshold method dominates all other schemes in this model except Large. Large has an interesting bad-good phase transition at #0B = 1=8, and can prevent manipulation completely for 1=8 #14 #0B #14 1=4 even though agents with small Vickrey discounts might have benefited from manipulation with hindsight. Agent uncertainty coupled with the risk of bidding too low and either falling from the flat section or under-bidding the highest outside bid lead agents to bid truthfully.

9 It is useful to confirm that all expressions reduce to that for the Vickrey and No-Discount rules at extreme parameter values (e.g. #16 = f0; 1g in Fractional, C = f0; #0E=2g in Threshold, etc.)

Example Derivation: Threshold Rule. Each agent receives discount max#280; b, #28x + C#29#29, for some constant C #3E 0. The agent's utility given bid v , #12, value v, highest outside bid x, and Threshold C, is computed as:

Assume that C #14 #0E, so that the agent will receive a discount for some choice of #12 #3C #0E. Consider three cases. Case (1), #12 #14 #0E,C. The expected utility for bid #12 given C, EU#28#12;C#29 is:

#12#28#0E,#12#29=2#0E. In Case (3), #0E #3C #12, then EU#28#12; C#29 = 0. ¿From this, the agent's optimal bidding strategy, denoted #12 #03 #28C#29, by differentiation w.r.t. #12 and case analysis, is:

The discount to the agent for bid b = v,#12 is: #01#28v , #12; v; x;C#29 = max #5B0; v,#12,#28x+C#29#5D. The expected discount, first in the case that #12 #14 #0E ,C, is:

or E#01#28#12;C#29 = 0 in the case #12 #3E #0E,C. Substituting for the agent's optimal bidding strategy #12 #03 #28C#29 we have: E#01#28#12 #03 #28C#29;C#29 = max h 0; #28#0E,2C#29 2 4#0E i . Now, with per-agent surplus #0B#0E and budget-balance, such that E#01 #03 #28C#29 #14 #0B#0E, the exchange should set C #03 #28#0B#29 = min #02 0; #0E 4 , 2 , p 16#0B #01#03 to minimize manipulation.

Experimental Analysis

In this section we provide an experimental analysis of the payment schemes in a set of combinatorial problem instances. Agents are either buyers or sellers, and values are assigned to agents for bundles following the Random, Weighted Random, Decay, and Uniform distributions from Sandholm (1999), adapted in this case to a combinatorial exchange. Each agent submits bids (asks) for multiple bundles, with exclusive-or constraints across bids (asks). We test problems with 5, 10, and 20 agents, a total of 100 bids and asks (evenly distributed across agents), 50 goods, and with different proportions of buyers and sellers. 10

10 Results are averaged over 80 problem instances, for numbers of Buyer/Sellers 2 f5=5; 7=3; 2=3; 4=1; 10=10; 15=5g.

In our theoretical model we adopted average-case budgetbalance to make the analysis tractable. We now revert to the more natural worst-case (or every-time) budget-balance in which the market maker distributes exactly the available surplus every time the exchange is cleared. Payment rules are now computed after bids are received.

We perform a limited strategic analysis. First, we assume that the strategy of agent l is to adjust all its bids and asks by the same fractional amount, y l %, i.e. submitting bid prices y l % below value and ask prices y l % above value. Second, we look for a symmetric Nash equilibrium in which every agent follows the same strategy, for some y%. Finally, we compute an approximation to this equilibrium for computational tractability. We compute the average utility gain to a single agent for 0% vs. y% manipulation, given that every other agent manipulates by y%, and determine the amount of manipulation, y #03 , that maximizes this utility gain. We assume that this is also the optimal strategy for an individual agent against a population of agents with fixed strategies y #03 , and therefore the Nash equilibrium. 11

Given this, we read off the symmetric Nash equilibrium under a particular payment rule as the peak of a plot such as that in Figure 5, which plots the gain in utility for strategy y% vs. 0% in a system in which every agent follows strategy y%, in this case for the 5 buyers/5 sellers problem set. In this case, notice that the equilibrium manipulation level in Large and Threshold is less than under the other rules, in this case around 10% and 20% in Large and Threshold, compared with 30%, 40% and 50% in Fractional, Equal and No-Discount. In addition, the amount of utility gain in Large and Threshold is much less than in the other schemes.

In Table 4 we summarize the results of experiments across all problem sets. We compare: the average utility gain, and the correlation with Vickrey discounts, at manipulation levels of 10%, 20% and 30% in each scheme; and the average optimal degree of manipulation by agents in each scheme, and the corresponding allocative efficiency. The allocative efficiency in the Large and Threshold schemes is considerably higher than in the other schemes.

11 One benefit of this technique is that we have a method to measure the degree of manipulation even when there is in fact no symmetric pure Nash equilibrium.

Discussion

The partial ordering fLarge, Threshold g #1F Fractional #1F Reverse #1F fEqual, Small g from the experimental results is remarkably consistent with the results of our theoretical analysis. Although the Large scheme generates slightly less manipulation and higher allocative efficiency than Threshold, the correlation between discounts and Vickrey discounts is much greater in Threshold than Large. An agent's discount in Large is very sensitive to its bid, and we expect Large to be less robust than Threshold in practice because of this all-or-nothing characteristic.

As discussed earlier, we have made a number of assumptions, both in the analytic models of agent manipulation and also in the manipulation structure considered experimentally. In addition to understanding the effects of these assumptions, in future work we would also like to: quantify worst-case and average-case utility gains from manipulation in each payment scheme, given a particular amount of surplus; and derive optimal payment schemes, for example minimizing worst-case gains from manipulation. One avenue is to ask how bad would the efficiency get if every agent was perfectly informed about the other agents, and followed a best-possible bidding strategy given the payment rules. Finally, we suspect that stochastic payment rules might prove to have interesting incentive properties.

Conclusions

We constructed budget-balanced payment schemes to minimize different distance functions to Vickrey payments, and showed analytically and experimentally that a simple Threshold rule has better incentive properties than other payment schemes. The effect of the payment scheme is to implement a distribution of manipulation-preventing discounts across a population of agents to exploit an agent's inherent uncertainty about bids from other agents and the degree to which manipulation can be useful. The Threshold rule increases the amount by which an agent with a large degree of manipulation freedommust adjust its bid to have a useful effect on the price it finally pays, while leaving unaffected the manipulation properties for agents with a small degree of manipulation freedom.

Finally, we note that the schemes outlined here can also allow a market maker to make a small profit by taking a sliver of budget-balance, or used in combination with a participation charge to move payments closer to Vickrey payments.

Acknowledgments

We thankWilliamWalsh, and the anonymous reviewers, for their helpful comments and suggestions. This research was funded in part by National Science Foundation Grant SBR 97-08965. The first author gratefully acknowledges financial support from an IBM Research Fellowship.