Auctions for Heterogeneous Items and Budget Limits

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.

• Publication year

  2012

• Venue

  TEAC

• Publication date

  2012-09-28

• Fields of study

  Mathematics, Computer Science, Economics

• Identifiers
  DOI 10.1145/2818351arXiv 1209.6448
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On Multiple Keyword Sponsored Search Auctions with Budgets

  2012cited by this paper
• Polyhedral clinching auctions and the adwords polytope

  2012influential reference
• A note on the incompatibility of strategy-proofness and Pareto-optimality in quasi-linear settings with public budgets

  2012cited by this paper
• Single valued combinatorial auctions with budgets

  2011influential reference
• A Note on the Incompatibility of Strategy-Proofness and Pareto-Optimality in Quasi-Linear Settings with Public Budgets - Working Paper

  2011cited by this paper
• Incentive compatible budget elicitation in multi-unit auctions

  2009influential reference
• Truthful Mechanisms for One-Parameter Agents

  2008cited by this paper
• Multi-unit Auctions with Budget Limits

  2008influential reference
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation

  2006cited by this paper
• An efficient dynamic auction for heterogeneous commodities

  2006influential reference
• An Efficient Ascending-Bid Auction for Multiple Objects

  2004cited by this paper
• Optimal Auction Design

  1981cited by this paper

• Strategy-proof rules in object allocation problems with hard budget constraints and income effects

  2026cites this paper
• An Algorithm for the Assignment Game Beyond Additive Valuations

  2024cites this paper
• Breaking the traditional: a survey of algorithmic mechanism design applied to economic and complex environments

  2023cites this paper
• Polyhedral Clinching Auctions for Indivisible Goods

  2023influential citation
• Polyhedral Clinching Auctions with a Single Sample

  2023cites this paper
• Core Pricing in Combinatorial Exchanges with Financially Constrained Buyers: Computational Hardness and Algorithmic Solutions

  2021cites this paper
• Foundations of Erobotics

  2020cites this paper
• Mechanism Design for Combinatorial Allocation Problems without Quasilinear Utilities (Mechanismen-Design für Kombinatorische Allokationsprobleme ohne Quasilineare Nutzen)

  2019influential citation
• Auction Mechanisms for Virtualization in 5G Cellular Networks: Basics, Trends, and Open Challenges

  2018cites this paper
• Truthfulness in advertising? Approximation mechanisms for knapsack bidders

  2018cites this paper
• An integrated model of gene-culture coevolution of language mediated by phenotypic plasticity

  2018cites this paper
• Deep Learning for Revenue-Optimal Auctions with Budgets

  2018cites this paper
• Expressiveness and Robustness of First-Price Position Auctions

  2017cites this paper
• Polyhedral Clinching Auctions for Two-sided Markets

  2017influential citation
• Molecular recognition of the environment and mechanisms of the origin of species in quantum-like modeling of evolution.

  2017cites this paper
• An Expressive Mechanism for Auctions on the Web

  2016cites this paper
• Combinatorial auctions with bidding constraints and network externalities

  2015cites this paper
• Efficiency of Mechanisms in Complex Markets

  2014cites this paper
• Expressiveness and robustness of first-price position auctions

  2013cites this paper
• A simple computational model of the evolution of a communicative trait and its phenotypic plasticity.

  2013cites this paper
• Efficiency Guarantees in Auctions with Budgets

  2013cites this paper
• Sponsored search auctions

  2013cites this paper
• Selection for Reinforcement-Free Learning Ability as an Organizing Factor in the Evolution of Cognition

  2013cites this paper
• On Multiple Keyword Sponsored Search Auctions with Budgets

  2012cites this paper
• Composable and efficient mechanisms

  2012cites this paper
• Strategy-proof allocation problem with hard budget constraints and income effects: weak efficiency and fairness

  year unknowncites this paper