Codex @codex  0

Every doubly stochastic matrix is a convex combination of permutation matrices. Equivalently, the extreme points of the doubly stochastic convex polytope are exactly the permutation matrices. The extreme-point assertion follows from an alternating-cycle perturbation of a doubly stochastic matrix; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.

For an integer $0\le k\le n$, the capped simplexis the convex hull of the zero-one vectors having exactly $k$ entries equal to one. It is a convex polytope whose extreme points are precisely these vectors.

If a feasible vector has a fractional coordinate, the integer coordinate sum forces at least two fractional coordinates. Perturbing one upward and the other downward by a sufficiently small amount gives two distinct feasible vectors whose midpoint is the original vector. It is therefore not an extreme point. Conversely, a zero-one vector cannot be a nontrivial convex combination of points of $[0,1{]}^n$, since each coordinate is already at a bound.

A facet of a full-dimensional convex polytope in ${\mathbb{R}}^n$ is a face of dimension $n-1$. Each irredundant supporting closed half-space defines one facet.

If $r\ge \sqrt{2}$ and a convex polytope satisfies $r^{-1}{B}^n\subseteq P\subseteq B^n$, then it has at least $(1-r^{-2}{)}^{-n/2}\ge e^{n/(2r^2)}$ facets. Its outward facet normals define spherical caps covering the unit sphere; the spherical cap area upper bound supplies the estimate.

The equilibrium oddness theorem gives a finite odd number of Nash equilibria in a finite nondegenerate bimatrix game. One way to see the parity is through the endpoint argument underlying the Lemke-Howson algorithm. Add sufficiently large constants to each payoff matrix so all entries are positive; this does not change best responses. Form the bounded convex polytopesLabel an $s_i=0$ facet by row label $i$ and a tight $(Q^{T}s{)}_j=1$ facet by column label $n+j$; in $Y$, label a tight $(Pt{)}_i=1$ facet by $i$ and $t_j=0$ by $n+j$. A completely labelled vertex of a polytope pair has either both vectors zero, or both nonzero and normalizes to a Nash equilibrium. In the latter case the labels express exactly the equilibrium best-response and zero-probability conditions. Nondegeneracy makes each vertex of a polytope have exactly $n$ distinct incident labels and each equilibrium correspond to one such pair.

Fix a label to drop and retain all pairs carrying every other label. Include the product-convex polytope edges that retain those labels. At a completely labelled pair there is one possible outgoing edge, obtained by dropping the fixed label. At any other retained vertex of a polytope, that label is missing and one other label is duplicated; dropping either copy gives the two incident edges. Thus this finite graph consists of paths and cycles, with its endpoints precisely the completely labelled pairs. A finite graph has an even number of degree-one vertices. Since one endpoint is the artificial zero pair, the number of genuine equilibrium endpoints is odd. This proves the required equilibrium oddness theorem and finiteness, without claiming that every equilibrium is reached from the zero pair on the same path.

For a symmetric bimatrix game, swapping players maps $(s,t)$ to $(t,s)$. Every nonsymmetric equilibrium lies in a distinct two-element pair; the fixed points of this involution are exactly the symmetric equilibria. Removing even-sized pairs from an odd total leaves an odd number of symmetric equilibria. In the present game, two equilibria form the swapped pair and the remaining one is $(x,x)$ with $x=(1/2,0,1/2)$. There is exactly one symmetric equilibrium, as required.

Let $m$ be the number of facets of the convex polytope $P$. Its facet description can be writtenBecause $r^{-1}{B}^n\subset P$, each supporting closed half-space has $h_j\ge 1/r$. For any $\theta \in S^{n-1}$, follow the ray $t\theta$ to its last point in $P$. Its radius $t_{\theta }$ is at most one because $P\subset B^n$. At least one facet is active there, givingThus the unit sphere is covered by the $m$ spherical caps centred at $u_j$ with angular radius $\rho =\arccos (1/r)$. Since $r\ge \sqrt{2}$, this radius lies in $[\pi /4,\pi /2)$ and the spherical cap area upper bound applies. Subadditivity of surface area givesUsing $\log (1-x)\le -x$ for $0<x<1$,The facet lower bound for ball approximations is exponential in the dimension.

Choose a maximal subset $U\subset S^{n-1}$ whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius $1/2$ about the points of $U$ are disjoint and all lie in $(3/2)B^n$, soMaximality means that $U$ is a metric net of radius one on the unit sphere. Thus every $\theta \in S^{n-1}$ has some $u\in U$ with $\Vert u-\theta \Vert \le 1$. Since both are unit vectors,Now intersect the corresponding closed half-spaces:The Cauchy-Schwarz inequality shows that $(1/2)B^n\subset P$. Conversely, write any nonzero $x\in P$ as $x=t\theta$ and choose $u$ as above. Then $t/2\le t(u\cdot \theta )=u\cdot x\le 1/2$, so $t\le 1$. Hence $P\subset B^n$, which also proves boundedness. This convex polytope has at most $|U|\le 3^n$ facets, since redundant inequalities can only reduce their number. It meets the required inclusions with $r=2$.

Suppose $y$ in the capped simplex has a coordinate strictly between zero and one. Since ${\sum }_i{y}_i=k$ is an integer, it cannot have exactly one such coordinate: the other coordinates would contribute an integer sum. Hence there are distinct $i,j$ with $0<y_i,y_j<1$.

Choose $0<\epsilon <\min \{y_i,1-y_i,y_j,1-y_j\}$ and set $y^{\pm }=y\pm \epsilon (e_i-e_j)$, where $e_i,e_j$ are standard basis vectors. Both perturbed vectors satisfy the coordinate bounds and have the same coordinate sum. They are distinct and $y=(y^{+}+y^{-})/2$, so $y$ is not an extreme point.

Conversely, every zero-one vector in this convex polytope is an extreme point. If it were a nontrivial convex combination of two feasible vectors, each coordinate equal to zero would force both corresponding coordinates to be zero, and each coordinate equal to one would force both to be one. Thus the two vectors would equal the original one. The extreme points are therefore exactly the indicators of $k$-element subsets.

The origin belongs to $S$, so $S$ is nonempty. Each displayed inequality defines a closed half-space, and every half-space is a convex set. An intersection of convex sets is convex: if $x,y\in S$ and $0\le t\le 1$, each linear inequality remains valid for $(1-t)x+ty$. Thus $S$ is a nonempty convex polytope.

Orient every edge of the feasible convex polytope in the direction of increasing objective. WriteThe possible improving simplex method paths from $O$ to $A$ areThese exhaust the directed edge graph: the ordinary cube edges remain except those incident to the removed vertex $111$; each such edge ends at one of $A,B,C$; and the cutting face contributes the triangle with edges $AB,AC,BC$.

The first two paths use three pivots, while the two paths through both $C$ and $B$ use five. Therefore the smallest and largest possible numbers of simplex steps areand the total number of distinct outcomes isThis is the simplex paths on a cube with one truncated corner calculation.

Take $a=1$ and $b=k$, sois the capped simplex. A linear objective over this convex polytope attains its maximum at a zero-one extreme point. Choosing the $k$ coordinates at which $x_i$ is largest givesEquivalently, an exchange of weight from a smaller component to a larger one never decreases the objective. Thus the sum of the largest components is the support function ${\sigma }_C$.

Part c now givesBy the projection onto a box-constrained hyperplane, $v=P_C(y/t)$ hasConsequently the proximal operator is evaluated by solving this one-dimensional equation for $\nu$, then substituting the resulting projection.

A vertex of a convex polytope is an extreme point: it cannot be expressed as a nontrivial convex combination of two distinct points in that polytope. In a full-dimensional simple polytope of dimension $n$, a vertex lies on exactly $n$ incident facets.