Speaker: |
Agniv Bandyopadhyay |

Date: |
Friday, 24 Mar 2023, 14:30 to 15:30 |

Venue: |
A201 |

(Scan to add to calendar)

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.