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

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.6Comparisonofspendrelativetoan