114 Pages
English

Compact Bidding Languages and Supplier Selection for Markets with Economies of Scale and Scope [Elektronische Ressource] / Stefan Schneider. Gutachter: Martin Bichler ; Gudrun Johanna Klinker. Betreuer: Martin Bichler

Gain access to the library to view online
Learn more

Description

Institut fur Informatikder Technischen Universit at Munc henLehrstuhl fur Informatik XVIIICompact Bidding Languages andSupplier Selection for Marketswith Economies of Scale and ScopeStefan SchneiderVollst andiger Abdruck der von der Fakult at fur Informatik der TechnischenUniversit at Munc hen zur Erlangung des akademischen Grades einesDoktors der Naturwissenschaften (Dr. rer. nat.)genehmigten Dissertation.Vorsitzender: Univ.-Prof. Dr. Helmut SeidlPrufer der Dissertation:1. Univ.-Prof. Dr. Martin Bichler2. Gudrun J. Klinker, Ph.D.Die Dissertation wurde am 07.03.2011 bei der Technischen Universit atMunc hen eingereicht und durch die Fakult at fur Informatik am 30.07.2011angenommen.AbstractPreference elicitation is a fundamental problem in single-unit combinatorialauctions, but it becomes prohibitive even for small instances of multi-unitcombinatorial auctions. The bidders cannot express their preferences exactlyas this would take a huge number of bids, typically leading to ine cient allo-cations.Hence, markets with economies of scale and scope require more compact andyet expressive bidding languages. In this thesis, we propose an expressive bid-ding language allowing bidders to describe the characteristics of their cost func-tions. Bidders in these auctions can specify various discounts and markups,and specify pricing rules as logical functions.

Subjects

Informations

Published by
Published 01 January 2011
Reads 15
Language English

Informatikur¨fInstitutderTechnischenUniversit¨atM¨unchen
Lehrstuhlf¨urInformatikXVIII

andLanguagesBiddingCompactwithSupplierEconomiesSelectionofScaleforandMarketsScope

SchneStefanderi

VUnivollst¨ersit¨andigeratM¨AbunchendruckzurdervonErlangungderFdesakult¨akatf¨urademischenInformatikGradesderTeinesechnischen

DoktorsderNaturwissenschaften(Dr.rer.nat.)

Dissertation.genehmigten

VPr¨uferorsitzender:derDissertation:Univ.-Prof.Dr.HelmutSeidl

2.1.Univ.-Prof.Univ.-Prof.Dr.GudrunMartinJ.BicKlinkhlerer,Ph.D.

DieDissertationwurdeam07.03.2011beiderTechnischenUniversit¨at
M¨uncheneingereichtunddurchdieFakult¨atf¨urInformatikam30.07.2011
angenommen.

Abstract

Preferenceelicitationisafundamentalprobleminsingle-unitcombinatorial
auctions,butitbecomesprohibitiveevenforsmallinstancesofmulti-unit
combinatorialauctions.Thebidderscannotexpresstheirpreferencesexactly
asthiswouldtakeahugenumberofbids,typicallyleadingtoinefficientallo-
cations.

Hence,marketswitheconomiesofscaleandscoperequiremorecompactand
yetexpressivebiddinglanguages.Inthisthesis,weproposeanexpressivebid-
dinglanguageallowingbidderstodescribethecharacteristicsoftheircostfunc-
andtions.specifyBidderspricingintheserulesasauctionslogicalcanspfunctioecifyns.variousFindingthediscountsoptimalandallomarkcationups,
giventhesepricingrulesisastronglyNP-hardoptimizationproblemandwe
proposeamixedintegerprogramtosolveit.

Basedonfielddata,weintroduceamulti-itemcostfunctionandprovideex-
tensivecomputationalexperimentstoexplorethecomputationalburdenand
theimpactofdifferentlanguagefeaturesonthecomputationaleffortandtotal
spendoftheauctioneer.Inaddition,weexplorecharacteristicsoftheknowl-
edgerepresentationofthebiddinglanguage.

i

ii

Zusammenfassung

KombinatorischeAuktionenbietendieM¨oglichkeitSynergieeffektezunutzen,
indemnatoriscsiehenmehrereAuktionG¨mitutereininereinernichtAutrivialenktionAnzahlzusammenfassen.vonG¨uternInisteinerkallerdingsombi-
bereitsdasAbfragenderrelevantenWertigkeitenproblematisch,dadieBieter
nicAllokhtsoationvielesicherEinzelgebzuboteestimmen.abgebenDiesesk¨onnenProblemwien¨votigerscw¨h¨arftaren,sicumhwdieeiter,effizienwennte
bproer¨ucGuksicthnichtigttnwurerdeneinesollen.Einheitversteigertwird,sondernauchMengenrabatte

Daherben¨otigenderartigeM¨arktekompaktere,unddadurchbeherrschbare,
aberdennochersch¨opfendeBietsprachen.IndervorliegendenArbeitschla-
genwireinederartigeSprachevor,welcheesdenBieternaufvielf¨altige
WeiseerlaubtihreKostencharakteristikainkompakterundintuitiverForm
auszudr¨ucken.Dazuk¨onnensieverschiedenartigePreismodifikatorenverwen-
den,welcheihrerseitsvonflexiblenundlogischkombinierbarenBedingungen
abh¨angen.DieseBedingungenk¨onnensichdabeisowohlaufdiegekaufte
MengealsauchdenerzieltenUmsatzbeziehen.DasBestimmenderopti-
malenAllokationausdiesenkomplexenPreisstrukturenisterwiesenermaßen
NPvollst¨andig,undvondaherinderBerechnungpotentiellsehraufw¨andig.
Wirschlagendahereingemischt-ganzzahligesOptimierungsproblemvor,mit
dessenHilfedieseberechnetwerdenkann.

AbschließendevaluierenwirunserenAnsatzmitHilfeeinesselbstentwickelten
Kostenmodells,dessenCharakteristikaaufEchtdatenberuhen,welchewirin
Feldversuchensammelnkonnten.AlsHauptergebnissondierenwir,welche
Problemgr¨oßeninakzeptablerZeitl¨osbarsind.Wiruntersuchendabeiden
EinflussverschiedenerElementederBietspracheaufBerechnungsaufwandund
Einsparungsm¨oglichkeitengegen¨ubereinfacherenAns¨atzen.

iii

iv

tswledgmenknoAc

solchZuerallerstinteressanwillicteshundmichbeispannendesMartinFBicorschlerhf¨urungsprodiejekt¨Gelegenhubeeitrnehmenbedankzuden,¨urfen.ein
Diefreiz¨ugigundgestaltendeArbeitdaranhatmirvielSpassbereitetundich
habevielesdabeigelernt.

AspecialthanksgoestoKemalGulerandMehmetSayalforaveryinspiring
collaborationandthegreattimeinCalifornia.

BeimeineKollgenGeorgZiegler,PashaShabalin,TobiasScheffel,J¨urgenWolf,
AlexanderPikovsky,ChristianMarkl,OliverH¨uhnundChristianHassm¨ochte
ichmichf¨urdieDiskussionenundwertvolleAnregungenbedanken.

Ichm¨ochteFelixSchmiddaf¨urdankenseinZimmerbelagernzud¨urfenund
MariaSchmidf¨urIhretreibendeGeduld.

v

vi

tstenCon

Abstract..................................i
Zusammenfassung.............................iii
Acknowledgements............................v

ListFiguresof

ablesTofList

xi

xv

1ductiontroIn11.1Motivation..............................1
1.2Contributions............................3
1.3StructureoftheThesis.......................4

2CombinatorialAuctionsandtheirApplicabilitytoMulti-unit
7Settings2.1CharacterizationsofMulti-itemandMulti-unitAuctions....7
2.2IterativeCombinatorialAuctions.................8
2.2.1BiddingLanguages.....................8
2.2.2WinnerDetermination...................10
2.2.3Non-LinearPersonalizedPriceAuctions.........13
2.2.4AscendingVickreyAuctions................14
2.2.5LinearPriceAuctions...................15

vii

3

4

5

2.2.6Problems..........................16
2.2.7Evaluation..........................17
2.2.8Results............................22
2.2.9ApplicabilitytoProcurementAuctions..........35
2.3VolumeDiscountAuctions.....................36
2.3.1BiddingLanguages.....................36
2.3.2WinnerDetermination...................36
2.3.3OpenIssues.........................37

TheLESSBiddingLangue39
3.1BiddingLanguage..........................39
3.1.1DescriptionLengthofBiddingLanguages.........39
3.1.2TheLBiddingLanguage................42
SSE

TheSupplierandQuantitySelection45
4.1TheSupplierQuantitySelectionProblemFormulation.....45
4.2ScenarioAnalysis..........................49
4.2.1PriceFeedbackinL..................51
SSE

53SetuptalerimenExp5.1ValueModel”CostofProduction“................53
5.1.1CompositionofCost....................54
5.1.2ParametrizableCostFunction...............58
5.2BidGeneration...........................64
5.2.1FixedIntervalBidding...................65
5.2.2FixedApproximationErrorBidding............67

viii

6

7

ResultstalerimenExp

6.1CostofFlexibility..........................

6.2ValueModelCostofProduction..................

6.2.1SingleItemInstances....................
6.2.2SingleItemInstanceswithLumpSumDiscountsand
Markups...........................

6.2.3MultiItemInstances-RealisticProblems........

andConclusionokOutlo

7.1

7.2

Conclusion..............................

Outlook...............................

ix

71

71

75

7580

81

87

87

89

x

ofListFigures

2.12.22.32.42.5

5.15.25.35.45.55.6

Efficiencyandrevenueofiterativecombinatorialauctionsfor
theTransportationvaluemodel..................
Efficiencyandrevenueofiterativecombinatorialauctionsfor
theRealEstate3x3valuemodel..................
Efficiencyandrevenueofiterativecombinatorialauctionsfor
thePairwiseSynergyvaluemodel.................
Roundsneededbyiterativecombinatorialauctions.......
ImpactofBSConpricesforstraightforwardbiddingwiththe
RealEstatevaluemodel......................

Tunitsotal,apurcveragehasedandifonlymarginalfixedcostscostsofdep1000enden$tareonthepresenntum.b.er.of..
Tunitsotal,apurcveragehasedandifonlymarginalstepwisecostsfixeddepcostsendentofon200the$nareumbpreseneroft.
Total,averageandmarginalcostsdependentonthenumberof
unitspurchasedifonlyvariablecostsof1$arepresent.....
Total,averageandmarginalcostsdependentonthenumberof
unitspurchasediffixedcostsof1000$andsuperlinearvariable
costsarepresent..........................
Total,averageandmarginalcostsdependentonthenumberof
vunitsariablepurccostshasedareifpstepresentwise..fi.xed...costs..of..200..$.and...sup...erlinear...
Costfunctionbasecase(notrandomized).............

xi

2526273233

555556575760

5.7Randominstacesofthecostfunctionforseeds2,3and9....62
5.8Randominstancesofthecostfunctionforseeds2,3and9and
differentsupplierrealizationsindottedlines...........64
5.9Comparisonoffixedintervalbiddingwith5intervals......66
5.10Comparisonoffixedintervalbiddingwith5intervalsandstep-
wisefixedcosts...........................67
5.11Comparisonoffixedapproximationerrorbiddingwithamaxi-
mumerrorof25%.........................68
5.12Comparisonoffixedapproximationerrorbiddingwithamaxi-
mumerrorof25%withoutfixedcosts...............69

6.1Descriptionlengthcomparisonofincrementalvs.totalquantity
bidsinLESSfor32supplierinstancesofthebasecase......76
6.2Comparisonofnumberofpriceintervalsfordifferentincremen-
talandtotalquantitybiddingpoliciesfor30singleitemCoP
instances...............................76
6.3Comparisonofcomputationtimefordifferentincrementaland
totalquantitybiddingpoliciesfor30singleitemCoPinstances
with2suppliers...........................77
6.4Comparisonofcomputationtimefordifferentincrementaland
totalquantitybiddingpoliciesfor30singleitemCoPinstances
with8suppliers...........................78
6.5Comparisonofcomputationtimefordifferentincrementaland
totalquantitybiddingpoliciesfor30singleitemCoPinstances
with64suppliers..........................78
6.6Comparisonofspendrelativetoansplitawardauctionfordiffe-
rentincrementalandtotalquantitybiddingpoliciesfor30single
itemCoPinstanceswith2suppliers................79
6.7Comparisonofspendrelativetoansplitawardauctionfordiffe-
rentincrementalandtotalquantitybiddingpoliciesfor30single
itemCoPinstanceswith64suppliers...............80
6.8Comparisonofcomputationtimefordifferentincrementaland
totalquantitybiddingpoliciesfor30singleitemCoPinstances
with64suppliers..........................81

xii

6.9

Comparison

tren

sum

of

endps

incremenandtal

tsdiscoun

and

elativre

to

a

split

ytitquantotal

markups

for

xiii

30

ardwa

auction

oliciespbidding

single

item

CoP

for

using

diffe-

lump

instances

.

.

81

xiv

TofListables

2.12.22.32.42.52.62.7

4.14.24.3

5.15.25.35.4

PBiddingerformancAgeneoftsforiterativtheeRealcomEstatebinatorialvaluemoauctionsdel.with....differing....
PBiddingerformancAgeneoftsforiterativtheePcomairwisebinatorialSynergyvauctionsaluemowithdel...differing...
PBiddingerformancAgeneoftsforiterativtheeTcomransportbinatorialationvalueauctionsmodelwith....differing...
Numbinatorialberofauctions,instancesofwherethesmallthresholdbiddersproblemactuallyinwoniterativ..e..com-..
ComparisonofICAswithdifferingcompetitionlevels......
moRevdelenuewithin%BSCtothefulfilledVCG..o..utcome,....in..the..Real....Estate..v..alue..
moRevdelenuewithin%BSCtonottheVfulfilledCGo..utcome,....in..the..Real....Estate..v..alue..

ListofVariablesinSQS.....................
ListofParametersinSQS.....................
ListofSetsinSQS.........................

Singleitemcostfunctionparameters...............
Multiitemcostfunctionparameters................
Parametersofthecostfuntionintheproposedbasecase....
Parametersofthecostfuntioninthebase(singeitem)case...

xv

22232430323333

474748

58606163

6.1

6.2

6.3

6.4

6.5

ComparisonofSQSagainsttheresultsbyGoossensetal.(2007)
(basecase).............................

ComparisonofSQSagainsttheresultsinGoossensetal.(2007)
(moreforless)...........................

Parametersofthesingleitemruns...........

Comparisonofspendrelativetoasplitawardauciton

Provenoptimalityofthesolutionsintable6.4

xvi

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

72

73

75

83

84

1Chapter

ductiontroIn

impProortancurementtroleisinonetheofovtheerallkeypactivitieserformanceinoftheacosupplympancyhain.Wiandthomarginsccupiesavdwin-ery
dling,duetoincreasedcompetitioninnearlyallindustries,itbecomeseven
moreindispensabletofirmstominimizetheirprocurementcostbyprocuring
prices.estbtheatductionEconomiesfunctiofonscalethatandscoinfluencepethedescribepriceskeyoncproharacteristicscurementofmarkaets.supplier’sWhereaspro-
economiesofscaleprimarilyrefertoefficienciesassociatedwithsupply-side
cprohanges,ducttypsuce,haseconomiesincreasingoforscopereferdecreasingtotheefficienciesscaleofassoprociatedductionwithofademand-single
sidechanges,suchasincreasingordecreasingthescopeofmarketingand
distribution,ofdifferenttypesofproducts.
Auctionsasanadvancedmechanismfortradinghavesuccessfullybeenused
andabilityeasedtofindnegotipricesationinthatmanreflectyenthevironmenmarketts.Onesituationoftheircloselymainbycofeaturesordinatingisthe
etition.compthe

tionaMotiv1.1

Usingauctionsauctareionsinregularprolyusedcuremenintprisacticethereforeforamlogicalulti-item,stepmandulti-unsimpleitsplit-anegotiations.ward
Thereticularthegoobdestandbidderthegetssecondabestpredefinedbidderlargergetstheshareofremainingthevolumeshare.foraThispar-is

1

ODUCTIONINTR1.CHAPTER

donetoontheonehandassuresupplyifonesupplierisunabletofulfillhis
contractandontheotherhandaminimalsupplierpoolinthelongrun.With
significanteconomiesofscale,suppliersfaceastrategicproblemintheseauc-
tions.Sincethereisuncertaintyaboutwhichquantitytheywillgetawarded,
theymightspeculateandbidlessaggressivelybasedontheunitcostforthe
smaller,moreexpensive,share.Inotherwords,simplesplitawardauctionsdo
notallowsupplierstoadequatelyexpresseconomiesofscale.
Intherecentyears,drivenbythenewpossibilitiesoftheInternet,agrowing
literatureisdevotedtothedesignofoptimization-basedmarkets(aka.smart
markets)(GallienandWein2005),andinparticulartocombinatorialauctions,
wherebiddersareallowedtosubmitbidsonpackagesofdiscreteitems(Cram-
tonetal.2006).Thepromiseofthesemechanismsisthatbyallowingmarket
participantstorevealmorecomprehensiveinformationaboutcoststructures
orutilityfunctions,thiscandrasticallyincreaseallocativeefficiencyandlead
tohighereconomicwelfare.Unfortunately,thematchingofcomplexpreference
profilestypicallyleadstohardoptimizationproblems.Theliteratureinthis
fieldistypicallyfocusedonmulti-itembutsingle-unitnegotiationsandrespec-
tiveauctionformatsdonoteasilyextendtomulti-unitmarketswitheconomies
ofscale.Whilepreferenceelicitationisalreadyafundamentalproblemforbid-
dersinsingle-unitcombinatorialauctions,itbecomesprohibitiveinmulti-unit
combinatorialauctions.Marketswitheconomiesofscaleandscoperequirea
fundamentallydifferentbiddinglanguagethatallowstospecifydiscountrules
ratherthanahugenumberofmulti-unitpackagebids.
Sofartwocentraltypesofvolumediscountsarediscussedintheliterature:
incrementaldiscountsandtotalquantitydiscounts.Totalquantitydiscounts
havebeendescribedasadiscountpolicy,wherethesupplierhasspecified
anumberofquantityintervals(aka.discountintervals),andthepriceper
unitfortheentirequantitydependsonthediscountintervalinwhichthe
totalamountorderedliesGoossensetal.(2007).Incontrast,incremental
volumediscountsdescribeadiscountpolicy,wherethediscountsapplyonlyto
theadditionalunitsabovethethresholdofthequantityinterval.Inbusiness
practice,suchdiscountpoliciesareoftenalsodefinedonspendoronspendand
quantityforoneormoreitems.Inaddition,wewillalsoallowforlumpsum
discounts,definingaonetimereversepaymentonoverallspendorquantity.So
far,optimizationformulationsonlyexistforincrementalorfortotalquantity
discountbids,definedonquantitypurchased.

2

ONTRIBUTIONSC1.2.

tributionsCon1.2

Wehaveinvestigatedthefactorslimitingtheuseofwellunderstoodcombina-
torialauctionsforaprocurementsetting.Whiletheexistingacademicwork
coerfulversimpbiddingortantlanguagerequiremenforts,practicalmanyreal-wapplicabilitorldy.Incasespardemandticularwforeafocusmoreonpothew-
question:wingfolloHowcanbiddersmanageablyexpresstheircoststructuresincorporating(dis-
)economiesofscaleandscopeforuseinatractableprocurementauction?
Tolanguageanswerforthismarketsquestion,withweecdidonomiesthefolloofscwing:aleWandescintropoe,duceareferredcomptoactasLEbiddingSS.
Ourbiddinglanguageallowsfortwodifferenttypesofdiscounts,whichhaveal-
readybeendiscussedintheliterature:incrementalandtotalquantitydiscount
habids.veseenOursevapproaceralhalloapplications,wstohandwherelebothdifferentyptesofbiddersvolumesubmitdiscountsdifferen,tatndypwese
ofvolumediscountbids.Inadditiontopreviousapproaches,LESSallowsfor
lumpsumdiscountsontotalspendtomodeleconomiesofscopeandvarious
cLESSonditionsisonconsiderablyspendormorequantityexpressivforethethandprevifferentiousdiscounapproacttypheses.andAsgivaesresult,sup-
wepliersintrohighduceflexibilitdescriptionyinsplengthecifyingasantheirimpofferings.ortantApartcriterionfromforbidexpressivlanguages,eness,
sincebidderscannotbeexpectedtosubmitarbitrarilymanyparametersor
LEbids.SSWbidsewillwithseetotalthatquantheretityareorwithconsiderableincrementaldifferencesvolumebetwdiscouneents.bundlebids,
Inthiswork,wewillinvestigatethebuyer’sproblem,whoneedstoselectquan-
titiesfromsuppliersprovidingbidsinLESSsuchthathiscostsareminimized
andQuantityhisSeledemandctionis(SQSsatisfied.)WproblemewillandreferproptoosethisarespproblemectiveasmixethedinteSupplierger
program(MIP).Modelingmattersandthereareconsiderabledifferencesin
thediscusssolutionadditionaltimealdeplocationendingcononstraintsdifferenastmotheydelaretformypicallyulations.usedWforewillscenarioalso
vigation.naProcancuremenanalyzetinanmanagersinteractivneedeamannerclearduringunderstandingthescenarioofwhichanalysisproblemorinsizesdynamicthey
extensivauctions.eevaluationTherefore,ofwethewillshoempiricwalthatharSQSdnessisofNPthe-complete,supplierquanandtitrepyortonselectionan

3

INTR1.CHAPTERODUCTION

problem.Similaranalyseshaverecentlybeenperformedforthewinnerdeter-
minationproblemincombinatorialauctionsbyLeyton-Brownetal.(2009).
Itisimportantthatprobleminstancesfortheexperimentalevaluationmirror
real-worldcharacteristics.Wehaveintroducedamultiproductcostfunctionfor
marketswithscaleandscopeeconomiesandgeneratedbidsbasedonthese
costfunctions.LESSandthesoftwareframeworkusedinthispaperhaveal-
readybeenusedtosupportanumberofhigh-stakessourcingdecisionswith
anindustrypartner.Thesyntheticbidsmatchedthecharacteristicsofthose
thatwealsofoundinthefield.Theexperimentalresultsshowthatrealistic
problemsizesoftheSQSproblemcanbesolvedtooptimalityinamatterof
minuteswithIBM’sCPLEX(version12)andGurobi3.0.(Allresultsreported
arebasedonCPLEX.)Wehavealsofoundthattheshapeoftheunderlying
costfunctionandthedemandcanhaveasignificantimpactontheruntimeof
theproblemsandempiricalevaluationsneedtobeinterpretedwithcare.
Previousworkhasonlyfocusedonthecomputationalcomplexityofthewin-
nerdeterminationproblem.Thecostcurvesinourexperimentalevaluation
allowedustocomparethetotalcostachievedwithLESSbidsanddifferent
typesofvolumediscountsandbidsforsplit-awardauctions.Whilewedonot
discussmechanismdesignquestionsinouranalysis,weassumeadirectreve-
lationmechanismwherebidderssubmitbidsinawaythatreflectstheircost
curvesascloselyaspossible.Evenifbiddingbehaviorinthelaborinthefield
mightbedifferent,thisresultsuggeststhataricherbiddinglanguagecanlead
toconsiderablylowercostandmoreefficientresultsinmarketswitheconomies
ofscaleandscopewithLESS.

ofStructure1.3Thesisthe

Thethesisisorganizedasfollows:
Chapter2givesanintroductionintothefundamentalsofmulti-itemandmulti-
unitprocurementauctionsandmotivatesourapproach.Chapter3introduces
ournewbiddinglanguageandchapter4aMIPformulationtocalculatethe
optimalallocation.Chapter5explainsthedesignofoursimulations.Itde-
scribestheeconomicenvironment,ouraprioriassumptionsaboutthebidding
behavioranditdefinesandmotivatesthevaluemodelwecreated.Inchapter
6theresultsofoursimulationsarepresentedandchapter7finallydrawscon-
clusionsandproposessomefutureresearchtopicsinthisarea.TheAppendix

4

1.3.

STUCTURER

antainscon

and

OF

erviewvo

tainscon

of

additional

THE

the

THESIS

PQRS

results

of

arewsoft

the

platform

conducted

exp

used

in

our

ts.erimen

exp

tserimen

5

6

CHAPTER

1.

ODUCTIONINTR

2Chapter

theirCombinatorialApplicabilityAuctionstoandMulti-unit
Settings

Generallyspeaking,anauctionistheprocessoftradingitems,wherethegoods
arefirstannouncedandthenbidsarecollectedandintheendsomeofthebids
areselectedandrealized.Thedifferencebetweenauctionsandsimpleprice
negotiationsisthefixedsetofrules,whichisknowntoallparticipantsin
e.ancadvInthischapterwewillfirstgiveashortintroductionintomulti-unitandmulti-
itemauctionsandtheirdifferentformsingeneral.Thenwewilltakeacloser
lookintocombinatorialauctionsastheyarethetheoreticallyveryclosetoour
problem,andalsoinvestigatewhichproblemsexistthatarelimitingtheiruse
inpracticalprocurementsettings.Partofthisworkhasbeenpublishedin
Schneideretal.(2010).Finallywewillstudyexistingapproachestosimiliar
problems.

2.1Multi-unitCharacterizationsAuctionsofMulti-itemand

mIntheultiplemostidenticalbasicforminstancesanofanauctioniteminvareolvessoldonlyatcoponceyoftheaauctionsingleisitem.calledIf

7

CHAPTER2.COMBINATORIALAUCTIONSANDTHEIR
APPLICABILITYTOMULTI-UNITSETTINGS
amulti-unitauction,andifmultipledifferentitemsareinvolved,theaction
iscalledamulti-itemorcombinatorialauction.Naturallytherealsoexist
combinationsofbothtypes.Multi-itemauctionsaremotivatedbyeconomies
ofscopewherethevalueofanitemforthebuyerdependsonthecombinationof
itemsthathegets,andmulti-unitauctionsendorseeconomiesofscalewhere
thevalueoftheitemsdependsonthenumberofcopiesofanitemthatis
traded.Ifasingleauctioneersellsgoodsorservicestoacompetingsetofbidders
theauctioniscalledaforwardauctionorsellauctionandifasetofbidders
competesfortherightanddutytoselltoasingleauctioneeritiscalleda
auction.buyorerserevIfallbidsinanauctionhavetobesubmittedblindlyinadvancetheauction
iscalledasealed-bidauctionincontrasttoaniterativeauctionwherethebids
arecollectedinmultiplerounds.Inmostcasesthereissomesortoffeedback
mechanismguidingthebiddersinbetweenrounds.

2.2IterativeCombinatorialAuctions

Asoutlinedinchapter1combinatorialauctionsaretheoreticallythemecha-
nismofchoiceforoursetting.Inpracticalapplicationsthough,theynevergot
acceptedwidely.Asafirststepwewillthereforegiveabriefintroductioninto
combinatorialauctionsandexaminewhytheyarenotsuitableforcomplex
cases.tcremenproThetypicalprocessofaniterativecombinatorialaction(ICA)consistsofthe
stepsofbidsubmission,bidevaluation(akawinnerdetermination,market
clearing,orresourceallocation)followedbyfeedbacktothebidders,andis
repeateduntilthestoppingruleisfulfilled.Thefeedbackistypicallygivenin
formofaskpricesandtheprovisionalallocation.

LanguagesBidding2.2.1

Oneofpropagationthemostofcinformationhallengingfrompartsoftheambiddersulti-itemtothecomauctioneer,binatorialnamelauctionyisatheset
it.ofInpairstheconclassictainingEnglishwhattheAuctionbiddersettingwantswithandonlywhatonehegoisodwillingsoldattoapatimeyforit

8

2.2.ITERATIVECOMBINATORIALAUCTIONS

reducestothebiddersannouncingtheamounttheyarewillingtopayinorder
item.theereceivtoIncombinatorialauctionsaswehaveseenthebiddersdonotonlyhavethe
possibilitytocontemplatetheentiresetofindividualitemsbutalsocombina-
tionsofitemscalledbundles.Foreachofthe2i−1bundlesthebiddersnow
mustcommunicatetheamounttheyarewillingtopaytotheauctioneerinthe
worstcase.Intheliteraturethisiscalledcommunicationcomplexityandhas
beenanactivefieldofresearchnotonlyintheenvironmentofauctions.
knoResearcwledgehinrepresenArtificialtationInandtelligencereasoninghaslongforadealtparticularwithquestionsapplicationofdomaadequatein.
Therepresenmosttation,importanwheretthedecisionoptimaltobecasemadeisisfulltheexpressivitexpressivity,yofwheretheallknobunwledgedles
priced.ebcanexprDefinitionessthe1valuation(Expressivforalleness)p.ossibleAbiddingbundles.languageisfullyexpressiveifitcan

Typically,therearetwodownsides,themoreexpressivelanguagesare,the
harderitistoautomaticallyderiveinferencesandthelessunderstandable
theyaretohumans.Withtheuseofadvancedsoftwarefortheguidanceofthe
bidderstheunderstandabilityproblemcanbeavoidedtoacertainamount.
Ontheotherhandweknowfrominformationtheory,thatitisimpossibleto
findatrulycompact(linear)representationofallbidamounts.Theproofcan
bereadinNisan(2006)andusesthefactthattherearelessthan2tstringsof
.tlengthbitInthecaseofcombinatorialauctionsthemostbasiclanguagesarebasedthe
booleanoperationsAND,ORandXOR.ANDiscommonlyusedtocompose
thebundlesoutoftheindividualitems,whereasthebundlesitselfthenare
eitherconnectedwithORorXOR.
Definition2(XORBidding).Thebiddinglanguageexclusive-OR(XOR)al-
lowsbidderstosubmitmultiplesetsofitemsthatarepairedwiththeamount
heiswillingtopayforthisset.Theauctioneerthenisallowedtoselectat
sets.itemtheonemostDefinition3(ORBidding).Thebiddinglanguageadditive-OR(OR)allows
bidderstosubmitmultiplesetsofitemsthatarepairedwiththeamounthe
iswillingtopayforthisset.Theauctioneerthenisallowedtoselectany
combinationofsetsthathavenoitemincommon.

9

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

TheresultingORandXORbiddinglanguageshaveincontrasttotheirsim-
ilarcompositionverydistinctcharacteristics.TheORbiddinglanguagefor
exampleiseasiertounderstandforthebiddersbutitisnotfullyexpressive.
Thisfollowsfromthefactthatabundlepricecannotbelowerthanthesum
ofthepricesoftheitemsitiscomposedof.

Winner2.2.2Determination

Giventheprivatebiddervaluationsforallpossiblebundles,theefficientallo-
cationcanbefoundbysolvingtheWinnerDeterminationProblem(WDP).
WDPcanbeformulatedasabinaryprogramusingthedecisionvariablesxi(S)
whichindicatewhetherthebidofthebidderiforthebundleSbelongstothe
cation:alloLetK={1,...,m}denotethesetofitemsindexedbykandI={1,...,n}
denotethesetofbiddersindexedbyiwithprivatevaluationsvi(S)≥0,
vi(∅)=0forbundlesS⊆K.Inadditionweassumefreedisposal:IfS⊂T
thenvi(S)≤vi(T).

xi(maxS)S⊆Ki∈Ixi(S)vi(S)
s.t.S⊆Kxi(S)≤1∀i∈I(WDP)
S:k∈Si∈Ixi(S)≤1∀k∈K
xi(S)∈{0,1}∀i,S
Thefirstsetofconstraintsguaranteesthatanybiddercanwinatmostone
bundle,whichisonlyrelevantfortheXORbiddinglanguage.TheXORlan-
guageisusedbecauseitisfullyexpressivecomparedtotheORlanguagewhich
allowsabiddertowinmorethanonebid.Subadditivevaluations,wherea
bundleisworthlessthanthesumofindividualitems,cannotbeexpressedus-
ingtheORbiddinglanguage.Thesecondsetofconstraintsensuresthateach
itemisonlyallocatedonce.Muchresearchhasfocusedonsolvingthewinner
determinationproblem,whichisknowntobeNP-hardParkandRothkopf
(2005);Rothkopfetal.(1998);Sandholm(1999).
Havingdeterminedthewinningbids,theauctioneerneedstodecidewhatthe
winnersshouldpay.Asimpleapproachisforbidderstopaytheamountof

10

2.2.ITERATIVECOMBINATORIALAUCTIONS

theirbids.However,thiscreatesincentivesforbidderstoshadetheirbidsand
mightultimatelyleadtostrategiccomplexity,i.e.,tospeculationandinefficient
cations.allo

Pricing2.2.2.1TheVCGauctionisageneralizationoftheVickreyauctionformultiplehetero-
geneousgoods.Inthisauctionbiddershaveadominantstrategyofreporting
theirtruevaluationsvi(S)onallbundlesStotheauctioneer,whothendeter-
minestheallocationandrespectiveVickreyprices.TheVCGdesigncharges
thebidderstheopportunitycostsoftheitemstheywin,ratherthantheirbid
prices.Adifficultyinthecombinatorial(multi-item)caseisthattheopportunitycosts
thateverybidderhastobe∗pay,cannotbeexpressedasthesumofthe(second
best)itembids.GivenX−jastheoptimalallocationexcludingbidderjthe
pricepaidbyawinningbidderjonbundleSiscalculatedas

pj(S)=vj(S)xj(S)−(vi(S)xi∗(S)−vi(S)x∗−j(S))
S⊆KS⊆Ki∈IS⊆Ki∈I

ThisrequirestofindX−∗jforeachwinner,aproblemthatisasdifficultasthe
.WDPAlthoughithasasimpledominantstrategy,VCGdesignsuffersfromanumber
ofpracticalproblemssinceitsoutcomecanbeoutsideofthecoreAusubeland
Milgrom(2006b);Rothkopf(2007).Therevenuecandecreaseasmorebidders
evareenaddedzero.orTheasVsomeCGmecbiddershanismraiseistheirsusceptiblebids,andtocanshillbebiddingunacandceptablycollolusion.wor
Formally,letNdenotethesetofallbiddersIandtheauctioneerwithi∈N,
andM⊆Nbeacoalitionofbidderswiththeauctioneer.Letw(M)denote
thecoalitionalvalueforasubsetM,equaltothevalueoftheWDPwithall
biddersi∈Minvolved.(N,w)isthecoalitionalgamederivedfromtrade
betweenthesellerandbidders.Corepayoffsπarethendefinedasfollows:

Core(N,w)={π≥0|πi=w(N),πi≥w(M)∀M⊂N}
i∈Ni∈M

11

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

Thismeans,thereshouldbenocoalitionM⊂N,whichcanmakeacoun-
terofferthatleavesthemselvesandtheselleratleastaswellasthecurrently
winningcoalition.Intheirseminalpaper,BikhchandaniandOstroy(2002)
showthatthereisanequivalencebetweenthecoreofthecoalitionalgameand
thecompetitiveequilibriumforsingle-sidedauctions.
Definition4(CompetitiveEquilibrium,CEParkes(2006)).PricesP,and
allocationX∗areincompetitiveequilibriumifallocationX∗maximizesthe
payoff∗ofeverybidderandtheauctioneerrevenuegivenpricesP.Thealloca-
tionXissaidtobesupportedbypricesPinCE.

BikhchandaniandOstroy(2002)showthatX∗issupportedinCEbysome
setofpricesPifandonlyifX∗isanefficientallocation.AlthoughCEalways
exist,theypossiblyrequirenon-linearandnon-anonymousprices.Pricesare
linepricesarifarethepriceanonymousofaifbundlepricesisareequalequaltofortheeverysumofbidder.pricNesoofn-anonitsitems,ymousandask
pricesarealsocalledpersonalizedprices.Followingthreetypesofaskprices
discussed:usuallyare

1.asetoflinearanonymouspricesP={p(k)}
2.asetofnon-linearanonymouspricesP={p(S)}
3.asetofnon-linearpersonalizedpricesP={pi(S)}

GeneratingminimalCEpricesisdesirable,sinceitusuallyimposesincentive
compatibilityoftheauctiondesign.
Definition5(MinimalCEPricesParkes(2006)).MinimalCEPricesmini-
mizetheauctioneerrevenueΠ(X∗,P)onanefficientallocationX∗acrossall
CEpriceswhichsupportit.

MinimalCEpricesarenotnecessarilyunique.OnewaytoderiveminimalCE
pricescouldbetousethedualsoftheWDP.Unfortunately,WDPisabinary
program,andthesolutionwillnotbeintegralinmostcasesifsolvedasan
LPrelaxation.Therefore,thedualswillnotbeminimalandover-estimatethe
valueoftheitems.

12

2.2.ITERATIVECOMBINATORIALAUCTIONS

2.2.3Non-LinearPersonalizedPriceAuctions

Byaddingconstraintsforeachsetpartitionofitemsandeachbiddertothe
onWDPallvtheariablesformcanulationbecanomitbetedstrengtbutthehened,solutionsothisatstilltheinalwategralitysinytegral.constrainSuctsh
asolvformableulationwithlineardescribesprogrammeverying.feasiblePersonasolutionlizedtoannon-linearintegerCEproprblem,icescanandbise
derivOstroyed(from2002).WtheedualwillreferstrengthenedtothisformproblemulationasasdescribNLPPedAinWDPBikhc.handaniand
Fromdualitytheoryfollowsthatthecomplementaryslacknessconditionsmust
holdinthecaseofoptimality.Ithasbeenshownthattheseareequaltothe
CEconditions,statingthateverybuyerreceivesabundleoutofhisdemand
setDi(P)andtheauctioneerselectstherevenuemaximizingallocation.
bundDefinitionleswhich6(DemandmaximizeaSet).bidder’sThepdemandayoffπisetatDithe(P)givenofapricbidderesPi:includesall
Di(P)={S:πi(S,P)≥Tmax⊆Kπi(T,P),πi(S,P)≥0,S⊆K}

Complementaryslacknessprovidesuswithanoptimalitycondition,whichalso
servesasaterminationruleforNLPPAs.Ifbiddersfollowthestraightforward
strategythenterminatingtheauctionwheneachactivebidderreceivesabun-
dleinarevenue-maximizingallocationwillresultintheefficientoutcome.Note
thatademandsetcanincludetheemptybundle.Additionally,thestarting
pricesmustrepresentafeasibledualsolutiondeVriesetal.(2007).Atrivial
solutionistousezeropricesforallbundles.
IndividualNLPPAformatshavedifferentrulesofselectingbundlesandbidders
whosepricesareincreased.TheAscendingProxyAuctionhasbeensuggested
inthecontextoftheUSFCCspectrumauctiondesignAusubeletal.(2006);
AusubelandMilgrom(2006a).ItissimilartoiBundle(3),buttheuseofproxy
agentsismandatory,whichessentiallyleadtoasealed-bidauctionformat.
SincethisisthemaindifferencecomparedtoiBundle(3),wewillonlydiscuss
wing.follotheiniBundleTheiBundleauctioncalculatesaprovisionalrevenuemaximizingalloca-
tionattheendofeveryroundandincreasesthepricesbasedonthebids
ofnon-winning(unhappy)bidders.ParkesandUngar(2000)suggestthree
differentversionsofiBundle:iBundle(2)withanonymousprices,iBundle(3)
withpersonalizedprices,andiBundle(d)whichstartswithanonymousprices

13

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

andswitchestopersonalizedpricesforagentswhichsubmitbidsfordisjoint
bundles.WewillrestrictouranalysistoiBundle(2)andiBundle(3)forthe
er.papthisofquestionsThedVSVauctiondeVriesetal.(2007)designdiffersfromiBundleinthat
itdoesnotcomputeaprovisionalallocationineveryroundbutincreasesprices
foraminimallyundersuppliedsetofbidders.
Definition7(Minimallyundersuppliedsetofbidders).Asetofbiddersis
minimallyundersuppliedifinnoefficientallocationeachbiddersreceivea
bundlefromhisdemandset,andremovingoneofthebiddersforfeitsthis
erty.oppr

SimilartoiBundle(3),itmaintainsnon-linearpersonalizedpricesandincreases
thepricesforallagentsinaminimallyundersuppliedsetbasedontheirbids
round.lasttheof

kreyVicAscending2.2.4Auctions

iBundle(3)anddVSVresultinminimalCEprices.MinimalCEpricesand
VCGpaymentstypicallydiffer.BikhchandaniandOstroy(2002)showthatthe
biddersaresubstitutescondition(BSC)isnecessaryandsufficienttosupport
VCGpaymentsincompetitiveequilibrium.
Definition8(BiddersareSubstitutesCondition,BSC).TheBSCcondition
esquirer

w(N)−w(N\M)≥[w(N)−w(N\i)],∀M⊆N
M∈i

IfBSCfails,theVCGpaymentsarenotsupportedinanypriceequilibrium
andtruthfulbiddingisnotanequilibriumstrategy.Abidder’spaymentin
theVCGmechanismisalwayslessthanorequaltothepaymentbyabidder
atanyCEprice.EventhoughtheBSCconditionissufficientforVCGprices
tobesupportedinCE,AusubelandMilgrom(2006a)showthataslightly
strongerbiddersubmodularitycondition(BSM)isrequiredforanascending
auctiontoimplementVCGpayments.

14

2.2.ITERATIVECOMBINATORIALAUCTIONS

allMDefinition⊆M9⊆N(BidderandallSubmoi∈NdularittheryeisCondition,BSM).BSMrequiresthatfor
w(M∪{i})−w(M)≥w(M∪{i})−w(M)

deVriesetal.(2007)showthatunderBSMtheirprimal-dualauctionyields
VCGpayments.WhentheBSMconditiondoesnothold,thepropertybrakes
downandastraightforwardstrategyislikelytoleadabiddertopaymorethan
theVCGpriceforthewinningbundleDunfordetal.(2007).deVriesetal.
(2007)alsoshowthatwhenatleastonebidderhasanon-substitutesvaluation
anascendingCAcannotimplementtheVCGoutcome.BSMisoftennotgiven
inrealisticvaluemodelsastheonesprovidedbyCATSLeyton-Brownetal.
).2000(TheCreditDebitAuctionbyMishraandParkes(2007)isanextension
tothedVSVdesignwhichachievestheVCGoutcomeforgeneralvaluations.
Itintroducestheconceptofuniversalcompetitiveequilibrium(UCE)prices,
whichareCEpricesforthemaineconomyaswellasforeverymarginalecon-
omy,whereasinglebuyerisexcluded.Theirauctionterminatesassoonas
UCEpricesarereachedandVCGpaymentsaredeterminedeitherasone-time
discountsdynamicallyduringtheauction.Theauthorsshowthattruthful
biddingisanexpostNashequilibriumintheseauctions.Thisisnotacontra-
dictionwiththepreviousparagraph,sincethebiddersdonotalwayspaytheir
bidsbutcanreceivediscounts.Theauction,however,sharesthecentralprob-
lemoftheVCGauction:ifbuyersubmodularityisnotgiven,theoutcomes
mightnotbeinthecore.

AuctionsPriceLinear2.2.5

Thoughwehaveseenthatlinearpricesdonotsupporttheefficientallocation
inallcases,theyarethewidespreadinpracticaluse,andthereforeweinclude
twoofthemhere.
TheCombinatorialClockAuction(CCauction)describedinPorter
etal.(2003)utilizesanonymouslinearpricescalleditemclockprices.Ineach
roundbiddersexpressthequantitiesdesiredonthebundlesatthecurrent
prices.Aslongasdemandexceedssupplyforatleastoneitem(eachitemis
countedonlyonceforeachbidder)thepriceclock“ticks”upwardsforthose
items(theitempricesareincreasedbyafixedpriceincrement),andtheauc-
tionmovesontothenextround.Ifthereisnoexcessdemandandnoexcess

15

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

supply,theitemsareallocatedcorrespondingtothelastroundbidsandthe
auctionterminates.Ifthereisnoexcessdemandbutthereisexcesssupply
(allactivebiddersonsomeitemdidnotresubmittheirbidsinthelastround),
theauctioneersolvesthewinnerdeterminationproblemconsideringallbids
submittedduringtheauctionruntime.Ifthecomputedallocationdoesnot
displaceanybidsfromthelastround,theauctionterminateswiththisalloca-
tion,otherwisethepricesoftherespectiveitemsareincreasedandtheauction
es.utinconTheALPS(ApproximateLinearPriceS)designBichleretal.(2009)isbased
ontheResourceAllocationDesign(RAD)proposedbyKwasnicaetal.(2005)
andusesanonymouslinearaskpriceswhicharederivedfromtherestricted
dualoftheLPrelaxationoftheWDPRassentietal.(1982).Thetermination
ruleoftheRADauctionhasbeenimprovedinALPStopreventpremature
auctiontermination.Furthermore,theaskpricecalculationbetterminimizes
andbalancestheprices.InamodifiedversionALPSm,allbidssubmittedin
anauctionremainactivethroughouttheauction.Thisrulehadasignificant
positiveimpactonefficiencyinexperimentalevaluations.Inthefollowing,we
willonlyconsidertheresultsofALPSmandtheCombinatorialClockauction
toprovideacomparisontoNLPPAs.

Problems2.2.6

Clearlynatorial,NLPPauctionAsctheoryanb,eastheyconsidereddescribaefundameniterativetalauctioncontributiondesignstothatthearecomfubi-lly
lar,efficienstrt.aighHotforwwevarder,theybiddingaremighbasedtnotonaholdnuminberpractoficalassumpsettingstions.whereInparticu-bidders
haularitvebyoundedconditionrationaliholds,ty,andgiventherethatisabiddershugendon’tumbknoerofw,bundleswhetherathebiddersubmohasd-
todealwith.Recentexperimentalworkhasactuallyshownthatbiddersdid
notfollowapurebest-responsestrategy,eveninsimplesettingswithonlya
fewitemsScheffeletal.(2010).Itisalsoimportanttonotethat,ifoneofthe
biddersdeviatesfromhisbest-responsestrategyinaNashequilibrium,aNash
equilibriumstrategyisalsonotnecessarilyabestresponseforotherbidders
anymore.Forthereasonsoutlinedabove,itislikelythatnotallbidderswill
followastraightforwardbiddingstrategy.
straighTherefore,tforwitardisimpbiddingortanttostrategies,understandwhenbidderstheirpeithererformancecannotinfollocasewofsuchnon-a

16

2.2.ITERATIVECOMBINATORIALAUCTIONS

strategyforcomputationalorcognitivereasons,ordeliberatelychooseanother
.strategy

Ev2.2.7aluation

Laboratoryexperimentsareverycostlyandtypicallyrestrictedtoasmallnum-
berdifferenofttyptreatmenesoftsandbiddingbsessions.ehaviorcanTherefore,bestbtheerobanalyzedustnessinofNLPPcomputationalAsagainstex-
ts.erimenp

2.2.7.1SetupofNumericalSimulations

Oursimulationenvironmentconsistsofthreemaincomponents.Avaluemodel
definesvaluationsofallbundlesforeachbidder.Abiddingagentimplements
abiddingstrategyadheringtothegivenvaluemodelandtotherestrictions
ofthespecificauctiondesign.Anauctionprocessorimplementstheauction
logic,enforcesauctionprotocolrules,andcalculatesallocationsandaskprices.
Differentimplementationsofvaluemodels,biddingagents(i.e.,strategies)
andauctionprocessorscanbecombined,whichallowsperformingsensitivity
analysisbyrunningasetofsimulationswhilechangingonlyonecomponent
parameters.otherallpreservingandForthecomparisonofauctionformats,weuseasetoffocusvariables,suchas
allocativeefficiency,revenuedistribution,andspeedofconvergencemeasured
bynumberofauctionrounds.Webelievethatthenumberofroundsisthe
mostrelevantnumbertorepresenttheauctionduration,sincetheabsolute
timewillheavilydependoncomputationalcapacitiesofbiddersandspeedof
communication.Weuseallocativeefficiency(orsimplyefficiency)asaprimary
measuretobenchmarkauctiondesigns.Itismeasuredastheratioofthetotal
valuationoftheresultingallocationXtothetotalvaluationofanefficient
allocationX∗Kwasnicaetal.(2005):

vi(S⊆K:xi(S)=1S)
E(X)=i∈I
vi(S⊆K:xi∗(S)=1S)
∈Ii

17

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

Thetermi∈Ivi(S⊆K:xi(S)=1S)canbesimplifiedtoi∈IS⊆Kxi(S)vi(S)in
caseoftheXORbiddinglanguage,sinceatmostonebundleperbiddercan
cated.alloebeconomicSimilarly,wgaienismeasuredistributedtherevbenetwueeenthedistributionauctioneerwhichandshowsbidders.howtheGivoenvertheall
resultingallocationXandthebidprices{bi(S)},theauctioneer’srevenue
vsharaluatioeisnsofmeasuredaneffiascienthtealloratiocationoftheX∗:auctioneer’sincometothetotalsumof

xi(S)bi(S)
∈Ii⊆KSR(X)=vi(S⊆K:xi∗(S)=1S)
∈IiInordertocomparedifferentsettings,wewillsometimesalsoplotauctioneer
revenueas%oftherevenueintheVCGoutcome.Thecumulativebidders’
revenueshareisE(X)−R(X).Notethatitispossiblefortwoauctionoutcomes
withequalefficiencytohavesignificantlydifferentauctioneerrevenues.Inthe
following,wewillbrieflydiscussthevaluemodelsandbehavioralassumptions
ts.agenbiddingourin

delsMoalueV2.2.7.2Sincetherearehardlyanyreal-worldCAdatasetsavailable,wehavebasedour
researchontheCombinatorialAuctionsTestSuite(CATS)valuemodelsthat
ethaval.eb(een2000).widelyIntheusedfolloforwing,theevwewillaluationofdescribeWDPavaluealgorithmsmodelasaLeyton-Brofunctiwnon
thatgeneratesrealistic,economicallymotivatedcombinatorialvaluationson
allpossiblebundlesforeverybidder.
InrealtheestaRteeallotskEstate,whic3xh3havvealuevmoaluationsdel,vthekdraitemswnsoldfrominthethesameauctionnormalarethedis-
tributionforeachbidder.Adjacencyrelationshipsbetweentwopiecesoflandl
andm(elm)arecreatedrandomlyforallbidders.Edgeweightsrlm∈[0,1]are
generatedforeachbidderandusedtodeterminebundlevaluationsofadjacent
land:ofpieces

18

v(S)=(1+rlm)vk
elm:l,m∈Sk∈S

2.2.ITERATIVECOMBINATORIALAUCTIONS

WeusetheRealEstate3x3valuemodelwith9lotsandnormallydistributed
individualitemvaluationswithameanof10andavarianceof2.Thereisa
90%probabilityofaverticalorhorizontaledge,andan80%probabilityofa
diagonaledge.Edgeweightshaveameanof0.5andavarianceof0.3.Unless
explicitlystated(Section2.2.8.5),allauctionexperimentswiththeRealEstate
valuemodelareconductedwith5bidders.
TheTransportationvaluemodelmodelsanearlyplanartransportation
graphinCartesiancoordinates,whereeachbidderisinterestedinsecuring
apathbetweentworandomlyselectedvertices(cities).Theitemstradedare
edges(routes)ofthegraph.ParametersfortheTransportationvaluemodel
arethenumberofitems(edges)mandgraphdensityρ,whichdefinesanav-
eragenumberofedgespercity,andisusedtocalculatethenumberofvertices
as(m∗2)/ρ.Thebidder’svaluationforapathisdefinedbytheEuclidean
distancebetweentwonodesmultipliedbyarandomnumber,drawnfroma
uniformdistribution.WeconsidertheTransportationvaluemodelwith25
edges,15vertices,and15bidders.Everybidderhadinterestin16different
erage.vaonbundlesThePairwiseSynergyvaluemodelfromAnetal.(2005)isdefinedbya
setofvaluationsofindividualitems{vk}withk∈Kandamatrixofpairwise
itemsynergies{synk,l:k,l∈K,synk,l=synl,k,synk,k=0}.Thevaluationof
abundleSisthencalculatedas

|S|1|S||S|
v(S)=vk+|S|−1synk,l(vk+vl)
k=1k=1l=k+1
Asynergyvalueof0correspondstocompletelyindependentitems,andthe
sumsynergyofvthealueofindividual1meansitemvthataluations.thebundleThevmodelaluationisverisytwicegeneric,asashighitasallothews
typdifferenesofttyptranspesofortationsynergisticauctionsvAnaluations,etal.but(it2005was).alInsothisusedpaptoer,mowdeleusecertainthe
PforeacairwisehauctionSynergyvindepalueendenmodeltlywithfrom7aitems,uniformwheredistritemibutionvbetaluationsweenare4anddrawn12.
2.0.TheWesynergytestedvloaluesweraresynergydrawnvalues,fromabutuniformfoundlittledistributiondifferencebetinweenthe1.5results.and
AllauctionswithPairwiseSynergyvaluemodelhave5bidders.
inInatheRmaximealumEstatebundleandsizePairwiseof3,bSynerecausegyvinaluethesemodelsvaluebiddersmodelswerelargeinterestedbund-

19

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

lesobservareatialwonsaysAnvetaluedal.o(ver2005).smallones.WithoutThisthisisalsolimitation,motivtheatedbauctionyreal-wusuallyorld
degeneratesintoascenariowithasinglewinnerforthebundlecontainingall
items.IntheTransportationvaluemodelbidderswerenotrestrictedinbundle
size.Thetions.valueSomemohavdelsesmalldescribevbundleseryonlydifferen,tsomeprohavcessesesmallfortheandlargegenerationbundles,ofvalua-and
alsothewayhowsynergiesaredeterminedisdifferent.
Forthenumericalexperimentsallvaluationsforallbiddersneedtobegen-
eratedandineachroundallbundlesneedtobesortedbypayoff.Thisleads
tosubstantialcomputationtimeandputsapracticallimitonthesizeofthe
vtionaluewimothdel,thewhicRealhcanEstatebevsimaluemoulated.delFtoorokupexampleto,twaosinglehoursdueCreditDebittotheauhighc-
numberofauctionrounds.

2.2.7.3BehavioralAssumptionsandBiddingAgents

TheoreticalmodelsprovideargumentsforstraightforwardbiddinginNLPPAs.
Inanauctionwithprivatevaluations,however,whenthebiddersdonotknow
whetherthebiddersubmodularityholds,andthereforecandecidetoshade
theirbids.Therearealsocognitivebarriersforthestraightforwardstrategy,
sincebiddersneedtodeterminetheirdemandsetforanexponentialnumber
ofpossiblebundlebidsineachround.
Itisusefultolookatempiricalobservationsandthebehavioralliteratureto
derivehypothesesonbiddingstrategiesinNLPPAs.Unfortunately,sofar,
therehaveonlybeenafewlabexperimentsusingNLPPAsandwedonot
knowofanyapplicationsinthefield.ChenandTakeuchi(2009)comparedthe
VCGauctionandiBEAinexperimentswherehumanscompetedagainstarti-
ficialbidders.Biddersweresignificantlymorelikelytobidonpackageswith
ahightemporaryprofit,butdidnotfollowthepurestraightforwardstrat-
egy.Morerecently,Scheffeletal.(2010)conductedexperimentscomparing
iBundle,ALPS,CombinatorialClock,andtheVCGauction.Again,bidders
intheiBundleauctiondidnotfollowthestraightforwardstrategy,eventhough
theywereprovidedwithadecisionsupporttoolthathelpedthemselecttheir
demandset.Therewas,however,ahighlikelihoodtobidononeofthebest10
bundlesbasedontheirpayoffinthecurrentround.Bidderidiosyncrasiesand
mixedstrategiessuchasintrembling-handperfectequilibriaSelten(1975)are

20

2.2.ITERATIVECOMBINATORIALAUCTIONS

possibleexplanationsofthesefindings.Unfortunately,behavioralmodelsof
biddinginmulti-itemauctionsarerarePlottandSalmon(2002).
Wehavedevelopedanumberofbiddingagentsthataremotivatedbydifferent
conjecturesaboutthebehaviorofbiddersinNLPPAs.Theseagentsimplement
abiddingstrategyadheringtothegivenvaluemodelandtotherestrictions
ofaspecificauctionformat.
Thestraightforwardbidderismotivatedbythetheory.Healwaysbidshis
demandsetwhichmaximizeshissurplusifitweretowinoneofitsbidsatthe
currentprices.Obviously,theresultsofauctionswithstraightforwardbidders
shallachievetheoutcomespredictedbythetheory.
Fromlabexperiments,weknowthatbiddersdonotalwaysfollowthestraight-
forwardstrategyduetocognitivereasonsandsimpleerrors.Theforgetful
agentfollowsthestraightforwardstrategy,but“forgets”tosubmit10%ofhis
bidsineachround.These10%aredeterminedrandomlyandindependently
foreveryround.Similarlywealsomodeledaheuristicbidder.Thisagent
randomlyselects5outofhis20bestbundlesbasedonhispayoffinaround.
Sometimesbiddersinthelabtrytoincreasetheirchancesofwinningbybid-
dingonmanybundles,whichcanbeexplainedbyriskaversion.Thepowerset
bidderevaluatesallpossiblebundlesineachround,andsubmitsbidsforbund-
leswhichareprofitablegivencurrentprices.Wehavelimitedthisbidderto10
bundleswiththehighestpayoffineachround,whichisbasedontheobser-
vationthatbidderstypicallydonotbidonmanybundlebidsinanauction
roundScheffeletal.(2010).
Typically,inoursettingsthese10bundleswillhaveupto20%differencein
payoffatthebeginningoftheauctiongivenequalstartprices.
TheNLPPAs,whichwestudyinthiswork,terminateassoonasthenew
provisionalallocationincludesbidsfromallactivebidders.Thistermination
rulemaymotivatecollusivebidderstosubmitmorethenjustthedemandset
inthefirstroundinthehopethatasuitableallocationisfoundearlyandthe
auctionterminatesbeforethepricesrise.Thelevelbiddermodelsadishonest
strategythattriestoexploitthisidea.Wemodifythestraightforwardbidder
byloweringvaluationsofhisbestlbundlesandsettingallofthemequaltothe
valuationofthelthbestbundle.Inoursimulations,wehaveusedl=10.Note
thatproxybiddingagentscannotpreventbiddersfromadoptingthisstrategy.
Ifabidderisrestrictedintimeduringtheauction,hemightselecthismost
valuablebundlesapriori,andsticktothisselectionthroughouttheauction.

21

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

Thisstraighprtforweseleardctstraagenttegy,selectsonlyhisusing20themostvpreselectedaluablebundlesbundles.andAgain,folloawsprothexy
cannotdetectorpreventthisstrategy.
Toensurecomparabilitybetweenauctionformats,weuseafixedminimumin-
NLPPcrementAsofalw1aandysintegeterminatervwithaluationsanforefficieallntvsolutionaluations.givUnenderstraighthesetforwardconditions,bid-
dingdeVriesetal.(2007).

Results2.2.8

Thissectiondescribestheresultsofsimulationsintermsofefficiency,revenue
distributionandthenumberofauctionrounds.Unlessexplicitlystatedother-
wise,eachauctionsetupwasrepeated50timeswithdifferentrandomseedsfor
valuemodelsand,whereappropriate,biddingagents.Overall,weprovidethe
resultsofanextensiveexperimentaldesignwithmorethan25,000auctions.

ICAFormatCredit-dVSViBundleiBundleALPSmClockVCG
BiddingAgentDebit(3)(2)truth
StraightforwardRev.EfficiencyAuctioneerin%in%100.0083.45100.0084.57100.0084.6183.8899.9084.0998.6487.0595.16100.0083.17
Rev.Roundsallbiddersin%139.9616.55137.9015.43151.2815.39149.2616.0172.5614.5528.768.1016.831.00
ForgetfulEfficiencyin%99.9299.78100.0099.9298.6496.35
10%chancetoRev.Auctioneerin%81.7385.2884.7383.8884.1188.02
forgeteachbidRev.allbiddersin%18.1914.5115.2716.0314.548.30
Rounds550.54545.30329.68237.2072.2629.52
Level10Efficiencyin%90.0090.0589.7190.1291.1286.67
Rev.Rev.allAuctioneerbiddersinin%%18.1272.1017.9772.2917.5872.3418.7271.5519.0172.2510.3076.46
Rounds82.3882.00133.22130.96128.8826.06
P10owbesterset10bundlesRev.EfficiencyAuctioneerin%in%23.1090.5071.5389.6782.9398.4882.1499.2087.6599.5794.0997.27
inselectedeachroundRev.Roundsallbiddersin%1525.4467.331519.5818.22979.1815.55283.4617.0224.9411.9125.303.20
Preselect20Efficiencyin%98.2498.2498.2497.5691.5192.07
20bestbundlesRev.Auctioneerin%76.2679.5579.2778.6976.3584.65
Rev.allbiddersin%21.9418.6418.9218.7915.077.39
Rounds147.18141.32146.34145.6261.7628.32
HeuristicEfficiencyin%76.0973.6898.9497.5199.2998.18
5bundlesrandomoutRev.Rev.allAuctioneerbiddersinin%%54.0722.1121.5652.1616.8882.0314.0283.5511.4087.8894.194.00
of20bestRounds3183.123058.881860.88524.0427.4425.60

Table2.1:PerformanceofiterativecombinatorialauctionswithdifferingBidding
AgentsfortheRealEstatevaluemodel

22

2.2.ITERATIVECOMBINATORIALAUCTIONS

2.2.8.1AnalysisofDifferentBiddingStrategies

Firstweassumethatallbiddersintheauctionusethesamestrategyandana-
lyzetheresultsfordifferentvaluemodelsandbiddingstrategies.Inparticular,
wewanttoinvestigatehowdifferentNLPPAsbehavewhenthebiddersdeviate
fromthestraightforwardstrategy.
TheaverageperformancemetricsaresummarizedinTable2.1fortheReal
Estate,inTable2.2forthePairwiseSynergy,andinTable2.3fortheTrans-
portationvaluemodels.
Interestingly,wefoundasimilarpatternintheresultsforallvaluemodels.
WehavealsorepeatedthesametestswithdifferentinstancesofthePairwise
Synergyvaluemodel,wherethesynergylevelwaslowerandinsomecases
negative(subadditivevaluations),andwiththeRealEstatevaluemodelwith
amaximumbundlesizeoffourinsteadofthree.Thesemodificationsledto
results.similarBiddingAgentICAFormatCredit-DebitdVSViBundle(3)iBundle(2)ALPSmClockVtruthCG
StraightforwardEfficiencyin%100.00100.00100.00100.0099.6599.53100.00
Rev.Rev.allAuctioneerbiddersinin%%89.6310.3790.539.4790.469.5490.479.5389.819.8592.836.6910.4089.60
Rounds204.44202.96154.96154.8268.7031.681.00
ForgetfulEfficiencyin%99.8199.65100.0099.9999.6599.56
10%forgetceachancehtobidRev.Rev.allAuctioneerbiddersinin%%88.3111.5091.048.6390.419.5990.549.4589.929.7392.976.58
Rounds715.40712.26333.48243.3268.6031.86
Level10Efficiencyin%98.4098.4198.4898.4797.2194.46
Rev.Auctioneerin%88.3888.7888.8288.8088.0886.90
Rev.allbiddersin%10.039.649.679.689.147.59
Rounds150.16149.44150.28150.10117.7433.66
10Pobwesterset10bundlesRev.EfficiencyAuctioneerin%in%35.8296.0187.0695.9189.0199.1689.9899.5592.2899.7598.1999.51
inselectedeachroundRev.Roundsallbiddersin%1353.5060.181352.368.85650.2410.15192.609.5729.347.4731.241.31
Preselect20Efficiencyin%85.8085.8085.8085.8082.7585.21
20bestbundlesRev.Auctioneerin%79.4779.9179.9779.9877.0782.30
preselectedRev.allbiddersin%6.355.905.845.845.702.91
beforetheauctionRounds230.90230.06138.54138.4648.1430.56
HeuristicEfficiencyin%85.3385.4098.7098.1599.4099.35
5outofrandom20bestbundlesRev.Rev.allAuctioneerbiddersinin%%25.9759.3760.6424.7888.869.8488.859.3092.876.5397.921.41
Rounds2551.942544.981261.50338.5031.8631.34

Table2.2:PerformanceofiterativecombinatorialauctionswithdifferingBidding
AgentsforthePairwiseSynergyvaluemodel

OnlyrobustnesstheTranspagainstortationpreselectvaluebidding.modelwTheasmaindifferentreasonwithistheresploectwntoumitsberhighof

23

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

ICAFormatCredit-dVSViBundleiBundleALPSmClockVCG
BiddingAgentDebit(3)(2)truth
StraightforwardRev.EfficiencyAuctioneerin%in%100.0056.13100.0066.93100.0065.4365.3699.9965.9299.5577.1099.48100.0055.49
Rev.Roundsallbiddersin%216.7843.87205.1833.0778.6634.5778.0234.6332.2433.6029.6422.4144.511.00
ForgetfulEfficiencyin%99.4799.6099.9399.9799.5599.58
10%chancetoRev.Auctioneerin%51.3867.8865.5565.8165.9277.10
forgeteachbidRev.allbiddersin%48.1031.7634.3534.1533.6022.48
Rounds434.96414.70124.84106.9032.2429.74
Level10Efficiencyin%84.9585.0683.6484.0183.9684.56
Rev.Rev.allAuctioneerbiddersinin%%23.1361.9226.5658.4626.3657.3126.3057.7027.6556.1937.0547.36
Rounds60.5656.0640.1439.3819.6214.02
10Pobwesterset10bundlesRev.EfficiencyAuctioneerin%in%91.332.4756.0991.7358.9497.2859.9597.2672.5699.7888.6097.39
inselectedeachroundRev.Roundsallbiddersin%312.5688.80311.3635.52154.0638.1993.3637.2019.8027.1825.008.82
Preselect20Efficiencyin%99.8099.8099.8099.8099.5299.24
20bestbundlesRev.Auctioneerin%55.4066.5165.2465.2466.4476.77
preselectedRev.allbiddersin%44.3933.2834.5634.5633.0622.50
beforetheauctionRounds217.24205.6278.6478.1232.5629.88
HeuristicEfficiencyin%84.1484.5096.2496.1099.7597.73
5outofrandom20bestbundlesRev.Rev.allAuctioneerbiddersinin%%78.266.0654.9829.7559.0437.1059.5936.4373.8225.9088.359.33
Rounds789.24788.24268.62158.1221.2025.08

Table2.3:PerformanceofiterativecombinatorialauctionswithdifferingBidding
AgentsfortheTransportationvaluemodel

bundleswithsignificantcompetition,whichisduetotheunderlyingtopology
oftransportationnetworksandthefactthatonlyafewbundlesareofinterest
toeverybidder.Forthesamereason,thelevelbidderscouldsuccessfully
colludeandsignificantlyincreasetheirpayoff.
Belowwedescribethemainfindingsforeverytypeofthebiddingstrategy,for
thecasewhenallbiddersintheauctionfollowit.

2.2.8.1.1StraightforwardBidderOurcomputationalexperimentswith
straightforwardbiddersandNLPPAsyieldedoutcomesinlinewiththetheory.
AllNLPPAswereefficient.iBundle(3)anddVSVachievedVCGoutcomes
onlywhentheBSCconditionwassatisfied.WhenBSCwasnotsatisfied,
iBundle(3)anddVSVresultedinhigherprices.IntheTransportationvalue
modelwecouldobservecaseswherethepricesinNLPPAswereupto250%
higherthanintheVCGauction(seeFigure2.1),whereasintheRealEstate
andPairwiseSynergyvaluemodels,thepriceincreasewaslow(seeFigures2.2
).2.3andTheCreditDebitauctionalwaysresultedinVCGpayoffs,astheorypredicts.
iBundle(2)didnotresultinanefficientoutcomeforsomeinstances,butthese

24

2.2.

ITERATIVE

Figure

(a)

2.1:

TORIALCOMBINA

ardtforwStraigh

revenueandEfficiency

tationroranspT

value

of

UCTIONSA

iterative

delmo

(b)

orgetfulF

combinatorial

auctions

for

the

25

Figure

26

(a)

2.2:

CHAPTER

TORIALCOMBINA2.

APPLICABILITY

Straighardtforw

ofrevenueandEfficiencydelmovalue3x3Estate

iterative

OT

UCTIONSATHEIRAND

TI-UNITMUL

(b)

orgetfulF

combinatorialauctions

SETTINGS

for

the

Real

2.2.

TIVEITERA

Figure

(a)

2.3:

TORIALCOMBINA

ardtforwStraigh

revenueandEfficiency

airwiseP

gyreSyn

value

of

UCTIONSA

iterative

delmo

(b)

orgetfulF

combinatorial

auctions

for

the

27

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

ois,thatccasionswereiBundle(2)rareisandefficienthetlossforofsuperadefficiencditivyevgenerallyaluationsveryPloarkw.esaOnendUngarreason
(2000),whichismostlythecaseinourvaluemodels.
Inthelinear-priceauctions(ALPSandCC)thestraightforwardbidderwas
onlessavefficieneragetforthantheRealNLPPAs.EstateStill,valuetheirmodel,efficiencyandevwasenmore95.16%thanand99%98.6for4%
thePairwiseSynergyandtheTransportationvaluemodel.Itisimportant
tonotethatwiththestraightforwardbidder,weobservedcasesinALPSm
andstraighCCtforwauctions,ardstrategywhereinefficiencyALPSandwastheasCClowasauction,70%.itIfcanbiddershappenfollothatwththeey
donotrevealcertainvaluationsthatwouldbepartoftheefficientsolution
Bichleretal.(2009).Inthepresenceofactivityrules,biddersareforcedto
bidrobustnessonmoreofthanALPSmjusttheirformatasdemandwewillset.seeThiswhenwillwhaeveadiscusspositivpoweerseteffectonbidders.the

bidders,2.2.8.1.2andFtheorgetfulefficiencyBidderlosseswereNLPPlow.AswOnlyerethefairlynumbrobusterofagainstauctionforoundsrgetful
auctionincreasedtookonsignificanavtlyerageacross139.96allvauctionaluemoroundsdels.inFortheexampRealle,EstatethevalueCreditDebitmodel
withstraightforwardbiddersand550.54roundswithforgetfulbidders.Inter-
straighestingly,tforwtheardlinearbiddingpriceauctionsstrategy.wereAlsothehardlyaverageimpactednumatberallofcomparedauctiontoroundsthe
same.ethalmostremained

2.2.8.1.3LevelBidderAsexpected,thecollusivelevelbiddercausesan
efficiencyloss.IntheRealEstatevaluemodelefficiencydroppedtoaround
can90%tlyinalldifferentauction(t-test,formatsα=0and.05).alsoInthetheTauctioneerransprevortationenuevwalueasmonotdel,signthisifi-
strategywasverysuccessful.Here,thelevelbidderachievedasignificantly
ofhigherefficiencyreven,uewhichthandroppwithedatostraigharoundtforw84%ardonavstrategyerage.,hoFworevtheer,Tatransptheexportationense
vthealuetranspmodel,ortationthecompnetworketitionandisitfoiscusedmoreonlikaelysmallthatnaumvbaliderofalloitemscationorislegsfoundin
earlierwhenallbiddersfollowthelevelbiddingstrategy.
IntheCreditDebitauctionthehighbidderrevenuecausedbyoverestimated
pricediscountsduetothebidshadinginthelevelstrategy.Inallauction
formats,however,therearealsoinstancesinwhichtheauctioneergainedmore

28

2.2.ITERATIVECOMBINATORIALAUCTIONS

andthebiddersgainedlesscomparedtothestraightforwardbiddingstrategy.
Thisstrategyworksonlyinanexpectedsenseifallbiddersadheretoit.It
doesnotrepresentastableequilibrium.

the2.2.8.1.4CreditDebitPowersetauction,BidderthisFstrategyorthelediBundtoale(2),significantiBundle(3),decreasedVSV,ineandffi-
ciency(t-test,α=0.05).ForiBundleauctionstheefficiencylosswaslower
thanfordVSVandtheCreditDebitauctions.Apparently,thepricecalcula-
tionalgorithmusingminimallyundersuppliedsetislessrobustagainstnon-
bidding.ardtforwstraighIncontrast,theefficiencyandauctioneerrevenueshareofALPSauctionswas
equalorhighercomparedtothestraightforwardstrategyinallvaluemod-
els.auctionSimpultaneouslyerformedwtheellninumberhomogenousofroundsmarkwasets,mosignificandeledtlybyRealreduced.EstateTheandCC
PairwiseSynergyvaluemodels.Typically,theselinear-priceauctionsareused
withstrongactivityrulestoencouragetherevelationofmanybundleprefer-
encesalreadyintheearlyroundsofanauction,whichmightleadtoasimilar
strategywithbiddersinthefield.

2.2.8.1.5PreselectBidderTheefficientsolutioncannotbefoundifit
includesthebundleswhichareomittedbythepreselectbidder.IntheTrans-
portationvaluemodelthishadlittleeffectonefficiencycomparedtostraight-
forwardbidding,sincethereisonlyasmallnumberofinterestingbundlesfor
everybidder.Inothervaluemodelswecouldseeasignificantdecreaseinall
ts.measuremen

2.2.8.1.6HeuristicBidderHeuristicbidder,whobidsonramdom5of
his20bestbundles,causessignificantefficiencylossesinallNLPPAs.We
observedthehighestefficiencylossesfordVSVandtheCreditDebitauction.
areThereasonmiscalculatedfortheiflonotwallrevenuebundleofthebidsareaCreditDebitvailableatauctiontheisend.thatIndiscoaddition,unts
themorecomplexpriceupdateruleislessrobustagainstnon-straightforward
bidding.

29

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

2.2.8.2Sensitivitywrt.StraightforwardBidding

WehaveconductedanothersetofauctionsusingRealEstateandTransporta-
tionvaluemodelstomeasuretheeffectofonesinglebidderdeviatingfromthe
straightforwardstrategy,whiletherestadherestoit.Foreachsetting,werun
50auctionsusingiBundle(3),iBundle(2)andALPSmformats.
TheresultsfollowthesamepatternoverallthreeICAformatsandbothvalue
models.Theallocativeefficiencywasnotimpacted,exceptthatalreadya
singlelevelbidderreducedtheefficiencysignificantly.Thelevelbidderalso
sufferedhighestrevenuelossof46%ofhisrevenue,followedbythepreselect
bider,whohadjustaminorlossoflessthen5%.Allotherbiddertypesdidnot
changetheauctionoutcomesignificantly.Thisindicatesthattheequilibrium,
whichbringssignificantincreaseinrevenuetolevelbidderswhenallbidders
followthisstrategy,isnotstable.

Threshold2.2.8.3problem

Thethresholdproblemischaracterizedbyasituationwhereseverallocalbid-
dersarecompetingagainstaglobalbidder.Thelocalbiddersareinterestedin
individuallotsorsmallbundles,andtheglobalbiddertriestowinalargerset
oflots.Asuccessfulauctiondesignshallhelpthelocalbidderstocoordinate
theirbidsinordertowinagainsttheglobalbidderincasesuchanallocation
t.efficienisWeanalyzeddifferentICAdesignswithrespecttothethresholdproblemusing
theRealEstatevaluemodelwithdedicatedlocalbidderforeachofthenine
lotsandtwoglobalbidders.Thevaluationswereselectedsuchthatthey
imposeahighcompetitionbetweenlocalandglobalbidders.In20selected
instancestheefficientallocationincludedtheninelocalbiddersandnotthe
globalbiddersandtheallocationwithglobalbidderswaswithin10%from
theoptimalsolution.Wefocusedonthestraightforward,theforgetful,the
heuristic,andthepowerset10bidder.
❤❤Bidding❤❤Agen❤t❤❤ICA❤F❤❤ormatCreditDebitdVSViBundle(3)iBundle(2)ALPSmClockVCG
Straightforward❤20202018192020
PFoworgetfulerset101111462519191918
Heuristic00442020
Table2.4:Numberofinstancesofthethresholdprobleminiterativecombinatorial
auctions,wheresmallbiddersactuallywon

30

2.2.ITERATIVECOMBINATORIALAUCTIONS

AsTable2.4illustrates,bothlinearandnon-linearauctionformatscansolve
thethresholdproblemwithstraightforwardbidding.Ifthebiddersdeviated
fromstraightforwardbidding,theNLPPAsfailedtosolvethethresholdprob-
leminmostcases.ThereasonisthattheNLPPAsdonotpreserveinformation
aboutbidssubmittedinpreviousrounds.Onlystraightforwardbiddersal-
waysincludeoldbidswithupdatedpricessincethedemandsetcanonlygrow
throughouttheauctiongiventheNLPPApriceupdaterule.Strongactivity
rules,assuggestedbyMishraandParkes(2007),canbeusedtoforcebidders
toconformtothestraightforwardbiddingstrategyandimproveperformance
ofNLPPAsinthissituation.Howeversuchstrongrulesrequirethebidder
totionevinaluatetoaandsealed-bidrankallformat,bundlesthusinadvaneliminatingceandtheadvvirtuallyantagestransformofantheiterativauc-e
preferenceelicitationprocess.

2.2.8.4SpeedofConvergence

TheCCauctionhadthelowestnumberofauctionroundsinalltreatments.
Onaverage,NLPPAstookthreetimesasmanyroundsaslinear-pricebased
auctions(Figure2.4).Incontrasttothetheorythatexpectsalowernumberof
auctionroundsindVSVcomparedtoiBundle(3),weobservedahighernumber
ofroundsindVSV.Thishappensbecausetheminimallyundersuppliedsetis
notuniqueandweusedthesmallestpossibleminimallyundersuppliedset
wefound,whichresultedinsmallpricesteps.Forthesamereason,non-
straightforwardstrategiescausedthehighestincreaseinroundsfordVSVand
CreditDebitauctions,comparedtootherformats.Thespeedofconvergence
ofthesetwoformatscanbeimprovedbyincreasingpricesonseveraldisjunct
minimallyundersuppliedsetsineveryround.

2.2.8.5ImpactofIncreasingCompetition

Auctionsareexpectedtoyieldmorerevenueifthereismorecompetition.Table
mo2.5delpresenandtsavresultsaryingofnumbdiffereneroftauctionbidders.EaformatschnumusingbertherepresenRealtsanEstateavveraaluege
of10auctionswithsamesettinganddifferentrandomseedsforthevalue
modesign.del.WTheeoavbserverageedrevtheenueexpshareectedinbehathevioCrCinauctionNLPPsAsanddecreasedinthefrom5ALPSmto7
numbidders.berofLinearroundswithprice-basedanauctionsincreasingandnumtheberofiBundlebidders.designInshoconwedtrast,alowtheer

31

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

Figure2.4:Roundsneededbyiterativecombinatorialauctions

dVSVandCreditDebitauctionsshowedamassiveincreaseofrounds.Thisis
explainedbydifferentpriceupdatemechanisms.TheiBundledesign,which
increasespricesforallunhappybidders,willgenerallyincreasemoreprices
whenthecompetitionishigher.ThedVSVandCreditDebitauctions,which
increasepricesforaminimallyundersuppliedsetofbidders,willbeableto
findasmallerminimallyundersuppliedset(typicallywithonlyonebidder)
whenthecompetitionincreases,andthereforeincreasepricesforlessbundles
round.heacinICAFormatCredit-dVSViBundleiBundleALPSmClockVCG
BiddingAgentDebit(3)(2)truth
4biddersEfficiencyin%99.74100.00100.00100.0096.6995.88100.00
BSCfulfilledRev.Auctioneerin%78.4980.3480.3479.9684.1773.8279.96
100%Rev.allbiddersin%21.2519.6619.6620.0412.5222.0620.04
Rounds195.84201.4683.4083.4035.66103.061.00
5biddersEfficiencyin%99.94100.00100.00100.0096.5295.06100.00
BSCfulfilledRev.Auctioneerin%84.4884.9484.9483.1688.0977.2783.16
90%Rev.allbiddersin%15.4615.0615.0616.848.4317.7916.84
Rounds148.96150.10143.72146.2831.1468.921.00
6biddersEfficiencyin%99.91100.00100.00100.0094.7497.06100.00
BSCfulfilledRev.Auctioneerin%87.0087.2087.3985.4288.0482.4485.42
50%Rev.allbiddersin%12.9112.8012.6114.586.6914.6214.58
Rounds132.58133.42207.10209.6230.6861.861.00
7biddersEfficiencyin%99.89100.00100.00100.0094.3596.98100.00
BSCfulfilledRev.Auctioneerin%88.2988.6188.7986.3887.9484.4586.38
40%Rev.allbiddersin%11.5911.3911.2113.626.4112.5413.62
Rounds122.06122.82271.46274.5429.9252.581.00

Table2.5:ComparisonofICAswithdifferingcompetitionlevels

BSCofImpact2.2.8.6

WDueehatovediscussedcomputationalthatifreasons,BSMiswesatisfied,haveNLPPrestrictedAswillourselvleadestotoVickreyanalyzeprices.the

32

2.2.ITERATIVECOMBINATORIALAUCTIONS

somewhatweakerBSCconditiononly.TheresultsbasedontheRealEstate
valuemodel,wheretheBSCconditionwasfulfilledinapproximatelyhalfof
therandomlygeneratedinstances,andallagentswerefollowingthestraight-
forwardstrategyaresummarizedinTables2.6and2.7,aswellasFigure2.5.
Asexpected,pricesandconsequentlyrevenuewerehigherthantheVCGout-
comeinNLPPAs.Forlinear-priceauctions,theimpactwasnotsignificantly
t.differen❤❤Reve❤nue❤❤❤❤ICA❤F❤❤ormatiBundle(2)iBundle(3)dVSVCreditDebitClockALPSm
❤❤MinMean98.8699.87100.00100.00100.00100.00100.00100.00102.40107.5197.2586.68
Max101.72100.00100.00100.00120.81116.51
Table2.6:Revenuein%totheVCGoutcome,intheRealEstatevaluemodelwith
fulfilledBSC❤❤❤❤ICAFormat
Revenue❤❤❤❤❤❤❤❤iBundle(2)iBundle(3)dVSVCreditDebitClockALPSm
Min96.55100.52100.52100.0095.7184.56
MaxMean112.34102.48111.69103.31111.69103.30100.00100.00127.99111.39119.2598.61
Table2.7:Revenuein%totheVCGoutcome,intheRealEstatevaluemodelwith
defulfillnotBSC

Figure2.5:ImpactofBSConpricesforstraightforwardbiddingwiththeReal
Estatevaluemodel

Summary2.2.8.7

Inshare,terestinglyand,wauctionehadroundssimilaracrossresultsallvregalueardingmodels.efficiencyOnly,atheTuctioneer’sransprevortatienonue

33

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

valuemodelwasdifferentwrt.thehighlevelofaskpricescomparedtothe
VCGauction,andalsoitsstabilityagainstpreselectbidding.Themainreason
wasthelownumberofbundleswithsignificantcompetitionthatisduetothe
underlyingtopologyoftransportationnetworks.Forthesamereason,thelevel
bidderscouldsuccessfullycolludeandsignificantlyincreasetheirpayoff.
Linearpriceauctionswererobustagainstallstrategies,exceptthelevelstrat-
egy,whichassumescollusivebehaviourandmakesitdifficultforanyauctioneer
toselectanefficientsolutioningeneral.NLPPAswererobustagainstforgetful
bidders,butattheexpenseofahighnumberofbiddingrounds.Therewere
significantefficiencylossesinNLPPAswithheuristicbidders,powerset,level,
rs.biddepreselectanddVSVandCreditDebitauctionshaveasignificantlylowerefficiencythan
iBundle(3)withheuristicandpowersetbidders.Themaindifferencebetween
theseformatsisthesetofbidders,forwhichtheaskpricesareincreased.
Increasingtheaskpricesonaminimallyundersuppliedsetofbiddersisless
robustagainstthesestrategies.NotethatProxyagents,whichcanbeusedto
enforcestraightforwardbiddingMishraandParkes(2004),cannotdetectand
preventlevelandpreselectbiddingstrategies.

Conclusion2.2.8.8

NLPPAssuchasiBundle(3),dVSV,iBEA,andCreditDebitauctionshave
anismsgreatlyinadvtheancedrealmourofprivunderstandingatevaluations.fortheThesedesignofformatsefficienaretmoauctiondeledmeafcterh-
well-knownoptimizationalgorithmsthatleadtoefficientsolutions,provided
thatbiddersfollowthestraightforwardstrategy.
Sincewhereallthese2marevaluexactationsofalgorithms,alllosingthebiddersauctionaregenerelicited.allyrequiresBoththemanyhighnrounds,um-
berofauctionroundsandthenecessityofthestraightforwardbiddingstrat-
egythirdmotivparty,atewhicthehuseessenoftiallyproxyreducesagents,thewhichauctionneedtotoabesealed-bidhostedbevyenattruforsttheed
strategybidders.inWhilethesethereauctions,areitincenistivnotesalwforaysbiddersacceptabletofollotowusetheproxystraighagentforwts,ardnor
cantheypreventcertainstrategies,suchaslevelbidding.
Inproacconhtotrast,findlinearthepriceoptimalcomsolution.binatorialWhileauctionsourresultsfollowacahievmoreehighheuristicefficiencyap-

34

2.2.ITERATIVECOMBINATORIALAUCTIONS

vcannotaluesboneavefficienerage,tBiconehlercanetal.easily(2009).constructThereareexamples,afewwhereremedies,linearsucpricehasCAsthe
proxyphaseintheClock-ProxyauctionAusubeletal.(2006)thataddresses
theseBlumroseninefficienandcies,Nisanbut(2005these).designshavenotyetbeenthoroughlyanalyzed
Linear-pricedesignssufferfromthefactthattheycannotbe100%efficient,
advbutantheytages.haveTheshownmaintobadveanmoretageisrobusttheaagainstlinearnmanumyberofstrategiespricesandbneeded.earaThisfew
reducesguidelinethetohelpcommbiddersunicationfindfromprofitabletheitemsauctioneerandtothebundlesbiddersKwonandetal.presen(2005ts).a
TheyalsoexhibitalownumberofauctionroundscomparedtoNLPPAs.
Overallwehaveseenthatifbiddersdonotexpresstheirvaluationscorrectely,
sptheectptoerformanceefficiency)ofallmayauctionhappenbformatsecausesuofffers.strategicSuboptimalconsiderationsbiddingin(withsomere-
mighcasestbutfailbevenecauseiftheofthebidderscomwplexitantytotodoexpressso.theirvaluationscorrectelythey

2.2.9ApplicabilitytoProcurementAuctions

proMulti-unitcurementcomsettings,binatorialasauctibiddersons,canwilllikrealisticallyelyleadonlytoexpresseconomicaveryinefficienciessmallfrac-for
cantionofalreadytheirbsubmidsofit2inI−1terest.pFossibleorabids.comIfbinatoryoualialsoalloauctionwforwithkIquanitems,titiesaofbiddereach
item,thenumberofpossiblebidsgrowsevenfaster(φ(I,k)=jI=0−1kI−jjn).
Forexample,with10itemsitwouldbepossibletospecify1023bidsinasingle-
unitcombinatorialauction.However,with6allowablequantitiesforeachitem
thesuppliercanpossiblyspecifymorethan282millionbids.Clearly,bidders
willonlybeabletosubmitasmallproportionofthepossiblebidsofinterest,
andtheauctioneerwillmostlikelynotfindtheefficient,maybenotevena
cation.allofeasibletionThereandaretwreducesoposstheinbleumberremedies:ofpossibilitiesEithertheabidderauctioneercanbidonsimplifiesthroughthepre-auc-
morebundlingpoworerfulotherbiddingformsoflanguagethsimplificationatallowsMilgrotomdescrib(2009e),hisorprheeferencesprovidesinaa
.yawconcise

35

CHAPTER2.COMBINAAPPLICABILITYTORIALTOAMULUCTIONSTI-UNITANDSETTINGSTHEIR

2.3VolumeDiscountAuctions

Volumediscountbidsallowforacompactrepresentationofbidsinmarkets
witheconomiesofscale.Thesebidtypesdefineunitpricesforspecificvolume
intervalsasstepwiselinearfunctions.

LanguagesBidding2.3.1

Theearlierliteratureonsupplierselectionandvolumediscountsincludesstud-
iesofvariousdiscountingschemes,suchasunitdiscountsSilversonandPeter-
son(1979),inventorymodelswithdemanduncertaintyandincrementalquan-
titydiscountsandcarloadquantitydiscountsJuckerandRosenblatt(1985);
LeeandRosenblatt(1986).MunsonandRosneblatt(1998)provideaper-
spectiveondiscountsusedinpractice,whileChaudhryetal.(1993)discussa
vendorselectionmodelinthepresenceofpricebreaks.
DavenportandKalagnanam(2000)wereamongthefirstauthorstofocuson
auctionswithincrementalvolumediscountbids.Anapplicationthereofhas
beendescribedinHohneretal.(2003).Theirbiddinglanguagerequiressuppli-
erstospecifycontinuoussupplycurvesforeachitem.Esoetal.(2001)further
advancetheideasdescribedinDavenportandKalagnanam(2000)andallow
fordiscontinuitiesanddecreasingslopesinthebids.
Therehasalsobeensomeworkontotalquantitydiscounts,wheretheunitprice
startingataparticularquantityischargedfortheentirequantitypurchased,
notonlyfortheunitsabovethethresholdquantity.Katzetal.(1994)discussa
procurementdecisionsupportsystemandarespectivemathematicalprogram
withtotalquantitydiscounts.Cramaetal.(2004)investigateaproblem,where
achemicalcompanyneedstopurchaseanumberofingredientsfromoneor
moresupplierswithatotalquantitydiscount.Here,onlyonediscountrate
isusedforallingredients.Cramaetal.(2004)alsoneedtodecidehowto
usethepurchasedingredientstomanufacturethedesiredquantitiesoftheend
products,wheretherearealternativerecipes,whichisdifferenttotheproblem
thesis.thisinanalyzed

DeterminationWinner2.3.2

asWhileComthebineNet,academicEmptoris,literatureIasta,isstillandinTitsinfancyradeExtension,anumbGartnererof(2008companies)prosucvideh

36

2.3.VOLUMEDISCOUNTAUCTIONS

decisionsupportsystemsallowingforvarioustypesofdiscountsandcomplex
bidtypes.Thesetoolsenablepurchasingmanagerstoexploredifferentaward
scenariosbasedonvariousoperationalorstrategicsideconstraints.Respective
softwarevendorsofferawidevarietyofconstraintsamongseveraldozensor
evenhundredsofconstraintclassesBichleretal.(2006).
ThegeneralproblemhasbeendiscussedinGoossensetal.(2007).Theypro-
videaninterestingcontributiontothesupplierselectionproblemwithtotal
quantitydiscountsandaproof,showingthatnopolynomial-timeapproxima-
tionschemewithconstantworst-caseratioexistsforthissupplierselection
problemandthatthedecisionversionisstronglyNP-complete.
Acomplexityanalysisofasimilarallocationproblemwithlineardemandcurve
bidscanbefoundinSandholmandSuri(2001).Thesetypesofbidsdescribe
piecewiselinearunit-pricefunctionsofthedemandandtheauthorsarguethat
theycanapproximateanyfunctionarbitrarilyclose.Notethatalsostepunit-
pricefunctionsm,astheonesthatwillbediscussedinthispaper,become
piecewiselineartotalcostfunctions.DangandJennings(2003)discussed
marketclearinginmulti-unitcombinatorialauctionswithsupplyfunctionbids,
wheresuppliersspecifyquantitiesandpricesforpackagesofitems.

IssuesenOp2.3.3

Wehaveworkedwithanumberofprocurementmanagersinthepastfewyears
toevalutewhythereisverylittleapplication.Whiletheaboveacademicwork
coversimportantrequirements,manyreal-worldcasesdemandforamorecom-
prehensivebiddinglanguageforpracticalapplicability.Inmanyapplications,
somesuppliersprovideincrementalvolumediscountbids,otherstotalquantity
discountbids,oroveralllump-sumdiscountsontotalspend.
Asoutlined,inthiswork,weconsiderablyextendtheexpressivenessofthe
biddinglanguagesdiscussedintheliteratureandproposeamixedintegerpro-
grammingformulationtosolvepracticallyrelevantproblemsizes.Incontrast
topreviouswork,wesuggestaparametricmulti-productcostfunctiontogen-
eraterealisticbidsandanalyzedifferentdiscountpoliciesbasedoncostand
length.description

37

38

CHAPTER

2.

TORIALCOMBINA

APPLICABILITY

OT

UCTIONSA

AND

TI-UNITMUL

THEIR

SETTINGS

3Chapter

TheLESSBiddingLangue

LanguageBidding3.1

Insupplier’sthissection,costwefunction.willinWtroefoducecusaonmbiddingarketslanguagewithalloeconomieswingtoofscaledescribeanda
scopnomice,cwhereharacteristics.bidderstAypicallylanguageexpressindiscouncomputertsinscienceordertoandreflectlogictheseassignseco-a
comsemanticbinatorialtoasynauctionstax.AbracBiddingheetal.languages(2004ha);vebBoutiliereenstudiedandHoinos(the2001con);textNisanof
(2006).However,thisresearchtypicallyfocusesonmulti-item,butsingle-unit
negotiations.

3.1.1DescriptionLengthofBiddingLanguages

ThereisavastliteratureinMicroeconomicsandEconometricsonmodelingand
estimationofmulti-productcostfunctions.Suchmulti-productcostfunctions
describethecostofproductioncs:RI→Rasafunctionofthetotalquantity
producedinallproductsoritemsi∈Iforasuppliers∈S.Depending
onindustryandcompanyspecifics,differenttypesandparametricshapesof
suchcostfunctionscanbefound,sometimesexplicitlygivenbasedondata
fromcostaccounting.Afirmhaseconomiesofscale(i.e.,isoperatingin
adownwardslopingregionoftheaveragecostcurve)ifandonlyifithas
increasingreturnstoscale.Likewise,ithasdiseconomiesofscale(isoperating
inanupwardsloping,convexregionoftheaveragecostcurve)ifandonlyifit
hasdecreasingreturnstoscale.

39

CHAPTER3.THELESSBIDDINGLANGUE

Biddinglanguagesshouldbeexpressiveenoughtoallowforthedescriptionof
differentshapesthatmulti-productcostfunctionscanassume.Atthesame
time,thebiddinglanguageshouldallowtodescribebidsinacompactway
withonlyafewparameters.Ingeneral,expressivityofabidlanguageshould
increaseefficiencyofeconomicmechanisms,sincebiddersareabletobetter
describetheirpreferences(Benischetal.,2008;Sandholm,2008).Combinato-
rialauctionsallowbidderstoexpressalltypesofsynergiesacrossitems,but
thenumberofpossiblebidsinlarge-scalecombinatorialauctionsistypically
beyondwhathumanbidderscanexpress.Thereisanumberofarticleson
thecommunicationcomplexityofsuchauctionsNisanandSegal(2001).As
wehavediscussedinSection2.2.9,thisphenomenonbecomesevenworsewith
multi-unitcombinatorialauctions.Compactbiddinglanguages,whichallow
bidderstodescribetheirpreferencesonmultipleitemsandquantitiesasa
function,canalleviatethisproblem.
ResearchinArtificialIntelligencehaslongdealtwithquestionsofadequate
knowledgerepresentationandreasoningforaparticularapplicationdomain.
Themostimportantdecisiontobemade,istheexpressivityoftheknowledge
representation.Typically,themoreexpressivelanguagesare,theharderitis
toautomaticallyderiveinferences.Inageneralway,thishasbeenshownfor
formallanguages,whereregularlanguages(type-3)canbedecidedinlinear
time,whereasthegeneralclassofrecursivelyenumerablelanguages(type-0)re-
quireaTuringmachine.Inlogic,thebooleansatisfiabilityproblem(SAT)isa
well-knownNP-completedecisionproblem,whereasreasoninginpropositional
Hornlogic(HORNSAT)isP-complete.Incontrast,satisfiabilityoffirst-order
HornclausesisundecidableSowa(2000).So,thereisalsoatrade-offbe-
tweentheexpressivityofabiddinglanguageandthetimetosolverespective
allocationproblemsusingdifferentinferencemechanisms.
ThepricingrulesintroducedintheLESSbiddinglanguagecouldbedescribed
asHornclauses.Inthispaper,wewillsolvetheallocationproblemasan
MILPandnotasalogicprogram,asMILPsaregearedtooptimizationwith
discreteandcontinuousvariables,whichisrequiredinourcase,whilelogic
programminghasitsstrengthwhenreasoningondiscretelogicvariables.There
isasubstantialliteratureontherelationshipbetweenmixedintegerlinear
programs(MILPs)andlogicprograms.Forexample,(ChandruandHooker,
1999)showedthatmanylogicalinferenceproblemscanbesolvedasarelaxed
linearprogrameventhoughtheyarenotHornclauses.
Wewilladdressthehardnessofthewinnerdeterminationproblemgivenan
LESSbiddinglanguageinthenextsection.Fornow,wewanttoconcentrate

40

GELANGUABIDDING3.1.

ontheexpressivenessofabiddinglanguage.Benischetal.(2008)trytodefine
generalnotionsofexpressivenessofeconomicmechanisms.Thisisanimpor-
tantnewstrandintheliterature,asmanyofthestrategiccomplexitiesandthe
inefficienciesofpopularauctionmechanismssuchassplit-awardauctionsor
thesimultaneousmultiroundauction(SMR)canbeattributedtothelimited
problemexpressivenessarisingofintheSMRbiddingthatcanlanguagebesolvused.edbAygoalloodwingexamforpleispacktheageexpbidsosurein
combinatorialauctions(Cramtonetal.,2006).
canMilgromgive(rise2009to)alsosadditionalhowsunthatwanintedcertainequilibriasettingsandpooradditionalefficiencyexpressiv.There-eness
fore,hearguesforsimplifiedmechanismswithrestrictedmessagespacesand
showsthat,ifcarefullydesigned,simplificationcanavoidunwantedequilibria,
withoutwithoutahgourtingodefficiencyunderstanding.Findingofthegoodbidders’vsimplifications,aluationsorhowcostever,isfunctions.difficult
aDefinitionfunctionps:10.RIA→Rcompactofquantitybiddingforlanguaonegeoralmorlowsetoitemsdefinei∈Ithe.bidpriceas

Wewillalsousethetermbidfunctionforpsinthispaper.Suchabidfunction
hasaparticularparametricform.Clearly,themostcompactformatwouldbe
torevealtheparametersandthespecificationofthetruetotalcostfunctionina
directrevelationmechanismtoanauctioneer.Forexample,wewilluseamulti-
productcostfunctionwitheightparametersfortheexperimentalevaluation
insection5.1.Theparametricshapeofsuchcostfunctionsmightbenon-
linearanddifferentamongsuppliersandindustries,whichisjustoneofthe
reasons,whythetruespecificationofthefunctionistypicallynotrevealed
inpractice.Itisrathercommontospecifyvolumediscountsormarkupsfor
economiesordiseconomiesofscale.Suchvolumediscountscanbeformulated
aspiecewise-definedlinearfunctions,whichapproximatetheunderlyingcost
curve.Therefore,suchbidsaretypicallyanapproximationoftheunderlying
costfunction,evenifbiddersarewillingtorevealtheircoststruthfully.Letus
nowintroducedescriptionlengthasameasureforhowcompactbidderscan
describeinformationabouttheirpreferencesortheirunderlyingcostfunction.
Definition11.Thedescriptionlengthofabidconsistsofthebitstodescribe
theparametersofthebidfunctionpsforagivenmaximumapproximation
error,max,totheunderlyingutilityorcostfunction.

ofBiddingcostfunctions,languagesbutshouldtheallosamewfortimeaclosehaveaapprolowximationdescripoftionwide-sprlength.eadAtypbades

41

CHAPTER3.THELESSBIDDINGLANGUE

approximationwillmakeitdifficultfortheauctioneertofindanefficiental-
loprocation.ximations,Multi-unitastheybundonlylespbidsecifyincomdiscretepbinatorialointsbutauctationsthealloexpwenseforofcloseahap-uge
numberofbidsrequiredtodescribeabidder’scosts.

3.1.2TheLESSBiddingLanguage
talExistingvolumebidtypdiscounestinorthetotalliteraturequantitysupportdiscounspts,ecificsucthypesasoinfDaeithervenportincremen-and
Kalagnanam(2000)andGoossensetal.(2007).Incontrast,bidlanguages
weobservedinpracticeexhibitsubstantialstructuralvariationacrossbidders.
quanOfferstityfromdiscounsuppliersts,depcanendingcomeoninmanyultiplecombconditinationions.ofToincremenaccomtalmoordatettotalhe
richnessobservedinpracticeoneneedsalanguagethatallowsfordifferent
discounttypes,denotedRd.
yInondcasetheofproductiondiseconomiescapacitofyscale,ofaforsupplier,example,hewhenmightthweanvtoltoumecahargewardedrespisectbive-e
markupsRmtocoverhisincreasedper-unitcosts.Whilemarkupsareconcep-
tuallyequivalenttovolumediscounts,wewilluseaseparatenotationRmin
thenextsection,astheyneedtobemodeleddifferentlyinourMIP.
Inaddition,weregularlyobservedlumpsumdiscountsRl,whichdescribe
refundsofpartofthetotalprice.Forexample,ifthevolumepurchasedexceeds
athreshold,asuppliermightbewillingtoreducetheoverallpaymentbya
canfixedalsoamounbetRdefinedl=on$10,sp000endonSltheorquantotaltityprice.QlandThesearelumpoftensumusedtodiscoundescribtsRel
e.scopofeconomiesInEvLeryESS,supplierbidderss∈SshouldbsubmitseableatobasepexpressricePsuci,shforevdiffereneryttitemypesi∈ofIdiscounandthets.
maximumquantityEi,sheiswillingtosupply.Inaddition,hespecifiesvolume
discountsd∈D,lumpsumdiscountsl∈L,andmarkupsm∈Mtomodify
thebaIsepricebasedoncertainspendconditions.Thetotalbidpricefunction
ps:R→RofasetofitemsIcanbewrittenas

p

42

s(x1,...,xI)=i∈IPi,sxi,s−d∈DRdyd1{Cd}+m∈M

Rmym1{Cm}−Rl1{Cl}
∈Ll

GELANGUABIDDING3.1.

ifawherespRenddcdescribonditionesaCisvolumetrue,disce.g.,ountpafterertheunitquanthattitisyawexceedsardedonaacertainquantitloywyerd
dboundonquantity,Qd,orspend,Sd.NotethatQdandSdcanbedefinedona
Weparticularwilluseitemtheprotermvidedb”discounythetinsupplierterval”orandalsoreferasettoofspenditemsbyconditions,thissupplier.which
defineaunitpriceforaparticularquantityinterval.Volumediscountsofa
specificbiddercanbevalidforthetotalquantitypurchased(totalquantity
disc(volume)ounts)discorforountsthe).Thisamountalsohexceedingoldsforapre-spmarkupsecifiedRm.Lumpthreshold(sumincrdiscounementalts
Rlaredefinedonoverallspendorquantity,notonperunit.
Spflexibilitendcy.Byonditionsallo(Cwing)areanconditionalimportantdiscountslanguageandfeature,markupswhicwithhpallowossiblyformmucul-h
tipleconditions,weareabletoformalizeallfeaturesofbidsthathavebeen
consideredintheliteratureorwehaveencounteredinpractice.Spendcondi-
(Qtions)purcancbehased.definedForonaexample,setofifspitemsendandonbtheebaseditemsonAspandendB(Sis)ormorevolumethan
$100,000,asupplieroffersanlumpsumdiscountofRl=$4,000.Anelemen-
StaryA,B>spend100,000$conditionsorQAC>is2000.treatedCompasaositeliteralspendinpropconditionsositionaltakelogicthesucformhofas
aconjunctionofmelementaryconditions.Soingeneral,adiscountruletakes
theformofaHornclause,withC1∧C2...∧Ck=⇒R.Welimiteddiscount
rulesselectiontoHornproblemclauses,oftheinorderauctioneertokaseepcothencisecoasrresppossibleonding(seesuppliersectionquan4.1tit).y
Modelingdisjunctionsandconjunctionsintheconditionofsuchadiscount
ruleispossibleaswell,butrarelynecessaryaswefound.
Definition12(Discountrule).AdiscountruleFisaHornclauseoftheform
C1∧C2...∧Ck=⇒R,where

•Cisaliteraldefinedonspendlevelsorquantitylevelsforasetofitems,
withkk={1,..,K}beingthesetofrespectivespendconditions.
•cRount,isaadisctotalount,quantityi.e.,adisclumpount,sumoradiscrespount,ectiveanincrmarkup.ementalvolumedis-

Therulescannosuppliertbisealsoactiveableattothespecifysamedisjutime.nctivFeordiscounexample,trules,incasei.e.,tthewoorsuppliermore
purcAlternativhaseselymore,ifthanthesupplier$10,000frombuysitemmoreAthanandB,5,000thereunitsisafromdiscounitemtofA,$1.77.the

43

CHAPTER3.THELESSBIDDINGLANGUE

willdiscounchotoseisthe$1.02.discounOnlytonethatoftheseminimizestwohisdiscountotaltsiscost.eligible,andtheauctioneer
Definition13.AnLESSbidisatuple(P,E,H,K),where

•Pisasetofbaseunitpricesforeachitemi∈I,
•EisasetofmaximumquantitiesEi,sthatasupplierscanprovidefor
eachitemi∈I,
•HisasetofdiscountrulesF∈H,and
•KisasetofdisjunctionsspecifiedonthesetofrulesinH.

LESSprovidesexpressivenessatlowdescriptionlengthbyallowingtoexpress
stepfunctionstodescribetheaverageunitcostsofasupplier,ortherespective
piecewiselinearfunctionsdescribingthetotalcostfunctioncs(x).
VolumecriminationdiscounaccordtsofingthistosortPigoua(re1946also).InLreferredESStoweaisgnoresecondfirstordegreethirdpricedegreedis-
buypriceersordifferenbuyertiation,segmenasts,theseandwepricingfocusponoliciesbidsdifferenthataretiatesentamongtoaindividparticularual
buyerasaresponsetoarequestforquotation(RfQ)orinareverseauction.
Wewillalsoignoreproductdifferentiation,wheresupplierssubmitinformation
onandmpaultipleymentquathatlitativmighetattribdifferenutestiatesuchoasneprosupplierductfromattributes,another.termsofOften,delivtheseery
multipleattributesarequalitativstandareattdizedributesinanandRfQprice.inorderBiddingtoavoidlanguageshavingfortoconfigurabletrade-off
andmulti-attributeauctionshavebeendiscussedbyBichlerandKalagnanam
(2005mensions).inaAccordingtoBbusiness-to-businessichleretal.pro(2002),curemenwhotnegdistinguishotiation,Lamongisthreesuitabledi-
formulti-item,multi-unitnegotiations.ESS

44

4Chapter

TheSupplierandQuantity
Selection

Inthefollowing,wewillinvestigateabuyer’sproblem,whoneedstoselect
quantitiesfromeachsupplierprovidingbidsinLESSsuchthathiscostsare
minimizedandhisdemandissatisfied.WewillrefertothisproblemasSupplier
QuantitySelection(SQS)problemandintroducearespectivemixedinteger
wing.follotheinprogram

4.1TheSupplierQuantitySelectionProblem
ulationormF

Wewillfirstintroducesomenecessarynotation.Wewilluseuppercaseletters
forandparameterscalligraphicfon(tabletsfor4.2),setslow(tableercase4.3).lettersSetsforindexeddecisionbyvamemariablesberof(tableanother4.1),
setrepresentthesubsetofallelementsthatarerelevanttotheindex.

45

CHAPTER4.THESUPPLIERANDQUANTITYSELECTION

mini∈Is∈SPi,sxi,s−d∈DRdyd+m∈MRmym−l∈LRlcl+k∈KRkck

s.t.xi,s≥Wi∀i∈I(1)
∈SSxi,s≤Ei,s∀i∈I,(2)
S∈s∀i∈Idxi,sd−Ddcd≥yd∀d∈D(3d)
i∈Imxi,sm+Bcm−Dm≤ym+B∀m∈M(3m)
Bcd≥yd∀d∈D(4d)
n∈Njn−¯ce≥|Nd|cd∀d∈D(5d)
de∈Ed
n∈Nljn−e∈E¯lce≥|Nl|cl∀l∈L(5l)
|Nm|−1(jn+1)−ce≤cm+1∀m∈M(5m)
n∈Nme∈E¯
|Nk|−1(jn+1)−mce≤ck+1∀k∈K(5k)
n∈Nke∈E¯k
i∈InPi,snxi,sn−d∈DnRdyd+m∈MnRmym≥Snjn∀n∈N(6l,d)
i∈Ixi,sn≥Qnjn∀n∈N(7l,d)
i∈Ixi,sn−Qn<Bjn∀n∈N(8m,k)
xi,s,yd,ym≥0∀i∈I,
∀∀ds∈∈SD,,
M∈m∀cd,cm,cl,ck,jn∈{0,1}∀d∈D,
,L∈l∀∀∀nm∈∈NM,,
K∈k∀TheobjectivefunctionminimizestheproductofallbasepricesPi,sandquan-
titiesxi,sofitemipurchasedofsuppliers,subtractsthesumofalldiscounts
RdandlumpsumdiscountsRl,andaddsthemarkupsRmandlumpsum
.kmarkupsThefirstconstraints(1)ensurethatthedemandWiisfulfilled,andthesecond
setofconstraints(2)thattheamountpurchasedfromaproductidoesnot
46

4.1.THESUPPLIERQUANTITYSELECTIONPROBLEM
TIONORMULAF

ariablesVDecisionOccurrenceRangeDescriptionaraibleVxi,sAmountofitemiboughtfromsuppliers∈N0|S|∗|I|
ydAmountactiveindiscountd∈N0|D|
ymAmountactiveinmarkupm∈N0|M|
cdIndicatorfordiscountd∈{0,1}|D|
cmIndicatorformarkupm∈{0,1}|M|
clIndicatorforoveralldicountl∈{0,1}|L|
jnIndicatorforconditionn∈{0,1}|N|
Table4.1:ListofVariablesinSQS

Theexceedtheconstrainmtaximsetsum(3d)quanandtity(3m)Fi,sdeteprovidedrminebytheeacrelevhantsuppliervolumeofeacydhorquanym,titfory.
whichthediscountormarkupresp.isdefined,andBisasufficientlylarge
number.Forexample,ifDd=0,then(3d)definesatotalquantitydiscount,
wherediscounytdis=vxi,salid,,asotherwise,suchdeDsdcisribingsettoantheincrementhreshold,talvafterolumewhicydh=thexi,sv−olumeDd.
Tcanypicallyalsob,ethedefineddiscounontminultitervplealsitemsandi∈markupsI.holdforasingleitem,butthey
darametersPDescriptionarameterPPi,sBasepriceforitemiformsuppliers
RdAmount(pricedecrease)ofdiscountd
RmAmount(priceincrease)ofmarkupm
RRlkAmounAmountt(lump(lumpsumsumpapaymenyment)t)ofoflumplumpsumsummarkupdiscountkl
WiDemand(want)foritemi
Fi,sQuantitiythatsupplierscanprovideofitemi
DdDisplacementfordiscountd
DmDisplacementformarkupm
SQnMinimalMinimalspquanendtityforforspspendendconditionconditionnn
nBBig(enough)number
Table4.2:ListofParametersinSQS
Foreachdiscountrule,weintroduceabinaryvariablecd,cl,andcm.Such
decisionvariablesaredeterminedbasedonspendconditions,whichwedefine
47

CHAPTER4.THESUPPLIERANDQUANTITYSELECTION

inconstraintsets(6-8).Constraint(4)makessurethatadiscountisonly
provided(yi,s>0)iftherespectivebinaryvariableforthisdiscount,cd,is
true.Constraintsets(5d),(5l),and(5m)makesurethatifaparticularset
ofspendconditionsisgiven(jn=1),whichareapreconditionforadiscount,
markup,orlumpsumdiscount,thenalsotherespectivebinaryvariablecd,cl,
orcmistrue.|Nd|,|Nm|,and|Nl|describethenumberofconditionsthatneed
tobetruefortherespectivebinaryvariabletobecometrue.Theseconstraints
alsoallowtospecifysetsofrulesE¯⊂D∪M∪L∪K,whichcannotbeactive
atthesametimeastherespectiverule.
SetsDescriptionSetsuppliersallofSetSitemsallofSetIDSetofalldiscounts
markupsallofSetMLSetofalllumpsumdiscounts
KSetofalllumpsummarkups
InSetoffallitemsincludedinspendconditionn
NSetoffallspendconditions
NdSetoffallspendconditionsnecessaryfordiscountd
NmSetoffallspendconditionsnecessaryformarkupm
NlSetoffallspendconditionsnecessaryforlumpsumdiscountl
NkSetoffallspendconditionsnecessaryforlumpsummarkup+k
E¯dSetoffallpricingrulesthatdisablediscountd
E¯mSetoffallpricingrulesthatdisablemarkupm
E¯lSetoffallpricingrulesthatdisablelumpsumdiscountl
E¯kSetoffallpricingrulesthatdisablelumpsummarkupk
Table4.3:ListofSetsinSQS
Thefinalsetsofconstraints(6-8)modelsindividualconditionsonspendor
quantitythatneedtobefulfilledforaparticulardiscountruleinconstraintsets
(5).Forexample,constraintset(6l,d)specifiesaminimumspendcondition
forvolumediscountsandlumpsumdiscounts.Inwords,ifthetotalcost
includingmarkupsanddiscounts(notconsideringotherlumpsumdiscounts)
exceedsSn,thenanadditionallumpsumdiscountwillbegranted.Constraint
set(7l,d)determinesaminimumquantityconditionusedinvolumeandlump
sumdiscounts.Constraintset(8m)definesaminimumquantityconditionfor
rule.markupa48

4.2.SCENARIOANALYSIS

Gothatossensofferaetval.ariet(y2007of)itemsdescribusingethetotalproblemquantityofdiscounselectingts.aThesetofproblemsuppliersisre-
ferredtoasTQD.Theyhaveprovidedapolynomialreductionof3-dimensional
matching,awell-knownstronglyNP-completeproblem,toTQD.Showing
thatSQSisNP-completeisstraightforward,asitcontainsTQDasaspecial
case.Theorem1.ThedecisionversionoftheSQSproblemisstronglyNP-
omplete.c

Here,werefertoTQD’asthedecisionversionofthemore-for-lessvariantof
TQD,andSQS’asthedecisionversionofSQS.AnyinputforTQD’can
besolvedwithSQS’,andasolutiontoSQS’wouldsolveTQD’.SQS’is
obviouslyinNPsincegivenasolutionitsufficestochecktheconstraintsand
thevalueofthesolution.
WhilethisshowsthatSQSisatleastashardasTQDtosolve,itisinteresting
tounderstandhowtheincreasedexpressivenessofLESSimpactstheempirical
hardnessoftheproblem.Asisoftenthecase,theformulationoftheproblem
matters,andtherearesignificantdifferencesinruntimedependingonthe
modelformulation(Hooker,2009).

AnalysisScenario4.2

Weanalysis,willfoprocusoncurementscenariomanagersanalysistasypicallyatuseypicaluseadditionalcase.sideDuringconstrainscenatsrioto
exploredifferentawardscenarios.Forexample,apurchasingmanagermight
beinterestedinanoptimalallocationwithamaximumof5winners,orthe
millionoptimalallodollarscation,duetowherecertaintheriskspendonconsideratioanns.individualAnex-psupplierostisanalysislimitedbasedtoon1
alreadysubmittedbidsalsoallowstoanalyzethecostofaparticularconstraint
bycomparingtheobjectivevalueofrespectivescenarios.
Wewillnowdiscussanumberofsideconstraintsthatareimportantforpro-
curementmanagersandusedduringthescenarioanalysis.Purchasingman-
agerswanttosetalowerandanupperboundforthequantityasuppliercan
winoverall(Vsl,Vsu)in(9),oronaparticulariteml(uVi,sl,Vi,su)in(10).Also,
theywanttolimittheoverallspendperwinner(Ts,Ts)in(11).Inconstraint
sets(12&13)themaximumnumberofwinnersLisrestricted.

49

CHAPTER4.THESUPPLIERANDQUANTITYSELECTION

Vsl≤xi,s≤Vsu∀s∈S(9)
Vi,sll≤∈Ixi,s≤Vi,su∀i∈I,(10)
∀s∈S
Tsl≤i∈IsPi,sxi,s−d∈DsRdyi,d+m∈MsRmyi,m≤Tsu∀s∈S(11)
i∈Ixai,s≤≤BLas∀s∈S(13)(12)
s∈Ssas∈{0,1}∀s∈S

Thecuremennumtberofmanagersscenariostoknocanw,bwhicehhugeside,anditconstrainwouldtshabveeintheterestingbiggestforimpactpro-
ontotalcost.Forlinearprogramssuchinformationisprovidedbythedual
vavariablailableesofforrespmixedectivinetegersideconstrainprogramsts.andSucIPhddualitualyisainformationnotoriouslyisnotreaddifficultily
topicGuzelsoyandRalphs(2007);Williams(1996).Onecan,however,fix
thebinaryvariablestotheiroptimalvaluesandresolvetheMIPasalinear
program.Theresultingdualscanthenprovideusefulshadowpricesforcon-
straintssuchas(1),(9),(10),and(11).Itcanalsobehelpfultoincludethe
right-handsidesofcertainconstraintsasvariables,andaskwhetherthereisan
baewacardhievedscenariobythatconstrainimproingvesthetheobtotaljectivecostbyfunctionavcertainaluepercenaccordinglytage..ThisOverall,can
sensitivityanalysiscanprovidevaluablefeedbackforprocurementmanagers
lysis.anascenarioduringScenarioanalysiscanbechallengingfortheprocurementmanager,asthere
aremanydifferentsideconstraintsonecanexplore.Itwouldbeveryvaluable
tobinding,havedi.e.,ualhaveinformationthealargestvailableimpactthatontotalindicates,cost.whichUnfortunaconstraintelyts,areSQSmostis
amixedintegerlinearprogram.Theintegralityconstraintstransformthe
dualproblemproblemfromamighcontvhaexvetoanaobnon-conjectivveexfunctionoptimizatiovaluenthatproblemisandstrictlythelinsmallerear
thantheobjectivefunctionoftheprimalproblem.Inthiscase,thedual
variableswillnotprovideusefulinformation.
TheORliteraturehasaddressedtheproblemoffindingdualpriceinterpreta-
tionstointegerprogramsandMIPs(Williams,1996).Theclassicworkinthis
arearelaxationisGomoryoftheandMIP,Baumolwhich(d1960efine).linearTheyaddcombinationsadditionalofconstrainexistingtstoconstraintheLPts,

50

4.2.SCENARIOANALYSIS

untilthesolutionresultsinanintegersolution.Theresultingdualvaluescan
beimputedbacktotheoriginalconstraintsfromwhichtheywerederived.
inHotrowevduceder,tothesethepricesformareulationnotanduniquedifficultastheytoindepterendpretontheeconomicallysequence.ofGuzelsocutsy
andTheyRalphsalsod(escrib2007)eaprovidepracticalanapproacup-to-datehtosurveysensitivofittheyanalysisliteratureoninrighthist-handfield.
solvsideersvariables,returnlowusingerbwoundsarm-startingfortheproblemfunctionalitwithyainmomodifieddernrighMIPtsolvhanders.sideTheus-
ingtheinformationgatheredfromthebranchingtreeoftheoriginalproblem
solvsourceed.solvWeerranSymphonexpyerimen(htsttps://prowithandjects.coin-or.withoutwarmstartingorg/SYMPHONY/),inthewhopicen-h
providessuchfunctionality.However,theresultswerenotstableenoughto
ort.repApartfromdualinformationonindividualconstraints,itcanbehelpfulto
includetheright-handsidesofcertainconstraintsasvariables,andaskwhether
Thisthereiscananbeawacardhievedscenaribyothatconstrainingimprovesthetheobjectivtotalecostbfunctionyavcertainaluepercenaccordinglytage..

4.2.1PriceFeedbackinLESS
Thereisahugeliteratureoncompetitiveequilibriumpricesiniterativecombi-
natorialauctions(Parkes,2006).Linearaswellasnon-linearpricingconcepts
inthisliteraturehavebeendevelopedonlyforsimplebundlebidsandawinner
determinationwithoutadditionalsideconstraints.Withmorecomplexbid-
dinglanguagesandmultipleallocationconstraintsinSQSitisunclear,how
suchaskpricescouldbederivedinLESS.However,feedbackinformationis
importantineveryindirectmechanismtohelpbiddersimprovetheirbidsand
becomewinninginthenextround.
Mechanismdesignquestionsoranygame-theoreticalanalysisofiterativemech-
anismswithLESSisbeyondthescopeofthiswork.Nevertheless,pricefeed-
backcanbederivedbasedontheWDP.Wesuggestasingle-dimensionalask
pricebycalculatingtheheightofthelumpsumdiscount,abidderwouldhave
hadtoprovide,inordertobecomewinning.Forthis,abidderscanspecify
acertainvectorofdesiredquantitiesx1,s,...,xI,sandtheauctioneerresponds
byarespectivelumpsumdiscountRlask.Thislumpsumdiscountcanbecal-
culatedbyresolvingtheMILPwithaxi,sfixedtotheamountthatsupplier
swantstowinoneachitemi∈I.Thisissimilarinspirittothewinning

51

elslev

4.CHAPTER

SUPPLIERTHESELECTIONQUANTITYAND

describedinAdomaviciusandGupta(2005)forcombinatorialauctions,

althoughtheircalculationisdifferent.Whetheritispossibletoperformsce-

narioanalysisorderiverespectiveask

onthetimetosolverealisticproblem

tserimenexp

52

to

lyzeana

the

empirical

inprices

Insizes.

hardness

aninteractivemannerdepends

thefollowing,wewill

of

these

problems.

ortrep

on

5Chapter

SetuptalerimenExp

Inthischapterwewillintroduceavaluationmodelcalled“CoP-Costof
Production“thatgeneratesinstancesthatwewilluseinourexperimentsand
describehowwesettheexperimentsup.Wefocusedonthetwomainperfor-
mancemeterswewanttoexamine:thecomputationtimedependentonthe
problemsizeandthesavingsinspendversussimplermechanisms.

5.1ValueModel”CostofProduction“

Thekeycomponentinanexperimentwithcomputationalsimulationsisthe
inqualittheiryofworktheaboutgeneratedatesttestsuitedata.forAscomdescribbinatorialedbyauctionsLeyton-Bro“thewnlacetkal.of(2000stan-)
paredardized,algorithms,realisticitdotestescasesmakedoitesdifficultnotmaktoeknoitwimpwhatossibletomagnitudeevofaluatereal-worcom-orld
problemsproblemseaceachhalgorithmalgorithmisiscapablecapableofofexsolving,ploiting“.orwhatfeaturesofreal-world
Intheirenvironmentatestcaseconsistsofasetofbidsforwhichtherevenue
maximizingallocationshallbedetermined.Inordertogeneratethemtheyuse
amodel,calledvaluemodelfromhereon,thatprovidesanumericalvaluefor
everypossiblebundledescribingthevalueofit.Thissocalledvaluationcan
Asthen,themdepweendingwillon”assumetheaassumedsealed-bidstrategyincenoftivthee-compatiblebidders,mectranslatedhanism,intowhbids.ere
theauctionspricesetting,offeredfor[...]eviseryequalbundletoandthebidderbiddersavbidisaluation.“placedInwithacomthebidbinatorialprice

53

CHAPTERSETUPALEXPERIMENT5.

settothevaluationofthebidder.Aswehaveseeninsection2.2.9thiswould
leadtoanunmanageablehugenumberofbidsinoursetting,andwewant
tointerpolatethecostfunctionwithfewerbids.Naturallytheinterpolation
methodandqualityhaveabigimpactontheperformanceofthesupplierand
algorithm.selectionytitquanInordertomakeourvaluemodelrealisticandclosetobusinessreality,we
deriveditfromthetheoryofcostofproductionineconomics,asdescribed
forexampleinPindyckandRubinfeld(2005).Thecostofproductionisnot
theonlyfactorimpactingthepriceofagood,butaccordingtoKalecki(1991)
thereareindustrieswherethepriceiscost-determined.

ositionComp5.1.1Costof

Thetotalcostdescribesthetotaleconomiccostofproducingagivenquantity
ofanobject.Thegraphofthecostofproducingagivenquantityofanobject
iscalledacostcurve.Thereareseveraltypesofcostcurves,whichareall
relatedtoeachother.Themostbasiconesaretotalcostcurves,plottingthe
costtoproduceaquantityofanobjectagainstthequantityproduced.Average
totalcostcurvescapturetherelationshipbetweenthecostofproducingone
copyoftheobjectandthequantitythatisproduced.Finallymarginalcost
betcurvweseenarethemarginalfirst(i.e.,derivativincremeneofatal)totalcostcostincurredcurveandandtherepresenquanttitytheofrelationoutput
duced.proThetotalcostisusuallyconsideredtobecomposedoffixedandvariablecost.
Ineconomicsitisusuallyalsodifferedbetweenlongandshortruncost,but
forusonlytheshortruncostisofinterest,asitinfluencesthepricesdirectly.

CostFixed5.1.1.1

Fixedcostsdifferfromvariablecosts,astheyareindependentofthequantity
produced.Theyarenotpermanentlyfixedassunkcosts,butinrelationto
thequantityofproductionfortherelevantperiod.Considertheexampleofa
smallpresentlogisticsindependencompantlyyofthewhereamounthetcostofofdelivleasingerydoneatrucwithktoit.Asdeliveronegocaondsseeis
infigure5.1fixedcostsleadtoflattotalcostsandmarginalcoststhathave
onlyapeakatthefirstunitbutdecreasingaveragetotalcost.Fixedcoststhat

54

5.1.VALUEMODEL”COSTOFPRODUCTION“

Figure5.1:Total,purchasedaverageifonlyandfixedmarginalcostsofcosts1000dep$areendentponresentthenumberofunits

canbespreadagainstabiggerquantityaretheprimarysourcesofeconomies
scale.of

Figure5.2:Total,purchasedaverageifonlyandstepmawiserginalfixedcostscostsdepofendent200$onarethepresentnumberofunits

Theassumptionofcoststhatarefixedforallpossibleamountsisverynarrow.
Thereforeweincludedstepcosts,alsocalledsemi-fixedcosts,thatremainfixed
onlyoverarangeofunitsproducedandincreasetoahigherlevelonceacritical
levelofoutputhasbeenreached.Infigure5.2itcanbeseenthatthesteps
arediminishingintheaveragecostperspectivebutnotinthemarginalcost
perspective.Inourexample,asecondtruckmightbeneededasthecapacity

55

ofthefirstoneisfullyutilized.

SETUPALEXPERIMENT5.CHAPTER

CostariableV5.1.1.2Variablecostsontheotherhandchange,inproportiontothequantitythat
isproproduceduced.constanIntafigureverage5.3wandemcanseearginalthatcost.linearThisvcanariablebeincoststerponolateditsowneasilydo
withexampleasinglethisprice,couldbbeoththewithcostforincrementhetalfuelandused,totalwhicquanhistitylineardiscouninthets.wIneighourt
k.tructheof

Figure5.3:Total,purchasedaverageifonlyandvamariablerginalcostscostsof1dep$areendentpresentonthenumberofunits

IneconomicsliteraturePindyckandRubinfeld(2005)averagecostisgenerally
thoughttobeU-shaped,becauseforlowquantitiestheeconomiesofscale
dominateuntilanoptimalpointfromwherethediseconomiesofscalebecome
t.dominanInourexamplevariablecostscouldrelatetothecostsofthelaborneededfor
handlingthegoodstransported.Foramountsthatcanbehandledbyregular
staffintimeitisdecreasing,butwhenthecapacityisfullyutilizedthecost
pisointincreasingfromwhbereonecausetheyofthegrowovfasterertimewthanork.linearVarwithiablethecostsamounthereforetpurchavhased.ea
Tasseenogetherinwithfigurefixed5.4.costsIftheretheyarecomnotbineonlytoasupU-shaperlineedaravvariableeragecostcostpresenfunctiont
butalsostepwisefixedcoststheaveragetotalcostgets”W“-shapedasseen
.5.5figurein

56

5.1.VALUEMODEL”COSTOFPRODUCTION“

Figure5.4:Total,averageandmarginalcostsdependentonthenumberofunits
purchasediffixedcostsof1000$andsuperlinearvariablecostsare
resentp

Figure5.5:Total,averageandmarginalcostsdependentonthenumberofunits
purchasedifstepwisefixedcostsof200$andsuperlinearvariablecosts
resentprea

Thismakesthesecondderivativenon-continuousandtheapproximationwith
volumediscountshard.Apossiblewaytoavoidthis,ifthejumpsinthecost
functionareknown,istouselumpsummarkups.

57

SETUPALEXPERIMENT5.CHAPTER

5.1.2ParametrizableCostFunction
Inordertogeneratesimulationinstancesweneedtodefineafunctionthat
canontheonehandrepresentallthecharacteristicswehaveseeninthe
previoussection,andontheotherhanditmustbepossibletoparameterize
it.randomizeeatablyrepand

5.1.2.1ParametrizableSingleItemCostFunction
Weproposethefollowingfunctiontogenerateourinstanceswithallavailable
parametersaresummarizedintable5.1.Similarcostfunctionshavebeenused
toestimatecostparametersofcompanieswithmultipleproductsoroutputs
(Baumol,1987;EvansandHeckman,1984;Stewart,2009)ineconomics.

ci,s(xi,s)=Bi,sxi,s/zi,s+αi,sxi,s+βi,s(xi,s/γi,s)ρi,s
Thefirstphenomenonwe’veseenare,possiblystepwise,fixedcosts,whichcan
bedistributedoveranincreasingnumberofgoodsforincreasingdemand,and
leadtodecreasingaveragecosts.Thisismodeledbythefirstelementand
thereforeparameterofthecostfunctionBi,s.Thisdescribestheitemspecific
stepwisefixedcostforitemi,wherezmodelsthecapacitybound,afterwhich
anadditionalBi,sofcostsarise.Note,thatwithstepwisefixedcostspresent,
thecostfunctionisnotcontinuousanymore.
arametersPfunctionCostDescriptionarameterPBi,sItemstepwisefixedcostofsuppliersforitemi
zi,sCapacityofproductionlineforitemifromsuppliers
αi,sLinearvariablecostofsuppliersforitemi
βi,sSlopeofthenonlinearvariablecostofsuppliersforitemi
γi,sDelayofthenonlinearvariablecostofsuppliersforitemi
ρi,sExponentofthenonlinearvariablecostofsuppliersforitemi
Table5.1:Singleitemcostfunctionparameters

Thesecondphenomenonisthe,possiblynon-linear,variablecost.Wehave
includedαi,sdescribingthelinearpartofthevariablecosts,thoughthispa-
rameterisnotbyitselfnecessaryinordertorepresentallthecharacteristics,

58

5.1.VALUEMODEL”COSTOFPRODUCTION“

becausetogetherwiththefixedcoststheyallowdifferentsupplierstobethe
cheapestatdifferentdemandlevels.
iβi,sandisdescribalsoesthenotslopindispeofensablethebutnonlinearmakespartofbalancingthevbariableetweencoststheforfixedproductand
variablecostseasier.ρi,sistheexponentofthenonlinearelementinthecost
isvfunction,erysensitivrepresenetotingthisparameterdiseconomiesandofforscale.valuesThe≥shap1.3eitofbtheecomescostdominanfunctiont
evenformoderatedemandlevels.
Inscaletopracticearisewe’vonlyeseenforthehighcostdemandcurveslevtoelsbebutrelativthereelyflatquiteandsharp.Indiseconomiesourcostof
functionthisismadepossiblebyγi,swhichdelaystheeffectofthenonlinear
partofthecostfunction.Problemsinstanceswithonlyasmallflatproportion
toofsolvnearebmiecausenimalavlargeeragepartscostsofarethenotcostonlycurvesdounrealisticnotbutneedtoalsobeatcoypicallynsidered.easy

5.1.2.2ParametrizableMultiItemCostFunction
Oneofourkeycontributionsisthepossibilitytoincludeeconomiesofscopeand
functionthereforewetherebalsoymwanusttedbtoecomeaincorp”numorateberofthemindifferentotourgooexpdteypriments.es”-dimensioThecostnal
function,givingacostforeverypossiblecombinationofamountsofthegoods.
Therearesynergies(similarities)twomainbetsourcesweenofitems.economiesBothofcanscopbee,addedsharedeasilyfixedtothecosts,singleand
function:costitem

cs(x1,...,xI)=
Asi∈Ixi/Wi+i∈IBi,sxi/zi+i∈Iβi,s(xi/γi,s)ρ+i∈Ixii=jχi,j,sxj
Asdescribesthefixedoverheadcostofsuppliersandχi,j,sisusedtomodel
synergiesbetweentwoproductsiandj.Thetermrepresentingthesynergies
issquarerootedtomakeitalinearpartofthecostfunctionandcanmodel
botheconomiesanddiseconomiesofscopewithnegativeandpositivesvalues
ofχi,j,s.Table5.2givesasummaryofallavailableparametersinthemulti
function.costitemEachoftheseparametershastobechosencarefullyinordernottodegenerate
function.costresultingthe

59

SETUPALEXPERIMENT5.CHAPTER

arametersPfunctionCostDescriptionarameterPAi,sOverheadcostofsuppliers
Bi,sItemstepwisefixedcostofsuppliersforitemi
zi,sCapacityofproductionlineforitemifromsuppliers
αi,sLinearvariablecostofsuppliersforitemi
βi,sFactorofthenonlinearvariablecostofsuppliersforitemi
γi,sDelayofthenonlinearvariablecostofsuppliersforitemi
ρi,sExponentofthenonlinearvariablecostofsuppliersforitemi
χi,j,sCrossitemcostsynergyofsuppliersforitemiandj
Table5.2:Multiitemcostfunctionparameters

5.1.2.3arametrizationPosedProp

Eventhebestparameterizablecostfunctionwillnotgeneratemeaningfultest
instancesiftheparametersarenotchosencarefully.Fortherelatedfamilyof
knapsackproblemsithasbeenshownbyPisinger(2005)thatthecorrelation
betweentheweightandtheprofitofanitemhasabigimpactonthehardness
problem.theof

Figure5.6:Costfunctionbasecase(notrandomized)

bTheetweenequivthealenceamounoftthispurchasedcorrelationandintheourcostssettingforit.wThisouldbemapsthetoourcorrelatobser-ion
vcostsation,curvthatesareinstancesharder.whereInfigurethere5.6isayoulargecanrelativseetheelyflatshapareeaofinthethecostavcueragerve

60

5.1.VALUEMODEL”COSTOFPRODUCTION“

wediscussedusedasinabasesectioncase5.1.1forandoursimfeaturesulations.alargeItrelativincludeselyallflattheareapropintheertiesavweragee’ve
cost.Intable5.3youcanseewhichparameterswereusedtogeneratethiscost
e.curv

aluevDefaultariableV5000.0Bi,s33%zi20.0αi,sβ20.0i,s60.0γi,s15ρTable5.3:Parametersofthecostfuntionintheproposedbasecase

Ontheotherextremeinstancesthatincorporateconstantaveragecostsare
latetrivialthetoo,costbcurecauseveandthenthethereformareulnoationpabymenecomestmoadifierslinearneededprogramtoinwithoutterpo-
ts.constrainytegralitin

Randomization5.1.2.4

Inordertogeneraterandomprobleminstancesoutofthisparameterizable
tocostbefucarefulnction,tothebalanceparametersbetweenneedtogeneratingbedisturbinstancesedwithrandomlysuffici.enHeretvweariationneed
andkeepingthefundamentalcharacteristicsofthecostfunction.
Theparametersforarandomizedinstanceusuallyaredrawnfromaprobability
distribution.Bythecentrallimittheorem,thesumofanumberofrandom
variableswithfinitemeansandvariancesapproachesanormaldistributionas
thenumberofvariablesincreases.
haThevepricesfiniteformeansaproandductvareariances.affectedbThereforeyalargewencumhosebertoofdrafactworsallthatparametersclearly
formeanthebcosteingthefunctionbaseofparaaspmeterecificasininstancetablefrom5.3.aThenormalstandarddistributiondeviationwithwtheas
setto“W”-shapvaluesedcostthatgavefunctionawideandspareectrumsummarizeofshapdines,tablebutin5.4a.veragestillyielda
Foreveryparametertherewasaplausibilitycheckadded,whichprevented

61

SETUPALEXPERIMENT5.CHAPTER

inconsistentvaluesandabolishedtherespectinginstances.Infigure5.7you
canseethreeexamplesofrandomlyparameterizedcostfunctions.

Figure5.7:Randominstacesofthecostfunctionforseeds2,3and9

Thepliersissimilaritanotheryofimptheortanpricestforfactorequalthatneedsamountstobepurchasedconsidered.fromFordifferenrealtwosup-rld
productsthepricesfromdifferentsuppliersareclearlycorrelatedthroughsim-
ilarproductionstandardsandthemarketpressurenivellatesdisparitieseven
further.InLeyton-Brownetal.(2002)theauthorshaveshownthatthenumberof
dominatedbidsisthekeycharacteristicforthecomputationalhardnessofa

62

5.1.VALUEMODEL”COSTOFPRODUCTION“

Variableµσitemσsupplier
500.02500.05000.0Bzii,s33%25%15%
βαi,s20.020.010.010.05.05.0
i,sγρi,s1560.020.02.010.00.5
Table5.4:Parametersofthecostfuntioninthebase(singeitem)case

combinatorialauctioninstance,andmanydistributionsproposedinthelitera-
turefailtogenerateasufficientnumberofthem.Thisleadstoamisjudgment
oftheproblemsizeandinterferespredictionsoftherunningtime.Analogously
tothedominatedbidsinLeyton-Brownetal.(2002)costcurvesthataredom-
inatedbyothercostcurvescontainmanypaymentmodifiersthatdonotneed
considered.ebtoAsseeninfigure5.7theshapesofthecostfunctionsfordifferentseedsare
quitevaryingbydesignandalotofthemwouldbedominatedifassignedto
thesameitem.Thereforewechooseatwostepprocesswherewehavedrawn
therespectiveparametersforacostcurveperitem.Andinasecondstep
addedadditionalvariationforeachsuppliertakingtherealizationoftheinitial
randomvariableasthemeanofanewsupplier-specificrandomvariable.The
respectivestandarddeviationvaluesareshownintable5.4andthreeresulting
supplierspecificcostcurvesareshowninfigure5.8.
Theresultingcostcurvestogetherwiththeamountdemandedalreadydefine
theoptimal,meaningcostminimizing,solutionoftheproblem.Translatedinto
acombinatorialauctioninstance,everypossiblecombinationofitemamounts
requestedwouldtranslatetoabid.ThesamewouldbepossibleinLESSby
specifyingapaymentmodifierforeverypossiblecombinationofitemamounts
requested.Thisextremeapproachclearlyisacontradictiontoourgoalof
reducingtherepresentationcomplexityforthebidders.Thereforethenext
stepwillbetoderiveruleshowsimulatedbidderscouldinterpolatetheircost
functionwiththepossibilitiesLESSoffers.

63

Figure

5.8:

5.CHAPTER

ALEXPERIMENTSETUP

Randominstancesofthecostfunctionforseeds2,3and9and
differentsupplierrealizationsindottedlines

GenerationBid5.2

Thebidgenerationdescribestheprocessofapproximatingthecostfunction
withLESS,similartowhathasbeendescribedin??.Theresultingfunction
willbecalledbidinterpolationfunctionfromhereon.

Note,thatinarealprocurementauctionsuppliersmightnotwanttoreveal

64

BID5.2.TIONGENERA

theirtruecostfunctionsifitisnotinducedbytheauctionmechanism.For
comauctionbinatorialforexampleauctionsasthisdescribcanedbinereac2.2.2.1hed.byNoteasofurther,calledthatifgeneralizedthevicapprokeyx-
imationunderlyingerrorcostgetsfunctionlargeandarbtheitrarilybidclose,languagethisdomighestnothaveallowantoimpactdescribonethethe
biddingstrategyandbiddersmighthaveanincentivetospeculate.
Theapplicabilityortransformabilityofthismechanismtoourproblemwould
beantheoreticalinanterestingalysisfurtheronlywmakorkesandsenseisifnotweexaminedalreadyhainvethisawthorkingesis.Agabiddingme
languageandsupplierselectionprocess,andthereforeweassumewellbehaving
bidderstoevaluatethepossibleperformanceofourapproach.
vealbAccordinglyidswreflectingeassumetheaunderlyingdirectrevtotalelationcostmecfunctionhanism,wheretruthfullyabiddersndastryclosetore-as
possiblewithoutunderbiddingtheircosts.Weanalyzetwotreatments:Either
thefixed,numorbtheerofsuppliersdiscountscanpersupplyitemanandthearbitrarycorrespnumbondingerofinquantervtitalsyintervdeterminedalsare
byapredefinedapproximationerrorsmax.

5.2.1FixedIntervalBidding

byOftentheinauction,practicalasthissettingsonlythebrequiresoundariestheofbiddersthepricetoinsubmittervalsaaresinglenpredefinedumber
perintervalindicatingthepricevalidinthatinterval.Thisalsocanbeeasily
implementedinawebformforexample.
Predefiningtheintervalsnaturallylimitstheexpressivenessofthebiddinglan-
costguage.Infunctionfigurewithout5.9youstepcanwiseseethefixedbidcostsinterpusingolationfivefunctionsequidistanoftinourtervstandaalsforrd
incrementalandtotalquantitybids.
Fwiseortotallinearquanintittheyinbids,tervals,whereonethecanrsee,esultingthatintheterpbidolationinterpfunctionolationisfunctionpiece-
overlapswiththecostfunctionatthepointofmaximalaveragecosts.As
totalquantitybidsdescribeapiecewiseconstantfunctioninaveragecoststhis
pointdeterminestheminimalpriceatwhichtheinterpolationfunctionnever
forliesbtheelowwholethecostamountfunction.purchased,Asforthetotalresultingquanintityterpdiscounolationtsthefunctionpriceinisvtersectsalid
theoriginofthecoordinatesystemintotalcosts,resultinginthetypicalsaw

65

SETUPALEXPERIMENT5.CHAPTER

Figure5.9:Comparisonoffixedintervalbiddingwith5intervals

toothshape.Theapproximationerrorincreaseswithanincreasinggradientof
theaveragecostcurve.

Withincrementalbidsontheotherhandthepriceisvalidonlyfortheincre-
mentalunitsandthetotalcostcurveofthebidinterpolationfunctiondosnot
incorporateanyjumps.Theresultingbidinterpolationfunctionisconstant
onmarginalmarginalcostcucostsrve.andAsthediscussedapproinximation??theerrorapprodepximationendsonerrortheofgradienincrementofthetal
bidsisnevergreaterthantheapproximationerroroftotalquantitybidsfor
functions.costexvcon

Iffixedthecostscostforfunctionexample,itselfthisdoesdoesincorpnolongerorateholdjumps,forasallcases.generatedThebystepjumpswisein
nototallongercostoveffectserlapwthatiththethebidcostinfunterpctionolationatthefunctionintervforalbincremeoundarnies.talbidsThereforedoes
inthetervalapproboundaryximation.Terrorotalcanquangettitybidsarbitrarilydonotbigifsufferajumpfromothisccurseffectclosebuttothean
interpolationerroralsotendstoincreasewiththepresenceofstepwisefixed
scale.smalleraoncosts

66

GENERABID5.2.TION

Figure5.10:Comparisonoffixedintervalbiddingwith5intervalsandstepwise
costsfixed

5.2.2FixedApproximationErrorBidding

TheintentionofLESSwastomakeithandleableforbidderstoexpresstheir
costfunctionbyreducingthenumberofpricedneeded.Thereforeweinvesti-
angatedbtheoundedquestionapprohoximwationmanyerrorpricedandarewhicnheededimpactotexpresshasathiscostonfuncticomputationonwith
end.sptotalandtimeToanswerthisquestionweimplementedasimulatedbiddingagentthatinter-
polatesagivencostfunctionwithagivenapproximationerrorusingaslittle
intierstervasalspossible.regardingItthefeaturestolerablegreedyapproapproacximationhthaterrorgeneratesrelativetomaximallythecurrenwidet
totalcosts,startingatasingleitem.In5.11youcanseetheresultingbid
functions.ximationapproThelargeapproximationerrorsforincrementalbidswithfixedintervalsare
breakscausedfbyreely,disadvasinanLEStageousS,ainjumptervalinbthecostoundaries.functionIfbidderscanbecaninterpdefineolatedthepricewith
anincrementalmarkupfollowedbyanincrementaldiscount.Thejumpin
totalwithancostincrementranslatestalintoatervalspikofeinlengthmarginal1.costs,whichcanbeinterpolated

67

5.11:Figure

5.CHAPTER

SETUPALEXPERIMENT

Comparisonoffixedapproximationerrorbiddingwithamaximum
erro25%ofr

Fortotalquantitybiddingtheadvantageofhavingfreelysettablepriceranges
isnotasoutstandingbutitallowsthebidderstoexpresstheircostsfunc-
tionsascloseasdesired.Forbothdiscounttypeshavingfreelysettableprice
rangesallowstointerpolateanygivencostfunctionexactlybydefiningaprice
individuallyforeverypossiblequantity.

68

TIONGENERABID5.2.

5.2.2.1FixedApproximationErrorBiddingwithLumpSumMod-
ifiers

Aspointedoutin5.1.1jumpsinthecostfunctioncannotonlybeexpressedas
apairofanincrementaldiscountandmarkupinLESS,butalsobysocalled
lumpsummarkups.Iflumpsummarkupsareusedtoexpressjumpsthenet
costfunctionisconvexagainandincrementalbiddingreducestopiecewise
linearinterpolationasdescribedin??.

Figure5.12:Comparisonoffixedapproximationerrorbiddingwithamaximum
errorof25%withoutfixedcosts

Infigure5.12youcanseetheapproximationofourstandardcostfunction
thewherefixedthecostsfixedarecostsalreadysettocovzero.eredThisusingreflectslumpthesumsituationmarkups.aWithbiddernofacesfixedif
costsincremenpresentaltthebiddingaverageonlycostsmarkupsareneededstrictlytoincreasing.describetheThereforenonlinearitthereyatarehighfor
amounapparents.tForabsencetotalofquanfixedtitycostsbiddinmakgesthethetotalsituationcostevenfunctioimpronvgoesmorethroughasthethe
originofthecoordinatesystem.

69

70

CHAPTER

5.

ALEXPERIMENT

SETUP

6Chapter

talerimenExpResults

Inthischapterwewillsummarizetheresultsofoursimulationexperiments.

Cost6.1yFlexibilitof

Goossensetal.(2007)providedatailor-madeformulationfortotalquantity
discountbids,aswellascomputationalresultsonrandomlygeneratedtest
instances.Incontrast,LESSprovidesbidderswithmoreflexibilityandallows
forothertypesofvolumediscountsandvariousspendconditions.Typically,
moreflexibilityandexpressivenesscomesatthecostofcomputationalcom-
plexity.Itisinterestingtosee,iftheexpressivenessofLESScomesatalarge
cost.computationalTherefore,inafirstsetofexperiments,weusedthesyntheticbids,whichwere
kindlyprovidedbyGoossensetal.(2007)foracomparison.Theseexperiments
arelimitedtobidswithtotalquantitydiscountsonly.
Intheirinstanceswith40items,Goossensetal.(2007)generatedan
upperbound-increasefromoneintervaltothenext,whichwasarandomnum-
berbetween10,000and50,000,whileforinstanceswith100items,theup-
perboundincreasewasarandomnumberbetween10,000and100,000.The
resultsoftheformulationinGoossensetal.(2007)withabranch-and-cutap-
proachandwiththeSQSformulationcanbefoundinTables6.1and6.2.We
focusonthebranch-and-cutresults,sincethoseprovidedthebestresultsfor
largerinstances.NotethatwehaveusedCPLEXversion12.1,whileGoossens

71

Instances34010S54010S310010S10010S5

SS2020404035
SS202010010053

SS5050404035
SS505010010053

RR1010404035
RR101010010053

RR2020404035
RR202010010035

CHAPTER6.EXPERIMENTALRESULTS

SQSb&cGoossensb&c
comp.time#nodescomp.time#nodes
0.080.1716.49.30.150.0910.90.3
0.20.1250.1331.11.133.20.55

0.160.870.492.40

0.795.872.4521.67

0.071.100.223.814

0.293.761.4129.75

10.936.717.132.1

34.6102.928.094.8

6.785.57.270.8

18.7138.525.9274.9

0.120.500.341.17

0.512.991.4510.45

0.090.590.141.50

0.291.810.836.81

0.54.72.12.1

2.716.52.114.7

2.130.52.631.7

9.568.58.170.1

R504032.0171.31.6781.6
R5040526.90346.514.18140.9
R50100312.7591.98.8443.8
R501005451.84996.061.71216.8
Table6.1:ComparisonofSQSagainsttheresultsbyGoossensetal.(2007)(base
case)

etal.(2007)usedversion8.1.Also,theyusedaPentiumIV2GHzcomputer
with512MbRAM.Nevertheless,thecomparisonhelpsunderstandpossible
penaltiesforamoreexpressivebiddinglanguage.

72

FLEXIBILITYOFOSTC6.1.

Instancescomp.SQStimeb&c#nodescomp.Gotimeossensb&#nocdes
SS10104040530.160.0512.66.20.490.1423.20.4
SS1010100100531.050.0926.42.12.480.2966.56.8
SS20204040350.120.8731.98.90.454.42148.75.2
SS2020100100532.080.4428.811.111.472.08164.243.4
S504030.6119.48.90261.9
SS505040100532.176.02100.620.4147.5628.422500.0523.7
S50100521.0284.7271.803006.0

RR10104040530.710.0740.76.30.670.1018.50.1
R1010030.197.50.170.2
R1010053.1951.52.4942.6
R204030.2412.80.6015.9
R204052.6480.73.5589.8
RR20201001005331.381.073222125.091.85434.817.6
RR505040405321.821.65298.749.1169.8235.161511.11196.8
RR505010010035400.6810.781064.368.62036.07274.82176035.4577.4
Table6.2:ComparisonofSQSagainsttheresultsinGoossensetal.(2007)(more
less)rfo

Interestingly,muchlargerinstancescouldbesolvedtooptimalitywiththisset
ofbidsinseconds,andthedifferencesinruntimebetweentheresultsreported
byGoossensetal.(2007)andtheresultsofSQSweresmall.Theresultsfor

73

CHAPTER6.EXPERIMENTALRESULTS

thebasecaseinTable6.1whereabitslower,whiletheresultsforthemore-
aimedfor-lessforscenariooptimalinTsolutionsable6.2withwerefreeactuallydisposaloffaster.additionalThequanmore-for-lesstity,whilescenariothe
not.didcasebase

Obviously,thestructureofthebidshasasignificantimpactontheruntime.
Thebidsgeneratedbasedonourmulti-productcostfunctionwereconsiderably
hardersolutionstowithsolve.similarWeobassumejectivethatfunctionsmovothalue,costatypefunctionsofsymmetrygeneratealotproblem.of
ThewhereinstructuredtervalswithinstancesmoreinquanGotitossensyhaveteal.low(er2007)pricesincludethaninterveconomiesalsofwithscale,less
quantity,whereasthecostfunctionsinourpaperalsoincludediseconomiesof
runscale.timesAlsocantheincrease,demandbcanecausemakthereeaaredmoreifference.pIfossiblethequandemandtitiesistopurcincreased,hase.

Instructuresummaryof,thethebidspredictivandethequalitrespyofectivsucehscaleruntimeeconomiesexperimeninatsmarkdepet.endsOvonerall,the
ouranalysisrevealsthatsurprisinglylargeinstancescanbesolvedtooptimality
withthesetypesofbids.

74

6.2.VALUEMODELCOSTOFPRODUCTION

6.2ValueModelCostofProduction

InourmainexperimentsweusedthevaluemodelCOPtogenerateinstancesas
describedinchapter5.1.WeusedtheseinstancestoevaluateLessandSQS
withrespecttothecomputationalandcommunicationalburdenaswellas
thepossiblesavingsinspendrelativetoasplitawardauction.Computation
timeiscentralifSQSistobesolvedinaninteractiveanalysisofdifferent
awardscenariosduringthescenarioanalysis.Thebidevaluationshouldnot
takemorethanaminute,asthisallowsexploringdifferentsideconstraintsin
aninteractivemanner.Inthissection,wehavethereforesetatimelimitof
60secondsandreportedthecurrentbestsolutionfornotprovenoptimalor
instances.optimalsub

6.2.1InstancesItemSingle

Inthefirstsetofexperimentswegeneratedinstancesasoutlinedinsection
5.1.2.4withasingleiteminordertoevaluatetheimpactofscaleeconomiesin
isolation.Intable6.3theparametersoftherunsaresummarized.
aluesVariableVNumberofsuppliers2,8,32,64
Numberofitems1
Numberofpriceintervals4,8
Acceptableapproximationerror1%,25%
1-30SeedTable6.3:Parametersofthesingleitemruns

6.2.1.1DescriptionLength

Wbidehavlanguagee,discussedtheindescriptionsectionleng3.1.1ththatmatters.apart6.1fromshothewshowexpressivthenumenessberofofa
intervalsintheSQSformulationincreaseswithadecreasingmaximalabsolute
approximationerrorsmax.Therequirednumberofdiscountintervalsismuch
higherfortotalquantitybids.
Thelargenumberofintervalsneededtodescribeacostfunctionwithalow
approximationerrorcanmakebiddingimpractical.Notethatinanincentive

75

CHAPTER6.EXPERIMENTALRESULTS

Figure6.1:Descriptionlengthcomparisonofincrementalvs.totalquantitybidsin
LESSfor32supplierinstancesofthebasecase

truthfullycompatiblemighmectnothanismbeasuchdominanasthetVicstrategy,krey-Clarkunlesse-Grothevesbiddingmechanism,languageallobiddingws
describingtheunderlyingcostfunctioncloseenoughwitharealisticnumber
bids.of

Figure6.2:Comparisonofnumberofpriceintervalsfordifferentincrementaland
totalquantitybiddingpoliciesfor30singleitemCoPinstances

Infigure6.2wehaveplottedtheresultingnumberofpriceintervalsforthe
parametersusedinoursimulations.Theboxesshowthenumberofintervals
thatweregeneratedasdescribedinsection5.2.

76

6.2.VALUEMODELCOSTOFPRODUCTION

Forincrementalbiddingthenecessarynumberofpriceintervalswasalways
belowtenevenwithanapproximationerrorof1%.Fortotalquantitybidding
ontheotherhand,evenanapproximationerrorof25%demandedaround20
priceintervals.Thisshows,theburdenforthebidderstocommunicatetheir
costfunctionnearlyexactlyisonlymanageableusingincrementalbidsinthese
settings.

BurdenComputational6.2.1.2

Infigures6.3,6.4and6.5onecanseeacomparisonofthecomputationtime
neededtosolveSQSforinstanceswith2,8and64suppliersandfordifferent
olicies.pbidding

Figure6.3:Comparisonofcomputationtimefordifferentincrementalandtotal
quantitybiddingpoliciesfor30singleitemCoPinstanceswith2
suppliers

Thenumberofintervalsgreatlyinfluencestheexpectedcomputationtimefor
SQS,whichcanbeclearlyseeninourresults.Allinstancesexcepttheones
withtotalquantitybidsandanapproximationerrorlimitingbiddingpolicy
couldbesolvedtoprovenoptimalitywithin60seconds.Withanallowed
approximationerrorof25%onlyafewinstancestimedout,whereaswithan
allowedapproximationerrorof1%andatleast8suppliersmorethanhalfof
out.timedinstancestheTheinstanceswithafixednumberofpriceintervalscouldallbesolvedto
optimalityinlessthan20seconds.Atfourpricelevelstotalquantityinstances

77

CHAPTER6.EXPERIMENTALRESULTS

Figure6.4:Comparisonofcomputationtimefordifferentincrementalandtotal
quantitybiddingpoliciesfor30singleitemCoPinstanceswith8
suppliers

totookokmlessoretimethanon10avtimeserageasbutlongat8aspricetheinresptervectivalsesomeincrementotaltalquantitinstances.yinstance

Figure6.5:Comparisonofcomputationtimefordifferentincrementalandtotal
quantitybiddingpoliciesfor30singleitemCoPinstanceswith64
suppliers

Overallonecansaythattheusageofincrementalbids,ofpredefiningafixed
numberofpriceintervals,makesscenarionavigationpossibleforauctions
wherebigquantitiesofonlyonegoodareauctioned.

78

6.2.VALUEMODELCOSTOFPRODUCTION

ComparisonendSp6.2.1.3

TheformulationoptimalitforySthatQS,isandmeneventionedanin100the%optimalprevioussolutisectiononcanrelatesonlytobetheasgoMIPod
asthebidsthatweresubmitted.Forrealworldusesthespend,thetotal
ties,amounistthethatmosttheimpauctioneerortantbhasenctohmark.payinInrealorderwtoorldgetcasesthethedemandedmostquancommonti-
ersapproacsubmhisittingtotusewoanpricesplitaquoteswardforauceaction.hitemThereforeat30%weandused70%simofulatedthevolusuppli-me
inasplitawardauctionasthepointofreference.

Figure6.6:Comparisonofspendrelativetoansplitawardauctionfordifferent
incrementalandtotalquantitybiddingpoliciesfor30singleitemCoP
suppliers2withinstances

Infigures6.6and6.7thespendthatresultedfromusingLessandSQSwith
thedifferentbiddingpoliciesagainstasplitawardauction.
Itisveryoutstanding,thatthespendofallincrementalauctionswasnearly
equal.Theaveragespendoftheinstanceswithanallowedapproximationerror
25%was0.027%higherthantheoneresultingfromanallowedapproximation
errorof1%.Evenifonly4fixesintervalswereusedthespendwasonly0.45
percenthigher.Totalquantitybidsshowedsimilarresultsforthebidding
policieswithanapproximationerrorbound.Forfixedpriceintervalstheresults
havebeennotsogood.Intheworstcaseandonly4intervalsavailablethe
spendwasevenhigherthanwithasimplesplitawardauction.Thisdidonly
happenforalownumberofsuppliersastherearefewalternativesolutions,
andtheoptimalsolutioncanbeblockedbyabadcostapproximation.

79

CHAPTER6.EXPERIMENTALRESULTS

Figure6.7:Comparisonofspendrelativetoansplitawardauctionfordifferent
incrementalandtotalquantitybiddingpoliciesfor30singleitemCoP
suppliers64withinstances

6.2.2SingleItemInstanceswithLumpSumDiscounts
Markupsand

InLesssuppliershavetheoptiontodefinesocalledlumpsumdiscounts
andmarkups,thatareaonetimepayment.Theselumpsumdiscountsand
markupscanbeinterpretedasadirectwaytocommunicatejumpsinthecost
function,asillustratedinsection5.2.2.1.Inpracticethebidderswillonlyvery
seldombeableandorwillingtocommunicatethisinformationsothisismore
alue.vtheoreticalofInfigure6.8onecansee,thattheuseoflumpsummarkupstoindicatethe
jumpsinthecostfunctionmakescomputingSQSfaster,andallinstances
couldbesolvedinlessthanasecond.Figure6.9showsthespendifbidders
usewithinlumplesssumthan0.1markups.%oftheForalloptimuerrorm.bWithoundincremenbiddingtalpobidslicies4thepricespinendtervwalsas
werealsosufficienttogetclosetotheoptimalspend,andalsototalquantity
lot.aprofitedbids

80

6.2.VALUEMODELCOSTOFPRODUCTION

Figure6.8:Comparisonofcomputationtimefordifferentincrementalandtotal
quantitybiddingpoliciesfor30singleitemCoPinstanceswith64
suppliers

Figure6.9:Comparisonofspendrelativetoasplitawardauctionfordifferent
incrementalandtotalquantitybiddingpoliciesusinglumpsum
discountsandmarkupsfor30singleitemCoPinstances

6.2.3MultiItemInstances-RealisticProblems

Finally,wewilldiscusstheimpactofthedifferentdiscountpoliciesonthe
totalcostofthepurchasingorganizationwhenauctioningmultipleitemsat
once.Thisisthemostrealisticbutalsomostchallengingscenarioforthe
biddinglanguageandsupplierselection.Incontrasttothesingleitemcases
wherewefocusedonelaboratingeffectsscaleeconomiesonbiddingandsupplier

81

CHAPTER6.EXPERIMENTALRESULTS

selection,wetriedheretoexploretheapplicabilityofLessandSQSforrealistic
instances.itemultimAgain,weassumeadirectrevelationmechanism,andbidderssubmittheir
bidinawaythatapproximatestheirtruecostsascloseaspossible,either
restrictedbythenumberofintervalsorapredefinedapproximationerror.We
simulatedsupplierssubmittingtwopricequotesforeachitemat30%and70%
ofthevolumeinasplit-awardauctionusingthevaluemodelcostofproduction
withparametersoutlinedas5.1.2.4.Thesamesuppliersalsosubmitbidsin
anauctionwithonlytotalquantitydiscountbids,andinanauctionwithonly
incrementalvolumediscountbids.Forthelattertwoauctiontypes,wealso
distinguishedsettingswithafixedsetof5intervals,oranapproximationerror
%.1.0ofTheresultsaresummarizedinTable6.4.Eachrowsummarizestheresultof
aparticularvolumediscountauctionrelativetothecostofthesplit-award
auctioninpercentagevaluesafter5,10,20,60,120,and500seconds.All
reportednumbersareaveragenumbersfor30instancessolved.
Aspendgreaterthantheonethatcouldberealizedbyansplitawardauction
canbearesultoftwofactors,eithertheinterpolationerroristoobigorthe
currentintegersolutionistoofarawayfromtheoptimum.Thereforewehave
thenanalyzedtheprovenoptimalityoftheseinstances,andtheMIPgapafter
5,10,20,60,120and500secondscanbefoundin6.5.Avalueof−1.000
meansthatthebestboundfoundsofarisstill≤0,andthereisnomeaningful
MIPgapreportedbythesolver.
Asonecanseetheincrementalinstanceswith5intervalswerenotsolvedto
optimality,whiletheinstanceswithtotalquantitydiscountscouldbesolved
tooptimalityevenforlargerinstanceswith30suppliersand10itemsin2
minutes.SotheMIPgapoftheincrementalvolumediscountbidswasalways
higher,whenthenumberofintervalswaslimitedtofive.Withalimitonthe
approximationerrorto1%,thenumberofintervalsgrowsuptomorethan80
intervalsperitemincaseoftotalquantitydiscountbids,butonlyuptoaround
30intervalsincaseofvolumediscountbids.Interestingly,theinstanceswith
onlyincrementalvolumediscountbidsarestillhardertosolveandtheMIP
gapistypicallylarger.So,thestructureoftheproblemswithtotalquantity
discountsallowsforlargerproblemstobesolved.
Wewillnowtakealookatthespendwithafixednumberof5intervals.Ifthe
MIPgapishigh,thenalsothespendwithtotalquantitydiscountbidsand
incrementalvolumediscountbidscanbemuchworsethanwithsimplesplit

82

6.2.VALUEMODELCOSTOFPRODUCTION
SuppliersItems5sSpendin%10sofsplita20swardswith60stimelimit120s500s
Totalquantity5intervals
1010101.13100.94100.94100.02100.94100.94
1030101.22101.22101.22101.58101.22101.22
30101050101.44102.28101.44102.20102.19101.44102.45101.44102.19101.44102.1101.494
3030102.75102.59102.57103.80102.56102.56
3050102.79102.69102.48102.74102.27102.27
Incremental5intervals
1010103093.6597.3193.4795.5093.4994.6793.2794.8493.4594.4893.4694.40
1050103.54100.7296.7095.8795.6295.46
301096.7694.8694.3792.6394.2894.21
30305030115.53109.45113.37109.09107.40105.02103.0797.8197.9895.9795.8595.62
Totalquantity=1.0
101093.5993.6093.6093.5293.2587.89
103029311.8395.3795.3795.7795.3695.17
3010105031571117653.66.8829585.3497.3697.3496.6596.4997.4497.3696.6496.96.9664
303092869.8592869.8592869.85102.60102.30102.29
305082807.6583589.5283589.5292582.93103.08103.08
Incremental=1.0
10101030374.7187.72132.4087.7394.4786.3590.6886.0988.0886.2787.6986.15
1050450.39335.86123.0295.0889.9489.19
3010930.91184.2296.9689.4687.8887.29
303030501449.131675.841277.11433.8731350.741333.95162.00696.10103.73150.8494.0890.97
Table6.4:Comparisonofspendrelativetoasplitawardauciton
athewardMIPgapauctions.waslow.Therefore,Inweterestinglywill,inmainlythelooksettingatthewithcolumntotalquanwithtity500s,bidswheandre
5intervals,thespendachievedwashigherthanthatofsplitawardauctions,
althoughthesmallerinstancescouldbesolvedtooptimality.Thereasonfor
thisisthebadapproximation.Incontrast,incrementalvolumediscountbids
83

CHAPTER6.EXPERIMENTALRESULTS

Optimalitywithtimelimit
TotalSuppliersquantityItems,5intervPricesals5s10s20s60s120s500s
101051.0001.0001.0001.0001.0001.000
103051.0001.0001.0001.0001.0001.000
30101050551.0000.9970.9981.0000.9991.0000.9991.0001.0001.0001.0001.000
30305030550.9890.9930.9910.9960.9930.9970.9960.9980.9960.9980.9970.998
Incremental,5intervals
101050.9370.9440.9470.9630.9580.965
103050.8900.9090.9190.9270.9230.926
30101050550.8870.8440.9090.8670.9160.9040.9250.9180.9210.9160.9270.920
30305030550.3190.4380.5120.7650.7650.8020.8040.8770.8400.8810.8660.889
T10otalquantit10y<1.080.410.6360.6800.7250.7750.8120.868
103077.36-1.0000.5090.5580.6380.6810.758
105076.65-1.000-1.0000.4960.5820.6150.699
301080.41-1.0000.5150.5840.6460.6930.760
3030305077.3676.92-1.000-1.000-1.000-1.000-1.000-1.0000.4930.0000.5290.4410.6210.549
Incremental<1.0
101028.200.5950.8110.8800.9370.9110.946
103025.28-1.0000.2190.3750.4120.5380.597
105024.58-1.000-1.0000.3280.4380.4990.576
301028.20-1.000-1.000-1.000-1.0000.0960.168
3030503024.5225.22-1.000-1.000-1.000-1.000-1.000-1.000-1.000-1.000-1.000-1.000-1.00.10800

Table6.5:Provenoptimalityofthesolutionsintable6.4

achievedalowertotalcostcomparedtosplitawardauctionsforallproblem
sizesalreadyafter120seconds.Thiswasthecase,eventhoughtheproblems
couldnotbesolvedtooptimalitywithin500seconds.
Insituations,wheretheapproximationerrorwaslimitedto1%,totalquantity

84

6.2.

VALUEMODELCOSTOFPRODUCTION

discountbidsledtocostsavingsafter500secondscomparedtosplit-award
auctions.Largerinstanceswith30suppliersand30itemsledtoalargeMIP
gapevenafter500secondsandtheresultswereworsethanthoseofasplit
awardauction.Alsointhissetting,theincrementalvolumediscountsledto
lowertotalcostcomparedtosplit-awardauctionsforallproblemsizes,but
alsocomparedtototalquantitydiscountbidsafter500seconds.

85

86

CHAPTER

6.

ALEXPERIMENT

TSRESUL

7Chapter

okOutloandConclusion

Conclusion7.1

Wehavesuggestedabiddinglanguageformarketswitheconomiesofscaleand
scopeandarespectiveMIPtosolvetheresultingsupplierquantityselection
(SQS)problem.Wetrytoeasytheproblematicbiddingcomplexity,inducedby
thehugenumberofpossiblebidcombinations,forthebiddersinacombintorial
auction.Thisproblemwe’veshown,bynumericalsimulations,tobealimiting
factoroftheperformanceofcombinatorialauctionsingeneral.Thisgetseven
worseinprocurementsettings.
Theproposedbiddinglanguageisconsiderablymoreexpressivethanwhathas
beendiscussedintheliteraturesofarandincludesincrementalvolumedis-
counts,totalquantitydiscounts,lumpsumdiscounts,andavarietyofspend
conditionsdefinedonspendandquantityofselecteditems.Whileboth,in-
crementalvolumediscountbidsandtotalquantitydiscountbids,havebeen
describedintheliteratureandareusedinprocurementpractice,therehasnot
beenathoroughcomparisonamongthosediscountpoliciesasofyet.Thisis
thefirstpaper,tousedifferenttypesofcostfunctionstogeneratebids,which
allowedustoanalyzenotonlycomputationtimes,butalsototalspendof
differentdiscountpolicies.
Ourresultsshowthatthatrealisticproblemsizescanbesolvedinamatter
ofminutes,butthatbigmultiitemproblemswithonlyincrementalvolume
discountbidsarehardertosolvethanthosewithonlytotalquantitydiscount
bids.Ontheotherhandifasupplierwantstoapproximatehistruecost

87

CHAPTER7.CONCLUSIONANDOUTLOOK

functionwithtotalquantitydiscountbidsclosely,thisleadstoamuchlarger
andnumberofdiscountintervals.
Therewereseveralsituations,wheretheresultsofsimplesplit-awardauctions
withsimplepricequotesleadtolowertotalcostthanthoseofmoreadvanced
biddinglanguages.Thereasoniseitherabadapproximationofthecostsorthe
inabilitytofindthecost-minimalsolutionwithinanacceptableresponsetime.
Forexample,ifsuppliersonlyusedafewtotalquantitydiscountintervals,this
ledtomuchhighertotalcostforthebuyer.However,wehavealsoshownthat
significantsavingscanbeachievedwithcompactbiddinglanguagescompared
tosplitawardauctions,ifbiddersareabletoapproximatetheircostfunctions
well.Eventhoughbiginstanceswithfewincrementalpriceintervalscouldnot
beproventobeoptimal,theresultingcostswerealwayslowerthantheones
resultingofasplitawardauction.
Insummary,aprocurementmanagerneedstotakecarethatthebiddinglan-
guageprovidesenoughflexibilitysothatbidderscandescribetheircoststruc-
turesarbitrarilyclose.Atthesametimebidsshouldhavelowdescription
length,suchthatsuppliersareonlyforcedtospecifyafewparametersandnot
hundredsofnumbers.Also,aprocurementmanagershouldmakesurethat
thenumberofbidsinanapplicationissuchthathecanexpecttosolvethe
probleminstancestooptimality.Theresultsofouranalysisshouldprovidea
betterunderstandingunderwhichcircumstancescompactbiddinglanguages
shouldbeusedinprocurementpractice.Mechanismdesignquestionshave
beenoutsidethescopeofthispaper,andremainfruitfulquestionsforfuture
area.thisinhresearcWhilethebidlanguageleadstomuchflexibilityforthesuppliersinspecify-
ingdiscountsinacompactformat,italsoincurscomputationalcomplexity
onthebuyer’sside.Practicalapplicationsspanawiderangeofpossiblecom-
putationaltimerequirementsrangingfromdemandinginteractiveusessuch
asscenarioanalysis,anddynamicreverseauctionswhereacceptablecompu-
tationaltimesmaybeinthescaleofminutes,tolessdemandingcasessuch
asmultipleroundnegotiationswhereruntimesinhours,oftendays,maybe
tolerable.WehaveanalyzedtheempiricalhardnessofSQSandthetimeto
solvevariousproblemsizesinordertounderstandtheimpactofdifferenttypes
ofconstraintsanddiscountsontheruntimewithafocusoninteractiveappli-
cationssuchasscenarioanalysis.
Theresultsprovideanunderstandingunderwhichcircumstancessuchexpres-
sivebiddinglanguagescanbeusedinprocurementpractice.Wehavealso

88

LOOKTUO7.2.

ofanalyzedthepurcthephasingotentialmanager,impactifofbidderssuchrevealbiddingtheirlanguagescostsontruthfullythe,totalandspefoundnd
thatthecostsavingsdependontheparametersofthecostfunctionandthe
used.languagebidding

okOutlo7.2

Ourgivingmainthegoalsuppliewasrsatobetterimprovpetheossiblitpytoerformanceexpressoftheirprocosts,curementandtheauctionstherbbyy
loingwoferingthethescenariocosts.forWiththebuyourer,computogethertationalwithexpproerimenvindintsgawebhaettervenshounderstand-wnthe
bidders,feasibilityandofourthereforeaproacahvinerificationpriciple,ofbutourrealevresultsentsbyalwlabaysexpincorperimenoratetshremainsuman
animportantopenissue.
Mechanismdesignquestionshavebeenoutofthescopeofthisworkandwe
haveassumedextremelywellbehavingbidders,whichclearlyisaverystrong
assumption.Agametheoreticalanalysisoftheproposedmechanismcould
thereforeprovidevalueableinsightshowbiddersmightbehaveinsuchapro-
t.enevtcuremenThecapabilityofthebidderstoexpresstheircost,iscrucialaswehaveseen,
ofandtotalcouldquantitgreatlyybbiddingenefitisfromstillavisualdominatingreprinesenrealtationproofcmentheirtevenbids.ts,asThetheyuse
theseemtoresultingappearcosts,easierastoforgraspexampleinastextualinform.section5.2Already,couldavhelperyinsimplepromotingplotof
thetheuseresultingofincremenjumpsintalthediscouncosttsinfunction.ouropinion,astheywoulddemonstrate
Initerativecombinatorialauctionsthebiddersgainfeedbackinbetweenrounds
bytheformofaskpricesandcanimprovetheirbidsaccordingly.Inpractical
settingsfurtherguidanceofthebiddersisnecessaryasScheffeletal.(2010)
haveshownintheiranalysisoflinearpriceauctionsandthereinalsoimportance
ofbidderdecisionsupport.Forcombinatorialauctionswehaveseenthat
thesimplerlinearpriceauctionscanperformverygood,incontrasttotheir
limitations.theoreticalInsumsectiondiscount4.2.1wrequest.ehavIteremainssuggestedanainteresimplestingpricequestionfeedbacifksuchbasedavoneryasimplelump
feedback,thathastheadvantageofaveryeasyandfastcomprehensiveness,

89

could

S

QS

90

.

guide

the

ersbuy

CHAPTER

accordingly

in

7.

an

CONCLUSION

eiterativ

nactio

AND

based

KOUTLOO

on

L

ess

and

Bibliography

Abrac2004.he,AJanewwad,biddingBenoˆıtframewBourborkeau,forTeocomdorGabrielbinatorialCrainic,e-auctions.MichelComputersGendreau.&
OperationsResearch31(8)1177–1203.
Adomasupportvicius,inG.,iterativA.ecomGupta.binat2005.orialTowauctions.ardscomprehensivInformationeSystemsreal-timeResearbidderch
169–185.16(ISR)An,N.,W.Elmaghraby,P.Keskinocak.2005.Biddingstrategiesandtheirim-
pactonrevenuesincombinatorialauctions.JournalofRevenueandPricing
.ManagementAusubticalel,comL.,P.binatorialCramton,auctionP.Milgrom.design.P.2006.CramTheton,clocY.k-proShoham,xyauctioR.n:SteinAbprac-erg,
eds.,CombinatorialAuctions.MITPress,Cambridge,MA.
AusubY.el,Shoham,L.,P.R.SteinMilgrom.berg,2006a.eds.,AscendingCombinatorialproAxyuctionsauctions..MITP.Press,CramtCam-on,
MA.bridge,PAusub.el,CramL.,ton,P.Y.Milgrom.Shoham,2R.006b.SteinbTheerg,loeds.,velybutCombinatoriallonelyvicAkreyuctions.auction.MIT
MA.bridge,CamPress,Baumol,W.J.1987.Microtheory:ApplicationsandOrigins.1sted.MIT
USA.MA,bridge,CamPress,Beniscmech,hanisms.M.,N.23rdSadeh,AAAIT.ConferSandholm.enceon2008.AArtificialtheoryIntelofligence.expressivenessin
Bichler,curemenM.,tA.auctDaions.venpP.ort,CramG.ton,Hohner,Y.J.Shoham,Kalagnanam.R.Steinb2006.erg,eds.,IndustrialCombina-pro-
torialAuctions.MITPress.

91

BIBLIOGRAPHY

Bichler,M.,J.Kalagnanam.2005.Configurableoffersandwinnerdetermina-
160tion(2)inm380–394.ulti-attributeauctions.EuropeanJournalofOperationalResearch
BicG.hler,Lin,M.,Y.J.Lu.Kalagn2002.anam,ApplicationsK.ofKatircioglu,flexibleA.pricingKing,inR.Lawrence,business-to-businessH.Lee,
electroniccommerce.IBMSystemsJournal41287–302.
Bicpricehler,M.,iterativP.ecomShabalin,binatorialA.Pikovskyauctions..2009.AInformationcomputationalSystemsRanalysisesearofch20linear-(1)
33–59.Bikhchandani,S.,J.M.Ostroy.2002.Thepackageassignmentmodel.Journal
ofEconomicTheory107(2)377–406.
Blumrosen,L.,N.Nisan.2005.Onthecomputationalpowerofiterative
auctions.ACMConferenceonElectronicCommerce(EC05).Vancouver,
Canada.17thBoutilier,C.,InternationalH.H.HoJointos.2001.ConferBidencedingonAlanguagesrtificialforIntelcomligencebinatorial(IJCAI)auctions.2001.
1211–1217.USA,ashington,WJohnChandru,WileyV.,J.&HoSons.oker,eds.1999.OptimizationMethodsforLogicalInference.
EurChaudhryope,anS.,F.JournalForst,ofJ.OpL.eraitonalZydiak.Rese1993.archV70endor52–66.selectionwithpricebreaks.
Chen,Yan,KanTakeuchi.2009.Multi-objectauctionswithpackagebidding:
AnBehaviorexperimentoapptalear–.comparisonofvickreydoi:10.1016/j.geb.2009.10.00andibea.7.GamesandEconomic
theCrama,Y.,presenceR.Pofascual,totalA.quanTtityorres.discoun2004.tsOandptimalaltproernativecuremenprotductdecisionsrecipes.in
EuropeanJournalofOperationalResearch159364–378.
Cramton,P.,Y.Shoham,R.Steinberg.2006.Introductiontocombinatorial
tionsauctions..MITP.Press,Cramton,CamY.bridge,Shoham,MA.R.Steinberg,eds.,CombinatorialAuc-

92

BIBLIOGRAPHY

Dang,V.,N.Jennings.2003.Optimalclearingalgorithmsformulti-unitsingle-
itemandmulti-unitcombinatorialauctionswithdemand-supplyfunction
bidding.Technicalreport,Dept.ofElectronicsandComputerScience,Univ.
.UKSouthampton,ofDavenport,A.,J.Kalagnanam.2000.Pricenegotiationsforprocurementof
directinputs.IMA¨HotTopics¨Workshop:MathematicsoftheInternet:E-
AuctionandMarkets,vol.127.Minneapolis,USA,27–44.
deVries,S.,J.Schummer,R.Vohra.2007.Onascendingvickreyauctionsfor
heterogeneousobjects.JournalofEconomicTheory13295–118.
Dunford,M.,K.Hoffman,D.Menon,R.Sultana,T.Wilson.2007.Testing
linearpricingalgorithmsforuseinascendingcombinatorialauctions.Tech.
rep.,GeorgeMasonUniversity.
Eso,M.,S.Ghosh,J.Kalagnanam,L.Ladanyi.2001.Bidevaluationinpro-
curementauctionswithpiece-wiselinearsupplycurves.Technicalreport
rc22219,IBMT.J.WatsonResearchCenter.
Evans,D.,J.Heckman.1984.Atestforsubadditivityofthecostfunction
withanapplicationtothebellsystem.AmericanEconomicReview74(4)
615–623.Gartner.2008.Magicquadrantforsourcingapplicationsuites.Tech.rep.,
Consulting.GartnerGomory,R.E.,W.J.Baumol.1960.Integerprogrammingandpricing.Econo-
521–550.28ametricGoossens,D.R.,A.J.T.Maas,F.Spieksma,J.J.vandeKlundert.2007.
Exactalgorithmsforprocurementproblemsunderatotalquantitydiscount
structure.EuropeanJournalofOperationalResearch178603–626.
Guzelsoy,M.,T.Ralphs.2007.Dualityformixed-integerlinearprograms.The
InternationalJournalofOperationsResearch4118–137.
Hohner,G.,J.Rich,E.Ng,G.Reid,A.Davenport,J.Kalagnanam,H.Lee,
C.An.2003.Combinatorialandquantitydiscountprocurementauctions
withmutualbenefitsatmars,incorporated.Interfaces33(1)23–35.
Hooker,J.N.2009.Aprincipledapproachtomixedinteger/linearproblem
formulation.INFORMSComputingSocietyConference.79–100.

93

BIBLIOGRAPHY

Jucker,J.V.,M.J.Rosenblatt.1985.Singleperiodinventorymodelswith
demanduncertaintyandquantitydiscounts:Behavioralimplicationsanda
newsolutionprocedure.NavalResearchLogisticsQuarterly32(4)537–550.
Kalecki,Michal.1991.CollectedWorksofMichalKalecki,vol.VolumeII:
Capitalism:EconomicDynamics.OxfordUnivP.
Katz,P.,A.Sadrian,P.Tendrick.1994.Telephonecompaniesanalyzeprice
quotationswithbellcore’spdsssoftware.Interfaces2450–63.
Kwasnica,T.,J.O.Ledyard,D.Porter,C.DeMartini.2005.Anewand
improveddesignformulti-objectiveiterativeauctions.ManagementScience
419–434.(3)51Kwon,R.H.,G.Anandalingam,L.H.Ungar.2005.Iterativecombinatorial
auctionswithbidder-determinedcombinations.ManagementScience51(3)
407–418.Lee,H.L.,M.J.Rosenblatt.1986.Ageneralizedquantitydiscountpricing
modeltoincreasesupplier’sprofit.ManagementScience321177–1188.
Leyton-Brown,K.,E.Nudelman,Y.Shoham.2009.Empiricalhardnessmod-
els:Methodologyandacasestudyoncombinatorialauctions.Journalof
1–52.56CMAtheLeyton-Brown,K.,M.Pearson,Y.Shoham.2000.Towardsauniversaltest
suiteforcombinatorialauctionalgorithms.
Leyton-Brown,Kevin,EugeneNudelman,YoavShoham.2002.Learningthe
empiricalhardnessofoptimizationproblems:Thecaseofcombinatorialauc-
tions.ConstraintProgramming(CP).556–572.
Milgrom,P.2009.Simplifiedmechanismswithanapplicationtosponsored-
searchauctions.GamesandEconomicBehaviortoappear.
Mishra,D.,D.Parkes.2004.Ascendingpricevickreyauctionsusingprimal-
dualalgorithms.Discussionpaper,HarvardUniversity.
Mishra,D.,D.Parkes.2007.Ascendingpricevickreyauctionsforgeneral
valuations.JournalofEconomicTheory132335–366.
Munson,C.L.,M.J.Rosneblatt.1998.Theoriesandrealitiesofquantity
discounts:anexploratorystudy.ProductionandOperationsManagement
352–369.(4)7

94

BIBLIOGRAPHY

Nisan,N.2006.Biddinglanguages.P.Cramton,Y.Shoham,R.Steinberg,
eds.,CombinatorialAuctions.MITPress,Cambridge,MA.
Nisan,N.,I.Segal.2001.Thecommunicationcomplexityofefficientallocation
problems.DIMACSworkshoponComputationalIssuesinGameTheoryand
MechanismDesign.Minneapolis,MI.
Park,S.,M.H.Rothkopf.2005.Auctionswithbidder-determinedallowable
combinations.EuropeanJournalonOperationalResearch161399–415.
Parkes,D.2006.Iterativecombinatorialauctions.P.Cramton,Y.Shoham,
R.Steinberg,eds.,CombinatorialAuctions.MITPress,Cambridge,MA.
Parkes,D.,L.H.Ungar.2000.Iterativecombinatorialauctions:Theoryand
practice.17thNationalConferenceonArtificialIntelligence(AAAI-00).
Pigou,A.C.,ed.1946.TheEconomicsofWelfare.Macmillan&Co.Ltd.,
London.Pindyck,RS,DLRubinfeld.2005.Microeconomics(6thedn).
Pisinger,D.2005.Wherearethehardknapsackproblems?Computers&
OperationsResearch32(9)2271–2284.
Plott,C.,T.Salmon.2002.Thesimultaneousacendingauction:Dynamicsof
priceadjustmentinexperimentsandintheu.k.3gspetrumauction.Social
ScienceWorkingPaper1155,CaliforniaInstituteofTechnology.
Porter,D.,S.Rassenti,A.Roopnarine,V.Smith.2003.Combinatorialauction
design.ProceedingsoftheNationalAcademyofSciencesoftheUnitedStates
ofAmerica(PNAS)10011153–11157.
Rassenti,S.,V.L.Smith,R.L.Bulfin.1982.Acombinatorialauctionme-
chanismforairporttimeslotallocations.BellJournalofEconomics13
402–417.Rothkopf,M.H.2007.Thirteenreasonswhythevickrey-clarke-grovesprocess
isnotpractical.OperationsResearch55191–197.
Rothkopf,M.H.,A.Pekec,R.M.Harstad.1998.Computationallymanageable
combinatorialauctions.ManagementScience441131–1147.

95

BIBLIOGRAPHY

Sandholm,T.2008.Expressivenessinmechanismsanditsrelationtoeffi-
ciency:auctions,Ourandexprecenteriencetheory.fromProc$40eedingsbillionofofthecom2ndbinatorialInternationalmulti-attributeWorkshop
onComputationalSocialChoice.

Sandholm,T.,S.Suri.2001.Marketclearability.ProceedingsoftheInterna-
tionalJointConferenceonArtificialIntelligence.IJCAI.

rialSandholm,auctions.Tuomas.Decision1999.SuppApproacorthesSystemsto28winner(1)165–176.determinationincombinato-

Scheffel,T.,A.Pikovsky,M.Bichler,K.Guler.2010.Anexperimentalcom-
parisonoflinearandnon-linearpricecombinatorialauctions.Information
SystemsResearchtoappear.

Schneider,S.,P.Shabalin,M.Bichler.2010.Ontherobustnessofnon-linear
personalizedpricecombinatorialauctions.EuropeanJournalofOperational
Research206(1)248–259.

pSelten,ointsR.in1975.extensivAegames.reexaminationInternationalofthepJournalerfectnessofGameconceptTheforory4equilibrium25–55.

Silvmenterson,andR.,proE.A.ductionPeterson.planning.1979.JohnDeWilercisionandsystemsSons,forNewYinventoryork.manage-

Sowa,J.F.2000.KnowledgeRepresentation:Logical,Philosophical,andCom-
putationalFoundations.BrooksColePublishingCo.

Stewart,K.G.2009.Non-jointnessandscopeeconomiesinthemultiprod-
uctsymmetricgeneralizedmcfaddencostfunction.JournalofProductivity
Analysistoappear.

Williams,ming.H.JournalP.of1996.DualitOptimizationyinThemathematicsoryandandAppliclinearationsand90integer257–278.program-

96