# Complexity of Equilibria in First-Price Auctions under General Tie-Breaking Rules

arXiv: https://arxiv.org/abs/2303.16388 · HTML: https://mlsanity.com/paper/2303.16388/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2023.

## Built on by (most cited first, 5 of 5)

- [Joint Value Estimation and Bidding in Repeated First-Price Auctions](https://mlsanity.com/paper/2502.17292/) (2025)
- [Learning to Bid in Non-Stationary Repeated First-Price Auctions](https://mlsanity.com/paper/2501.13358/) (2025)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions](https://mlsanity.com/paper/2605.09448/) (2026)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)

## Abstract (arXiv)

We study the complexity of finding an approximate (pure) Bayesian Nash equilibrium in a first-price auction with common priors when the tie-breaking rule is part of the input. We show that the problem is PPAD-complete even when the tie-breaking rule is trilateral (i.e., it specifies item allocations when no more than three bidders are in tie, and adopts the uniform tie-breaking rule otherwise). This is the first hardness result for equilibrium computation in first-price auctions with common priors. On the positive side, we give a PTAS for the problem under the uniform tie-breaking rule.