Decision Support for Multiple-Unit Combinatorial Auctions
No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology |
Licentiate thesis
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Author
Date
2007
Department
Major/Subject
Yritysstrategia ja kansainvälinen liiketoiminta
Mcode
TU-91
Degree programme
Language
en
Pages
140
Series
Abstract
The purpose of this study is to develop and test a support tool for bidders in a semi-sealed-bid, multi-unit, combinatorial auction. We consider a reverse auction setting. Combinatorial auctions, i.e. auctions in which bids are placed for bundles of different items, are complicated bidding environments. The formulation of bidding strategies is difficult, because there is a certain cooperative flavor to bidding. The winning bids complement each other, unless the winning bid is for the whole combination. In sealed- and semi-sealed-bid auctions bidders are unaware of the bids placed by their competitors. Thereby, it is impossible to place bids that would be good complements for other bidders' bids. So far there has been very little research in helping bidders find complementing combinations. Thus, we have designed a support tool that offers bidders a list of bids that would complement existing bids, and become the provisional winners of the auction. Our quantity support mechanism can be formulated as a mixed integer programming problem. The objective is to maximize the profit of the bidder subject to constraints requiring that the buyer's demand for each item is met, and that the total cost to the buyer decreases by a certain decrement. We do not assume to know the bidders' cost structures, and thus the cost function is approximated with a linear function. The parameters of the linear function are the dual prices of the demand constraints from the winner determination problem (the dual prices can be interpreted as market prices). We tested our quantity support mechanism with two separate simulation studies. In the first study we compared the quantity support mechanism using dual prices with a mechanism using randomly chosen parameters in the linear cost function approximation. The results indicate that the dual price mechanism finds better bid suggestions. In the second study we examined the efficiency of the auction outcomes. We compared the final allocations of auctions in which quantity support was used, and final allocation in auctions in which it was not used to the theoretically efficient allocation. The efficiency of quantity support auctions was significantly higher than the efficiency of other auctions. We also studied the effects of initial parameter choices (number of bidders, degree of economies of scope, bidders' capacities and the logic for initial bid generation) affected the outcome. The results seemed rather insensitive to changes in the initial setting. Assuming equal capacities across bidders, increasing the number of bidders improved the efficiency of the outcome, but only marginally. We conclude that quantity support mechanism improves the efficiency of the auction outcomes, and it is a useful support tool for bidders.Tässä lisensiaattityössä tutkitaan tarjoajien päätöksenteon tukemista suljetuissa, kombinatorisissa huutokaupoissa. Tarkastelen käänteisiä huutokauppoja, joissa tarjoajat ovat myyjiä. Kombinatorisissa huutokaupoissa tarjoukset tehdään erilaisten hyödykkeiden yhdistelmille. Tarjousten tekeminen tällaisessa huutokaupassa on monimutkaista, sillä voittavat tarjoukset täydentävät toisiaan, ellei sitten yksi tarjous täytä koko kysyntää. Suljetuissa huutokaupoissa tarjoajat eivät tiedä toistensa tekemiä tarjouksia, joten heidän on mahdoton tietää, millainen tarjous täydentäisi hyvin olemassa olevia tarjouksia. Toistaiseksi on tehty hyvin vähän tutkimusta tarjoajien päätöksenteon tukemisesta. Siksi olemme suunnitelleet työkalun, joka auttaa tarjoajia löytämään sopivia hyödykekombinaatiota täydentämään olemassa olevia tarjouksia. Työkalu ehdottaa eri hinta-hyödyke -kombinaatioita, jotka kaikki olisivat sillä hetkellä huutokaupan voittajien joukossa. "Quantity support" -työkalumme on formuloitu kokonaislukuoptimointiongelmana. Tavoitteena on maksimoida tarjoajan voitto ehdolla, että kaikkien hyödykkeiden kysytyt määrät täyttyvät ja että ostajan kokonaiskustannus alenee tietyllä summalla. Oletamme, että tarjoajien kustannusfunktiot ovat tuntemattomat, joten turvaudumme lineaariseen approksimaatioon kohdefunktiossa. Approksimoidun kustannusfunktion kertoimet saadaan sen optimointitehtävän, jossa ratkaistaan voittajat, kysyntärajoitteiden varjohinnoista. Nämä varjohinnat voidaan tulkita hyödykkeiden markkinahinnoiksi, joten päätimme käyttää niitä kustannusten approksimointiin. Olemme tehneet kaksi erillistä simulaatiotutkimusta testataksemme "quantity support" -työkalua. Ensimmäisessä tutkimuksessa vertasimme "quantity support" -työkalua vastaavanlaiseen työkaluun, jossa varjohinnat oli korvattu satunnaisesti valituilla luvuilla. Tulokset osoittivat, että käyttämällä varjohintoja löydetään tarjoajien kannalta parempia tarjouksia. Toisessa simulaatiotutkimuksessa tutkimme huutokauppojen lopputilanteen tehokkuutta. Vertasimme sellaisia huutokauppoja, joissa "quantity support" -työkalu oli käytössä ja sellaisia huutokauppoihin, joissa se ei ollut käytettävissä teoreettisesti tehokkaaseen lopputulokseen. Totesimme, että ne huutokaupat, joissa "quantity support" -työkalua käytettiin, päätyivät keskimäärin merkittävästi tehokkaampaan lopputuloksen. Tutkimme myös simulaatioparametrien (tarjoajien määrän, rinnakkaistuotannon etujen suuruuden, tarjoajien kapasiteettien ja ensimmäisen tarjousten luontilogiikan) vaikutusta lopputulokseen. Tulokset vaikuttivat olevan suhteellisen riippumattomia alkuarvoista. Asettamalla tarjoajien kapasiteetit yhtä suuriksi tai kasvattamalla tarjoajien määrää saatiin tehokkuutta parannettua, mutta vain vähän. Olemme sitä mieltä, että "quantity support" -työkalu parantaa kombinatoristen huutokauppojen tehokkuutta ja on hyödyksi tarjoajille.Description
Supervisor
Wallenius, HanneleThesis advisor
Wallenius, HanneleWallenius, Jyrki
Keywords
combinatorial auctions, kombinatoriset huutokaupat, decision support, päätöksenteon tukeminen, electronic auctions, sähköiset huutokaupat