Take three players and define the simple cooperative gameIt is a superadditive coalitional game: two disjoint coalitions cannot both have value one because each would need player 1. If one has value one, their union does too; if neither does, the desired inequality is immediate.

The vector $(1,0,0)$ belongs to the core of a cooperative game. More strongly, it is the unique core vector: singleton constraints give nonnegative coordinates, efficiency gives sum one, and the value-one coalitions $\{1,2\}$ and $\{1,3\}$ force $x_3=x_2=0$.

In a random player ordering, player 1 is pivotal unless it comes first, giving Shapley value $2/3$. Player 2 is pivotal only in order $1,2,3$, and player 3 only in order $1,3,2$. ThusThe coalition $\{1,2\}$ receives only $5/6<1$, so the Shapley value is outside the core. This proves that superadditivity and nonempty core do not imply Shapley stability.

For an $n$-player transferable utility game with $v(\varnothing )=0$, the Shapley value isIt averages player $i$'s marginal contribution over uniformly random orders of all players. Exactly $|S|!(n-|S|-1)!$ of the $n!$ permutations put precisely $S$ before $i$. For a cooperative cost game, apply the same linear formula to the cost function; the result represents payments instead of distributed benefits.

Let $P_k$ be the initial proposer's share, measured as a fraction of the pie currently available, with $k$ rounds remaining. The last-round argument in part (e) gives $P_1=1$. Rejecting an offer leaves the responder as next proposer with a pie smaller by factor $\alpha$, so its continuation value is $\alpha P_{k-1}$. The current proposer offers exactly that amount, which is accepted by the continuous-offer bargaining acceptance lemma. HenceThe formula follows by summing a finite geometric series, or by induction in the recurrence. Agreement is immediate in every subgame, so this share is player 1's actual initial payoff.

For odd $k$, $P_k=(1+{\alpha }^k)/(1+\alpha )$ lies above $1/(1+\alpha )$ and decreases with $k$. For even $k$, $P_k=(1-{\alpha }^k)/(1+\alpha )$ lies below that value and increases with $k$. Thus prefer odd to even, fewer rounds among odd choices, and more rounds among even choices. For the given $k_1<k_2$, this simplifies to choose $k_1$ if $k_1$ is odd, and choose $k_2$ if $k_1$ is even. All comparisons are strict because $0<\alpha <1$. This is the finite-horizon bargaining parity effect.

In the final round, player 1 strictly accepts every $q_2>0$. In any subgame perfect equilibrium it must also accept $q_2=0$ with probability one. Otherwise, if that acceptance probability were $a<1$, offering zero would give player 2 only $a\alpha$. A sufficiently small positive offer would be accepted and yield more. No positive offer maximizes player 2's payoff either, because a smaller positive offer improves it. The same supremum argument rules out a mixed offer distribution attaining the missing maximum. Thus the final-round equilibrium uniquely has $q_2=0$, accepted, with payoffs $(0,\alpha )$.

In round one, player 2 therefore rejects $q_1<\alpha$ and accepts $q_1>\alpha$. At $q_1=\alpha$ it is indifferent, but equilibrium again forces acceptance with probability one: if acceptance were less likely, player 1 could improve on any proposed optimum with an offer just above $\alpha$. Since $\alpha <1$, player 1 strictly prefers the resulting positive payoff to rejection.

Consequently the unique equilibrium outcome is immediate agreement at $q_1=\alpha$, giving payoffs $(1-\alpha ,\alpha )$. The full strategies are: player 1 offers $\alpha$ initially and accepts every nonnegative final offer; player 2 accepts initial offers at least $\alpha$, rejects smaller ones, and offers zero in every reached final-round subgame. These prescriptions cover off-path histories too. Acceptance at indifference follows from the continuous-offer bargaining acceptance lemma, rather than an arbitrary tie-breaking convention.

Yes: let the order be voter 2, then voter 3, then voter 1. When voter 1 moves last, it makes $A$ win whenever that is possible; otherwise it prefers $B$ to $C$. For the first two votes in this new order, its optimal continuation winners areRows now record voter 2's initial choice and columns voter 3's choice. In a three-way split, the specified tie-break produces $A$, which explains, for example, the off-diagonal $B,C$ entry.

Voter 3 optimizes its ranking $B\succ C\succ A$ in each row, giving the continuation winners $A,B,C$. Voter 2 then chooses $C$, its favourite of the three. The winner is therefore $C$ in every subgame perfect equilibrium, again by unique outcome under strict outcome preferences. In particular, if voter 2 starts with $C$, voter 3 must also vote $C$: either other vote lets the last voter force $A$.

For each history of the first two votes, voter 3 selects its favourite achievable winner. Writing rows for voter 1's vote and columns for voter 2's vote, the resulting continuation winners areFor example, after votes $B,C$, voter 3 can make either $B$ or $C$ win, and prefers $B$; a vote for $A$ would instead produce the tie-break winner $A$.

Voter 2 prefers $C$ to $B$ to $A$. Optimizing each row therefore gives continuation winners $C,B,C$ after voter 1's respective choices $A,B,C$. Voter 1 prefers $B$ to $C$ and therefore votes $B$, giving winner $B$ in every subgame perfect equilibrium.

Some histories admit several equally good votes, but they produce the same winning candidate. Since each voter strictly ranks the three possible winners, unique outcome under strict outcome preferences makes this winner independent of those action ties. This is backward induction over outcomes, not a claim that the entire equilibrium strategy profile is unique.

Apply backward induction in games, or Zermelo's algorithm, from the terminal decision points. At node 4, player 1 chooses $R_4$ because $6>3$, giving continuation payoffs $(6,9)$. At node 5, player 1 chooses $L_5$ because $4>2$, giving $(4,6)$. At node 3, player 2 compares its continuation payoffs nine and six, so chooses $L_3$. At node 2, player 2 chooses $R_2$, receiving four rather than two.

At the root, player 1 consequently receives six from either action: $L_1$ leads to $(6,4)$ and $R_1$ to $(6,9)$. Thus there are two pure subgame perfect equilibria, with strategiesThe semicolon separates the players, and each list specifies the player's action at every one of its decision points. All four non-root choices are strict. If mixed strategies are included, every mixture between $L_1$ and $R_1$ at the root is also an equilibrium, with those other actions fixed. There are no further mixtures at the strict decision points.

A game tree is a rooted tree representing successive histories. A nonterminal vertex specifies the player who moves, its outgoing edges are the available actions, and each leaf specifies a terminal payoff for every player. A pure strategy specifies an action at every decision point belonging to that player, including decision points not reached by the eventual play.

For a perfect-information game, each player observes the exact preceding history. An extensive-form game with imperfect information additionally groups indistinguishable decision points into information sets, with compatible available actions. Chance moves, if present, carry specified probabilities; the displayed game has none. A subgame perfect equilibrium must prescribe a Nash equilibrium in every proper subgame as well as in the whole game.

Continue with $0<h<d$ and set $r=d/h$. Part (e) requires an interior count to satisfy $s\le r\le s+1$ with $s\ge k$; the all-deer endpoint $s=n$ is allowed when $r\ge n$. If $r$ is nonintegral and $k\le r<n$, only $s=\lfloor r\rfloor$ works. If $r=m$ is an integer with $k+1\le m\le n$, both $s=m-1$ and $s=m$ work. At $r=k$ only $s=k$ remains, while $r>n$ permits only $s=n$. When $r<k$, there is no positive equilibrium count.

Thus there are at most two positive counts, and exactly one precisely whenThis includes $k=n$, when the excluded set is empty. It counts numbers of deer hunters, not the many choices of which hunters participate. The argument is the threshold stag-hunt equilibrium count.

The original paper states only $h<d$ explicitly. Its assertion needs the usual strict positivity of the hare reward. If zero is included, take $n=6,k=4,d=1,h=0$. Counts $s=1$ and $s=2$ both give unsuccessful hunters zero, and one additional deer hunter still cannot reach the threshold; all unilateral alternatives also pay zero. The count $s=6$ is an equilibrium as well. These are three positive equilibrium counts, contradicting an unrestricted reading. More generally, for $h=0<d$, the positive counts are $1,\dots ,k-2$ and $n$.

Assume $0<h<d$ and the feasible threshold $2\le k\le n$. An unsuccessful deer hunter would gain by switching to hare, so an equilibrium with deer participants must have $s\ge k$. A deer hunter then earns $d/s$ and must not gain by changing to hare; this requires $d/s\ge h$. A hare hunter who joins would earn $d/(s+1)$, so staying with hare requires $h\ge d/(s+1)$. Hence the necessary and sufficient conditions for the stated range $0<s<n$ areThese conditions check every possible unilateral change in this two-action game, so they also prove sufficiency. Equality is allowed because a Nash equilibrium rules out strict improvements, not indifferent deviations. The endpoint $s=n$ has no hare hunter to check; it is an equilibrium exactly when $d/n\ge h$.

Under the intended positive rewards $0<h<d$, a hunter at the all-hare strategy profile receives $h$. A unilateral switch to deer leaves only one participant. Since the integer threshold satisfies $k>n/2$ with $n\ge 3$, we have $k\ge 2$, so that deer hunt fails and pays zero. Thus no player can gain by switching, and the all-hare profile is a Nash equilibrium. At $h=0$ it remains an equilibrium through indifference; negative $h$ would invalidate the claim.

Yes: choose $Y=4/X$. The equilibrium expected payoffs are opposite because this is a zero-sum game. They are equal exactly when both are zero. Part (b)'s value vanishes exactly when $XY=4$, and $4/X>0$ for every allowed $X>0$. This establishes both existence and the unique suitable positive choice of $Y$.

With rows and columns ordered Head, Tail, the payoff matrix of ordered pairs isThis is a zero-sum game. There is no pure Nash equilibrium: when the coins match, player 1 gains by switching to a mismatch; when they do not match, player 2 gains by making them match. Since $X,Y>0$, these improvements are strict.

Let $p$ and $q$ be the respective probabilities that players 1 and 2 choose Head. Player 1's payoffs from Head and Tail are $X-(X+2)q$ and $(Y+2)q-2$. Player 2 is indifferent when the corresponding player-1 payoffs against its two pure actions, $Y-(Y+2)p$ and $(X+2)p-2$, agree. The resulting unique fully mixed Nash equilibrium isBoth numbers lie strictly between zero and one. If either player instead used a pure action, the other's unique best response would force the pure-action cycle above, so there are no additional partly mixed equilibria. Substitution gives player 1's expected payoff $(XY-4)/(X+Y+4)$ and its negative for player 2.

For $X=1,Y=3$, the best response correspondences areTheir intersection is $(p,q)=(5/8,3/8)$, with expected payoffs $(-1/8,1/8)$.

For a finite normal-form game, a mixed strategy ${\sigma }_i$ is a probability distribution over player $i$'s pure strategies. Independent randomization by the players defines an expected payoff $u_i(\sigma )$. A strategy profile $\sigma$ is a Nash equilibrium iffor every player $i$ and every alternative mixed strategy ${\tau }_i$. By linearity in a player's own distribution, it is enough to check all pure deviations. Equivalently, every pure strategy in the support of a mixed strategy must be a best response to the other players' choices.

Combine all inequalities, including nonnegativity, into $Cx\le d$; explicitly, the rows $-e_j^{T}x\le 0$ encode $x_j\ge 0$. Let $x_{\ast }$ be a vertex of a linear polyhedron, equivalently an extreme point of the feasible linear polyhedron, and let $I$ index the active constraints there.

Suppose the active row normals have rank smaller than $n$. By the rank-nullity theorem there is a nonzero vector $h$ with $C_{i}h=0$ for every $i\in I$. Every inactive row has positive slack variable value $s_i=d_i-C_i{x}_{\ast }>0$. Since there are only finitely many rows, choose $\epsilon >0$ so small thatThen both $x_{\ast }+\epsilon h$ and $x_{\ast }-\epsilon h$ are feasible points: the active constraints remain equalities and no inactive inequality is violated. They are distinct, and $x_{\ast }$ is their midpoint, contradicting the extreme point property.

Therefore the active row normals have rank $n$, and at least $n$ linearly independent constraints are satisfied with equality. In particular at least $n$ constraints are tight, as claimed. Nonnegativity bounds must be counted: for example, at the origin these can supply all $n$ active rows. Degeneracy can make more than $n$ constraints tight, so the result does not assert exactly $n$.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

Remove the integer requirements from the previous formulation to obtain its linear programming relaxation. Give each edge constraint a nonnegative dual variable $y_e$, and each bound for $v\in Z$ a nonnegative dual variable $z_v$. Since all right-hand sides are one, the dual linear program isAn integer feasible point selects a multiset of edges touching every nonisolated vertex, together with at least one singleton for each isolated vertex. Repeated edges or singleton choices can be discarded without losing coverage, so an optimum has a genuine edge cover of the nonisolated part and one singleton per isolated vertex. If $G$ has no isolated vertices, this is exactly an edge cover, with the objective counting selected edges including any unnecessary multiplicities. The isolated-singleton extension is necessary because a graph with an isolated vertex admits no ordinary edge cover.

This interpretation concerns integer feasible dual solutions. The linear programming relaxation can have fractional optima, so its value need not equal the integer independent set optimum. For example, the triangle has relaxed independent-set value $3/2$, whereas its maximum independent set has size $1$ and its minimum edge cover has size $2$.

Let $Z$ be the set of isolated vertices of the finite simple graph $G=(V,E)$. Introduce a nonnegative integer $x_v$ for every vertex. Use the integer programEvery nonisolated vertex belongs to an edge, whose inequality and the other endpoint's nonnegativity already imply $x_v\le 1$. The explicit bounds on $Z$ therefore make all variables binary. For an integer feasible point, $S=\{v:x_v=1\}$ is an independent set, and its cardinality is the objective. Conversely the indicator vector of any independent set is feasible. Thus the optimal value is the maximum independent set size. Including the isolated-vertex bounds is essential for an arbitrary graph; without them the formulation would be unbounded whenever an isolated vertex is present.

Use the standard maximum form of a linear programAn arbitrary linear program can be converted by the following operations.

These substitutions preserve the attainable objective values, up to the stated sign and constant corrections, and map feasible points in both directions. An alternative standard-form convention uses $Az=b,z\ge 0$: add a nonnegative slack variable to each upper-bound row, or subtract a nonnegative surplus variable from a lower-bound row. The inequality convention above is used in the remaining solutions.

For a connected graph with at least one edge, run depth-first search and output the set $I$ of internal vertices of a rooted tree in its discovery tree $T$. Part (d) proves that $I$ is a vertex cover. It is also connected: every ancestor of an internal vertex is internal, so the graph path in $T$ from that vertex to the root stays inside $I$. The root is internal when $|V|\ge 2$.

For the approximation guarantee, choose a maximum-size proper matching in a rooted tree $M$ of $T$, whose existence is supplied. It is used only in the analysis; the algorithm need not construct it. Since every matched edge uses two distinct vertices,By part (e), $|L(T)|\ge |U(M)|$. ThereforeThe final inequality holds because every vertex cover of $G$, connected or otherwise, must use at least one distinct endpoint for each of the disjoint edges in $M\subseteq E(G)$. Thus this is a 2-approximation algorithm in $O(|V|+|E|)$ time complexity.

For completeness, a disconnected input needs a feasibility check: if two different connected components of a graph contain edges, no connected vertex cover can meet both. If exactly one component contains edges, run the construction on that component and ignore isolated vertices. If there are no edges, the empty vertex cover is optimal when an empty solution is permitted; if a nonempty connected solution is required, any single vertex is optimal for a nonempty input. These conventions cover the boundary cases omitted from the main approximation argument.