Iterative Vickrey Auctions via Linear Programming

Building on the linear programming approach to competitive equilibrium pricing, we develop a general method for constructing iterative auctions that achieve Vickrey-Clarke-Groves (VCG) outcomes. We show how to transform a linear program characterizing competitive equilibrium prices into one that characterizes universal competitive equilibrium (UCE) prices, which elicit precisely the information needed to compute VCG payments. By applying a primal-dual algorithm to these transformed programs, we derive iterative Vickrey auctions that maintain a single price path, eliminating the overhead and incentive problems associated with multiple price paths used solely for payment calculations. We demonstrate the versatility of our method by developing a novel iterative Vickrey auction for the multi-unit setting and an iterative variant of the Product-Mix auction. The resulting auctions combine the transparency of iterative price discovery with the efficiency and incentive properties of the VCG mechanism.

• Publication year

  2025

• Venue

  arXiv.org

• Publication date

  2025-07-03

• Fields of study

  Computer Science, Economics

• Identifiers
  DOI 10.48550/arXiv.2507.03252arXiv 2507.03252
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Implementing Walrasian Equilibrium: the Languages of Product-mix Auctions

  2024cited by this paper
• Auction Theory

  2021cited by this paper
• REVEALED PREFERENCE AND ACTIVITY RULES IN DYNAMIC AUCTIONS

  2020cited by this paper
• Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities

  2019cited by this paper
• Solving Strong-Substitutes Product-Mix Auctions

  2019cited by this paper
• A Practical Guide to the Combinatorial Clock Auction

  2017cited by this paper
• Market Design and the Evolution of the Combinatorial Clock Auction

  2014cited by this paper
• An Experimental Comparison of Linear and Nonlinear Price Combinatorial Auctions

  2011cited by this paper
• On the robustness of non-linear personalized price combinatorial auctions

  2010cited by this paper
• The Product-Mix Auction: A New Auction Design for Differentiated Goods

  2010influential reference
• Multi-item Vickrey-Dutch auctions

  2009cited by this paper
• A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats

  2009cited by this paper
• On the Robustness of Primal-Dual Iterative Combinatorial Auctions

  2007cited by this paper
• Ascending price Vickrey auctions for general valuations

  2007influential reference
• On ascending Vickrey auctions for heterogeneous objects

  2007influential reference
• An efficient dynamic auction for heterogeneous commodities

  2006cited by this paper
• Iterative Combinatorial Auctions

  2006cited by this paper
• Ascending price Vickrey auctions

  2006cited by this paper
• A New and Improved Design for Multiobject Iterative Auctions

  2005cited by this paper
• An Efficient Ascending-Bid Auction for Multiple Objects

  2004cited by this paper
• The Lovely but Lonely Vickrey Auction

  2004cited by this paper
• Ascending Auctions with Package Bidding

  2002cited by this paper
• Price-Based Information Certificates for Minimal-Revelation Combinatorial Auctions

  2002influential reference
• The Package Assignment Model

  2002influential reference
• Linear Programming and Vickrey Auctions

  2001influential reference
• Iterative Combinatorial Auctions: Theory and Practice

  2000cited by this paper
• The English Auction with Differentiated Commodities

  2000cited by this paper
• iBundle: an efficient ascending price bundle auction

  1999cited by this paper
• WALRASIAN EQUILIBRIUM WITH GROSS SUBSTITUTES

  1999cited by this paper
• Putting Auction Theory to Work: The Simultaneous Ascending Auction

  1999cited by this paper
• Competitive Equilibrium in an Exchange Economy with Indivisibilities

  1997cited by this paper
• Why Are Vickrey Auctions Rare?

  1990cited by this paper
• Multi-Item Auctions

  1986cited by this paper
• Elicitation of Honest Preferences for the Assignment of Individuals to Positions

  1983cited by this paper
• Job Matching, Coalition Formation, and Gross Substitutes

  1982cited by this paper

• No citing papers are available for this paper.