---
_id: '11794'
abstract:
- lang: eng
  text: We study individual rational, Pareto optimal, and incentive compatible mechanisms
    for auctions with heterogeneous items and budget limits. For multi-dimensional
    valuations we show that there can be no deterministic mechanism with these properties
    for divisible items. We use this to show that there can also be no randomized
    mechanism that achieves this for either divisible or indivisible items. For single-dimensional
    valuations we show that there can be no deterministic mechanism with these properties
    for indivisible items, but that there is a randomized mechanism that achieves
    this for either divisible or indivisible items. The impossibility results hold
    for public budgets, while the mechanism allows private budgets, which is in both
    cases the harder variant to show. While all positive results are polynomial-time
    algorithms, all negative results hold independent of complexity considerations.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Paul
  full_name: Dütting, Paul
  last_name: Dütting
- 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: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
citation:
  ama: 'Dütting P, Henzinger M, Starnberger M. Auctions with heterogeneous items and
    budget limits. In: <i>8th International Workshop on Internet and Network Economics</i>.
    Vol 7695. Springer Nature; 2012:44–57. doi:<a href="https://doi.org/10.1007/978-3-642-35311-6_4">10.1007/978-3-642-35311-6_4</a>'
  apa: 'Dütting, P., Henzinger, M., &#38; Starnberger, M. (2012). Auctions with heterogeneous
    items and budget limits. In <i>8th International Workshop on Internet and Network
    Economics</i> (Vol. 7695, pp. 44–57). Liverpool, United Kingdom: Springer Nature.
    <a href="https://doi.org/10.1007/978-3-642-35311-6_4">https://doi.org/10.1007/978-3-642-35311-6_4</a>'
  chicago: Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Auctions with
    Heterogeneous Items and Budget Limits.” In <i>8th International Workshop on Internet
    and Network Economics</i>, 7695:44–57. Springer Nature, 2012. <a href="https://doi.org/10.1007/978-3-642-35311-6_4">https://doi.org/10.1007/978-3-642-35311-6_4</a>.
  ieee: P. Dütting, M. Henzinger, and M. Starnberger, “Auctions with heterogeneous
    items and budget limits,” in <i>8th International Workshop on Internet and Network
    Economics</i>, Liverpool, United Kingdom, 2012, vol. 7695, pp. 44–57.
  ista: 'Dütting P, Henzinger M, Starnberger M. 2012. Auctions with heterogeneous
    items and budget limits. 8th International Workshop on Internet and Network Economics.
    WINE: International Conference on Web and Internet Economics, LNCS, vol. 7695,
    44–57.'
  mla: Dütting, Paul, et al. “Auctions with Heterogeneous Items and Budget Limits.”
    <i>8th International Workshop on Internet and Network Economics</i>, vol. 7695,
    Springer Nature, 2012, pp. 44–57, doi:<a href="https://doi.org/10.1007/978-3-642-35311-6_4">10.1007/978-3-642-35311-6_4</a>.
  short: P. Dütting, M. Henzinger, M. Starnberger, in:, 8th International Workshop
    on Internet and Network Economics, Springer Nature, 2012, pp. 44–57.
conference:
  end_date: 2012-12-14
  location: Liverpool, United Kingdom
  name: 'WINE: International Conference on Web and Internet Economics'
  start_date: 2012-12-11
date_created: 2022-08-11T11:32:25Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2024-11-06T12:12:38Z
day: '01'
doi: 10.1007/978-3-642-35311-6_4
extern: '1'
external_id:
  arxiv:
  - '1209.6448'
intvolume: '      7695'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1209.6448
month: '12'
oa: 1
oa_version: Preprint
page: 44–57
publication: 8th International Workshop on Internet and Network Economics
publication_identifier:
  isbn:
  - '9783642353109'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11794'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Auctions with heterogeneous items and budget limits
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7695
year: '2012'
...