Ex-post IR Dynamic Auctions with Cost-per-Action Payments

Ex-post IR Dynamic Auctions with Cost-per-Action Payments

Weiran Shen, Zihe Wang, Song Zuo

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 505-511. https://doi.org/10.24963/ijcai.2018/70

Motivated by online ad auctions, we consider a repeated auction between one seller and many buyers, where each buyer only has an estimation of her value in each period until she actually receives the item in that period. The seller is allowed to conduct a dynamic auction but must guarantee ex-post individual rationality. In this paper, we use a structure that we call credit accounts to enable a general reduction from any incentive compatible and ex-ante individual rational dynamic auction to an approximate incentive compatible and ex-post individually rational dynamic auction with credit accounts. Our reduction obtains stronger individual rationality guarantees at the cost of weaker incentive compatibility. Surprisingly, our reduction works without any common knowledge assumption. Finally, as a complement to our reduction, we prove that there is no non-trivial auction that is exactly incentive compatible and ex-post individually rational under this setting.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems