Game-theoretic design for assignment and ranking in online advertising and human computation

Abstract

This thesis uses elements and tools from the theory of games to study two fundamental problems, the assignment problem and the ranking problem. We explore the former problem in sponsored search advertising, and the latter in human computation. In sponsored search, we study the assignment problem for context-based advertising, where advertisers have different valuations for different disjoint contexts. When no budget constraints exist, we show how the corresponding assignment problem can be decomposed into a set of disjoint assignment problems. We subsequently address each of the disjoint problems using well-studied mechanisms. Furthermore, we explore combinatorial auctions as a way to guarantee the search engine revenue. When budget constraints are present, we distinguish between two cases: advertisers may be indifferent to the price per click, or they may not be willing to pay more than their valuation. For the first case, we introduce a probabilistic framework from resource allocation markets. Under reasonable conditions, a Nash equilibrium always exists, and we can compute it by using distributed dynamics. In the second case, we cannot show that a Nash equilibrium always exists, but we manage to bound a player's most profitable deviation using concave relaxations of the utilities. In human computation, we address ranking in human computation games. We first argue how human computation games have the weak-link property, i.e., the game outcome is determined by low-skill players. We then introduce a Bayesian rating model that incorporates the weak-link property and the task difficulties. To infer the ratings, we develop two methods. The first is an ELO-based scheme, where players get rewarded if they perform better than expected, or punished in the opposite case. The second performs approximate Bayesian inference using the moment-matching technique. Finally, we show how it is possible to rate and rank the players using item response theory and the expectation-maximization algorithm. Extensive experiments confirm the effectiveness of the proposed methods in both problems.

Date of Award	2015
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology