Game’s Degeneracy Running Proportional to Polytope’s Redundancy.

For a given set of vertices V ⊆ R^K a Polytope P can be defined as the following set of points:

P = {∑_i=1^|V|λ_iv_i ∈ R^K | ∑_i=1^|V|λ_i = 1; λ_i ≥ 0; v_i ∈ V}

Polytope is an intersection of boundaries that separate the space into two distinct areas. If a polytope is to be defined as an intersection of half spaces, then for a matrix M ∈ R^mxn, and a vector b ∈ R^m, polytope P is defined as a set of points

P = {x ∈ Rⁿ | M_x ≤ b}

Switching over to a two-player game, (A, B) ∈ R^mxn2_>0, the row/column best response polytope P/Q is defined by:

P = {x ∈ R^m | x ≥ 0; xB ≤ 1}

Q = {y ∈ Rⁿ | Ay ≤ 1; y ≥ 0}

The polytope P, corresponds to the set of points with an upper bound on the utility of those points when considered as row strategies against which the column player plays.

An affine combination of points z₁,….z_k in some Euclidean space is of the form ∑_i=1^kλ_iz_i, where λ₁, …, λ_k are reals with ∑_i=1^kλ_i= 1. It is called a convex combination, if λ_i ≥ 0 ∀ i. A set of points is convex if it is closed under forming convex combinations. Given points are affinely independent if none of these points are an affine combination of the others. A convex set has dimension d iff it has d + 1, but no more, affinely independent points.

A polyhedron P in R^d is a set {z ∈ R^d | C_z ≤ q} for some matrix C and vector q. It is called full-dimensional if it has dimension d. It is called a polytope if it is bounded. A face of P is a set {z ∈ P | c^⊤z = q₀} for some c ∈ R^d, q₀ ∈ R, such that the inequality c^⊤z ≤ q₀ holds for all z in P. A vertex of P is the unique element of a zero-dimensional face of P. An edge of P is a one-dimensional face of P. A facet of a d-dimensional polyhedron P is a face of dimension d − 1. It can be shown that any nonempty face F of P can be obtained by turning some of the inequalities defining P into equalities, which are then called binding inequalities. That is, F = {z ∈ P | c_iz = q_i, i ∈ I}, where c_iz ≤ q_i for i ∈ I are some of the rows in C_z ≤ q. A facet is characterized by a single binding inequality which is irredundant; i.e., the inequality cannot be omitted without changing the polyhedron. A d-dimensional polyhedron P is called simple if no point belongs to more than d facets of P, which is true if there are no special dependencies between the facet-defining inequalities. The “best response polyhedron” of a player is the set of that player’s mixed strategies together with the “upper envelope” of expected payoffs (and any larger payoffs) to the other player.

Nondegeneracy of a bimatrix game (A, B) can be stated in terms of the polytopes P and Q as no point in P has more than m labels, and no point in Q has more than n labels. (If x ∈ P and x has support of size k and L is the set of labels of x, then |L ∩ M| = m − k, so |L| > m implies x has more than k best responses in L ∩ N. Then P and Q are simple polytopes, because a point of P, say, that is on more than m facets would have more than m labels. Even if P and Q are simple polytopes, the game can be degenerate if the description of a polytope is redundant in the sense that some inequality can be omitted, but nevertheless is sometimes binding. This occurs if a player has a pure strategy that is weakly dominated by or payoff equivalent to some other mixed strategy. Non-simple polytopes or redundant inequalities of this kind do not occur for “generic” payoffs; this illustrates the assumption of nondegeneracy from a geometric viewpoint. (A strictly dominated strategy may occur generically, but it defines a redundant inequality that is never binding, so this does not lead to a degenerate game.) Because the game is nondegenerate, only vertices of P can have m labels, and only vertices of Q can have n labels. Otherwise, a point of P with m labels that is not a vertex would be on a higher dimensional face, and a vertex of that face, which is a vertex of P, would have additional labels. Consequently, only vertices of P and Q have to be inspected as possible equilibrium strategies. Algorithmically, if the input is a nondegenerate bimatrix game, and output is an Nash equilibria of the game, then the method employed for each vertex x of P − {0}, and each vertex y of Q − {0}, if (x, y) is completely labeled, the output then is the Nash equilibrium (x · 1/1^⊤x, y · 1/1^⊤y).

Advertisement