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.


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
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar