  Auto-bidding is an area of increasing importance in the domain of online
advertising. We study the problem of designing auctions in an auto-bidding
setting with the goal of maximizing welfare at system equilibrium. Previous
results showed that the price of anarchy (PoA) under VCG is 2 and also that
this is tight even with two bidders. This raises an interesting question as to
whether VCG yields the best efficiency in this setting, or whether the PoA can
be improved upon. We present a prior-free randomized auction in which the PoA
is approx. 1.896 for the case of two bidders, proving that one can achieve an
efficiency strictly better than that under VCG in this setting. We also provide
a stark impossibility result for the problem in general as the number of
bidders increases -- we show that no (randomized) anonymous truthful auction
can have a PoA strictly better than 2 asymptotically as the number of bidders
per query increases. While it was shown in previous work that one can improve
on the PoA of 2 if the auction is allowed to use the bidder's values for the
queries in addition to the bidder's bids, we note that our randomized auction
is prior-free and does not use such additional information; our impossibility
result also applies to auctions without additional value information.

Computer Science and Game Theory