Reviews: Multiagent Evaluation under Incomplete Information

This paper investigates the evaluation of multiagent strategies in the incomplete information and general-sum setting. The primary algorithm to be analyzed is alpha-rank, which is a ranking algorithm based on the stationary distribution of a markov chain with states defined over all strategy profiles. Since payoff tables M are typically estimated empirically, the authors provide sample complexity bounds on the number of (uniformly distributed) observations of each strategy profile to be observed for the resultant stationary distribution to be close to the true stationary distribution. The authors propose an adaptive sampling strategy based on confidence intervals over each pair of strategy profiles and analyze its sample complexity. The paper also shows how to propagate uncertainties in M to uncertainty in the ranking weights that alpha-rank yield.