Efficiency through disinformation

RichardMetzler,1,2MarkKlein,3andYaneerBar-Yam1

NewEnglandComplexSystemsInstitute,24Mt.AuburnSt.,Cambridge,MA02138,USADepartmentofPhysics,MassachusettsInstituteofTechnology,Cambridge,MA02139,USA3

CenterforCoordinationScience,MassachusettsInstituteofTechnology,Cambridge,MA02139,USA

21

arXiv:cond-mat/0312266v1 [cond-mat.dis-nn] 10 Dec 2003Westudytheimpactofdisinformationonamodelofresourceallocationwithindependentselfishagents:clientssendrequeststooneoftwoservers,dependingonwhichoneisperceivedasofferingshorterwaitingtimes.Delaysintheinformationabouttheservers’stateleadstooscillationsinload.Serverscangivefalseinformationabouttheirstate(globaldisinformation)orrefuseservicetoindividualclients(localdisinformation).Wediscussthetradeoffbetweenpositiveeffectsofdisinformation(attenuationofoscillations)andnegativeeffects(increasedfluctuationsandreducedadaptability)fordifferentparametervalues.

Competitionforlimitedresourcesoccursinmanydifferentsituations,anditofteninvolveschoosingtheresourceleastpopularamongcompetitors–onecanthinkofdriverswhowanttotaketheleastcrowdedroad,investorswhowanttobuyhotstocksbeforeotherbuyersdrivethepriceup,computersthatsendrequeststotheleastbusyservers,andmanymore.Fromanindividualperspective,agentsinthesescenariosactselfishly–theywanttoachievetheirparticularaims.Atthesametime,thisselfishbehaviorcanbebeneficialforthesystemasawhole,insofarasitleadstoeffectiveresourceutilization[1];however,thisisnotalwaysthecase.Fromthepointofviewofthesystem,theproblemthenbecomesoneofdistributionofresources,ratherthancompetition.

Themostcommonlystudiedmodelinthiscontext,theMinorityGame(MG)[2,3,4],hasagentschooseoneoftwoalternatives,basingtheirdecisiononashorthistoryoftheglobalstateofthesystem.Amultitudeofpossiblestrategiesfortheagentscanbeconceived.OnerecurringthemeinmanyoftheMG’svariationsisoscillationsofpreferences:insomecases,preferencesoscillateintime[5,6],whereasinothers,areactionofthesystemtoagivenhistorypatternwillbefollowedbytheoppositeofthatreactionthenexttimethispatternoccurs[7,8].Thepresenceofoscillationsindicatessuboptimalresourceutilization.Theirsourceisthefactthatagentsmaketheirdecisionbasedonobsoletedata,i.e.,thereisadelaybetweenthetimethattheinformationunderlyingtheirdecisionisgeneratedandthetimetheirdecisionisevaluated.ThisisoftenobscuredbytheuseofdiscretetimestepsinmostvariationsoftheMG.Inthispaper,westudyacontinuous-timeMG-likescenariowithanexplicittimedelay,whichwasinspiredbythecompetitionofcomputersfornetworkserverservice,butcanserveasamodelcaseforotherproblems.

Wealsointroduceanewwaytothinkaboutcontrollingthedynamicsofthesystem.Inpreviouspapers,possiblewaystoimproveefficiencywereexploredfromthepointofviewofagents’strategies:howshouldanagentbehavetoachievemaximumpayoff?Theresult,however,wasmeasuredasanaggregatequantity–thetotaldegreeofresourceutilization.Inthispaper,weassumethattheagentsareselfishandshort-sighted,andtheirstrategyisnotaccessibletomodification.Responsibilityforsystemefficiencylieswiththeservers,whocaninfluencebehaviorbyprovidingincorrectinformation.Wefirstintroducethesystem,studyitsnativedynamics,anddetermineunderwhatcircumstancescontrolmeasurescanimproveefficiency.Wethenpresentvariouspossiblescenariosofinfluencingtheglobalbehavior.

Themodel–Thesystemweconsider[9]consistsoftwoserversR1andR2,whichofferthesameservicetoanumberNofclients.Clientssenddatapacketstooneoftheservers.AfteratraveltimeτT,thepacketsarriveattheserver,andareaddedtoaqueue.ServersneedatimeτPtoprocesseachrequest.WechoosethetimescalesuchthattP=1.Whenaclient’srequestiscompleted,theserversendsa“done”message(whichtakesanotherτTtoarrive)totheclient.TheclientisthenidleforatimeτI,afterwhichitsendsanewpacket.Clientsreceiveinformationaboutthestateofeachserver.Theydecidewhichserveroffersshorterwaitingtimesbasedonthisinformation,andsendtheirpacketstotherespectiveserver.However,forvariousreasons,theinformationtheyreceiveisobsolete–theyhaveaccesstothelengthofthequeuesadelaytimeτDago.

Thesystemcanbesolvedsimply,ifbothserversacceptallincomingrequestsanddemandisdistributeduniformlyenough,suchthatbothserversarebusyatalltimes.TheonlyrelevantvariablesareN1(t)andN2(t),thenumberofclientswhosedataisinthequeueorbeingprocessedbyR1andR2,respectively,attimet;wetreatthemascontinuousvariables.Idleclientsdonothavetobetakenintoaccountexplicitly;neitherdoclientswhoarewaitingfortheir“done”messagefromtheserver–forourpurposes,theyarethesameasidleagents.Wewillfirstsolvetheproblemneglectingagentswhosemessageistravellingtotheserver,thenincludenon-vanishingtraveltimes.

Thereareonlytwoprocesseswhichchangethelengthofthequeues:(a)Duetoprocessedrequests,bothN1andN2decreaseby1pertimeunit.(b)Inthesametimespan,twoclients(whosedatawasprocessedbyR1andR2atimeτT+τIago)comparetheobsoletevaluesN1(t−τD)andN2(t−τD)andaddtheirrequeststothequeueaccording

2

tothisinformation.Wewritedelay-differentialequationsforNi:

dN1

=2Θ(N1(t−τD)−N2(t−τD))−1,

(1)

dt

whereΘstandsfortheHeavisidestepfunction.ThiscanbesimplifiedevenmorebyintroducingA(t)=N1(t)−N2(t),thedifferenceinqueuelengths:

dA

4τD

wheretri(x)isthetrianglefunction

󰀃

4x−1

tri(x)=

−4(x−1/2)+1

󰀂+φ,

(3)

forfor0≤x<1/2,1/2≤x<1,

periodicin1,

(4)

andφisaphasedeterminedbyinitialconditions.

Eq.(3)showsthatthesolutionisoscillatory.Thefrequencyofoscillationisonlydeterminedbythedelay,andtheamplitudebytheratioofdelaytimetoprocessingtime–thetotalnumberofclientsdoesnotplayarole.Clientstypicallyspendmuchoftheirtimewiththeirrequestinthequeue,andaddingmoreclientsonlymakesbothqueueslonger.Also,ifthedelaygoestozero,sodoestheamplitudeofoscillations:theminoritygameistrivialifagentscaninstantaneouslyandindividuallyrespondtothecurrentstate.Fig.1showsthatcomputersimulationsareingoodagreementwithEq.(3)andinparticularthatthetreatmentofNiascontinuousvariablesworkswellevenforsmallamplitudes.

Introducinganon-vanishingtraveltimeτThasthesameeffectonA(t)asincreasingthedelaytime:itleadstothedelay-differentialequation

dA

dtdN2

=2[(1−p)Θ(−A(t−τD))+pΘ(A(t−τD))]−1;

dt

=−2(1−2p)sign(A(t−τD)).(7)

3

10A0-10100150Nslope 20N/2τLt200250slope -2AτDT-NtFIG.1:Unmodifieddynamicsofthesystem.Top:ComparisonbetweensimulationswithN=100andτT=0toEq.(3).ThedelayisτD=5,yieldingaperiodof20andanamplitudeof10.Bottom:AnexampleofA(t)intheregimewhereserversgoidleperiodically.

ThisequationhastheformofEq.(2)withaprefactorof1−2p,andhasasteady-statesolution

󰀁

t

A(t)=2τD(1−2p)tri

3.Forsmallp,theamplitudeisreducedlinearly;forlargerp,fluctuationsincrease,

dominatingthedampenedoscillations.Whentheamplitudeoftheundisturbedsystemissmall,fluctuationshavealargeimpact.Astheamplitudeofoscillationsgetslarger,theimpactoffluctuationsbecomessmaller,andthevalueofpwherefluctuationsdominatemovescloserto1/2.

Undertheinfluenceofrandomness,Aperformsabiasedrandomwalk:letusassumethatserverR2iscurrentlypreferred.Ineachunitoftime,A/4increasesby1withprobabilityp2(thetwoclientsprocessedbothgotoR1),staysconstantwithprobabilityp(1−p),anddecreasesby1withprobability(1−p)2(bothclientsmovefromR1toR2).Toreproducequantitativelytheeffectsoffluctuations,onecannumericallyaverageA2oversucharandomwalkthattakesplaceintwophases:thefirstphaselastsuntilA=0isreached;thesecondtakesanotherτDstepsuntilthedirectionofthebiasisreversed.TheprobabilitydistributionofAatthebeginningofthehalf-periodhastobe

4

chosenself-consistentlysuchthatitisamirror-imageoftheprobabilitydistributionattheend;theproperchoiceforA/4isaGaussianrestrictedtopositivevalueswithmean(1−2p)τDandvariance2p(1−p)τD.ThenumericalresultsareshowninFig.2;theyagreewellwithvaluesfromthesimulation.Notethatintheabovetreatment,weneglectedcomplicationslikemultiplecrossingsoftheA=0line.

Adaptability–Anotheraspectthatdetermineswhatdegreeofdisinformationshouldbechosenisadaptabilityofthesystem.Thereasontohavepublicinformationabouttheserversinthefirstplaceistobeabletocompensateforchangesintheenvironment:e.g.,oneservermightchangeitsdatathroughputduetohardwareproblems,orsomeclientsmight,forwhateverreason,developastrongpreferenceforoneoftheservers.Iftheotheragentscanrespondtothesechanges,globalcoordinationremainsgood;iftheirabilitytounderstandthesituationistoodistortedbydisinformation,globalefficiencysuffers.

Letusassumethatafractionbofagentsdecidetosendtheirrequeststoserver1,regardlessofthelengthofqueues.Underglobaldisinformation,outofthefraction1−bthatisleft,anotherfractiondwillsendtheirrequeststothewrongserver,andyetanotherfractiondisneededtocompensateforthat.Soafraction(1−b)(1−2d)islefttocompensatefortheactionofthebiasedgroup,andthemaximumlevelofdisinformationthatstillleadstoreasonablecoordinationisp=(1−2b)/(2−2b)–largerlevelsleadtolargedifferencesinqueuelength,andfinallytolossofdatathroughputbyemptyingaqueue.Thatestimateisconfirmedbysimulations(seeFig.2).Similarargumentsholdifthepreferencesvaryslowlycomparedtooscillationtimes.Ontheotherhand,ifthepreferencesofthebiasedagentsoscillateintimewithaperiodsmallerthanthedelaytime,theyaverageoutandhavelittleeffectonthedynamics.Asimilarargumentalsoappliesiftheservershavedifferentcapacity.LetussayR1hasaprocessingtimeτP1,whereasR2hasτP2>τP1.Afractionf=τP2/(τP1+τP2)>1/2ofclientsshouldchooseR1–ifpissmallerthan1−f,thequeueofR1willnotbecomeempty;otherwiseitwill.

Individualrejection–Evenifserverscannotinfluencethepublicinformationonqueuestatus,theycaninfluencethebehaviorofclientsdirectly:theyclaimtheyarenotcapableofprocessingarequest,andrejectit–letussay,withaconstantprobabilityr.Comparedtoglobaldisinformation,anewpossibilityarisesthatarequestbouncesbackandforthseveraltimesbetweentheservers,butthataddsnothingnewinprinciple:thefractionofrequeststhatendupattheserverthattheytriedatfirstis(1−r)+r2(1−r)+r4(1−r)+...=1/(r+1),whereasafractionr/(r+1)willbeprocessedattheotherserver.Thisisequivalenttosettingp=r/(1+r)inthe“globaldisinformation”scheme,andgivesequivalentresults.Choosingrcloseenoughto1reducestheamplitudeofoscillationsdramatically;however,eachmessageisrejectedalargenumberoftimesonaverage,generatinglargeamountsofextratraffic.

Load-dependentrejection–Ratherthansettingaconstantrejectionrate,itseemsintuitivetouseaschemeofload-dependentrejection(LDR),inwhichridependsonthecurrentlengthofthequeue.ThisisbeingconsideredforpreventingtheimpactofsingleserveroverloadinRef.[10].Forexample,letusconsiderthecasewhereri=cNiifcNi<1,and1otherwise,withsomeappropriatelychosenconstantc.Theanalysisfromthe“indiviualrejection”sectioncanberepeatedwiththeadditionalslightcomplicationoftwodifferentrejectionratesr1andr2.Afraction(1−r1)/(1−r1r2)ofagentswhoinitiallytryserver1endsupbeingacceptedbyit,whereasafractionr1(1−r2)/(1−r1r2)finallywindsupatserver2,andviceversaforclientswhoattempted2first.Combiningtheresultingdelay-differentialequationsforN1andN2intooneforA,oneobtains

dA

1−r1r2

(Θ(−A(t−τD))(1−2r1+r1r2)−Θ(A(t−τD))(1−2r2+r1r2)).

(9)

Wecannowsubstitutetheload-dependentrates.Wewritethemasfollows:r1=r¯+c′A,r2=r¯−c′A,withr¯=(r1+r2)/2andc′=c/2.

ForsmallamplitudesArelativetothetotalnumberofplayersN,thedeviationfromr¯doesnotplayasignificantrole,anditisr¯thatdeterminesbehavior,yieldingthesameresultsasaconstantrejectionrate.Forlargerrelativeamplitudes,theoscillationsarenolongerpuretrianglewaves,buthaveamorecurvedtip.Figure3showsArmsforload-dependentrejection,comparedtoconstant-raterejectionwithr=r¯.ThesenonlineareffectsmakeLDRmoreefficientatsuppressingoscillations,atleastif2τDisnotsmallcomparedtoN.Theyalsoprovideforarestoringforcethatsuppressesfluctuationseffectively.ItfollowsthatLDRisbetteratimprovingdatathroughputinparameterregimeswhereserversemptyout,whichisconfirmedbysimulations.

WenoteoneproblemwithLDR:ifc>2/N,bothservershavethemaximalnumber1/cDiscussion–Wehaveintroducedamodelforthecoordinationofclients’requestsforservicefromtwoequivalentservers,foundthedependenciesoftheresultingoscillationsontheparametersofthemodel,anddeterminedwhenandhowtheseoscillationsdecreasedatathroughput.

Wehavethensuggestedanumberofserver-sidewaystodampentheoscillations,whichinvolvepurposelyspreadingwronginformationaboutthestateoftheservers.Alloftheseschemescanachieveanimprovement,showingthatthepresenceoffaultyorincompleteinformationcanbebeneficialforcoordination.Themarginsforimprovementare

5

1.21Arms / (2 τD)0.80.60.40.20simulation: τD=5τD=10τD=15theory: τD=5τD=10τD=15no fluctuations00.1disinformation probability p0.20.30.40.51.21Arms / (2 τD)0.80.60.40.20Simulation: τD=10, b=0τD=10, b=0.1τD=10, b=0.2τD=10, b=0.3theory, b=0, no fluctuations00.1disinformation probability p0.20.30.40.5FIG.2:Top:Globaldisinformation–they-axisshowstherootmeansquaredifferenceinqueuelengths,rescaledbytheamplitudeoftheundisturbedsystem.ThetheoryfornegligiblefluctuationsisgivenbyEq.(8);agreementwithsimulationsbecomesbetterasabsoluteamplitudesincrease.Theimpactoffluctuationscanbemodeledusingadiscreterandomwalk.Bottom:Adaptability–ifapercentagebofclientsalwayschoosesthesameserver,disinformationdisruptscoordinationforvaluesp<∼(1−2b)/(2−2b),indicatedbyverticallinesforseveralvaluesofb.

6

0.80.6Arms/(2τD)LDR, τD=15, N=80N=140N=200N=400constant rejection, τD=15, N=2000.40.2000.20.4c N/2, r0.60.81FIG.3:Load-dependentrejection:comparedtorejectionwithaconstantrate,LDRismoreefficientatsuppressingbothoscillationsandfluctuations.Theformerbecomesmorepronouncedif2τDisnotsmallcomparedtoN.

higherintheregimeoflargenumbers,whentheamplitudeisontheorderofmanytensorhundredsratherthanafewindividuals–inthelattercase,increasedfluctuationscanoutweighthebenefitsofreducedoscillation.Whilesomedisinformationgenerallyimprovesperformance,monitoringoftheaverageloadandamplitudeisnecessarytochoosetheoptimaldegreeofdisinformation.

Thebasicingredientsoftheserver-clientscenario(delayedpublicinformationandminority-game-likestructure)appearinmanycircumstances.Onecanthinkoftrafficguidancesystemsthatrecommendoneoftwoalternativeroutes,stockbuyingrecommendationsinmagazines,careerrecommendationsbyemploymentcenters,andothers.Exploringtheimpactofdisinformationontheseproblemsiscertainlyworthwhile.

[1][2][3][4][5][6][7][8][9][10]

A.Smith,AnInquiryintotheNatureandCausesoftheWealthofNations(MethuenandCo.,Ltd,London,1904).D.ChalletandY.-C.Zhang,PhysicaA246,407(1997).D.ChalletandM.Marsili,Phys.Rev.E60,R6271(1999).

Minoritygamehomepage(withextensivebibliography),http://www.unifr.ch/econophysics/minority.E.NakarandS.Hod(2002),cond-mat/0206056.

G.Reents,R.Metzler,andW.Kinzel,PhysicaA299,253(2001).M.MarsiliandD.Challet(2000),cond-mat/0004376.

R.Savit,R.Manuca,andR.Riolo,Phys.Rev.Lett.82,2203(1999).

M.KleinandY.Bar-Yam,HandlingResourceUseOscillationinOpenMulti-AgentSystems.aAMASWorkshop(2003).B.Braden,D.Clark,etal.,RecommendationsonQueueManagementandCongestionAvoidanceintheInternet.NetworkWorkingGroup(1998).