Average testing and Pareto efficiency (Q694740)

The authors propose the average testing as a simple adaptive procedure for playing strategic games. According to this procedure, each player sticks to her current strategy if it yields a payoff that exceeds her average payoff by at least some fixed positive \(\varepsilon\). Otherwise the player chooses a strategy at random. The authors consider generic two-person games where both players play according to the average testing procedure on blocks of \(k\) periods. They obtain that for sufficiently large \(k\;\) \((k>k_0(\varepsilon))\) the pair of time average payoffs converges almost surely to the \(3\varepsilon\)-Pareto efficient boundary. The case when both players choose different block sizes \(k\) is also discussed. The authors show that a variant of the average testing procedure achieves a similar convergence result.