|
Article Excerpt
1. Introduction
Recent years have seen a growing number of transactions in Internet marketplaces, and this has generated great interest in online auctions in the academic research communities (Pinker et al. 2003). Most procurement e-markets feature numerous auctions hosted by single buyers (e.g., Gallien and Wein 2005). Although one-sided auctions are well suited for markets with a limited number of buyers, these mechanisms impose a formidable computational burden on sellers when the markets consist of numerous buyers and sellers (e.g., the agribusiness market and the energy market). To maximize profit, a potential seller may bid repeatedly in various auctions, and he has to contemplate the possible outcomes of the auctions hosted by different buyers. This computational burden hinders the trades, especially in combinatorial auctions (de Vries and Vohra 2003, Pekec and Rothkopf 2003). (1)
To relieve this computational burden and promote transactions, much recent research has been devoted to the double-auction design, which embraces multiple buyers and sellers all at once. For various exchange environments, McAfee (1992), Huang et al. (2002), Babaioff and Walsh (2003), Babaioff et al. (2004), and Chu and Shen (2006, 2008) provide truthful, or strategy-proof, double-auction mechanisms under which bidding the true valuation is each agent's best strategy. Nevertheless, these mechanisms cannot be applied to the bundle/multiunit market in which each buyer demands some bundle(s) of various commodities and each seller supplies multiple units of one commodity. For such a market, Guo et al. (2007) propose an iterative double-auction based on the decomposition scheme (also see Fan et al. 2003), whereas Jain and Varaiya (2006) propose an one-shot combinatorial seller's bid double-auction. Given these mechanisms, both papers study the agents' bidding behavior. Guo et al. (2007, p. 1356) further comment on the difficulty of designing a truthful mechanism: "An alternative is to design direct revelation mechanisms to induce agents to truthful bidding. Such methods have largely failed in simple contexts (Jennergren and Muller 1973, Myerson and Satterthwaite 1983), let alone complex setting such as ours."
This paper is devoted to filling this void by providing truthful double-auction mechanisms that support bundle synergy, enable straightforward decision making, and promote sufficiently many transactions. When calculating the buying prices, we introduce a fictitious buyer who intensifies the competition on the buyer side and intentionally creates imbalances between the supply availability and demand requirement. Ultimately, this padding enables us to design budget-balanced, strategy-proof double-auction mechanisms. We further show that by carefully selecting the padding, these mechanisms dominate the known strategy-proof bundle/single-unit mechanisms in both social welfare and agents' payoffs when each seller only supplies a single unit of one commodity.
Given a mechanism, a self-interested agent maximizes its (quasilinear) utility, which is the difference between the valuation and the amount of money transferred if the agent trades and zero otherwise. A practical auction mechanism needs to be individually rational and budget-balanced. A mechanism is (ex post) individually rational if each agent has a bidding strategy that guarantees a nonnegative utility regardless of the behavior of the other agents. A mechanism is (ex post weakly) budget balanced if the auctioneer's payoff (i.e., money collected from the buyers minus the payout to the sellers) is nonnegative regardless of the behavior of the agents. Thus, individual rationality draws the potential buyers and sellers, whereas budget balance motivates the auctioneer to hold the auction.
To promote the transactions and attract both buyers and sellers in the long run, we focus on efficiency-maximizing mechanisms that maximize the social welfare--i.e., the summation of the auctioneer's payoff and each agent's utility. A mechanism is efficient if the allocation maximizes social welfare. A weaker notion is asymptotic efficiency, which means that the welfare loss under the mechanism compared with the maximal social welfare converges to zero as maximal social welfare approaches infinity. In this paper, we propose strategy-proof, individually rational, budget-balanced, and asymptotically efficient mechanisms for the bundle/multiunit exchange environment.
The remainder of this paper is organized as follows. In [section]2, we review the double-auction design literature. In [section]3, we propose the "padding" method, a general framework to design truthful double-auction mechanisms. In [section]4, we propose the linear-program-based padding mechanism when each buyer only asks for a specific bundle. We then investigate the case when buyers may be interested in multiple bundles, and we propose the integer-program-based padding mechanism in [section]5. We evaluate the efficiency of the mechanisms in [section]6 and conclude in [section]7.
2. Related Literature
The most well-known, strategy-proof mechanism is the Vickrey-Clarke-Groves (VCG) mechanism (Vickrey 1961, Clarke 1971, Groves 1973), in which the allocation is efficient and the agent's utility equals its incremental contribution to the overall system, which is the difference between the social welfare with the agent's participation and the social welfare without it. The VCG mechanism is strategy proof, individually rational, and efficient.
Nevertheless, the VCG double-auction mechanism is not budget-balanced. Furthermore, Myerson and Satterthwaite (1983) show that it is impossible to implement an efficient, individually rational, and budget balanced mechanism even for a simple exchange environment. As a result, most research has focused on the asymptotically efficient mechanisms that host sufficiently many transactions.
2.1. Trade Reduction Method
Early truthful double-auction mechanisms adopt the trade reduction method under which the allocation is determined by removing trades from the efficient allocation and the buying and selling prices are determined by the highest losing bid by the buyers and the lowest losing bid by the sellers, respectively. The trade-reduction method recognizes that one can establish a strategy-proof and budget-balanced mechanism by selecting a subset of trades that would be executed in an efficient allocation.
Using this idea, McAfee (1992) proposes a strategy-proof mechanism for a simple exchange environment in which multiple buyers and sellers exchange single units of the same commodity. Huang et al. (2002) employ a rationing technique to design a strategy-proof mechanism for a multi-unit exchange environment with a single type of commodity. Babaioff and Walsh (2003) propose the strategy-proof known single-minded trade reduction (KSM-TR) mechanism for the bundle/single-unit environment under which each buyer asks for a bundle of various commodities and each seller supplies a single unit of one commodity. Babaioff et al. (2004) propose a truthful trade-reduction mechanism for a simple exchange environment in which agents live in numerous markets and transportation costs are incurred for transactions between the markets. Gonen et al. (2007) propose a generalized trade-reduction procedure that iteratively removes trades.
To illustrate this method, consider a bundle/single-unit market with three buyers, five sellers, and one commodity. Buyer 1 wants two units of the commodity at a per-unit price of $4; buyers 2 and 3 want one unit at $3 and $2, respectively. The five sellers each offer one unit at price $1. Assume all of the agents bid their true valuations. The trade-reduction mechanism first solves the efficient allocation under which all three buyers trade. Starting from this allocation, the mechanism removes the trading buyer with lowest bid for each bundle preference--i.e., the mechanism removes buyer 1 (the lowest bidder for two-unit bundle) and buyer 3 (the lowest bidder for one-unit bundle), and leaves buyer 2 the only trading buyer in the allocation. The selling price is $1 because the lowest bid of the nontrading sellers is $1 and the buying price of buyer 2 is $2, the bid price of buyer 3. The auctioneer's payoff is 2 - 1 = $1, and no agent can benefit from misreporting its true valuation.
2.2. Shadow Price Method
Because the buying price is set to be the highest losing bid by the buyers with the same bundle preference, a buyer does not trade if no one else desires the same bundle under the trade reduction method. To tackle this problem, Chu and Shen (2008) propose the strategy-proof buyer competition LP (BC-LP) and modified buyer competition (MBC) mechanisms, which determine the buying prices by a shadow price method.
Under this method, the mechanisms first sets the buying price for each buyer to be her bid price minus her minimum shadow price in the linear relaxation of the welfare-maximization integer programming formulation. That is, the buyer's utility is her marginal contribution, similar to the VCG mechanism. Then all of the buyers who bid higher than their buying prices become the trading buyers and trade according to the efficient allocation among the trading buyers and original sellers. The selling price of each trading seller is set to be his ask price plus his maximum shadow price in the linear relaxation of the welfare-maximization formulation among the trading buyers and original sellers.
Let us revisit the bundle/single-unit example. Recall that buyer 1 wants two units at a per-unit price of $4; buyers 2 and 3 want one unit at $3 and $2, respectively. The five sellers each offer one unit at price $1. Assume all of the agents bid their true valuations. At the optimal solution to the linear relaxation formulation, all of the buyers acquire their bundles. The buyer who has a higher bid price has a higher shadow price. For any buyer, the per-unit buying price equals the marginal cost to acquire one more unit, which is $1 and is lower than her bid. Thus, all of the buyers trade in the allocation, and the per-unit buying price is $1 for all of the buyers. With all of the buyers trading, the marginal price for the commodity is again $1 from the sellers' perspective. Therefore, the selling price is $1 for all of the sellers and the auctioneer's payoff is zero. For any buyer, she trades at price $1 as long as she bids a per-unit price higher than $1 and she does not trade if her bid is lower than $1. For any seller, he sells at price $1 if his bid is lower than $1 and he does not sell if his bid is higher than $1. No agent can benefit from misreporting its true valuation.
2.3. Potential Budget Deficit
The single-output restriction--i.e., each seller only supplies a single unit of one commodity--is assumed by the KSM-TR, BC-LP, and MBC mechanisms. When a seller offers multiple units, the single-item results do not carry over in multiple-unit settings (e.g., Rothkopf and Harstad 1994, Bapna et al. 2002), and a straightforward extension of these truthful mechanisms is not budget balanced.
To illustrate this point, let us modify the above bundle/single-unit example so that instead of five sellers each offering one unit at price $1, three sellers offer one unit at price $1 and one seller offers two units at a per-unit price of $1. The buyer side remains the same: buyer 1 wants two units at a per-unit price of $4; buyers 2 and 3 want one unit at $3 and $2, respectively.
Assume all of the agents bid their true valuations. If the above shadow price method is adopted, all of the buyers should trade at a per-unit price of $1. We will show that the seller with two units has a per-unit selling price greater than $1 and has a positive utility if the mechanism is strategy proof and individually rational. Because all other selling prices are no less than $1 under an individually rational mechanism, the auctioneer faces a deficit.
To understand that the seller with two units has a positive utility, consider the case in which this seller asks for a per-unit price of x between $1 and $2 when all other agents bid truthfully. According to the shadow price method, the marginal cost to acquire one more unit is now x, which is lower than any buyer's bid. All of the buyers trade, and the seller with two units can sell at least one unit at a price no lower than x and obtain a positive utility under an individually rational mechanism. This seller enjoys at least the same positive utility if he bids truthfully under a strategy-proof mechanism.
3. Padding Method
To recover this deficit, we propose a "padding" method that introduces a gap Q = [([Q.sup.c]).sub.[c[member of]C]] between supply availability and demand requirement for the commodities set C. The gap can be viewed as resulting from a phantom competitor: a buyer with bundle preference [(Q.sup.c).sub.[c[member of]C]] and unlimited budget. If the agents only exchange a single type of commodity, this phantom buyer essentially shifts the demand curve to the right as shown in Figure 1 for an atomless market.
[FIGURE 1 OMITTED]
As illustrated by Figure 1, the new equilibrium price will be a little higher due to padding. If we set the buying price at this higher equilibrium price, the transaction quantity may shrink a little bit. Given a smaller transaction quantity, the selling price is a little lower than the original equilibrium price as well. Therefore, padding enables a budget surplus. This idea can be carried through to an atomic market with...
|
