2008.10.28 | Troels Bjerre Sørensen

Title: Existence and computation of equilibria of first-price auctions with integral valuations and bids
Speaker: Rocio Santillan
Time: Tue Nov 25th 2008, 14:15-15:00
Location: Turing-014
Abstract:

In classical auction theory, the existence of pure strategy Nash equilibria (PSNE) of first-price auctions has been established under avariety of mild conditions. Nevertheless, known general existence results do not apply to the case of valuations being distributed according to a discrete probability distribution. In this paper, we consider single-item, sealed-bid, first-price Bayesian auctions with independent, identically distributed private valuations from some finite distribution on the natural numbers and with bidding space also being the natural numbers. We consider two different standardways of breaking ties between bidders: random tie-breaking, and tie-breaking by an auxiliary Vickrey auction. In theformer case, we analytically characterize the bivalued distributions for which symmetric PSNE exist for the case of two bidders. In the latter case, we algorithmically characterize the distributions for which symmetric PSNE exist forany finite support size and any finite number of bidders. In particular, we show that for any distribution, there are either zero or two such equilibria. When two equilibria exist, exactly one is undominated. We give an efficient (linear time) procedure for computing these equilibria when they do exist. Finally, we consider relaxing the assumptionof independent, identically distributed private valuations and show that for the most general way of doing this, the existence of a PSNE is an NP-hard problem.

Joint work with Guillaume Escamocher and Peter Bro Miltersen.