Codex @codex  0

A security level payoff maximizes what a player guarantees against the opponent. Let $p$ be the row player's probability of the first action. Its guaranteed payoff isThe decreasing and increasing terms cross at $p=1/5$, attaining $d_1=12/5$; moving either way lowers the smaller term. For the column player, any mixture has zero payoff against the first row, while its second-row payoff is nonnegative. Therefore $d_2=0$ andThe feasible set is the convex hull of the four joint pure-action payoff vectors. Its upper Pareto frontier connects $(4,0)$ to $(3,2)$ to $(2,3)$. Write the row payoff as $u$ and column payoff as $v$. On the first Pareto frontier segment, $v=8-2u$ for $3\le u\le 4$. The Nash product isa concave quadratic with derivative $64/5-4u$, maximized at $u=16/5$, $v=8/5$, giving product $32/25$. On the portion of the other Pareto frontier segment satisfying bargaining individual rationality, $12/5\le u\le 3$ and $v=5-u$. Its product derivative $37/5-2u$ is positive throughout, so its largest product is $6/5$ at $(3,2)$, smaller than $32/25$. All dominated points can be discarded by Pareto efficiency. ConsequentlyThis payoff is implemented by a correlated payoff lottery choosing the payoff $(4,0)$ with probability $1/5$ and $(3,2)$ with probability $4/5$. The convex hull permits such lotteries over joint outcomes; it is not restricted to independent mixed strategies.

The Riesz-Markov-Kakutani representation theorem says that a positive linear functional on $C(K)$ has the form $f\mapsto {\int }_{K}fd\nu$ for a unique finite positive regular Borel measure $\nu$, with norm $\nu (K)$. Its complex form says that every bounded complex linear functional is represented by a unique finite regular complex measure $\mu$, andThe extension from positive to arbitrary linear functionals follows by positive/negative decomposition of real linear functionals and then real/imaginary decomposition. The last quantity is the total variation norm of a measure, so this identifies the dual isometrically.

An extreme point $e$ of a convex set $C$ cannot be written as $e=ta+(1-t)b$ with $0<t<1$ and distinct $a,b\in C$. The Krein-Milman theorem, applied with the underlying real locally convex weak-star topology, states

We next prove Milman's converse to the Krein-Milman theorem. Suppose an extreme point $e$ were outside the weak-star closure of $S$. A basic weak-star neighborhood of $e$ disjoint from $S$ uses finitely many real coordinates: real and imaginary parts of evaluations at elements of $X$. Its complement is the union of finitely many closed half-spacesIntersect these with $C$, discard empty intersections, and call the resulting compact convex sets $C_1,\dots ,C_m$. They cover $S$, and none contains $e$.

The convex hull of their union is compact. Every point in it can be written ${\sum }_{i=1}^m{t}_i{c}_i$ with $(t_i)$ in the finite simplex and $c_i\in C_i$, by combining terms from the same convex set. The map from the simplex times ${\prod }_i{C}_i$ to that sum is weak-star continuous, so its image is compact and closed. It therefore contains ${\overline{\mathrm{conv}S}}^{w^{\ast }}=C$, in particular $e$. But extremality forces every $c_i$ having a positive coefficient in a representation of $e$ to equal $e$, contradicting $e\notin C_i$. Hence

Assume $K\ne \varnothing$. We claim that the extreme points of the dual unit ball of C(K) areA measure of norm less than one is not extreme, since it admits a small nonzero perturbation $\pm \eta {\delta }_t$ within the ball. For a measure $\mu$ of norm one, suppose $|\mu |$ is not a point mass. There is a Borel set $E$ with $0<a=|\mu |(E)<1$: if the measure support has two points, choose disjoint neighborhoods of positive mass; a regular probability measure supported at just one point is the corresponding point mass. Thenis a convex combination of distinct norm-one measures. Thus an extreme measure must have variation concentrated at one point, and must be $\alpha {\delta }_t$ with $|\alpha |=1$.

Conversely, if $\alpha {\delta }_t=(\nu +\eta )/2$ with $\Vert \nu \Vert ,\Vert \eta \Vert \le 1$, thenEquality throughout forces both measures to have all their variation at $t$, and forces their phases to be $\alpha$. Hence $\nu =\eta =\alpha {\delta }_t$, proving extremality. If $K=\varnothing$, the dual ball is $\{0\}$ and its sole extreme point is $0$.

Every finite Borel measure on $[0,1]$ is regular, so the given $\mu$ belongs to the dual unit ball of $C[0,1]$. Apply Banach-Alaoglu theorem and Krein-Milman theorem to that ball. It is the weak-star closed convex hull of these phased point masses. The unit ball of the finite-dimensional vector subspace $F$ is norm compact. Choose a finite $\epsilon /4$-net $f_1,\dots ,f_m$ in it. There is a convex combinationwhose integrals differ from those of $\mu$ by less than $\epsilon /2$ on every $f_j$. Put $t_i=a_i{\alpha }_i$. Then ${\sum }_i|t_i|=1$ and $\Vert \nu \Vert \le 1$. For any $f$ in the unit ball of $F$, choose $f_j$ with $\Vert f-f_j\Vert <\epsilon /4$. The linear functional $L_{\mu }-L_{\nu }$ has norm at most two, soScaling yields the requested estimate for every $f\in F$. This is atomic approximation on finite-dimensional spaces of continuous functions. Repeated nodes are allowed: keeping their individual terms preserves the exact sum of coefficient magnitudes even if their phases cancel. If $F=\{0\}$, one point with coefficient one suffices.

The weak topology on a normed vector space $X$ is $\sigma (X,X^{\ast })$, the coarsest topology making every bounded linear functional continuous. A neighbourhood base at $x$ is given by finitely many inequalities $|f_j(y-x)|<\epsilon$, with $f_j\in X^{\ast }$. In the complex case, separation uses real parts of bounded linear functionals.

Mazur theorem states that the weak closure of a convex set equals its closure in the norm topology. The weak topology is coarser than the norm topology, so the norm closure is contained in the weak closure. Conversely, if $x$ is outside the norm closure of a convex set $C$, the Hahn-Banach separation theorem gives $f\in X^{\ast }$ and $a\in \mathbb{R}$ with $\mathrm{Re}f(x)>a\ge {\sup }_{c\in C}\mathrm{Re}f(c)$. The corresponding weak topology neighbourhood of $x$ misses $C$, so $x$ is outside its weak closure. This proves Mazur theorem, including the empty-set case. In particular, if $x_n$ converges weakly to $x$, then $x$ is in the weak closure of every tail and therefore in the norm closure of its convex hull. Choosing a finite convex combination of the $n$th tail within $1/n$ of $x$ proves the usual Mazur lemma formulation as well.

The weak-star topology on the continuous dual space $X^{\ast }$ is $\sigma (X^{\ast },X)$: convergence means pointwise convergence on $X$, and a neighbourhood base prescribes finitely many evaluation inequalities. The Banach-Alaoglu theorem states that the closed unit ball of $X^{\ast }$ is compact in this weak-star topology, even if $X$ is incomplete. Embed this closed unit ball intowhere $\mathbb{K}=\mathbb{R}$ or $\mathbb{C}$. Each factor is compact, so $P$ is compact by the Tychonoff theorem. Inside $P$, the equations $a_{x+y}=a_x+a_y$ and $a_{\lambda x}=\lambda a_x$ define a closed set. Every such point defines a linear functional satisfying $|a_x|\le \Vert x\Vert$, hence belongs to the closed unit ball of $X^{\ast }$. Thus this image is closed in $P$. The product topology on it is exactly the weak-star topology, proving Banach-Alaoglu theorem. Evaluations also separate its points, so the weak-star topology is Hausdorff.

For the canonical embedding into the bidual $J_X:X\to X^{\ast \ast }$, we have $(J_{X}x)(f)=f(x)$. Restricting all evaluations at $f\in X^{\ast }$ therefore gives exactly $\sigma (X,X^{\ast })$. Thus the induced subspace topology is the weak topology on $X$.

Now identify $X$ with $J_{X}X$. Let $C$ be a bounded convex set, write $D$ for its norm closure in $X$, and let $K$ be its weak-star topology closure in $X^{\ast \ast }$. Boundedness places $K$ in a multiple of the closed unit ball of $X^{\ast \ast }$, so $K$ is compact by Banach-Alaoglu theorem. The preceding subspace topology identification and Mazur theorem giveIf $D$ is a weakly compact set, its image in the Hausdorff weak-star topology is compact and therefore closed. It contains $C$, so $K\subseteq D\subseteq X$. Conversely, if $K\subseteq X$, the displayed identity gives $K=D$, and its compactness is precisely weak compactness in $X$. Hence $\boxed{D\text{ is weakly compact}⟺K\subseteq X}$. This argument also covers $C=\varnothing$.

For a bounded linear operator $T:X\to Y$, its Banach-space adjoint is $T^{\ast }:Y^{\ast }\to X^{\ast }$, defined by $(T^{\ast }{y}^{\ast })(x)=y^{\ast }(Tx)$. Evaluation at any fixed $x$ is thus evaluation at $Tx$ after applying $T^{\ast }$. Each is continuous in the relevant weak-star topology, proving that $T^{\ast }$ is weak-star continuous. Applying the same result to $T^{\ast }$ shows that $T^{\ast \ast }:X^{\ast \ast }\to Y^{\ast \ast }$ is weak-star continuous. Direct evaluation gives

Use $B_X$ for the closed unit ball; using the open ball gives the same norm closure of $T(B_X)$. Goldstine theorem says that $J_X{B}_X$ is weak-star dense in $B_{X^{\ast \ast }}$. Put $K=T^{\ast \ast }(B_{X^{\ast \ast }})$. It is compact and closed in the weak-star topology by Banach-Alaoglu theorem and the established continuity. It contains $J_{Y}T(B_X)$. Conversely, Goldstine theorem gives, for every $x^{\ast \ast }\in B_{X^{\ast \ast }}$, a net $(J_X{x}_{\alpha })$ from $J_X{B}_X$ converging weak-star to $x^{\ast \ast }$; its image converges weak-star to $T^{\ast \ast }{x}^{\ast \ast }$. ConsequentlyApply the preceding bounded convex set criterion in $Y$, and then scale the closed unit ball. We obtain the bidual characterization of weakly compact operators:The canonical embedding into the bidual on the right specifies exactly which copy of $Y$ is intended.

For a convex subset of a Banach space, weak closure equals norm closure. The Mazur theorem states that for every convex set $C\subseteq X$,Since every bounded linear functional is norm-continuous, the weak topology is weaker than the norm topology, giving ${\overline{C}}^{\Vert \cdot \Vert }\subseteq {\overline{C}}^w$.

For the reverse inclusion, use this form of the Hahn-Banach separation theorem: if $D$ is a nonempty norm-closed convex set in a real normed vector space and $x\notin D$, there is a continuous real-linear functional $F$ such thatApply it to $D={\overline{C}}^{\Vert \cdot \Vert }$. In a complex Banach space, use the underlying real space; every continuous real-linear $F$ is the real part of the complex bounded linear functional $f(v)=F(v)-iF(iv)$. The separating strict inequality gives a neighbourhood open for the weak topology of $x$ disjoint from $D$, so $x\notin {\overline{C}}^w$. The empty set case is immediate. This proves the Mazur theorem.

A weakly null sequence has disjoint convex blocks converging to zero in norm. If $x_n\stackrel{w}{\to }0$, then for every starting index $m$,The Mazur theorem places $0$ in the norm closure of that tail convex hull. Thus a finite convex combination of vectors from any tail can have norm less than any prescribed $\epsilon >0$.

Choose the convex blocks recursively. After selecting the previous terminal index $q_{n-1}$, let $p_n>q_{n-1}$, and choose a finite convex combination from $\{x_i:i\ge p_n\}$ with norm less than $2^{-n}$. Choose $q_n$ beyond its largest used index, padding the intervening coefficients and the final coefficient with zero. This ensures the printed strict condition $p_n<q_n$ as well as $q_n<p_{n+1}$. Setting unused coefficients to zero yieldsTherefore $u_n\to 0$ in norm. The recursive tail selection is what makes these convex blocks, rather than merely unrelated convex combinations.

Next suppose $X^{\ast }$ is separable and $(x_n)$ is bounded. Use the canonical embedding into the bidual $J_X:X\to X^{\ast \ast }$, where $J_{X}x(f)=f(x)$. If $\Vert x_n\Vert \le M$, then $J_X{x}_n\in M{B}_{X^{\ast \ast }}$. The Banach-Alaoglu theorem makes this ball compact in $\sigma (X^{\ast \ast },X^{\ast })$, and weak-star metrizability of the dual ball makes it metrizable because its predual $X^{\ast }$ is separable. A compact space that is a metric space is sequentially compact, so some subsequence $(y_n)$ satisfiesThe limit need not belong to $J_{X}X$; it is precisely the use of the bidual space that supplies compactness without assuming reflexivity.

For a convex block $u_n={\sum }_{i=p_n}^{q_n}{a}_i{y}_i$, every $f\in X^{\ast }$ satisfiesBoth $f(y_n)$ and $f(u_n)$ tend to $\varphi (f)$, soThis is the useful convex-block cancellation of a weak-star limit; it does not require the limit to be a vector in $X$.

The quotient sequence has approximate lifts in $3B_X$ that are weakly null after passing to a subsequence. Let $q:X\to Z=X/Y$ be the quotient map, with the quotient norm. Since $\Vert z_n\Vert \le 1$, choose $v_n\in X$ such thatThis uses the infimum defining the quotient norm and does not assume that it is attained. By the preceding compactness argument, pass to a subsequence $y_n=v_{k_n}$ with a common weak-star limit in $X^{\ast \ast }$. Its quotient images $q(y_n)=z_{k_n}$ form a weakly null sequence.

Apply the convex block construction to $(q(y_n))$ in the quotient Banach space. Using the same coefficients on $(y_n)$ gives convex blocksSet $x_n=y_n-u_n$. The convex-block cancellation of a weak-star limit proves $x_n\stackrel{w}{\to }0$, whileThus the approximate weakly null lifting through a quotient is achieved with the required bound:

The useful form is Talagrand's convex distance inequality. Let $({\Omega }_i,{\mu }_i)$ be standard probability spaces, let $\Omega ={\prod }_{i=1}^n{\Omega }_i$ carry the product measure $\mu ={⨂}_i{\mu }_i$, and let $A\subset \Omega$ be a measurable event with $\mu (A)>0$. For $x\in \Omega$, form the mismatch vectorsThe Talagrand convex distance is the distance from zero to their closed convex hull:Equivalently, by the Hahn-Banach separation theorem for two convex sets,Nonnegative weights suffice because every mismatch vector has nonnegative coordinates. Talagrand's convex distance inequality statesIn particular, Markov's inequality gives the product-space concentration inequalityThe same conclusion is interpreted with outer probabilities if a distance set is not measurable; the continuous geometric function used below has measurable level sets. A median $M$ of a real random variable $Z$ means that $\mathbb{P}(Z\le M)\ge 1/2$ and $\mathbb{P}(Z\ge M)\ge 1/2$. Applying the displayed concentration inequality to suitable level sets will control deviations around a median.

Normalize $v_K$ by $v_K({\pi }_K)=1$ and put $v_K(0)=+\infty$. Write $f(X)={\sum }_{j=0}^d{a}_j{X}^j$, with $a_d=1$ and $a_0\ne 0$. In the usual coefficient-exponent convention, the Newton polygon $N_K(f)$ is the lower boundary of the convex hull of the upward vertical rays starting atIt runs from $(0,v_K(a_0))$ to $(d,0)$, with nondecreasing slopes from left to right. Zero coefficients contribute no finite point. Equivalently it is the largest convex piecewise-linear function lying below all these coefficient points.

The Newton polygon root valuation theorem says that a segment of slope $s$ and horizontal length $r$ accounts for exactly $r$ roots of valuation $-s$, counted with multiplicity, using the extended valuation on an algebraic closure. The nonzero constant coefficient excludes a zero root.

For a short justification, use the weighted Gauss valuation $w_t(P)={\min }_j(v(c_j)+jt)$ for $P=\sum c_j{X}^j$. It is multiplicative: after scaling $X$ by an element of valuation $t$ in a valued extension, the initial nonzero residue polynomials multiply without vanishing. Rational $t$ suffice. Factoring a monic polynomial into linear factors gives $w_t(f)={\sum }_r\min (t,v(r))$. This supporting-line function changes derivative at precisely the root valuations; its derivative drops count their multiplicities. Supporting lines to the lower polygon have slope $-t$, proving the sign and horizontal-length assertion.

Slope convention for part (b). Reflecting the horizontal axis, by plotting $(d-j,v_K(a_j))$, produces the reflected Newton polygon convention; its slopes are the root valuations themselves. Part (b)'s wording with $m$ instead of $-m$ is correct under this positive-root-valuation convention. The proof below gives both forms explicitly, so the result does not depend on silently changing the sign.

Use an ideal carrier-sense multiple access scheme on the interference graph. An active station finishes its transmission after an independent unit-rate exponential distribution waiting time. An inactive station has an independent attempt clock with an exponential distribution of rate $e^{{\theta }_r}$; an attempt succeeds only when all its neighbors are inactive. Attempts that are blocked do not change the state. Thus, on the independent sets represented by $S$, the continuous-time Markov chain has transition ratesThe empty independent set can be reached by successive deactivations, and any other independent set can be reached from it by successive activations. Hence this finite chain is an irreducible Markov chain. The weight $a_{\theta }(n)=e^{\theta \cdot n}$ satisfiesBy detailed balance for a continuous-time Markov chain, its unique stationary law isThis is a finite exponential family. Its natural parameter of an exponential family is $\theta$ and its mean parameter of an exponential family is the vector of active fractions.

The throughput region of an interference graph is exactly $\Lambda =\mathrm{conv}S$. To see the possibly less immediate inclusion, suppose a random feasible schedule has mean $v\ge \lambda$. Retain each of its active vertices $r$ independently with probability ${\lambda }_r/v_r$, interpreting zero coordinates as always deleted. A subset of an independent set remains an independent set; the thinned schedule has mean exactly $\lambda$. Thus $\lambda$ lies in the convex hull of $S$. The opposite inclusion follows from the definition using equality. Moreover $0,e_1,\dots ,e_R\in S$, so this convex hull has full dimension.

Now choose $\epsilon >0$ such that $\mu =\lambda +\epsilon 1$ remains in the interior of $\mathrm{conv}S$. Use interior moment matching in a finite exponential family. Consider the convex functionThere is a ball of radius $\delta >0$ around $\mu$ contained in $\mathrm{conv}S$. Maximizing a linear functional over the convex hull is the same as maximizing over its generating set, so, for every $\theta$,The last inequality uses the point $\mu +\delta \theta /\Vert \theta \Vert$ when $\theta \ne 0$. Hence $F$ is a coercive function and has a finite minimizer ${\theta }^{\ast }$. Differentiating the finite normalizing sum givesThis covariance matrix is a positive-definite matrix: a linear functional constant on all states of positive weight must be constant on $0,e_1,\dots ,e_R$, so its coefficients vanish. Thus $F$ is a strictly convex function; its minimizer is unique. At that minimizer the desired strict service margins areFor a backlogged station that transmits at unit speed whenever active, the long-run throughput is ${\mathbb{E}}_{\theta }[n_r]$, by the ergodic theorem for a finite continuous-time Markov chain. Therefore the ideal carrier-sense multiple access scheme can supply a strict service margin for every arrival vector in the interior of the throughput region of an interference graph. The local attempt rates can realize the whole interior capacity region in this sense. Boundary points may require parameters tending to infinity, and the argument gives no uniform delay or mixing-time bound near the boundary.

The weak topology $\sigma (X,X^{\ast })$ is the coarsest topology making every bounded linear functional continuous. A neighbourhood basis at $x$ consists of sets $\{y:|f_j(y-x)|<ϵ,1\le j\le m\}$ for finite families in $X^{\ast }$.

Mazur theorem says that for any convex subset $C$ of a real or complex normed vector space,The norm closure is convex. If $x$ is outside it, the Hahn-Banach separation theorem gives a bounded linear functional $f$ and a real $a$ with $\mathrm{Re}f(x)>a\ge {\sup }_{y\in C}\mathrm{Re}f(y)$. In the real case omit the real part. Thus $x$ has a weak neighbourhood missing $C$, proving that the weak closure lies in the norm closure. The other inclusion follows because the weak topology is weaker than the norm topology. In the complex case real separation is converted to a complex functional by $f(z)=h(z)-ih(iz)$.

The sequential formulation, Mazur lemma, follows as well. If $x_n\rightharpoonup x$, then $x$ lies in the weak closure of each tail and hence in the norm closure of its convex hull. Select a finite convex combination of the $n$th tail at norm distance less than $1/n$ from $x$.

A weakly bounded set $D$ satisfies ${\sup }_{x\in D}|f(x)|<\infty$ for every $f\in X^{\ast }$. Regard $J(D)$ as a pointwise bounded family of functionals on $X^{\ast }$. The completeness of the dual space holds even if $X$ is incomplete: a norm-Cauchy sequence of functionals has a pointwise bounded linear limit and then converges uniformly on the unit ball. The Uniform boundedness principle therefore gives ${\sup }_{x\in D}\Vert Jx\Vert <\infty$, and $\Vert Jx\Vert =\Vert x\Vert$ proves norm boundedness.

One can see the precise Baire argument here. The closed sets $F_n=\{f\in X^{\ast }:{\sup }_{x\in D}|f(x)|\le n\}$ cover the Banach space $X^{\ast }$. The Baire category theorem makes some $F_n$ contain a ball $f_0+r{B}_{X^{\ast }}$, after shrinking the radius. For $\Vert g\Vert \le r$, both $f_0$ and $f_0+g$ lie in $F_n$, so ${\sup }_D|g(x)|\le 2n$. Scaling and the dual norm formula yield ${\sup }_D\Vert x\Vert \le 2n/r$. A weakly compact set is weakly bounded because each functional has compact, hence bounded, image. Consequently it is norm bounded.

For a Banach space, let $J:X\to X^{\ast \ast }$ be its canonical isometry. We use two explicitly stated weak-star facts: Banach-Alaoglu theorem makes a dual unit ball weak-star compact, and Goldstine theorem makes $J(B_X)$ weak-star dense in $B_{X^{\ast \ast }}$. The weak topology on $X$ is carried by $J$ to $\sigma (X^{\ast \ast },X^{\ast })$ on its image, since their coordinates are the same evaluations $f(x)$.

If $X$ is a reflexive Banach space, $J(B_X)=B_{X^{\ast \ast }}$ and Banach-Alaoglu proves weak compactness. Conversely, if $B_X$ is weakly compact, its image is weak-star compact and hence closed in the Hausdorff space $X^{\ast \ast }$. Goldstine density then forces $J(B_X)=B_{X^{\ast \ast }}$, which implies $JX=X^{\ast \ast }$. This proves the weak compactness characterization of reflexivity:Finally let $K\subset X$ be weakly compact and let $(f_n)\subset B_{X^{\ast }}$ separate points. If $K$ is empty there is nothing to prove; otherwise defineThe summands are bounded by $2^{-n}$ and separation makes $d(x,y)=0$ only for $x=y$. The coordinate maps are weakly continuous, so the series, being uniformly convergent, makes the identity from weak $K$ to metric $K$ continuous. A continuous bijection from a compact space to a Hausdorff space is a homeomorphism. Thus $d$ induces precisely the weak topology on $K$, the countable separating family metrizes a weakly compact set result. No norm-density of the separating family in $X^{\ast }$ is claimed or required.