---
_id: '11669'
abstract:
- lang: eng
  text: We study individual rational, Pareto-optimal, and incentive compatible mechanisms
    for auctions with heterogeneous items and budget limits. We consider settings
    with multiunit demand and additive valuations. For single-dimensional valuations
    we prove a positive result for randomized mechanisms, and a negative result for
    deterministic mechanisms. While the positive result allows for private budgets,
    the negative result is for public budgets. For multidimensional valuations and
    public budgets we prove an impossibility result that applies to deterministic
    and randomized mechanisms. Taken together this shows the power of randomization
    in certain settings with heterogeneous items, but it also shows its limitations.
article_number: '4'
article_processing_charge: No
article_type: original
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 for heterogeneous items and
    budget limits. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1).
    doi:<a href="https://doi.org/10.1145/2818351">10.1145/2818351</a>
  apa: Dütting, P., Henzinger, M., &#38; Starnberger, M. (2015). Auctions for heterogeneous
    items and budget limits. <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery. <a href="https://doi.org/10.1145/2818351">https://doi.org/10.1145/2818351</a>
  chicago: Dütting, Paul, Monika Henzinger, and Martin Starnberger. “Auctions for
    Heterogeneous Items and Budget Limits.” <i>ACM Transactions on Economics and Computation</i>.
    Association for Computing Machinery, 2015. <a href="https://doi.org/10.1145/2818351">https://doi.org/10.1145/2818351</a>.
  ieee: P. Dütting, M. Henzinger, and M. Starnberger, “Auctions for heterogeneous
    items and budget limits,” <i>ACM Transactions on Economics and Computation</i>,
    vol. 4, no. 1. Association for Computing Machinery, 2015.
  ista: Dütting P, Henzinger M, Starnberger M. 2015. Auctions for heterogeneous items
    and budget limits. ACM Transactions on Economics and Computation. 4(1), 4.
  mla: Dütting, Paul, et al. “Auctions for Heterogeneous Items and Budget Limits.”
    <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1, 4, Association
    for Computing Machinery, 2015, doi:<a href="https://doi.org/10.1145/2818351">10.1145/2818351</a>.
  short: P. Dütting, M. Henzinger, M. Starnberger, ACM Transactions on Economics and
    Computation 4 (2015).
date_created: 2022-07-27T12:09:15Z
date_published: 2015-12-05T00:00:00Z
date_updated: 2024-11-06T12:06:53Z
day: '05'
doi: 10.1145/2818351
extern: '1'
external_id:
  arxiv:
  - '1209.6448'
intvolume: '         4'
issue: '1'
keyword:
- Algorithmic game theory
- auction theory
- Clinching auction
- Pareto optimality
- Budget limits
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1209.6448
month: '12'
oa: 1
oa_version: Preprint
publication: ACM Transactions on Economics and Computation
publication_identifier:
  eissn:
  - 2167-8383
  issn:
  - 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Auctions for heterogeneous items and budget limits
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...