The combinatorial world (of auctions) according to GARP

DOI10.1007/978-3-662-48433-3_10zbMATH Open1358.91056arXiv1505.00508OpenAlexW3106282085MaRDI QIDQ3449587FDOQ3449587

Authors: Shant Boodaghians, Adrian Vetta 

Publication date: 4 November 2015

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Abstract: Revealed preference techniques are used to test whether a data set is compatible with rational behaviour. They are also incorporated as constraints in mechanism design to encourage truthful behaviour in applications such as combinatorial auctions. In the auction setting, we present an efficient combinatorial algorithm to find a virtual valuation function with the optimal (additive) rationality guarantee. Moreover, we show that there exists such a valuation function that both is individually rational and is minimum (that is, it is component-wise dominated by any other individually rational, virtual valuation function that approximately fits the data). Similarly, given upper bound constraints on the valuation function, we show how to fit the maximum virtual valuation function with the optimal additive rationality guarantee. In practice, revealed preference bidding constraints are very demanding. We explain how approximate rationality can be used to create relaxed revealed preference constraints in an auction. We then show how combinatorial methods can be used to implement these relaxed constraints. Worst/best-case welfare guarantees that result from the use of such mechanisms can be quantified via the minimum/maximum virtual valuation function.

Full work available at URL: https://arxiv.org/abs/1505.00508

Recommendations

• Truth revelation in approximately efficient combinatorial auctions
• scientific article; zbMATH DE number 1966906
• Truthful randomized mechanisms for combinatorial auctions
• Truthful randomized mechanisms for combinatorial auctions
• Valuation compressions in VCG-based combinatorial auctions

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• The Nonparametric Approach to Demand Analysis
• Walrasian equilibrium with gross substitutes
• A characterization of the minimum cycle mean in a digraph
• Job Matching, Coalition Formation, and Gross Substitutes
• The Construction of Utility Functions from Expenditure Data
• Two new proofs of Afriat's theorem
• Mechanism design. A linear programming approach.
• Supermodularity and preferences
• Strong activity rules for iterative combinatorial auctions

Cited In (5)

• Connected price dynamics with revealed preferences and Auctioneer's discretion in VCG combinatorial auction
• Welfare and rationality guarantees for the simultaneous multiple-round ascending auction
• Revealed preference dimension via matrix sign rank
• Title not available (Why is that?)
• Revealed preference and activity rules in dynamic auctions

This page was built for publication: The combinatorial world (of auctions) according to GARP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449587)