We consider the problem of computing a (pure) Bayes-Nash equilibrium in the
first-price auction with continuous value distributions and discrete bidding
space. We prove that when bidders have independent subjective prior beliefs
about the value distributions of the other bidders, computing an
$\varepsilon$-equilibrium of the auction is PPAD-complete, and computing an
exact equilibrium is FIXP-complete. We also provide an efficient algorithm for
solving a special case of the problem, for a fixed number of bidders and
available bids.

本文研究在连续价值分布和离散竞标空间的第一价格拍卖中计算贝叶斯 - 纳什均衡的问题，并证明当投标人对其他竞标人的价值分布有独立的主观先验信念时，计算该拍卖的 ε- 均衡是 PPAD - 完全的，而计算精确均衡是 FIXP - 完全的。此外，我们还提供了一个有效的算法来解决该问题的特殊情况，即有固定数量的投标人和可用的报价。

一级定价拍卖中均衡计算的复杂性

On the Complexity of Equilibrium Computation in First-Price Auctions

The first-price auction is popular in practice for its simplicity and
transparency. Moreover, its potential virtues grow in complex settings where
incentive compatible auctions may generate little or no revenue. Unfortunately,
the first-price auction is poorly understood in theory because equilibrium is
not {\em a priori} a credible predictor of bidder behavior.
We take a dynamic approach to studying first-price auctions: rather than
basing performance guarantees solely on static equilibria, we study the
repeated setting and show that robust performance guarantees may be derived
from simple axioms of bidder behavior. For example, as long as a loser raises
her bid quickly, a standard first-price auction will generate at least as much
revenue as a second-price auction. We generalize this dynamic technique to
complex pay-your-bid auction settings and show that progressively stronger
assumptions about bidder behavior imply progressively stronger guarantees about
the auction's performance.
Along the way, we find that the auctioneer's choice of bidding language is
critical when generalizing beyond the single-item setting, and we propose a
specific construction called the {\em utility-target auction} that performs
well. The utility-target auction includes a bidder's final utility as an
additional parameter, identifying the single dimension along which she wishes
to compete. This auction is closely related to profit-target bidding in
first-price and ascending proxy package auctions and gives strong revenue
guarantees for a variety of complex auction environments. Of particular
interest, the guaranteed existence of a pure-strategy equilibrium in the
utility-target auction shows how Overture might have eliminated the cyclic
behavior in their generalized first-price sponsored search auction if bidders
could have placed more sophisticated bids.

本文以动态方法代替静态均衡，研究了英国拍卖和其他拍卖形式，其中提出了 Utility-Target auction，并得出了许多动态执行过程的结论。