Approximately Efficient Double Auctions with Strong Budget Balance

Riccardo Colini-Baldeschi · Bart de Keijzer · Stefano Leonardi · Stefano Turchetta

32 citations0/0 files storedACM-SIAM Symposium on Discrete Algorithms (SODA)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Auction Theory and Applications Game Theory and Voting Systems Optimization and Search Problems

Abstract

Mechanism design for one-sided markets is an area of extensive research in economics and, since more than a decade, in computer science as well. Two-sided markets, on the other hand, have not received the same attention despite the numerous applications to web advertisement, stock exchange, and frequency spectrum allocation. This work studies double auctions, in which unit-demand buyers and unit-supply sellers act strategically. An ideal goal in double auction design is to maximize the social welfare of buyers and sellers with individually rational (IR), incentive compatible (IC) and strongly budget-balanced (SBB) mechanisms. The first two properties are standard. SBB requires that the payments charged to the buyers are entirely handed to the sellers. This property is crucial in all the contexts that do not allow the auctioneer retaining a share of buyers' payments or subsidizing the market. Unfortunately, this goal is known to be unachievable even for the special case of bilateral trade, where there is only one buyer and one seller. Therefore, in subsequent papers, meaningful trade-offs between these requirements have been investigated. Our main contribution is the first IR, IC and SBB mechanism that provides an O(1)-approximation to the optimal social welfare. This result holds for any number of buyers and sellers with arbitrary, independent distributions. Moreover, our result continues to hold when there is an additional matroid constraint on the sets of buyers who may get allocated an item. To prove our main result, we devise an extension of sequential posted price mechanisms to two-sided markets. In addition to this, we improve the best-known approximation bounds for the bilateral trade problem.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 32 citations exist upstream.

References

1961COUNTERSPECULATION, AUCTIONS, AND COMPETITIVE SEALED TENDERS 1981Optimal Auction Design 1971Multipart pricing of public goods 1983Efficient mechanisms for bilateral trading 1992A dominant strategy double auction 1999Algorithmic mechanism design (extended abstract)1994Convergence to Efficiency in a Simple Market with Incomplete Information 1989The Rate of Convergence to Efficiency in the Buyer's Bid Double Auction as the Market Becomes Large

Cited by

2016SBBA: A Strongly-Budget-Balanced Double-Auction Mechanism 2017Fixed Price Approximability of the Optimal Gain from Trade

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.