Setting lower bounds on truthfulness (extended abstract)

MaRDI QIDQ2934709zbMATH OpenFDO

Authors Ahuva Mu'alem, Michael Schapira

Publication date 18 December 2014

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Recommendations

• Setting lower bounds on truthfulness
• Improved Lower Bounds for Non-utilitarian Truthfulness
• Improved lower bounds for non-utilitarian truthfulness
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• A new lower bound for deterministic truthful scheduling

Cited in

(29)

• Truthful optimization using mechanisms with verification
• Improved Lower Bounds for Non-utilitarian Truthfulness
• The anarchy of scheduling without money
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• A lower bound for scheduling mechanisms
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions
• On truthfulness and approximation for scheduling selfish tasks
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Average-case approximation ratio of scheduling without payments
• The power of verification for one-parameter agents
• No truthful mechanism can be better than n approximate for two natural problems
• Scheduling without payments
• Improved lower bounds for non-utilitarian truthfulness
• Mechanisms for scheduling with single-bit private values
• Reducing truth-telling online mechanisms to online optimization
• Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
• Fair by design: multidimensional envy-free mechanisms
• Distributed algorithmic mechanism design for scheduling on unrelated machines
• Optimal collusion-resistant mechanisms with verification
• Truthful mechanisms for selfish routing and two-parameter agents
• Private Capacities in Mechanism Design
• Unrelated parallel machine scheduling -- perspectives and progress
• Bribeproof Mechanisms for Two-Values Domains
• Setting lower bounds on truthfulness
• On scheduling mechanisms beyond the worst case
• The anarchy of scheduling without money
• New bounds for truthful scheduling on two unrelated selfish machines
• A truthful constant approximation for maximizing the minimum load on related machines

This page was built for publication: Setting lower bounds on truthfulness (extended abstract)

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