Strongly Budget Balanced Auctions for Multi-Sided Markets

Rica Gonen, Erel Segal-HaleviAAAI 2020 · DOI

Abstract

In economic mechanism design, achieving efficiency, truthfulness, and budget balance simultaneously is a known impossibility in two-sided markets. This paper extends the challenge to multi-sided markets—complex environments like supply chains where a single transaction requires a specific "recipe" of multiple agents. We present two mechanisms: a direct-revelation External-Competition Auction and an iterative Ascending-Prices Auction. Both mechanisms are Dominant-Strategy Truthful (DST), Individually Rational (IR), and Strongly Budget Balanced (SBB), meaning the auctioneer neither subsidizes the market nor retains a surplus. While these auctions sacrifice the single least-profitable deal to maintain these properties, they are asymptotically optimal, capturing at least $(k-1)/k$ of the maximum possible gain-from-trade.

Introduction

The "holy grail" of mechanism design is to create an auction that is efficient (maximizes total value), truthful (incentivizes honest reporting), individually rational (ensures no participant loses money), and budget-balanced (requires no external subsidy). However, the Myerson-Satterthwaite impossibility theorem establishes that these conditions cannot be perfectly satisfied together, even in simple two-sided markets. Standard solutions like the Vickrey-Clarke-Groves (VCG) auction often result in a deficit, requiring the auctioneer to pay out of pocket. Conversely, "weakly budget-balanced" auctions may generate a surplus for the auctioneer, which can discourage participation if the "tax" on trade is too high.

This research addresses the challenge of achieving Strong Budget Balance (SBB)—where money only moves between participants and the auctioneer takes exactly zero—within multi-sided markets. These markets are characterized by complex dependencies where a deal requires a specific combination of agents, such as one buyer, two sellers, and a transporter.

The Multi-Sided Market Model

The authors formalize these dependencies using the Procurement-Set (PS) Recipe. A recipe is a vector defining the number of agents required from each category to complete a single transaction. For example, a recipe of $(1, 2, 2)$ indicates that every deal requires one buyer, two sellers, and two transporters. This framework generalizes the standard two-sided model into a multi-layered supply chain structure.

Proposed Mechanisms

The paper introduces two primary mechanisms designed to handle the complexities of multi-sided trade while maintaining SBB.

1. The External-Competition Auction (Direct Revelation)

In this direct mechanism, agents report their private values to the auctioneer, who then calculates the optimal set of trades to maximize the Gain-From-Trade (GFT). To ensure truthfulness and budget balance without a subsidy, the auctioneer employs a "trade reduction" strategy: the least profitable deal in the optimal set is removed from the trade.

This removed deal, along with other non-trading agents, forms the "external competition." The values of these sidelined agents are used to set the prices for the remaining active traders. This ensures that the sum of prices in every completed deal is exactly zero, satisfying the SBB requirement while maintaining the incentive for agents to report their true values.

2. The Ascending-Prices Auction (Iterative)

To address practical implementation, the authors propose an iterative version where prices for each category start at negative infinity and gradually increase. Agents drop out of the auction when the price exceeds their internal valuation. The auction concludes when the weighted sum of the current prices for a specific recipe equals zero.

This mechanism is obviously truthful, a stronger condition than standard truthfulness. It ensures that even agents without sophisticated game-theoretic knowledge can easily perceive that their best strategy is to remain in the auction until the price reaches their true valuation. The authors prove that this iterative process reaches the same economic outcome as the direct External-Competition Auction.

Key Insights and Results

The Power of Sidelining

The core innovation lies in the intentional sacrifice of the least-profitable deal. By sidelining this deal, the auctioneer creates a "price discovery" mechanism. The values of the agents who just missed the cutoff provide the competitive benchmark necessary to set prices for the remaining participants without requiring an auctioneer surplus.

Asymptotic Optimality

While the removal of one deal means the auction is not 100% efficient, it is asymptotically optimal. As the market grows and the number of potential deals ($k$) increases, the fraction of lost gain ($1/k$) becomes negligible. Specifically, the mechanisms are guaranteed to capture at least $(k-1)/k$ of the maximum possible GFT.

Theoretical Validation

The paper utilizes a synthetic "lemonade market" example—comprising buyers, sellers, and mediators—to demonstrate how the algorithms calculate prices and determine winners. The results confirm that both proposed auctions are Dominant-Strategy Truthful (DST), Individually Rational (IR), and Strongly Budget Balanced (SBB).

Limitations and Future Work

While providing a robust framework for SBB in multi-sided markets, the authors identify several areas for future research:

  • Single Recipe Constraint: The current model assumes a fixed recipe for deals. Future iterations could allow for multiple recipes (e.g., substituting one large seller for two smaller ones).
  • Transaction Costs: The model does not currently account for variable external costs, such as shipping fees based on distance, which would complicate the calculation of the optimal trade.
  • Multi-Parametric Agents: The study focuses on agents with a single private value for a single item. Handling agents with complex preferences across multiple combinations of goods remains an open challenge for SBB auctions.

Summary updated

BibTeX
@inproceedings{gonen2020strongly,
  author = {Rica Gonen and Erel Segal-Halevi},
  title = {{Strongly Budget Balanced Auctions for Multi-Sided Markets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5571},
}
Figure