∗
CorkConstraintAlanComputationHolland
CentreDepartmentofComputerScienceUniversityCollegeCork,Ireland
a.holland@4c.ucc.ieABSTRACT
Bidssubmittedinauctionsareusuallytreatedasenforceablecom-mitmentsinmostbiddingandauctiontheoryliterature.Inrealitybiddersoftenwithdrawwinningbidsbeforethetransactionwhenitisintheirbestintereststodoso.Givenabidwithdrawalinacombinatorialauction,findinganalternativerepairsolutionofad-equaterevenuewithoutcausingunduedisturbancetotheremain-ingwinningbidsintheoriginalsolutionmaybedifficultorevenimpossible.Wehavecalledthisthe“Bid-taker’sExposureProb-lem”.Whenfacedwithsuchunreliablebidders,itispreferableforthebid-takertopreemptsuchuncertaintybyhavingasolutionthatisrobusttobidwithdrawalandprovidesaguaranteethatpossiblewithdrawalsmayberepairedeasilywithaboundedlossinrevenue.Inthispaper,weproposeanapproachtoaddressingtheBid-taker’sExposureProblem.Firstly,weusetheWeightedSuperSo-lutionsframework[13],fromthefieldofconstraintprogramming,tosolvetheproblemoffindingarobustsolution.Aweightedsupersolutionguaranteesthatanysubsetofbidslikelytobewithdrawncanberepairedtoformanewsolutionofatleastagivenrevenuebymakinglimitedchanges.Secondly,weintroduceanauctionmodelthatusesaformofleveledcommitmentcontract[26,27],whichwehavecalledmutualbidbonds,toimprovesolutionreparabilitybyfacilitatingbacktrackingonwinningbidsbythebid-taker.Wethenexaminethetrade-offbetweenrobustnessandrevenueindif-ferenteconomicallymotivatedauctionscenariosfordifferentcon-straintsontherevenueofrepairsolutions.Wealsodemonstrateexperimentallythatfewerwinningbidspartakeinrobustsolutions,therebyreducinganyassociatedoverheadindealingwithextrabid-ders.Robustsolutionscanalsoprovideameansofselectivelydis-criminatingagainstdistrustedbiddersinameasuredmanner.
CategoriesandSubjectDescriptors
J.4[SocialandBehavioralSciences]:Economics;K.4.4[Computers∗landThisworkhasBrahimundergrantnumberreceived00/PI.1/C075.supportfromTheScienceauthorsFoundationwishIre-ments.
Hnichandtheanonymousreviewersfortheirhelpfultothankcom-Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.
EC’05,June5–8,2005,Vancouver,BritishColumbia,Canada.Copyright2005ACM1-59593-049-3/05/0006...$5.00.
CorkConstraintBarryO’Sullivan
ComputationCentreDepartmentofComputerScienceUniversityCollegeCork,Ireland
b.osullivan@4c.ucc.ie
andSociety]:ElectronicCommerce;I.2.8[ArtificialIntelligence]:ProblemSolving,ControlMethods,andSearch.
GeneralTerms
Algorithms,Economics,Reliability.
Keywords
CombinatorialAuctions,Bidwithdrawal,Robustness,ConstraintProgramming,WeightedSuperSolutions.
1.INTRODUCTION
Acombinatorialauction(CA)[5]providesanefficientmeansofallocatingmultipledistinguishableitemsamongstbidderswhoseperceivedvaluationsforcombinationsofitemsdiffer.Suchauc-tionsaregaininginpopularityandthereisaproliferationintheirusageacrossvariousindustriessuchastelecoms,B2Bprocurementandtransportation[11,19].
Revenueisthemostobviousoptimizationcriterionforsuchauc-tions,butanotherdesirableattributeissolutionrobustness.Intermsofcombinatorialauctions,arobustsolutionisonethatcanwith-standbidwithdrawal(abreak)bymakingchangeseasilytoformarepairsolutionofadequaterevenue.AbrittlesolutiontoaCAisoneinwhichanunacceptablelossinrevenueisunavoidableifawinningbidiswithdrawn.Insuchsituationsthebid-takermaybeleftwithasetofitemsdeemedtobeoflowvaluebyallotherbidders.Thesebiddersmayassociateahighervaluefortheseitemsiftheywerecombinedwithitemsalreadyawardedtoothers,hencethebid-takerisleftinanundesirablelocaloptimuminwhichaformofbacktrackingisrequiredtoreallocatetheitemsinamannerthatresultsinsufficientrevenue.Wehavecalledthisthe“Bid-taker’sExposureProblem”thatbearssimilaritiestothe“ExposureProb-lem”facedbybiddersseekingmultipleitemsinseparatesingle-unitauctionsbutholdinglittleornovalueforasubsetofthoseitems.However,reallocatingitemsmayberegardedasdisruptivetoasolutioninmanyreal-lifescenarios.ConsiderascenariowhereprocurementforabusinessisconductedusingaCA.Itwouldbehighlyundesirabletoretractcontractsfromagroupofsuppliersbecauseofthefailureofathirdparty.Arobustsolutionthatistol-erantofsuchbreaksispreferable.Robustnessmayberegardedasapreventativemeasureprotectingagainstfutureuncertaintybysac-rificingrevenueinplaceofsolutionstabilityandreparability.Weassumeaprobabilisticapproachwherebythebid-takerhasknowl-edgeofthereliabilityofbiddersfromwhichthelikelihoodofanincompletetransactionmaybeinferred.
Repairsolutionsarerequiredforbidsthatareseenasbrittle(i.e.likelytobreak).Repairsmayalsoberequiredforsetsofbidsdeemedbrittle.WeproposetheuseoftheWeightedSuper
Solutions(WSS)framework[13]forconstraintprogramming,thatisidealforestablishingsuchrobustsolutions.Asweshallsee,thisframeworkcanenforceconstraintsonsolutionssothatpossi-blebreakagesarereparable.
Thispaperisorganizedasfollows.Section2presentstheWin-nerDeterminationProblem(WDP)forcombinatorialauctions,out-linessomepossiblereasonsforbidwithdrawalandshowshowsim-plymaximizingexpectedrevenuecanleadtointolerablerevenuelossesforrisk-aversebid-takers.ThismotivatestheuseofrobustsolutionsandSection3introducesaconstraintprogramming(CP)framework,WeightedSuperSolutions[13],thatfindssuchsolu-tions.WethenproposeanauctionmodelinSection4thatenhancesreparabilitybyintroducingmandatorymutualbidbonds,thatmaybeseenasaformofleveledcommitmentcontract[26,27].Sec-tion5presentsanextensiveempiricalevaluationoftheapproachpresentedinthispaper,inthecontextofanumberofwell-knowncombinatorialauctiondistributions,withveryencouragingresults.Section6discussespossibleextensionsandquestionsraisedbyourresearchthatdeservefuturework.Finally,inSection7anumberofconcludingremarksaremade.
2.COMBINATORIALAUCTIONS
Beforepresentingthetechnicaldetailsofoursolutiontothe“Bid-taker’sExposureProblem”,weshallpresentabriefsurveyofcombinatorialauctionsandexistingtechniquesforhandlingbidwithdrawal.
Combinatorialauctionsinvolveasinglebid-takerallocatingmul-tipledistinguishableitemsamongstagroupofbidders.Thebid-takerhasasetofmitemsforsale,M={1,2,...,m},andbid-derssubmitasetofbids,B={B1,B2,...,Bn}.AbidisatupleBj=Sj,pjwhereSj⊆Misasubsetoftheitemsforsaleandpj≥0isaprice.TheWDPforaCAistolabelallbidsaseitherwinningorlosingsoastomaximizetherevenuefromwinningbidswithoutallocatinganyitemtomorethanonebid.ThefollowingistheintegerprogrammingformulationfortheWDP:
maxnp
jxjs.t.
xj≤1,∀i∈{1...m},xj∈{0,1}.
j=1
j|i∈Sj
ThisproblemisNP-complete[23]andinapproximable[25],andisotherwiseknownastheSetPackingProblem.Theaboveproblemformulationassumesthenotionoffreedisposal.Thismeansthattheoptimalsolutionneednotnecessarilysellalloftheitems.Iftheauctionrulesstipulatethatallitemsmustbesold,theproblembecomesaSetPartitionProblem[5].TheWDPhasbeenextensivelystudiedinrecentyears.Thefastestsearchalgorithmsthatfindoptimalsolutions(e.g.CABOB[25])can,inpractice,solveverylargeproblemsinvolvingthousandsofbidsveryquickly.
2.1TheProblemofBidWithdrawal
Weassumeanauctionprotocolwithathreestageprocessin-volvingthesubmissionofbids,winnerdetermination,andfinallyatransactionphase.Weareinterestedinbidwithdrawalsthatoc-curbetweentheannouncementofwinningbidsandtheendofthetransactionphase.Allbidsarevaliduntilthetransactioniscom-plete,soweanticipateanexpedienttransactionprocess1.1
considerationInsomeinstancesthetransactionperiodmaybesolengthythatfair.difficultBreaksthatofoccurnon-winningduringabidslengthyasstilltransactionbeingvalidphasemaynotbeample,thebreakiftotheremedyoccursitemafterisandaservicemayrequireasubsequentauction.areFormoreex-partialcontractfulfilmentforofagiventhiscontract,periodofthetimeother
andAnexampleofawinningbidwithdrawaloccurredinanFCCspectrumauction[32].Withdrawals,orbreaks,mayoccurforvar-iousreasons.Bidwithdrawalmaybeinstigatedbythebid-takerwhenQualityofServiceagreementsarebrokenorpaymentdead-linesarenotmet.Werefertobidwithdrawalbythebid-takerasitemwithdrawalinthispapertodistinguishbetweentheactionsofabidderandthebid-taker.HarstadandRothkopf[8]outlinedseveralpossibilitiesforbreaksinsingleitemauctionsthatinclude:1.anerroneousinitialvaluation/bid;
2.unexpectedeventsoutsidethewinningbidder’scontrol;3.adesiretohavethesecond-bestbidhonored;
4.
informationobtainedoreventsthatoccurredaftertheauctionbutbeforethetransactionthatreducesthevalueofanitem;5.therevelationofcompetingbidders’valuationsinfersreducedprofitability,aproblemknownasthe“Winner’sCurse”.
Kastneretal.[15]examinedhowtohandleperturbationsgiven
asolutionwhilstminimizingnecessarychangestothatsolution.Theseperturbationsmayincludebidwithdrawals,changeofvalu-ation/itemsofabidorthesubmissionofanewbid.Theylookedattheproblemoffindingincrementalsolutionstorestructureasup-plychainwhoseformationisdeterminedusingcombinatorialauc-tions[30].Followingaperturbationintheoptimalsolutiontheyproceedtoimposeinvoluntaryitemwithdrawalsfromwinningbid-ders.Theyformulatedanincrementalintegerlinearprogram(ILP)thatsoughttomaximizethevaluationoftherepairsolutionwhilstpreservingtheprevioussolutionasmuchaspossible.
2.2BeingProactiveagainstBidWithdrawal
Whenabidiswithdrawntheremaybeconstraintsonhowthesolutioncanberepaired.Ifthebid-takerwasfreelyabletorevoketheawardingofitemstootherbiddersthenthesolutioncouldberepairedeasilybyreassigningalltheitemstotheoptimalsolutionwithoutthewithdrawnbid.Alternatively,thebidderwhorenegeduponabidmayhaveallhisotherbidsdisqualifiedandtheitemscouldbereassignedbasedontheoptimumsolutionwithoutthatbidderpresent.However,thebid-takerisoftenunabletofreelyreassigntheitemsalreadyawardedtootherbidders.Whenitemscannotbewithdrawnfromwinningbidders,followingthefailureofanotherbiddertohonorhisbid,repairsolutionsarerestrictedtothesetofbidswhoseitemsonlyincludethoseinthebid(s)thatwererenegedupon.Wearefreetoawarditemstoanyofthepreviouslyunsuccessfulbidswhenfindingarepairsolution.
Whenfacedwithuncertaintyoverthereliabilityofbiddersapos-sibleapproachistomaximizeexpectedrevenue.Thisapproachdoesnotmakeallowancesforrisk-aversebid-takerswhomayviewasmallpossibilityofverylowrevenueasunacceptable.
ConsidertheexampleinTable1,andtheoptimalexpectedrev-enueinthesituationwhereasinglebidmaybewithdrawn.TherearethreesubmittedbidsforitemsAandB,thethirdbeingacom-binationbidforthepairofitemsatavalueof190.Theoptimalsolutionhasavalueof200,withthefirstandsecondbidsaswin-ners.Whenweconsidertheprobabilitiesoffailure,inthefourthcolumn,theproblemofwhichsolutiontochoosebecomesmoredifficult.
Computingtheexpectedrevenueforthesolutionwiththefirstandsecondbidswinningtheitems,denoted1,1,0,gives:(200×0.9×0.9)+(2×100×0.9×0.1)+(190×0.1×0.1)=181.90.bidders’fashion.
valuationsfortheitemmayhavedecreasedinanon-linearTable1:ExampleCombinatorialAuction.
Items
BidsABABWithdrawalprob
x1100000.1x2010000.1x3
0
0
190
0.1
Ifasinglebidiswithdrawnthereisprobabilityof0.18ofarevenueof100,giventhefactthatwecannotwithdrawanitemfromtheotherwinningbidder.Theexpectedrevenuefor0,0,1is:
(190×0.9)+(200×0.1)=191.00.
Wecanthereforesurmisethatthesecondsolutionispreferabletothefirstbasedonexpectedrevenue.
Determiningthemaximumexpectedrevenueinthepresenceofsuchuncertaintybecomescomputationallyinfeasiblehowever,asthenumberofbrittlebidsgrows.AWDPneedstobesolvedforallpossiblecombinationsofbidsthatmayfail.Thepossiblelossinrevenueforbreaksisalsonottightlyboundedusingthisapproach,thereforealargelossmaybepossibleforasmallnumberofbreaks.Considerthepreviousexamplewherethebidamountforx3be-comes175.Theexpectedrevenueof1,1,0(181.75)becomesgreaterthanthatof0,0,1(177.50).Therearesomebid-takerswhomaypreferthelattersolutionbecausetherevenueisneverlessthan175,buttheformersolutionreturnsrevenueofonly100withprobability0.18.Arisk-aversebid-takermaynottoleratesuchapossibility,preferringtosacrificerevenueforreducedrisk.
Ifwemodifyourrepairsearchsothatasolutionofatleastagivenrevenueisguaranteed,thesearchforarepairsolutionbe-comesasatisfiabilitytestratherthananoptimizationproblem.Theapproachesdescribedaboveareincontrasttothatwhichwepro-poseinthenextsection.Ourapproachcanbeseenaspreventativeinthatwefindaninitialallocationofitemstobidderswhichisro-busttobidwithdrawal.Possiblelossesinrevenueareboundedbyafixedpercentageofthetrueoptimalallocation.Perturbationstotheoriginalsolutionarealsolimitedsoastominimizedisruption.Weregardthisastheidealapproachforreal-worldcombinatorialauctions.
DEFINITION1(ROBUSTSOLUTIONFORACA).Arobustsolutionforacombinatorialauctionisonewhereanysubsetofsuccessfulbidswhoseprobabilityofwithdrawalisgreaterthanorequaltoαcanberepairedbyreassigningitemsatacostofatmostβtootherpreviouslylosingbidstoformarepairsolution.Constraintsonacceptablerevenue,e.g.beingaminimumper-centageoftheoptimum,aredefinedintheproblemmodelandarethussatisfiedbyallsolutions.Themaximumcostofrepair,β,maybeafixedvaluethatmaybethoughtofasafundforcompensat-ingwinningbidderswhoseitemsarewithdrawnfromthemwhencreatingarepairsolution.Alternatively,βmaybeafunctionofthebidsthatwerewithdrawn.Section4willgiveanexampleofsuchamechanism.Inthefollowingsectionwedescribeanidealconstraint-basedframeworkfortheestablishmentofsuchrobustsolutions.
3.FINDINGROBUSTSOLUTIONS
Inconstraintprogramming[4](CP),aconstraintsatisfactionprob-lem(CSP)ismodeledasasetofnvariablesX={x1,...,xn},
asetofdomainsD={D(x1),...,D(xn)},whereD(xi)isthesetoffinitepossiblevaluesforvariablexiandasetC={C1,...,Cm}ofconstraints,eachrestrictingtheassignmentsofsomesubsetofthevariablesinX.Constraintsatisfactioninvolvesfindingvaluesforeachoftheproblemvariablessuchthatallcon-straintsaresatisfied.Itsmainadvantagesareitsdeclarativenatureandflexibilityintacklingproblemswitharbitrarysideconstraints.ConstraintoptimizationseekstofindasolutiontoaCSPthatop-timizessomeobjectivefunction.Acommontechniqueforsolvingconstraintoptimizationproblemsistousebranch-and-boundtech-niquesthatavoidexploringsub-treesthatareknownnottocontainabettersolutionthanthebestfoundsofar.AninitialboundcanbedeterminedbyfindingasolutionthatsatisfiesallconstraintsinCorbyusingsomeheuristicmethods.
Aclassicalsupersolution(SS)isasolutiontoaCSPinwhich,ifasmallnumberofvariableslosetheirvalues,repairsolutionsareguaranteedwithonlyafewchanges,thusprovidingsolutionrobustness[9,10].ItisageneralizationofbothfaulttoleranceinCP[31]andsupermodelsinpropositionalsatisfiability(SAT)[7].An(a,b)-supersolutionisoneinwhichifatmostavariableslosetheirvalues,arepairsolutioncanbefoundbychangingatmostbothervariables[10].
Supersolutionsforcombinatorialauctionsminimizethenumberofbidswhosestatusneedstobechangedwhenformingarepairsolution[12].Onlyaparticularsetofvariablesinthesolutionmaybesubjecttochangeandthesearesaidtobemembersofthebreak-set.Foreachcombinationofbrittleassignmentsinthebreak-set,arepair-setisrequiredthatcomprisesthesetofvariableswhoseval-uesmustchangetoprovideanothersolution.Thecardinalityoftherepairsetisusedtomeasurethecostofrepair.Inreality,chang-ingsomevariableassignmentsinarepairsolutionincursalowercostthanotherstherebymotivatingtheuseofadifferentmetricfordeterminingthelegalityofrepairsets.
TheWeightedSuperSolution(WSS)framework[13]considersthecostofrepairrequired,ratherthansimplythenumberofas-signmentsmodified,toformanalternativesolution.ForCAsthismaybeameasureofthecompensationpenaltiespaidtowinningbidderstobreakexistingagreements.Robustsolutionsarepartic-ularlydesirableforapplicationswhereunreliabilityisaproblemandpotentialbreakagesmayincurseverepenalties.Weightedsu-persolutionsofferameansofexpressingwhichvariablesareeas-ilyre-assignedandthosethatincuraheavycost[13].Hebrardetal.[9]describehowsomevariablesmayfail(suchasmachinesinajob-shopproblem)andothersmaynot.AWSSgeneralizesthisap-proachsothatthereisaprobabilityoffailureassociatedwitheachassignmentandsetsofvariableswhoseassignmentshaveprobabil-itiesoffailuregreaterthanorequaltoathresholdvalue,α,requirerepairsolutions.
AWSSmeasuresthecostofrepairing,orreassigning,othervari-ablesusinginertiaasametric.Inertiaisameasureofavariable’saversiontochangeanddependsonitscurrentassignment,futureassignmentandthebreakagevariable(s).
Itmaybedesirabletoreassignitemstodifferentbiddersinordertofindarepairsolutionofsatisfactoryrevenue.Compensationmayhavetobepaidtobidderswholoseitemsduringtheformationofarepairsolution.Theinertiaofabidreflectsthecostofchangingitsstate.Forwinningbidsthismayreflectthenecessarycompensationpenaltyforthebid-takertobreaktheagreement(ifsuchbreachesarepermitted),whereasforpreviouslylosingbidsthisisafreeop-eration.Thetotalamountofcompensationpayabletobiddersmaydependuponotherfactors,suchasthecauseofthebreak.Thereisalimittohowmuchtheseoverallrepaircostsshouldbe,andthisisgivenbythevalueβ.Thisvaluemaynotbeknowninadvanceand
Algorithm1:WSS(intlevel,doubleα,doubleβ):Booleanbegin
iflevel>numberofvariablesthenreturntruechooseunassignedvariablex
foreachvaluevinthedomainofxdo
assignx:v
ifproblemisconsistentthen
foreachcombinationofbrittleassignments,Ado
if¬reparable(A,β)thenreturnfalse;
ifWSS(level+1)thenreturntrue
unassignxreturnfalseendmaydependuponthebreak.Therefore,βmaybeviewedasthefundusedtocompensatewinningbiddersfortheunilateralwith-drawaloftheirbidsbythebid-taker.Insummary,an(α,β)-WSSallowsanysetofvariableswhoseprobabilityofbreakingisgreaterthanorequaltoαberepairedwithchangestotheoriginalrobustsolutionwithacostofatmostβ.
Thedepth-firstsearchforaWSS(seepseudo-codedescriptioninAlgorithm1)maintainsarc-consistency[24]ateachnodeofthetree.Assearchprogresses,thereparabilityofeachpreviousas-signmentisverifiedateachnodebyextendingapartialrepairso-lutiontothesamedepthasthecurrentpartialsolution.Thismaybethoughtofasmaintainingconcurrentsearchtreesforrepairs.Arepairsolutionisprovidedforeverypossiblesetofbreakvari-ables,A.TheWSSalgorithmattemptstoextendthecurrentpartialassignmentbychoosingavariableandassigningitavalue.Back-trackingmaythenoccurforoneoftworeasons:wecannotextendtheassignmenttosatisfythegivenconstraints,orthecurrentpar-tialassignmentcannotbeassociatedwitharepairsolutionwhosecostofrepairislessthanβshouldabreakoccur.Theprocedurereparablesearchesforpartialrepairsolutionsusingbacktrack-ingandattemptstoextendthelastrepairfound,justasin(1,b)-supersolutions[9];thedifferencesbeingthatarepairisprovidedforasetofbreakagevariablesratherthanasinglevariableandthecostofrepairisconsidered.Asummationoperatorisusedtode-terminetheoverallcostofrepair.Ifafixedbounduponthesizeofanypotentialbreak-setcanbeformed,theWSSalgorithmisNP-complete.ForamoredetaileddescriptionoftheWSSsearchalgo-rithm,thereaderisreferredto[13],sinceacompletedescriptionofthealgorithmisbeyondthescopeofthispaper.
EXAMPLE1.WeshallstepthroughtheexamplegiveninTa-ble1whensearchingforaWSS.Eachbidisrepresentedbyasin-glevariablewithdomainvaluesof0and1,theformerrepresentingbid-failureandthelatterbid-success.Theprobabilityoffailureofthevariablesare0.1whentheyareassignedto1and0.0other-wise.TheproblemisinitiallysolvedusinganILPsolversuchaslp_solve[3]orCPLEX,andtheoptimalrevenueisfoundtobe200.Afixedpercentageofthisrevenuecanbeusedasathresholdvalueforarobustsolutionanditsrepairs.Thebid-takerwishestohavearobustsolutionsothatifasinglewinningbidiswithdrawn,arepairsolutioncanbeformedwithoutwithdrawingitemsfromanyotherwinningbidder.Thisexamplemaybeseenassearchingfora(0.1,0)-weightedsupersolution,βis0becausenofundsareavailabletocompensatethewithdrawalofitemsfromwinningbid-ders.Thebid-takeriswillingtocompromiseonrevenue,butonlyby5%,say,oftheoptimalvalue.
Bids1and3cannotbothsucceed,sincetheybothrequireitem
A,soaconstraintisaddedprecludingtheassignmentinwhichbothvariablestakethevalue1.Similarly,bids2and3cannotbothwinsoanotherconstraintisaddedbetweenthesetwovariables.There-fore,inthisexamplethesetofCSPvariablesisV={x1,x2,x3},whosedomainsareall{0,1}.Theconstraintsarex1+x3≤1,x+x≤1and
23xi∈Vaixi≥190,whereaireflectstherele-vantbid-amountsfortherespectivebidvariables.Inordertofindarobustsolutionofoptimalrevenueweseektomaximizethesumoftheseamounts,maxxi∈Vaixi.
Whenallvariablesaresetto0(seeFigure1(a)branch3),thisisnotasolutionbecausetheminimumrevenueof190hasnotbeenmet,sowetryassigningbid3to1(branch4).Thisisavalidsolu-tionbutthisvariableisbrittlebecausethereisa10%chancethatthisbidmaybewithdrawn(seeTable1).Thereforeweneedtode-termineifarepaircanbeformedshoulditbreak.Thesearchforarepairbeginsatthefirstnode,seeFigure1(b).Noticethatvalue1hasbeenremovedfrombid3becausethissearchtreeissimulatingthewithdrawalofthisbid.Whenbid1issetto0(branch4.1),themaximumrevenuesolutionintheremainingsubtreehasrevenueofonly100,thereforesearchisdiscontinuedatthatnodeofthetree.Bid1andbid2arebothassignedto1(branches4.2and4.4)andthetotalcostofboththesechangesisstill0becausenocompensa-tionneedstobepaidforbidsthatchangefromlosingtowinning.Withbid3nowlosing(branch4.5),thisgivesarepairsolutionof200.Hence0,0,1isreparableandthereforeaWSS.WecontinueoursearchinFigure1(a)however,becauseweareseekingarobustsolutionofoptimalrevenue.
Whenbid1isassignedto1(branch6)weseekapartialrepairforthisvariablebreaking(branch5isnotconsideredsinceitoffersinsufficientrevenue).Therepairsearchsetsbid1to0inaseparatesearchtree,(notshown),andcontrolisreturnedtothesearchforaWSS.Bid2issetto0(branch7),butthissolutionwouldnotproducesufficientrevenuesobid2isthensetto1(branch8).Wethenattempttoextendtherepairforbid1(notshown).Thisfailsbecausetherepairforbid1cannotassignbid2to0becausethecostofrepairingsuchanassignmentwouldbe∞,giventhattheauctionrulesdonotpermitthewithdrawalofitemsfromwinningbids.Arepairforbid1breakingisthereforenotpossiblebecauseitemshavealreadybeenawardedtobid2.Arepairsolutionwithbid2assignedto1doesnotproducesufficientrevenuewhenbid1isassignedto0.Theinabilitytowithdrawitemsfromwinningbidsimpliesthat1,1,0isanirreparablesolutionwhentheminimumtolerablerevenueisgreaterthan100.TheitalicizedcommentsanddashedlineinFigure1(a)illustratethesearchpathforaWSSifbothofthesebidsweredeemedreparable.Section4introducesanalternativeauctionmodelthatwillallowthebid-takertoreceivecompensationforbreakagesandinturnusethispaymenttocompensateotherbiddersforwithdrawalofitemsfromwinningbids.Thiswillenablethereallocationofitemsandpermittheestablishmentof1,1,0asasecondWSSforthisex-ample.
4.
MUTUALBIDBONDS:ABACKTRACK-INGMECHANISM
Someauctionsolutionsareinherentlybrittleanditmaybeim-possibletofindarobustsolution.Ifwecanaltertherulesofanauctionsothatthebid-takercanretractitemsfromwinningbid-ders,thenthereparabilityofsolutionstosuchauctionsmaybeim-proved.Inthissectionweproposeanauctionmodelthatpermitsbidanditemwithdrawalbythebiddersandbid-taker,respectively.Weproposeamodelthatincorporatesmutualbidbondstoenablesolutionreparabilityforthebid-taker,aformofinsuranceagainst
16Find partial repair for bid 1 breakage18(a) Extend partial repair for bid 1 breakage1(b) Find partial repair 9for bid 2 breakage01Bid 12057Bid 23Bid 30[0]04[190]Find repair solution for bid 3 breakage101Insufficient revenue100Insufficient revenue1[100][100]Insufficient revenue[200]Find repair solutions for bid 1 & 2 breakages(a)SearchforWSS.
4.14.2Bid 10Insufficient revenue4.3Insufficient revenue11inertia=04.4inertia=0Bid 201014.50inertia=0Bid 3010101(b)Searchforarepairforbid3breakage.
Figure1:SearchTreeforaWSSwithoutitemwithdrawal.
thewinner’scurseforthebidderwhilstalsocompensatingbiddersinthecaseofitemwithdrawalfromwinningbids.Weproposethatsuch“Winner’sCurse&Bid-taker’sExposure”insurancecompriseafixedpercentage,κ,ofthebidamountforallbids.Suchmutualbidbondsaremandatoryforeachbidinourmodel2.Theconditionsattachedtothebidbondsarethatthebid-takerbeallowedtoannulwinningbids(itemwithdrawal)whenrepairingbreakselsewhereinthesolution.Intheinterestsoffairness,compensationispaidtobiddersfromwhomitemsarewithdrawnandisequivalenttothepenaltythatwouldhavebeenimposedonthebiddershouldhehavewithdrawnthebid.
Combinatorialauctionsimposeaheavycomputationalburdenonthebiddersoitisimportantthatthehedgingofriskshouldbeasimpleandtransparentoperationforthebiddersoasnottofur-therincreasethisburdenunnecessarily.Wealsocontendthatitisimperativethatthebidderknowsthepotentialpenaltyforwith-drawalinadvanceofbidsubmission.Thisinformationisessentialforbidderswhendetermininghowaggressivetheyshouldbeintheirbiddingstrategy.Bidbondsarecommonplaceinprocurementforconstructionprojects.Usuallytheyaremandatoryforallbids,areafixedpercentage,κ,ofthebidamountandareunidirectionalinthatitemwithdrawalbythebid-takerisnotpermitted.Mutualbidbondsmaybeseenasaformofleveledcommitmentcontractinwhichbothpartiesmaybreakthecontractforthesamefixedpenalty.Suchcontractspermitunilateraldecommitmentforpre-specifiedpenalties.Sandholmetal.showedthatthiscanincreasetheexpectedpayoffsofallpartiesandenablesdealsthatwouldbeimpossibleunderfullcommitment[26,28,29].
Inpracticeabidbondtypicallyrangesbetween5and20%oftheMakingtheinsuranceoptionalmaybebeneficialinsomein-stances.Ifabidderdoesnotagreetotheinsurance,itmaybein-ferredthathemayhaveaccuratelydeterminedthevaluationfortheitemsandthereforelesslikelytofallvictimtothewinner’scurse.Theprobabilityofsuchabidbeingwithdrawnmaybeless,soare-pairsolutionmaybedeemedunnecessaryforthisbid.Ontheotherhanditdecreasesthereparabilityofsolutions.
2
bidamount[14,18].Ifthedecommitmentpenaltiesarethesameforbothpartiesinallbids,κdoesnotinfluencethereparabilityofagivensetofbids.Itmerelyinfluencesthelevelsofpenaltiesandcompensationtransactedbyagents.Lowvaluesofκincurlowbidwithdrawalpenaltiesandsimulateadictatorialbid-takerwhodoesnotadequatelycompensatebiddersforitemwithdrawal.AnderssonandSandholm[1]foundthatmyopicagentsreachahighersocialwelfarequickeriftheyactselfishlyratherthancooperativelywhenpenaltiesinleveledcommitmentcontractsarelow.Increasedlevelsofbidwithdrawalarelikelywhenthepenaltiesarelowalso.
Highvaluesofκtendtowardsfull-commitmentandreducetheadvantagesofsuch“Winner’sCurse&Bid-taker’sExposure”in-surance.Thepenaltiespaidareusedtofundareassignmentofitemstoformarepairsolutionofsufficientrevenuebycompensat-ingpreviouslysuccessfulbiddersforwithdrawaloftheitemsfromthem.
EXAMPLE2.ConsidertheexamplegiveninTable1oncemore,wherethebidsalsocompriseamutualbidbondof5%ofthebidamount.Ifabidiswithdrawn,thebidderforfeitsthisamountandthebid-takercanthencompensatewinningbidderswhoseitemsarewithdrawnwhentryingtoformarepairsolutionlater.Thesearchforrepairsolutionsforbreakstobid1andbid2appearinFigures2(a)and2(b),respectively3.
Whenbid1breaks,thereisacompensationpenaltypaidtothebid-takerequalto5thatcanbeusedtofundareassignmentoftheitems.Wethereforesetβto5andthisbecomesthemaximumexpenditureallowedtowithdrawitemsfromwinningbidders.βmayalsobeviewedasthesizeofthefundavailabletofacilitatebacktrackingbythebid-taker.Whenweextendthepartialrepairforbid1sothatbid2losesanitem(branch8.1),theoverallcostofrepairincreasesto5,duetothisitemwithdrawalbythebid-taker,TheactualimplementationofWSSsearchchecksprevioussolu-tionstoseeiftheycanrepairbreaksbeforesearchingforanewrepairsolution.0,0,1isasolutionthathasalreadybeenfoundsothesearchforarepairinthisexampleisnotstrictlynecessarybutisdescribedforpedagogicalreasons.
3
6.1inertia=0 =58.2inertia=10 =10Bid 18.1inertia=5 =59.201Bid 18.3inertia=10 =109.401Bid 29.1Bid 3001Bid 29.3Bid 3011inertia=5 =501inertia=10 =10Insufficient revenueInsufficient revenue(a)Searchforarepairforbid1breakage.(b)Searchforarepairforbid2breakage.
Figure2:RepairSearchTreeforbreaks1and2,κ=0.05.
andisjustwithinthelimitgivenbyβ.InFigure1(a)thesearchpathfollowsthedashedlineandsetsbid3tobe0(branch9).Therepairsolutionsforbids1and2canbeextendedfurtherbyassigningbid3to1(branches9.2and9.4).Therefore,1,1,0maybeconsideredarobustsolution.Recall,thatpreviouslythiswasnotthecase.Usingmutualbidbondsthusincreasesreparabilityandallowsarobustsolutionofrevenue200asopposedto190,aswaspreviouslythecase.
5.EXPERIMENTS
WehaveusedtheCombinatorialAuctionTestSuite(CATS)[16]togeneratesampleauctiondata.Wegenerated100instancesofproblemsinwhichthereare20itemsforsaleand100-2000bidsthatmaybedominatedinsomeinstances4.Suchdominatedbidscanparticipateinrepairsolutionsalthoughtheydonotfeatureinoptimalsolutions.CATSuseseconomicallymotivatedbiddingpat-ternstogenerateauctiondatainvariousscenarios.Tomotivatetheresearchpresentedinthispaperweusesensitivityanalysistoex-aminethebrittlenessofoptimalsolutionsandhencedeterminethetypesofauctionsmostlikelytobenefitfromarobustsolution.WethenestablishrobustsolutionsforCAsusingtheWSSframework.
5.1SensitivityAnalysisfortheWDP
Wehaveperformedsensitivityanalysisofthefollowingfourdis-tributions:airporttake-off/landingslots(matching),electroniccomponents(arbitrary),property/spectrum-rights(regions)andtransportation(paths).Thesedistributionswerechosenbe-causetheydescribeabroadarrayofbiddingpatternsindifferentapplicationdomains.
Themethodusedisasfollows.Wefirstofalldeterminedtheoptimalsolutionusinglp_solve,amixedintegerlinearprogramsolver[3].Wethensimulatedasinglebidwithdrawalandre-solvedtheproblemwiththeotherwinningbidsremainingfixed,i.e.therewerenoinvoluntarydropouts.Theoptimalrepairsolutionwasthendetermined.Thisprocessisrepeatedforallwinningbidsintheoveralloptimalsolution,thusassumingthatallbidsarebrittle.Figure3showstheaveragerevenueofsuchrepairsolutionsasapercentageoftheoptimum.Alsoshownistheaverageworst-casescenarioover100auctions.Wealsoimplementedanauctionrulethatdisallowsbidsfromtherenegingbidderparticipateinarepair5.Figure3(a)illustrateshowthepathsdistributionisinherentlythemostrobustdistributionsincewhenanywinningbidiswith-drawnthesolutioncanberepairedtoachieveover98.5%ofthe4
setTheCATSflagsincludedintpriceswith5
to1000.thebidalphaparameterdummyWeassumeditemwerethatfromallbidsthesameinabidder.
givenXORbidwiththesameoptimalrevenueonaverageforauctionswithmorethan250bids.Therearesomecaseshoweverwhensuchwithdrawalsresultinso-lutionswhoserevenueissignificantlylowerthanoptimum.Eveninauctionswithasmanyas2000bidsthereareoccasionswhenasinglebidwithdrawalcanresultinadropinrevenueofover5%,althoughtheaverageworst-casedropinrevenueisonly1%.Fig-ure3(b)showshowthematchingdistributionismorebrittleonaveragethanpathsandalsohasaninferiorworst-caserevenueonaverage.Thistrendcontinuesastheregions-npv(Figure3(c))andarbitrary-npv(Figure3(d))distributionsaremorebrit-tlestill.Thesedistributionsareclearlysensitivetobidwithdrawalwhennootherwinningbidsinthesolutionmaybeinvoluntarilywithdrawnbythebid-taker.
5.2RobustSolutionsusingWSS
Inthissectionwefocusuponboththearbitrary-npvandregions-npvdistributionsbecausethesensitivityanalysisindi-catedthatthesetypesofauctionsproduceoptimalsolutionsthattendtobemostbrittle,andthereforestandtobenefitmostfromso-lutionrobustness.Weignoretheauctionswith2000bidsbecausethesensitivityanalysishasindicatedthattheseauctionsareinher-entlyrobustwithaverylowaveragedropinrevenuefollowingabidwithdrawal.Theywouldalsobeverycomputationallyexpensive,giventheextracomplexityoffindingrobustsolutions.
ApureCPapproachneedstobeaugmentedwithglobalcon-straintsthatincorporateoperationsresearchtechniquestoincreasepruningsufficientlysothatthousandsofbidsmaybeexamined.Globalconstraintsexploitspecial-purposefilteringalgorithmstoimproveperformance[21].ThereareanumberofwaystospeedupthesearchforaweightedsupersolutioninaCA,althoughthisisnotthemainfocusofourcurrentwork.Polynomialmatchingalgorithmsmaybeusedinauctionswhosebidlengthisshort,suchasthoseforairportlanding/take-offslotsforexample.TheintegerprogrammingformulationoftheWDPstipulatesthatabideitherlosesorwins.Ifwerelaxthisconstraintsothatbidscanpartiallywin,thiscorrespondstothelinearrelaxationoftheproblemandissolvableinpolynomialtime.Ateachnodeofthesearchtreewecanquicklysolvethelinearrelaxationoftheremainingprobleminthesubtreebelowthecurrentnodetoestablishanupperboundonremainingrevenue.Ifthisupperboundplusrevenueintheparenttreeislessthanthecurrentlowerboundonrevenue,searchatthatnodecancease.The(continuous)LPrelaxationthusprovidesavi-talspeed-upinthesearchforweightedsupersolutions,whichwehaveexploitedinourimplementation.TheLPformulationisasfollows:
max
aixi
xi∈V
100100
9595
Revenue (% of optimum)90
Revenue (% of optimum)Average Repair Solution RevenueWorst-case Repair Solution Revenue
250
500
750
1000
Bids
1250
1500
1750
2000
90
8585
8080
7575
Average Repair Solution RevenueWorst-case Repair Solution Revenue
250
500
750
1000
Bids
1250
1500
1750
2000
(a)paths
100
100
(b)matching
9595
Revenue (% of optimum)90
Revenue (% of optimum)Average Repair Solution RevenueWorst-case Repair Solution Revenue
250
500
750
1000
Bids
1250
1500
1750
2000
90
8585
8080
7575
Average Repair Solution RevenueWorst-case Repair Solution Revenue
250
500
750
1000
Bids
1250
1500
1750
2000
(c)regions-npv(d)arbitrary-npv
Figure3:Sensitivityofbiddistributionstosinglebidwithdrawal.
s.t.
j|i∈Sj
xj≤1,∀i∈{1...m},xj≥0,xj∈R.
Additionaltechniques,thatareoutlinedin[25],canaidthescal-abilityofaCPapproachbutourmainaimintheseexperimentsistoexaminetherobustnessofvariousauctiondistributionsandcon-siderthetradeoffbetweenrobustnessandrevenue.TheWSSsolverwehavedevelopedisanextensionofthesupersolutionsolverpre-sentedin[9,10].Thissolveris,inturn,basedupontheEFCcon-straintsolver[2].
Combinatorialauctionsareeasilymodeledasaconstraintopti-mizationproblems.Wehavechosenthebranch-on-bidsformula-tionbecauseintestsitworkedfasterthanabranch-on-itemsfor-mulationforthearbitrary-npvandregions-npvdistribu-tions.Allvariablesarebinaryandoursearchmechanismusesare-verselexicographicvalueorderingheuristic.Thiscomplementsourdynamicvariableorderingheuristicthatselectsthemostpromisingunassignedvariableasthenextoneinthesearchtree.WeusetheproductofthesolutionoftheLPrelaxationandthedegreeofavariabletodeterminethelikelihoodofitsparticipationinarobustsolution.HighvaluesintheLPsolutionareastrongindicationofvariablesmostlikelytoformahighrevenuesolutionwhilsttheavariable’sdegreereflectsthenumberofotherbidsthatoverlapintermsofdesireditems.Bidsforlargenumbersofitemstendtobemorerobust,whichiswhyweweightourrobustsolutionsearchinthismanner.WefoundthisheuristictobeslightlymoreeffectivethantheLPsolutionalone.Asthenumberofbidsintheauctionincreaseshowever,thereisanincreaseintheinherentrobustnessofsolutionssothedegreeofavariablelosessignificanceastheauctionsizeincreases.
5.3Results
Ourexperimentssimulatethreedifferentconstraintsonrepairsolutions.Thefirstisthatnowinningbidsarewithdrawnbythe
bid-takerandarepairsolutionmustreturnarevenueofatleast90%oftheoptimaloverallsolution.Secondly,werelaxedtherevenueconstraintto85%ofoptimum.Thirdly,weallowedbacktrackingbythebid-takeronwinningbidsusingmutualbidbondsbutmain-tainingtherevenueconstraintat90%ofoptimum.
PriortofindingarobustsolutionwesolvedtheWDPoptimallyusinglp_solve[3].Wethensettheminimumtolerablerevenueforasolutiontobe90%(then85%)oftherevenueofthisopti-malsolution.Weassumedthatallbidswerebrittle,thusarepairsolutionisrequiredforeverybidinthesolution.Initiallyweas-sumethatnobacktrackingwaspermittedonassignmentsofitemstootherwinningbidsgivenabidwithdrawalelsewhereintheso-lution.Table2showsthepercentageofoptimalsolutionsthatarerobustforminimumrevenueconstraintsforrepairsolutionsof90%and85%ofoptimalrevenue.Relaxingtherevenueconstraintonre-pairsolutionsto85%oftheoptimumrevenuegreatlyincreasesthenumberofoptimalsolutionsthatarerobust.Wealsoconductedexperimentsonthesameauctionsinwhichbacktrackingbythebid-takerispermittedusingmutualbidbonds.Thissignificantlyimprovesthereparabilityofoptimalsolutionswhilststillmaintain-ingrepairsolutionsof90%ofoptimum.Aninterestingfeatureofthearbitrary-npvdistributionisthatoptimalsolutionscanbecomemorebrittleasthenumberofbidsincreases.Thereasonforthisisthatoptimalsolutionsforlargerauctionshavemorewin-ningbids.Someoftheoptimalsolutionsforthesmallestauctionswith100bidshaveonlyonewinningbidder.Ifthisbidiswith-drawnitisusuallyeasytofindanewrepairsolutionwithin90%ofthepreviousoptimalrevenue.Also,repairsolutionsforbidsthatcontainasmallnumberofitemsmaybemadedifficultbythefactthatareducednumberofbidscoveronlyasubsetofthoseitems.Amitigatingfactoristhatsuchbidsformasmallerpercentageoftherevenueoftheoptimalsolutiononaverage.
Wealsoimplementedarulestipulatingthatanylosingbidsfrom
100
Table2:OptimalSolutionsthatareInherentlyRobust(%).
#Bids
98
MinRevenue
10025050010002000arbitrary-npvrepair≥90%21533793repair≥85%
26154087100MBB&repair≥90%41356094≥93regions-npvrepair≥90%3033619198repair≥85%
507195100100MBB&repair≥90%
60
78
96
99
≥98
Table3:OccurrenceofRobustSolutions(%).
#Bids
MinRevenue
1002505001000arbitrary-npvrepair≥90%58395198repair≥85%
86889499MBB&repair≥90%788698100regions-npvrepair≥90%617097100repair≥85%
899999100MBB&repair≥90%
83
96
100
100
awithdrawingbiddercannotparticipateinarepairsolution.Thisactsasadisincentiveforstrategicwithdrawalandwasalsousedpreviouslyinthesensitivityanalysis.Insomeauctions,arobustso-lutionmaynotexist.Table3showsthepercentageofauctionsthatsupportrobustsolutionsforthearbitrary-npvandregions-npvdistributions.Itisclearthatfindingrobustsolutionsfortheformerdistributionisparticularlydifficultforauctionswith250and500bidswhenrevenueconstraintsare90%ofoptimum.Thisdif-ficultywaspreviouslyalludedtobythelowpercentageofoptimalsolutionsthatwererobustfortheseauctions.Relaxingtherevenueconstrainthelpsincreasethepercentageofauctionsinwhichrobustsolutionsareachievableto88%and94%,respectively.Thisim-provesthereparabilityofallsolutionstherebyincreasingtheaver-agerevenueoftheoptimalrobustsolution.Itissomewhatcounter-intuitivetoexpectareductioninreparabilityofauctionsolutionsasthenumberofbidsincreasesbecausetheretendstobeanincreasednumberofsolutionsabovearevenuethresholdinlargerauctions.TheMBBauctionmodelperformsverywellhowever,andensuresthatrobustsolutionsareachievableforsuchinherentlybrittleauc-tionswithoutsacrificingover10%ofoptimalrevenuetoachieverepairsolutions.
Figure4showstheaveragerevenueoftheoptimalrobustsolu-tionasapercentageoftheoveralloptimum.RepairsolutionsfoundforaWSSprovidealowerboundonpossiblerevenuefollowingabidwithdrawal.Notethatinsomeinstancesitispossibleforarepairsolutiontohavehigherrevenuethantheoriginalsolution.Whenbacktrackingonwinningbidsbythebid-takerisdisallowed,thiscanonlyhappenwhentherepairsolutionincludestwoormorebidsthatwerenotintheoriginal.Otherwisetherepairbidswouldparticipateintheoptimalrobustsolutioninplaceofthebidthatwaswithdrawn.AWSSguaranteesminimumlevelsofrevenueforrepairsolutionsbutthisisnottosaythatrepairsolutionscannotbeimprovedupon.Itispossibletouseanincrementalalgorithmto)mumitpo fo %96
( euneveR94
Repair Revenue: Min 90% Optimal92
MBB: Repair Revenue: Min 90% Optimal
Repair Revenue: Min 85% Optimal 250
500
750
1000 1250
1500
1750
2000
Bids
(a)regions-npv
100
98
)mumitpo fo %96
( euneveR94
Repair Revenue: Min 90% OptimalMBB: Repair Revenue: Min 90% Optimal
Repair Revenue: Min 85% Optimal92
250
500
750
1000 1250
1500
1750
2000
Bids
(b)arbitrary-npv
Figure4:Revenueofoptimalrobustsolutions.
determineanoptimalrepairsolutionfollowingabreak,whilstsafeintheknowledgethatinadvanceofanypossiblebidwithdrawalwecanestablishalowerboundontherevenueofarepair.Kastneretal.haveprovidedsuchanincrementalILPformulation[15].Mutualbidbondsfacilitatebacktrackingbythebid-takeronal-readyassigneditems.Thisimprovesthereparabilityofallpos-siblesolutionsthusincreasingtherevenueoftheoptimalrobustsolutiononaverage.Figure4showstheincreaseinrevenueofrobustsolutionsinsuchinstances.Therevenuesofrepairsolu-tionsareboundedbyatleast90%oftheoptimuminourexperi-mentstherebyallowingadirectcomparisonwithrobustsolutionsalreadyfoundusingthesamerevenueconstraintbutnotprovidingforbacktracking.Itisimmediatelyobviousthatsuchamechanismcansignificantlyincreaserevenuewhilststillmaintainingsolutionrobustness.
Table4showsthenumberofwinningbidsparticipatinginop-timalandoptimalrobustsolutionsgiventhethreedifferentcon-straintsonrepairingsolutionslistedatthebeginningofthissec-tion.Asthenumberofbidsincreases,moreoftheoptimaloverallsolutionsarerobust.Thisleadstoaconvergenceinthenumberofwinningbids.Thenumbersinbracketsarederivedfromthesensi-tivityanalysisofoptimalsolutionsthatrevealsthefactthatalmostalloptimalsolutionsforauctionsof2000bidsarerobust.Wecanthereforeinferthattheaveragenumberofwinningbidsinrevenue-maximizingrobustsolutionsconvergestowardsthatoftheoptimaloverallsolutions.
Anotableside-effectofrobustsolutionsisthatfewerbidspartic-ipateinthesolutions.ItcanbeclearlyseenfromTable4thatwhenrevenueconstraintsonrepairsolutionsaretight,therearefewerwinningbidsintheoptimalrobustsolutiononaverage.Thisisparticularlypronouncedforsmallerauctionsinbothdistributions.Thiscanwinbenefitsforthebid-takersuchasreducedoverheadsindealingwithfewersuppliers.AlthoughMBBsaidsolutionrepara-
Table4:Numberofwinningbids.
#Bids
Solution
10025050010002000arbitrary-npvOptimal
3.315.607.179.3110.63Repair≥90%1.402.186.109.03(≈10.63)Repair≥85%1.653.816.789.31(10.63)MBB(≥90%)2.335.497.339.34(≈10.63)regions-npvOptimal
4.347.059.1010.6712.76Repair≥90%3.035.768.6710.63(≈12.76)Repair≥85%3.456.759.07(10.67)(12.76)MBB(≥90%)
3.90
6.86
9.10
10.68
(≈12.76)
bility,thenumberofbidsinthesolutionsincreasesonaverage.Thisistobeexpectedbecauseagreaterfractionofthesesolutionsareinfactoptimal,aswesawinTable2.
6.DISCUSSIONANDFUTUREWORK
Biddingstrategiescanbecomecomplexinnon-incentive-compat-iblemechanismswherewinnerdeterminationisnolongernecessar-ilyoptimal.Theperceivedreparabilityofabidmayinfluencethebidamount,withreparablebidsreachingalowerequilibriumpointandperceivedirreparablebidsbeingmoreaggressive.
Penaltypaymentsforbidwithdrawalalsocreateanincentiveformoreaggressivebiddingbyprovidingaformofinsuranceagainstthewinner’scurse[8].Ifawinningbidder’srevisedvaluationforasetofitemsdropsbymorethanthepenaltyforwithdrawalofthebid,thenitisinhisbestintereststoforfeittheitem(s)andpaythepenalty.Shouldtheauctionrulesstatethatthebid-takerwillrefusetoselltheitemstoanyoftheremainingbiddersintheeventofawithdrawal,theninsuranceagainstpotentiallosseswillstimu-latemoreaggressivebidding.However,inourcaseweareseekingtorepairthesolutionwiththegivenbids.Aside-effectofsuchapolicyistooffsettheincreasedaggressivenessbyincentivizingre-ducedvaluationsinexpectationthatanotherbidder’ssuccessfulbidiswithdrawn.HarstadandRothkopf[8]examinedtheconditionsrequiredtoensureanequilibriumpositioninwhichbiddingwasatleastasaggressiveasifnobidwithdrawalwaspermitted,giventhiscountervailingincentivetounder-estimateavaluation.Threema-jorresultsarosefromtheirstudyofbidwithdrawalinasingleitemauction:
1.Equilibriumbiddingismoreaggressivewithwithdrawalforsufficientlysmallprobabilitiesofanawardtothesecondhigh-estbidderintheeventofabidwithdrawal;
2.Equilibriumbiddingismoreaggressivewithwithdrawalifthenumberofbiddersislargeenough;
3.Formanydistributionsofcostsandestimates,equilibriumbiddingismoreaggressivewithwithdrawalifthevariabilityoftheestimatingdistributionissufficientlylarge.Itisimportantthatmutualbidbondsdonotresultindepressedbiddinginequilibrium.Ananalysisoftheresultantbehaviorofbid-dersmustincorporatethepossibilityofabidderwinninganitemandhavingitwithdrawninorderforthebid-takertoformulatearepairsolutionafterabreakelsewhere.HarstadandRothkopfhaveanalyzedbidderaggressiveness[8]usingastrictlygame-theoreticmodelinwhichtheonlyreasonforbidwithdrawalisthewinner’s
curse.Theyassumedallbidderswererisk-neutral,butsurmisedthatitisentirelypossibleforthebid-takertocollectariskpremiumfromrisk-aversebidderswiththeofferofsuchinsurance.Combi-natorialauctionswithmutualbidbondsaddanextraincentivetobidaggressivelybecauseofthepossibilityofbeingcompensatedforhavingawinningbidwithdrawnbyabid-taker.Thisismilitatedagainstbytheincreasedprobabilityofnothavingitemswithdrawninarepairsolution.Weleaveanin-depthanalysisofthesufficientconditionsformoreaggressivebiddingforfuturework.
WhilsttheWSSframeworkprovidesampleflexibilityandex-pressiveness,scalabilitybecomesaproblemforlargerauctions.Althoughsolutionstolargerauctionstendtobenaturallymorero-bust,somebid-takersinsuchauctionsmayrequirerobustness.Apossibleextensionofourworkinthispapermaybetoexaminethefeasibilityofreformulatingintegerlinearprogramssothattheso-lutionsarerobust.Hebrardetal.[10]examinedreformulationofCSPsforfindingsupersolutions.Alternatively,itmaybepossi-bletouseatop-downapproachbylookingatthek-bestsolutionssequentially,intermsofrevenue,andperformingsensitivityanaly-sisuponeachsolutionuntilarobustoneisfound.Inprocurementsettingstheprincipleoffreedisposalisoftendiscountedandallitemsmustbesold.Thisreducesthenumberofpotentialsolutionsandtherebyreducesthereparabilityofeachsolution.Theimpactofsuchaconstraintonrevenueofrobustsolutionsisalsoleftforfuturework.
Thereisanotherinterestingdirectionthisworkmaytake,namelyrobustmechanismdesign.Porteretal.introducedthenotionoffaulttolerantmechanismdesigninwhichagentshaveprivatein-formationregardingcostsfortaskcompletion,butalsotheirprob-abilitiesoffailure[20].Whenthebid-takerhascombinatorialval-uationsfortaskcompletionsitmaybedesirabletoassignthesametasktomultipleagentstoensuresolutionrobustness.Itisdesirabletominimizesuchpotentiallyredundanttaskassignmentsbutnottothedetrimentofcompletedtaskvaluations.ThisproblemcouldbemodeledusingtheWSSframeworkinasimilarmannertothatofcombinatorialauctions.
Inthecasewherenorobustsolutionsarefound,itispossibletooptimizerobustness,insteadofrevenue,byfindingasolutionofatleastagivenrevenuethatminimizestheprobabilityofanir-reparablebreak.Inthismannertheleastbrittlesolutionofadequaterevenuemaybechosen.
7.CONCLUSION
Fairnessisoftencitedasareasonforchoosingtheoptimalsolu-tionintermsofrevenueonly[22].Robustsolutionsmilitateagainstbidsdeemedbrittle,thereforebiddersmustearnareputationforbeingreliabletorelaxthereparabilityconstraintattachedtotheirbids.Thismaybeseenasbeingfairtolong-standingbusinesspartnerswhosereliabilityisunquestioned.Internet-basedauctionsareoftenseenasunwelcomeprice-gougingexercisesbysuppliersinmanysectors[6,17].Traditionalbusinesspartnershipsarebe-ingseveredbyincreasedcompetitionamongstsuppliers.QualityofServicecansufferbecauseoftheincreasedfocusonshort-termprofitabilitytothedetrimentofthebid-takerinthelong-term.Ro-bustsolutionscanprovideameansofselectivelydiscriminatingagainstdistrustedbiddersinameasuredmanner.Ascombinato-rialauctiondeploymentmovesfromlargevalueauctionswithasmallpooloftrustedbidders(e.g.spectrum-rightssales)towardslowervalueauctionswithpotentiallyunknownbidders(e.g.Sup-plyChainManagement[30]),solutionrobustnessbecomesmorerelevant.Aswellasbeingusedtoensurethatthebid-takerisnotleftvulnerabletobidwithdrawal,itmayalsobeusedtocementrelationshipswithpreferred,possiblyincumbent,suppliers.
WehaveshownthatitispossibletoattainrobustsolutionsforCAswithonlyasmalllossinrevenue.Wehavealsoillustratedhowsuchsolutionstendtohavefewerwinningbidsthanoveralloptimalsolutions,therebyreducinganyoverheadsassociatedwithdealingwithmorebidders.Wehavealsodemonstratedthatintro-ducingmutualbidbonds,aformofleveledcommitmentcontract,cansignificantlyincreasetherevenueofoptimalrobustsolutionsbyimprovingreparability.Wecontendthatrobustsolutionsus-ingsuchamechanismcanallowabid-takertoofferthepossibilityofbidwithdrawaltobidderswhilstremainingconfidentaboutpost-repairrevenueandalsofacilitatingincreasedbidderaggressiveness.
8.REFERENCES
[1]MartinAnderssonandTuomasSandholm.Leveled
commitmentcontractswithmyopicandstrategicagents.JournalofEconomicDynamicsandControl,25:615–640,2001.SpecialissueonAgent-BasedComputationalEconomics.
[2]FahiemBacchusandGeorgeKatsirelos.EFCsolver.
www.cs.toronto.edu/˜gkatsi/efc/efc.html.[3]MichaelBerkelaar,KjellEikland,andPeterNotebaert.
lpsolveversion5.0.10.0.
http://groups.yahoo.com/group/lp_solve/.[4]RinaDechter.ConstraintProcessing.MorganKaufmann,
2003.
[5]SvenDeVriesandRakeshVohra.Combinatorialauctions:A
survey.INFORMSJournalonComputing,pages284–309,2003.
[6]JimEricson.Reverseauctions:Badidea.Line56,Sept2001.[7]MatthewL.Ginsberg,AndrewJ.Parkes,andAmitabhaRoy.
SupermodelsandRobustness.InProceedingsofAAAI-98,pages334–339,Madison,WI,1998.
[8]RonaldM.HarstadandMichaelH.Rothkopf.Withdrawable
bidsaswinner’scurseinsurance.OperationsResearch,43(6):982–994,November-December1995.
[9]EmmanuelHebrard,BrahimHnich,andTobyWalsh.Robust
solutionsforconstraintsatisfactionandoptimization.InProceedingsoftheEuropeanConferenceonArtificialIntelligence,pages186–190,2004.
[10]EmmanuelHebrard,BrahimHnich,andTobyWalsh.Super
solutionsinconstraintprogramming.InProceedingsofCP-AI-OR2004,pages157–172,2004.
[11]GailHohner,JohnRich,EdNg,GrantReid,AndrewJ.
Davenport,JayantR.Kalagnanam,HoSooLee,andChaeAn.Combinatorialandquantity-discountprocurementauctionsbenefitMarsIncorporatedanditssuppliers.Interfaces,33(1):23–35,2003.
[12]AlanHollandandBarryO’Sullivan.Supersolutionsfor
combinatorialauctions.InErcim-ColognetConstraintsWorkshop(CSCLP04).SpringerLNAI,Lausanne,Switzerland,2004.
[13]AlanHollandandBarryO’Sullivan.Weightedsuper
solutionsforconstraintprograms,December2004.TechnicalReport:No.UCC-CS-2004-12-02.
[14]SelectiveInsurance.Businessinsurance.
http://www.selectiveinsurance.com/psApps/Business/Ins/bonds.asp?bc=13.16.127.[15]RyanKastner,ChristinaHsieh,MiodragPotkonjak,and
MajidSarrafzadeh.Onthesensitivityofincremental
algorithmsforcombinatorialauctions.InWECWIS,pages81–88,June2002.
[16]KevinLeyton-Brown,MarkPearson,andYoavShoham.
Towardsauniversaltestsuiteforcombinatorialauctionalgorithms.InACMConferenceonElectronicCommerce,pages66–76,2000.
[17]AssociatedGeneralContractorsofAmerica.Associated
generalcontractorsofAmericawhitepaperonreverseauctionsforprocurementofconstruction.
http://www.agc.org/content/public/pdf/Member_Resources/
ReverseAuctionWhitePaper.pdf,2003.
[18]NationalSocietyofProfessionalEngineers.Abasicguideto
suretybonds.http://www.nspe.org/pracdiv/76-02surebond.asp.
[19]MartinPesendorferandEstelleCantillon.Combination
biddinginmulti-unitauctions.HarvardBusinessSchoolWorkingDraft,2003.
[20]RyanPorter,AmirRonen,YoavShoham,andMoshe
Tennenholtz.Mechanismdesignwithexecutionuncertainty.InProceedingsofUAI-02,pages414–421,2002.[21]Jean-CharlesR´egin.Globalconstraintsandfiltering
algorithms.InConstraintandIntegerProgramming–TowardsaUnifiedMethodology,chapter4,pages89–129.KluwerAcademicPublishers,2004.
[22]MichaelH.RothkopfandAleksandarPeke˘c.Combinatorial
auctiondesign.ManagementScience,4(11):1485–1503,November2003.
[23]MichaelH.Rothkopf,AleksandarPeke˘c,andRonaldM.
Harstad.Computationallymanageablecombinatorialauctions.ManagementScience,44(8):1131–1147,1998.[24]DanielSabinandEugeneC.Freuder.Contradicting
conventionalwisdominconstraintsatisfaction.InA.Cohn,editor,ProceedingsofECAI-94,pages125–129,1994.[25]TuomasSandholm.Algorithmforoptimalwinner
determinationincombinatorialauctions.ArtificialIntelligence,135(1-2):1–54,2002.
[26]TuomasSandholmandVictorLesser.LeveledCommitment
ContractsandStrategicBreach.GamesandEconomicBehavior,35:212–270,January2001.
[27]TuomasSandholmandVictorLesser.Leveledcommitment
contracting:Abacktrackinginstrumentformultiagentsystems.AIMagazine,23(3):89–100,2002.
[28]TuomasSandholm,SandeepSikka,andSamphelNorden.
Algorithmsforoptimizingleveledcommitmentcontracts.InProceedingsoftheIJCAI-99,pages535–541.MorganKaufmannPublishersInc.,1999.
[29]TuomasSandholmandYunhongZhou.Surplusequivalence
ofleveledcommitmentcontracts.ArtificialIntelligence,142:239–264,2002.
[30]WilliamE.Walsh,MichaelP.Wellman,andFredrikYgge.
Combinatorialauctionsforsupplychainformation.InACMConferenceonElectronicCommerce,pages260–269,2000.[31]RainierWeigelandChristianBliek.Onreformulationof
constraintsatisfactionproblems.InProceedingsofECAI-98,pages254–258,1998.
[32]MargaretW.Wiener.Accessspectrumbidwithdrawal.
http://wireless.fcc.gov/auctions/33/releases/da011719.pdf,July2001.
因篇幅问题不能全部显示，请点此查看更多更全内容