Modularity and greed in double auctions

Paul Dütting, Inbal Talgam-Cohen and Tim Roughgarden

LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library

Abstract: Designing double auctions is a complex problem, especially when there are restrictions on the sets of buyers and sellers that may trade with one another. The goal of this paper is to develop a modular approach to the design of double auctions, by relating it to the exhaustively-studied problem of designing one-sided mechanisms with a single seller (or, alternatively, a single buyer). We consider several desirable properties of a double auction: feasibility, dominant-strategy incentive compatibility, the still stronger incentive constraints offered by a deferred-acceptance implementation, exact and approximate welfare maximization, and budget balance. For each of these properties, we identify sufficient conditions on two one-sided algorithms—one for ranking the buyers, one for ranking the sellers—and on a method for their composition into trading pairs, which guarantee the desired property of the double auction. Our framework also offers new insights into classic double auction designs, such as the VCG and McAfee auctions with unit-demand buyers and unit-supply sellers.

Keywords: mechanism design; double auctions; trade reduction mechanism; deferred-acceptance auctions (search for similar items in EconPapers)
JEL-codes: J1 (search for similar items in EconPapers)
Date: 2017-09-01
New Economics Papers: this item is included in nep-des and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Published in Games and Economic Behavior, 1, September, 2017, 105, pp. 59-83. ISSN: 0899-8256

Downloads: (external link)
http://eprints.lse.ac.uk/83199/ Open access version. (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ehl:lserod:83199

Access Statistics for this paper

More papers in LSE Research Online Documents on Economics from London School of Economics and Political Science, LSE Library LSE Library Portugal Street London, WC2A 2HD, U.K.. Contact information at EDIRC.
Bibliographic data for series maintained by LSERO Manager ().