The combinatorial world (of auctions) according to GARP

DOI10.1007/978-3-662-48433-3_10MaRDI QIDQ3449587zbMATH OpenOpenAlexFDO

Authors Shant Boodaghians, Adrian Vetta

Publication date 4 November 2015

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(5)

• Revealed preference and activity rules in dynamic auctions
• scientific article; zbMATH DE number 1966906 (Why is no real title available?)
• Revealed preference dimension via matrix sign rank
• 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

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)