The Trading Agent Competition Supply Chain Management scenario (TACSCM)

CHRISTOPHERKIEKINTVELD,MICHAELP.WELLMAN,SATINDERSINGH,andVISHALSONIUniversityofMichigan

TheTACsupply-chaingamepresentsautomatedtradingagentswithchallengingdecisionprob-lems,includingprocurementofsuppliesacrossmultipleperiodsusingmultiattributenegotiations.Theprocurementprocessinvolvessubstantialuncertaintyandcompetitionamongmultipleagents.Ouragent,DeepMaize,generatesrequestsforcomponentsbasedondeviationsfromareferenceinventorytrajectorydefinedbyestimatedmarketconditions.Itthenselectsamongsupplieroffersbyoptimizingavaluefunctionoverpotentialinventoryprofiles.ThisapproachofferedstrategicflexibilityandachievedcompetitiveperformanceintheTAC-03tournament.

CategoriesandSubjectDescriptors:I.2.11[ArtificialIntelligence]:DistributedArtificialIntel-ligence—intelligentagentsandmultiagentsystems;J.4[ComputerApplications]:SocialandBehavioralSciences—economicsGeneralTerms:Algorithms,Economics

AdditionalKeyWordsandPhrases:TradingAgents,E-Commerce,SupplyChains

1.INTRODUCTION

TheTradingAgentCompetitionSupplyChainManagementscenario(TAC/SCM)wasdesignedtoposeacomplexmulti-tiered,multi-periodproblemforautomatedtradingagentsinaplausiblesupplychaingame[Sadehetal.2003].TheTAC/SCMenvironmentischallengingformanyreasons.Oneisthatagentsarefacedwithsub-stantialuncertainty:aboutthelocalstateofotheragentsinthegame,aswellastheunderlyingdemandandsupplyprocesses.Theenvironmentisalsostrategic,comprisingsixprofit-maximizingproduceragents.Agentsmustnegotiatemultiat-tributedealswithsuppliersandcustomers,sotheymustbeabletoreasonabouttherelativevaluesofthoseattributes.Finally,theSCMgameforcesagentstomakedecisionsovermultiplestages,andondifferenttimescales.Agentsmustmakede-cisions(e.g.,componentprocurement)beforeallrelevantuncertaintyisresolved(e.g.,customerdemand,futurecomponentprices).

WedesignedtheUniversityofMichigan’sagent,DeepMaize,toparticipateinthe

Author’saddress:ComputerScienceandEngineeringDivision,UniversityofMichigan,AnnAr-bor,MI48109.

Email:{ckiekint,wellman,baveja,soniv}@umich.edu

Permissiontomakedigital/hardcopyofallorpartofthismaterialwithoutfeeforpersonalorclassroomuseprovidedthatthecopiesarenotmadeordistributedforprofitorcommercialadvantage,theACMcopyright/servernotice,thetitleofthepublication,anditsdateappear,andnoticeisgiventhatcopyingisbypermissionoftheACM,Inc.Tocopyotherwise,torepublish,topostonservers,ortoredistributetolistsrequirespriorspecificpermissionand/orafee.c2004ACM0000-0000/2004/0000-0009$5.00󰀄

ACMSIGecomExchanges,Vol.4,No.3,February2004,Pages9–18.

10

·

Kiekintveldetal.

2003TAC/SCMtournament.DeepMaizeemploysdistributedfeedbackcontroltocoordinateitsvariousmodulesandoperaterobustlydespitedynamicuncertainty.Itsoverallfeedback-controlapproachandthespecificmethodsbywhichDeepMaizesetsitsreferenceinventorytrajectoryaredefinedelsewhere[Kiekintveldetal.2004].Herewefocusonhowtheagentmanagesitsprocurementactionsgiventhereferencetrajectory,byoptimizingavaluefunctionoverpotentialinventoryprofiles.

Valuefunctionrepresentationshavebeenusedtomakedecisionsinotherman-ufacturingcontexts.Forexample,Schneideretal.[1998]formulateaproductionschedulingproblemasaMarkovDecisionProcess(MDP)andusereinforcementlearningmethodstoapproximatethevaluefunctionofthisMDP.ThedecisionproblemweaddressdoesnotfittheassumptionsoftheMDPmodelandmustbemadeinthecontextofalargeragentmakingmanydistributedbutinterrelateddecisions.Ourapproachusesaheuristicvaluefunctionrepresentationthatincor-poratesvaluesfromseveraldifferentsourcesinsupportofasingledecision.2.

PROCUREMENTDECISIONSINTAC/SCM

EachdaySCMagentsmustmakeseveraldecisions,twoofwhichcomprisetheprocurementpolicy:(1)WhatRFQstoissuetocomponentsuppliersand(2)Oftheoffersreceivedfromsuppliers,whichtoaccept.Thereareeightsuppliers,eachproducingtwocomponenttypesfromfourcategoriesofcomponents:CPU,moth-erboard,memory,andharddisk.ThefourCPUtypesareeachsoldbyasinglesupplier;thetwotypesofcomponentsinallothercategoriesareeachsoldbytwosuppliers.Eachsupplierhasanominalcapacitytoproduce500perdayofeachcomponenttypeitsupplies.Actualproductionvariesaboutthiscapacityinaran-domwalk.Toacquirecomponents,anagentsendsRFQstoasupplier(uptotenpersupplierperday,inpriorityorder),eachspecifyingadesiredquantityandduedate.Thesupplierrespondsthenextdaywithoffersspecifyingquantity,duedate,andprice,andreservessufficientcapacitytomeetthesecommitments.Ifprojectedcapacityisinsufficienttomeettherequestedquantityanddate,thesupplierinsteadoffersapartialquantityattherequesteddateand/orthefullquantityatalaterdate.Suppliersassumenominalcapacitywhenprojectingfutureavailability.Togenerateresponses,suppliersexecutethefollowinguntilallRFQsareexhausted:(1)randomlychooseanagent,(2)takethehighest-priorityRFQremainingonitslist,(3)generateanoffer,ifpossible.Agentsmustacceptordeclineeachofferthedaytheyreceiveit.

Supplierssetpricesbasedonananalysisofavailablecapacity.TheTAC/SCMcomponentcatalog[Arunachalametal.2003]associateseverycomponentcwithabaseprice,bc.Thecorrespondencebetweenpriceandquantityforcomponentsuppliesisdefinedbythesuppliers’pricingformula.Thepriceofferedbyasupplieratdaydforanordertobedeliveredondayd+iis

κc(d+i)

,(1)500i

whereκc(j)denotesthecumulativecapacityforcthesupplierprojectstohaveavailablefromthecurrentdaythroughdayj.Thedenominator,500i,representsthenominalcapacitycontrolledbythesupplieroveridays,notaccountingforanycapacitycommittedtoexistingorders.

pc(d+i)=bc−0.5bc

ACMSIGecomExchanges,Vol.4,No.3,February2004.

DeepMaizeProcurementinTAC/SCM

·

11

3.DEEPMAIZEREFERENCEINVENTORYTRAJECTORY

Thereferenceinventorytrajectoryisthesumofthreesourcesofcomponentrequire-ments:(1)outstandingcustomerorders,(2)expectedfuturecomponentutilization,and(3)baselinebufferlevels.First,outstandingcustomerordersentailaknownrequirementforspecificcomponentsintimetoproducetheorders.

Second,wederivethetimeseriesofexpectedfuturecomponentutilization,basedonprojectionsoffuturecustomerdemandforPCsandmarketequilibriumcalcula-tions.TheprojectionofcustomerdemandusesadynamicBayesiannetworkmodeltoestimatetheunderlyingdemandstateandprojectthesevaluesforwardusingthespecifiedsystemdynamics.Marketequilibriumisderivedforeachdaybycalcu-latingtheprices(basedonEq.(1))atwhichthesupplywouldequaltheprojectedcustomerdemand.DeepMaizeassumesthatitwillgarner,onaverage,neworderscovering1/6oftheequilibriumquantityQdfordayd,evenlydistributedacrossthepossiblePCtypes.Toaccountforunpredictabilityinthedemandtrends,wesetasomewhatmoreconservativereference,basedonthedemandquantityQ󰀄satis-fyingPr(Qd≥Q󰀄)=0.63(0.63waschosensomewhatarbitrarily).Overtherangewhereexistingandprospectivecustomerordersoverlap,wephaseintheexpectedutilizationproportionately.

Thefinalcontributortoourinventoryreferenceisabaselinebufferlevel,main-tainedtomitigateshort-termnoiseinprocurementandsalesactivityandallowtheagenttoactmoreopportunistically.Forthetournament,DeepMaizesetthebaselinelevelat6.0timesthecurrentexpecteddailyconsumption(alsosomewhatarbitrary).Thislevelisscaledgraduallytozeroattheendofthegame,atwhichpointinventoriesbecomeworthless.Thesumoftheserequirementsrepresentsthetrajectoryofgrossinventoryrequirements.Todeterminethenetreferencetrajec-tory,wesubtractthecurrentinventoryofcomponents(includingthosecontainedinfinishedPCs)plusanticipateddeliveriesofcomponentsalreadypurchasedfromthegrossrequirements.

4.DEEPMAIZEPROCUREMENTPOLICY

EachdayagentsissueRFQstosuppliersandacceptorrejectsupplieroffersre-ceivedinresponsetothepreviousday’sRFQs.DeepMaizeappliesthesameRFQ-generationandoffer-acceptancepoliciestoeverydayofthegame,withonesig-nificantexception:theverybeginningofthegame(day0).Thesupplierpricingformulaprovidesastrongincentivetoprocurelargequantitiesofcomponentsonthisday,aspricesareattheirlowestandavailabilityisashighasitwilleverbe.1Asaresult,inTAC-03agentsemployedincreasinglyaggressiveday-0procure-mentpolicies,leadingtoamutuallydestructiveovercapacityofcomponentsfortheaggregatesystem.Weanticipatedthiseffectandintroducedourownpreemptiveday-0strategythatneutralizedthisbehaviorsomewhatand,ineffect,reestablishedasettingwhereinagentshadtoprocuresuppliesthroughoutthegame.Thedetailsofourday-0strategyanditseffectsaredescribedinaseparateaccount[Estelleetal.2003].Forourpresentpurpose,itsufficestonotethatweemployedspecialRFQgenerationandofferacceptancestrategiesattheverybeginningofthegame.

1Due

toitsdistortingeffects,thiswillbemodifiedforthe2004tournament.

ACMSIGecomExchanges,Vol.4,No.3,February2004.

12

·

Kiekintveldetal.

4.1RFQGeneration

DeepMaizegeneratesRFQstoreducethedifferencebetweenthecurrentandref-erenceinventorytrajectories.Threeelementsofthereferencetrajectoryarecon-sideredinturn:outstandingcustomerorders,baselinebufferlevel,andexpectedfuturecomponentutilization.Thisprioritizationtakesintoaccounttheimmediacyofcurrentordersandsubsequentopportunitiestoprocurecomponentsforfutureconsumption.TAC/SCMlimitsagentstotenRFQsperdaypersupplier,andDeepMaizeusesalltheseslots.ItgeneratestenRFQs(splitacrosstwosuppliers)foreachnon-CPUcomponenttype,andfiveforeachCPU.

4.1.1RFQsforoutstandingcustomerorders.Figure1depictstheprocessofgeneratingorder-relatedRFQs.Wecomputethecurrentinventorytrajectoryin-cludingcomponentsinassembledPCsaswellasknownfuturecomponentarrivals.Foreachcustomerorderthatcannotbefilledusingcurrentinventory,wegenerateanRFQforthecorrespondingdeficitquantityandduedate.Ifmorethan8RFQsaregenerated,thosewithnearbyduedatesaremergedtostaywithinthisquota.

QuantityInventory ProjectionQuantityPrevious Inventory Projection

New Inventory Projection

Quantity Required(for outstanding customerorders)Due DateDeficit Quantities

(a)

(b)

Due Date

Fig.1.Generatingorder-relatedRFQsforaparticularcomponent.(a)Quantitiesrequiredand(b)Finalcomponentinventoryprojection.RFQsarecreatedforthedeficitquantitiesin(b).

4.1.2RFQsforbaselinebufferlevel.Thecurrentinventorytrajectoryismodi-fiedbyremovingPCsandcomponentsalreadycommittedtooutstandingcustomerorders.AnRFQisgeneratedforthefirstdaythistrajectorydropsbelowthebase-linebufferleveltomakeupthedifference.Ifthisquantityislarge,theRFQissplitintwo,withhalfthequantitysenttoeachsupplierforthecomponenttype.4.1.3RFQsforexpectedcomponentutilization.AnyremainingRFQslotsareusedtorequestcomponentsaddressingthelong-termexpectedcomponentutiliza-tion.ThesamecurrentinventorytrajectoryusedforgeneratingbaselineRFQsisusedagain,andtheexpectedcomponentutilizationcurveissubtractedfromthis

ACMSIGecomExchanges,Vol.4,No.3,February2004.

DeepMaizeProcurementinTAC/SCM

·

13

trajectory.ApotentialRFQisgeneratedforeachdaywherethisquantityisneg-ative.AsubsetoftheseRFQsareselectedtofilltheavailableRFQslots.Theselectionisprobabilisticallybiasedtowardsdayswhencomponentsareexpectedtobecheaper.ToestimateavailablepricesDeepMaizemaintainsanassessmentofeachsupplier’savailablecapacityprofile,basedontheoffersseenandthesupplierpricingfunction.Eachofferyieldsinformationaboutthesupplier’scurrentcapac-ity.Forexample,apartialcompletionoffermeansthatasupplierhasexactlytheofferedquantityavailablebytherequestedduedate,andnomorethantheofferedquantityavailableonanypreviousday.Calculatingtheimplicationsofeveryofferyieldsanupperboundoncapacity(andthuslowerboundonprice)foreachday.4.1.4ProbeRFQs.IfRFQslotsareavailableafterallreferenceinventorytrajec-toryneedshavebeenmet,DeepMaizeissuesprobeRFQs—forasinglecomponentonarandomdate—togarneradditionalinformationaboutsupplierstate.4.2

OfferAcceptance

Theofferacceptancemechanismselectswhichsupplierofferstoacceptbasedonthereferenceinventorytrajectory.DeepMaizemakesitsacceptancedecisionsseparatelyforeachcomponenttype.Foreachofferreceived,itmayhavethreechoices:reject(R),acceptcomplete(AC),oracceptpartial(AP)—thethirdoptionisapplicableonlyiftheofferincludesthisoptionduetothesupplier’sinabilitytoprovidethefullquantitybytherequesteddate.

Givenasetofnoffers,leto=󰀇o1···on󰀈,oi∈{R,AC,AP},denoteadecisionvector.Theagent’soptimizationproblemistoidentify

󰀁

argmaxnV(s,o)−Ci(oi),(2)

o∈{R,AC,AP}

i

whereV(s,o)isthevalueoftheinventorytrajectorystartingfromcurrentstates

plustheordersacceptedaccordingtoo.Thestatecomprisesallinformationrelevanttothereferenceinventorytrajectory,includingcurrentinventoryofcomponentsandPCs,anticipatedcomponentdeliveries,andoutstandingcustomerorders.Ci(AC)(respectively,Ci(AP))denotesthecostofacceptingthecomplete(resp.partial)orderi.Foralli,Ci(R)=0.

Thethreesourcesofcomponentrequirementscontributedifferentiallytothevaluefunction.Componentsrequiredtofillexistingcustomerordersarevaluedattheentirepriceoftheorderplusthepenaltychargesavoidedbymeetingtheorder.ThepenaltyamountspecifiedinthecustomerRFQispaideachdayanorderislateuntilitexpires,sothepenaltychargessavedvarydependingonwhentheordercanbemet.Thesevaluesarequitehighcomparedtothecostofanindividualcomponent,implyingthat(almost)anyoffernecessarytomeetanexistingcustomerorderwillbeaccepted,regardlessofprice.Includingpenaltychargesallowstheagenttoreasonaboutcaseswhereanordercanbemetearlierbyacceptingoneofferoveranother,reducingpenaltypayments.Componentsthataddressfutureexpectedconsumptionarevaluedattheexpectedequilibriumpricefortheprojecteddayofconsumption.Thisreflectsanassumptionthatthemarketwillbeinequilibrium,andthusanycomponentsobtainedforlessthantheequilibriumpricewillleadtoprofitablefutureproduction.

ACMSIGecomExchanges,Vol.4,No.3,February2004.

14

·

Kiekintveldetal.

Componentsthatfillbaselineinventoryarevaluedattheequilibriumpriceforthecurrentdayplusabaselinepremium.Thebaselinepremiumisdefinedonaslidingscale,withhigherpremiumvaluesforthefirstcomponents.2Thepremiumvaluesareintendedtoheuristicallyaccountfortwofactors:(1)thefactthatcompo-nentsactuallyhavevalueonlywhencombinedwithothercomponentsand(2)theopportunitycostofhavingproductionconstrainedbyavailablecomponents.Thebaselinevaluesaredecayedbyaconstantmultiplicativefactoreachdaytorepresentabiastowardsachievingthebaselineinventoryassoonaspossible.

Tovalueaninventorytrajectory,westartbycreatingasortedlistofpossiblecomponentvaluesforeachfutureday.Unitvaluescalculatedfromthecurrentreferencetrajectoryaccordingtotherulesaboveareinsertedintothelistforthelastdaytheneedcanbemet.Eachcomponentisthenvaluedinorderofarrival.Thealgorithmlooksforwardfromthedayofarrivaltofindthemaximumpossiblevaluethatcanbeassignedtothecomponentandremovesthisvaluefromthecorrespondinglist.Ifthevalueisfromalaterdaythanthecomponentarrives,thevalueisreplacedwiththehighestvaluefromanearlierday.Thisisnecessarytoensurethatthemaximalsumisalwaysassigned.Toseewhythisisso,considerahighlysimplifiedexamplewithsinglecomponentsarrivingondays0and2andthefollowingunitvaluesforthenextthreedays:OriginalValuesDay0:20,5

Day1:15,10,10Day2:30,15,5

WithoutReplacementDay0:20,5

Day1:15,10,10Day2:15,5

WithReplacementDay0:5

Day1:15,10,10Day2:20,15,5

Thatis,havingoneunitonday0isworth20,andthesecondisworthanadditional5.Thecenterandrightcolumnsreflectthevaluesafterassigning(andremoving)onevalue,withandwithoutreplacement.Withoutreplacement,thevalue30isassignedtothefirstcomponentand15tothesecond.Thesevaluesarenotmaximalsincethefirstcomponentcouldbeassignedthevalue20andthesecondassignedthevalue30withbothcomponentsstillarrivingintime.Byreplacingthevalue30withthevalue20whenitisremovedwecanrepresentthepossibilitythatalaterarrivingcomponentcouldfillthisneed,freeingthefirstcomponenttofillanearlierhigh-valuedneed.

Whenallcomponentsarrivingonagivendayhavebeenvalued,anyremain-ingorder-basedorbaselinevaluesarepropagatedtothenextday,accountingforpenaltiespaid,orderexpirations,anddecayofbaselinevalues.Expectedutilizationvaluesareneverpropagated.Oncetheentireinventorytrajectoryisprocessed,itstotalvalueissimplythesumofthevaluesassignedtoitscomponents.Thenetvalueoftheorder-acceptancedecisionisthisvalueminusthecostofacceptedorders(Eq.2).

Usingthisproceduretoevaluatecandidatechoices,wesetupasearchproblemforeachcomponenttype.Thesearchspaceisdefinedbythepossibleacceptancedecisions.Sincethereareatmostthreepossibledecisionsandn≤10originalRFQs,thereareupto310inventorytrajectoriestoevaluate.Thisistoomanygiventhelimitedtimeavailable(15seconds)foreachday’sdecisions,soweperformalocal

2Values

from25–100%ofthecomponentbasepricewereusedduringthetournament

ACMSIGecomExchanges,Vol.4,No.3,February2004.

DeepMaizeProcurementinTAC/SCM

·

15

TableI.DeepMaizetournamentprocurementbyRFQtype.Pricesarenormalizedtoapercentageofthebaseprice.

StrategicOrdersBaselineUtilizationProbe

PercentageofRFQs0.8%1.7%6.6%27.7%63.3%AcceptanceRate32.3%10.3%24.7%53.0%18.4%PercentageofQuantity51.2%0.7%14.0%33.1%9.4%AveragePrice57.684.868.565.361.4optimizationusinghill-climbingsearch.Totheextentthatanofferisworthwhile

ornotindependentofwhichothersareaccepted,hill-climbingshouldquicklyfindanear-optimalsolution.

Thesearchstartsfromanoderepresentingthestatemaximallyacceptingoffers.Ateachnode,theneighborhoodofstateswithonedecisionchangedisexamined.Ifahigher-valuedstateisfound,thatstatebecomesthenewcurrentsearchnode,anditsneighborhoodisexpanded.Whennohigher-valuedstateisfoundinthisneighborhood,thesearchisextendedtoaneighborhoodincludingstateswithtwodecisionschanged.Searchterminateswhentheextendedsearchfailstofindahigher-valuedstate,orwhentimerunsoutformakingadecision.Toallowequalopportunitytofindreasonableacceptancesetsforallcomponenttypeswerunsearchesforall10typesinparallel,evaluatingonestateeachturn.Onceallsearchesterminate,ordersaresentforthehighest-valuedacceptancesets.5.

DISCUSSION

InthissectionwepresentsomeresultsfromtheTAC-03tournamenttoshowhowDeepMaize’sprocurementstrategyworksinpractice.TableIshowsabreakdownofhowthedifferenttypesofRFQsDeepMaizesendscontributedtoitsprocure-mentduringthesemi-finalandfinalrounds.3Procurementquantitiesweresplitalmostevenlybetweenstrategicandsteady-statebehaviors.Order-basedneedswerethemostexpensivetofill,followedbybaselineandfutureutilizationneeds.Thisisconsistentwiththerelativevaluesassignedtothoseneedsduringtheofferacceptanceprocess,andindicatesthatthepremiumvalueschangetheacceptancedecisionsintheintendedway.DeepMaizepurchasedthebulkofitscomponentsusingthestrategicandfutureutilizationmechanisms,avoidingtheneedtopayhighpremiumsforcomponentsinallbutrareinstances.

WealsocomparedtheaveragepricespaidandquantitiesprocuredbyDeepMaizetotheotherfiveagentsinthetournamentfinals.Theresultsarebrokendownintothreetimeperiods:day0,days1–2,andtherestofthegame.Day0iswhenmostofthestrategicinteractionsplayedout,butRedAgentandDeepMaizebothhadfallbackstrategiesthatprocuredsubstantialadditionalquantitiesimmediatelyafterday0.Days3–219representthedayswhenourprocurementmodulewasusingitssteady-statepolicy.InTableIIweseethatallagentspurchasedasubstantialfractionoftheircomponentsonday0.Whitebearpurchasedcomponentsonlyonday0,butendeduppurchasingfarfewertotalcomponentsthanmostotheragents.All

allgamesplayedbyDeepMaizeexcept1241,1269,and1429whenDeepMaizeexpe-riencednetworkproblems(atotalof28games).WealsonotethatDeepMaizeusedsomewhatdifferentday-0procurementstrategiesinthethreerounds.Thepatternofresultspresentedhereholdswhentheroundsareconsideredindividuallyinsteadofinaggregate.

ACMSIGecomExchanges,Vol.4,No.3,February2004.

3Includes

16

·

Kiekintveldetal.

TableII.ComponentquantitiespurchasedduringdifferentgameperiodsintheTAC-03finalround.CheckmarksindicateastatisticallysignificantdifferencewithDeepMaize(p≤0.05),whilexindicatesalesssignificantdifference(p≤0.10).Agentsarelistedintheordertheyplacedinduringthetournamentfinals.

Day0Days1–2Days3–219Ave.TotalPurchased

RedAgent40.9%x19.5%󰀁39.7%254101󰀁deepmaize31.1%29.4%39.5%226423TacTex33.0%0.8%󰀁66.3%󰀁80396󰀁Botticelli41.2%x0.0%󰀁58.8%󰀁213340PackaTAC20.4%󰀁3.8%󰀁75.8%󰀁117545󰀁whitebear100.0%󰀁0.0%󰀁0.0%󰀁53571󰀁TableIII.Averagenormalizedpricespaidforcompo-nentsduringtheTAC-03finalround.Checkmarksindi-cateastatisticallysignificantdifferencewithDeepMaize

(p≤0.05).

Days0–219Days1-2Days3–219RedAgent0.6330.822󰀁0.676󰀁deepmaize0.6320.7670.630TacTex0.6410.656󰀁0.722󰀁Botticelli0.575󰀁-.-0.630PackaTAC0.734󰀁0.854󰀁0.796󰀁whitebear0.500󰀁-.--.-

otheragentspurchasedthroughoutthegame,withsignificantprocurementactivity

fromdays3–219.

Someinformationabouttheprocurementstrategiesoftheotheragentsafterday0canbefoundintheirpublishedaccounts.RedAgent[KellerandDuguay2004]andPackaTAC[Dahlgren2003]bothusedvariationsofastrategybasedonmaintainingathresholdinventorylevelwithareorderpolicyifinventorylevelsbelowthethresholdweredetected.Bothusedfairlysimpleofferacceptancestrategiesthatdidnotrejectoffersonthebasisofprice.TacTex[PardoeandStone2004]hadaprocurementstrategysomewhatsimilartoDeepMaize’s.Itprojectedinventoryneedsforthenext50daysandissuedRFQstofillthoseneedsfordayswithlowexpectedprices.Offerswereacceptedifmarginalvaluesexceededthecostoftheorder(independentlyfromotheroffers).TacTexprojectsneedsandcalculatesmarginalvaluesbasedonhistoricaldata,whileDeepMaizeusesprojectionsoffuturecustomerdemandandmarketanalysis.Botticelli[Benischetal.2004]didnotconsidertheprocurementdecisionaspartoftheiroveralloptimizationapproachbecauseoftheday-0effects,andWhitebeardidnotpurchaseanycomponentsafterday0.

LookingatTableIIIweseethatDeepMaizeachievedsignificantlybetterpricesthaneveryagentexceptBotticellifromdays3–219.BotticelliandDeepMaizehadalmostidenticalperformance.Inthefirstcolumnweseethatthetopthreeplac-ingagentspaidverysimilaraveragepricesforcomponentsovertheentiregame.PackaTACpaidsignificantlyhigherprices,whileBotticelliandWhitebearpaidlowerprices(inWhitebear’scasebecausetheyonlypurchasedonday0).Interestingly,lookingonlyattheseprocurementnumbersBotticelliappearstohavethemostefficientoverallprocurementstrategy.Itpurchasedasimilartotalquantityofcom-ponentsasthetoptwoagents,andpurchasedthemforlowerprices.Thatthisagentplacedfourthoverallistestamenttothefactthataveragepricesdonottell

ACMSIGecomExchanges,Vol.4,No.3,February2004.

DeepMaizeProcurementinTAC/SCM

·

17

thefullstory;whencomponentsarriveandwhattheagentdoeswiththemalsomatter.

ThisanalysisshowsthatDeepMaizehadacompetitiveoverallprocurementpol-icy.Thesteady-statepartofthispolicywasbasedonvalue-drivenprocurementguidedbyareferenceinventorytrajectory.Itwasflexibleenoughtoexpressmanytypesofprocurementrequirements,androbustenoughtobeusedinconjunctionwithseveralinitialprocurementstrategies.Thetournamentbehaviorofthepro-curementmodulecorrespondedwelltotheintendedbehaviorrepresentedbythevaluefunction.ThisresultedinDeepMaizeachievingaveragepriceperformanceequaltoorbetterthanallotherfinalsagentswhenthesteady-statepolicywasactive.Onecaveattoconsideristhattheimportanceofday0procurementinTAC-03mayhavecausedmanyoftheotheragentdeveloperstoputlesseffortintodevelopingpoliciesforprocurementduringtherestofthegame.SincechangeswillbemadeforTAC-04toreducetheimpactofday0procurement,welookforwardtothe2004competitionasabettertestforDeepMaize’ssteady-stateprocurementpolicy.

TherearemanypossibilitiesforimprovementstoDeepMaize’sprocurementap-proach.Forinstance,someoftheparametersdefiningthereferenceinventorytra-jectory(e.g.baselinelevelandpremiums)weresetsomewhatarbitrarilyandcouldundoubtedlybeimprovedbyadditionaltuning,analysis,orlearningmethods.Ourestimatesofsuppliercapacitycouldalsobeusedmoreeffectivelytotargetsupplierswithavailablecapacityatlowprices,potentiallyimprovingofferacceptanceratesandcomponentprices.Thesesameestimatescouldalsobeusedtoimproveourprojectionsoffuturecomponentconsumptionbyidentifyingtimeswhenproductionwillbeimpossiblebecausekeycomponentsarenotavailableorareveryexpensive.Webelievethattheseandotherimprovementswillbeinterestingavenuesforfurtherresearchonvalue-drivenprocurementinfutureTAC/SCMcompetitions.

ACKNOWLEDGMENTS

WegratefullyacknowledgethehelpofmanypeoplewhomadetheTAC/SCMtour-namentpossibleincludingR.Arunachalam,J.Eriksson,N.Finne,S.Janson,andN.Sadeh.AttheUniversityofMichigan,DeepMaizewasdesignedandimplementedwiththeadditionalhelpofJoshuaEstelle,YevgeniyVorobeychik,MatthewRudary,KevinO’Malley,ThedeLoder,andShih-FenCheng.ThisworkwassupportedinpartbyNSFgrantIIS-0205435.

REFERENCES

Arunachalam,R.,Eriksson,J.,Finne,N.,Janson,S.,andSadeh,N.2003.TheTACsupplychainmanagementgame.Tech.rep.,SwedishInstituteofComputerScience.DraftVersion0.62.

Benisch,M.,Greenwald,A.,Naroditskiy,V.,andTschantz,M.2004.Astochasticprogram-mingapproachtoschedulinginTACSCM.InFifthACMConferenceonElectronicCommerce.NewYork.

Dahlgren,E.2003.PackaTAC:Aconservativetradingagent.M.S.thesis,LundUniversity.Estelle,J.,Vorobeychik,Y.,Wellman,M.P.,Singh,S.,Kiekintveld,C.,andSoni,V.2003.Strategicinteractionsinasupplychaingame.Tech.rep.,UniversityofMichigan.

Keller,P.W.andDuguay,F.-O.2004.RedAgent-winnerofTACSCM2003.SIGecomExchanges4,3.

ACMSIGecomExchanges,Vol.4,No.3,February2004.

18

·

Kiekintveldetal.

Kiekintveld,C.,Wellman,M.P.,Singh,S.,Estelle,J.,Vorobeychik,Y.,Soni,V.,andRudary,M.2004.Distributedfeedbackcontrolfordecisionmakingonsupplychains.InFourteenthInternationalConferenceonAutomatedPlanningandScheduling.Whistler,BC.Pardoe,D.andStone,P.2004.TacTex-03:Asupplychainmanagementagent.SIGecomExchanges4,3.

Sadeh,N.,Arunachalam,R.,Eriksson,J.,Finne,N.,andJanson,S.2003.TAC-03:Asupply-chaintradingcompetition.AIMagazine24,1,92–94.

Schneider,J.G.,Boyan,J.A.,andMoore,A.W.1998.Valuefunctionbasedproductionscheduling.InFifteenthInternationalConferenceonMachineLearning.Madison,WI,522–530.ReceivedJanuary2004;RevisedFebruary2004;AcceptedFebruary2004;

ACMSIGecomExchanges,Vol.4,No.3,February2004.