La programación de trabajos veraz es una variante del diseño del mecanismo del problema de programación del taller de trabajo de la investigación de operaciones .
Tenemos un proyecto compuesto por varios "trabajos" (tareas). Hay varios trabajadores. Cada trabajador puede hacer cualquier trabajo, pero para cada trabajador se necesita una cantidad de tiempo diferente para completar cada trabajo. Nuestro objetivo es asignar puestos de trabajo a los trabajadores de manera que se minimice la duración total del proyecto. En el problema de programación estándar del taller de trabajos, se conocen los tiempos de todos los trabajadores, por lo que tenemos un problema de optimización estándar. Por el contrario, en el problema de la programación veraz del trabajo, no se conocen los horarios de los trabajadores. Le preguntamos a cada trabajador cuánto tiempo necesita para hacer cada trabajo, pero es posible que los trabajadores nos mientan. Por lo tanto, tenemos que incentivar a los trabajadores para que nos digan sus verdaderos horarios pagándoles una determinada cantidad de dinero. El desafío es diseñar un mecanismo de pago que sea compatible con los incentivos.
El problema de la programación veraz del trabajo fue presentado por Nisan y Ronen en su artículo de 1999 sobre el diseño de mecanismos algorítmicos . [1]
Definiciones
Existen trabajos y trabajadores ("m" significa "máquina", ya que el problema proviene de programar trabajos en computadoras). Obrero puede hacer el trabajo a tiempo . Si trabajador se le asigna un conjunto de trabajos , luego puede ejecutarlos a tiempo:
Dada una asignación de puestos de trabajo a los trabajadores, la duración de un proyecto es:
Una asignación óptima es una asignación de puestos de trabajo a los trabajadores en la que se minimiza la rentabilidad. El intervalo mínimo se denota por.
Un mecanismo es una función que toma como entrada la matriz (el tiempo que cada trabajador necesita para hacer cada trabajo) y devuelve como resultado:
- Una asignación de puestos de trabajo a los trabajadores, ;
- Un pago a cada trabajador, .
La utilidad del trabajador , bajo tal mecanismo, es:
Es decir, el agente gana el pago, pero pierde el tiempo que dedica a ejecutar las tareas. Tenga en cuenta que el pago y el tiempo se miden en las mismas unidades (por ejemplo, podemos suponer que los pagos están en dólares y que cada unidad de tiempo le cuesta al trabajador un dólar).
Un mecanismo se llama veraz (o compatible con incentivos ) si cada trabajador puede alcanzar una utilidad máxima informando su verdadero vector de tiempo (es decir, ningún trabajador tiene un incentivo para mentir sobre sus tiempos).
El factor de aproximación de un mecanismo es la relación más grande entre y (cuanto más pequeño, mejor; un factor de aproximación de 1 significa que el mecanismo es óptimo).
La investigación sobre la programación de trabajos veraz tiene como objetivo encontrar límites superiores (positivos) e inferiores (negativos) en los factores de aproximación de los mecanismos veraces.
Cota positiva - m - mecanismo VCG
La primera solución que me viene a la mente es el mecanismo VCG , que es un mecanismo veraz genérico. Se puede utilizar un mecanismo de VCG para minimizar la suma de costos. Aquí, podemos usar VCG para encontrar una asignación que minimice el "total", definido como:
Aquí, se puede minimizar la suma simplemente asignando cada trabajo al trabajador que necesita el menor tiempo para ese trabajo. Para mantener el mecanismo veraz, a cada trabajador que acepta un trabajo se le paga el segundo tiempo más corto por ese trabajo (como en una subasta de Vickrey ).
Sea OPT una asignación que minimiza la utilidad. Luego:
(donde la última desigualdad se sigue del principio del casillero ). Por lo tanto, el factor de aproximación de la solución VCG es como máximo - el número de trabajadores.
El siguiente ejemplo muestra que el factor de aproximación de la solución VCG puede ser exactamente . Supongamos que hay Los trabajos y los horarios de los trabajadores son los siguientes:
- El trabajador 1 puede hacer todos los trabajos en el tiempo 1.
- Los otros trabajadores pueden hacer todos los trabajos a tiempo. , dónde es una pequeña constante.
Luego, el mecanismo VCG asigna todas las tareas al trabajador 1. Tanto el "make-total" como el makespan son . Pero, cuando cada trabajo se asigna a un trabajador diferente, la utilidad es.
Un factor de aproximación de no es muy bueno y muchos investigadores han intentado mejorarlo durante los años siguientes.
Por otro lado, existen algunos resultados de imposibilidad que demuestran que el factor de aproximación no puede ser demasiado pequeño.
Límite negativo - 2
El factor de aproximación de todo mecanismo determinista veraz es al menos 2. [1] : 177–
La prueba es típica de límites inferiores en el diseño de mecanismos. Verificamos escenarios específicos (en nuestro caso, tiempos específicos de los trabajadores). Por veracidad, cuando un solo trabajador cambia su declaración, no debe poder beneficiarse de ella. Esto induce algunas limitaciones en las asignaciones devueltas por el mecanismo en los diferentes escenarios.
En el siguiente esquema de prueba, por simplicidad asumimos que hay 2 trabajadores y que el número de trabajos es par, . Consideramos los siguientes escenarios:
- Los tiempos de ambos trabajadores para todos los trabajos son 1. Dado que el mecanismo es determinista, debe devolver una asignación única. . Supongamos, sin pérdida de generalidad, que (al trabajador 1 se le asignan como máximo tantos trabajos como al trabajador 2).
- Los tiempos del trabajador 1 a los trabajos en están (una constante positiva muy pequeña); los tiempos del trabajador 1 a los trabajos en están ; y los tiempos del trabajador 2 para todos los trabajos siguen siendo 1. El trabajador 1 sabe que, si miente y dice que sus tiempos para todos los trabajos son 1, el mecanismo (determinista) le asignará los trabajos eny su costo estará muy cerca de 0. Para permanecer veraz, el mecanismo debe hacer lo mismo aquí, de modo que el trabajador 1 no se beneficie de la mentira. Sin embargo, el tamaño de la bandeja se puede hacer la mitad de grande dividiendo los trabajos en igualmente entre los agentes.
Por tanto, el factor de aproximación del mecanismo debe ser al menos 2.
Referencias
- ^ a b Nisan, Noam; Ronen, Amir (2001). "Diseño de mecanismos algorítmicos". Juegos y comportamiento económico . 35 (1–2): 166–196. doi : 10.1006 / game.1999.0790 .