On Designing
Truthful Mechanisms for
Online Scheduling
V. Auletta, R. De Prisco, P.P. and G. Persiano
Università di Salerno
The Internet
Open, self organized, no central authority, anarchic
Different “components” which
• have their own goal
• may not follow the “protocol”
Selfish agents
The Internet
Open, self organized, no central authority, anarchic
Link down
AS1
source
destination
AS2
An Autonomous System may report false link status
to redirect traffic to another AS
Routing/Scheduling
Scheduling Selfish Machines:
Selfish users own the links and privately know their speeds
s1 0
s2
0
source
sm 0
destination
•Unsplittable traffic J1, J2 ,…,Jn
•We look at the network congestion (makespan)
max i Wi /si
Wi= Jk assigned to machine i
Mechanism design
Mechanism:
M=(A,P)
Computes a solution
X=A(r1,r2,…, ri ,…,rm )
Provides a payment
Pi(r1,r2,…, ri ,…,rm )
s1,s2,…, si ,…,sn
costtrue
input
i(X,s
i) = wi/si
Agents’ GOAL: maximize their own utility
ui (ri) := Pi(r1,r2,…, ri ,…,rm ) – costi(X,si)
Mechanism design
Strategyproof mechanisms:
no incentive to lie (report ri  si)
ui (si)  ui (ri)
(truth-telling is the best strategy)
Scheduling Selfish Machines
Monotone algorithms: an agent declaring a higher
speed does not get less work.
A monotone
[Archer & Tardos, FOCS 2001]
M=(A,P) strategyproof
Example: Greedy Algorithm
NOT MONOTONE
2
2
3
3
1
1+
1+
(1+)2
2
2
1
Related Work
• Algorithms:
• (1 + )-APX for any m
[Hochbaum & Shmoys, J. ACM 1987]
• 8-competitive for any m [Aspnes & Azar & Fiat & Plotkin & Waarts, STOC93]
• -competitive for m = 2 [Graham, Bell Syst. J. 1966], no better than 3/2
• Monotone Algorithms (Mechanisms):
• 5-APX for any m
[Andelman & Azar & Sorani, STACS05]
• (1 + )-APX for m = O(1) [Andelman & Azar & Sorani, STACS05]
• Mechanisms With Verification:
• (1 + )-APX for any m [Auletta & De Prisco & P. & Persiano, ICALP04]
Monotonization techniques
Algorithm
Mechanism
A
A
hard
M=(A,P)
Amon
loss of performance
M=(Amon,P)
Our contribution (1/2)
(the case of two machines)
Offline:
A
“easy”
Amon
c’ = c(1+)
c-apx
c’-apx
A black-box, polytime
Online:
A
Jobs hard
arrive one by one, no reallocation!
Amon
c •  < c’  c • 
Proved c-comp
for any m = O(1) c’-comp
in [Andelman & Azar & Sorani, STACS05]
must loose something
Lower Bound
Theorem 3: There is no r-competitive online monotone
algorithm, where r  min {r, 1+1/r} and r > 1
Corollary 4: No truthful mechanism can be less than
-competitive, even for 2 jobs and 2 machines.
Lower Bound
Theorem 3: There is no r-competitive online monotone
algorithm, where r  min {r, 1+1/r} and r > 1
Proof:
1
r
r
1
r
1
1
1
1
r
r/opt1+1/r
= r/1=r
r
1
r
Upper Bound (m = 2)
Theorem 5:
A
c-comp
Amon
c’-comp
• c’  max {cr, 1+1/r},  r  1
• c is the comp. ratio on identical speeds
Corollary 5:
Greedy
Greedymon
3/2-comp
c’-comp
c’= 1.823... (-comp)
(1-comp)
Lower bound: =1.62… (2 jobs).
Our contribution (2/2)
(any number of machines)
Mechanisms with Verification: Observe jobs’ released time
Weak Monotonicity Suffices
[Auletta et al, ICALP04]
Online 12-competitive strategyproof mechanism for any m
Mechanisms With Verification
Weakly Monotone algorithms:
w1
w2
s1
s2
w1’
w2’
s1
s2
…
…
wi
… wm
si
sm
wi’
s i’
’
w
… m
sm
si’ > si
wi > 0
wi’ > 0
Mechanisms With Verification
An 8-competitive algorithm:
2opt
UB
Jk
Jk
Jk
Jk
w1
Jk
w2
s1  s 2
wi
wm
 …  si  … 
sm
Try UB = 1, 2, 4, 8, ...  stop UB ≤ 2opt
Mechanisms With Verification
Problem:
Jk
Jk
s1
sj
si
“hole”
machine
sj>s
i’>si+1 shifts
no work
sm
sj+1
Mechanisms With Verification
Fix: Avoid “Holes”
Jk
Jk
Jk
OK
Jk
Jk
NO, Reallocate
Mechanisms With Verification
Fix: Analysis
Jk
Original alg
8opt
Reallocated
4opt
12-comp. mechanism
Open Questions
• Close the gaps:
No verification
Verification
m
Lower Bound
Upper Bound
2
1.62…
1.823…
O(1)
1.62…
????
any
1.62…
12
Thank You