Titolo della tesi: Some Algorithmic Problems for the Web Economy
This thesis investigates algorithmic problems arising in the context of the Web economy, focusing on two central themes: learning Random Utility Models (RUMs) and Online Bipartite Matching. Both problems are motivated by modern digital platforms—RUMs model user choice behavior in online platforms, while Online Bipartite Matching captures core challenges in online advertising allocation.
The first part of the thesis considers platforms that host vast catalogs of items but interact with users only through small subsets of options (``slates''). This setting reflects practical constraints faced by real-world systems, such as the ten blue links of web search or a movie shelf on Prime Video or Netflix. Modeling user behavior through Random Utility Models—the gold standard in Economics for discrete choice problems—we establish sharp bounds on the slate size required to predict user preferences across all possible subsets of items. We present improved algorithms and strong impossibility results for this problem. These impossibility results, which are further supported by empirical assessments on real-world datasets of moderate size, reveal a significant gap in the ability of current recommendation platforms to infer global preferences from limited interactions.
The second part addresses Online Bipartite Matching, a fundamental abstraction for online ad allocation. We derive a new impossibility bound showing that no online algorithm can achieve a competitive ratio better than 1-e^{1-e}≈0.8206. Our result, based on a simple and analytically tractable construction, currently stands as the best-known upper bound for many variants of stochastic online bipartite matching, including the famous randomly-permuted-adversarial-graph variant, improving the long-standing 0.823 bound of Manshadi, Oveis Gharan, and Saberi (SODA 2011) after 14 years.
Overall, this thesis advances the state of the art on two fundamental problems at the intersection of algorithms and economics, highlighting both the algorithmic possibilities and the intrinsic limitations of large-scale online systems.