The use of simple auction mechanisms like the GSP in online advertising can lead to significant loss of efficiency and revenue when advertisers have rich preferences — even simple forms of expressiveness like budget constraints can lead to suboptimal outcomes. While the optimal allocation of inventory can provide greater efficiency and revenue, natural formulations of the underlying optimization problems grow exponentially in the number of features of interest, presenting a key practical challenge. To address this problem, we propose a means for automatically partitioning inventory into abstract channels so that the least relevant features are ignored. Our approach, based on LP/MIP column and constraint generation, dramatically reduces the size of the problem, thus rendering optimization computationally feasible at practical scales. Our algorithms allow for principled tradeoffs between tractability and solution quality. Numerical experiments demonstrate the computational practicality of our approach as well as the quality of the resulting abstractions.

Engineering automated negotiation across the supply chain is a central research challenge for the important problem of supply chain formation. The difficult problem of designing negotiation strategies is greatly simplified if the negotiation mechanism is incentive compatible, in which case the agents' dominant strategy is to simply report their private information truthfully. Unfortunately, with twosided negotiation it is impossible to simultaneously achieve perfect efficiency, budget balance, and individual rationality with incentive compatibility. This bears directly on the mechanism design problem for supply chain formation---the problem of designing auctions to coordinate the buying and selling of goods in multiple markets across a supply chain. We introduce incentive compatible, budget balanced, and individually rational auctions for supply chain formation inspired by previous work of Babaioff and Nisan, but extended to a broader class of supply chain topologies. The auctions explicitly discard profitable trades, thus giving up perfect efficiency to maintain budget balance and individual rationality. We use a novel payment rule analogous to 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 su...

Supply chain formation is the process of determining the structure and terms of exchange relationships to enable a multilevel, multiagent production activity. We present a simple model of supply chains, highlighting two characteristic features: hierarchical subtask decomposition, and resource contention. To decentralize the formation process, we introduce a market price system over the resources produced along the chain. In a competitive equilibrium for this system, agents choose locally optimal allocations with respect to prices, and outcomes are optimal overall. To determine prices, we define a market protocol based on distributed, progressive auctions, and myopic, non-strategic agent bidding policies. In the presence of resource contention, this protocol produces better solutions than the greedy protocols common in the artificial intelligence and multiagent systems literature. The protocol often converges to high-value supply chains, and when competitive equilibria exist, typically to approximate competitive equilibria. However, complementarities in agent production technologies can cause the protocol to wastefully allocate inputs to agents that do not produce their outputs. A subsequent decommitment phase recovers a significant fraction of the lost surplus.

Supply chain formation presents difficult coordination issues for distributed negotiation protocols. Agents must simultaneously negotiate production relationships at multiple levels, with important interdependencies among inputs and outputs at each level. Combinatorial auctions address this problem by global optimization over expressed offers to engage in compound exchanges. A one-shot combinatorial auction that optimizes the reported value of the bids results in optimal allocations with truthful bids. But autonomous self-interested agents have an incentive to bid strategically in an attempt to gain extra surplus. We investigate a particular combinatorial protocol consisting of a one-shot auction and a strategic bidding policy. We experimentally analyze the efficiency and producer surplus obtained in five networks, and compare this performance to that of a distributed, progressive auction protocol with non-strategic bidding. We find that producers can sometimes gain significantly by bidding strategically. However, when the available surplus is small relative to the consumers ’ values, the producers’ strategic behavior may prevent the supply chain from forming at all, resulting in zero gains for all agents. We examine the robustness of the combinatorial protocol by investigating agent incentives to deviate, identifying quasi-equilibrium behavior for an example network. 1.

Market mechanisms solve distributed scheduling problems by allocating the scheduled resources according to market prices. We model distributed scheduling as a discrete resource allocation problem, and demonstrate the applicability of economic analysis to this framework. Drawing on results from the literature, we discuss the existence of equilibrium prices for some general classes of scheduling problems, and the quality of equilibrium solutions. We then present two auction protocols for implementing solutions, and analyze their computational and economic properties.