Kolmogorov meets Turing 2017 - Roma Tre




Kolmogorov meets Turing IV

December 1st, 2017 - DMF Roma Tre


Titles and abstracts:



Chris Schwiegelshohn
PCA for k-means: Preserving Cost, Clusters, And Beyond

Abstract: Principal Component Analysis is a widely used tool for dimension reduction. Among its many applications is the use of PCA as preprocessing step for k-means clustering. In this talk, we will give an overview on the relationship between these two problems and further present recent results and developments.

Marco Scarsini
When is selfish routing bad? The price of anarchy in light and heavy traffic.

This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin-destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain bounded away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials), the price of anarchy does converge to 1 in both heavy and light traffic conditions, and irrespective of the network topology and the number of O/D pairs in the network. Joint work with Riccardo Colini-Baldeschi, Roberto Cominetti, Panayotis Mertikopoulos.

Francesco Pasquale
Rationality and Randomness.
Game theory provides a powerful framework to study strategic interactions among agents of a system. The assumption about the 'rationality' of the agents is at the heart of classical solution concepts like Nash equilibria. However, in several scenarios those solution concepts often fall short of expectations when used to make predictions; some branches of game theory are thus trying to relax the rationality assumption. The Logit dynamics is a model for strategic interactions, inspired by statistical mechanics, that uses 'randomness' to model the uncertainty about the rationality level of the agents. In the first part of the talk I will sum up our research program on the Logit dynamics for strategic games, in which we proposed to consider the unique stationary distribution of the induced ergodic Markov chain as the long-term solution concept for the game, we analyzed the mixing time of the chains for some classes of games, and we defined the concept of metastable probability distribution for Markov chains with exponential mixing time. The usefulness of reasoning about 'metastability' goes beyond the realm of game theory and Markov chains. In the second part of the talk, I will discuss a recent work where the analysis of the metastable phase of a simple dynamics allowed us to come up with an efficient fully-distributed algorithm for the community detection problem.

Alexandre Stauffer
Multi-particle diffusion limited aggregation.

We consider a random model for the growth of an aggregate on Z^d, motivated by processes from physics such as dielectric breakdown and electrodeposition. Start with an infinite collection of particles located at the vertices of the lattice, with at most one particle per vertex, and initially distributed according to the product Bernoulli measure with parameter $\mu\in(0,1)$. In addition, there is an aggregate, which initially consists of only one particle placed at the origin. Non-aggregated particles move as continuous time simple symmetric random walks obeying the exclusion rule, whereas aggregated particles do not move. The aggregate grows indefinitely by attaching particles to its surface whenever a particle attempts to jump onto it. In the talk I will survey the known results about this model, and talk about our result on the speed of growth of the aggregate. This is a joint work with Vladas Sidoravicius.


Back to main page



Organizers: Luca Becchetti, Pietro Caputo, Andrea Clementi, Stefano Leonardi, Marco Scarsini