Bidding Marginal Utility in Simultaneous Auctions

Amy GreenwaldIJCAI 2003 · OpenReview

Abstract

In simultaneous auctions (SAs) for related goods, agents face the "exposure problem," where the value of an item depends on the acquisition of others. This paper investigates bidding strategies for agents dealing with complementary and substitute goods. By comparing independent marginal utility bidding with a coherent approach that first solves the "acquisition problem," we demonstrate that targeting a specific optimal set of goods leads to superior outcomes and prevents over-commitment in complex market environments.

Introduction

In many real-world auction environments, such as eBay or the Trading Agent Competition (TAC), multiple auctions for related goods occur simultaneously. For an autonomous agent, determining the correct bid for a single item is non-trivial because the item's utility is often contingent on the outcome of other auctions. This interdependence manifests in two primary ways: complements, where goods are worth more together (e.g., a hotel room and a flight), and substitutes, where goods are worth less together (e.g., two different flights to the same destination).

Traditional bidding strategies often struggle with the "exposure problem"—the risk of winning a partial set of complements that is useless on its own, or winning multiple substitutes and overpaying for redundant utility. This paper explores how agents can mitigate these risks by shifting from independent bidding to a strategy based on coherent marginal utility.

The Acquisition Problem and Bidding Strategies

To address the complexities of simultaneous auctions, the paper formalizes the agent's decision-making process into three distinct tasks:

  1. Allocation: Determining the best arrangement of goods already held to maximize utility.
  2. Acquisition: Identifying which additional goods to purchase, given current market prices, to maximize total utility (valuation minus cost).
  3. Completion: A general framework involving both buying (bids) and selling (asks) to reach an optimal state.

The research compares two dominant bidding philosophies inspired by successful agents in the TAC benchmark:

1. Independent Marginal Utility (ATTAC-style)

In this approach, the agent calculates the marginal utility of every available good independently. It asks, "How much does this specific item add to my current holdings?" and places a bid based on that value. While computationally straightforward, this method fails to account for the synergy or redundancy between items across different auctions.

2. Coherent Marginal Utility (ROXYBOT-style)

This strategy requires the agent to first solve the Acquisition Problem. Instead of looking at items in isolation, the agent identifies the specific subset of goods that maximizes its potential utility based on predicted or current market prices. Once this "coherent" set is identified, the agent only bids the marginal utility for items within that specific set. This ensures that all bids are working toward a single, optimized goal.

Theoretical Insights and Results

The Danger of Substitutes

The paper highlights a critical failure mode for independent bidding through the lens of substitute goods. If an agent bids on three substitute goods independently, it may inadvertently win all three. Even if each individual bid was "fair" relative to the item's utility, the cumulative cost of three items may far exceed the utility of the single item actually required, leading to a net loss. The coherent approach prevents this by recognizing that once one substitute is accounted for in the target set, the marginal utility of the others drops to zero.

Optimality Under Certainty

A key contribution of this work is the proof of Proposition 2.4, which establishes that if market prices are exogenous (fixed and known), bidding the marginal utility on the optimal acquisition set is a guaranteed optimal policy. Specifically:

  • For any good $x$ within the optimal acquisition set, the market price will not exceed its marginal utility.
  • For any good $x$ not in the set, its marginal utility will not exceed the market price.

Computational Efficiency

Beyond performance, the coherent strategy offers computational advantages. By explicitly choosing a target set of goods before bidding, the agent avoids the need to calculate complex marginal utilities for every possible combination of items it does not intend to acquire. This streamlines the decision-making process in high-stakes, fast-moving auction environments.

Conclusion

The research demonstrates that Strategy 2 (ROXYBOT-style) consistently outperforms Strategy 1 (ATTAC-style) in environments with complex combinatorial valuations. While the current model assumes exogenous prices—where an agent's bids do not influence the market—it provides a robust foundation for more complex scenarios.

Future work involves extending these principles to stochastic environments where prices are uncertain. By maintaining the principle of bidding on a coherent set of goods even amidst price fluctuations, autonomous agents can navigate simultaneous auctions with greater efficiency and significantly reduced risk of the exposure problem.

Summary updated

BibTeX
@inproceedings{greenwald2003bidding,
  author = {Amy Greenwald},
  title = {{Bidding Marginal Utility in Simultaneous Auctions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
  url = {https://openreview.net/forum?id=BkVxO4zd-B},
}
Figure