---
_id: '11901'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Veronika
  full_name: Loitzenbauer, Veronika
  last_name: Loitzenbauer
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: M. Henzinger and V. Loitzenbauer, “Truthful unit-demand auctions with budgets
    revisited,” <i>Theoretical Computer Science</i>, vol. 573. Elsevier, pp. 1–15,
    2015.
  ista: Henzinger M, Loitzenbauer V. 2015. Truthful unit-demand auctions with budgets
    revisited. Theoretical Computer Science. 573, 1–15.
  mla: 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>.
  short: M. Henzinger, V. Loitzenbauer, Theoretical Computer Science 573 (2015) 1–15.
date_created: 2022-08-17T09:06:53Z
date_published: 2015-03-30T00:00:00Z
date_updated: 2024-11-06T12:24:01Z
day: '30'
doi: 10.1016/j.tcs.2015.01.033
extern: '1'
intvolume: '       573'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1016/j.tcs.2015.01.033
month: '03'
oa: 1
oa_version: None
page: 1-15
publication: Theoretical Computer Science
publication_identifier:
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Truthful unit-demand auctions with budgets revisited
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 573
year: '2015'
...