Designing bidding strategies for trading agents in electronic auctions

EduardGim´enez-Funes

Llu´ısGodoJuanA.Rodr´ıguez-Aguilar

PereGarcia-Calv´es

ArtificialIntelligenceResearchInstitute,IIIA

08193Bellaterra,Barcelona,Spainduard,godo,jar,pere@iiia.csic.es

Abstract

Auction-basedelectroniccommerceisanincreasinglyinterestingdomainfordevelopingtradingagents.Inthispaperwepresentourfirstcontributionstowardsthecon-structionofsuchagentsbyintroducingbothaformalandamorepragmaticalapproachforthedesignofbiddingstrate-giesthatprovidebuyeragentswithusefulheuristicguide-linestoparticipateinauction-basedtournaments.Ontheonehand,ourformalviewreliesonpossibilistic-basedde-cisiontheoryasthemeansofhandlingpossibilisticun-certaintyontheconsequencesofactionsduetothelackofknowledgeabouttheotheragents’behaviour.Ontheotherhand,forpracticalreasonswealsoproposeatwo-foldmethodfordecisionmakingthatdoesnotrequiretheevaluationofthewholesetofalternativeactions.Thisap-proachutilizesglobal(market-centered)probabilisticinfor-mationinafirstdecisionstepwhichissubsequentlyre-finedbyaseconddecisionstepbasedontheindividual(rival-centered)possibilisticinformationinducedfromthememoryofcasescomposingthehistoryoftournaments.Inthisway,theresultingbiddingstrategybalancestheagent’sshort-termbenefits,relatedtotheprobabilisticinformation,withitslong-termbenefits,relatedtothepossibilisticinfor-mation.

1.Introduction

OnlineauctionssuchasAuctionline,Onsale,InterAUC-TION,eBayandmanyothershaveproliferatedovertheIn-ternetaswell-establishedmechanismsformulti-partynego-tiation.Asamatteroffact,auction-basedelectroniccom-merceappearstobeanareawheretheWebisprovingtobebetterthantraditionalalternativesduemainlytoitshighlyinteractivenature,theimplicationofmanytraders—insteadofaconventionalsale’ssinglebuyerandseller—,andthefactthatonlineauctionsdosignificantlyreducecosts.Asamajorbenefitofdynamicallynegotiatingapricethrough

auctions,thetaskofdeterminingthevalueofagoodistransferredfromthemerchanttothemarket,leadingtoafairallocationoflimitedresources(tothosewhovaluethemmost).Thisisthereasonwhyauctionsarenotonlyem-ployedinonlineretail,butalsoasthekeyelementforbuild-ingsolutionstoresourceallocationproblems(f.i.energymanagement[20],climatecontrol[8],flowproblems[19]).Hence,auctionsmustberegardedasanattractivedomainfordevelopingagents.

Nonetheless,designing,building,andtuningtradingagentsbeforelettingthemlooseinwildlycompetitivesce-narioslikeelectronicauctionsinhabitedby(bothhumanandsoftware)experttradershappenstobeanarduoustask.ThisfactmotivatedtheconstructionofFM97.6,atest-bedforelectronicauctions[14]thatintendstoprovidesupporttoagentdevelopersinsuchachallenge.FM97.6permitsthedefinition,activation,andevaluationofexperimental

whichde-game-liketradingscenarioscalled

finestandardizedconditionsunderwhichagentscompeteformaximizingtheirbenefits.

Tradingwithinanauctionhousedemandsfrombuyerstodecideonanappropriatepriceonwhichtobid,andfromsellers,essentiallyonlytochooseamomentwhentosub-mittheirgoods.Butthosedecisions—ifrational—shouldprofitfromwhateverinformationmaybeavailableinthemarket:participatingtraders,availablegoodsandtheirex-pectedre-salevalue,historicalexperienceonpricesandpar-ticipants’behaviour,etc.However,richnessofinformationisnottheonlysourceofcomplexityinthisdomain.Theactualconditionsfordeliberationarenotonlyconstantlychangingandhighlyuncertain–newgoodsbecomeavail-able,otherbuyerscomeandleave,priceskeeponchang-ing;noonereallyknowsforsurewhatutilityfunctionsotheragentshave,norwhatprofitsmightbeaccrued–butontopofallthat,deliberationsaresignificantlytime-bounded.Consequently,ifatradingagentintendstobehaveaptlyinthiscontext,theagent’sdecision-makingprocessmaybequiteelaborate.

Theproblemofchoosingasuccessfulbiddingstrategy

byatradingagentin-agentsauctiontournamentsisclearlynotdeterministicanditwilldependonmanyfactors,inpar-ticularonthestrategiesthemselvesoftheothercompetingagents.Aslongastheknowledgetheagentwillhaveabouttheotheragents’strategieswillbeusuallyincomplete,ourapproachpresentedinthispaperconsistsinlookingatthisproblemasadecisionmakingproblemunderuncertainty.AsinanyDecisionTheoryproblem,thetradingagenthastochooseadecision(bid)amongasetofavailableal-ternatives,takingintoaccountherpreferencesonthesetofpossibleconsequencesintermsofmaximisingherbenefit.Indecisionproblems,givena(finite)setofpossiblestatesor

situations

anda(finite)setofpossibleconsequencesoroutcomesofthedecisions,adecisionisrepresentedbyafunctionassigningtoeachsituationthe

consequence

ofhavingtakenthedecisionatthestate.Ontheotherhand,consequencesarerankedbyautilityfunctionmodellingthedecisionmaker’spref-erencesamongthem.Inadecisionprocess,uncertaintymaybeinvolvedinknowingeitherwhattherealsituationisorwhatthepreciseconsequencesofdecisionsare.Classicalapproachestodecisionmakingunderuncertaintyassumethatuncertaintyisrepresentedbyprobabilitydistributions.Inthefirstcaseitisassumedthataprobabilitydistributiononthesetofsituationsisknown.Then,theutilityofadecisionismeasuredbytheexpectedvalueofw.r.t.to:

Inthecasewhenweknowtherealsituationbutthecon-sequencesofdecisionsarenotpreciselyknown(foreach

decisionweonlyknowtheprobabilityofeachcon-sequence),thentheutilityofadecisionisevalu-atedinananalogouswayastheexpectedvalueofw.r.t.to:

Thiskindofapproachescorrespondtothewell-knownEx-pectedUtilityTheory(EUT)[12,16],buttheypresentsomeproblemsandparadoxes,basicallyrelatedwithinferringtheprobabilities.Indeed,EUTiswellsuitedwhenthe

space

ofthepossiblestatesiswell-known,itiseasytofigureoutwhichistheoutcomeofeachdecisionateachstate,andofcoursewhentheprobabilitydistributionsoverstatesoroutcomesarealsowell-known.However,inourproblemoftradingagentstheworkingassumptionisthattheknowledgetheagenthasabouttheotheragents’strategiesisreducedtoamemory(orhistory)ofsuccess-fulbidscorrespondingtoprevioustournaments.Thisispreciselythekindofdecisionproblemsaddressedbytheso-calledCase-basedDecisionTheory(CBDT)proposedbyGilboaandSchmeidlerin[6],wherecasesareviewedasinstancesofdecisionmakingandwherethedecision

makeronlyknowscaseswhichhavebeenpreviouslyex-perienced.Inthatcase,givenamemoryofprece-dentdecisionprobleminstances,representedbytriples

,andareal-valuedsimilar-ityfunctionamongsituations,theyproposeinanewsit-uation

tochoosethedecisionwhichmaximisesthefol-lowingexpression

In[3,4]anothercase-basedviewofdecisionmakingispro-posedandshowntobeincloseconnectionwithapossibilis-ticdecisionmodelearlierintroducedbyDuboisandPradein[5].Indeed,theprocessoflookingatthewinningbe-haviourofothertradingagentsinprevioussimilarsituationsandadoptingasimilarbehaviourforouragentinducesanuncertaintywhichisofpossibilisticnatureratherthanprob-abilistic:themoresimilararethecases,themoreplausibleistoassumetheoutcomeofagivendecisioninonecasefortheotherone.

Inthispaperweadaptthislatterdecisionmodeltode-signbiddingstrategiesfortradingagents.NextsectionsketchesouttheauctiontournamentenvironmentFM97.6,andpresentshowtournamentscenarioscanbeformallyde-fined.InSection3,thetheoreticalunderpinningsofthede-cisionmodelaredescribed,whileSection4isdevotedtoexplainhowthisdecisionmodelcanbeemployedinthede-signofbiddingstrategiesfortournamentscenarios.Finally,weendupwithadiscussionaboutrelatedworkandanout-lineofourfuturework.

2.ATest-bedforAuctionTournaments

Following[13],thefishmarketcanbedescribedasaplacewhereseveralscenesrunsimultaneously,atdifferentplaces,butwithsomecausalcontinuity.Theprincipalsceneistheauctionitself,inwhichbuyersbidforboxesoffishthatarepresentedbyanauctioneerwhocallspricesinde-scendingorderaccordingtothedownwardbiddingprotocolwhosedynamicsisdescribedasfollows:

[Step1]Theauctioneerchoosesagoodoutofalotof

goodsthatissortedaccordingtotheorderinwhichsellersdelivertheirgoodstothesellers’admitter.[Step2]Withachosengood,theauctioneeropensa

biddingroundbyquotingoffersdownwardfromthegood’sstartingprice,previouslyfixedbythesellers’admitter,aslongasthesepricequotationsareaboveareservepricepreviouslydefinedbytheseller.[Step3]Severalsituationsmightariseduringthisround:

Bids:One(orseveral)buyer(s)submithis/theirbids

atthecurrentprice.Ifthereisonlyonebid,the

goodissoldtothebidder.Otherwise,acollisioncomesabout,thegoodisnotsold,andtheauc-tioneerrestartstheroundatahigherprice.Nobids:Nobuyersubmitsabidatthecurrentprice.

Ifthereservepricehasnotbeenreachedyet,theauctioneerquotesanewlowerprice,otherwisetheauctioneerdeclaresthegoodwithdrawnandclosestheround.[Step4]Thefirstthreestepsrepeatuntiltherearenomore

goodsleft.However,beforethoseboxesoffishmaybesold,fisher-menhavetodeliverthefishtothefishmarket,atthesell-ers’registrationscene,andbuyersneedtoregisterforthemarket,atthebuyers’registrationscene.Likewise,onceaboxoffishissold,thebuyershouldtakeitawaybypass-ingthroughabuyers’settlementsscene,whilesellersmaycollecttheirpaymentsatthesellers’settlementssceneoncetheirlothasbeensold.

In[15,21,13]wepresentanelectronicauctionhousebasedonthetraditionalfishmarketmetaphor.Inahighlymimeticway,theworkingsofFM96.5alsoinvolvethecon-currencyofseveralscenesgovernedbythemarketinterme-diariesidentifiedinFishMarket.Therefore,selleragentsregistertheirgoodswithaselleradmitteragent,andcangettheirearnings(fromasellermanager)oncetheauction-eerhassoldthesegoodsintheauctionroom.Buyers,ontheotherhand,registerwithabuyeradmitter,andbidforgoodswhichtheypaythroughacreditlinethatissetupandupdatedwithasellermanager.BuyerandselleragentscantradegoodsaslongastheycomplywiththeFishMar-ketinstitutionalconventions.Thoseconventionsthataffectbuyersandsellershavebeencodedintowhatwecallamar-ketinteragent[11]whichconstitutesthesoleandexclusivemeansthroughwhichatraderagent—beitasoftwareagentorahumantrader—interactswiththemarketinstitution.Amarketinteragentgivesapermanentidentitytothetraderandenforcesaconversationprotocolthatestablisheswhatillocutionscanbeutteredbywhomandwhen—andcon-sequentlywhattheirlanguageandcontent,sequencingandeffectsmaybe1.

Inordertoobtainanauctiontournamentenvironment,morefunctionalityhasbeenaddedtoFM96.5toturnitintoatest-bed,FM97.6.Theresultingtest-bedhasthefollowingsalientcharacteristics2:

Itisdomain-specificinthesensethatitmodelsandsimulatesanelectronicauctionhouse.

(minimumtimebetweenrounds).De-laybetweenconsecutiveroundsbelongingtothesameauction.

(maximumnumberofsuccessivecolli-sions).Thisparameterpreventsthealgorithmfromen-teringaninfiniteloopasexplainedabove.

(sanctionfactor).Thiscoefficient

isutilizedbythebuyers’managertocalculatetheamountofthefinetobeimposedonbuyerssubmittingunsupportedbids.

(priceincrement).Thisvaluedetermines

howthenewofferiscalculatedbytheauctioneerfromthecurrentofferwheneitheracollision,oranunsup-portedbidoccur.

Notethattheidentifiedparametersimposesignificant

constraintsonthetradingenvironment.Forinstance,

andaffecttheagents’time-boundedness,

andconsequentlythedegreeofsituatednessviableforbid-dingstrategies.

Nextweintroducethenotionoftournamentdescriptorasanattempttoencompassalltheinformationcharacteriz-ingtournamentscenarios.Thus,wedefineaTournamentDescriptorasthetuplesuchthat:

isthenumberofauctionstotakeplaceduringatour-nament.

isthetimebetweenconsecutiveauctions.

isafinitesetofbiddingprotocols’dynamicsde-scriptors.

isafinitefamilyofcommunicationprotocolsthata

buyeragentmustemploytointeractwithitsinteragentindexedbydifferentbiddingprotocoltypes(f.i.

).

isafinitesetofidentifierscorre-spondingtoallparticipatingbuyers.

isafinitesetofidentifierscorre-spondingtoallparticipatingsellers.

isasequenceofdescriptors.

Eachspecifiesthewayauctionisdynamicallygenerated.

isapairofwinnerevaluationfunction

thatpermittocalculaterespectivelythescoreofbuyersandsellers.

Observethatamultitudeofexperimentaltournament

scenariosofvaryingdegreesofrealismandcomplexitycanbegeneratedbythetournamentdesignerwheninstantiatingthedefinitionoftournamentdescriptor3.Theinformationwithinthetournamentdescriptormustbeconveyedtothebuyersparticipatingintournamentssothattheyknowthefeaturesofthecompetitivescenariotheyareimmersedin.

3.Possibilistic-basedDecisionTheory

Inthissectionwedescribethepossibilistic-baseddeci-sionmakingmodelthatweshallsubsequentlyemployfordesigningcompetitivebiddingstrategiesfortradingagents.WestartbyintroducingthebasicsofDuboisandPrade’spossibilisticdecisionmodel[5](withsomesimplifications),andthenwefollowwithsomeextensionsthatweproposeinordertoshowhowthisdecisionmodelgeneralizesotherde-cisionmodelssuchas,f.i.GilboaandSchmeidler’sCBDT.

3.1.Background

Firstofallweintroducesomenotationanddefinitions.

willdenoteafinitesetofconse-quences,

alinearscaleofuncertainty,with.willdenotethesetofconsistent

possibilitydistributionsonover,i.e.

suchthat.Finally,

willdenotealinearscaleofpreference(orutility),with

and,andautility

functionthatassignstoeachconsequenceofaprefer-encelevelof.Forthesakeofsimplicityhere,we

maketheassumptionthat

.Theworkingassumptionofthedecisionmodelisthateverydecisioninducesapossibilitydistribution

onthesetofconsequences.Thus,rank-ingdecisionsamountstorankingpossibilitydistributions

of.distribution.Insuchaframework,DuboisandPrade[5]proposetheuseoftwokindsofqualitativeutil-ityfunctionstoorderpossibilitydistributions.Thebasicunderlyingideaisbasedonthefactthatautilityfunc-tionontheconsequencescanberegardedasspecifyingafuzzysetofpreferred,goodconsequences:

thegreateris

,themorepreferredistheconsequenceandthemorebelongstothe(fuzzy)setofpreferredconsequences.Ontheotherhand,apossibilitydistribu-tion

specifiesthefuzzysetofwhichconse-quencesareplausible:thegreater,themoreplausibleistheconsequence.Therefore,aconservativecriterionistolookforthose’swhich,atsomeextent,makehardlyplausibleallthebadconsequences,orinotherwords,allplausibleconsequencesaregood.Onthecontrary,anopti-misticcriterionthatmaybeusedtobreaktiesistolookfor

those’sthat,alsotosomeextent,makeplausiblesomeofthegoodconsequences.

Foreachutilityfunction

theconservativeandoptimisticqualitativeutilitiesusedinthepossibilisticdecisionmodelarerespectively:

Onecaneasilynoticethatand

arenothingbutthenecessityandpossibilitydegreesofthefuzzysetw.r.t.thedistribution[1],orinotherwords,theSugenointegralsoftheutilityfunctionwithrespecttothenecessityandpossibilitymeasuresinducedbythedis-tribution.Moreover,whendenotesacrispsubset(i.e.if,otherwise),

and,and

hence,maximizingandgeneralizesthewell-knownmaximinandmaximaxdecisioncriteriarespectively.See[4]foranaxiomatizationofthepreferencerelationin-ducedby

,,andotherrelatedutilityfunctions.3.2.Possiblegeneralizations

Itiswellknowninfuzzysettheorythatthenecessity

andpossibilitymeasuresaccountforaqualitativenotionoffuzzysetinclusionshipandintersection,respectively.Thus,intermsoffuzzysetoperations,thedecisioncriteriaabove

usingthe

andfunctionscanbereadasthehigherthedegreeoffuzzysetinclusionshipoftheinto,thehigherrankingofaccordingtotheconservativecri-terion,whilethehigherthedegreeoffuzzysetintersectionofthewith,thehigherrankingofaccordingtotheoptimisticcriterion.

Thus,besidesthosepurequalitativeutilities,onecannat-urallythinkofintroducingsomeotherexpressionsofamorequantitativenature,butstillaccountingforanotionofinclu-sionandintersection.Forinstance,themostgeneralwayofdefiningthedegreeofintersectionofandis:

where,beingat-norm4op-erationin[0,1].However,todefineadegreeofinclusionofinto,thereareatleasttwowaysbasedon:(i)towhatextentallelementsofarealsoelementsof;(ii)thepro-portionofelementsof

withrespecttotheelementsof.Theformercomesfromalogicalviewwhilethelattercomesfromaconditioningview.Theyleadtothefollowingexpressions:

,

where

denotesfuzzycardinality6.

Atthispoint,thefollowingremarksareinorder.1.Ifbothanddefinecrispsubsetsofconsequences,

then

iseither1or0,whileisnothingbuttherelativecardinalityofinside,andforboth,thedegreeis1onlyif.

2.Whenand

,we

recoverthequalitativeutilityfunctions:

and

.

3.When,isnothingbuttheex-pectedvalueoftheutilityfunctionw.r.t.totheunnormalizedprobabilitydistribution,orinotherwords,theweightedaverageofthevaluesaccordingtotheweights.Whencomes

fromasimilarityfunction,then

canbecloselyrelatedtoGilboaandSchmeidler’sCBDT.

Finally,basedonthenotionsofdegreeofinclusionandintersectiondefinedabove,wecanconsidertheutilityfunc-tions

.

,,and4.Case-basedDecisionModelforDesigningBiddingStrategies

Anagent’sbiddingstrategymustdecideonanappro-priatepriceonwhichtobidforeachgoodbeingauctionedduringeachroundcomposingthetournament.Duetothenatureofthedomainfacedbytheagent,wemustdemandthatsuchbiddingstrategybalancestheagent’sshort-termbenefitswithitslong-termbenefitsinordertosucceedinlong-runtournaments.

Inwhatfollowswemakeuseofthepossibilistic-baseddecision-makingmodeldescribedaboveasthekeyelementtoproduceacompetitivebiddingstrategy.Foreachround,theresultingstrategyperformsahybrid,two-folddecisionmakingprocessthatinvolvestheusageofglobal(market-centered)probabilisticinformationinafirstdecisionstep,andindividual(rival-centered)possibilisticinformationinasecond,refiningdecisionstep.

4.1.TheDecisionProblem

Foreachroundcomposingatournamentscenario,thedecisionproblemforatradingagentconsistsinselectingabidfromthewholesetofpossiblebids—fromthestartingpricedowntothereserveprice.

Inordertoapplythepossibilisticdecisionmodelfirstwehavetoidentifythevariablesinvolvedinthedecisionproblemofourinterest.

Wemodelmarketsituationsfacedbyouragent,denotedhereafter,asvectorsoffeatures

characterizingroundofauctionsuchthatisthetype

ofthegoodtobeauctioned,isitsstartingprice,isitsresaleprice,is

thevectorofscores(

),andisthenumberofroundsleft.

Thedecisionsetwillconsistofthesetofallowedbidsouragentcansubmit.Givenanewmarketsituation,weshallhave

,whereandarethestarting

andreservepricesinsituation,andmeansthattheagentsubmitsabidatprice.

Ateachround,eithertheagent()wins,orbuyerwins,,orbuyerwinsbysubmittingbidsatdifferentprices.Therefore,thesetofoutcomes(orconsequences)isdefinedastheset

,wheremeansthat

buyerwinstheroundbysubmittingabidatprice.

Hereafterweshallassumethattheagentkeepsamemoryofcasesstoringthehistoryof(pastandthecurrent)tour-naments,whosecasesareoftheform

,wherebisthebuyerwhowontheroundcharacterizedby

(asdefinedabove)bysubmittingabidatprice.Finally,wemustrecallfromthedecisionmodelintro-ducedintheprevioussectionthatgivenanewmarketsitu-ation,theagenthastoassess,foreachpossibledecision(bid),thepossibilityandutilityvalues,,inordertobeabletocalculateaglobaland

utilityforeach(usingeither,,,or).Thewayofgeneratingpossibilitiesandassessingutilitiesispresentedalongthenextsubsections.

4.2.ReducingtheSearchSpace

Evidently,deployingthepossibilistic-baseddecision

mechanismfromthewholesetofpossibledecisions(bids)appearstobeprohibitivelyexpensive.Instead,were-ducethedecisionsetbyconsideringasubsetcomposedofthosedecisions(bids)maximizingtheagent’sshort-termex-pectedbenefitforthecurrentround,theso-calledsetofcandidatebids.Thispre-processingofwillideallyhelp

theagent’sdeliberationprocesstoconstraintotimeandresource-boundedness.

Inordertoobtainasetofcandidatebidsforagivenroundofauctioncharacterizedbyafeaturevector,wefirstlyinferaprobabilitydistributiononthesalepricefromthepasthistoryofthetournament.Secondly,weuti-lizesuchdistributiontoobtainthepricewhichmaximizestheagent’sshort-termexpectedbenefitforthecurrentroundgivenbythefollowingexpression

Fromthisset,weshallredefinethedecisionsetas

.

4.3.GenerationofPossibilityDistributions

Inordertoobtainapossibilitydegreeforeachconse-quencein,weobservethebehaviourofeachagentinprevioussimilarsituations.Then,theuncertaintyonthebe-haviourofeachagentinfrontofanewmarketsituationisestimated,asapossibilitydegree,intermsofthesimilaritybetweenthecurrentsituationandthosemarketsituationswheretheagentexhibitedthatbehaviour.

Giventhecurrentmarketsituation,foreachpossiblebid,ouragenthastoevaluatethepossibil-ityofeachbuyer(includinghimself)winningtheround,i.e.thepossibilityofeachconsequence.Let

.Weshallassumebeaasconsequenceaworkingprincipleandthatacasein

morepossible“themoresimilaristo,thewillbethewinnerin”(asimilarprinciplehasbeerecentlyconsid-eredinaframeworkoffuzzycase-basedreasoning[3]).Ifdenotesthefuzzysetofsituationssimilarto,theaboveprinciplecanbegiventhefollowingsemantics:

wheredenotesthemembershipdenotesfunctionofthefuzzysetandthemembershipfunctionofthefuzzyset.Theyaredefinedasand,whereandarefuzzyrelationsonthesetofsituationsandonthesetofpricesrespectively,accountingforanotionofproximityorsimilarity.

Therefore,wecanestimatethepossibilitydegreesforeachas:

forallconstructaninitialfuzzy.set

Fromthesepossibilitiesningbidsofeachparticipatingbuyerofthewecan

as

possiblewin-forallsuchthat.Howeverthisfuzzysetmaybefurthermodifiedbymeansofasetoffuzzyruleswhichattemptatmodellingtherationalbehaviourofbuyersinparticularsituationsthatmaynotbesufficientlydescribedbythecasesinthememory.Forinstance,weconsiderthefollowingsetoffuzzyrules:

if[

ishigh]and[Risvery

positiveif

[

ismedium]and[Risvery

positive

expressingheuristicrulesdescribingexpectedchangesinthestrategyofabuyerwhenonlyafewroundsare

left(is

is).In),theseandhesituations,lagsbehinddependingintheranking(rulesaboveonmodeltheagents’currentcredit(),thefuzzyanincreaseintheagresivenessofthebuyer,atdifferentdegrees,byyieldingtheexpectedincreases()intheagent’sbid.Ingeneral,byapplyingasetoffuzzyrulesofthattypeinthestandardway,weobtainforeachbuyer

afuzzyset

representingtheexpectedvariationoftheobservedbiddingstrategyofeachbuyer.

Fromthecombinationoftheinitialfuzzysetofpossi-blebids

withthefuzzysetofexpectedvariationsweobtainthefinalfuzzysetofpossiblebids

where

denotesfuzzyaddition,i.e.

Finally,wemakeuseofthefuzzysetpossibilitiestoeachconsequenceforeach

toreassign

Finally,toestimatethepossibilityofouragentwinningwithabidatpricewelookintothememoryforthosecasessuchthatthesalepricewasnotgreaterthan.Then

.Let

Thesearethepossibilitiestobeutilizedwhenapplyingourdecisionmodel.

4.4.AssessingUtilities

Givenanewmarketsituation,foreachconsequence

ouragentmustassesstheutilityvalueat

thefactthatbuyerwinstheroundbysubmittingabidat

price,

.Inwhatfollowsweproposeautilityfunctionforconstructinganagentthatpreferstowaitandseewhenheisahead,whereashebecomesmoreandmoreagressivewhenhelagsbehindinordertoreachthefirstpositioninthetournament.

Forthispurpose,weconsiderthefollowingfunction:

where,beingtheresaleprice,andtheevaluationfunctionforbuyers.We

assumethat

,and,i.e.buyersonlyconsiderbidsthatcanimprovetheirscore,andtheyhaveenoughcredittosubmitthebidatprice.Inthefactors

,,and

),otherwise—thebuyerisbehindtheleader–theutility

ofbiddingisvaluedpositively(

Robocup[9]isattemptingtoencouragebothAIresearchersandroboticsresearcherstomaketheirsystemsplaysoccer,autonomousmobilerobotstrytoshowtheirskillsinofficenavigationandincleaningupthetenniscourtintheAAAIMobileRobotCompetition[10],andevenautomatedtheo-remprovingsystemsparticipateincompetitions[17].ButsurelyourproposalisclosertotheDoubleauctiontour-namentsheldbytheSantaFeInstitute[2]wherethecon-tenderscompetedfordevelopingoptimizedtradingstrate-gies.However,themainconcernofourproposalconsistsinprovidingamethodforperformingmulti-agentreason-ingunderuncertaintybasedonthemodellingoftheotheragents’behaviourlikewise[18],wheretherecursivemod-ellingmethod[7]wasusedforconstructingagentscapableofpredictingtheotheragents’behaviourinDoubleauctionmarkets.

Atpresent,aproof-of-conceptimplementationofourproposalisundergoingempiricalevaluation.Wearebasi-callyanalyzingwhichutilityandsimilarityfunctionsyieldgoodperformances.Ingeneral,conservativeutilitiesleadtoapreferringhigherbidsthan.Astoourfuturework,firstlyourresearchwillheadtowardstheconstruc-tionofactualagentscapableoftradinginactualauctionmarketsundertherulesofanyauctionprotocol.Secondly,inparallel,FM97.6willbemadetoevolvetohostother(evenmoreflexible)formsofprice-fixingmechanisms(En-glishauction,Doubleauction,discounting,opennegotia-tion,etc.),andwillbeequippedwithatrading-agentshelltohelpagentdesignersconstructtheiragents.

6.Acknowledgements

ThisworkhasbeenpartiallysupportedbytheSpan-ishCICYTprojectSMASH,TIC96-1038-C04001.EduardGim´enezandJuanA.Rodr´ıguez-AguilarenjoytheCIRITdoctoralscholarships1998FI0005andFI-PG/96-8.490re-spectively.

References

[1]Z.L.A.Fuzzysetsasabasisforthetheoryofpossibility.

FuzzySetsandSystems,(1):3–28,1978.

[2]M.AndrewsandR.Prager.GeneticProgrammingfor

theAcquisitionofDoubleAuctionMarketStrategies,pages355–368.TheMITPress,1994.

[3]D.Dubois,F.Esteva,P.Garcia,L.Godo,R.L.deMantaras,

andH.Prade.Fuzzymodellingofcase-basedreasoninganddecision.InLeakeandPlaza,editors,Proceedings2nd.Int.Conf.onCaseBasedReasoning(ICCBR’97),pages599–611,1997.

[4]D.Dubois,L.Godo,H.Prade,andA.Zapico.Makingde-cisioninaqualitativesetting:fromdecisionunderuncer-taintytocase-baseddecision.InProceedingsofthe6th..

Int.Conf.onPrinciplesofKnowledgeRepresentationandReasoning(KR’98),1998.

[5]

D.DuboisandH.Prade.Possibilitytheoryasabasisforqualitativedecisiontheory.InProceedingsofthe14thIn-ternationalJointConferenceonArtificialIntelligence(IJ-CAI’95),pages1924–1930,1995.

[6]I.GilboaandD.Schmeidler.Case-basedtheory.TheQuar-terlyJournalofEconomics,pages607–639,1995.

[7]

P.GmytrasiewiczandE.H.Durfee.Arigorous,opera-tionalformalizationofrecursivemodeling.InProceedingsoftheFirstInternationalConferenceonMulti-AgentSys-tems,pages125–132,1995.

[8]

B.A.HubermanandS.Clearwater.Amulti-agentsystemforcontrollingbuilgingenvironments.InProceedingsoftheFirstInternationalConferenceonMulti-AgentSystems(ICMAS-95),pages171–176.AAAIPress,June1995.

[9]

H.Kitano,M.Asada,Y.Kuniyoshi,I.Noda,andE.Osawa.Robocup:Therobotworldcupinitiative.InFirstInterna-tionalConferenceonAutonomousAgents,1997.

[10]

D.Kortenkamp,I.Nourbakhsh,andD.Hinkle.The1996AAAIMobileRobotCompetitionandExhibition.AIMag.,18(1):25–32,1997.[11]

F.J.Mart´ın,E.Plaza,J.A.Rodr´ıguez-Aguilar,andJ.Sabater.Jimajavainteragentformulti-agentsystems.InProceedingsoftheAAAI-98WorkshoponSoftwareToolsforDevelopingAgents,1998.

[12]

J.V.NeumannandO.Morgenstern.TheoryofGamesandEconomicBehaviour.PrincetonUniv.Press,Princeton,NJ,1944.

[13]

P.Noriega.Agent-MediatedAuctions:TheFishmarketMetaphor.PhDthesis,UniversitatAutonomadeBarcelona,1997.AlsotoappearinIIIAmongraphyseries.[14]

J.A.Rodr´ıguez-Aguilar,F.J.Mart´ın,P.Noriega,P.Gar-cia,andC.Sierra.Competitivescenariosforheterogeneoustradingagents.InProceedingsoftheSecondInternationalConferenceonAutonomousAgents(AGENTS’98),1998.[15]

J.A.Rodr´ıguez-Aguilar,P.Noriega,C.Sierra,andJ.Padget.Fm96.5ajava-basedelectronicauctionhouse.InSecondInternationalConferenceonThePracticalApplicationofIntelligentAgentsandMulti-AgentTechnology(PAAM’97),1997.

[16]L.J.Savage.TheFoundationsofStatistics.Dover,1972.[17]

C.B.SuttnerandG.Sutcliffe.ATPSystemCompetition,vol-ume1104ofLectureNotesinArtificialIntelligence,pages146–160.SpringerVerlag,1996.

[18]

J.M.VidalandE.H.Durfee.Buildingagentmodelsineco-nomicsocietiesofagents.InWorkshoponAgentModelling(AAAI-96),1996.

[19]

M.P.Wellman.Amarket-orientedprogrammingenviron-mentanditsapplicationtodistributedmulticommodityflowproblems.JournalofArtificialIntelligenceResearch,(1):1–23,1993.

[20]

F.YggeandH.Akkermans.Powerloadmanagementasacomputationalmarket.InProceedingsoftheSecondInter-nationalConferenceonMulti-AgentSystems(ICMAS-96),1996.

[21]

TheFishMarketProject.http://www.iiia.csic.es/Projects/-fishmarket.