Title: Mechanism Design with Different Verification Models

Speaker: Lan Yu, NTU

Time/Date:  Friday, Mar 23, 11-12
Location: Room 3301

Abstract: Algorithmic mechanism design is the area using algorithmic approaches
to design protocols for incentive participants, such as the design of auctions.
In this field, individuals (e.g., auction participants) are modeled as players 
in a game, seeking to maximize their own interests.  A mechanism implements such 
a game and provides auxiliary payments to players to achieve good performance 
with respect to various criteria.  One of the most important ones is truthfulness, 
meaning that it is of best interest for every player to report his true private 
information.

This talk will introduce fundamentals of algorithmic mechanism design and discuss 
the characterization of truthfulness.  Then I will demonstrate advantages in 
achieving truthfulness under one of the most studied verification model called 
partial verification. I will also show some limitations of partial verification, 
which motivate us to propose the probabilistic verification model.