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

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.

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2011
• Nombre de lectures: 15
• Langue: English

Extrait

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