Truthful mechanism design for multidimensional scheduling via cycle monotonicity

DOI10.1016/J.GEB.2008.08.001zbMATH Open1168.90454OpenAlexW2068852191MaRDI QIDQ834857FDOQ834857

Authors: Ron Lavi, Chaitanya Swamy 

Publication date: 27 August 2009

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

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.5034

Recommendations

• Truthful Mechanisms for Competitive Reward-Based Scheduling
• On truthfulness and approximation for scheduling selfish tasks
• On designing truthful mechanisms for online scheduling
• Structural Information and Communication Complexity
• A truthful mechanism for interval scheduling
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• Truthful approximation mechanisms for scheduling selfish related machines
• STACS 2005

Mathematics Subject Classification ID

Social choice (91B14) Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Maximal Flow Through a Network
• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for NP-hard problems.
• Finding Minimum-Cost Circulations by Successive Approximation
• Title not available (Why is that?)
• Approximation algorithms for scheduling unrelated parallel machines
• Optimal Auction Design
• Incentives in Teams
• State Constraints in Convex Control Problems of Bolza
• Algorithmic mechanism design
• A necessary and sufficient condition for rationalizability in a quasilinear context
• Multidimensional incentive compatibility and mechanism design
• A lower bound for scheduling mechanisms
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
• Truth revelation in approximately efficient combinatorial auctions
• STACS 2004
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Setting lower bounds on truthfulness (extended abstract)
• Truthful approximation mechanisms for scheduling selfish related machines
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• Mechanism Design for Fractional Scheduling on Unrelated Machines
• Approximation techniques for utilitarian mechanism design
• Algorithms – ESA 2005

Cited In (30)

• Truthful optimization using mechanisms with verification
• Online scheduling of jobs with favorite machines
• A lower bound for scheduling mechanisms
• Black-box reductions for cost-sharing mechanism design
• On optimal mechanism design for a sequencing problem
• The VCG Mechanism for Bayesian Scheduling
• Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs
• Mechanisms with monitoring for truthful RAM allocation
• Singleton Acyclic Mechanisms and Their Applications to Scheduling Problems
• Average-case approximation ratio of scheduling without payments
• Recent developments in the mechanism design problem for scheduling
• A new lower bound for deterministic truthful scheduling
• A unified approach to truthful scheduling on related machines
• Mechanism design
• No truthful mechanism can be better than \(n\) approximate for two natural problems
• Black-box reductions for cost-sharing mechanism design
• Mechanisms for scheduling with single-bit private values
• Optimal collusion-resistant mechanisms with verification
• Testing the quantal response hypothesis
• A proof of the Nisan-Ronen conjecture
• Private Capacities in Mechanism Design
• Cycle monotonicity in scheduling models
• Bribeproof Mechanisms for Two-Values Domains
• On scheduling mechanisms beyond the worst case
• Setting lower bounds on truthfulness
• The Pareto frontier of inefficiency in mechanism design
• Bayesian truthful mechanisms for job scheduling from bi-criterion approximation algorithms
• Mechanisms for scheduling with single-bit private values
• Truthful mechanism design via correlated tree rounding
• Obviously Strategyproof Mechanisms for Machine Scheduling.

This page was built for publication: Truthful mechanism design for multidimensional scheduling via cycle monotonicity

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