ContentslistsavailableatSciVerseScienceDirect
Applied Soft Computing
jo u r n al h om epa g e :w w w . e l s e v i e r . c o m / lo c a t e / a s o c
Multi-objective optimization and decision making approaches to cricket team selection
Faez Ahmed
a, Kalyanmoy Deb
a,b,c, Abhilash Jindal
a,∗aKanpurGeneticAlgorithmsLaboratory(KanGAL),IndianInstituteofTechnologyKanpur,Kanpur208016,India
bKoenigEndowedChairProfessor,DepartmentofElectricalandComputerEngineering,MichiganStateUniversity,EastLansing,MI48824,USA
cAaltoUniversitySchoolofEconomics,Helsinki,Finland
a r t i c l e i n f o
Articlehistory:
Received9September2011
Receivedinrevisedform18April2012 Accepted19July2012
Availableonline3September2012
Keywords:
Cricketteamselection
Evolutionarymulti-objectiveoptimization NSGA-II
Multi-criteriadecisionmaking Trade-offsolutions
a b s t r a c t
Selectionofplayersforasportsteamwithinafinitebudgetisacomplextaskwhichcanbeviewedas aconstrainedmulti-objectiveoptimizationandamultiplecriteriadecisionmakingproblem.Thetaskis speciallychallengingforthegameofcricketwhereateamrequiresplayerswhoareefficientinmultiple roles.Intheformationofagoodandsuccessfulcricketteam,battingstrengthandbowlingstrengthof ateamaremajorfactorsaffectingitsperformanceandanoptimumtrade-offneedstobereached.We proposeanovelgenerepresentationschemeandamulti-objectiveapproachusingtheNSGA-IIalgorithm tooptimizetheoverallbattingandbowlingstrengthofateamwith11playersasvariables.Fielding performanceandanumberofothercricketingcriteriaarealsousedintheoptimizationanddecision- makingprocess.Usingtheinformationfromthetrade-offfrontobtained,amulti-criteriadecisionmaking approachisthenproposedforthefinalselectionofteam.Casestudiesusingasetofplayersauctioned inIndianPremierLeague(IPL)4theditionareillustratedandplayers’currentstatisticaldataisused todefineperformanceindicators.Theproposedcomputationaltechniquesarereadytobeextended accordingtoindividualisticpreferencesofdifferentfranchisesandleaguemanagersinordertoforma preferredteamwithinthebudgetconstraints.Itisalsoshownhowsuchananalysiscanhelpindynamic auctionenvironments,likeselectingateamunderplayer-by-playerauction.Themethodologyisgeneric andcanbeeasilyextendedtoothersportslikeAmericanfootball,baseballandotherleaguegames.
PublishedbyElsevierB.V.
1. Introduction
Formationof a good teamfor anysport isvital toitseven- tualsuccess.Teamselection inmostsports isasubjectiveissue involving commonly accepted notions to form a good team.
Applicationofobjectivemethodsforteamselectionisarelatively newphenomenonand theeffectseemsmore pronouncedafter theinvolvement of variouscompetitive leaguesinvolvinglarge budgetstobuy players.Inthisstudy,wehavechosenthegame ofcricketforwhichdifferentperformancemeasuresforchoosing playershavebeensuggested[10,3,13,14].Cricketisabat-and-ball gameplayedbetweentwoteamsof11 playerswhereoneteam bats,tryingtoscoreasmanyrunsaspossible,whiletheotherteam bowlsandfields,tryingtodismissthebatsmenoneatatimeand thuslimitingtherunsscoredbythebattingteam[1].Battingand bowlingperformanceofateamarethemajorcriteriaaffectingits successalongwithmany otherobjective and subjectivefactors
∗ Correspondingauthor.
E-mailaddresses:[email protected](F.Ahmed),
[email protected],[email protected](K.Deb),[email protected](A.Jindal).
likefielding performance, captaincy (the ability of a captainto choose the right bowler and field placement according to the situation),homeadvantageetc.[11,12].Optimizationstudieshave beendoneinmany sportsin thepast[18,9] and alsohasbeen doneinvariousissuesinthegameofcricket[17].Justasinmost leaguecompetitions,apoolofplayersisavailablealongwiththeir performance statistics. Each playeris paid a certain amountof moneybytheteamownersforplayingfortheirteam,whichwe refertoasplayer’scost.Leagueorganizersimposeanupperlimit onbudgetforeachfranchise/clubtoavoidgivingundueadvantage torichfranchises.Playercostiseitherfixedbyorganizers,decided throughauctionordeterminedbysomecontract.
Twenty20(T20)isthelatestinnovationinthegameandiseven shorterversionthanOneDayInternationalcricket.Thetotaldura- tionoftheT20gameisabout3h,andeachteamgetstoplayamax- imumof20overs.WehaveconsideredTwenty20cricketgameand theIndianPremierLeague(IPL)asatestcaseforouranalysis.IPLis aprofessionalleagueforTwenty20cricketcompetitioninIndiaand isgainingalotofpopularity[23,16].Asofnow,onlyafewrecent studieshaveexploredteamformationinthisformatsincethecon- ceptofIPLandothersuchcompetitionsarerelativelynew.Lemmer [13]analyzestheperformanceofplayersforthefirstT20Worldcup 1568-4946/$–seefrontmatter.PublishedbyElsevierB.V.
http://dx.doi.org/10.1016/j.asoc.2012.07.031
series.Lourens[14]identifiesthreemaincategoriesofthegame (batting,bowling,and fielding)and devisesa numberofperfor- mancecriteriaforevaluatingplayersforeachcategoryofthegame.
Thereafter,alinearprogrammingmodelisconstructedandsolved tobuildateamof15players(11plusfourreserveplayers)forthe SouthAfricandomesticPro20cricketteambymaximizingasingle objectivecalculatedbyaddingtheperformancevalueofeachplayer intheteam.Anotherstudy[24]usesmoresophisticatedstatistical performancemeasuresandalsoemploysasingle-objectivelinear programmingapproachtoconstructafantasyleagueteam.These arenicestudiesinwhichsomeearliereffortswerealsodiscussed andcompared.However,oneaspectclearlymentioned bythese authorsisthatallthreecategoriesofthegameinvolvemultiple performancemeasuresandoftentheyareinconflicttoeachother.
Forexample,abatsmanmayhaveanexcellentrecordintermsof
‘battingaverage’(averagerunsscoredbytheplayerinpastgames), butmayhaveapoor‘strikerate’(rateatwhichtheplayerscores runs),trading-offtheperformanceoftheplayerinthebattingcate- goryofthegame.Theyareinconflict,sinceaslowbutsteadyplayer willhaveabetterbattingaverage,butapoorstrikerate.Ideally, thegamerequiresabatsmanwithbothqualities,butanimpor- tantquestionthenremains:‘Whatperformancecriterionshould oneusetoselectabatsmanintheteam?’Suchquestionsbecome evendifficulttoanswerinchoosingabatsmanoverabowlerora batsmanoverafielder.Althoughthesepaststudieseitherchoose onecriterionforeach categoryoruseaprioripreferenceofone criterionoverother,thestudiesmakeoneaspectamplyclear:a decision-makingtaskinchoosingplayersistrulymulti-objective innatureandaprioriconsiderationofperformancemeasuresmay resultinateamthatmaynotbeagreeabletoall.In[20],35all- rounders(whocanbat,bowlandfieldwell)areclassifiedbased on‘strike rate’(abattingaspect)and‘economyrate’(abowling aspect)intofournon-overlappingclasses–performer,battingall- rounder,bowlingall-rounder,andunder-performer.Althoughno optimizationstudyisperformed,aBayesianapproachisusedfor theclassificationpurpose.Thekeyaspectofthisstudyistheuse oftwoconflictingcriteriaforclassifyingall-rounderplayersand theuseofrecentstatisticaltechniquesinrankingplayers.Above- mentionedstudiesmakeoneaspectclear:playerscanbeevaluated fromtheirpastperformancedatausingwell-establishedstatistical andmachinelearningproceduresforthemtobeincludedinafuture teamandmultiplecriteriamustbeconsideredtoanalyzethedata forthepurposeofconstructingateamforoptimalperformance.
Interestingly,suchadata-miningprocedurecanbegenerically applicabletodifferentgamesforwhichplayers’pastperformance dataisavailable.Forexample,inthesoccerleaguematches,players canbechosenfortheirpositionsasgoal-keeper,fullbacks,midfield- ers,andforwardsdependingontheirpastrecordedperformances indifferentpositions.Ateamcanbeconstructedfromsuchinfor- mationfortwoconflictingteamperformances–goalsscoredversus goalsconceded.
InIndianPremierLeague(IPL)ofTwenty20cricket,thefran- chisehavethetaskofbuildingawinningteamwithinthebudget cap,restrictedbytheIPLboard.Individualplayersareboughtby thefranchisesduringapublicauctionoftheplayers.Sincethetotal numberofplayersinthemarketpoolislarge,thechallengeoffind- ingahigh-performingteambecomesanincreasinglycomplicated procedure.Datausedforthiswork(downloadedfromthepublic domainsources)hasapoolof129playersfromIPL4theditionand istabulatedelsewhere[2].TheplayercostsaretheIPL4thedition auctionpricesforrespectiveplayers.Wehaveusedotherperfor- mancestatisticsofeachplayerfromthepublicdomainsourceson theInternationalTwenty20versionofthegame.
Withsomanyplayersavailableforchoosingateam,theneed foraneffectiveoptimizationtechniquecanbejustifiedbymaking aroughcalculationoftheapparentsizeofthedecisionspace.From
thegivendataofonly129playersfromIPL4theditionauction, containing10captainsand15wicket-keepers,thetotalnumberof possibleteamsundertheconstraintsofatleastonewicket-keeper andonecaptainareincludedineach teamcanbecalculatedas follows:
totalnumberofteams=
10 115 1
127 9
. (1)
Consideringthelargenumberofdifferentpossibleteamcombina- tions(totheorderof1015),findingoptimalteamsundertheadded constraintofbudgetisnotatrivialtask.Currentlymostoftheteam selectionsaredoneusingdifferentheuristics,pastexperiences,or atmostusingsomecrudemethodologies.Forexample,onestrat- egyistochoosetwoorthreehighperformancebatsmenorbowlers andtheremainingteamslotsarefilledaccordingtobudgetcon- straints.But,thisapproachmaynotalwaysgiveanoptimalora near-optimalsolution,sincematchesarewonbyateameffortand notbyhavingoneortwostarplayersintheteam.Hence,ouraim inthispaperistoinvestigatetheformationofanoverallteamthat isoptimalornear-optimalfromthepointofmultiplecriteria.Since battingandbowlingperformancesofateamaregenerallyconsid- eredtobeconflictingtoeachother,weusethesetwocriteriain ouroptimizationstudy,while allotherobjectiveandsubjective criteria,suchasfieldingperformance,captaincy,wicket-keeper’s performance,brandvalueofateamandothers,areusedduringthe subsequentdecisionmakingphase.Itisdifficulttoarguewhether abatting-dominantteamisbetterorabowling-dominantteamis better.Thisisanunavoidabledilemmathattheteamselectorsface whileformingateam.Duetoourconsiderationofbothbowling andbattingperformancesinformingateam,weattempttofinda numberofhigh-performingteamshavingagoodtrade-offbetween thesetwomainobjectives.Thereafter,weargueanddemonstrate thataconsiderationofanumberofothercriteriaappliedonthe obtainedhigh-performingteamsmakesitconvenientfortheteam managerstoidentifyapreferredteamoftheirchoice.
Inthispaper,wehaveexploredtheproblemofbuildingahigh- performingteamoutofasetofplayersgiventheirpastperformance statistics andsuggested,for thefirsttime, acomputationaland decision-making methodology fromthe perspectiveof a multi- objectiveconsideration.Anovelrepresentationschemeofateamof 11playersissuggestedtohandledifferentconstraintsassociated withtheteamselectionproblem.Theelitistevolutionarymulti- objectiveoptimizationalgorithm(NSGA-II[6])isextendedtofind multiplehigh-performingteams.Anumberofrealisticdecision- makingconsiderationsarethenusedtopickasuitableteam.
Intheremainderofthis paper,wedescribetheoptimization problemcorrespondingtothecricketteamselectionproblemin Section2.Anovelschemetorepresenta11-playerteamthatauto- maticallysatisfiesanumberofconstraintsisdescribednext.The computing procedures of differentobjective functionsare then discussed. Section3 presents the results obtained through our multi-objectiveoptimizationstudy.Ourobtainedhigh-performing teamsarecomparedagainsttheIPL4theditionwinningteam.The (theoretical)superiorityofourteamsisclearfromthefigure.The obtainedsolutionsareanalyzedfortheirsensitivitytotheoverall allowablebudgetandinterestingconclusionsaremade.Section4 thensuggestsanumberofdecisionmakingtechniquestochoosea singlepreferredteamfromthesetoftrade-offteams.Thisincludes thestandardknee-pointapproach,adynamicapproachsimulat- ingtherealauctionprocedure,andacoupleofotherinteresting criteria.Amulti-objectiveoptimizationstudytofindasetofteams providingatrade-offbetweenbattingandbowlingperformances andthenamulti-criteriondecisionmakinganalysisprocedureto finallypickapreferredteamremainasahallmarkfeatureofthis study. Theprocedure is ready tobe appliedin practice witha
minimalfine-tuningneededtosuitvariousotherrulesoftheIPL teamselectionprocess.ConclusionsofthisstudyaremadeinSec- tion5.
2. Proposedmethodology
Inthegameofcricket,playerstatisticshavemultipleparame- ters,likenumberofmatchesplayed,totalrunsmade,battingstrike rate,numberofwicketstakenbyabowler,numberofoversbowled, etc.Importantly and interestingly,the values of theseparame- tersformostactiveplayersareavailable.However,itisimportant tofirstidentifythestatisticalparametersthatreliablyindicatea player’sperformance.Theoverallaimofafranchiseistobuilda teamof11playerswithoptimumbowling,batting,aswellasfield- ingperformancewithinbudgetand otherruleconstraints.Rule basedconstraintslikepresenceofatleastoneplayercapableof wicket-keepingandonecaptainhavealsotobetakenintoaccount.
Consideringthelargeamountofstatisticaldatadenotingvari- ouscricketingattributesthatisavailableforeachplayer,wefirst tendtoreducethedimensionofdata.Oneapproachcanbetouse standardbatting,bowling,andfieldingratingofcricketersobtained afterexhaustivestatisticalanalysis.Suchratings,liketheICCworld cricketrating,takesintoaccountmultiplefactorsofperformance.
But,sucharatingsystemiscurrentlyavailableonlyforone-dayand testmatchversionsofthisgame.SinceTwenty20versionofthe gameisverydifferentandtheperformanceofaplayerinonever- sionofthegamedoesnotextrapolatetoanotherversionformost players,wecannotapplytheavailabledataforone-daymatches andtest matches totheTwenty20format, whichwe areinter- estedinthisstudy.Forsimplicity,wehaveusedbattingaverage andbowlingaverageofa playerin thepastfoureditionsofthe internationalTwenty20cricketasameasureoftheirperformance inbattingandbowling.Forbrevity,thedataistakenfromthepublic domainsources,compiledandstoredinawebsite[2].
Eachplayerisassignedatagindicatingtheplayer’suniqueiden- tity.Usingtheavailabledata,wethenformulatetheteamselection problemasamulti-objectiveoptimizationproblem,asfollows:
arg max
t={c,w,p1,p2,...,p9}
⎧ ⎪
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎪ ⎨
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎪ ⎪
⎩
f1(t)=
i=c,w,p1,...,p9
battingperformance(i),
f2(t)=
i=c,p1,...,p9
bowlingperformance(i),
f3(t)=
i=c,w,p1,...,p9
fieldingperformance(i).
(2) Notethatthewicket-keeper(w)doesnotaffectthebowlingperfor- manceofateam.Theteamissubjecttothefollowingconstraints:
g1(t)≡c∈captainlist, (3)
g2(t)≡w∈wicket-keeperlist, (4)
g3(t)≡notwoplayersareidenticalinateam, (5) g4(t)≡notmorethanfourforeignplayersinateam, (6) g5(t)≡
i={c,w,p1,...,p9}
cost(i)≤TotalBudget. (7)
Here,trepresentsateamcomprisingofc(thetagofthecaptainof theteamchosenfromacaptainlist(CL)havingof10names,pre- sentedin[2]),w(thetagofthewicket-keeperoftheteamfrom awicket-keeperlist(WL)having15names,andp1,...,p9 (tags ofnineotherplayersoftheteamchosenfrom129totalnames arrangedina rankedlist(RL),excludingthechosencaptainand wicket-keeper).Tohaveadistinctsetof11players,notwoplayers
inateamcanbeidentical.Playersarealsotaggedasaforeigner(a non-residentIndianplayer)ornot.AsanIPLrule,ateamshouldnot havemorethanfourforeignplayers.Thefinalconstraintindicates thatoverallcostoftheteammustbewithinthespecifiedupper limit.Wenowdescribethecomputationalprocedureforeachof threeobjectivefunctions.
2.1. Battingperformance
Aplayer’sbattingaverageisthetotalnumberofrunshehas scoreddividedbythenumberoftimeshehasbeenout.Sincethe numberofrunsaplayerscoresandhowoftenhegetsoutarepri- marilymeasuresofhisownplayingabilityandlargelyindependent ofabilitiesofhisteammates,battingaverageisagoodmetricfor anindividualplayer’sskillasabatsman.Theobjectivefunctionin ouranalysishasbeentakenasthesummationofbattingaverages ofallplayers.Theproblemwiththisapproachisthatsomenew players,evenbowlers,mayhaveabattingaveragecomparableto fewofthebestestablishedbatsmenduetogoodperformancein fewmatchesplayed.Hence,toavoidthisscenario,theconceptof primaryresponsibilityofaplayerisused.Aplayerisidentifiedas adesignatedbatsmanonlyifhehasscoredatleast300runsin aninternationalTwenty20format.Incalculationofateam’snet battingperformance,thebattingaverageofplayersidentifiedas designatedbatsmenisonlyaddedtofindnetbattingaverage.Thus, theoverallbattingaverageofteammustbemaximized,buthere, weminimizethenegativeofthenetbattingaveragefortheconve- nienceofshowingtrade-offsolutions.
2.2. Bowlingperformance
Abowler’sbowlingaverageisdefinedasthetotalnumberof runsconceded bythebowlerdividedbythenumberofwickets takenbythebowler.So,lowerthebowlingaverage,thebetteristhe bowler’sperformance.Againtoavoidincludingmisleadinghighor lowaveragesresultingfromacareerspanningonlyafewmatches, wequalifyaplayerasbowleronlyifhehastakenatleast20wick- etsinTwenty20format.Onlythebowlingaverageofthesequalified bowlersissummedtogetanetbowlingaverageofateam.Total bowlingaverageofateamistakenasameasureofbowlingperfor- manceandisminimized.Unlikeinthebattingperformance,here, lowerthenetbowlingaverage,betterthebowlingperformance.
Usingsuchastrategyinoptimizationmayresultinateamhaving anexclusionofallbowlers,sothatnetbowlingaverageofteamis zero.Hence,insteadofassigningazerovaluetoanon-bowler,we assignanartificialpenaltyof100asthebowlingaverageforeach non-bowler.Thisvalue(100)ischoseninsuchawaysoastomake itworsethanadesignatedbowlerhavingtheworst(highest)bowl- ingaverage.Hence,ateam’sbowlingperformanceiscomputedby addingthetruebowlingaveragesofdesignatedbowlersand100 foreachnon-designatedbowler.
2.3. Fieldingperformance
Aplayer’sfieldingperformanceiscalculatedasfollows:
player’sfieldingperformance
= totalcatchestaken
totalnumberofinningsplayed. (8)
Team’snet fieldingperformance is summation of allindividual playersfieldingperformance.Otherstatisticssuchasrunssaved andrun-outsmadecanalsobeconsideredhere.Thenumberof stumpingsbyawicket-keeperistakenashiswicket-keeper’sper- formancemeasure.
2.4. Multi-objectiveformulationandNSGA-II
To solve the above problem, we employ the elitist non- dominatedsortinggeneticalgorithmorNSGA-II[6].Weprovide abriefdescriptionoftheNSGA-IIprocedurehere,butreaderscan refer totheoriginalstudy for moreinformation. TouseNSGA- IIforateamselectionproblem,oneneedstohaveameaningful representationscheme,thatwillbeprocessedfavorablytocreate feasibleteamsbyNSGA-II’srecombinationandmutationopera- tors.Forexample,theplayerrepresentedasacaptaininoneteam shouldbecomparedwiththecaptainofamatingteaminorderto createanoffspringteamthatwouldchooseoneofthetwocaptains fromthematingteamsoronefromthelistofcaptainsasaviable captain.Similarlyforthemutationoperation,aplayershouldbe changedtoanotherplayerwithinitsownclass–abatsmanreplaced with another batsman most often and a batsman is replaced toa bowler witha small probability.Thus, the representation- operatorcombinationisoneofthemostcriticalmatterasitdirectly affects theconvergence speed of a geneticalgorithm. The rep- resentationschemeexplainedbelowattainsthefollowingmajor tasks:
• Agenericschemewhichcanbedirectlyemployedinothersports wheredifferentrolesofindividualsarerequiredinateamand theyhavetobechosenfromasetofviableplayers.
• TheschemeensuresmeaningfulGAoperatorsactingonsimilar players.
• Teamsformedbygeneticoperationsarerepairedsoastoreduce thechanceofcreatinginfeasibleteams.
• Caterstopracticalities,suchasoneplayercanactinmultiple roles(suchaswicket-keeperandcaptainarethesameplayerin acricketgame,andgoal-keeperandcaptainarethesameplayer inasoccergame).
Asexplainedabove,thefirsttaskinapplyingaGAistochoosea representationschemethatissuitedtohandleconstraintsandalso tofacilitateaneasieruseofgeneticoperators.Torepresentateamin ourproposedNSGA-IIandtoalsotakecareoffirstthreeconstraints (Eqs.3to5),eachplayerisassignedatag,thedetailsofwhichare presentedin[2].Toassignatagforaplayer,first,wesortall129 playersaccordingtoplayercostandthenassignauniqueinteger numberindicatingtheplayer’srankintherange[1,129].Thesorted listiscalledrankedlistorRL.Next,fromthegiven129players,we identifythecaptainsandarrangetheminascendingorderoftheir priceinacaptainlist,orCL.Thereare10captainsinthelist,thus thelistcontainsintegersintherange[1,10].Similarly,thewicket- keepersareidentifiedandputinanascendingorderoftheirprice inthewicket-keeperlist,orWL.Thereare15wicket-keepersinthe list,therebymakingthelisttakingvaluesintherange[1,15].Note thataparticularvalueinCLmayrefertothesameplayercorre- spondingtoavalueinWL,andallvaluesinCLandWLcorrespond toplayersrepresentedinRL. Thereisa reasonfor this compli- cation of maintainingthree lists in our representation scheme, whichwillbeclearinthenextparagraph.Wenowdiscussthecon- structionprocedureofarandompopulationmemberintheinitial generation.
Everypopulationmemberisrepresentedwithtwovectors:(i) acode-vectorand(ii)avariable-vector.Wefirstdiscusstheproce- dureofcreatingacode-vector.Thefirstelementofthecode-vector iscreatedatrandomfromCL.Thus,thiselementisarandominte- gerintherange[1,10].Thecorrespondingname(say,‘c’)isthe captainoftheteam.Thesecondelementofthecode-vectoriscre- atedatrandomfromWLandisanintegerintherange[1,15].The selectedname(say‘w’)isthewicket-keeperoftheteam.There- after,theremainingnineelementsinthecode-vectorareselected atrandomfromRL,sothatthereisnorepetitionamongthesenine
elements.Thus,theyarenineuniqueintegersintherange[1,129].
Theseareothernineteammembers.If‘c’or‘w’isidenticaltoany oftheothernineteammembers,anotherteammemberischosen atrandomandtheprocessiscontinuedtilltheninemembersare differentfrom‘c’and‘w’.Thereafter,thetagsofninemembersare arrangedinascendingorderoftheirvalues.
Next,thevariable-vectorisconstructedfromthecode-vectorby copyingthetagnumberofeveryplayeronebyonestartingwith thetagofthecaptain,thenthetagofthewicket-keeper,followed bytagsofnineteammembers.Thus,theonlydifferencebetweena code-vectoranditscorrespondingvariable-vectorisinthefirsttwo elements.Inthecode-vector,theyareranksofcaptainandwicket- keeperinCLandWL,respectively,andinthevariable-vectorthey aretagsofcaptainandwicket-keeper.Weillustratetherepresen- tationprocedurebycreatingarandompopulationmemberinthe following:
Solution1:
Position: 1 2 3 4 5 6 7 8 9 10 11
Code-vector: 3 6 10 15 36 41 59 75 88 115 125
Variable-vector: 96 48 10 15 36 41 59 75 88 115 125 Intheaboveteamrepresentedbythecode-vector,thefirstele- ment(3,createdatrandomfrom[1,10])representsthethirdplayer (AdamGilchrist)inthecaptainlist(CL).Thesecondelement(6, createdatrandomfrom[1,15])representsthesixthplayer(Parthiv Patel)fromthewicket-keeperlist(WL)showninthesametable.
Theremainingnineelementsinthecode-vectorarechosenatran- domfromtherankedlist(RL)andpresentedinascendingorder ofthetagvalue.Thevariable-vectorisconstructedthenfromthe code-vector.Interestingly,thevariable-vectorisidenticaltothe code-vector except at the first two positions. The tag value of AdamGilchristandParthivPatelaretakenfromtheRLandput in the first and second positionin thevariable-vector, respec- tively.Thevariable-vectoristhenusedtocomputetheobjective andconstraintvalues.Thecode-vectorwillbeusedforthegenetic operations–recombinationandmutation,asdiscussedlater.
Thereisapossibilityofduplicationthatweresolveinourrepre- sentationscheme.Incertainpopulationmembers,thechosenfirst twoelementsofthecode-vectormayrefertothesameplayerwhich isawicket-keepercaptain.Inthiscase,thevariable-vectorwillindi- catethatitsfirsttwoelementsareidenticalandinrealitythereare only10playersrepresentedbythevectors.Toresolvethisissue, wesimplyreplacethesecondelementofthevariable-vectorwith arandomintegerfromRLandensurethatitisnotidenticaltothe 10playersalreadypresentinvariable-vector.Letusillustratethis scenariowithanexamplepopulationmember:
Solution2:
Position: 1 2 3 4 5 6 7 8 9 10 11
Code-vector: 2 10 5 16 54 68 77 95 101 113 122
Variable-vector: 86 86 5 16 54 68 77 95 101 113 122 Mod.var.-vector: 86 72 5 16 54 68 77 95 101 113 122 Here,thecaptainand wicket-keeperisthesameplayer(Kumar Sangakkara).Thus,althoughthecode-vectorhas11distinctele- ments, there are in fact 10 players. To resolve this problem, wechangethesecond elementinthevariable-vectorby aran- dom tag from RL that is not identical to any element already presentin theentirevariable-vector.Say,wechoosetheplayer withthetag72in thiscase.Therevisedvariable-vectoristhen formedandusedforcomputingobjectivefunctionandconstraint values.
Inanoccasion inwhichthechosencaptainis alsoa wicket- keeper(suchasAdamGilchrist,KumarSangakkaraorM.S.Dhoni) butthechosenwicket-keeperisadifferentperson(sayBrendon McCullumor ParthivPatel),we stillconsiderthesituationas if thewicket-keeperisidenticaltocaptain(thatis,thecaptainwill alsoperformthejobofwicket-keeping)andreplacethechosen wicket-keeperwitharandomplayer(butnon-identicaltoanyother alreadychosenplayers)fromRL.
Itisinterestingtonotethattheaboveprocedureguarantees thatthefirstthreeconstraintsarealwayssatisfiedinallpopula- tionmembers.Thevariable-vectorcannowbeusedtocomputethe objectivefunctionandremainingconstraints,asmentionedabove.
Insteadofusinganysophisticatedmethodstosatisfythefourth andfifthconstraints,here,wesimplycountthenumberofforeign playersintheteamandcalculatethetotalbudgetforhiringthe team.Thereafter,wecheckthesetwovaluesagainsttheirallowable values.Iftheyarewithinlimits,wedeclaretheteamasafeasible team,otherwise,wedeclareitasaninfeasibleteamandcompute constraintviolationasfollows:
CV(t)=min
0,numberofforeignplayers
4 −1
+min
0,
i={c,w,p1,...,p9}cost(i) TotalBudget −1
. (9)
TheconstraintviolationvalueofateamwillbeusedinNSGA-II’s selectionoperator,whichweshalldiscussalittlelater.Notethat forafeasiblesolution,theconstraintviolationvalueiszero.
Fromtheavailablebowling,batting,andfieldingaveragevalues ofeachofthe11chosenplayersforateam,wecanthencompute theoverallbowling,battingandfielding strengthsfortheteam.
NSGA-IIiscapableofhandlingthreeobjectivesandwecanemploy ittofindatrade-offfrontierthatisexpectedtohaveindividual optimalsolutions and alsoa number of differentcompromised solutions.Alittleproblemknowledgewillrevealthatateamhav- inganextremelygoodfieldingabilityandnotenoughbattingand bowlingskillsmaynotbewhatateamselectioncommitteemay belookingforinateam.Thus,insteadoftreatingthefieldingper- formanceasanobjectiveofitsowninouroptimizationstudy,we treatitmorelikeasecondaryobjectiveanduseittobreakatie amongtrade-offsolutions.Inthetournamentselectionoperatorof comparingtwosolutions,ifbotharenon-dominatedtoeachother fromthebowlingandbattingobjectives,theteamhavingabetter fieldingperformancewinsthetournament.
TheNSGA-II proceduregoesasfollows.Fromthecurrentset of N population members describing population Pt, a new set of Nsolutions (population Qt)is created repeateduse of tour- namentselection,recombinationandmutationoperators.Inthe tournamentselectioncomparingtwopopulationmembers,afea- siblesolutionispreferredoveraninfeasiblesolutionandalesser constraint-violatedinfeasiblesolutionwinsoveranotherinfeasible solution. Whentwo feasible solutions are compared, a hierar- chyofdecisionmakingisperformed.First,asolutiondominating its tournament competitor wins. Second, if both solutions are non-dominatedtoeachother,theonehavingbetterfieldingper- formancewins.Otherwise,ifbothsolutionshavethesamefielding performance, theone residing ona less-crowdedregionin the objectivespacewins.Thisisachievedbycomputingthecrowd- ingdistanceoperator [6].Twosuchselected solutionsare then matedunderarecombinationscheme(wediscusstherecombina- tionschemeinthenextparagraph)usingaprobabilitypcandtwo newoffspringteamsarecreated.Ifrecombinationoperationisnot performed,twoselectedsolutionsaresavedasoffspringsolutions.
Toachieveameaningfulrecombinationoperationbetweentwo NSGA-IIpopulationmembers,weusethecode-vectoroftwopar- ents,insteadoftheirvariable-vectors.Thus,acodeofthecaptain representedinoneparentmateswiththatinthesecondparentso thattwooffspringcodesintherange[1,10]arecreated.Forexam- ple,ifsolutions1and2mentionedabovearerecombinedatthe firstpositionasparents,codevalues3and2willgetrecombined asintegernumbers in therange [1,10] and twooffspring inte- gers,representingthecodevalueoftherespectivecaptainsfrom CL,willbecreated.Similarly,thecodeofthewicket-keeperofone
parentmateswiththatofthesecondparentsothattwooffspring codesintherange[1,15]arecreated.Noteherethatwhensolu- tions1and2mentionedabovearerecombined,codevalues6and 10willbeusedasparentintegersandtwooffspringintegerswillbe created.Thus,inthissituation,thewicket-keepercaptain(Kumar Sangakkara)willbeparticipatetwice(ifbothpositionsaretobe recombined)intherecombinationoperations–onceasacaptain forthefirstpositionandagainasawicket-keeperforthesecond position.Theremainingninecode-vectorsmateelement-wisefrom thethirdelementto11thelementandoffspringcodevaluesinthe range[1,129]arecreated.Alittlethoughtwillrevealthatsincethe remainingninecodevaluesarearrangedinascendingorderoftheir tagvalues,avariable-wiserecombinationbecomesmeaningfulin thesensethatalow-costplayergetsachancetomatewithanother low-costplayer,andahigh-costplayermateswithanotherhigh- costplayer.Weusetheinteger-versionoftheSBXoperator[5]as arecombinationoperator.Inthisoperator,everyelementinthe code-vectorisrecombinedwithaprobability0.5,thusonanaver- age50%oftheelementsgetrecombinedinacrossoveroperation.
Notethatevenifoneparentinvolvesawicket-keepercaptainand anotherinvolvesadifferentcaptainandawicket-keeper,sincethey arerecombinedwiththeircode-vectors,ameaningfulrecombina- tionwillalwaystakeplace.Eachoftheoffspringsolutionsarethen mutatedwithainteger-versionofthepolynomialmutationoper- ation[4]toslightlyperturbthem.Thisisdonewithamutation probabilitypm.Afterthemutationoperation, thecorresponding variable-vectorofeachoffspringisconstructed.Intheeventofa repetitionoftagvalues,additionalmutationoperationsareper- formedtilladistinct11-memberteamisformed.Theseoperations guaranteethatallcreatedoffspringsolutionssatisfythefirstthree constraints.WethenrelyonNSGA-II’sconstrainthandlingcapa- bilitiestosatisfyfourthandfifthconstraintsandcreatefeasible populationmembers.AfterthenewpopulationQtiscreated,itis combinedwithPtandacombinedpopulationRt=Pt∪Qtisformed.
Thecombinedpopulationisthensortedbasedonnon-domination level(withrespecttothebowlingandbattingobjectives).There- after,tocreatethenextgenerationpopulationPt+1,solutionsfrom thefirstsortedfrontisselectedfirst,thenthesecondfrontmem- bersaretaken,andsoon.Thisprocessiscontinuedtillnomore frontscanbeaccommodatedtothenewpopulation(recallthat Rt hasasizetwicetothatofPt+1).Thelastfrontthatcannotbe fullyaccommodatedinPt+1isundergonewithmorecriteria.First, theusualcrowdingdistancevaluesareassignedtoeachmember.
Second,theindividualobjective-extremesarechosenstraightway.
Third,thefrontmembersaresortedwiththethirdobjective(field- ingperformance)andtheremainingpopulationslotsarefilledwith solutionshavinghigherfieldingperformancevalues.Intheeventof atie,solutionsarechosenbasedontheircrowdingdistancevalue.
ThisendstheoperationofagenerationandPt+1isdeclaredasthe nextgenerationpopulation.NSGA-IIoperatorsarecontinuedinthis fashiontillapredefinednumberofgenerationsareelapsed.
3. Multi-objectiveoptimizationresults
Herewepresentthesimulationresultsoftheabove-mentioned algorithmappliedtotheplayerdatabase.Thebudgetconstraint isconsideredtohaveTotalBudget=6milliondollars.Atleastone wicket-keeper,onecaptain,andamaximumoffourforeignplayers mustbeincludedinateam,asmentionedbefore.Weusethefollow- ingstandardparametersettingsinalloursimulations:population size=400,maximumgenerations=400,crossoverprobability=0.9, mutationprobability=0.05, SBXdistributionindex=10[5],and mutationdistributionindex=20[4].
Fig.1showsthetrade-offfrontobtainedbyourmodifiedNSGA- II.Eachpointonthetrade-offfrontrepresentsateamof11players.
200 300 400 500 600 700 800 900 1000
−400
−350
−300
−250
−200
−150
−100
Net Bowling Average
−Net Batting Average Team B
Team C Team D
Chennai Super Kings
Team A
Fig.1.Multi-objectivetrade-offfrontobtainedbyNSGA-IIisshown.CSKteamis outperformedbyTeamsBandC(obtainedinthisstudy)onbattingandbowling performances.
Afewteamscorrespondingtothetrade-offpointsmarkedonthe figureareshowninTable1.Eachteamhasacaptain,a wicket- keeperandatmostfourforeignplayers.Also,theyallsatisfythe stipulatedbudgetconstraint.Therightextremeofthefrontmarks theteam havinghighest overall batting average, while theleft extremeshowsthemostbowlingdominantteam.Thetrade-off betweenthesetwoobjectivesisclearfromthisfigure.
Tocompareourresults,weconsiderarealteamof11crick- eterswhoplayedfortheChennaiSuperKings(CSK)teaminthe lastIPL(tookplaceinIndiaduring8Aprilto28May2011)and alsowonthefinal.Thebowlingandbattingperformanceofthis teamarecalculatedusingthesameprocedureasdescribedabove.
ThetotalcostofhiringtheCSKteamisestimatedtobearound 7.5milliondollars.Itturnsoutthatitisnotafeasibleteaminour representationbecauseofitsspendingmorethan6milliondollars inhiringtheplayers.Despitespendingmoremoney,CSKteamhas bowlingandbattingperformancesthatareworsethananumberof teamsfoundbyourNSGA-II.ThepointrepresentingtheCSKteamis shownontheobjectivespaceinFig.1.Itcanbeseenthattheteam isnon-optimalaswellascostlier.Similarobservationswerefound forotherpastIPLteamsaswell.Forbrevity,wedonotdiscussthem here.
Wenowperformanumberofpost-optimalityanalysestodeci- pher and understand useful insights about the team selection problem.
200 400 600 800 1000 1200
−450
−400
−350
−300
−250
−200
−150
−100
Net Bowling Average
−Net Batting Average
6 million USD 5 million USD 7 million USD No Budget
Fig.2. Budgetsensitivityanalysisillustratinghowthetrade-offfrontchangeswith theupperlimitonthetotalbudget.
3.1. Budgetsensitivityanalysis
To analyzethe effect of budget constraint ona team’sper- formance we have performed a sensitivity analysis where the optimizationprocessisrunforarangeofbudgetconstraintsandthe correspondingtrade-offfrontobtainedbyourmodifiedNSGA-IIis plotted.ItcanbeseenfromtheFig.2thatthebudgetconstraint affects batting dominant teams more than bowling-dominant teams.Thisisbecausethepricedifferenceamongbatsmenwith ahighbattingaverageandthosehavingalowaverageissignifi- cant.Thesameeffectdoesnotexistamongbowlersandhencethe minimumbowlingaverageregionofthetrade-offfrontisfairly unchangedduetoincreaseordecreaseintheTotalBudgetvalue.To getanideaoftheextremetrade-offfront,wealsoperformarunin whichnolimitonthetotalbudgetisimposed.Suchananalysiscan providetheteammanagersanideaabouthowmuchgaininbat- tingandbowlingaveragesispossiblebyspendingcertainamountof moremoneyinhiringateam.Interestingly,forthechosenplayer’s performancestatisticsandprice,alargeamountofinvestmentneed notmakeabetterbowlingteam,however,abetterbattingteamis possibletobeformedbyinvestingmoremoney.
Table2showsthebestbattingteamsfoundbyourproposed NSGA-IIprocedurefordifferentbudgetrestrictions.Itisclearhow
Table1
Fourteamschosenfromthetrade-offfront(Fig.1)obtainedbyNSGA-II.Thefirstrowmarksthecaptainandthesecondrowmarksthewicket-keeperofateam.Foreign playersinateamareshowninitalics.
TeamA TeamB TeamC TeamD
Players
SachinTendulkar YuvrajSingh YuvrajSingh YuvrajSingh
WriddhimanSaha WriddhimanSaha WriddhimanSaha WriddhimanSaha
MichaelHussey N.McCullum J.P.Duminy R.Ashwin
ManojTiwary ManojTiwary SudeepTyagi SudeepTyagi
RahulDravid RavindraJadeja RavindraJadeja N.Rimmington
SureshRaina SureshRaina SureshRaina PaulCollingwood
ShaunMarsh JamesFranklin JamesFranklin StevenSmith
AaronFinch BradHodge BradHodge PragyanOjha
A.McDonald A.McDonald A.McDonald ShakibAlHasan
ShikharDhawan ShikharDhawan JaidevUnadkat JaidevUnadkat
NamanOjha AmitMishra AmitMishra AmitMishra
Bat.avg. 378.0 324.1 269.8 120.2
Bowl.avg. 949.5 506.6 341.0 277.9
Cost($) 5,950,000 5,930,000 5,845,000 4,935,000
Table2
Bestbattingteamschosenfromthetrade-offfrontiers(Fig.2)obtainedfordifferentbudgetrestrictions.Firstrowindicatescaptainsandsecondrowindicateswicket-keepers.
Foreignplayersareshowninitalics.
5M$ 6M$ 7M$ Nolimit
Players
SachinTendulkar SachinTendulkar SachinTendulkar SachinTendulkar
WriddhimanSaha WriddhimanSaha WriddhimanSaha M.S.Dhoni
V.V.S.Laxman SureshRaina ShaunMarsh MichaelHussey
RahulDravid RahulDravid RahulDravid ManojTiwary
AaronFinch ShaunMarsh SureshRaina AaronFinch
ShaunMarsh AaronFinch AaronFinch RohitSharma
ManojTiwary MichaelHusse ManojTiwary SaurabhTiwary
MohammadKaif ShikharDhawan MichaelHussey S.Badrinath
ShikharDhawan A.McDonald A.McDonald A.McDonald
MichaelHussey NamanOjha ShikharDhawan ShaunMarsh
AndrewMcDonald ManojTiwary SBadrinath SureshRaina
Bat.avg. 364.7 378.0 389.3 403.1
Bowl.avg. 1022.4 949.5 949.5 874.7
Cost($) 4,910,000 5,950,000 6,530,000 11,030,000
mostteamsincludewell-renownedbatsmenineachoftheteams.
Whennobudgetrestrictionisused,theteamgotmultipleexpen- sivebatsmen,suchasSachinTendulkarandM.S.Dhoniinoneteam.
Althoughnoneoftheseteamsdowellinthebowlingcompartment ofthegameandafranchisemaynotchooseanyoftheseextreme teams,thepurposeofpresentingtheseteamsistodemonstrate thattheproposedNSGA-IIisabletofindsuchdreambattingteams asbestbattingteamsfordifferentbudgetaryrestrictions.Italso emphasizesthemotivationforchoosinganintermediatetrade-off solutionasapreferredteamwhichwouldhaveagoodtrade-off betweenbattingandbowlingaspectsofthegame.
3.2. Playerfrequencytable
Analyzingthetrade-offfrontshowninFig.1notonlyprovides uswith a setof high-performingteamsbut can alsogive us a betterinsightinteamselectionstrategies undera multi-criteria decisionmakingprocessandinadynamic,auction-likesituation.
Inthissection,werevealsomeimportantfeaturesofchoosinga high-performingteambasedontheinnovizationprinciplerecently suggestedelsewhere[8].
Toprepareacricketteamselectionstrategy,identificationof keyplayersisanimportanttask.Ausualapproachforthispurpose wouldbetoidentifythetopbatsmenortopbowlersaskeyplay- ersfortheteam[14],butitturnsoutthatchoosingsuchplayers usuallycomewithahighcostandateamhavingabunchoftop domain-specificgoodplayersmaynotresultinahigh-performing andcost-effectiveteam.Toidentifythekeyplayersinateamwe suggesta novelconcepthere.Allteamsappearingonthetrade- offfrontareconsideredforananalysisandthefrequencyofeach playerappearingonallteamsonthetrade-offfrontiscomputed.
Forexample,say,thereare50teamsonthetrade-offfrontandthe player,SachinTendulkar,appearsinfiveoftheseteams.Hence,his frequencyis5/50or10%.Fig.3showsthefrequencyofallplayers fromthedatasetonabargraph.Theplayersarerepresentedbythe tagsassignedtothemintheoptimizationprocess.Namesofafew highfrequencyplayersarealsomentionedonthebargraph.From thefigure,itcanbeseenthatmanyhigh-costplayersappearing ontherighthalf ofbargraph havea zerofrequency.Secondly, only35ofthe129playershavefrequencygreaterthanzeroand appearsin theteamsonthetrade-offfront,meaningthatother 94playersdonotcauseagoodtrade-offbetweenbatting,bowl- ingandfieldingperformanceswhenafixedbudgetisinmind,to appearonanyofthehigh-performingteam.Someofthesemost frequentlyappearing keyplayerscanbeidentifiedfromthebar graphand canbegiven highpriorityin forminga teamduring theauctionprocess. Acloseexaminationofthebargraphindi- catesthatourcommon-sensemethodofformingateamwithtop
batsmen and bowlers (mentionedabove) would failto capture thesecommonly-appearinghigh-valuedplayersonthetrade-off frontandsomefamousandhighly-pricedspecialistplayersmaynot haveagoodbatting-bowling-fieldingtrade-offtoappearasagood choiceforaneffectiveteam.Inasense,theaboveanalysisofiden- tifyingfrequentlyappearingplayersontheentiretrade-offfront providethenamesofeffectiveplayersforallthreecompartments ofthegame.Theseplayersarecommonly-appearingingredients ofhigh-performingteamsandhencemustbedesignatedasmost valuedplayersfortheoveralleffectiveperformanceofateam.It shouldbenotedthataplayer’sfrequencyisnotadirectindica- torofhowgoodanindividualplayerisonanyonecompartment ofthegame,butratherindicateshisimportanceintheformation ofahigh-performingteamconsideringbudgetconstraints,allthree aspectsofthegame(bowling,battingandfielding)andimportantly thechemistryinvolvedinotherplayer’spresenceintheteam.A knowledgeofsuchplayersmaybeusefulinthedynamicauction processofchoosingateamaswell.
Anotherobservationthatcanbemadeby ananalysisofthe obtainedtrade-offsolutionsisthecostofhiringeachteamunder the given budget restriction. An important question to ask is thatalthoughabudgetof6M$wastherestriction,didallhigh- performingtrade-offteamsutilizeallthat budget?Fig.4shows theamountofmoneyspenttoformhigh-performingteamsonthe
0 20 40 60 80 100 120 140
0 10 20 30 40 50 60 70 80 90 100
Player Tag
Frequency
Yuvraj Raina McDonald
Unadkat
Hodge
Manoj
Piyush
Dravid
Sachin Amit
Saha
Fig.3. Frequencyofplayersappearingonteamsfromthetrade-offfront(Fig.1).
949.46 649.05 556.26 482.53 409.23 392.80 314.53 298.15 286.21 278.10 0
1 2 3 4 5 6
x 106
Bowling Strength of Pareto Solution
Team Cost
Fig.4.Totalinvestmentinhiringeachteamonthetrade-offfrontwith6M$budgetrestriction.
trade-offfront.Theteamsarearrangedfromhighbattingstrength (ontheleft)tohighbowlingstrength(ontheright),orhightosmall valuesofbowlingstrength.Itisclearfromthefigurethatteams havinghighbattingstrengthmustspendalmostalltheallocated budgetinhiringtheteams,asmostgoodbatsmanaremorecostly than goodbowlers (see theresource containingplayers’ statis- tics[2]).Onlypredominantlybowlingteamsrequireabout80%of costneededtohireagoodbattingteam.Toinvestigateifthisisa trendwithothertwotrade-offfrontiers(having7M$andunlim- itedbudget),weplotthetotalamountofmoneyneededtohire eachofthehigh-performingteamswiththesebudgetrestrictions inFigs.5and6,respectively.Asimilartrendcanbeobservedfrom thesetwofiguresaswell.Inthecaseof7M$budget,mostteamsuti- lizethestipulatedallowedbudget,exceptthattheoptimalbowling teamsuselessbudget.Forthecaseofunlimitedbudgetrestriction, theresultisslightlydifferent.Optimalbattingteamsrequirehigher budgetscomparedtooptimalbowlingteams,buttheteamswitha goodtrade-offinbothaspectsofbattingandbowling(intermediate teams)requiresahighbudgetofaround12–14M$.Thisalsoreveals thatifarichfranchiseiswillingtospendmoremoney(saytothe tuneof20M$)tohireprobablythebestteamaround,thefranchise
willbeononehanddisappointedthattheredoesnotexistahigh- performingteamthatwillcostsomuchandontheotherhandthe franchisewouldbehappythatwithamuchlessermoneyahigh- performingteamcanbehired.Thus,theaboveanalysisnotonly helpsgetessentialqualitativeinformationofhowtoformahigh- performingteam,butalsoprovidesquantitativeinformationabout specificsand,aboveall,thenamesofarealteamwith11players thatwoulddothetrick.
Whenweinvestigatethenumberofforeignplayersineachof thesehigh-performingteamsacrossallthreefronts,weobserve thattheyallhaveexactlyfourforeignplayersineachteam,despite thefactthattherecouldhavebeenzerotoamaximumfourforeign playerspresentinanyteam.Thistellsusthatonewaytochoosea high-performingteamistomakesuretherearefourforeignplayers (themaximumnumberallowed)inateam,nomatterwhateveris therestrictionontheoverallbudget.Sinceafewforeignplayersare consideredinthedatabase,theyaresupposedtobegoodplayers anditisinterestingthatthequotaoffourforeignplayersisfilled ineachoptimalteam.
Someoftheseinsightsarenotobviousorintuitivebeforethe optimizationrunisperformedandresultingsolutionsareanalyzed.
949.46 719.64 586.66 490.78 415.28 389.23 307.72 294.20 287.77 283.52 277.85 0
1 2 3 4 5 6 7
x 106
Bowling Strength of Pareto Solution
Team Cost
Fig.5.Totalinvestmentinhiringeachteamonthetrade-offfrontwith7M$budgetrestriction.
874.65 490.41 349.74 315.73 300.14 288.71 277.41 0
5 10 15x 106
Bowling Strength of Pareto Solution
Team Cost
Fig.6.Totalinvestmentinhiringeachteamonthetrade-offfrontwithnobudgetrestriction.
Clearly,theabove optimization-cum-analysisprocedurereveals crucialinsightsthatcanactasthumb-rulesdictatingwhatateam- managermustdotoputtogetherahigh-performingteam.
4. Teamselectionasadecisionmakingprocess
Theobjectiveoftheentireprocessistoobtainahigh-performing singleteamof11players,ratherthanjustfindingandsuggesting a number of trade-off teams. Having identified a set of high- performingtrade-offteamswith differentbowling,batting and fieldingperformancevalues,weshallnowdiscussafewpragmatic methodologiesinchoosingaparticularteam.Towardthisgoal,we usecertainmulti-criteriadecisionmaking(MCDM)methods[15]
combinedwithcertainsubjectiveconsiderations.Decision-making insuchascenarioisadifficulttask,asthedecision-makersneedto keepinmindanumberofdifferentsubjectiveyetimportantcon- siderations,suchasbiasingforzonalplayersforsatisfyingfan-base, inclusionofstarplayersdespitetheircurrentpoorperformances etc. Afterthe initialoptimizationanalysis, we have a trade-off front,similartothatshowninFig.1.Differentmethodsnowcan beadoptedforthispurpose, buthere,wesuggestthefollowing twomethodsfortheselectionofafinalteam.
4.1. Kneeregionapproach
Theobtainedtrade-offfrontcomprisesofasetofpointsinthe objectivespacerepresentingvariousteams.Ifthetrade-offfront hasaknee-region,itisadvisabletoselectasolutionthatliesin thekneeregion.Suchasolutionismostalwayspreferredbecause deviatingfromthekneeregionmeansthatasmallchangeinthe valueofoneoftheobjectiveswouldcomefromalargecompromise inatleastoneotherobjective.Arecentstudysuggestedanumber ofviablewaysofidentifyingakneepointinatwo-objectivefront [7].Althoughakneeregionmaynotexistinalltrade-offfrontiers, avisualinspectionoftrade-offfrontsshowninFig.2revealsthat ingeneralabatting-bowlingtrade-offfrontexhibitsakneeinmost fixedbudgetconditionsforthegameofTwenty20cricket.
Applying the knee-finding methods on our trade-off front showninFig.1,weobservethatteamsBandClieneartheknee regions,althoughthekneeregionisnotvisuallyapparenttohave akneefortheobtainedfront.TheseteamsareshowninTable1.
TeamsCandDshowareasonablecompromisebetweenbatting andbowlingperformancesascomparedtoTeamsAandD.
4.2. Multiplecriterianon-dominatedsortingapproach
Thekneeregionapproachdescribedabovedoesnottakeinto accountmanysubjectivefactorsthatmay,inreality,defineagood team,suchasthefollowing:
1.Directfieldingperformance.
2.Successrateofthecaptain.
3.Wicket-keeper’sperformance.
4.Teamexpenditure.
5.Brandvalueofplayers,andothers.
Totakeinto accountthesefactors,we considerthesolution setobtainedfromknee-regionanalysisandcomputetheabove- mentionedfactors.Thereafter,arankingofimportanceoftheabove factorsaregatheredfromtheselector’spointofview.Forexample, thedirectfieldingperformancemaybethemostimportantfactor amongtheothersmentionedaboveinourteamselectionstrategy.
So,wesortthesolutionsetwithrespecttofieldingperformanceand pickthesolutionhavingthebestfieldingside.Intheeventofatie ondirectfieldingperformance,thenextrankedfactorcanbeused tochoosea teaminalexicographicmanner.SomeotherMCDM techniques,suchasanaggregatevotingstrategy[15]oranalytical hierarchyprocess(AHP)[19]canalsobeused.
To another extreme, if all the above factors are equally important,adominationapproachcanbeappliedtofindthenon- dominatedteamswithrespecttoalltheabovefactors.Theresultant bestfrontsolutions arethenconsideredfor furtheranalysis.To illustrate,weuseherethefirstthreecriteriaoffielding,captaincy, and wicket-keepingperformance for a non-dominatedanalysis.
Afteridentifyingthenon-dominatedteams,wesortthemaccord- ingtoremainingfactors,suchas,theteamexpenditureorthebrand valueofplayers.Usinganon-dominatedsortingoftheteamsinthe kneeregionusingthefirstthreefactors,weobtainonlythefollow- ingtwoteamsonthenon-dominatedfront.Theplayersinthese teamsaregivenbelow:
Team1:YuvrajSingh(C),WriddhimanSaha(W),SureshRaina, ManojTiwary,RoelofvanderMerwe,Amit Mishra,BradHodge, ShikharDhawan,NathanMcCullum,AndrewMcDonald,Ravindra Jadeja.
Team 2: Sachin Tendulkar (C), Wriddhiman Saha (W), Suresh Raina,Manoj Tiwary,James Franklin,Amit Mishra,BradHodge,
ShikharDhawan,RyantenDoeschate,AndrewMcDonald,Ravindra Jadeja.
To illustrate, we now use the team expenditure factor and observethatthecostofTeam1islesserthanthatofTeam2.Hence, Team1wouldbeourfinalpreference.
4.3. Customizedcriteria
Using the above multiple criteria non-dominated sorting approach,finallyTeam1isproposedtobehigh-performingand preferredteamwithinthesixmilliondollarcostconstraint.From Table1,itcanalsobeobservedthattheobtainedteamshaveover- allhighbattingandbowlingaveragebutlackfamousgoodbowlers (suchas DimitriMascarenhas (21),Nathan McCullum(25), and PiyushChawla(101)).Weobservethatthisisaproblemoriginating duetostatisticaldataconsideredwherethedifferenceinbowling averageofagoodbowlerandanormalbowlerismarginal,whilethe pricedifferencesaresignificant.InTwenty20formatofthegame,it canbearguedthatafewwell-knownexperiencedplayerscanplay akeyroletowardasuccessinamatchandjustoverallstrengthof teammaynotbenotenough.Such‘star’playersarenecessaryfora widefanbaseofafranchiseaswell.Hence,aparticularteamman- agementmayrequireatleastafewstarplayersinitsteamwhich canbeconsideredasanadditionalconstraint.Thisthenrequires thatinsteadofusingagenericalgorithmictechnique,somecus- tomizedcriteriamaybeincludedinchoosinga singlepreferred team.
Todemonstratetheeffectofcustomizedcriterion,weconsider ascenarioinwhichanemphasisofincludingstarplayersismade.
Wedefineastarbatsmanasaplayerwhohasscoredatleast1,500 runswithabattingaveragegreaterthan30inTwenty20formatand astarbowlerasonewhohastakenatleast70wicketswithabowl- ingaveragelessthan25.Inoursimulation,wealsoassumethata franchisedecidestokeepatleasttwostarbatsmenandthreestar bowlersinitsteam.Otherconstraintsimposedaresixmilliondollar budget,amaximumfourforeignplayers,andatleastonewicket- keeper,andonecaptain.Theresultanttrade-offfrontisshownin Fig.7.Again,usingthemultiple criterianon-dominated sorting decisionmakingprocedureoutlinedabove,weobservethatonly TeamQliesonthenon-dominatedfrontusingtheprimarycriteria offielding,captaincyandwicket-keeping.TeamQalongwithafew otherteamscorrespondingtopointsmarkedonthetrade-offfront areshowninTable3.Acomparisonoffourteamsinthistablewith thetwoteams(1and2)listedattheendofSection4.2,itisclear thatmostofthesenewteamshavestarplayers,therebymaking theseteamswell-acceptableamongthefansandalsotonothave tocompromiseontheoverallbatting-bowlingperformanceofthe teams.Interestingly,alltrade-offteamshaveexactlyfourforeign players,therebymakingthefourthconstraintactiveatthetrade-off solutions.
200 300 400 500 600 700 800
−350
−300
−250
−200
−150
−100
Net Bowling Average
−Net Batting Average
Team P Team R
Team S
Team Q
Fig.7. Trade-offfrontforteamswithstarplayers.
4.4. Dynamicoptimization
Theaboveanalysisfocusedonattainingtheoptimalsetofteams andthenusingdecisionmakingapproachestoidentifykeyplayers andoptimalteam.Thefirststepresemblestoselectionofafantasy cricketteam.Theknowledgeobtainedfromsuchanalysiscanalso bedirectlyextendedtoanauctionscenariowhichiscurrentlyin useatIPLteamselectionprocess.Thismakestheplayerselection processadynamicevent.Inanauctionbasedteamselectionsys- tem,asinIPL,theentirepoolofplayersisnotavailableinonegofor teamselectorstochoose.Besides,thefinalpriceofplayersisalso notfixedbeforehand.Onlyaminimumbasepriceforeachplayeris usuallyspecified.In[22],ananalysisofIPL2008auctionprocedure hasbeendoneandinterestingconclusionshavebeenmadewhere theauthorthrowslightondifferentfacetsoftheauctionandpro- posestheuseofadraft.Singh,GuptaandGupta[21]focuseson formulatinganintegerprogrammingmodelfortheefficientbid- dingstrategyforthefranchisesandimplementsitintheformofa spreadsheetforaneasyuse.Theauctionbroadlycomprisesoftwo tasks–theassignmentofplayerstoteamsandthedetermination ofplayersalaries.Theroleofoptimizationcomesintoplaymainly fortheassignmentofplayerstoateamandtheplayerpricefactor actsasanconstraint.Ourproposaltohandlesuchascenarioisas follows.
First,apre-processingoptimizationanalysisusingthehighest expectedpriceofeachplayerisdone.Thedecisionmakingpro- cedurediscussed abovehelpsselectonedesiredteam fromthe
Table3
Fourteamschosenfromthetrade-offfrontwithcustomizedconditionsonstarplayers.Thefirstrowmarksthecaptainofateamandsecondrowmarksthewicket-keeper, exceptinTeamSthecaptainisalsoawicket-keeper.Foreignplayersareshowninitalics.
TeamP TeamQ TeamR TeamS
SachinTendulkar YuvrajSingh YuvrajSingh M.S.Dhoni
WriddhimanSaha WriddhimanSaha WriddhimanSaha PaulCollingwood
SBadrinath NathanMcCullum KieronPollard RAshwin
ManojTiwary ManojTiwary ManojTiwary PragyanOjha
NathanMcCullum BradHodge DimitriMascarenhas BradHodge
SureshRaina SureshRaina SureshRaina MunafPatel
ShaunMarsh PiyushChawla BradHodge StevenSmith
AmitMishra AmitMishra AmitMishra AmitMishra
AndrewMcDonald AndrewMcDonald AndrewMcDonald DimitriMascarenhas
ShikharDhawan ShikharDhawan JaidevUnadkat JaidevUnadkat
DimitriMascarenhas StevenSmith SudeepTyagi SudeepTyagi
obtainedtrade-offfront.It mayhappenthatintheauctionpro- cess,someplayersfromthedesiredteamarealreadyboughtby otherfranchises. Thus, teamowners must know trade-offs and alternativechoices duringtheauctionprocess.Hencein sucha dynamicenvironment,asystematicapproachneedstobefollowed.
Usingtheinitialbargraphanalysis(showninFig.3),highvalued playersarefirstidentified.Theseplayersmustthenbegivenpri- orityforselection.AfterPhase1is completed,theoptimization anddecision-makingprocessneedtobesimulatedagainwiththe remainingplayers.Here,theselectedplayersmustbeincludedin eachteamconsideredduringtheoptimizationprocessanddeci- sionmakingprocess.Thenewsetofhighvaluedplayerscanthen beidentifiedbyusinganotherbargraphanalysisprocessandthe nextsetofplayerscanbeidentified.Ateachphase,theselectionof playersfromtheobtainedtrade-offfrontmustbedonejudiciously fromthehighfrequency(valued)playerstoensureaproperbalance oftheteam.Henceusingsuchaprocedurerepeatedlyinadynamic optimizationmodeateamwithahighoverallperformancecanbe obtained.Weperformacasestudyinthefollowingparagraph.
Suppose,inPhase1ofauction,11 playerswithtags27,120, 121,122,123,124,125,126,127,128,and129areconsideredin theauctionpool,meaningthatonlytheseplayersarenowavail- abletopickedbyanyfranchise.LetusalsoassumethatafterPhase 1optimizationanddecision-making,thefranchiseXselectsTeam1 mentionedinSection4.2tobethemostpreferredteam.However, letusalsoconsiderapredicamentwherethecaptainofTeam1, YuvrajSingh,hasalreadybeenboughtbyanotherfranchiseandis nolongeravailableforfranchiseX.Thus,Team1asawholecannot beapreferredchoiceanymoreandfranchiseXnowneedstolook foranotherhigh-performingteamfromitsmulti-objectiveopti- mizationresults.Letusassumethatafterreviewingallthetrade-off high-performingteamsofPhase1thatdonotcontainYuvrajSingh, Team2 withSachinTendulkaras acaptain (mentionedin Sec- tion4.2)becomesthenextpreferredteamforfranchiseX.Ofthe above-mentionedauctionpoolof11names,SachinTendulkar(tag number120),isthenoptedandfinalizedasateammemberoffran- chiseX.Inthenextphase,alltheabove11namesintheauction poolareboughtbyotherfranchisesandarenolongeravailablefor furtherconsideration.
Inthisscenario,franchiseXcanperformanothermulti-objective optimizationrunwithSachinTendulkarasacaptainandlookfor ateamhaving10moreplayers.Fromthesetof129players,the Phase1auctionpoolplayersarealsoeliminatedandremaining 119playersbecomethepoolfromwhich10playersaretobecho- sen.Otherconstraintswillremainandanewoptimizationruncan beexecuted.Theresultingtrade-offfrontisshowninFig.8.Itis notasurprisethatwitharestrictedsetof(119)playersavailable tochoosefrom,thePhase2frontisdominatedbyPhase1front obtainedwithall129availableplayers.Duetoaslotfixedwith SachinTendulkar(whoisprimarilyabatsman),theteamwiththe bestbowlingperformanceissomewhatworsethatthebestbowl- ingteaminPhase1.However,thepresenceofagoodbatsmaninthe teammakesthebestbattingteaminPhase2tohaveamarginally worseperformancethanthebestbattingteaminPhase1.Thesight deteriorationinthebattingperformancecomesfromtheunavail- abilityofanotherbatsmanWriddhimanSaha(Tag27)inPhase2.
Afterobtainingthetrade-offfront,weperformanotherbar-graph analysistoinvestigatethemostvaluedplayersinPhase2.Thebar graphisshowninFig.9.Itcanbeseenhowthefrequencyofmost playersremainssimilartothepreviousbargraph(Fig.3),except forafewplayersforwhomitinstantlyrises.Forexample,thefre- quencyofNamanOjhaasawicket-keepershootsup,againdueto absenceofWriddhimanSaha(Tag27).Itcanbeobservedthatin Phase1mosttrade-offteamshadhimasawicket-keeperandhis absencehasincreasedthesuitabilityofNamanOjhaasthenext choiceforawicket-keeper.Againrepeatingthekneeregionand
200 300 400 500 600 700 800 900 1000
−400
−350
−300
−250
−200
−150
−100
X: 556.5 Y: −310.6
Net Bowling Average
−Net Batting Average
Phase 1 Phase 2
Team 2
Team 3
Fig.8. Trade-offfrontobtainedinPhase2iscomparedwiththatinPhase1during theauction-baseddecision-makingcasestudy.
non-dominatedsortinganalysiswiththenewtrade-offteamsas before,wechoosethefollowingteamasournextpreferredteam:
Team3:SachinTendulkar(C),NamanOjha(W),Roelofvander Merwe,ShikharDhawan,ManojTiwary,PiyushChawla,Amit Mishra,NathanMcCullum,AndrewMcDonald,BradHodgeand SureshRaina.
Team3isshownontheobjectivespaceinFig.8alongwithTeam 2.FranchiseXwouldthenchooseaplayerfromTeam3basedon thenextannouncedauctionpoolofplayersandthisprocesscan continuetillthecompleteteamisformed.Sinceateveryphase, thepreviously-chosenplayersareconsideredinbothoptimization anddecision-makingprocesses,theplayersarepickedasateam andthedynamicformationoftheteamwillproduceateamthat wasbestpossibletoachievegiventheauctionnatureoftheteam selectionprocess.Theaboveprocedureisflexibleandifinsteadof one-player-at-a-timeauction,ifmultiple-player-at-a-timeauction isplayed,theaboveprocedurewillallowasimplewaytochoose
0 20 40 60 80 100 120 140
0 10 20 30 40 50 60 70 80 90
Player Tag
Frequency
Sachin Naman
Manoj
Raina Hodge
Mcdonald
Ashwin Sudeep
Unadkat Amit
Fig.9.FrequencyofplayersduringPhase2auction.