Setting lower bounds on truthfulness

DOI10.1016/J.GEB.2018.02.001MaRDI QIDQ1651232zbMATH OpenOpenAlexFDO

Authors Ahuva Mu'alem, Michael Schapira

Publication date 12 July 2018

Published in Games and Economic Behavior (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic mechanism designBayesian incentive-compatible mechanismsrandomized truthful mechanismsschedulingtruthfulness-in-expectation mechanisms

Mathematics Subject Classification ID

Bayesian inference (62F15) Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: We present and discuss general techniques for proving inapproximability results for truthful mechanisms. We make use of these techniques to prove lower bounds on the approximability of several non-utilitarian multi-parameter problems. In particular, we demonstrate the strength of our techniques by exhibiting a lower bound of $2-frac1m$ for the scheduling problem with unrelated machines (formulated as a mechanism design problem in the seminal paper of Nisan and Ronen on Algorithmic Mechanism Design). Our lower bound applies to truthful randomized mechanisms (disregarding any computational assumptions on the running time of these mechanisms). Moreover, it holds even for the weaker notion of truthfulness for randomized mechanisms -- i.e., truthfulness in expectation. This lower bound nearly matches the known $frac74$ (randomized) truthful upper bound for the case of two machines (a non-truthful FPTAS exists). No lower bound for truthful randomized mechanisms in multi-parameter settings was previously known. We show an application of our techniques to the workload-minimization problem in networks. We prove our lower bounds for this problem in the inter-domain routing setting presented by Feigenbaum, Papadimitriou, Sami, and Shenker. Finally, we discuss several notions of non-utilitarian "fairness" (Max-Min fairness, Min-Max fairness, and envy minimization). We show how our techniques can be used to prove lower bounds for these notions.

Recommendations

• Setting lower bounds on truthfulness (extended abstract)
• Improved Lower Bounds for Non-utilitarian Truthfulness
• Improved lower bounds for non-utilitarian truthfulness
• Modeling the degree of truthfulness
• Modeling the degree of truthfulness
• scientific article; zbMATH DE number 1962848
• Truth-telling reservations
• On the generic impossibility of truthful behavior: A simple approach

Cites work

• A BGP-based mechanism for lowest-cost routing
• A Characterization of 2-Player Mechanisms for Scheduling
• A course in game theory.
• A deterministic truthful PTAS for scheduling related machines
• A lower bound for scheduling mechanisms
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Algorithmic Game Theory
• Algorithmic mechanism design
• An improved randomized truthful mechanism for scheduling unrelated machines
• Approximation algorithms for combinatorial auctions with complement-free bidders
• Approximation algorithms for scheduling unrelated parallel machines
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms
• Bundling equilibrium in combinatorial auctions
• Combinatorial auctions. Foreword by Vernon L. Smith.
• Competitive generalized auctions
• Copula-based randomized mechanisms for truthful scheduling on two unrelated machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Fair by design: multidimensional envy-free mechanisms
• Frugal path mechanisms
• Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations
• Improved lower bounds for non-utilitarian truthfulness
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Incentive-compatible interdomain routing
• Incentives in Teams
• Mechanism design for fractional scheduling on unrelated machines
• Mechanism design for policy routing
• Mechanisms for multi-unit auctions
• Microeconomic theory
• On the power of randomization in algorithmic mechanism design
• Optimal lower bounds for anonymous scheduling mechanisms
• Prior-independent mechanisms for scheduling
• Subjective-cost policy routing
• The communication requirements of efficient allocations and supporting prices
• The Santa Claus problem
• The Strategy Structure of Two-Sided Matching Markets
• The VCG Mechanism for Bayesian Scheduling
• Truth revelation in approximately efficient combinatorial auctions
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Truthful approximation mechanisms for restricted combinatorial auctions
• Truthful approximation mechanisms for scheduling selfish related machines
• Truthful approximation schemes for single-parameter agents
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Truthful randomized mechanisms for combinatorial auctions
• Twenty lectures on algorithmic game theory
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation

Cited in

(10)

• Setting lower bounds on truthfulness (extended abstract)
• Improved Lower Bounds for Non-utilitarian Truthfulness
• A new lower bound for deterministic truthful scheduling
• Improved lower bounds for non-utilitarian truthfulness
• A proof of the Nisan-Ronen conjecture
• On the Nisan-Ronen conjecture for submodular valuations
• A proof of the Nisan-Ronen conjecture
• Truthful allocation in graphs and hypergraphs
• An algorithmic framework for black-box reductions from Bayesian mechanism design to algorithm design
• Truth-telling reservations

This page was built for publication: Setting lower bounds on truthfulness

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