  We study the computational complexity of computing Bayes-Nash equilibria in
first-price auctions with discrete value distributions and discrete bidding
space, under general subjective beliefs. It is known that such auctions do not
always have pure equilibria. In this paper we prove that the problem of
deciding their existence is NP-complete, even for approximate equilibria. On
the other hand, it can be shown that mixed equilibria are guaranteed to exist;
however, their computational complexity has not been studied before. We
establish the PPAD-completeness of computing a mixed equilibrium and we
complement this by an efficient algorithm for finding symmetric approximate
equilibria in the special case of iid priors. En route to these results, we
develop a computational equivalence framework between continuous and discrete
first-price auctions, which can be of independent interest, and which allows us
to transfer existing positive and negative results from one setting to the
other. Finally, we show that correlated equilibria of the auction can be
computed in polynomial time.
