Truthful mechanism design for multidimensional scheduling via cycle monotonicity

DOI10.1016/j.geb.2008.08.001zbMath1168.90454OpenAlexW2068852191MaRDI QIDQ834857

Chaitanya Swamy, Ron Lavi

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

Mathematics Subject Classification ID

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

Related Items (22)

Private Capacities in Mechanism Design ⋮ The VCG Mechanism for Bayesian Scheduling ⋮ Setting lower bounds on truthfulness ⋮ Truthful optimization using mechanisms with verification ⋮ Mechanisms for scheduling with single-bit private values ⋮ Black-box reductions for cost-sharing mechanism design ⋮ Recent Developments in the Mechanism Design Problem for Scheduling ⋮ Mechanism Design ⋮ Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs ⋮ Optimal collusion-resistant mechanisms with verification ⋮ On optimal mechanism design for a sequencing problem ⋮ Average-case approximation ratio of scheduling without payments ⋮ No truthful mechanism can be better than \(n\) approximate for two natural problems ⋮ A Unified Approach to Truthful Scheduling on Related Machines ⋮ A new lower bound for deterministic truthful scheduling ⋮ Online scheduling of jobs with favorite machines ⋮ Obviously Strategyproof Mechanisms for Machine Scheduling. ⋮ Bribeproof Mechanisms for Two-Values Domains ⋮ TESTING THE QUANTAL RESPONSE HYPOTHESIS ⋮ A lower bound for scheduling mechanisms ⋮ The Pareto frontier of inefficiency in mechanism design ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• A necessary and sufficient condition for rationalizability in a quasilinear context
• Multidimensional incentive compatibility and mechanism design
• An approximation algorithm for the generalized assignment problem
• Truthful approximation mechanisms for scheduling selfish related machines
• Maximal Flow Through a Network
• Finding Minimum-Cost Circulations by Successive Approximation
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
• Truth revelation in approximately efficient combinatorial auctions
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• Approximation techniques for utilitarian mechanism design
• Optimal Auction Design
• Incentives in Teams
• STACS 2004
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Mechanism Design for Fractional Scheduling on Unrelated Machines
• Algorithms – ESA 2005
• State Constraints in Convex Control Problems of Bolza
• Algorithmic mechanism design

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