TL;DR
This paper introduces a novel bidding strategy for simultaneous ascending auctions that addresses the "exposure problem" by using self-confirming price distribution predictions. The authors demonstrate that this strategy forms a highly stable, pure-strategy Nash equilibrium in a complex auction environment, outperforming other known strategies.
What Problem Does This Paper Address?
Simultaneous ascending auctions (SAAs) are common for selling multiple related goods, where each good is auctioned separately but concurrently. A key challenge, known as the "exposure problem," arises when agents have preferences for bundles of goods. If an agent bids on a bundle but only wins some of the goods, the value of those individual goods might be significantly diminished or even worthless, leading to potential losses. Existing strategies, like straightforward bidding (SB), struggle with this problem, especially when agents value combinations of goods. While combinatorial auctions offer a solution by allowing bids on bundles, they are complex to implement. This paper focuses on developing better bidder strategies for SAAs that can mitigate the exposure problem without requiring a fundamentally different auction mechanism.
Methods
The core contribution is a new family of bidding strategies based on probabilistic price predictions. Instead of just predicting a single final price for each good (point prediction), these strategies predict the entire probability distribution of final prices.
The key innovation is the concept of self-confirming price distributions (SC). A prediction is self-confirming if, when all agents use this prediction to guide their bidding strategy, the actual resulting price distributions match the predictions. The authors propose an iterative simulation-based algorithm to derive these self-confirming distributions. This algorithm starts with an arbitrary prediction and repeatedly simulates the auction, updating the prediction based on the observed outcomes until the prediction stabilizes.
The bidding strategy itself, called PP(F) (where F is the predicted distribution), works by:
- Using the predicted price distribution to estimate the expected surplus for different bundles.
- Calculating expected incremental prices for goods, considering whether the agent already holds the good (and thus faces a sunk cost) or not.
- Choosing the bundle that maximizes expected surplus based on these incremental prices.
- Bidding incrementally on the goods in the chosen bundle that the agent doesn't already possess.
Datasets
Not discussed in the paper. The authors create simulated auction environments based on specific agent preference distributions (e.g., for market-based scheduling problems) to test their strategies.
Key Insights and Ideas
- Self-confirmation is key: The idea that an agent's beliefs about prices should align with the actual prices generated when everyone acts on those beliefs is a powerful concept for finding stable equilibria. It's like a collective "truth serum" for predictions.
- Distributions over prices are better than points: Predicting the whole distribution, rather than just a single price, allows agents to better account for risk and uncertainty, leading to more robust strategies.
- Exposure problem is central: The paper strongly emphasizes that the exposure problem is the primary strategic challenge in SAAs with complementary goods, and their strategy directly tackles this.
- Nash Equilibrium is rare but achievable: Finding pure-strategy Nash equilibria in complex auction settings is notoriously difficult. The paper's finding of a highly stable SC distribution predictor as a Nash equilibrium is a significant result.
- The "no price equilibrium" case is a hard limit: The paper demonstrates that self-confirming distributions (and thus their strategy) cannot exist in environments where no stable price equilibrium exists, highlighting a fundamental limitation.
Key Results
- In a 5x5 uniform environment (5 agents, 5 goods, uniform distributions for job lengths and deadlines), the self-confirming distribution predictor (PP(FSC)) is a highly stable, pure-strategy Nash equilibrium. This means no agent can improve its outcome by unilaterally switching to a different strategy.
- The authors were unable to find any other pure-strategy Nash equilibria in this complex 5x5 environment, suggesting PP(FSC) might be unique.
- In limited experiments across other environments, PP(FSC) consistently performs well, though it is not always a pure-strategy Nash equilibrium.
- The iterative algorithm for deriving SC distributions converges quickly (e.g., within 6-11 iterations for various scheduling problems) with a small KS statistic (0.01), indicating good approximation.
Limitations and Future Work
- Existence of SC distributions: While the authors conjecture SC distributions exist for "plausible" environments, they prove they don't always exist (e.g., in cases with no price equilibrium).
- Computational Intractability: Analyzing the full strategy space is computationally infeasible. The authors rely on empirical game-theoretic analysis of a subset of strategies.
- Simplifying Assumptions: The implementation of the distribution predictor assumes prices are independent across goods, which is a simplification.
- Future Work: The authors suggest exploring:
- Accounting for an agent's own effect on prices.
- Incorporating price dependencies more realistically with manageable computation.
- Developing strategies for environments where SC distributions don't exist.
- Optimizing bid timing to balance the risk of premature quiescence against the cost of driving up prices.
Summary updated