Truthful job scheduling

<h2 id="definitions">Definitions</h2>
There are 
 
 
 
 n
 
 
 {\displaystyle n}
 
 jobs and 
 
 
 
 m
 
 
 {\displaystyle m}
 
 workers ("m" stands for "machine", since the problem comes from scheduling <a href="/facts/Job_(computing)/pW4LEz0Q">jobs</a> 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 <a href="/facts/Makespan/w1HEjJaQ">makespan</a> 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:

<ul><li>An allocation of jobs to workers, 
 
 
 
 
 J
 
 1
 
 
 ,
 …
 ,
 
 J
 
 n
 
 
 
 
 {\displaystyle J_{1},\dots ,J_{n}}
 
;</li>
<li>A payment to each worker, 
 
 
 
 
 p
 
 1
 
 
 ,
 …
 ,
 
 p
 
 n
 
 
 
 
 {\displaystyle p_{1},\dots ,p_{n}}
 
.</li></ul>
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 <a href="/facts/Incentive_compatible/pE8NEGNx">incentive compatible</a>) 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.

<h2 id="positive-bound--m--vcg-mechanism">Positive bound – m – VCG mechanism</h2>
The first solution that comes to mind is <a href="/facts/VCG_mechanism/6qpvhNsW">VCG mechanism</a>, 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:

M
        a
        k
        e
        T
        o
        t
        a
        l
        (
        
          J
          
            1
          
        
        ,
        …
        ,
        
          J
          
            n
          
        
        )
        =
        
          ∑
          
            i
          
        
        
          
            T
            
              i
            
          
          (
          
            J
            
              i
            
          
          )
        
      
    
    {\displaystyle MakeTotal(J_{1},\dots ,J_{n})=\sum _{i}{T_{i}(J_{i})}}

Here, minimizing the sum can be done by simply allocating each job to the worker who needs the shortest time for that job. To keep the mechanism truthful, each worker that accepts a job is paid the second-shortest time for that job (like in a <a href="/facts/Vickrey_auction/5PRPtnI5">Vickrey auction</a>).
Let OPT be an allocation which minimizes the makespan. Then:

M
        a
        k
        e
        S
        p
        a
        n
        [
        V
        C
        G
        ]
        ≤
        M
        a
        k
        e
        T
        o
        t
        a
        l
        [
        V
        C
        G
        ]
        ≤
        M
        a
        k
        e
        T
        o
        t
        a
        l
        [
        O
        P
        T
        ]
        ≤
        m
        ⋅
        M
        a
        k
        e
        S
        p
        a
        n
        [
        O
        P
        T
        ]
      
    
    {\displaystyle MakeSpan[VCG]\leq MakeTotal[VCG]\leq MakeTotal[OPT]\leq m\cdot MakeSpan[OPT]}

(where the last inequality follows from the <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>). Hence, the approximation factor of the VCG solution is at most 
 
 
 
 m
 
 
 {\displaystyle m}
 
 – the number of workers.
The following example shows that the approximation factor of the VCG solution can indeed be exactly 
 
 
 
 m
 
 
 {\displaystyle m}
 
. Suppose there are 
 
 
 
 n
 =
 m
 
 
 {\displaystyle n=m}
 
 jobs and the timings of the workers are as follows:

<ul><li>Worker 1 can do every job in time 1.</li>
<li>The other workers can do every job in time 
 
 
 
 1
 +
 ϵ
 
 
 {\displaystyle 1+\epsilon }
 
, where 
 
 
 
 ϵ
 >
 0
 
 
 {\displaystyle \epsilon >0}
 
 is a small constant.</li></ul>
Then, the VCG mechanism allocates all tasks to worker 1. Both the "make-total" and the makespan are 
 
 
 
 n
 =
 m
 
 
 {\displaystyle n=m}
 
. But, when each job is assigned to a different worker, the makespan is 
 
 
 
 1
 +
 ϵ
 
 
 {\displaystyle 1+\epsilon }
 
.
An approximation factor of 
 
 
 
 m
 
 
 {\displaystyle m}
 
 is not very good, and many researchers have tried to improve it over the following years.
On the other hand, there are some impossibility results that prove that the approximation factor cannot be too small.

<h2 id="negative-bound--2">Negative bound – 2</h2>
The approximation factor of every truthful deterministic mechanism is at least 2.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>: 177- 
The proof is typical of lower bounds in mechanism design. We check specific scenarios (in our case, specific timings of the workers). By truthfulness, when a single worker changes his declaration, he must not be able to gain from it. This induces some constraints on the allocations returned by the mechanism in the different scenarios.
In the following proof sketch, for simplicity we assume that there are 2 workers and that the number of jobs is even, 
 
 
 
 n
 =
 2
 k
 
 
 {\displaystyle n=2k}
 
. We consider the following scenarios:

<ol><li>The timings of both workers to all jobs are 1. Since the mechanism is deterministic, it must return a unique allocation 
 
 
 
 
 J
 
 1
 
 
 ,
 
 J
 
 2
 
 
 
 
 {\displaystyle J_{1},J_{2}}
 
. Suppose, without loss of generality, that 
 
 
 
 
 |
 
 
 J
 
 1
 
 
 
 |
 
 ≤
 
 |
 
 
 J
 
 2
 
 
 
 |
 
 
 
 {\displaystyle |J_{1}|\leq |J_{2}|}
 
 (worker 1 is assigned at most as many jobs as worker 2).</li>
<li>The timings of worker 1 to the jobs in 
 
 
 
 
 J
 
 1
 
 
 
 
 {\displaystyle J_{1}}
 
 are 
 
 
 
 ϵ
 
 
 {\displaystyle \epsilon }
 
 (a very small positive constant); the timings of worker 1 to the jobs in 
 
 
 
 
 J
 
 2
 
 
 
 
 {\displaystyle J_{2}}
 
 are 
 
 
 
 1
 +
 ϵ
 
 
 {\displaystyle 1+\epsilon }
 
; and the timings of worker 2 to all jobs is still 1. Worker 1 knows that, if he lies and says that his timings to all jobs are 1, the (deterministic) mechanism will allocate him the jobs in 
 
 
 
 
 J
 
 1
 
 
 
 
 {\displaystyle J_{1}}
 
 and his cost will be very near 0. In order to remain truthful, the mechanism must do the same here, so that worker 1 does not gain from lying. However, the makespan can be made half as large by dividing the jobs in 
 
 
 
 
 J
 
 2
 
 
 
 
 {\displaystyle J_{2}}
 
 equally between the agents.</li></ol>
Hence, the approximation factor of the mechanism must be at least 2.

<h2 id="monotonicity-and-truthfulness">Monotonicity and Truthfulness</h2>
Consider the special case of <a href="/facts/Uniform-machines_scheduling/LFDtRUfD">Uniform-machines scheduling</a>, in which the workers are single-parametric: for each worker there is a speed, and the time it takes the worker to do a job is the job length divided by the speed. The speed is the worker's private information, and we want to incentivize machines to reveal their true speeds. Archer and Tardos<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> prove that a scheduling algorithm is truthful if and only if it is monotone. This means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:

<ul><li>Auletta, De Prisco, Penna and Persiano<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.</li>
<li>Ambrosio and Auletta<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> proved that the <a href="/facts/Longest_processing_time/EcPS5uh3">Longest Processing Time</a> algorithm is monotone whenever the machine speeds are powers of some c ≥ 2, but not when c ≤ 1.78. In contrast, <a href="/facts/List_scheduling/qUscTqbx">List scheduling</a> is not monotone for c > 2.</li>
<li>Andelman, Azar and Sorani<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> presented a 5-approximation monotone algorithm, which runs in polytime even when the number of machines is variable.</li>
<li>Kovacz<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> presented a 3-approximation monotone algorithm.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473. doi:10.1006/game.1999.0790. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". Games and Economic Behavior. 35 (1–2): 166–196. CiteSeerX 10.1.1.16.7473. doi:10.1006/game.1999.0790. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Archer, A.; Tardos, E. (2001-10-01). "Truthful mechanisms for one-parameter agents". Proceedings 42nd IEEE Symposium on Foundations of Computer Science. pp. 482–491. doi:10.1109/SFCS.2001.959924. ISBN 0-7695-1390-5. S2CID 11377808. <a href="0-7695-1390-5" target="_blank">0-7695-1390-5</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines". In Diekert, Volker; Habib, Michel (eds.). Stacs 2004. Lecture Notes in Computer Science. Vol. 2996. Berlin, Heidelberg: Springer. pp. 608–619. doi:10.1007/978-3-540-24749-4_53. ISBN 978-3-540-24749-4. <a href="978-3-540-24749-4" target="_blank">978-3-540-24749-4</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Ambrosio, Pasquale; Auletta, Vincenzo (2005). "Deterministic Monotone Algorithms for Scheduling on Related Machines". In Persiano, Giuseppe; Solis-Oba, Roberto (eds.). Approximation and Online Algorithms. Lecture Notes in Computer Science. Vol. 3351. Berlin, Heidelberg: Springer. pp. 267–280. doi:10.1007/978-3-540-31833-0_22. ISBN 978-3-540-31833-0. <a href="978-3-540-31833-0" target="_blank">978-3-540-31833-0</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). "Truthful Approximation Mechanisms for Scheduling Selfish Related Machines". In Diekert, Volker; Durand, Bruno (eds.). Stacs 2005. Lecture Notes in Computer Science. Vol. 3404. Berlin, Heidelberg: Springer. pp. 69–82. doi:10.1007/978-3-540-31856-9_6. ISBN 978-3-540-31856-9. <a href="978-3-540-31856-9" target="_blank">978-3-540-31856-9</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Kovács, Annamária (2005). "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines". In Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algorithms – ESA 2005. Lecture Notes in Computer Science. Vol. 3669. Berlin, Heidelberg: Springer. pp. 616–627. doi:10.1007/11561071_55. ISBN 978-3-540-31951-1. <a href="978-3-540-31951-1" target="_blank">978-3-540-31951-1</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Truthful job scheduling open-in-new

Truthful job scheduling