αα-Rank: Practically Scaling α-Rank through Stochastic Optimisation

Recently, α-Rank, a graph-based algorithm, has been proposed as a solution to ranking joint policy pro les in large scale multi-agent systems. α-Rank claimed tractability through a polynomial time implementation with respect to the total number of pure strategy pro les. Here, we note that inputs to the algorithm were not clearly speci ed in the original presentation; as such, we deem complexity claims as not grounded, and conjecture solving α-Rank is NP-hard. The authors of α-Rank suggested that the input to α-Rank can be an exponentially-sized payo matrix; a claim promised to be claried later. Even though α-Rank exhibits a polynomial-time solution with respect to such an input, we further re ect additional critical problems. We demonstrate that due to the need of constructing an exponentially large Markov chain, α-Rank is infeasible beyond a small nite number of agents. We ground these claims by adopting amount of dollars spent as a non-refutable evaluation metric. Realising such scalability issue, we present a stochastic implementation of α-Rank with a double oracle mechanism allowing for reductions in joint strategy spaces. Our method, α α-Rank, does not need to save exponentially-large transition matrix, and can terminate early under required precision. Although theoretically our method exhibits similar worst-case complexity guarantees compared to α-Rank, it allows us, for the rst time, to practically conduct large-scale multiagent evaluations. On 10 4 × 10 4 random matrices, we achieve 1000x speed reduction. Furthermore, we also show successful results on large joint strategy pro les with a maximum size in the order of O(2 25) (≈ 33 million joint strategies)-a setting not evaluable using α-Rank with reasonable computational budget.