Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
On the Hardness of Truthful Online Auctions with Multidimensional Constraints

Speaker: Rica Gonen


This paper assess the prospect of creating truthful mechanisms for sponsored
search auctions where advertisers have budget and time constraints. While the
existing impossibility in this area by \cite{BCIMS05} addresses the situation
where advertisers have budget limitations and static prices but not time
limitations; our result applies to the common setting in practice where
advertisers have time and budget limitations, prices are dynamic and
advertisers act strategically on their time limitation as well as their budget.

We show that in cases where advertisers' arrival and departure times are
private information,
no truthful deterministic mechanism for budgeted sponsored search with time
constrained advertisers can perform well
with respect to social welfare maximization. Essentially, to protect itself
from advertisers' time
manipulation a truthful mechanism must give up significant social welfare.

It is also shown that even in cases where advertisers' arrival and
times are known to the mechanism, the existence of advertiser budgets is itself
a problem.  In this case a budgeted sponsored search mechanism with time
constrained advertisers can not achieve non-trivial welfare approximation when
using a local pricing scheme (a player pricing history is not taken into
account). Also, it is shown that for a dynamic global pricing scheme no such
truthful mechanism exists.

websites: Arnold Beckmann 2008-06-18