This paper presents a parallel randomized algorithm which computes a pair of •-optimal strategies for a given (m,n)-matrix game A=[aij]∈[¸-1,1] in O(•’-2log2(n+m)) expected time on an (n+m)/log(n+m)-processor EREW PRAM. For any fixed accuracy •∈0, the expected sequential running time of the suggested algorithm is O((n+m)log(n+m)), which is sublinear in mn, the number of input elements of A. On the other hand, simple arguments are given to show that for •∈1/2, any deterministic algorithm for computing a pair of •-optimal strategies of an (m,n)-matrix game A with ¸∈1 elements examines ¦[(mn) of its elements. In particular, for m=n the randomized algorithm achieves an almost quadratic expected speedup relative to any deterministic method.
