Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types

Ruben Hoeksma () and Marc Uetz ()
Additional contact information
Ruben Hoeksma: Departamento de Ingeniería Industrial, Universidad de Chile, Santiago, Chile
Marc Uetz: Department of Applied Mathematics, University of Twente, Enschede, Netherlands

Operations Research, 2016, vol. 64, issue 6, 1438-1450

Abstract: We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria.

Keywords: scheduling; mechanism design; linear programming (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2016.1522 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:6:p:1438-1450

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().