On the Efficiency of All-Pay Mechanisms

Area of Science:

• Algorithmic Game Theory
• Auction Theory
• Computational Economics

Background:

• All-pay auctions are prevalent in various economic settings, including contests and procurement.
• Mixed Nash equilibria in auctions can lead to significant inefficiencies, quantified by the price of anarchy.
• Understanding these inefficiencies is crucial for designing better auction mechanisms.

Purpose of the Study:

• To analyze the price of anarchy for mixed Nash equilibria in combinatorial, multi-unit, and single-item all-pay auctions.
• To develop novel mechanisms that improve efficiency in these auction formats.
• To establish tight bounds on auction inefficiency under different valuation structures.

Main Methods:

• Investigated structural properties of mixed Nash equilibria in combinatorial all-pay auctions.
• Designed a new all-pay mechanism with a randomized allocation for multi-unit auctions.
• Analyzed single-item all-pay auctions and their relationship to contest theory.

Main Results:

• Strengthened the upper bound on the price of anarchy for item-bidding combinatorial auctions with fractionally subadditive valuations to 1.82.
• Developed a multi-unit all-pay auction mechanism admitting a unique, efficient pure Nash equilibrium for submodular valuations, outperforming existing bounds.
• Derived tight bounds for the price of anarchy in single-item all-pay auctions concerning social welfare, revenue, and maximum bid.

Conclusions:

• The study provides significant improvements in understanding and bounding auction inefficiencies.
• Novel mechanisms can achieve higher efficiency in all-pay auction settings.
• The findings have implications for the design of efficient auctions in various economic applications.