Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Bayesian Optimization for Best Response Computation in Combinatorial Auctions
Organization Unit
Authors
  • Marius Högger
Supervisors
  • Vitor Bosshard
  • Sven Seuken
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2018
Abstract Text The Bayes-Nash equilibrium (BNE) solution to combinatorial auctions (CAs) bears much information helping to understand allocation problems since it represents a stable situation where non of the bidders included would want to deviate. This thesis explores the possibility of using Bayesian optimization (BO) to reduce the number of expected utility evaluations when searching for the pointwise best response which is used for finding the BNE. This research is based on the algorithm presented in [Bosshard et al., 2017]. Comparing BO with pattern search (PS) on the univariate LLG-domain, the reduction of the costly evaluations is estimated and the influence of the variance of the Monte Carlo (MC) integration used for the calculation of the expected utility, is examined. Finally, the quality of the results when BO is used, is verified by comparing them against the known analytical results. Confirming that when using BO, equilibria of similar quality can be found with fewer evaluations, this thesis still highlights certain reservations concerning the effectiveness of BO for finding best responses in the LLG domain.
Zusammenfassung Um Zuordnungsprobleme besser zu verstehen, kann das Bayes-Nash Equilibrium (BNE) von kombinatorischen Auktionen untersucht werden da dieses eine stabile Situation wiedergibt in welcher sich keiner der beteiligten Bietern umentscheiden würde. Diese Arbeit untersucht inwiefern sich die Bayes'sche Optimierung (BO) eignet um die Anzahl Auswertungen der erwarteten Nutzenfunktion zu reduzieren. Diese Auswertungen werden verwendet um das BNE zu finden. Die Forschung in dieser Arbeit basiert auf dem von [Bosshard et al., 2017] präsentierten Algorithmus. Es wird erforschen inwiefern BO die Anzahl Auswertungen reduzieren kann und in welcher Hinsicht die Varianz der Monte Carlo (MO) Integration, welche zur Bestimmung des erwarteten Nutzens verwendet wird, einen Einfluss auf die Bestimmung des Maximums der Nutzenfunktion hat. Dabei wird BO mit dem "pattern search" (PS) Algorithmus auf dem eindimensionalen LLG-Bereich verglichen. Abschliessend ¸berprüfen wir die Qualität des mittels BO gefundenen Resultates, indem wir dieses mit der bekannten analytischen Lösung vergleichen. Diese Arbeit bestätigt, dass durch die Verwendung von BO die Anzahl Auswertungen reduziert werden kann, ohne dass, die Qualität der Lösung zu sehr zu beeinträchtigen wird. Dennoch erhebt diese Arbeit einige Zweifel gegenüber der Effektivität von BO im LLG-Bereich.
PDF File Download
Export BibTeX