Combinatorial Auctions: A Simple Approximation Method and Its Implications

Title: Combinatorial Auctions: A Simple Approximation Method and Its Implications

Research Question: How can we design a simple approximation method for combinatorial auctions that maintains the key properties of truth-telling and dominance?

Methodology: We introduce a simple greedy optimization method for combinatorial auctions and a novel payment scheme. We identify natural properties that guarantee truth-telling for a restricted class of players in combinatorial auctions.

Results: We show that our approximation method performs reasonably effectively, and that our payment scheme makes truth-telling a dominant strategy for a restricted class of players.

Implications: Our results suggest that approximate optimization methods can be used to design practical combinatorial auctions, and that the identified properties have broader applicability beyond the specific auction studied.

Link to Article: https://arxiv.org/abs/0202017v1 Authors: arXiv ID: 0202017v1