Asking the right question Risk and expectation in multi-agent contracting

inMulti-AgentContracting

AlexanderBabanov,JohnCollins,andMariaGiniDepartmentofComputerScienceandEngineering

UniversityofMinnesota

Author:AlexanderBabanov,DepartmentofComputerScienceandEngineering,

DepartmentofEconomics,UniversityofMinnesota,4-192EE/CSci,200UnionStSE,Minneapolis,MN55455,phone:(612)625-0265

Author:JohnCollins,DepartmentofComputerScienceandEngineering,Uni-versityofMinnesota,4-192EE/CSci,200UnionStSE,Minneapolis,MN55455

Author:MariaGini,DepartmentofComputerScienceandEngineering,University

ofMinnesota,4-192EE/CSci,200UnionStSE,Minneapolis,MN55455,phone:(612)625-5582,fax:(612)625-0572Numberofpages:32Numberoffigures:14Numberoftables:0

Runningtitle:RiskandExpectationinMulti-AgentContracting

1

AskingtheRightQuestion:RiskandExpectation

inMulti-AgentContracting

Keywords:Automatedauctions,multi-agentcontracting,expectedutility,riskestimation,optimization

Abstract

Inthispaperweareinterestedinthedecisionproblemfacedbyanagentwhenrequestingbidsforcollectionsoftaskswithcomplextimeconstraintsandinterdependencies.Inparticular,westudytheproblemofspecifyinganappropriatescheduleforthetasksintherequestforbids.Weexpectbidstorequireresourcecommitments,soweexpectdifferentsettingoftimewindowstosolicitdifferentbidsanddifferentcosts.Theagentisinterestedinsoliciting“desirable”bids,where“desirable”meansbidsthatcanbefeasiblycombinedinalowcostcombinationthatcoverstheentirecollectionoftasks.

Sincetherequestforbidshastobeissuedbeforetheagentcanseeanybids,inthisdecisionprocessthereisaprobabilityoflossaswellasaprobabilityofgain.Thisrequiresthedecisionprocesstodealwiththeriskpostureofthepersonororganizationonwhosebehalftheagentisacting.

WedescribeamodelbasedonExpectedUtilityTheory,andshowhowanagentcanattempttomaximizeitsprofitswhilemanagingitsfinancialriskexposure.Weillustratetheoperationandpropertiesofthemodel,anddiscusswhatassumptionsarerequiredforitssuccessfulintegrationinmulti-agentcontractingapplications.

2

1Introduction

E-commercetechnologyhasthepotentialtobenefitsocietybyreducingthecostofbuyingandsellingandbyopeningnewmarketopportunities.Weenvisionanauction-basedapproachtothemanagementofagileanddynamicsupply-chains,inwhichautonomous,self-interestedagentsnegotiateonbehalfoforganizationsandindividualstoorganizecoordinatedactivities.Thisisanareainwhichthepotentialpayoffisveryhigh,giventheprojectedsizeofthebusiness-to-businessandmake-to-ordere-commercemarkets.

Moreproductionprocessesarebeingoutsourcedtooutsidecontractors,makingsupplychainslongerandmoreconvoluted.Thisincreasedcomplexityiscompoundedbyincreasingcompetitivepressure,andacceleratedproductionscheduleswhichdemandtightintegrationofallprocesses.Findingpotentialsuppliersisonlyonestepintheprocessofproducinggoods.Timedependenciesamongoperationsmakeschedulingamajorfactor.Alatedeliveryofapartmightproduceacascadeofdevastatingeffects.Unfortunately,currentauction-basedsystemsdonothaveanynotionoftime.Handlingauctionsfortaskswithtimeconstraintsisbeyondthecapabilitiesofcurrente-commercesystems.

Wepresenttheresultsofastudyofhowanautonomousagentcanmaximizeitsprofitswhilepredictingandmanagingitsfinancialriskexposurewhenrequestingbidsfortaskswithcomplextimeconstraints.Weshowhowthiscanbedonebyspecifyingappropriatetimewindowsfortaskswhensolicitingbids,andbyusingreceivedbidseffectivelyinbuildingafinalworkschedule.

2MAGNET,AMulti-AgentNegotiationTestbedforContractingTaskswithTemporalandPrecedenceConstraints

ThisstudyisapartoftheMAGNET(Multi-AGentNEgotiationTestbed)researchproject[7].MAGNETagentsparticipateinfirst-price,sealed-bidcombinatorialauctionsovercollectionsoftaskswithprecedencerelationsandtimeconstraints.MAGNETpromisestoincreasetheefficiencyofcurrentmarketsbyshiftingmuchoftheburdenofmarketexploration,auctionhandling,andpreliminarydecisionanalysisfromhuman

3

decisionmakerstoanetworkofheterogeneousagents.

Wedistinguishbetweentwoagentroles,theCustomerandtheSupplier(seeFigure1).Acustomerhasasetoftaskstobeperformed,withcomplexdependenciesamongthetasks.Whenacustomerlackstheresourcestocarryoutitsowntasks,itmaysolicitresourcesfromsuppliersbypresentingaRequestforQuotes(RFQs)throughanagent-mediatedmarket.Supplieragentsmayoffertoprovidetherequestedresourcesorservices,forspecifiedprices,overspecifiedtimeperiods.Oncethecustomerreceivesbids,itevaluatesthemtoselectanoptimalsetofbidsandcreateaworkschedule.ThispaperdealswithdecisionproblemsintheBidManagercomponentoftheCustomerAgent.

Top−levelGoalCustomerAgentPlannerTaskNetworkRe−planDomainModelMarketMarketOntologyMarketStatisticsMarketSessionDomainModelSupplierAgentBidManagerCommitmentsAvailabilityBidManagerRe−bidTaskAssignmentStatisticsBidProtocolEvents andResponsesBidProtocolEvents andResponsesResourceManagerExecutionManagerFigure1:TheMAGNETarchitecture

Thisisaschematicoutlineofthemaininteractionsamongagents:

•AcustomerissuesanRFQwhichspecifiestasks,theirprecedencerelations,andatimelineforthebiddingprocess.Foreachtask,atimewindowisspecifiedgivingtheearliesttimethetaskcanstartandthelatesttimethetaskcanend.

•Supplierssubmitbids.Abidincludesasetoftasks,aprice,aportionofthepricetobepaidasanon-refundabledeposit,andestimateddurationandtimewindowdatathatreflectsupplierresourceavailabilityandconstrainthecustomer’sschedulingprocess.

4

•Thecustomerdecideswhichbidstoaccept.Eachtaskneedstobemappedtoexactlyonebid(i.e.nofreedisposal[24]),andtheconstraintsofallawardedbidsmustbesatisfiedinthefinalworkschedule.•Whenthecustomerawardsabid,itpaysadepositandspecifiestheworkschedule.•Whenthesuppliercompletesatask,thecustomerpaystheremainderoftheprice.

•Ifthesupplierfailstocompleteatask,thepriceisforfeitandthedepositmustbereturnedtothecustomer.Apenaltymayalsobeleviedfornon-performance,oraleveled-commitmentprotocol[35]maybeused.Thecustomerdecideswhethertohandlethefailurebyreplanningorrebiddingthefailedtask(s).

2.1AMotivatingExample

Asanexample,imaginethatweneedtoconstructagarage.Figure2showsthetasksneededtocompletetheconstruction.Thetasksarerepresentedinatasknetwork,wherelinksindicateprecedenceconstraints.ThefirstdecisionwearefacedwithishowtosequencethetasksintheRFQandhowmuchtimetoallocatetoeachofthem.Forinstance,wecouldreducethenumberofparalleltasks,allocatemoretimetotaskswithhighervariabilityindurationortasksforwhichthereisashortageoflaborers,orallowmoreslacktime.

2Roofing1Masonry3Plumbing4Electric5Exterior6Interior1

24

3

56tFigure2:AtasknetworkexampleandacorrespondingRFQ.

AsampleRFQisshowninFigure2.NotethatthetimewindowsintheRFQdonotneedtoobeytheprecedenceconstraints;theonlyrequirementisthattheacceptedbidsobeythem.Weassumethatthesupplierismorelikelytobid,andsubmitalower-costbid,ifitisgivenagreaterflexibilityinschedulingitsresources.Itisuptothecustomertofindabidcombinationthatformsafeasibleschedule.

5

2.2ExperiencesandObservations

Wehaveshown[6]thatthetimeconstraintsspecifiedintheRFQcanaffectthecustomer’soutcomeintwomajorways:

1.byaffectingthenumber,price,andtimewindowsofbids.Weassumethatbidswillreflectsupplierresourcecommitments,andthereforelargertimewindowswillresultinmorebidsandbetterutilizationofresources,inturnleadingtolowerprices[5].However,anRFQwithoverlappingtimewindowsmakestheprocessofwinnerdeterminationmorecomplex[5].Anotherlessobviousproblemisthateveryextrabidovertheminimumneededtocoveralltasksaddsonemorerejectedbid.Ultimately,alargepercentageofrejectionswillreducethecustomeragent’scredibility,which,afterrepeatedinteractionsinthemarket,willresultinfewerbidsand/orhighercosts.

2.byaffectingthefinancialexposureofthecustomeragent[6].Weassumenon-refundabledepositsarepaidtosecureawardedbids,andpaymentsforeachtaskaremadeasthetasksarecompleted.Thepayoffforthecustomeroccursonlyatthecompletionofallthetasks.Onceataskiscompletedinthetimeperiodspecified,thecustomerisliableforitsfullcost,regardlessofwhetherinthemeantimeothertaskshavefailed.Ifataskisnotcompletedbythesupplier,thecustomerisnotliableforitscost,butthisfailurecanruinotherpartsoftheplan.Slackinthescheduleincreasestheprobabilitythattaskswillbecompletedorthattherewillbeenoughtimetorecoverifanyfail.However,slackextendsthecompletiontimeandsoreducesthepayoff.Inmanybusinesssituations,thespeedisthekey;thevalueofthefinalpayoffmaydropoffverysteeplywithtime.

TheagentneedstoissuetheRFQbeforehavingreceivedanybid,sotheprocessofdecidinghowtoschedulethedifferenttasksandhowmuchtimetoallocatetoeachtask,involvesaprobabilityoflossaswellasaprobabilityofgain.Thisrequiresthedecisionprocesstodealwiththeriskpostureofthepersonororganizationonwhosebehalftheagentisacting.

Theagentcanuseinformationavailablefromthemarketonexpectedcosts,probabilityofcompletionoftaskswithinatimewindow,andexpectednumbersofbidderstoguideitsdecisiononhowtosequencethetasksandhowmuchtimetoallocatetoeach.

6

InthenextSection,wewillproposeaprincipledmethodforgeneratingRFQsthattakesintoaccounttheagent’sriskpostureandavailablemarketstatisticstoproduceaschedulethatoptimizestheagent’sexpectedutility.

3ExpectedUtilityApproach

InthissectionwedescribeanewapproachtotheconstructionofoptimalRFQsthatemploystheExpectedUtilityTheorytoreducethelikelihoodofreceivingunattractivebids,whilemaximizingthenumberofbidsthatarelikelytobeawarded.Thisapproachwasoriginallysuggestedinourpreviouswork[3].InthisworkweextenditandpayspecialattentiontotherelationbetweenthesizeofRFQtimewindowsandthenumberofexpectedbidsbyinvestigatingthebalancebetweenthequantityandthequalityofexpectedbids.

3.1Terminology

Atasknetwork(seeFigure2)isatuple󰀒N,≺󰀓ofasetNofindividualtasksandstrictpartialorderingonthem,suchthatforanyi,j∈N,i≺jimpliesthattaskiimmediatelyprecedestaskj.WealsouseNtodenotethenumberoftaskswhereappropriate.

Atasknetworkischaracterizedbyastarttimetsandafinishtimetf,whichdelimittheintervaloftimewhentaskscanbescheduled.Theplacementoftaskninthescheduleischaracterizedbytasknstarttime

f

tsnandtasknfinishtimetn,subjecttothefollowingconstraints:

s

ts≤tfm≤tn,

∀m∈P1(n)and

sf

tfn≤tm≤t

∀m∈S1(n)

whereP1(n)istheasetofimmediatepredecessorsofn,P1(n)={m∈N|m≺n}.S1(n)isdefinedsimilarlytobethesetofimmediatesuccessorsoftaskn.

Theprobabilityoftaskncompletionbytimet,conditionalontheultimatesuccessfulcompletionoftaskn,is

s

distributedaccordingtothecumulativedistributionfunction(CDF)Φn=Φn(tsn;t),limt→∞Φn(tn;t)=1.

7

ObservethatΦnisdefinedtobeexplicitlydependentonthestarttimetsn.Toseetherationale,considertheprobabilityofsuccessfulmaildeliveryinxdaysforpackagesthatweremailedondifferentdaysofaweek.Thereisanassociatedunconditionalprobabilityofsuccesspn∈[0,1]characterizingthepercentageoftasksthataresuccessfullycompletedgiveninfinitetime(seeFigure3).IntheempiricalsupportofworkweassumedWeibullprobabilitydistributionforΦn,howevertheformofthedistributionisnottiedinthetheory.Infact,weexpectthatthesuccessprobabilitieswouldbederivedfromtheavailablemarketinformation.

1pnpnΦn(tsn;t)tFigure3:Unconditionaldistributionforsuccessfulcompletionprobability.

Tasknbearsanassociatedcost1.Weassumethetotalcostoftasknhastwoparts:adeposit,whichispaidwhenthebidisaccepted,andacostcnwhichisduesometimeaftersuccessfulcompletionofn.Sincedepositsareassumedtobepaidupfront,theamountdoesnotchangebetweenschedulesandwecanassumewithoutlossofgeneralitythesumofdepositstobe0.

ThereisasinglefinalrewardVscheduledattheplanfinishtimetfandpaidconditionalonalltasksinNbeingsuccessfullycompletedbythattime.

Foreachcostandreward,thereisanassociatedrateofreturnqn2thatisusedtocalculatethediscountedpresentvalue(PV)forpayoffcndueattimetas

−t

PV(cn;t):=cn(1+qn).

WeassociatetherateofreturnqwiththefinalpayoffV.

weusewords“cost”and“reward”todenotesomemonetaryvalue,whilereferringthesamevalueas“payment”

or“payoff”wheneveritisscheduledatsometimet.

2Thereasonforhavingmultipleq’sisthatindividualtaskscanbefinancedfromdifferentsources,thusaffectingtasknscheduling.

1Hereafter

8

3.2ExpectedUtilityandCertaintyEquivalent

Werepresentthecustomeragent’spreferencesoverpayoffsbythevonNeumann-Morgensternutilityfunctionu[21].Wefurtherassumethattheabsoluterisk-aversioncoefficientr:=−u′′/u′ofuisconstantforanyvalueofitsargument,henceucanberepresentedasfollows:

u(x)=−exp{−rx}forr=0andu(x)=xforr=0

Itisimperativetonoteherethatwedonotcompareutilityvaluesdirectly;thecounterintuitive(i.e.de-creasinginmonetaryterms)formoftheutilityforr<0isatradeoffforsimplenotation.

Weassumethatafuturestateoftheworldcanbedescribedintermsofpotentialmoneytransfersandthecorrespondingprobabilities.Accordinglywedefinegambletobeasetofpayoff-probabilitypairsG=

󰀁

{(xi,pi)i}s.t.pi>0,∀iandipi=1.TheexpectationoftheutilityfunctionoveragambleGistheexpectedutility(EU):

Eu[G]:=

󰀂

(xi,pi)∈G

piu(xi)

Thecertaintyequivalent(CE)ofagambleGisdefinedasthesinglepayoffvaluewhoseutilitymatchestheexpectedutilityoftheentiregambleG,i.e.u(CE[G]):=Eu[G].Henceunderourassumptions

−1

CE(G)=log

r

󰀂

(xi,pi)∈G

piexp{−rxi}forr=0andCE(G)=

󰀂

(xi,pi)∈G

pixiforr=0

OurevaluationcriterionisbaseduponcomparingCEvalues,sincetheyrepresentmoneytransfersincertainandcurrentmoney.DuetothisinterpretationCEvalues,unlikeutilities,canbecomparedacrossvariousrisk-averitiesandalternativeschedules,evenbetweendifferentplans.Naturally,theagentwillnotbewillingtoacceptgambleswithnegativecertaintyequivalent,andhighervaluesofthecertaintyequivalentwillcorrespondtomoreattractivegambles.

Toillustratetheconcept,Figure4showshowthecertaintyequivalentdependsontherisk-aversityrofan

9

agent.Inthisfigureweconsideragamblethatbringstheagenteither100ornothingwithequalprobabilities.Agentswithpositivervaluesarerisk-averse;thosewithnegativervaluesarerisk-loving.Agentswithrisk-aversityclosetozero,i.e.almostrisk-neutral,haveaCEequaltothegamble’sweightedmean50.

100CE({(100,1/2),(0,1/2)})7550250−0.1r 0.1−0.0500.05Figure4:Certaintyequivalentofasimplegambleasafunctionoftherisk-aversity.

3.3CumulativeProbabilities

Tocomputethecertaintyequivalentofagambleweneedtodetermineascheduleforthetasksandcomputethepayoffprobabilitypairs.

˜n3isWeassumethatthepayoffcnfortasknisscheduledattfn,soitspresentvaluec

c˜n:=cn(1+qn)

−tfn

Wedefinetheconditionalprobabilityoftasknsuccessas

󰀅󰀄f

p˜n:=pnΦnts;tnn.

weusethetildetodistinguishvariablesthatdependonthecurrenttaskschedule,whileomittingcorresponding

indicesforthesakeofnotationalsimplicity.

3Hereafter

10

Wealsodefinetheprecursorsoftasknasasetoftasksthatfinishbeforetasknstartsinaschedule,i.e.

󰀇󰀆s˜(n):=m∈N|tfP≤tmn.

Theunconditionalprobabilitythattasknwillbecompletedsuccessfullyis

p˜c˜n×n=p

󰀃

˜(n)m∈P

p˜m.

Thatis,theprobabilityofsuccessfulcompletionofeveryprecursorandoftasknitselfareconsidered˜(n)failstobeindependentevents.Thereasonthisiscalculatedinsuchformisbecause,ifanytaskinPcompleted,thereisnoneedtoexecutetaskn.

TheprobabilityofreceivingthefinalrewardVistherefore

󰀃

n∈N

p˜=p˜n.

3.4ExampleandDiscussion

Toillustratethedefinitionsabove,let’sreturntothetasknetworkinFigure2andconsiderthesampletaskschedulesshowninFigure5.Inthisfigurethex-axisistime,they-axisshowsboththetasknumbersandthecumulativedistributionoftheunconditionalprobabilityofcompletion(comparetoFigure3).Circle

f

˜n(numbersmarkersshowstarttimestsn.Crossesindicatebothfinishtimestnandsuccessprobabilitiesp

nexttoeachpoint).Squaremarkersdenotethatthecorrespondingtaskcannotspanpastthispointduetoprecedenceconstraints.ThethickpartofeachCDFshowsthetimeallocatedtoeachtask.

Thecustomeragentneedsawayofcollectingthemarketinformationnecessarytobuildandusetheprob-abilitymodel.Theprobabilityofsuccessisrelativelyeasytoobserveinthemarket.ThisisthereasonforintroducingthecumulativeprobabilityofsuccessΦnandprobabilityofsuccesspn,insteadoftheaver-ageprojectlifespanorprobabilityoffailure.Indeed,itisrationalforthesuppliertoreportasuccessful

11

#123456020.990.960.950.980.970.999#1234560.990.960.950.980.97146810t0246810tFigure5:CEmaximizingtimeallocationsfortheplaninFigure2forr=−0.01(left)andr=0.02(right).completionimmediatelyinordertomaximizethepresentvalueofapayment.Alsoitisrationalnottoreportafailureuntilthelastpossiblemoment,duetoapossibilityofearningthepaymentbyrescheduling,outsourcing,orfixingtheprobleminsomeway.

3.5GambleCalculationAlgorithmandMaximization

GivenascheduleliketheoneshowninFigure5,weneedtocomputethepayoffprobabilityandthenmaximizetheCEforthegamble.Writinganexplicitdescriptionoftheexpectedutilityasafunctionofgamblesisoverlycomplicatedandreliesontheorderoftaskcompletions.Insteadweproposeasimplerecursivealgorithmthatcreatesthesegambles.WethenmaximizetheCEoverthespaceofallfeasibleschedulesandthecorrespondinggambles.Algorithm:G←calcGamble(T,D)

Requires:T“taskstoprocess”,D“processedtasks”Returns:G“subtreegamble”˜(m)⊂D}M←{m∈T|P

ifM=∅“it’sabranch”

n←first{M}“accordingtosomeordering”

12

T←T\\{n}G←∅

E←calcGamble(T,D)“follow...→n¯path”forall(x,p)∈E

G←G∪{(x,p×(1−p˜n)})endfor

I←calcGamble(T,D∪{n})“follow...→npath”forall(x,p)∈I

G←G∪{(x+c˜n,p×p˜n)}endfor

returnG“subtreeisprocessed”else“it’saleaf”

ifN=D“alltasksaredone”

return{(V,1)}else“sometaskfailed”

return{(0,1)}endifendif

Inthefirstcall,thealgorithmreceivesa“todo”tasklistT=Nanda“done”tasklistD=∅.Allthesubsequentcallsarerecursive.Toillustratetheideabehindthisalgorithm,werefertothepayoff-probabilitytreesinFigure6.ThesetwotreeswerebuiltforthetimeallocationsinFigure5andreflecttheprecursorrelationsforeachcase.

Consideringthemoresequentialscheduleontheright,wenotethatwithprobability1−p˜1task1fails,thecustomeragentdoesnotpayorreceiveanythingandstopstheexecution(path¯1intherighttree).With˜1theagentproceedswithtask3(path1inthetree).Inturn,task3eitherfailswithprobabilityp˜c1=pprobabilityp˜1×(1−p˜3),inwhichcasetheagentendsupstoppingtheplanandpayingatotalofc1(path1→¯3),oritiscompletedwiththecorrespondingprobabilityp˜c˜1×p˜3.Inthecasewhereboth1and33=p

13

arecompleted,theagentstartsboth2and4inparallelandbecomesliableforpayingc2andc4respectivelyeveniftheothertaskfails(paths1→3→2→¯4and1→3→¯2→4).Ifboth2and4fail,theresultingpathinthetreeis1→3→¯2→¯4andthecorrespondingpayoff-probabilitypairisframedinthefigure.

󰁢0¯33¯44󰁢c˜1c˜1+c˜4c˜1+c˜3¯55󰁢󰁢0c˜1p˜1×p˜3×(1−p˜4)×(1−p˜2)c˜1+c˜3¯55󰁢󰁢¯1󰁢¯1󰁢󰁢1¯2¯44c˜1+c˜3+c˜4c˜1+c˜3+c˜4+c˜5

1¯3¯43¯24󰁢󰁢c˜1+c˜3+c˜4c˜1+c˜3+c˜4+c˜52¯33¯44󰁢c˜1+c˜2c˜1+c˜2+c˜4c˜1+c˜2+c˜3

󰁢󰁢󰁢󰁢2¯44¯44c˜1+c˜2+c˜3󰁢¯55c˜1+...+c˜4¯66󰁢¯55c˜1+...+c˜4¯66󰁢c˜1+...+c˜5˜c˜1+...+c˜6+V

c˜1+...+c˜5˜c˜1+...+c˜6+V󰁢󰁢Figure6:Payoff-probabilitytreesforthetimeallocationsinFigure5.

󰀄󰀅

Thealgorithm’scomplexityisO2K−1×N,whereKisthemaximumnumberoftasksthatarescheduledtobeexecutedinparallel.ReducingthecomplexityofcalcGambleiscritical,sinceitwillbeexecutedintheinnerloopofanyCEmaximizationprocedure,unlesswesomehowfixprecursorrelationsand,consequently,atreestructure.IncommercialprojectstheratioK/Nislikelytobelow,sincenotmanyoftheseexhibitahighdegreeofparallelism.OurpreliminaryexperimentsallowustoconcludethattheK/Nratioislowerforrisk-averseagents(presumably,businessmen)thanforrisk-lovers(gamblers).Thesetwoconsiderationsmayreducetheneedforafasteralgorithm,thoughadditionalworktoimprovethealgorithmisplanned.

14

3.6ExperimentalResults

WehaveconductedasetofexperimentsonCEmaximizationinavarietyoftasknetworks.Someoftheresultsforourreference6–tasknetworkaresummarizedinFigure7.Inthisfigure,they-axisshows11differentrisk-aversityrsettingsandthebottomx-axisistimetintheplan.Theroundedhorizontalbarsineachof11sectionsdenotetimeallocationsforeachofsixtaskswithtask1beingontop.Sectionsr=−0.01andr=0.02correspondtoschedulesinFigure5(left)andFigure5(right)respectively.Finally,theverticalbarsshowthemaximumCEvaluesonthetopx-axisforeachrsetting.r 0.070.060.050.040.030.020.010−0.01−0.02−0.03t 012345678910050100150CE Figure7:CEmaximizingschedulesandCEvaluesfortheplaninFigure2andr∈[−0.03,0.07].Let’sexaminetherelativeplacementoftimeallocationsasafunctionofr.Forthisexamplewechosetwo

15

tasks,3and4,whichhavesimilarpositionsinthetasknetwork.Task3(blackhorizontalbars)hasalowerprobabilityofsuccessintheinfinitehorizonthantask4(whitebars),aswellasahighervarianceoftheprobabilityofsuccessdistribution.Also,thecostoftask3istwicethecostoftask4.Giventhissetup,weobservedfourdistinctcasesintheexperimentaldata:

1.Risk-lovingagentstendtoscheduletasksinparallelandlateintimeinordertomaximizethepresentvalueoftheexpecteddifferencebetweenrewardandpayoffstosuppliers.ThisconfirmstheintuitionfromFigure4–risk-loversleantowardreceivinghigh,riskypayoffsratherthanlowcertainpayoffs.2.Riskneutralandminimallyrisk-averseagentsplaceriskytask3firsttomakesurethatthefailuredoesn’thappentoofarintotheproject.Note,thattheystillkeeptask2inparallel,soincase2fails,theyareliableforpayingthesupplieroftask4onsuccess.Onecanconsiderthoseagentsassomewhatoptimistic.

3.Moderatelyrisk-averseagentstrytododgethesituationabovebyschedulingtask3aftertask2isfinished.Theseagentsarewillingtoaccepttheplan,buttheirexpectationsarequitepessimistic.4.Highlyrisk-averseagentsshrinktask1intervaltozero,thus“cheating”toavoidcoveringanycosts.Onemayinterpretthisasawayofsignalingarefusaltoaccepttheplan.Indeed,theassignmentofzerodurationtoaprecursor-lesstaskensureszeroprobabilityofcompletionand,hence,zeroCEeveninthecaseswhereanynon-degenerateschedulehasnegativeCEvalue.

4GenerationofRationalRFQ

IntheprevioussectionswehaveshownawayofgeneratingaCEmaximizingscheduleoftaskexecution,whichwehereafterreferasthereasonableschedule.Forachosenrisk-aversityvalueandknownmarketstatistics,thereasonablescheduleensuresthehighestexpectedqualityofthebidsthatsatisfyit.Byquality,weassumesomefunctionoftheexpectationsoverthecost,theprobabilityofsuccessfulcompletion,andtheprofitabilityoftheincomingbidsintheirfeasiblecombinationswithotherbids.

Thereasonableschedule,however,cannotserveasarationalRFQ,sinceitisunlikelythatbidswillbe

16

availabletocoverpreciselythesameintervalsasmandatedbytheCEmaximizingschedule.InordertoconstructaviableRFQusingthereasonablescheduleasabasis,thecustomeragentmightchoosetoloweritsexpectationsofthebidqualitytosomelevelbywideningtheRFQtimewindowsaroundthetimewindowsinthereasonableschedule,thusincreasing4theexpectednumberofincomingbids.InthissectionwediscusscriteriathatallowforrationalizingtheselectionamongallsuchRFQs.

Weapproachtheindividuallyrational(i.e.agent-dependent)RFQgenerationasfollows:

1.MeasurethesensitivityoftheexpectedbidqualitytodeviationsfromtheCEmaximizingschedule.2.DerivetherelationshipbetweenthequalityofincomingbidsandthesizeofRFQtimewindows.3.Choosarationalquality-quantitycombination.

Inaddition,wesearchforasolutionconceptthatgeneratesviableRFQsandiscomprehensibletoahumanuserofthesystem.

4.1CESensitivitytoScheduleChanges

WeproposemeasuringthesensitivityofCEbyinvestigatinghowCEvalueschangewithvariationsofasingletasknstarttimetsninthereasonableschedule.Forthesakeofbrevitytheresultingdependencyof

sCEvaluesisdenotedbyCE(tsn).Figure8showsCE(tn),n=1...6forour6-tasksampleproblemfor

r=−0.01andr=0.02respectively.Inthefigure,they-axisofeachhorizontalstripenrepresentsthe

spercentageofthemaximumCEvalueastsnvaries,thex-axisrepresentstn,andthehorizontallineswith

circleandcrossendsshowthecorrespondingreasonableschedules.

Thetasks1,3and5intherightgrapharerelativelyrestrictivetothestarttimesofthebidsthatcanbebundledwiththereasonablebidswithoutconsiderablyimpairingtheresultingbundle’svalue.However,thefactthatthetask2intherightgraphismoreflexibledoesnotguaranteethatitwillattractahighernumberofbids,sincethelatterdependsbothonthesizeofthecorrespondingtimewindowandonthemarketpropertiesofthetask:resourceavailability,numberofprospectivebidders,seasonalchanges,etc.

leasttosomeextent,—thereisafairchancethatthenumberoftheincomingbidswillceasetoincreasewheneverRFQtimewindowsbecometoolargetoinspireconfidenceonthepartofsuppliers.

4At

17

#12345602468#12345602468t10t10Figure8:CE(tsn)graphsforthecorrespondingreasonableschedulesinFigure5.

WeassertthatforthepurposeofcreatingarationalRFQ,itisadmissibletochoosetimewindowsbasedonthesensitivityofCEtodeviationsofasingletimeconstraintfromthereasonableschedule.TherationaleisthattherelationsbetweentasksarealreadyencapsulatedinthecalculationsofCE,sothechangeofoneconstraintwillapproximatethereschedulingofseveralrelatedtasksintheneighborhoodofthereasonableschedule.

4.2Qualityvs.Quantity

s

Observethatthetimewindowforthetaskn,{tsn|CE(tn)≥x},growsasthelowestexpectedCEvalue,x,

decreases.Therelationbetweenthesetwovariablesforthetasks3and4ofthetestproblemisshowninFigure9.ThecorrespondingrelationbetweenthelowestexpectedCEvalueandtheexpectednumberofbidsasafunctionofthewindowsizeisshowninFigure10.Intherightgraphweassumed,forthesakeofexample,thatthesupplyoftask3inthemarketishigherthanofthetask4,hencethedifferenceinrelativepositionsoftask3andtask4graphsinthetwofigures.

ThegraphinFigure10isanexampleoftherelationbetweenthequalityandthequantityofbidswearesearchingfor.Indeed,theonlyindependentvariableinthisgraphistsn.ThequantityofbidsdependsonthesizeandpositionsofRFQtimewindowsthat,inturn,dependonthedecisionaboutthelowestacceptable

18

100806040200% of max CEtask 3task 410080604020t0% of max CEtask 3task 4E#012345601234Figure9:RelationshipbetweentheRFQwindowsizeFigure10:Relationshipbetweentheexpectednumber(showninunitsoftimeonx-axis)andthelowestad-ofbids(shownonx-axis)andthelowestadmissibleper-missiblepercentageofthemaximumCEvalue.centageofthemaximumCEvalue.CEvalue.ThequalityofbidsisafunctionoftheRFQchoiceandthepropertiesoftheplan.Finally,itisexpectedthatthecustomeragentwillpreferapointonthegraphtoanypointbelowandtotheleftofit,hencethebestchoiceshouldlieonthegraph.

4.3RationalQuality-QuantityChoiceandRFQ

WeillustratethedecisionprocessofthecustomeragentinFigure11,wherethecustomeragent’spreferencesoverquality-quantitycombinationsarerepresentedbyafamilyofindifferencecurves,andthegraphofunderlyingquality-quantityrelationshipisasderivedintheprevioussection.Eachindifferencecurveshowsquality-quantitypairsthatareequivalentfromtheagent’spointofview.Inparticular,pointsA,BandCareconsideredtobeequallyattractive.TheintuitionisthatalthoughinpointAagentreceivesmuchsmallernumberofbidstocomparewithCandisexposedtoahigherriskofnotcoveringsometasks,thisisoffsetbyapositiveeffectofalowerpercentageofbidrejectionsonagent’sreputation.Alsothewinnerdeterminationproblemisexponentiallyeasiertosolve[5]forthelowerexpectednumberofbidsinpointA.Forallpointsbelowthemaximumexpectedqualityline(horizontaldashedlineinthegraph)agent’spref-erencesincreaseinthedirectionofpointM.ThusacurvethroughpointDispreferredoveronethrough

19

pointCandevenmoresooveronethroughpointE.Therationalchoicebelongstotheintersectionofthequality-quantitygraphandthehighestindifferencecurve(pointBinthegraph).

expected quality of bidsindifference curvesABMDCEdirection of increasingpreferencesexpected quantity of bidsFigure11:Quality-quantitygraphwiththreeindifferencecurves.

Aftertherationalchoiceofthequality-quantitycombinationsforalltasksintheplanisrevealed,weproceed

ls

withconstructingtheRFQtimewindows.Thechoiceofearlystarttimetesnandlatestarttimetnare

determinedbythevalueofthereciprocaloftheCE(tsn)attheminimumadmissibleCEchoiceforthetask

lsn.Thelatefinishtimetlfnischosentobeatthereasonabletimewindowlengthdistancefromtn.Figure12

showstwosampleRFQsforthegaragebuildingexample.Inthefiguregraybarsshowstarttimeintervals,

lslf[tesn,tn],theendsofwhitebarscorrespondtolatefinishtimes,tnandthehorizontallineswithcircleand

crossendsshowthecorrespondingreasonableschedules.#12345602468#12345602468t10t10Figure12:RationalRFQsforthecorrespondingreasonableschedulesinFigure5andthefollowingvectorofthemaximumCEpercentages:(80%,95%,50%,70%,50%,90%).

OurchoiceoftheRFQmaynotbeoptimalinthequantitativesense,howeveritisindividuallyrationalfor

20

thecustomeragent,itisalsofasttocompute,andarguablyeasytograspforahumanuserofthesystem.ItshouldbeemphasizedherethatthechoiceoftheRFQisbasedontheuncertainmarketinformation,henceanyquantitatively“optimal”solutionisitselfacompromise.

5OpenIssuesandFurtherResearch

InthissectionweoutlinetwomajorissuesthatarisewhenweemploytheexpectedutilityapproachtogeneraterationalRFQs.ThefirstissueconcernstheCEmaximizationinthedomainwithtemporalandprecedenceconstraints.ThesecondissueistheassessmentoftheEUapproachand,ultimately,theMAGNETsystemitselfintheabsenceofthereal-worlddataforthedomainofinterest.

5.1MultipleLocalMaxima

OneofthemostimportantissuesrelatedtotheCEmaximizationisthepresenceofmultiplelocalmaximaofCEevenincaseswheretasknetworksarefairlysimple.Wearguethatthispropertyispartiallyduetotherelativepositioningofthetasksoffthecriticalpath.Anytwotasksthatarenotorderedbytheprecedenceconstraintscanbescheduledinthreeways:parallelandtwosequential.Schedulingtasksinparallelincreasestheprobabilityofsuccessfulcompletion,whilesequentialschedulingminimizesoverallpayments,incaseoneofthetasksfails.Incaseswhereextraslackallowsforsequentialscheduling,itturnsoutthatparallelandsequentialpositioningsoftwoindependentindividualtasksleadtosimilarresultingCEvalues.

Toillustratetheissue,weconstructedasampletasknetworkwithtwoparalleltasks.Task1hasahighervarianceofcompletiontimeprobabilityandlowerprobabilityofsuccessthantask2,everythingelseisthesame.TheresultinggraphofCEisshowninFigure13.Thereare3localmaximawithpositiveCEvaluesinthisfigure:oneintheleftsidethatcorrespondstothetasktwobeingscheduledfirstinsequentialorder,anotherontherightsidecorrespondingtothetaskonebeingfirst,andyetanotheroneinthefurthermostcornerofthegraphrepresentingbothtasksbeingscheduledattime0andexecutedinparallel.Thenumberoflocalmaximagrowsconsiderablywiththenumberofthetasksthatarenotrestrictedbytheprecedence

21

relationship.

CE2015105005task 2 start time101005task 1 start timeFigure13:Localmaximafortwoparalleltasks.

5.1.1DomainandAlgorithmProperties

Thefollowinglistshowsthepropertiesofthedomainthatinfluencethesearchalgorithmdesign:•localmaximaareduetodifferentschedulingorderoftasksoffthecriticalpath;•groupsoflocalmaximahavesimilarCEvalues;

•anRFQbasedontheglobalmaximumcanbeoverlyrestrictive.

Thepropertiesofthedomainframethepropertiesofthesearchalgorithmthatwedesigntofitthisdomain.Namely,thesearchalgorithmmustbeabletotestdifferentorderingsoftasks,itshouldknowhowtoexploregroupsofsimilarlocalmaximaand,wheneverpossible,itshouldprovidealternativescheduleswithCEvaluesclosetotheglobalmaximum.

WeproposeasearchalgorithmbasedontheideasoftheSimulatedAnnealing[27]andGeneticAlgo-rithms[10].Thealgorithmwillcombinethestochastictemperature-drivennatureoftheSimulatedAnneal-ingwiththesimultaneoussearchspaceexplorationoftheGeneticAlgorithms.Inthissectionwedescribetheproposedalgorithminmoredetailsandexplaintherationaleofitsdesign.

22

5.1.2SearchAlgorithm

Theproposedsearchalgorithmexploresseveralalternativeschedulesinparallel.Theinitialsetofalternativescanbegeneratedinmanyways:randomgeneration,hill-climbingfromrandomschedule,CPM,etc.Theexecutionofthealgorithmproceedsinstepsbyrandomlyapplyingoneofthesixtransformationrulestoeachalternativeschedule.Theprobabilitiesofchoosingsomerulecanbeadjustedtoadjustalgorithm’sbehaviorinawiderange.

Figure14illustratesthealgorithmforthecaseofthreepairwiseindependenttasks.Inthisfigurecolumnsrepresentthreeconsequitivestatesofthealgorithm,eachcolumnlistsseveralalternativeschedules.Arrowsandlettersnexttothemdenotevarioustransformationsfromthefollowinglist:

1DERS5GSII92610371148Figure14:Twostepsofthesearchalgorithmexecution.

Distortionaltersstartandfinishtimesofoneorseveraltasksaswellasadjuststimewindowsofallrelated

taskstomaintainprecedenceconstraints(1→5inFigure14).DistortionmimicsthebasicstepoftheSAalgorithmincontinuous2N–dimentionalspaceoftaskstartandfinishtimes.

Gradientfollowingisoneormorestepsofagenericnumericalmaximizationmethod(5→9).Thisstep

isverycomputationalyintensive,asitrequiresmanycallstocalcGamblealgorithmintheprocessofcalculatingnumericalderivatives.Byvaryingrelativeprobabilitiesofthedistortionandgradientfollowingwemaychoosestochasticpropertiesoftheproposedapproach.

23

Shufflingchangesrelativeschedulingoftwoormoretaskswhereveritispermittedbytheprecedence

constraints.Shufflingcanswitchorderingoftasks(6→10),changesequentialorderingtoparallelorrescheduleparalleltaskstobeexecutedsequentially(4→8).ThemajorroleofshufflingistoexplorelocalmaximathathavesimilarCEvaluesduetodifferentschedulingoftasksoffthecriticalpath.Explosionaddsacopyofthesubjectscheduletothelistofalternatives(2→6,7).Explosioncompliments

shufflingbyallowingforsimultaneousexplorationofthegroupsofsimilarschedules.Wemaychoosetodecreasetherateofexplosionswiththeannealingtemperaturetofocusonimprovingthecurrentsetofsolutionafterthesearchspacewasexploredtoextent.

Implosionmergestwosimilar5schedulesinone.Implosionhelpsreducingcomputationalexpensesfrom

crowdingseveralalternativeschedulesaroundonemaximum(7,8→11).Therateofimplosionswillchangeintheoppositedirectiontotherateofexplosions.

Removaleliminatesalternativesthatdonotscorewellrelativetoothers(3→∅).Thistransformation

takescareoftheschedulesthatarestuckinlocalmaximawithlowCEvalues.Therateofremovalsgrowsastheannealingtemperaturedecreases.

EachofthefirstfivetransformationsistestedagainstSAtemperaturerulewheneveritleadstoadecreaseintheCEvalue.Incaseitisdiscarded,othertransformationsarechosenatrandomandapplieduntiloneofthemincreasesCEorpassesthetemperaturerule.

Theprobabilitiesoftransformationsaswellasdetailsoftheproposedsearchalgorithm’spropertiesaresubjecttofurtherresearch.ItisreasonabletobelievethoughthatthecomprehensivestudyoftheRFQgenerationmechanismisonlypossibleinthedynamicmarketenvironment.Inthenextsectionweoutlinetheapproachtothelarge-scaletestingoftheMAGNETsystemthatwepresentlyresearchandthatwillprovideuswiththenecessarydata.

5Similarity

isafunctionthedistancebetweentwoschedulesasbetweentwopointsinthe2N-dimensionaltimespace.

24

5.2EvolutionaryFrameworkforLarge-scaleTesting

WeplantodevoteeffortstothoroughlytestthesuggestedCE-basedapproachoftherationalRFQgeneration.Inparticular,weareinterestedintestinghowwellindividualagentsinteractinapopulatedmarket.Themajorgoalsofthispartofthestudywouldbe:

•providethestatisticaldatanecessaryfortheevaluationofthetheoreticalassumptionsandderivations;•facilitatetheunderstandingofthenuancesoftheCE-basedRFQgenerationandsuggestimprovementstothetheoryandimplementation;

•studytherelativeperformanceofagentsinasimulatedmarket,developinganunderstandingofthepropertiesofautomatedandmixed-initiativecombinatorialauction-basedtradingsocieties.

Themostcompellingapproachwouldbetogatherarichsetofstatisticaldatafromacommercedomain.Thathasnotproventobefeasible,fortworeasons.First,fewindustrialorganizationsaresufficientlyopentoexposethetypeofdatayouwouldneedtodothat,andwewouldneeddatafrommultipleorganizationsinasinglemarket.Second,dataisgatheredtoserveapurpose,andourexperiencetellsusthatwhenyouattempttoapplyexistingdatatoanewpurpose,itfrequentlyturnsouttobefullofinconsistenciesandmethodologicalproblems.

Inlieuofusingrealindustrydata,wearedesigningalarge-scaletestsuiteatopanabstractdomainwithcontrollablestatistics,basedontheevolutionaryapproachtoeconomicsimulation.EvolutionaryframeworkshavebeenusedextensivelyinEconomics[23,29,39].TheframeworkwillallowustotunethemarketbytweakingthefrequencyofissuingRFQsandwillallowforthedynamicintroductionofnewsupplierstrategies,withoutimposinganyassumptionsonthenatureofstrategies.Wewilllaterextendtheframeworktosupporttradegamestobeplayedwithhumansubjects.Thiswillbeatoolspeciallyusefulforteaching,asatooltoexplorestrategicbehaviorsandtostudytheemergenceofcooperation[1,2].

Wesuggestdetailedreasoningbehindourchoiceoftheevolutionaryapproachanddescribeexperimentalresultsfromapilottradingagentsocietymodelinourrelatedresearch[4].

25

6RelatedWork

ExpectedUtilityTheory[26]isamaturefieldofEconomicsthathasattractedmanysupportiveaswellascriticalstudies,boththeoretical[19,20]andempirical[16,37].Webelievethatexpectedutilitywillplayanincreasingroleinautomatedauctions,sinceitprovidesapracticalwayofdescribingriskestimationsandtemporalpreferences.

Despitetheabundanceofworkinauctions[22],limitedattentionhasbeendevotedtoauctionsovertaskswithcomplextimeconstraintsandinterdependencies.In[25],amethodisproposedtoauctionasharedtracklinefortrainscheduling.Theproblemisformulatedwithmixedintegerprogramming,withmanydomain-specificoptimizations.Bidsareexpressedbyspecifyingapricetoenteralineandatimewindow.Timeslotsareusedin[41],whereaprotocolfordecentralizedschedulingisproposed.Thestudyislimitedtoschedulingasingleresource.MAGNETagentsdealwithmultipleresources.

Mostworkinsupply-chainmanagementislimitedtohierarchicalmodelingofthedecisionmakingprocess,whichisinadequatefordistributedsupply-chains,whereeachorganizationisself-interested,notcooperative.Walshetal[40]proposeaprotocolforcombinatorialauctionsforsupplychainformation,usingagame-theoreticalperspective.Theyallowcomplextasknetworks,butdonotincludetimeconstraints.MAGNETagentshavealsotoensuretheschedulingfeasibilityofthebidstheyaccept,andmustevaluateriskaswell.AgentsinMASCOT[31]coordinateschedulingwiththeuser,butthereisnoexplicitnotionofpaymentsorcontracts,andthecriteriaforaccepting/rejectingabidarenotexplicitlystated.Theirmajorobjectiveistoshowpoliciesthatoptimizescheduleslocally[17].Ourobjectiveistooptimizethecustomer’sutility.Differentheuristicsforschedulingareproposedin[9].Thestrategiesareintendedfosupplieragentsthataretryingtoadjusttheirschedulestowinnewawards.Intheworkpresentedhere,weareconcernedwiththeschedulingthatcustomersneedtodobeforerequestingbids.

InMAGNETagentsinteractwitheachotherthroughamarket.Themarketinfrastructureprovidesacommonvocabulary,collectsstatisticalinformationthathelpsagentsestimatecosts,schedules,andrisks,andactsasatrustedintermediaryduringthenegotiationprocess.Themarketactsalsoasamatchmaker[38],

26

allowingustoignoretheissueofhowagentswillfindeachother.Forasurveyontheuseofintelligentagentsinmanufacturingsee[36].

Thedeterminationofwinnersofcombinatorialauctions[30]ishard.Dynamicprogramming[30]workswellforsmallsetsofbids,butdoesnotscaleandimposessignificantrestrictionsonthebids.AlgorithmssuchasCABOB[34],Bidtree[33]andCASS[11]reducethesearchcomplexity.Reevesetal[28]useauctionmechanismsto”fillintheblanks”inprototypedeclarativecontractsthatarespecifiedinalanguagebasedonCourteousLogicProgramming[13].Theseauctionssupportbiddingonmanyattributesotherthanprice,buttheproblemofcombiningcombinatorialbidswithsideconstraintsisnotaddressed.

Combinatorialauctionsarebecominganimportantmechanismnotjustforagent-mediatedelectroniccom-merce[14,42,32]butalsoforallocationoftaskstocooperativeagents(see,forinstance,[15,8]).

In[15]combinatorialauctionsareusedfortheinitialcommitmentdecisionproblem,whichistheproblemanagenthastosolvewhendecidingwhethertojoinaproposedcollaboration.Theiragentshaveprecedenceandhardtemporalconstraints.However,toreducesearcheffort,theyusedomain-specificroles,ashorthandnotationforcollectionsoftasks.Intheirformulation,eachtasktypecanbeassociatedwithonlyasinglerole.MAGNETagentsareself-interested,andtherearenolimitstothetypesoftaskstheycandecidetodo.In[12]schedulingdecisionsaremadenotbytheagents,butinsteadbyacentralauthority.Thecentralauthorityhasinsighttothestatesandschedulesofparticipatingagents,andagentsrelyontheauthorityforsupportingtheirdecisions.

Leyton-Brownetal[18]suggestawayofconstructingauniversaltestsuiteforwinnerdeterminationalgo-rithmsincombinatorialauctions.Theirworkdoesnotincludecaseswithprecedenceandtimeconstraintsand,thus,isnotdirectlyapplicabletotheMAGNETframework.Itneverthelessprovideswell-understoodtestcasesforcomparingtheperformanceofalgorithms.

27

7Conclusions

Auctionmechanismsareaneffectiveapproachtonegotiationamonggroupsofself-interestedeconomicagents.Weareparticularlyinterestedinsituationswhereagentsneedtonegotiateovermultiplefactors,includingnotonlyprice,buttaskcombinationsandtemporalfactorsaswell.

Wehaveshownhowanagentcanuseinformationabouttheriskpostureofitsprincipal,alongwithmarketstatistics,toformulateRequestsforQuotesthatoptimizethetradeoffbetweenriskandvalue,andincreasethequalityofthebidsreceived.Thisrequiresdecidinghowtosequencetasksandhowmuchtimetoallocatetoeachofthem.Bidsclosesttothespecifiedtimewindowsarethemostpreferredrisk-payoffcombinations.TheworkdescribedhereisapartofalargereffortattheUniversityofMinnesotathataimstostudyhowautonomousorsemi-autonomousagentscanbeusedincomplexcommerce-orienteddomains.

Acknowledgments

PartialsupportforthisresearchisgratefullyacknowledgedfromtheNationalScienceFoundationunderawardNSF/IIS-0084202.

References

[1]R.M.Axelrod.Theevolutionofcooperation.BasicBooks,1984.

[2]RobertAxelrod.Thecomplexityofcooperation.PrincetonUniversityPress,1997.

[3]AlexanderBabanov,JohnCollins,andMariaGini.Riskandexpectationsina-prioritimeallocation

inmulti-agentcontracting.InProc.oftheFirstInt’lConf.onAutonomousAgentsandMulti-AgentSystems,volume1,pages53–60,Bologna,Italy,July2002.

28

[4]AlexanderBabanov,WolfgangKetter,andMariaGini.Anevolutionaryframeworkforlarge-scale

experimentationinmulti-agentsystems.InTowardanApplicationScience:MASProblemSpacesandTheirImplicationstoAchievingGloballyCoherentBehavior,Bologna,Italy,July2002.

[5]JohnCollins.SolvingCombinatorialAuctionswithTemporalConstraintsinEconomicAgents.PhD

thesis,UniversityofMinnesota,June2002.

[6]JohnCollins,CoreyBilot,MariaGini,andBamshadMobasher.Decisionprocessesinagent-based

automatedcontracting.IEEEInternetComputing,pages61–72,March2001.

[7]JohnCollins,WolfgangKetter,andMariaGini.Amulti-agentnegotiationtestbedforcontractingtasks

withtemporalandprecedenceconstraints.Int’lJournalofElectronicCommerce,7(1):35–57,2002.[8]M.B.DiasandA.Stentz.Afreemarketarchitecturefordistributedcontrolofamultirobotsystem.In

SixthInt’lConf.onIntelligentAutonomousSystems,pages115–122,Venice,Italy,July2000.[9]ParthaSarathiDutta,SandipSen,andRajatishMukherjee.Schedulingtobecompetitiveinsupply

chains.InIJCAIworkshoponE-BusinessandtheIntelligentWeb,August2001.

[10]StephanieForrest.Geneticalgorithms:Principlesofnaturalselectionappliedtocomputation.Science,

261:872–878,1993.

[11]YuzoFujishima,KevinLeyton-Brown,andYoavShoham.Tamingthecomputationalcomplexityof

combinatorialauctions:Optimalandapproximateapproaches.InProc.ofthe16thJointConf.onArtificialIntelligence,1999.

[12]AlyssaGlassandBarbaraJ.Grosz.Sociallyconsciousdecision-making.InProc.oftheFourthInt’l

Conf.onAutonomousAgents,pages217–224,June2000.

[13]B.N.Grosof,Y.Labrou,andH.Y.Chan.Adeclarativeapproachtobusinessrulesincontracts:

CourteouslogicprogramsinXML.InProc.ofACMConfonElectronicCommerce(EC’99),pages68–77.ACM,1999.

29

[14]RobertH.Guttman,AlexandrosG.Moukas,andPattieMaes.Agent-mediatedelectroniccommerce:a

survey.KnowledgeEngineeringReview,13(2):143–152,June1998.

[15]LukeHunsbergerandBarbaraJ.Grosz.Acombinatorialauctionforcollaborativeplanning.InProc.

of4thInt’lConfonMulti-AgentSystems,pages151–158,Boston,MA,2000.IEEEComputerSocietyPress.

[16]BrunoJullienandBernardSalani´e.Estimatingpreferencesunderrisk:Thecaseofracetrackbettors.

TheJournalofPoliticalEconomy,108(3):503–530,June2000.

[17]DagKjenstad.CoordinatedSupplyChainScheduling.PhDthesis,DeptofProductionandQuality

Engineering,NorvegianUniversityofScienceandTechnology,Trondheim,Norway,1998.

[18]KevinLeyton-Brown,MarkPearson,andYoavShoham.Towardsauniversaltestsuiteforcombinatorial

auctionalgorithms.InProc.ofACMConfonElectronicCommerce(EC’00),pages66–76,Minneapolis,MN,October2000.

[19]MarkJ.Machina.Choiceunderuncertainty:Problemssolvedandunsolved.TheJournalofEconomic

Perspectives,1(1):121–154,1987.

[20]MarkJ.Machina.Dynamicconsistencyandnon-expectedutilitymodelsofchoiceunderuncertainty.

TheJournalofEconomicLiterature,27(4):1622–1668,December1989.

[21]AndreuMas-Colell,MichaelD.Whinston,andJerryR.Green.MicroeconomicTheory.OxfordUniver-sityPress,1995.

[22]R.McAfeeandP.J.McMillan.Auctionsandbidding.JournalofEconomicLiterature,25:699–738,

1987.

[23]RichardR.Nelson.Recentevolutionarytheorizingabouteconomicchange.JournalofEconomic

Literature,33(1):48–90,March1995.

[24]NoamNisan.Biddingandallocationincombinatorialauctions.In1999NWUMicroeconomicsWork-shop,1999.

30

[25]DavidC.ParkesandLyleH.Ungar.Anauction-basedmethodfordecentralizedtrainscheduling.In

Proc.oftheFifthInt’lConf.onAutonomousAgents,pages43–50,Montreal,Quebec,May2001.ACMPress.

[26]JohnW.Pratt.Riskaversioninthesmallandinthelarge.Econometrica,32:122–136,1964.

[27]ColinR.Reeves.ModernHeuristicTechniquesforCombinatorialProblems.JohnWiley&Sons,New

York,NY,1993.

[28]DanielM.Reeves,MichaelP.Wellman,andBenjaminN.Grosof.Automatednegotiationfromdeclar-ativecontractdescriptions.InProc.oftheFifthInt’lConf.onAutonomousAgents,pages51–58,Montreal,Quebec,May2001.ACMPress.

[29]DavidRode.Marketefficiency,decisionprocesses,andevolutionarygames.DepartmentofSocialand

DecisionSciences,CarnegieMellonUniversity,March1997.

[30]MichaelH.Rothkopf,AlexanderPeke˘c,andRonaldM.Harstad.Computationallymanageablecombi-natorialauctions.ManagementScience,44(8):1131–1147,1998.

[31]NormanM.Sadeh,DavidW.Hildum,DagKjenstad,andAllenTseng.MASCOT:anagent-based

architectureforcoordinatedmixed-initiativesupplychainplanningandscheduling.InWorkshoponAgent-BasedDecisionSupportinManagingtheInternet-EnabledSupply-Chain,atAgents’99,pages133–138,1999.

[32]TuomasSandholm.Analgorithmforwinnerdeterminationincombinatorialauctions.InProc.ofthe

16thJointConf.onArtificialIntelligence,pages524–547,1999.

[33]TuomasSandholm.Approachestowinnerdeterminationincombinatorialauctions.DecisionSupport

Systems,28(1-2):165–176,2000.

[34]TuomasSandholm,SubhashSuri,AndrewGilpin,andDavidLevine.CABOB:Afastoptimalalgorithm

forcombinatorialauctions.InProc.ofthe17thJointConf.onArtificialIntelligence,Seattle,WA,USA,August2001.

31

[35]TuomasW.Sandholm.NegotiationAmongSelf-InterestedComputationallyLimitedAgents.PhDthesis,

DepartmentofComputerScience,UniversityofMassachusettsatAmherst,1996.

[36]W.ShenandD.H.Norrie.Agent-basedsystemsforintelligentmanufacturing:Astate-of-the-artsurvey.

KnowledgeandInformationSystems,1999.

[37]V.KerrySmithandWilliamH.Desvousges.Anempiricalanalysisoftheeconomicvalueofriskchanges.

TheJournalofPoliticalEconomy,95(1):89–114,February1987.

[38]KatiaSycara,KeithDecker,andMikeWilliamson.Middle-agentsfortheInternet.InProc.ofthe15th

JointConf.onArtificialIntelligence,pages578–583,1997.

[39]LeighTesfatsion.Agent-basedcomputationaleconomics:Growingeconomiesfromthebottomup.ISU

EconomicsWorkingPaperNo.1,DepartmentofEconomics,IowaStateUniversity,December2001.[40]WilliamE.Walsh,MichaelWellman,andFredrikYgge.Combinatorialauctionsforsupplychainfor-mation.InProc.ofACMConfonElectronicCommerce(EC’00),October2000.

[41]MichaelP.Wellman,WilliamE.Walsh,PeterR.Wurman,andJeffreyK.MacKie-Mason.Auction

protocolsfordecentralizedscheduling.GamesandEconomicBehavior,35:271–303,2001.

[42]PeterR.Wurman,MichaelP.Wellman,andWilliamE.Walsh.TheMichiganInternetAuctionBot:

Aconfigurableauctionserverforhumanandsoftwareagents.InSecondInt’lConf.onAutonomousAgents,pages301–308,May1998.

32