Game-Theoretic Sponsored Search and Human Computation

PhD Thesis Proposal Defence


Title: "Game-Theoretic Sponsored Search and Human Computation"

by

Mr. Georgios TRIMPONIAS


Abstract:

This thesis applies concepts and tools from game theory in two areas with 
immense industrial potential, sponsored search and human computation. In 
sponsored search, we investigate contextualized advertising, where 
advertisers have different valuations for different disjoint contexts and 
the number of queries per context is known in advance. When no budget 
constraints exist, we properly adapt the GSP auction, and explore 
combinatorial auctions. 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 utilize a novel probabilistic framework that is 
inspired by resource allocation markets. Under reasonable conditions, a 
Nash equilibrium always exists; to compute it, we introduce three methods 
based on 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 two fundamental problems in human computation 
games. The first concerns methods for ranking players according to their 
skill. We discuss how human computation games are weak-link games, where 
low-skill players have a disproportionately greater impact on the game 
outcome. We then develop three ELO-based techniques that consider the 
weak-link structure as well as the task difficulty. Moreover, we introduce 
a Bayesian skill rating system, and show how to perform approximate 
inference using Expectation Propagation and a proportional heuristic for 
updating the posterior marginals. The second problem regards the mechanism 
design for generalizations of the ESP game. We apply Bayesian game theory 
to model and analyze how players behave in equilibrium. Our analysis 
explains how rational and strategic players may resort to adversarial 
actions to increase their score. To tackle this, we introduce an improved 
proportional mechanism.


Date:			Friday, 14 November 2014

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                         lifts 25/26

Committee Members:	Prof. Qiang Yang (Supervisor)
 			Prof. Dimitris Papadias (Chairperson)
 			Prof. Dit-Yan Yeung
 			Prof. Yang Wang (MATH)


**** ALL are Welcome ****