Report

Routing and Staffing to Incentivize Servers in Many Server Systems Amy Ward (USC) Raga Gopalakrishnan (Caltech/CU-Boulder/USC) Adam Wierman (Caltech) Sherwin Doroudi (CMU) Service systems are staffed by humans. m strategic servers system performance Service systems are staffed by humans. m Routing and Staffing to Incentivize strategic Servers servers system performance Queueing games:Assumes fixed Classic Queueing: [Hassin and Haviv 2003] • Strategic (arrival and) arrivals service rates. This •talk: Impact of strategic server on system design Service/price competition • Blue for strategic service rates • Yellow for routing/staffing policy parameters • Pink is to highlight. Outline • The M/M/1 Queue – a simple example • Model for a strategic server • The M/M/N Queue Routing which idle server gets the next job? Staffing how many servers to hire? • Classic policies in non-strategic setting • Impact of strategic servers M/M/1/FCFS λ m strategic server Values idleness Cost of effort I( m ) c( m ) U ( m ) = (I1( ml) -/ cm()m-)c ( m ) utility function l W= ? m(m - l) m What is the service rate? { } m = arg max U ( m ) * m >l ( ) l m * 2 ( ) = c' m * l W= * * m m -l ( ) Outline • The M/M/1 queue – a simple example • Model for a strategic server • The strategic M/M/N queue Scheduling Staffing • Classic policies in non-strategic setting • Impact of strategic servers M/M/N/FCFS l m m2 scheduling mN U i ( m;p ) = I i ( m;p ) - c (Umi () m ) = I ( m ) - c ( m ) i i i strategic servers { ( Nash equilibrium mi* Îarg max U i mi , m-i* ;p symmetric m = m for all i * i mi > l / N * )} Why symmetric? This is fair. (Server payment is fixed.) existence? performance? W =? Outline • The M/M/1 queue – a simple example • Model for a strategic server • The strategic M/M/N queue Scheduling Staffing • Classic policies in non-strategic setting • Impact of strategic servers M/M/N/FCFS l m scheduling m2 mN When servers are not strategic… • Fastest-Server-First (FSF) is asymptotically optimal for . [Lin and Kumar 1984] [Armony 2005] • Longest-Idle-Server-First (LISF) is asymptotically optimal subject to fairness (idleness distribution). [Atar 2008] [Armony and Ward 2010] M/M/N/FCFS l m m2 scheduling mN Q: Which policy does better – FSF or its counterpart, SSF? Theorem: No symmetric equilibrium exists under either FSF or SSF. Q: How about Longest-Idle-Server-First (LISF)? Theorem: All idle-time-order-based policies result in the same symmetric equilibrium as Random. Also, (Haji and Ross, 2013). Q: Can we do better than Random? Answer: Yes, but … M/M/N/FCFS l m m2 Random mN Theorem: For every λand N, under mild conditions on c, there exists a unique symmetric equilibrium service rate μ* under Random. Furthermore, U(μ*)>0. What is the symmetric equilibrium service rate? U ( m1 , m ) = I ( m1 , m ) - c ( m1 ) First order condition: ¶I ( m¶U ,m 1 ()m1 , m ) = c' ( m=)0 ¶ m1 ¶ m m1 = m 1 m1 = m Proposition: Under Random routing, æ æ öö ç ÷÷ æ r öç ræ m ö çç C(N , r ) ÷÷ I( m1 , m ) = ç 1- ÷ 1- ç 1- ÷ 1+ æ Nøç N è m1 ø ç è m1 ö ÷ ÷ N r + 1ç ç ÷÷ ç ÷ m è ø è øø è -1 ö æ m1 ö m1 ¶I I2 l æ C(N , r ) C( N , r ) ç 1+ ÷ = 2 + ç 1- ÷ 2 ¶ m1 m1 N - r çè N - ( r + 1- m1 / m ) è m ø m ( N - ( r + 1- m / m ) ) ÷ø 1 where r = l / m and C(N , r ) isthe Erlang - C formula rN C(N , r ) = N N! N - r å N -1 j=0 r j j! + r N N N! N - r . Gumbel (1960) for the fully heterogeneous case. Problem: This is a mess!!! There is no hope to use this to decide on a staffing level. Outline • The M/M/1 queue – a simple example • Model for a strategic server • The strategic M/M/N queue Scheduling Staffing • Classic policies in non-strategic setting • Impact of strategic servers M/M/N/FCFS l m m Random When servers are not strategic… staffing N l m Q: How many servers to staff? Objective: Minimize total system cost C l (N ) = cS N + wlWml N opt ,l = arg min C l (N ) N >l / m Answer: Square root staffing is asymptotically optimal. Halfin and Whitt (1981) and Borst, Mandelbaum and Reiman (2004) N BMR,l l l * = + b (cS , w) m m M/M/N/FCFS l m m Random staffing N m When servers are strategic… Q: How many servers to staff? Objective: Minimize total system cost C (N ) = cS N + wlW l N opt ,l l m* l = arg min C (N ) N >l / m Problem: Explicit expression is unknown. Fortunately, there is hope if we let λbecome large. l M/M/N/FCFS l m Random m N m When servers are strategic… 1. Rate-independent staffing N = f (l ) + o ( f (l )) l 2. Rate-dependent staffing æ æ l ö N = f ç l ,* ÷ + o ç èm ø è l æ l öö f ç l ,* ÷ ÷ è m øø staffing l M/M/N/FCFS l m m Random æ æ l ö N = f ç l ,* ÷ + o ç èm ø è l staffing N æ l öö f ç l ,* ÷ ÷ è m øø In order that there exists μ*,λ with l m Such a solution is not desirable. 0 < lim inf m *,l < limsup m *,l < ¥ l ®¥ Eliminates square-root staffing. Must staff order λmore. The cost function blows up at rate λ. we must staff l ®¥ ææ l öö æ l ö N = a ç l ,* ÷ + o ç ç l ,* ÷ ÷ for a > 1. èm ø èè m øø l M/M/N/FCFS l m m Random staffing N ææ l öö æ l ö N = a ç l ,* ÷ + o ç ç l ,* ÷ ÷ for a > 1. èm ø èè m øø What is a? Fluid scale cost. l m l ì a a -1 ü Set a = a* = arg min íc : 2 = mc'( m ) ý S a>1 î m a þ Since servers are strategic. Theorem: The staffing Nλ is asymptotically optimal in the sense that Cl N l lim l ®¥ C l ( ) (N ) opt ,l = 1. M/M/N/FCFS l m m Random staffing N ææ l öö æ l ö N = a ç l ,* ÷ + o ç ç l ,* ÷ ÷ for a > 1. èm ø èè m øø Example: p Suppose c m = m for some p ³ 1. l l m ( ) ìï 1.5 as p ¯ 1 1+ 2 / p ®í . Then a = 1+ 1/ p ïî 1.0 as ¥ l 1 l Note that r = l *,l ® < 1 as l ® ¥. Convexity helps. a N m 2 If p = 1, then a = 1.5 and m * = 0.222, and r l ® Efficiency is decreased. 3 as l ® ¥. Concluding remarks • We need to rethink optimal system design to account for how servers respond to incentives (i.e., when servers are strategic)! $$$$ l M/M/N/FCFS m FSF,SSF LISF = Random ? m m We solved for an asymptotically optimal staffing There is a loss of efficiency. l N > . N BMR,l .