Truthful unit-demand auctions with budgets revisited
Henzinger MH, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Loitzenbauer, Veronika
Abstract
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.
Publishing Year
Date Published
2015-03-30
Journal Title
Theoretical Computer Science
Publisher
Elsevier
Volume
573
Page
1-15
ISSN
IST-REx-ID
Cite this
Henzinger MH, Loitzenbauer V. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 2015;573:1-15. doi:10.1016/j.tcs.2015.01.033
Henzinger, M. H., & Loitzenbauer, V. (2015). Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2015.01.033
Henzinger, Monika H, and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science. Elsevier, 2015. https://doi.org/10.1016/j.tcs.2015.01.033.
M. H. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets revisited,” Theoretical Computer Science, vol. 573. Elsevier, pp. 1–15, 2015.
Henzinger MH, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets revisited. Theoretical Computer Science. 573, 1–15.
Henzinger, Monika H., and Veronika Loitzenbauer. “Truthful Unit-Demand Auctions with Budgets Revisited.” Theoretical Computer Science, vol. 573, Elsevier, 2015, pp. 1–15, doi:10.1016/j.tcs.2015.01.033.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access