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