Dear Colleagues,

We are pleased to invite you to the following SPASS seminar (jointly organised by UniPi, SNS, UniFi and UniSi):

Speaker: Alessandro Panconesi (Sapienza Università di Roma)

Title: Probabilistic Algorithms and Methods for the Web Economy

Date and time: Wed, April 29th at 14:00 CET

Place: Aula Mancini, Palazzo della Carovana, Scuola Normale Superiore, Pisa

Join online: https://meet.google.com/cuf-mjvp-ynv

On behalf of the organisers,
Alessandra Caraceni

*********************

Abstract:

The web economy offers a wealth of challenging problems for algorithmic research, many of which require fundamentally probabilistic techniques.
In this talk, I will briefly discuss two examples from our work. First, I will consider the classic online matching problem, a central primitive in online advertising. We prove a new impossibility result: no online algorithm can achieve a competitive ratio better than 1-e^{1-e}. Second, I will turn to problems arising in discrete choice, a framework widely used in economics. In particular, within random utility models (RUMs) – introduced by Nobel laureate Daniel McFadden – we establish a striking impossibility result about the learnability of user preferences. This result shows that even with massive data and computational power, web platforms face fundamental limits in inferring user behaviour.
This is joint work with Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Erasmo Tani, Andrew Tomkins and Andrea Vattani.