Paper Info
Title
Two dimensional optimal mechanism design for a sequencing problem
Abstract
We propose an optimal mechanism for a sequencing problem where the jobs' processing times and waiting costs are private. Given public priors for jobs' private data, we seek to find a scheduling rule and incentive compatible payments that minimize the total expected payments to the jobs. Here, incentive compatible refers to a Bayes-Nash equilibrium. While the problem can be efficiently solved when jobs have single dimensional private data, we here address the problem with two dimensional private data. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem in [13]. Our implementation is randomized and truthful in expectation. The main steps are a compactification of an exponential size linear program, and a combinatorial algorithm to decompose feasible interim schedules. In addition, in computational experiments with random instances, we generate some more insights.
Year
DOI
Venue
2013
10.1007/978-3-642-36694-9_21
IPCO
Keywords
Field
DocType
dimensional private data,linear program,open problem,private data,sequencing problem,incentive compatible payment,single dimensional private data,dimensional optimal mechanism design,bayes-nash equilibrium,linear programming technique,combinatorial algorithm
Mathematical optimization,Open problem,Incentive compatibility,Optimal mechanism,Computer science,Algorithmic game theory,Schedule,Mechanism design,Linear programming,Time complexity
Conference
Citations 
PageRank 
References 
5
0.43
12
Authors
2
Name
Order
Citations
PageRank
Ruben Hoeksma1338.23
Marc Uetz245643.99