Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research. We have a project composed of several "jobs" (tasks). There are several workers. Each worker can do any job, but for each worker it takes a different amount of time to complete each job. Our goal is to allocate jobs to workers such that the total makespan of the project is minimized. In the standard job shop scheduling problem, the timings of all workers are known, so we have a standard optimization problem. In contrast, in the truthful job scheduling problem, the timings of the workers are not known. We ask each worker how much time he needs to do each job, but, the workers might lie to us. Therefore, we have to give the workers an incentive to tell us their true timings by paying them a certain amount of money. The challenge is to design a payment mechanism which is incentive compatible. The truthful job scheduling problem was introduced by Nisan and Ronen in their 1999 paper on algorithmic mechanism design.
Definitions There are n {\displaystyle n} jobs and m {\displaystyle m} workers ("m" stands for "machine", since the problem comes from scheduling jobs to computers). Worker i {\displaystyle i} can do job j {\displaystyle j} in time T i , j {\displaystyle T_{i,j}} . If worker i {\displaystyle i} is assigned a set of jobs J i {\displaystyle J_{i}} , then he can execute them in time:
T i ( J i ) = ∑ j ∈ J i t i , j {\displaystyle T_{i}(J_{i})=\sum _{j\in J_{i}}t_{i,j}}
Given an allocation J 1 , … , J m {\displaystyle J_{1},\dots ,J_{m}} of jobs to workers, The makespan of a project is:
M a k e S p a n ( J 1 , … , J n ) = max i T i ( J i ) {\displaystyle MakeSpan(J_{1},\dots ,J_{n})=\max _{i}{T_{i}(J_{i})}}
An optimal allocation is an allocation of jobs to workers in which the makespan is minimized. The minimum makespan is denoted by M i n M a k e S p a n {\displaystyle MinMakeSpan} . A mechanism is a function that takes as input the matrix T {\displaystyle T} (the time each worker needs to do each job) and returns as output:
An allocation of jobs to workers, J 1 , … , J n {\displaystyle J_{1},\dots ,J_{n}} ; A payment to each worker, p 1 , … , p n {\displaystyle p_{1},\dots ,p_{n}} . The utility of worker i {\displaystyle i} , under such mechanism, is:
u i = p i − T i ( J i ) {\displaystyle u_{i}=p_{i}-T_{i}(J_{i})}
I.e, the agent gains the payment, but loses the time that it spends in executing the tasks. Note that payment and time are measured in the same units (e.g., we can assume that the payments are in dollars and that each time-unit costs the worker one dollar). A mechanism is called truthful (or incentive compatible) if every worker can attain a maximum utility by reporting his true timing vector (i.e., no worker has an incentive to lie about his timings). The approximation factor of a mechanism is the largest ratio between M a k e s p a n {\displaystyle Makespan} and M i n M a k e s p a n {\displaystyle MinMakespan} (smaller is better; an approximation factor of 1 means that the mechanism is optimal). The research on truthful job scheduling aims to find upper (positive) and lower (negative) bounds on approximation factors of truthful mechanisms.
Positive bound – m – VCG mechanism The first solution that comes to mind is VCG mechanism, which is a generic truthful mechanism. A VCG mechanism can be used to minimize the sum of costs. Here, we can use VCG to find an allocation which minimizes the "make-total", defined as:
… excerpt ends here. Continue reading the full article.
