On Consulting a Set

OnConsultingaSetofExpertsandSearchingbyIgalGalperinSubmittedtotheDepartmentofElectricalEngineeringandComputerScienceinpartialfulllmentoftherequirementsforthedegreeofDoctorofPhilosophyattheMASSACHUSETTSINSTITUTEOFTECHNOLOGYSeptember1996cMassachusettsInstituteofTechnology1996.Allrightsreserved.Author::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::DepartmentofElectricalEngineeringandComputerScienceSeptember5,1996Certiedby:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::RonaldL.RivestE.S.WebsterProfessorofComputerScienceThesisSupervisorAcceptedby:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::FredericR.MorgenthalerChairman,DepartmentalCommitteeonGraduateStudentsOnConsultingaSetofExpertsandSearchingbyIgalGalperinSubmittedtotheDepartmentofElectricalEngineeringandComputerScienceonSeptember5,1996,inpartialfulllmentoftherequirementsforthedegreeofDoctorofPhilosophyAbstractTwochaptersofthisthesisanalyzeexpertconsultingproblemsviagametheoreticmodels;therstpointsoutacloseconnectionbetweentheproblemofconsultingasetofexpertsandtheproblemofsearching.ThelastchapterpresentsasolutiontothedictionaryproblemofsupportingSearchandupdate(InsertandDelete)operationsonasetofkeyvalues.Therstchaptershowsthattheproblemofconsultingexpertson-linecanbemodeledbyachipgamesimilarandinsomecasesidenticaltothePaul-Carolegamesusedtomodelafaultysearchprocess.Itpresentsthebestknownworst-casealgorithmsforconsultingnitelymanyexperts,andthebestpossiblealgorithmsforconsultinginnitelymanyex-perts(modelselection)undersomeassumptions.Itincludesnewresultsaboutfaultysearchprocessesaswellasgeneralizationsandnewproofsofsomeknownresults.Thesecondchapterusespropertiesofcoalitionalgamestoanalyzetheperformanceofthegreedyheuristicfortheproblemofhiringexpertsfromapoolofcandidatesusingstochasticdata.TheresultsareinstrumentalinsuggestinganalternativetoaknownalgorithmforlearningLipschitzfunctionsbyamemory-basedlearningsystemsviaananalysisofthegreedyapproximatesolutionofthes-medianproblem.ThethirdandlastchapterisdedicatedtotheScapegoattreesdatastructure:asolutiontothedictionaryproblemthatusesbinarytreeswithnoauxiliarybalancingdatastoredatthetreenodestoachievelogarithmicworst-casesearchtime,andlogarithmicamortizedupdatetime.Allchaptersexplorealternativestothenowstandardworst-caseanalysisofalgorithms.Therstchapterintroducesandadvocatesthenotionsofopportunismandalmostoppor-tunismofon-linealgorithms.Thesecondchaptercontraststhepessimismofworst-caseanalysiswiththeoptimismofthegreedyheuristic,andpointsoutsomebenetsofexplor-ingthelatter.Thelastchapterevaluatesanoveldatastructurebycomputingitsamortizedperformance.ThesisSupervisor:RonaldL.RivestTitle:E.S.WebsterProfessorofComputerScienceAcknowledgmentsIwouldliketothankthethesissupervisorRonRivest.Heproposedthetopicsthisthesisaddresses,andposedquestionsthatadvancedmyresearch.Thedetailsowemuchtohiscarefulreadingandpatientcomments.ThethesiscommitteemembersJohnTsitsiklisandDavidKargermadehelpfulsugges-tions.JavedAslam,ShaiBen-David,MichaelBen-Or,ScottDecatur,PeterElias,CharlesLeiserson,NattiLinial,GaborLugosi,RafailOstrovsky,JereyUhlmann,andanonymousconferencecommitteememberslistened/readandprovidedadvice.Ialsothankthesup-portstuofthetheorygroup,inparticularBeHubbard,aswellasmanyofitsmembersthroughoutmystayhere.Ithankthemanypeoplewhoshowedmegenerosity,tolerance,sympathy,encourage-mentandsupport.Ibelievethatwithouttheextraordinaryeortsofmyfamily{parentsandsister{thecompletionofthisworkwouldnotbepossible.Ithankallthosewhohelpedyetwerenotthankedsofar.Contents0Introduction80.1Chapter1:ConsultingaSetofExpertsOn-LineandFaultySearching:::90.2Chapter2:GreedyExpertHiringandanApplication::::::::::::110.3Chapter3:SearchingaDynamicallyChangingSet::::::::::::::111OpportunisticAlgorithmsforExpertAdvisees131.1Introduction:::::::::::::::::::::::::::::::::::141.2Denitions,Notations,Conventions::::::::::::::::::::::181.3TheMathoftheGame:::::::::::::::::::::::::::::201.3.1MultistageTwo-PersonGames:::::::::::::::::::::211.3.2ExpertConsultingGames-CommonRules,Denitions:::::::241.3.3ExpertConsultingGames-Variations::::::::::::::::261.4AdversarialLogic::::::::::::::::::::::::::::::::281.4.1GenerallyApplicableObservations::::::::::::::::::281.4.2Non-AtomicGames:::::::::::::::::::::::::::331.4.3GameswithFinitelyManyExperts::::::::::::::::::361.5Games’ValuesandManagerialStrategies:::::::::::::::::::411.5.1TheValuesofGames::::::::::::::::::::::::::411.5.2TheManager’sStrategy::::::::::::::::::::::::421.6EciencyIssues:::::::::::::::::::::::::::::::::441.6.1FromStrategiestoAlgorithms:::::::::::::::::::::4441.6.2AbsolutePerformance:::::::::::::::::::::::::451.7ExtensionsandImplications::::::::::::::::::::::::::461.7.1ConsultingFinitelyManyExperts:ComparingPMtoBWandWM461.7.2ConsultingExpertsonMultipleChoiceQuestions::::::::::471.7.3\RealManagers::::::::::::::::::::::::::::481.7.4SearchinginthePresenceofErrors::::::::::::::::::481.7.5TheRelativeGame:::::::::::::::::::::::::::511.8Conclusion:::::::::::::::::