---
_id: '11796'
abstract:
- lang: eng
  text: "The design of truthful auctions that approximate the optimal expected revenue
    is a central problem in algorithmic mechanism design. 30 years after Myerson’s
    characterization of Bayesian optimal auctions in single-parameter domains [8],
    characterizing but also providing efficient mechanisms for multi-parameter domains
    still remains a very important unsolved problem. Our work improves upon recent
    results in this area, introducing new techniques for tackling the problem, while
    also combining and extending recently introduced tools.\r\n\r\nIn particular we
    give the first approximation algorithms for Bayesian auctions with multiple heterogeneous
    items when bidders have additive valuations, budget constraints and general matroid
    feasibility constraints."
alternative_title:
- LNCS
article_processing_charge: No
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: Angelina
  full_name: Vidali, Angelina
  last_name: Vidali
citation:
  ama: 'Henzinger MH, Vidali A. Multi-parameter mechanism design under budget and
    matroid constraints. In: <i>19th Annual European Symposium on Algorithms</i>.
    Vol 6942. Springer Nature; 2011:192–202. doi:<a href="https://doi.org/10.1007/978-3-642-23719-5_17">10.1007/978-3-642-23719-5_17</a>'
  apa: 'Henzinger, M. H., &#38; Vidali, A. (2011). Multi-parameter mechanism design
    under budget and matroid constraints. In <i>19th Annual European Symposium on
    Algorithms</i> (Vol. 6942, pp. 192–202). Saarbrücken, Germany: Springer Nature.
    <a href="https://doi.org/10.1007/978-3-642-23719-5_17">https://doi.org/10.1007/978-3-642-23719-5_17</a>'
  chicago: Henzinger, Monika H, and Angelina Vidali. “Multi-Parameter Mechanism Design
    under Budget and Matroid Constraints.” In <i>19th Annual European Symposium on
    Algorithms</i>, 6942:192–202. Springer Nature, 2011. <a href="https://doi.org/10.1007/978-3-642-23719-5_17">https://doi.org/10.1007/978-3-642-23719-5_17</a>.
  ieee: M. H. Henzinger and A. Vidali, “Multi-parameter mechanism design under budget
    and matroid constraints,” in <i>19th Annual European Symposium on Algorithms</i>,
    Saarbrücken, Germany, 2011, vol. 6942, pp. 192–202.
  ista: 'Henzinger MH, Vidali A. 2011. Multi-parameter mechanism design under budget
    and matroid constraints. 19th Annual European Symposium on Algorithms. ESA: European
    Symposium on Algorithms, LNCS, vol. 6942, 192–202.'
  mla: Henzinger, Monika H., and Angelina Vidali. “Multi-Parameter Mechanism Design
    under Budget and Matroid Constraints.” <i>19th Annual European Symposium on Algorithms</i>,
    vol. 6942, Springer Nature, 2011, pp. 192–202, doi:<a href="https://doi.org/10.1007/978-3-642-23719-5_17">10.1007/978-3-642-23719-5_17</a>.
  short: M.H. Henzinger, A. Vidali, in:, 19th Annual European Symposium on Algorithms,
    Springer Nature, 2011, pp. 192–202.
conference:
  end_date: 2011-09-09
  location: Saarbrücken, Germany
  name: 'ESA: European Symposium on Algorithms'
  start_date: 2011-09-05
date_created: 2022-08-11T11:51:39Z
date_published: 2011-09-01T00:00:00Z
date_updated: 2023-02-13T11:32:41Z
day: '01'
doi: 10.1007/978-3-642-23719-5_17
extern: '1'
intvolume: '      6942'
language:
- iso: eng
month: '09'
oa_version: None
page: 192–202
publication: 19th Annual European Symposium on Algorithms
publication_identifier:
  isbn:
  - '9783642237188'
  issn:
  - 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multi-parameter mechanism design under budget and matroid constraints
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6942
year: '2011'
...