{'fraction_non_alphanumeric': 0.04802631578947368, 'fraction_numerical': 0.021052631578947368, 'mean_word_length': 4.244827586206896, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Improved Equilibrium Enumeration for Bimatrix Games

The enumeration of all equilibria of a bimatrix game is a classical algorithmic problem in game theory. As shown by Vorob’ev (1958), Kuhn (1961), and Mangasarian (1964), all equilibria can be represented as convex combinations of the vertices of certain polyhedra defined by the payoff matrices. Simplified by a projective transformation that eliminates the payoff variable, these polyhedra have the form P1 = {x ∈ IR | x ≥ 0M , B>x ≤ 1N}, P2 = { y ∈ IR | Ay ≤ 1M , y ≥ 0N} . The players’ payoff matrices are A and B . These are w.l.o.g. positive, so that P1 and P2 are bounded and therefore polytopes. The disjoint sets M and N contain the row and column indices, respectively, which represent the pure strategies of the two players. The vectors 0 and 1 have all components equal to zero and one, respectively. The elements x in P1−{0M} and y in P2−{0N} represent the mixed strategies of the two players after normalization so that their components sum up to one. After this normalization, the right hand sides in B>x ≤ 1N and Ay ≤ 1M denote the expected payoff to the other player. If any of these inequalities is binding (holds as equality), the pure strategy corresponding to that inequality is optimal. In equilibrium, any pure strategy must be optimal or have probability zero. Hence, any Nash equilibrium of (A,B) corresponds to a complementary pair (x, y) in P1 × P2 where any inequality in M ∪N in the above definition of P1 and P2 is binding for x or for y.