Pricing and bidding strategies in iterative combinatorial auctions [Elektronische Ressource] / Alexander Pikovsky

Sujets

• Handel

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2008
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

Institut fur¨ Informatik
der Technischen Universit¨at Munc¨ hen
Lehrstuhl fur¨ Informatik XVIII
Pricing and Bidding Strategies in
Iterative Combinatorial Auctions
Alexander Pikovsky
Vollst¨andiger Abdruck der von der Fakultat¨ fur¨ Informatik der Technischen
Universit¨at Munc¨ hen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Michael Beetz, Ph.D.
Prufer¨ der Dissertation:
1. Univ.-Prof. Dr. Martin Bichler
2. Univ.-Prof. Alfons Kemper, Ph.D.
Die Dissertation wurde am 30.01.2008 bei der Technischen Universitat¨
Munc¨ hen eingereicht und durch die Fakult¨at fur¨ Informatik am 07.07.2008
angenommen.For Vita PikovskayaAbstract
Auctions have been getting increasing attention in computer science and eco-
nomics, as they provide an efficient solution to resource allocation problems
with self-interested agents. E-Commerce and finance have emerged as some
of their largest application fields. The need for new auction mechanisms that
allow for complex bids such as bundle bids and multi-attribute bids has been
raised in many situations. In addition to strategic problems, the design of
these multidimensional auctions exhibits hard computational problems. For
example, thewinnerdeterminationtypicallyleadstoNP-hardallocationprob-
lems in combinatorial auctions. More recently, researchers have focused on the
pricing and information feedback in combinatorial auctions.
Iterative combinatorial auctions (ICAs) are IT-based economic mechanisms
in which bidders submit bundle bids iteratively and the auctioneer computes
allocations and ask prices in each auction round. Several ICA designs have
beenproposedintheliterature, butverylittlewasknownabouttheirbehavior
in different settings. The multi-item and discrete nature of ICAs and complex
auction rules defy much of the traditional game theoretical analysis in this
field. The literature provides merely equilibrium analysis of ICAs with non-
linear personalized prices under strong assumptions on bidders’ strategies. In
contrast, ICAs based on linear prices have performed very well in the lab and
in the field.
Computational methods and laboratory experiments can be of great help in
iii
exploring potential auction designs and analyzing the virtues of various design
options. The goal of our research was to benchmark different existing ICA
designs and to propose new, improved auction rules. We focused on linear-
price auctions, but also included one ICA design with non-linear personalized
prices.
In the computational simulations we compared three selected linear price ICA
designsandtheVCGauctionbasedonthe allocative efficiency, revenue distri-
bution, and speed of convergence using different bidding strategies and bidder
valuations. We found that ICA designs with linear prices performed very well
for different value models even in case of high synergies among the valuations.
There were, however, significant differences in the efficiency and revenue dis-
tribution of the three ICA designs. Even heuristic bidding strategies in which
bidders submit bids for only a few of the best bundles led to high levels of
efficiency. We have also identified a number of auction rules for the ask price
calculation, bidder activity, and auction termination that have shown to per-
form very well in the simulations.
In the laboratory experiments we compared the same auction designs and one
ICA design with non-linear personalized prices in respect to the same perfor-
mance measures. We were able to identify several similarities to the compu-
tational results, but also quite heterogeneous bidding behavior, which did not
correspond to the pure myopic best-response bidding strategy in any of the
auction designs. Nevertheless, we achieved high efficiency levels in all auction
designs. Furthermore, we identified significant differences in the auctioneer
revenue depending on the auction design, but not on the number of the auc-
tioned items (3, 6, and 9). We also observed a very low speed of convergence
of the ICA design with non-linear personalized prices, which makes it (at least
in its current form without using proxy agents) hardly suitable for practical
applications.Zusammenfassung
Auktionen haben in den letzten Jahren zunehmende Aufmerksamkeit in In-
formatik und Wirtschaftswissenschaften gewonnen, da sie zur effizienten Al-
lokation von Ressourcen eingesetzt werden konnen.¨ Zu ihren gr¨oßten Ein-
satzgebieten geh¨oren unter anderem die Finanzbranche und E-Commerce. In
vielen F¨allen wurden dabei neue Auktionsmechanismen nachgefragt, die kom-
plexe Gebote auf mehrere Guter¨ oder unterschiedliche Eigenschaften eines
Gutes erm¨oglichen. Abgesehen von der strategischen Komplexit¨at, wird die
Konstruktion solcher Verfahren zus¨atzlich durch die Komplexit¨at der dort
auftretenden Berechnungsprobleme erschwert. Zum Beispiel geh¨ort das Al-
lokationsproblembeikombinatorischenAuktionenzurKlassederNP-schweren
Probleme. In jung¨ ster Zeit haben sich Wissenschaftler vorwiegend auf der
Preissetzung und auf den Arten der als Feedback ub¨ ermittelten Informationen
fokussiert.
Iterative kombinatorische Auktionen (ICAs) sind IT-basierte o¨konomische
Mechanismen, in denen Bieter die M¨oglichkeit haben, Gebote auf untrennbare
Guterb¨ undel¨ inmehrerenRundeniterativabzugeben. NachjederRundeerhal-
ten die Bieter vom Auktionator Informationen zu aktuellen Preisen und/oder
der aktuellen Zwischenallokation. In der Literatur wurden mehrere Auk-
tionsverfahren vorgeschlagen, aber ihr Verhalten unter unterschiedlichen Rah-
menbedingungen wurde zu wenig untersucht. Wegen ihrer diskreter Struk-
tur und komplexer Bietregeln, wird die spieltheoretische Analyse von ICAs
iiiiv
wesentlich erschwert. In der Literatur findet man lediglich Equilibrium-
AnalysenvonICAsmitnichtlinearenpersonalisiertenPreisenuntersehrstren-
gen Annahmen ub¨ er die verfolgten Bietstrategien. Im Gegenteil, ICAs mit
linearen anonymen Preisen wurden erfolgreich in Feldstudien und im Labor
eingesetzt.
Rechensimulationen und Laborexperimente k¨onnen bei der Analyse und Ver-
gleich von Auktionsformaten und bei der Untersuchung der Auswirkungen
von unterschiedlichen Konfigurationsparametern eine große Hilfe leisten. In
unseren Forschungsprojekten wollten wir diverse existierende Auktionsmech-
anismen vergleichen und neue, verbesserte, Auktionsregeln entwickeln. Dabei
haben wir uns auf Auktionen mit linearen anonymen Preisen konzentriert,
aber auch ein Auktionsformat mit nicht-linearen personalisierten Preisen un-
tersucht.
In den Rechensimulationen haben wir drei ausgew¨ahlte ICA Formate mit lin-
earen anonymen Preisen und die VCG-Auktion verglichen, indem die alloka-
tive Effizienz, die Gewinnverteilung und die Konvergenzgeschwindigkeit unter
Annahmen von unterschiedlichen Wertemodellen und Bietstrategien gemessen
wurden. Dabei haben die untersuchten ICAs mit linearen Preisen bei unter-
schiedlichenWertemodellenundsogarmithohenSynergienzwischeneinzelnen
Gutern¨ sehr gute Ergebnisse geliefert. Wir haben allerdings signifikante Un-
terschiede in der Effizienz und Gewinnverteilung zwischen den einzelnen Auk-
tionsformatenfestgestellt. AuchbeiheuristischenBietstrategien,beidenendie
Bietagentenuraufeinezuf¨alligausgew¨ahlteUntermengedermomentanbesten
Bunde¨ lGeboteabgeben,habenwirhoheEffizienzgradebeobachtet. Wirhaben
auch mehrere neue Preisberechnungs-, Aktivit¨ats- und Abschlussregeln en-
twickelt, mit denen die Auktionsergebnisse deutlich verbessert werden kon-
nten.
In den Laborexperimenten haben wir dieselben Auktionsformate und ein ICA
mit nicht-linearen personalisierten Preisen im Bezug auf dieselben Kriterienv
verglichen. Wir haben viele a¨hnliche Ph¨anomena wie bei unseren Simula-
tionsergebnissen identifiziert, aber auch ein sehr heterogenes Bietverhalten
beobachtet, wobei bei keinem der Auktionsformate eine Analogie zur “my-
opic best-response” Strategie ersichtlich war. Nichtsdestotrotz haben wir bei
allen Auktionsformaten hohe Effizienzgrade erzielt. Außerdem haben wir sig-
nifikante Unterschiede in der Gewinnverteilung beobachtet, die vom Auktions-
format, aber nicht von der Guterzahl¨ (3, 9 und 9) beeinflusst wurden. Beim
untersuchten ICA mit nicht-linearen personalisierten Preisen war die Konver-
genzgeschwindigkeit sehr niedrig, was dieses Auktionsformat (zumindest in
der aktuellen Form ohne Proxy-Agenten) fur¨ praktische Anwendungen kaum
brauchbar macht.vi