Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All

Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All

Speakers: Ermis Soumalias, Jakob Heiss, Jakob Weissteiner, Sven Seuken

Conference: ICML 2025

YouTube: https://slideslive.com/39044110

Overview

This talk introduces a groundbreaking hybrid auction mechanism that masterfully integrates two distinct types of queries—demand queries and value queries—powered by machine learning. Presented by Ermis Soumalias, Jakob Heiss, Jakob Weissteiner, and Sven Seuken, the research addresses the long-standing challenge of maximizing social welfare in complex combinatorial auctions where bidders' preferences exhibit intricate relationships like substitutes and complements. The core innovation lies in a phased approach that strategically leverages the complementary strengths of demand and value queries, each enhanced by ML models, to explore and then exploit bidder preferences efficiently.

The significance of this work is profound, particularly for high-stakes scenarios such as spectrum auctions, where governments sell licenses to network providers for billions of dollars annually. Traditional auction mechanisms struggle with the exponential complexity of bidder preferences, leading to suboptimal allocations and significant efficiency losses. By combining the exploratory power of demand queries with the precise information gathered by value queries, the proposed mechanism, dubbed PBV-MLCCA (Prices, Bids, Values - ML-Powered Combinatorial Auction), achieves unprecedented improvements.

The article details how this ML-driven combinatorial auction not only unifies the state-of-the-art across various industry-standard domains but also promises welfare gains of hundreds of millions of US dollars per auction in realistic settings. It represents a significant leap forward in auction design, offering a robust and highly efficient solution to a critical problem in economic systems, demonstrating how intelligent query design and machine learning can unlock substantial value in complex markets.

Background

▶ Watch: Introduction: Combinatorial auctions and VCG problem (0:00)

Combinatorial auctions are a powerful mechanism for allocating multiple items to several bidders, especially when bidders' valuations for bundles of items are not simply additive. These valuations often involve substitutes (where having one item reduces the value of another) and complements (where having one item increases the value of another). A classic example is the sale of spectrum licenses, where network providers might value contiguous blocks of spectrum much higher than fragmented ones, or where licenses in different regions might be complementary to build a nationwide network. Such auctions are immensely lucrative, often involving transactions worth billions of dollars annually.

The theoretical gold standard for achieving optimal social welfare (the sum of all bidders' values for the items they receive) in such settings is the VCG auction (Vickrey-Clarke-Groves). In a VCG auction, each bidder reports their value for every possible combination of items. Given this exhaustive information, the auctioneer can then optimally assign items to maximize social welfare. The problem, however, is one of immense practical intractability: the number of possible combinations of items grows exponentially with the number of items. For realistically sized auctions with many items, it becomes "practically impossible" for bidders to even report all these values, let alone for the auctioneer to process them. This exponential complexity renders VCG auctions unusable in most real-world scenarios.

To circumvent the limitations of VCG, iterative combinatorial auctions emerged. These mechanisms aim to gather information about bidder preferences incrementally by asking "targeted questions" over multiple rounds, rather than requiring full revelation upfront. Two primary types of queries have been extensively studied:

1. Demand Queries: In this type, the auctioneer posts a price for each individual item, and bidders respond by indicating their profit-maximizing bundle (the bundle of items they would want to buy at those prices, maximizing their value minus the total price). These responses provide a lower bound on bidders' values for specific bundles and help the auctioneer infer overall demand patterns.
2. Value Queries: Here, the auctioneer directly selects a specific bundle of items and asks a bidder to report their exact value for that particular bundle. These queries provide precise, local information about a bidder's preferences for a chosen bundle.

In the past, significant research has focused on employing machine learning to improve these iterative auctions. Various ML-powered approaches have been proposed to leverage the history of bidder responses to ask more targeted demand queries or more targeted value queries, each aiming to improve social welfare. However, as highlighted by the speakers, a critical gap in the existing literature was the combination of these two query types. Previous studies optimized them in isolation, failing to explore the potential synergy of a hybrid approach. This talk precisely fills that gap, demonstrating that combining both query types, especially with intelligent ML guidance, leads to dramatically superior outcomes.

Key Findings

▶ Watch: Starting with iterative demand queries (CCA) (2:55)

The central insight of this research is the discovery and exploitation of a profound synergy between demand queries and value queries in iterative combinatorial auctions. The authors demonstrate that these two query types, often treated as separate tools, are highly complementary when strategically combined and powered by machine learning.

The key findings and contributions are:

• Complementary Roles of Query Types: The talk establishes that demand queries are inherently better suited for the exploratory phase of an auction. They provide "global but coarse information," allowing the auctioneer to broadly map the bundle space and identify areas of high demand or contention. Conversely, value queries, while "local," provide "very precise information," making them ideal for exploiting and refining preferences in later stages when ML models have already developed a good approximation of bidders' value functions. This synergy also extends to their learning performance.
• Initial Phase Optimization: A crucial finding is that at the very start of an auction, when no prior information about bidder preferences is available, demand queries lead to "much higher expected social welfare" compared to random value queries. This provides a theoretical justification for beginning the auction with demand-based exploration.
• Limitations of Unimodal Querying: The research rigorously proves that even if an auction were to ask "uncountably many" demand queries, it cannot guarantee an efficiency higher than 55%. This highlights a fundamental limitation of relying solely on demand queries and underscores the necessity of incorporating value queries for high efficiency. In contrast, it is "quite trivial to show" that sufficiently many value queries can always reach 100% efficiency.
• The Bridge Bid for Robust Transition: A novel contribution is the introduction of the Bridge Bid, a specially designed value query. This query asks each bidder for their value for the bundle they would have received if the auction had concluded after the demand query phase. The authors prove that incorporating this single value query guarantees that the auction's final efficiency will be at least as high as the efficiency achieved at the end of the demand-query-only phase. This ensures a robust and non-regressing transition between the exploratory demand phase and the exploitative value phase.
• Unifying State-of-the-Art Performance: The proposed mechanism (PBV-MLCCA) achieves state-of-the-art results across all four domains of an industry-standard test suite. Importantly, it unifies the state-of-the-art, whereas previous best-performing mechanisms varied significantly from one domain to another. This demonstrates a robust and generalizable improvement.
• Dramatic Efficiency and Welfare Gains:
• The mechanism reduces efficiency loss by up to a factor of 10 compared to previous state-of-the-art methods.
• In two out of four domains, PBV-MLCCA achieves superior performance with only 42 queries, compared to the previous state-of-the-art (BOCA) requiring 100 queries. This indicates significant query efficiency.
• In the most realistic and critical domain, the mechanism yields welfare gains of over $100 million per auction, translating to hundreds of millions of US dollars in simulations.
• Robustness through Report-Dependent Allocation: A "cool thing" about the approach is that the final allocation depends only on the agents' reported values, not on the ML model's intermediate predictions. This design choice provides a crucial sense of robustness, mitigating concerns about potential model errors influencing the final outcome.
• Incentive Compatibility Insights: While lacking a universal mathematical guarantee for truthfulness (common in iterative auctions), the mechanism is designed with "stronger incentives" for bidders to report truthfully. The ML models used are capable of detecting inconsistent lies, requiring bidders to "pre-commit to lie in a specific way prior to even the start of the auction," which is deemed "quite unrealistic."

Technical Deep Dive

▶ Watch: Proving demand query limitations; value queries needed (4:10)

The proposed mechanism, Prices, Bids, Values: One ML-Powered Combinatorial Auction (PBV-MLCCA), is a multi-stage, hybrid approach designed to optimally combine demand queries and value queries using machine learning. It progresses through distinct phases, each tailored to a specific stage of information gathering and preference elicitation.

The auction begins with an initial exploration phase, leveraging the strengths of demand queries:

1. Initial Demand Query Phase (Exploration):

• The auction starts with very low prices posted for each item.
• Each bidder responds by reporting their profit-maximizing bundle at those prices.
• Based on these responses, the prices of over-demanded items are increased by a fixed percentage.
• This iterative process continues for a series of rounds, akin to the well-established Combinatorial Clock Auction (CCA), which is widely used in practice, particularly for spectrum allocation. This phase aims to quickly explore the overall demand landscape and identify highly valued items or bundles. The talk suggests using only a "small fraction" of the total query budget for this initial stage.

Following this initial exploration, the mechanism transitions to a more sophisticated, ML-powered demand query phase:

1. ML-Powered Demand Query Phase:

• In each round of this phase, machine learning models are trained for each individual bidder. These models learn from the bidder's past demand responses, effectively approximating their underlying value function.
• The collective set of these bidder-specific ML models is then used by the auctioneer to post new prices. The objective function for price setting is to minimize a "weighted sum of predicted over- and under-demand" for the items. This intelligent price-setting aims to guide bidders towards revealing more critical information about their preferences, focusing on areas where demand signals are ambiguous or highly contested.
• This iterative process continues for another fraction of the query budget.

A critical juncture in PBV-MLCCA is the transition from demand queries to value queries. This is facilitated by a novel component:

1. The Bridge Bid (Transition):

• The research proves that relying solely on demand queries, even extensively, cannot guarantee high efficiency (specifically, not even 55% efficiency). To bridge this gap and transition to the precision of value queries, the mechanism introduces the Bridge Bid.
• The Bridge Bid is a single, specific value query posed to each bidder. It asks them to report their value for the exact bundle they would have received if the auction had concluded immediately after the demand query phases (both initial and ML-powered).
• The theoretical significance of the Bridge Bid is paramount: it is proven to guarantee that the auction's final efficiency will be at least equal to the efficiency achieved at the end of the preceding demand-query-only phases. This prevents any regression in social welfare during the transition.

With the robust transition secured, the auction enters its final, exploitative phase, leveraging ML-powered value queries:

1. ML-Powered Value Query Phase:

• Similar to the ML-powered demand phase, in each round, machine learning models are continuously trained and updated on all the responses received from each bidder so far, including the Bridge Bid.
• These updated ML models are then used to predict the "optimal allocation" of items that would maximize social welfare based on the learned bidder preferences.
• For each bidder, the auctioneer then asks a value query for the specific bundle they would receive in this predicted optimal allocation. This strategy focuses queries on the most promising allocations, aiming to elicit precise values for the bundles that are most likely to be part of the final, optimal outcome.
• This phase continues until the entire query budget is exhausted.

A "cool thing" about this entire approach, as highlighted by the speakers, is its robustness: the final allocation of items is determined solely by the agents' reported values, not by the intermediate predictions of the ML models. This design ensures that the auction's outcome is grounded in actual bidder preferences, providing a strong sense of reliability and fairness, even if the ML models have minor inaccuracies in their predictions.

Furthermore, the discussion during the Q&A session revealed important details regarding the internal workings of the ML models and their role in ensuring incentive compatibility. The ML models are designed such that they always "reach zero loss" unless a bidder's reports are inconsistent. This means that if a bidder attempts to lie inconsistently across rounds (e.g., reporting a high value for a bundle in one round and a low value for a sub-bundle in another, contradictory to economic rationality), the ML model will "immediately figure out" the inconsistency. To successfully lie, a bidder would need to "pre-commit to lie in a specific way prior to even the start of the auction" and maintain this lie consistently throughout, which is deemed "quite unrealistic" and computationally challenging for the bidder. This inherent detection mechanism, while not a full mathematical guarantee of truthfulness under all conditions, provides a strong practical deterrent against strategic manipulation.

Experimental Setup & Results

▶ Watch: Impressive results: Outperforming state-of-the-art BOCA (5:25)

The effectiveness of the PBV-MLCCA mechanism was rigorously evaluated using a very industry-standard test suite that encompasses four distinct domains. This ensures that the results are not specific to a narrow set of scenarios but generalize across different types of auction environments and bidder preference structures. The specific datasets and their characteristics were not detailed in the talk but are implied to be standard benchmarks in the combinatorial auction literature.

The performance of PBV-MLCCA was primarily benchmarked against BOCA, which was identified as the previous state-of-the-art mechanism in this domain. The primary metrics for evaluation were social welfare and efficiency loss (the difference between the achieved social welfare and the theoretical maximum). The number of queries used was also a critical comparison point, reflecting the efficiency of the information elicitation process.

The experimental results were "extremely impressive," demonstrating a clear and significant advancement over existing methods:

• Unifying State-of-the-Art: PBV-MLCCA achieved state-of-the-art performance in all four domains of the test suite. This is a crucial finding, as previous research often showed that the best-performing mechanism varied from one domain to another. PBV-MLCCA provides a unified solution that consistently outperforms across diverse scenarios, highlighting its robustness and generalizability.
• Dramatic Reduction in Efficiency Loss: The mechanism successfully reduces efficiency loss by up to a factor of 10 compared to the previous state-of-the-art. This translates directly into substantial gains in overall social welfare. For example, if an auction previously lost 10% of potential value, it might now only lose 1%, representing a 90% reduction in inefficiency.
• Query Efficiency: In two out of the four domains, PBV-MLCCA demonstrated superior performance with significantly fewer queries. Specifically, it only needed 42 queries to surpass the performance achieved by BOCA using 100 queries. This highlights that not only is the hybrid approach more effective, but it is also more efficient in eliciting the necessary information from bidders, reducing the computational and cognitive burden.
• Significant Welfare Gains in Realistic Scenarios: In the "most realistic and critical domain" of the test suite, the mechanism yielded welfare gains of over $100 million per auction. Given that many large-scale combinatorial auctions (like spectrum auctions) occur regularly and involve billions of dollars, these gains can accumulate to "hundreds of millions of US dollars" annually. This underscores the profound practical impact of this research on real-world economic systems.

While the talk did not explicitly detail ablation studies in the traditional sense, the phased design of PBV-MLCCA inherently demonstrates the contribution of each component. The initial demand phase, the ML-powered demand phase, the Bridge Bid, and the ML-powered value query phase each build upon the previous, with the theoretical proofs (e.g., the 55% efficiency limit of demand queries alone, the guarantee of the Bridge Bid) acting as implicit ablations, justifying the necessity of each stage for optimal performance.

Practical Implications

▶ Watch: Key takeaway: Demand vs. value query strengths (5:40)

The development of PBV-MLCCA holds significant practical implications for various stakeholders involved in the design, execution, and participation of large-scale combinatorial auctions.

For Practitioners (Auctioneers and Regulators):

The most immediate implication is the availability of a highly efficient and robust auction mechanism. For governments conducting spectrum auctions, or large corporations allocating advertising space or logistics contracts, PBV-MLCCA offers a path to significantly increase social welfare and generate more revenue, potentially by hundreds of millions of dollars per auction. Its ability to unify state-of-the-art performance across diverse domains means auctioneers no longer need to search for domain-specific mechanisms, simplifying adoption and deployment. The improved query efficiency (achieving better results with fewer queries) also reduces the administrative burden and time required to run complex auctions.

For Infrastructure Teams and Model Builders:

Implementing PBV-MLCCA requires a robust machine learning infrastructure. This means having the capabilities to:

• Train and deploy bidder-specific ML models in real-time or near real-time during an ongoing auction.
• Handle continuous data ingestion from bidder responses and model retraining.
• Manage query generation algorithms that leverage these ML models to post prices or select bundles for value queries.
• The models must be capable of learning complex, non-linear bidder preferences and detecting inconsistencies in reported values. This implies a need for expertise in areas like preference learning, neural networks, or other advanced ML techniques suitable for economic agents.

For Bidders (Network Providers, Advertisers, etc.):

While the mechanism aims for efficiency, bidders will need to adapt their strategies. The inherent design, particularly the ML models' ability to detect inconsistent lies, means that simple, ad-hoc misrepresentation will be quickly identified. This pushes bidders towards either truthful reporting or a highly sophisticated, consistent pre-committed lying strategy, which the speakers deem "quite unrealistic." This effectively creates stronger practical incentives for truthfulness, leading to more transparent and efficient market outcomes. Bidders might also benefit from more predictable and fairer outcomes due to the mechanism's robustness (final allocation based only on reported values).

Tradeoffs and Limitations:

• Computational Overhead: While the mechanism avoids the exponential complexity of VCG, it introduces its own computational overhead related to training and deploying multiple ML models per bidder in an iterative fashion. This is a tradeoff: replacing intractable combinatorial explosion with manageable, but non-trivial, ML computations.
• Incentive Compatibility: A key discussion point was the absence of a universal mathematical guarantee for truthful reporting in all practical scenarios, a common challenge for iterative mechanisms. However, the mechanism makes strong arguments for practical incentive compatibility:
• It's designed to provide "stronger incentives" for truthfulness than existing iterative auctions like the Combinatorial Clock Auction (CCA).
• The ML models' ability to detect inconsistent reports forces any strategic lying to be "consistent" and "pre-committed," which is a high bar for bidders to meet. This acts as a powerful deterrent against adaptive, on-the-fly manipulation.
• Theoretical guarantees for truthfulness are provided under specific assumptions (e.g., 100% efficiency, bidders not manipulating their marginal economy), which may not be perfectly met in all real-world contexts, but provide a strong foundation.
• Query Budget Management: The mechanism requires strategic allocation of the query budget across its different phases. Determining the optimal number of rounds for initial demand, ML-powered demand, and ML-powered value queries is crucial for maximizing efficiency within a given budget constraint.
• Model Dependence: The effectiveness of the ML-powered phases depends on the accuracy and robustness of the underlying machine learning models in approximating bidder preferences. While the final allocation is robust, the efficiency of query generation relies on good model performance.

Despite these considerations, the PBV-MLCCA represents a significant advancement, offering a powerful, empirically proven solution to a critical problem in market design. Its practical benefits, particularly in high-value auctions, are substantial.

Key Takeaways

• Hybrid Approach is Superior: Combining demand queries and value queries in a phased, ML-powered framework dramatically outperforms mechanisms relying on either query type alone, achieving unprecedented levels of social welfare.
• Strategic Query Roles: Demand queries are best for initial, global exploration of the bundle space, while value queries excel at precise, local exploitation of bidder preferences in later stages.
• The Bridge Bid is Critical: The novel Bridge Bid serves as an essential, theoretically-backed transition mechanism, guaranteeing that efficiency is maintained or improved when moving from demand-based exploration to value-based exploitation.
• Significant Practical Gains: The PBV-MLCCA mechanism achieves state-of-the-art performance across diverse domains, reduces efficiency loss by up to a factor of 10, and yields welfare gains of over $100 million per auction in realistic settings.
• Robustness and Practical Incentives: The final allocation depends only on reported values, providing robustness. Furthermore, the ML models can detect inconsistent bidder reports, creating strong practical incentives for truthful bidding, even without a universal mathematical guarantee.
• Unifying Solution: This work unifies the state-of-the-art in combinatorial auction design, offering a single, powerful mechanism that consistently outperforms previous domain-specific solutions.

About the Speaker(s)

The research presented in this talk, "Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All," is a joint effort by Ermis Soumalias, Jakob Heiss, Jakob Weissteiner, and Sven Seuken. Ermis Soumalias presented the talk at ICML 2025, detailing the collaborative work. While specific titles and affiliations were not elaborated upon in the transcript, their collective contribution highlights expertise in machine learning, game theory, and auction design, particularly in the realm of complex economic mechanisms. The availability of their code on GitHub further underscores their commitment to open science and practical applicability of their research.