Auto-bidding is a framework of ad auctions where every advertiser can tell their long-term goals, such as budget, target return on spend (RoS), etc., to an auto-bidding agent interface. With this information, the interface bids on behalf of the advertiser to a central agency running some mechanism (an allocation rule and payment rule) to allocate the available ad slot to one of the bidders. A natural question is: what choice of mechanism provides the most efficient allocation in this auto-bidding world? Aggarwal et al. (2019) proved that a second price auction incurs a price of anarchy (PoA) of 2, even with two bidders (i.e., social welfare at the equilibrium bidding policy is at least 1/2 times the optimal social welfare achievable). Later Mehta (2022) proved that upon allowing randomized mechanisms, one could have a truthful mechanism with a PoA of approx. 1.896 when restricted to instances with only two bidders. Moreover, they proved an impossibility result that any randomized truthful mechanism has a PoA >=2 as the # of bidders increases to infinity. So, one natural question can be, can one have a lower PoA by allowing a non-truthful mechanism?
Liaw et al. (2022) addressed this question and proved that, even for non-truthful mechanisms with some assumptions, PoA >=2 as the # of bidders increases to infinity. They showed that every deterministic mechanism (truthful and non-truthful) satisfying some assumptions has a PoA >= 2, even with two bidders, and the bound is tight for first-price auctions. They also constructed a non-truthful randomized variant of the first-price auction with PoA=1.8 over instances with two bidders. Moreover, they proved that after modifying the same mechanism's payment rule to be truthful, PoA increases to 1.9, proving that non-truthfulness helps in those instances. As long as time permits, we will go through as many results as possible proven in this paper.
