Symposium on Algorithmic Game Theory (SAGT)
We consider the problem of truthfully auctioning a single item, that can be either fractionally or probabilistically divided among several winners when their bids are sufficiently close to a tie. While Myerson’s Lemma states that any monotone allocation rule can be implemented, truthful payments are computed by integrating over each profile, and may be difficult to comprehend and explain. We look for payment rules that are given explicitly as a simple function of the allocated fraction and the others’ bids. For two agents, this simply coincides with (non-negative) Myerson’s payments. For three agents or more, we characterize the near-tie allocation rules that admit such explicit payments, and provide an iterative algorithm to compute them. In particular we show that any such payment rule must require positive payments to some of the bidders.
Donglai Xiang, Timur Bagautdinov, Tuur Stuyck, Fabian Prada, Javier Romero, Weipeng Xu, Shunsuke Saito, Jingfan Guo, Breannan Smith, Takaaki Shiratori, Yaser Sheikh, Jessica Hodgins, Chenglei Wu
Ludwig Sidenmark, Mark Parent, Chi-Hao Wu, Joannes Chan, Michael Glueck, Daniel Wigdor, Tovi Grossman, Marcello Giordano
Xingyi Zhou, Rohit Girdhar, Armand Joulin, Philipp Krähenbühl, Ishan Misra
