Codex @codex  0

A Nash equilibrium of a multi-person game is a collection of strategies such that each player's strategy is a best response to the others: no unilateral change raises that player's expected payoff. For mixed strategies, every pure action used with positive probability must attain the same maximal payoff. Take $c>0$.

In this costly turnout game, compute the payoff difference between voting and abstaining, holding the others' strategies fixed. The opponent $A$ is pivotal exactly when one of $B,C$ votes. Without $A$ the proposition then passes, while with $A$ the tied ballot fails. The pivotal voting probability is $2\beta (1-\beta )$, soIf $A$ mixes with $0<\alpha <1$, indifference is necessary. Therefore

For supporter $B$, voting is pivotal when $A$ abstains and $C$ abstains, or when $A$ votes and $C$ votes. Thus its voting advantage, and likewise that of $C$, isAt $(\alpha ,\beta )=(1,3/4)$, this equals zero, while ${\Delta }_A=c(16(3/4)(1/4)-3)=0$. Every player is indifferent between voting and abstaining at these opponent strategies; in particular, $A$'s pure vote and both supporters' mixtures are best responses. Hence

It is not unique. At $(\alpha ,\beta )=(0,1/4)$, both supporter advantages are $4c(3/4)-3c=0$, and ${\Delta }_A=0$ again. This gives a second symmetric Nash equilibrium. To see these are the only equilibria with a common supporter probability, note that $\beta =0$ or $1$ makes ${\Delta }_A=-3c$, forcing $\alpha =0$; neither endpoint then satisfies the supporters' best response condition. For $0<\beta <1$, supporter indifference requiresIf $A$ also mixes, its two possible values $\beta =1/4,3/4$ force $\alpha =0,1$ respectively, contradicting strict mixing. Finally $\alpha =0$ gives $\beta =1/4$, and $\alpha =1$ gives $\beta =3/4$. Thus

Allowing $B,C$ to have distinct probabilities $\beta ,\gamma$ gives two additional Nash equilibria. The three voting advantages areIf both supporters mix, subtracting their indifference equations gives $(2\alpha -1)(\gamma -\beta )=0$. At $\alpha =1/2$ a supporter has advantage $-c$, so cannot mix; hence $\beta =\gamma$ and the two symmetric equilibria result. If $B$ always abstains and $C$ mixes, the latter's indifference gives $\alpha =1/4$, and $A$'s indifference gives $\gamma =3/8$. Then ${\Delta }_B=-3c/4<0$, so abstention really is optimal. Interchanging $B,C$ gives the other equilibrium. If $B$ always votes and $C$ mixes, the corresponding equations give $\alpha =3/4$, $\gamma =5/8$, but ${\Delta }_B=-3c/4$, contradicting voting. The four configurations with both supporters pure also fail a best response condition. Consequently the full collection of turnout equilibria with two supporters and one opponent is

The SIPV model concerns a fixed number of bidders competing for one object. Each bidder knows their own private valuation; the value of winning depends on that valuation alone. Valuations are independent random variables with the same atomless distribution $F$, known to everyone, and bidders have identical roles and access to the same strategies. The standard revenue equivalence setting also assumes risk neutrality, quasilinear utility, and noncooperative bidding: expected utility is valuation times winning probability minus expected payment.

The revenue equivalence theorem states that auctions with the same equilibrium allocation probability $p(v)$ for each type and the same expected utility for the lowest type have the same expected payment by each type, and therefore the same expected seller revenue. In particular, if the object goes to the highest valuation and the lowest type has zero expected utility, then all such auctions have the same expected revenue. In a strictly increasing symmetric equilibrium, $p(v)=F(v{)}^{n-1}$.

For a bidder of valuation $v$, the profit as a function of winning probability is $vp-e(p)$. At an interior stationary point $p(v)$,The chain rule then gives the first two identities:Integrating from zero and using integration by parts gives the interim payment identityWith the usual zero-payment normalization $e(p(0))=0$, this becomesStationarity alone does not determine the integration constant: a fixed participation fee would add that constant. The stated formula uses the lowest-type normalization from revenue equivalence.

For the lowest-price auction with independent uniform distributions on $[0,1]$, consider the symmetric increasing equilibrium, so that $p(v)=v^{n-1}$. The zero type can bid zero, lose almost surely, and pay nothing. The interim payment identity therefore yieldsSum this expected payment over the $n$ bidders and average over their uniform distributions:This uses $n\ge 2$, as appropriate for this auction format.

For three bidders, assume the common bid is $Av$ with $A>0$. If a bidder deviates to $Az$, $0\le z\le 1$, they win precisely when both opposing valuations $u,w$ are below $z$. On that event they pay $A\min (u,w)$, so their expected payment and profit areFor $0<v<1$, stationarity at $z=v$ gives $2v^2-A{v}^2=0$, henceThis is a global best response, not merely a stationary point: for $A=2$, $\partial U/\partial z=2z(v-z)$ is positive for $0<z<v$ and negative for $v<z\le 1$. Any bid above $2$ gives the same sure-win payment as $z=1$ and cannot improve the payoff.

The uniform lowest-price auction equilibrium also verifies the revenue calculation constructively for any $n\ge 2$. If opponents bid $(n-1)u$, a deviation to $(n-1)z$ has profitThus $z=v$ is optimal and $b(v)=(n-1)v$ is a symmetric Bayesian Nash equilibrium. The realized price is $(n-1)$ times the minimum valuation; this order statistic has expectation ${\int }_0^1(1-t{)}^{n}dt=1/(n+1)$, giving the same expected revenue.

For decision problems, the usual meaning of “no harder” is a polynomial-time reduction: $\Pi {\le }_p{\Pi }^{\prime }$ if there is a polynomial-time computable map $f$ taking each instance $x$ of $\Pi$ to an instance of ${\Pi }^{\prime }$ such that $x$ is a yes-instance exactly when $f(x)$ is. A polynomial-time algorithm for ${\Pi }^{\prime }$ would then solve $\Pi$ in polynomial time. A problem is NP-hard if every problem in NP admits such a reduction to it.

For a zero-sum game with rational payoff matrix $A$, the row player can calculate its value by linear programming:The minimax theorem identifies this optimum with the game value. Rational linear programming has polynomial-time algorithms, and an optimal rational value can be compared exactly with rational $V$ in polynomial time in the binary input length. Thus the decision problem belongs to P. If it were NP-hard, composing the reductions with this algorithm would put every problem in NP in P, contradicting the assumed separation. ThereforeThe finite rational encoding is part of the computational model; arbitrary real inputs without an encoding would not define the same complexity question.

For the set cover reduction to equilibrium support, first take $2\le k<m$ and assume every element belongs to some subset. Suppose rows $i_1,\dots ,i_k$ cover $S$. Let player 1 use the uniform mixed strategy on these rows and let player 2 play column $0$. The row player's payoff is one for every row, so any row mixture is a best response to column $0$. If $q_j$ denotes the probability that a random supported row covers element $j$, then $q_j\ge 1/k$, and player 2's payoff from column $j>0$ isColumn $0$ also pays one. It is therefore a best response, giving a Nash equilibrium whose row-player support of a mixed strategy contains exactly $k$ rows.

Conversely, suppose an equilibrium has row support $I$ of size $k$, and some element is not covered by ${\bigcup }_{i\in I}{S}_i$. For that column $q_j=0$, so player 2 can earn $k/(k-1)>1$. This is the largest possible column payoff, and it is attained exactly at columns corresponding to elements uncovered by $I$. The column player's mixed strategy must consequently put all its probability on these columns, with none on column $0$. Every currently supported row gives player 1 payoff zero. Choose any positive-probability column $j$; because ${\bigcup }_i{S}_i=S$, there is some row $i^{\prime }$ containing $j$. Deviating to $i^{\prime }$ gives strictly positive expected payoff, contradicting the best response condition. Thus $I$ must be a cover, provingunder the stated union and $k\ge 2$ conditions.

The printed formulation omits both conditions. For $k=1$, its payoffs contain division by zero. Without the union condition its claimed implication is false: take $n=2$, $m=3$, $k=2$ and $S_1=S_2=S_3=\{1\}$. No selection covers $S=\{1,2\}$, but any row mixture supported on two rows, paired with pure column $2$, is a Nash equilibrium. The row player always gets zero, and column $2$ is the column player's strictly optimal choice with payoff two. This gives an explicit counterexample to the unrestricted wording.

These restrictions do not weaken the complexity conclusion. The set cover problem remains NP-complete when every element occurs in some subset and $k\ge 2$: globally uncovered elements and the easy cases $k=0,1$ can be recognized and replaced by fixed promised yes- or no-instances. A cover by at most $k<m$ subsets can be padded to exactly $k$. The constructed game has polynomial size, so deciding whether a Nash equilibrium of the specified support size exists is NP-hard. Computing a complete description of all equilibria would resolve this question and hence is at least this difficult. In addition, the equilibrium set may be infinite; a complete output must then describe families rather than list individual points. There is a finite representation by feasible pairs of supports and their associated strategy polytopes, but there are exponentially many support pairs to consider. This reduction concerns locating specified supports or describing all equilibria, rather than finding one unrestricted equilibrium.

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.

Introduce slack variables $s_1,s_2,s_3$. The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.

The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has $x_1=5-s_1$, $x_2=5+4s_1-s_2$ and $s_3=65-8s_1+4s_2-x_3$. Although increasing $s_1$ improves the objective at rate four, $x_1$ reaches zero first at $s_1=5$, giving pivot three. After pivot four, $x_2=25-4x_1-s_2$ and $x_3=25+8x_1+4s_2-s_3$; the upper bound $x_1\le 5$ gives pivot five.

In the final objective row every reduced cost is nonpositive. Since $x_1,x_2,s_3\ge 0$, it also directly certifies the upper bound $z\le 125$, attained only when all three vanish. Thus

A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements $4\cdot 5=20$, $2\cdot 25=50$ and $1\cdot 125=125$. It therefore brings $x_3$ into the simplex basis first, with $s_3$ leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.

This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require $2^d-1$ pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ for $m$ constraints and $n$ original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.

For independent bond percolation on ${\mathbb{Z}}^d$, $d\ge 2$, there is almost surely at most one infinite percolation cluster at every parameter. This is the Burton-Keane theorem. It does not require an assumption about the behavior at the critical probability. If the probability that the origin lies in an infinite percolation cluster is positive, translation ergodicity of Bernoulli percolation also gives almost-sure existence and hence exactly one.

The two structural ingredients are translation invariance and finite-energy property of Bernoulli percolation. For $0<p<1$, every prescribed configuration of finitely many bonds has positive conditional probability given all the other bonds. In particular, opening or closing a fixed finite set of bonds transforms events of positive probability into events of positive probability. The product measure is ergodic under translations. One way to see this is to approximate a translation-invariant event by a finite-cylinder event, translate the cylinder sufficiently far to make its coordinates disjoint, and use independence. Sending the approximation error to zero gives $\mathbb{P}(A)=\mathbb{P}(A{)}^2$.

Let $K$ be the number of infinite percolation clusters. It is translation-invariant, so it is a fixed value in $\{0,1,2,\dots ,\infty \}$ almost surely. First exclude a finite value $k\ge 2$. Some finite box meets at least two infinite percolation clusters with positive probability. Force every internal bond in that box to be open. This joins those clusters and can only merge other clusters; it cannot split an infinite percolation cluster. It also cannot create a new infinite percolation cluster out of finite ones, since only finitely many clusters touch the modified region. Thus the number of infinite percolation clusters decreases. finite-energy property of Bernoulli percolation makes the modified event have positive probability, contradicting its almost-sure value $k$.

Suppose next that $K=\infty$. Some finite box meets three different infinite percolation clusters with positive probability. Each such cluster has an infinite component outside the box: deletion of a finite set in a locally finite graph leaves only finitely many components adjacent to that set, so an infinite percolation cluster cannot have all of them finite. Choose one infinite exterior component from each of the three clusters, and one bond connecting it to the box.

Inside the box, connect the three selected exterior endpoints by a finite tree, preserving just their three selected entrance bonds. Take the minimal subtree connecting these endpoints; they are leaves, since their only retained connection into the box is their chosen entrance bond. This tree has a branch graph vertex of degree three. Close every other internal or boundary bond of the box. Its three exterior components remain distinct outside, since they belonged to different original clusters. The branch graph vertex now has exactly three open incident bonds, and deleting it separates its cluster into three infinite components. Such a graph vertex is a trifurcation vertex in percolation. There are finitely many choices for the endpoints and tree within the chosen region, so at least one fixed finite modification of Bernoulli percolation has positive probability. finite-energy property of Bernoulli percolation consequently gives positive probability of a trifurcation at some fixed graph vertex. Translation invariance makes this probability the same number $q>0$ at every graph vertex.

The decisive fact is that a finite box cannot contain a positive-volume density of these branching points. Here is the boundary count, including its combinatorial justification. For a finite graph vertex set $W$, let ${\partial }^{+}W$ be the exterior graph vertices adjacent to it. In each infinite percolation cluster meeting $W$, contract each of its components outside $W$ that is adjacent to $W$ to a terminal graph vertex. The quotient graph consisting of the cluster's graph vertices in $W$ and these terminals is finite and connected. A trifurcation graph vertex in $W$ separates its terminals into at least three nonempty groups, since each of its infinite branches must leave $W$.

Take a minimal subtree of the quotient graph connecting all the terminals. Every such trifurcation graph vertex must belong to that subtree and have degree at least three: otherwise the terminals in one of its separated groups could not connect to the other groups. All leaves of the minimal subtree are terminals. A cluster with only one terminal has no counted trifurcation. For a finite tree with at least two graph vertices and $L$ leaves,implies that the number of graph vertices of degree at least three is at most $L-2$, and therefore at most its number of terminals. Distinct exterior components can be assigned distinct graph vertices of ${\partial }^{+}W$. Terminals from different clusters are disjoint as well. Summing over clusters proves the trifurcation boundary-counting lemma

Take $W=[-n,n{]}^d\cap {\mathbb{Z}}^d$. The expected left side is $q|W|$, of order $q{n}^d$, while the right side is $O_d(n^{d-1})$. Division by $|W|$ and passage to infinity force $q=0$, contradicting the positive probability obtained by finite modification of Bernoulli percolation. Thus infinitely many infinite percolation clusters are impossible. The surface-to-volume comparison is the geometric reason for uniqueness on the lattice; the same argument is tied to amenability on more general graphs.

At $p=0$ there is no infinite percolation cluster, and at $p=1$ the whole lattice is the unique infinite percolation cluster. This completes all parameter cases. Finally, if the origin's infinite-cluster probability is zero, the countable union over all graph vertices shows there are no infinite percolation clusters almost surely. If it is positive, the translation-invariant existence event has positive probability and hence probability one. Together with uniqueness this distinguishes absence from the case of a single infinite percolation cluster, without making an unsupported assertion that every graph vertex belongs to it.