Truthfulness and approximation with value-maximizing bidders

DOI10.1007/978-3-662-53354-3_19MaRDI QIDQ2819462zbMATH OpenOpenAlexFDO

Authors Salman Fadaei, Martin Bichler

Publication date 29 September 2016

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

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

zbMATH Keywords

approximation mechanismsrevenuetruthfulnessvalue bidders

Mathematics Subject Classification ID

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

Abstract: In markets such as digital advertising auctions, bidders want to maximize value rather than payoff. This is different to the utility functions typically assumed in auction theory and leads to different strategies and outcomes. We refer to bidders who maximize value as value bidders. While simple single-object auction formats are truthful, standard multi-object auction formats allow for manipulation. It is straightforward to show that there cannot be a truthful and revenue-maximizing deterministic auction mechanism with value bidders and general valuations. Approximation has been used as a means to achieve truthfulness, and we study which approximation ratios we can get from truthful approximation mechanisms. We show that the approximation ratio that can be achieved with a deterministic and truthful approximation mechanism with $n$ bidders and $m$ items cannot be higher than 1/n for general valuations. For randomized approximation mechanisms there is a framework with a ratio of O(sqrt(m)). We provide better ratios for environments with restricted valuations.

Recommendations

• Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets
• An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents
• scientific article; zbMATH DE number 2079341
• Truthfulness in advertising? Approximation mechanisms for knapsack bidders
• scientific article; zbMATH DE number 7053320

Cites work

• A Truthful Mechanism for Offline Ad Slot Scheduling
• Bundling equilibrium in combinatorial auctions
• Computationally efficient approximation mechanisms
• Independent sets with domination constraints
• Manipulation of Voting Schemes: A General Result
• On the Power of Randomization in Algorithmic Mechanism Design
• Single-value combinatorial auctions and algorithmic implementation in undominated strategies
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• Truth revelation in approximately efficient combinatorial auctions
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful randomized mechanisms for combinatorial auctions

Cited in

(4)

• Truthfulness in advertising? Approximation mechanisms for knapsack bidders
• Generalized assignment problem: truthful mechanism design without money
• Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets
• Truthful and Near-Optimal Mechanism Design via Linear Programming

This page was built for publication: Truthfulness and approximation with value-maximizing bidders

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