More about HKUST
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 ****