article published yes Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Veronika Loitzenbauer author We consider auctions of indivisible items to unit-demand bidders with budgets. This setting was suggested as an expressive model for single sponsored search auctions. Prior work presented mechanisms that compute bidder-optimal outcomes and are truthful for a restricted set of inputs, i.e., inputs in so-called general position. This condition is easily violated. We provide the first mechanism that is truthful in expectation for all inputs and achieves for each bidder no worse utility than the bidder-optimal outcome. Additionally we give a complete characterization for which inputs mechanisms that compute bidder-optimal outcomes are truthful. Elsevier2015 eng 0304-397510.1016/j.tcs.2015.01.033 5731-15 yes Henzinger M, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. <i>Theoretical Computer Science</i>. 2015;573:1-15. doi:<a href="https://doi.org/10.1016/j.tcs.2015.01.033">10.1016/j.tcs.2015.01.033</a> M. Henzinger, V. Loitzenbauer, Theoretical Computer Science 573 (2015) 1–15. M. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” <i>Theoretical Computer Science</i>, vol. 573. Elsevier, pp. 1–15, 2015. Henzinger M, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15. Henzinger, M., &#38; Loitzenbauer, V. (2015). Truthful unit-demand auctions with budgets revisited. <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/j.tcs.2015.01.033">https://doi.org/10.1016/j.tcs.2015.01.033</a> Henzinger, Monika, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” <i>Theoretical Computer Science</i>, vol. 573, Elsevier, 2015, pp. 1–15, doi:<a href="https://doi.org/10.1016/j.tcs.2015.01.033">10.1016/j.tcs.2015.01.033</a>. Henzinger, Monika, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” <i>Theoretical Computer Science</i>. Elsevier, 2015. <a href="https://doi.org/10.1016/j.tcs.2015.01.033">https://doi.org/10.1016/j.tcs.2015.01.033</a>. 119012022-08-17T09:06:53Z2024-11-06T12:24:01Z