Convergence to a Convention in Adaptive Learning in an Unperturbed 2x2 Coordination Game: A Relaxation of the Bounds of s
Young 1993\(^1\), established that in 2x2 coordination games a convention can be reached under unperturbed adaptive learning dynamics given that the sample size (s) was sufficiently small compared to the memory size (m). The limit of this bound was \(s \leq m / (L\_r+2)\) where \(L\_r\) is the maximum of the set of lengths of the shortest directed path in the best reply graph from any initial vertex to a strict Nash equilibrium. The bounds of this limit was expanded in Young 2020 \(^2\) to simply requiring \(s/m \leq 1/2\). In both cases, Young did not claim that the bound on \(s/m\) was the best possible.Here, I prove that any degree of incompleteness, \(s < m\) is a sufficient amount of incompleteness for conventions arise in the unperturbed proccess.
The sampling algorithm that makes the proof work is essentially the following:
1. Both players sample the most recent \(s\) records available.
2. If players have different best responses, continue to sample the most recent \(s\) records until atleast one player's best response changes.
3. If at any point both players have the same best response when sampling the most recent \(s\) records then if they continue to sample the most recent \(s\) records for \(m\) periods a convention will be reached and locked into.
4. If instead, there is a period where both players best responses flip simultaneously call this period \(t\).
5. For one player, have them sample the most recent \(s\) records from period \(t+1\) through period \(t+m\).
6. For the other player, have them sample the most recent \(s+1\) records excluding the record created in period \(t\) from period \(t+1\) through period \(t+m\).
The above algorithm works as long as \(s < m\). For an interactive and visual representation of the dynamics in action, please input any variables you like and use the application below. The full, rigorous proof is available to read or download just below the application.