Regret estimation for multi slot incentive compatible multi armed bandit

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.