[Todos] Seminario de Optimización y Grafos este jueves

[Flavia Bonomo]

Invitamos a todos al Seminario de Optimización y Grafos, edición 2008, del
grupo de investigación en Teoría de Grafos y Optimización Combinatoria
(http://www.dc.uba.ar/inv/grupos/grafos)
de los departamentos de Computación y Matemática de la FCEN, UBA y el
Instituto de Ciencias de la UNGS.

El seminario es los jueves de 19 a 20.30, y el cronograma preliminar
puede verse en http://www.dc.uba.ar/inv/grupos/grafos/seminario

Los invitamos este jueves 13 de noviembre a las 19hs en el Laboratorio 3
(planta baja, pab I).

--------
"Subastas estocásticas y determinísticas "veraces" para la búsqueda
patrocinada" (Truthful stochastic and deterministic auctions for sponsored
search)

Esteban Feuerstein (DC, FCEN, UBA)



Resumen:

Incentive compatibility is a central concept in auction theory, and a
desirable property of auction mechanisms. In a celebrated result,
Aggarwal, Goel and Motwani presented the first truthful deterministic
auction for sponsored search (i.e., in a setting where multiple distinct
slots are auctioned).
Stochastic auctions present several advantages over deterministic ones, as
they are less prone to strategic bidding, and increase the diversity of
the winning bidders. Meek, Chickering and Wilson presented a family of
truthful stochastic auctions for multiple identical items.
We present the first class of incentive compatible stochastic auctions for
the sponsored search setting. This class subsumes as special cases the
laddered auctions of and the stochastic auctions with the condex pricing
rule of Meek, Chickering and Wilson, consolidating these two seemingly
disconnected mechanisms in a single framework. Moreover, when the price
per click depends deterministically on the bids the auctions in this class
are unique. Accordingly, we give a precise characterization of all
truthful auctions for sponsored search, in terms of the expected price
that each bidder will pay per click.
We also introduce randomized algorithms and pricing rules to derive, given
an allocation mechanism for the single- or multiple-identical-slots
scenarios, a new mechanism for the multislot framework with distinct
slots. These extensions have direct practical applications.

La charla incluirá una introducción al tema para no iniciados, así que no
se requieren conocimientos previos.