Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation

We address the mechanism design problem of supply chain formation-the problem of negotiation mechanisms to coordinate the buying and selling of goods in multiple markets across a supply chain. Because effective negotiation strategies can be difficult to design for supply chains, we focus on incentive-compatible (IC) auctions, in which the agents' dominant strategy is to simply report their private information truthfully. Unfortunately, with two-sided negotiation, characteristic of supply chains, it is impossible to simultaneously achieve perfect efficiency, budget balance, and individual rationality with incentive compatibility. To resolve this problem, we introduce auctions that explicitly discard profitable trades, thus giving up perfect efficiency to maintain budget balance, incentive compatibility, and individual rationality. We use a novel payment rule based on Vickrey-Clarke-Groves payments, but adapted to our allocation rule. The first auction we present is incentive compatible when each agent desires only a single bundle of goods; the auction correctly knows all agents' bundles of interest, but the monetary valuations are private to the agents. We introduce extensions to maintain incentive compatibility when the auction does not know the agents' bundles of interest. We establish a good worst case bound on efficiency when the bundles of interest are known, which also applies in some cases when the bundles are not known. Our auctions produce higher efficiency for a broader class of supply chains than any other incentive-compatible, individually rational (IR), and budget-balanced (BB) auction we are aware of. (C) 2004 Elsevier B.V. All rights reserved.