Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types
Author
dc.contributor.author
Hoeksma, Ruben
Author
dc.contributor.author
Uetz, Marc
Admission date
dc.date.accessioned
2017-12-21T18:21:18Z
Available date
dc.date.available
2017-12-21T18:21:18Z
Publication date
dc.date.issued
2016
Cita de ítem
dc.identifier.citation
Operations Research Vol. 64, No. 6, November–December 2016, pp. 1438–1450
es_ES
Identifier
dc.identifier.issn
0030-364X
Identifier
dc.identifier.other
10.1287/opre.2016.1522
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/146264
Abstract
dc.description.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
es_ES
Patrocinador
dc.description.sponsorship
Millennium Nucleus Information and Coordination in Networks
ICM-FIC RC130003