Regret estimation for multi slot incentive compatible multi armed bandit
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
School of Science |
Master's thesis
Checking the digitized thesis and permission for publishing
Instructions for the author
Instructions for the author
Authors
Date
2011
Department
Major/Subject
Informaatiotekniikka
Mcode
T-61
Degree programme
Language
en
Pages
vi + 66
Series
Abstract
Nowadays it is important to be able to solve problems which involve multiple agents. In particular in this thesis we will focus on the problem of allocating advertisements on a search engine page. It is not trivial as a revenue optimization problem because it involves issues about the truthfulness of the agent's declarations and the chance that we do not have all the information about them. Natural solution to some of the problems we have in the allocation can be found in mechanism design on one hand and in multi armed bandit model on the other hand. In the machine design approach there is the intention to avoid situations where telling a lie is rewarded, but it does not have techniques which deals with truly unknown parameters. With multi armed bandit the estimation of some information is taken into account, but without any study about the truthfulness. Even the most advanced model could not handle solving a real advertisement auction unless it makes strong assumption. The purpose of this thesis is to provide a model that solves the problem of online advertisements allocation in a real life setting, using tools and concepts from both the aforementioned models. Starting from a simple auction, the study will be successively expanded in a way that will make it possible to solve a general case. Customized algorithms will be designed and theoretical bounds derived, in order to properly find a solution to the advertisement auction problem. After a theoretical analysis of the proposed solutions, a validation of the model will be provided, using simulated auctions.Description
Supervisor
Oja, ErkkiThesis advisor
Lazaric, AlessandroGatti, Nicola
Keywords
mechanism design, multi armed bandit, multi slot adverisement auction, auction with externalities, context dependent auction