Game-Theoretic Design for Assignment and Ranking in Online Advertising and Human Computation

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Game-Theoretic Design for Assignment and Ranking in Online 
Advertising and Human Computation"

By

Mr. Georgios TRIMPONIAS


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 (one for each context). We subsequently 
address each of the disjoint problems using well-studied mechanisms, such 
as the truthful and socially optimal VCG auction or the industrially 
popular GSP procedure. 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. To compute it, we introduce three methods that 
correspond to different families of 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 
discuss how human computation games have the weak-link property, i.e., the 
game outcome is determined by low-skill players. To perform ranking, we 
develop three classes of scoring/rating algorithms. The first class is an 
ELO-based scheme, where players get rewarded if they perform better than 
expected, or punished in the opposite case. The second class introduces a 
Bayesian skill rating system; player ratings can then be computed by 
performing approximate inference. The third class utilizes results from 
item response theory, a family of latent trait models that are used to 
establish psychometric properties of items. Extensive experiments confirm 
the effectiveness of the proposed methods in both problems.


Date:			Thursday, 26 February 2015

Time:			2:00pm - 4:00pm

Venue:			Room 3494
 			Lifts 25/26

Chairman:		Prof. Robert Qi (LIFS)

Committee Members:	Prof. Qiang Yang (Supervisor)
 			Prof. Dimitris Papadias
 			Prof. Dit-Yan Yeung
 			Prof. Yang Wang (MATH)
 			Prof. Jianwei Huang (Inf. Eng., CUHK)


**** ALL are Welcome ****