Alex Scott

Tom Johnston, Michael Savery, Alex Scott et al.

We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that, among games that are `generic' (without indifferences) and that have a pure Nash equilibrium, all but a small fraction are \emph{connected}, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in all but a small fraction of generic games that have one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in \emph{every} generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity.

Tom Johnston, Michael Savery, Alex Scott et al.

We study the typical structure of games in terms of their connectivity properties. A game is `connected' if it has a pure Nash equilibrium and there is a best-response path from every action profile which is not a pure Nash equilibrium to every pure Nash equilibrium; a game is generic if it has no indifferences. In previous work we showed that, among all $n$-player $k$-action generic games that admit a pure Nash equilibrium, the fraction that are connected tends to $1$ as $n$ gets sufficiently large relative to $k$. Here, we consider the large-$k$ regime, which behaves differently: we show that the connected fraction tends to $1-ζ_n$ as $k$ gets large, where $ζ_n>0$ is an explicit constant. Thus, a constant fraction of many-action games are \emph{not} connected. However, for $n\geq3$, $ζ_n$ is small and tends to $0$ rapidly with $n$, so as $n$ increases all but a vanishingly small fraction of many-player-many-action games are connected. Since connectedness is conducive to equilibrium convergence, we find a simple adaptive dynamic that is guaranteed to converge to a pure Nash equilibrium in all but a vanishingly small fraction of generic games that have one. We rely on new probabilistic and combinatorial arguments to tackle the large-$k$ regime.

Adrian Dumitrescu, János Pach, Morteza Saghafian et al.

Given a set $A$ of $n$ points (vertices) in general position in the plane, the \emph{complete geometric graph} $K_n[A]$ consists of all $\binom{n}{2}$ segments (edges) between the elements of $A$. It is known that the edge set of every complete geometric graph on $n$ vertices can be partitioned into $O(n^{3/2})$ crossing-free paths (or matchings). We strengthen this result under various additional assumptions on the point set. In particular, we prove that for a set $A$ of $n$ \emph{randomly} selected points, uniformly distributed in $[0,1]^2$, with probability tending to $1$ as $n\rightarrow\infty$, the edge set of $K_n[A]$ can be covered by $O(n\log n)$ crossing-free paths and by $O(n\sqrt{\log n})$ crossing-free matchings. On the other hand, we construct $n$-element point sets such that covering the edge set of $K_n[A]$ requires a quadratic number of monotone paths.

Quentin Lutz, Élie de Panafieu, Alex Scott et al.

Gathering training data is a key step of any supervised learning task, and it is both critical and expensive. Critical, because the quantity and quality of the training data has a high impact on the performance of the learned function. Expensive, because most practical cases rely on humans-in-the-loop to label the data. The process of determining the correct labels is much more expensive than comparing two items to see whether they belong to the same class. Thus motivated, we propose a setting for training data gathering where the human experts perform the comparatively cheap task of answering pairwise queries, and the computer groups the items into classes (which can be labeled cheaply at the very end of the process). Given the items, we consider two random models for the classes: one where the set partition they form is drawn uniformly, the other one where each item chooses its class independently following a fixed distribution. In the first model, we characterize the algorithms that minimize the average number of queries required to cluster the items and analyze their complexity. In the second model, we analyze a specific algorithm family, propose as a conjecture that they reach the minimum average number of queries and compare their performance to a random approach. We also propose solutions to handle errors or inconsistencies in the experts' answers.