Put $S_1={\sum }_i{Y}_i$, $S_2={\sum }_i{Y}_i^2$ and $R=\sqrt{S_2}$. Apart from a data-only constant, the log-likelihood isThe natural parameters in the ambient two-parameter exponential family of normal distributions are ${\eta }_1=1/\mu$ and ${\eta }_2=-1/(2{\mu }^2)$, restricted to the nonaffine curve ${\eta }_2=-{\eta }_1^2/2$, ${\eta }_1>0$. Its parametrization has rank one. Thus this is a one-dimensional curved exponential family inside a two-dimensional full family.

The Fisher-Neyman factorization theorem makes $(S_1,S_2)$ sufficient. For two samples $y,z$, the parameter-dependent part of their log density ratio is $\Delta S_1/\mu -\Delta S_2/(2{\mu }^2)$. A polynomial in $1/\mu$ is constant on $(0,\infty )$ only if both nonconstant coefficients vanish. The likelihood-ratio criterion for minimal sufficiency therefore proves $(S_1,S_2)$ is minimal sufficient.

Write $Y_i=\mu Z_i$ with independent $Z_i\sim N(1,1)$. Since $\mu >0$, $a=\sqrt{n}\sqrt{{\sum }_i{Z}_i^2}/{\sum }_i{Z}_i$ has a probability distribution independent of $\mu$: it is an ancillary statistic. The denominator is nonzero almost surely. The Cauchy-Schwarz inequality gives $|a|\ge 1$; on the requested positive branch, $S_1>0$ and $a\ge 1$.

The likelihood equation is $n{\mu }^2+S_1\mu -S_2=0$. Its positive root isThere is exactly one positive root. The sign of the score function changes from positive to negative there, and $\ell \to -\infty$ at both ends of $(0,\infty )$ when $S_2>0$, so it is the unique maximum-likelihood estimator. The useful identities areSubstitution yields, dropping the constant $-n/2$,Differentiating twice and using $q/a=q^2-1$ at the fitted value gives the observed informationThe scalar P-star approximation uses $\sqrt{j(v)}\exp \{\ell (\mu ;v,a)-\ell (v;v,a)\}$. Consequently, with its normalizing factor explicitly retained,Here $C_n(a)$ is chosen to make the density integrate to one, and is independent of $\mu$. To see this without assuming an approximate normalizer, defineThe integral is finite and positive, and normalized $p^{\ast }$ is exactlyIndeed $C_n(a)=\{\sqrt{n(1+q^2)/(2\pi )}\exp [n{q}^2/2-nq/a]J_n(a){\}}^{-1}$.

There is a direct check of this conditional scale density in a curved Gaussian family. In polar coordinates $y=Ru$, the sample density times volume element is proportional to ${\mu }^{-n}{R}^{n-1}\exp [-R^2/(2{\mu }^2)+R{\sum }_i{u}_i/\mu ]dRd\omega (u)$. Conditioning on $a$ fixes ${\sum }_i{u}_i=\sqrt{n}/a$. The remaining angular factor is independent of $R,\mu$, while $R=q\sqrt{n}v$. Thus the exact conditional radial density has the same normalized form. For $n=1$ the positive ancillary branch fixes the positive sign and the same one-dimensional radial calculation applies. In this scale model the normalized $p^{\ast }$ expression equals the exact conditional density, not merely its leading approximation.

For $t>0$, compute its conditional distribution by one-dimensional quadrature:It is zero for $t\le 0$; with the conditional-density calculation just given, this normalized formula is exact for almost every admissible $a$. Numerically, subtract the maximum log integrand before exponentiating to avoid overflow. The sampling probability still depends on the stipulated true $\mu$; replacing it by a fitted value would be a separate plug-in inference step.

A transformation model consists of a group $G$ acting measurably and invertibly on the sample space, an induced group action on the parameter space, and a family $\{P_{\theta }\}$ satisfying $Y\sim P_{\theta }\Rightarrow gY\sim P_{g\theta }$. In a generated, transitive model, every $P_{\theta }$ is the image of a reference distribution under some transformation. In the density formulation, the transformed density includes the appropriate sample-space Jacobian determinant; the model is a statement about whole probability laws, not merely about changing parameter names.

A maximal invariant $A$ has two properties: $A(gy)=A(y)$ for every $g$, and $A(y)=A(z)$ implies $z=gy$ for some $g$. It is therefore a coordinate for the group orbits, retaining exactly the information unaffected by the transformations. An equivariant estimator obeys $T(gy)=gT(y)$, where the right action is the induced parameter action.

For the normalization construction, suppose the estimator determines a group element $t(y)\in G$ with $t(gy)=gt(y)$. Define $A(y)=t(y{)}^{-1}y$. ThenIf $A(y)=A(z)$, rearranging gives $z=t(z)t(y{)}^{-1}y$. This is an actual transformation in $G$, so the normalized sample is a maximal invariant. This group-valued assumption matters: an estimator of a parameter with a nontrivial stabilizer does not necessarily determine a unique normalization. For a transitive parameter space $G/H$, choose a transformation carrying the estimated parameter to the reference value and take the resulting normalized sample modulo the remaining $H$-action. Different choices then have the same residual orbit. Under a free action $H$ is trivial and the simpler formula applies.

For a location-scale model, $g_{a,b}(y_1,\dots ,y_n)=(a+b{y}_1,\dots ,a+b{y}_n)$, $b>0$, with composition $(a,b)(c,d)=(a+bc,bd)$. Its parameter action is $(\mu ,\sigma )\mapsto (a+b\mu ,b\sigma )$. Choose location and scale estimates satisfyingFor instance, on nonconstant samples take the sample mean and the positive square root of $n^{-1}{\sum }_i(y_i-\bar{y}{)}^2$. The standardized vectoris invariant. Conversely, equality of these vectors gives $z_i=c+d{y}_i$ for all $i$, with $d=\hat{s}(z)/\hat{s}(y)>0$ and $c=\hat{m}(z)-d\hat{m}(y)$. Hence it is maximal, not just invariant. Degenerate constant samples have zero fitted scale and form a separate orbit; define a separate invariant value there. The construction is on labelled sample vectors: one must not discard their order unless permutations are also included in the transformation group.

The profile likelihood for the parameter of interest replaces the nuisance parameter by its constrained best fit: $L_p(\psi )={\sup }_{\lambda }L(\psi ,\lambda )$, with ${\ell }_p(\psi )=\ell (\psi ,{\hat{\lambda }}_{\psi })$. It is not in general a normalized sampling density. A conditional likelihood instead uses the sampling law conditional on a statistic carrying the nuisance dependence. In the canonical exponential family here, conditioning on $S$ removes $\lambda$ because the factor involving $\lambda$ is constant over the conditioning fibre.

Let ${\bar{T}}_1=n^{-1}{\sum }_i{\tau }_1(y_i)$ and let the observed $S$ equal $s$. For the cumulant-generating function of ${\tau }_2(Y)$ at fixed $\psi$,The saddlepoint solves $K^{\prime }(\hat{t})=s$, equivalently $d_{\lambda }(\psi ,{\hat{\lambda }}_{\psi })=s$ with ${\hat{\lambda }}_{\psi }=\lambda +\hat{t}$. This is also the constrained likelihood equation, since ${\ell }_{\lambda }=n(s-d_{\lambda })$. Assume an interior saddle, $d_{\lambda \lambda }>0$, and the usual smooth nonlattice conditions under which $S$ has a density. Exponential tilting to ${\hat{\lambda }}_{\psi }$ makes $s$ the tilted mean. A local normal approximation gives tilted density $\{n/(2\pi d_{\lambda \lambda }(\psi ,{\hat{\lambda }}_{\psi })){\}}^{1/2}$ at that mean; undoing the tilt gives the saddlepoint density approximationThe factor $n^{1/2}$ is for the sample mean, rather than the sum. A transform-based derivation gives the same expression by expanding $K$ to second order at its stationary point.

The joint log-likelihood is $n\psi {\bar{T}}_1+n\lambda s-nd(\psi ,\lambda )-{\sum }_{i}Q(y_i)$. Subtracting $\log {\hat{f}}_S(s;\psi ,\lambda )$ cancels every appearance of the original $\lambda$, leavingAny change from the ambient density to a conditional density on $S=s$ contributes only a data-dependent Jacobian determinant. Thus, up to a constant independent of $\psi$, the saddlepoint conditional likelihood adjustment isEquivalently $B=\frac{1}{2}\log j_{\lambda \lambda }(\psi ,{\hat{\lambda }}_{\psi })$ up to the constant $-\frac{1}{2}\log n$, where $j_{\lambda \lambda }=n{d}_{\lambda \lambda }$ is the nuisance observed information. The adjustment has a positive sign. The printed exponential-family form alone does not guarantee a density for $S$: for example a continuous $Y$ can have ${\tau }_2(Y)=1_{\{Y>0\}}$. In a lattice case one must approximate the probability mass of the sum instead; the displayed density calculation uses the regular continuous interpretation.

read.table(...,header=T) reads four grouped rows with column names. The displayed outcome counts give the observed risks $0.1519,0.2145,0.2611,0.5111$ in the indicated factor order. rbind in the first test pools over predisposition: the two rows represent no cannabis use and some use, with event/non-event counts $(341,1775)$ and $(82,238)$. Thus the pooled risks are $341/2116=0.1612$ and $82/320=0.2563$. This test concerns the marginal statistical association between use and outcome, not an association adjusted for predisposition.

Under independence, expected counts in the two-by-two contingency table are $E_{ij}=O_{i+}{O}_{+j}/N$. The ordinary Pearson chi-squared statistic is $17.5183$. The printed $16.8618$ is reproduced by the default two-by-two Yates continuity correction:All absolute differences here exceed one half. Comparison with a chi-squared distribution on one statistical degree of freedom gives $p=4.02\times 10^{-5}$. There is strong evidence of marginal association. The simplified output omits the usual continuity-correction wording, but its numerical value shows which statistic was used.

attach makes the data columns available by name, and tot=with+without obtains group sizes $1936,275,180,45$. The grouped binomial regression fits $Y_g\sim \mathrm{Bin}(n_g,{\pi }_g)$, with response $Y_g/n_g$ and prior weights $n_g$. These weights tell R the binomial denominator; treating the four proportions as four equally precise individual observations would be wrong. The default logit link isLet $A$ indicate some use and $B$ indicate predisposition. The additive logistic regression specifies $\eta =a+bA+cB$. Its log-likelihood, including the binomial constants, isDifferentiation gives score equations $X^T(Y-n\pi )=0$ and Fisher information matrix $X^{T}WX$, where $W_{gg}=n_g{\pi }_g(1-{\pi }_g)$. Fisher scoring solves these equations, and the inverse fitted Fisher information matrix gives the reported approximate coefficient variances. The number of scoring iterations records numerical convergence, not degrees of freedom or statistical evidence.

The intercept corresponds to no use and no predisposition and gives baseline fitted risk ${\mathrm{logit}}^{-1}(-1.73881)=0.1495$. The additive coefficients imply common adjusted odds ratios:They multiply the odds, not the risks. The Wald tests divide the estimates by their standard errors and use a standard normal distribution; both predictors have small two-sided p-values. Approximate $95\%$ confidence intervals for these odds ratios are $(1.296,2.266)$ and $(1.685,3.110)$, obtained by exponentiating the log-scale intervals. The intercept test against zero asks whether the reference risk equals one half, and is not a test of either exposure association. The binomial dispersion is assumed to be one because $\mathrm{Var}(Y_g)=n_g{\pi }_g(1-{\pi }_g)$; the output does not demonstrate independence or rule out extra-binomial variation.

There are four grouped probabilities and three fitted coefficients, leaving one residual degree of freedom. The fitted risks are approximately $(0.1495,0.2314,0.2869,0.4080)$. The binomial deviance compares this fit with the four unrestricted observed proportions:The deviance goodness-of-fit test against ${\chi }_1^2$ has p-value $0.0796$. The common-odds-ratio fit is not rejected at $5\%$, although the doubly exposed group's observed risk exceeds its fitted risk appreciably and suggests possible interaction.

The second formula adds $\delta AB$. Its four coefficients fit all four probabilities, making a saturated statistical model with zero grouped residual degrees of freedom. The near-zero deviance is roundoff from exact interpolation; it supplies no remaining grouped lack-of-fit test. Unlike Q1's unreplicated Gaussian fit, however, these grouped responses represent many independent Bernoulli trials, and their binomial variances are specified by their sizes and probabilities. Coefficient standard errors remain available from binomial information without estimating dispersion from the zero residual degrees of freedom.

Indeed, let ${\eta }_{ab}=\log [Y_{ab}/(n_{ab}-Y_{ab})]$ be the fitted cell logit link value. The saturated coefficients areThese calculations yield the printed estimates. The delta method gives $\mathrm{Var}({\hat{\eta }}_{ab})\approx 1/Y_{ab}+1/(n_{ab}-Y_{ab})$, and independent groups make the variance of $\hat{\delta }$ the sum of all eight reciprocal counts. Its square root is $0.37857$, reproducing the printed standard error.

The saturated logistic regression describes the conditional odds ratios as follows:Thus the main coefficients now concern effects at the other factor's reference level. Logistic interaction as a ratio of odds ratios gives $e^{\delta }=1.939$, with approximate $95\%$ confidence interval $(0.923,4.073)$. The interaction Wald test has $p=0.0802$, while the nested likelihood-ratio test uses deviance difference $3.0733$ on one statistical degree of freedom and has $p=0.0796$. The data suggest a larger odds association in predisposed subjects, but do not establish this interaction at the conventional $5\%$ level. This conclusion is specific to the odds scale; absolute-risk differences can vary even with no logit-scale interaction.

The Akaike information criterion is $-2\hat{\ell }+2k$. The additive fit has $k=3$ and AIC $31.766$; the interaction fit has $k=4$ and AIC $30.692$. The extra coefficient improves twice the log-likelihood by $3.0733$ but incurs penalty $2$, so AIC falls by only $1.0733$. It weakly favors the larger fit rather than decisively establishing an interaction, and AIC is not a p-value.

The marginal odds ratio $1.793$ and the fitted conditional odds ratios are different quantities. Predisposition is associated with both use frequency and outcome, so confounding is a substantive possibility; noncollapsibility of the odds ratio also means marginal and conditional odds ratios need not agree. This is an observational association analysis with only one adjustment factor. It does not by itself establish a causal effect, exclude other confounding, or validate the assumed independent binomial sampling.

scan reads the numerical prices, including the three missing-value markers, into a vector. The data must be read row by row for the subsequent factor construction to match them. The sample size available for analysis is therefore $37$, rather than $40$. The numerical summary describes the observed prices: the sample median is £43.54 and the sample mean is £46.94. The upper tail, particularly the boots, raises the sample mean above the sample median. These summaries mix very different products and are not adjusted country comparisons.

The two character scans create labels. gl(8,5,length=40,labels=item) makes a regression factor with each of eight item labels repeated five times. gl(5,1,length=40,labels=country) cycles through the five country labels once for each item. For a regression factor and numerical response, the two plot commands produce grouped box plots. The country box plots suggest lower US prices, while the item box plots show particularly expensive boots and inexpensive cardigans. They are descriptive displays of this small basket, with different item compositions where prices are missing; they cannot separate country effects from item effects.

The first lm fits an additive two-way analysis of variance:The constraints are R's usual treatment coding. The normal linear model used for the printed tests assumes independent errors with common variance and approximately a normal distribution, and no item-by-country interaction in the mean. Missing prices are omitted, leaving $37$ responses and $1+4+7=12$ independent mean coefficients. Thus the residual degrees of freedom are $37-12=25$. This deletion is defensible for the conditional price model when missingness does not depend on the unobserved error after conditioning on the two factors; the output itself does not establish such a missing-data mechanism.

The anova tables report sequential sums of squares, rather than order-independent adjusted effects. If $R_0,R_C,R_I,R_{CI}$ are the residual sums of squares from the intercept-only, country-only, item-only and additive fits, the first order allocates $R_0-R_C$ to country and $R_C-R_{CI}$ to item. The second order allocates $R_0-R_I$ to item and $R_I-R_{CI}$ to country. Both allocations sum to the same total explained sum of squares, and both end with the same residual sum of squares $659.4$. The three missing combinations destroy balanced factorial orthogonality, so the allocation changes with order. To test country after allowing for items, use the country row in the second table; to test item after allowing for countries, use the item row in the first table. The first-entered rows do not supply those adjusted tests.

Each mean square in ANOVA divides its sum of squares in ANOVA by its statistical degrees of freedom, and each printed F-statistic divides that mean square in ANOVA by $659.4/25=26.38$. In particular, the adjusted country partial F-test haswith an $F_{4,25}$ reference F-distribution and p-value approximately $1.86\times 10^{-6}$. The adjusted item partial F-test gives $F=91.58$ on $7,25$ statistical degrees of freedom. Both factors contribute strongly under the additive normal linear model. The larger item sum of squares in ANOVA measures the much greater differences between these products, but is not evidence that every pair of items differs significantly.

The intercept $50.799$ is the fitted UK price for the reference jeans, not their observed price and not the overall sample mean. Each country regression coefficient is its adjusted price difference from the UK, assumed common across items: Sweden is £5.224 lower, France £10.708 lower, Germany £7.676 lower and the US £21.328 lower. Each item regression coefficient is its adjusted difference from the reference jeans, assumed common across countries. Thus the fitted UK boots price is $50.799+52.854=103.653$, and the fitted US boots price is $103.653-21.328=82.325$.

The coefficient standard errors come from $s^2(X^{T}X{)}^{-1}$, where $s^2=659.4/25$ and $X$ is the design matrix. Dividing each estimate by its standard error gives the displayed Student t-test statistic, with $25$ statistical degrees of freedom. The stars summarize the corresponding two-sided p-values. The individual tests compare each indicated country or item with its reference level, conditional on all other additive terms; they are neither tests of every pairwise comparison nor a simultaneous confidence interval procedure. In particular, Sweden's p-value $0.0626$ provides weaker evidence than the other country contrasts, and does not establish equality with the UK. The intercept test has little substantive relevance, and interpreting many individual stars also raises multiple hypothesis testing issues.

The residual standard error $s=5.136$ measures unexplained prices in pounds. With total corrected sum of squares $T$, the coefficient of determination and adjusted coefficient of determination areMuch of this impressive fit is due to the large differences between items. The overall F-test compares the additive fit with a constant mean: $F=((T-659.4)/11)/(659.4/25)=62.12$ on $11,25$ statistical degrees of freedom. It tests that all eleven non-intercept coefficients vanish, not that the additive model is adequate. Regression diagnostics should examine regression residuals, changing price variability across items and possible interaction. Percentage differences may be more plausible than common pound differences, motivating a natural logarithm of price. No random sample of countries or products, and no independent replication of a price within a cell, is supplied; broad claims about all designer goods or the causes of country differences require more than these conditional tests.

Finally, Item*Country expands to both main effects and their full interaction. A cell-means parameterization has one separate fitted mean for every observed cell. With one response per cell its design matrix has row matrix rank $37$, while the full $8\times 5$ layout nominally has $40$ coefficients. Three coefficient combinations are aliased because their cells are missing. This is saturation of an unreplicated two-factor regression: every observed price is fitted exactly and the residual degrees of freedom are zero. The final fit has zero residuals, $R^2=1$ and no residual-based estimate of the error variance or ordinary interaction significance test. The printed numerical summary will mark three coefficients unestimable; coefficient standard errors, tests and adjusted $R^2$ involve undefined division by zero, potentially appearing as NaN or Inf according to numerical roundoff. Perfect interpolation here is a consequence of a saturated statistical model, not evidence for a superior predictive model.

In a second-price sealed-bid auction, fix the other players' bids and let $a$ be their highest bid. A player of valuation $v$ who wins pays $a$, obtaining quasilinear utility $v-a$; losing gives zero. If $v>a$, winning is optimal and bidding $v$ wins. If $v<a$, losing is optimal and bidding $v$ loses. If $v=a$, winning and losing both give zero, regardless of the fixed tie-breaking rule. Thus truthful bidding is a dominant strategy. In particular the profile in which every bidder bids its valuation is a Nash equilibrium, for every valuation profile, not merely on average.

A symmetric independent private values model gives each bidder a private valuation determined by its own type. The types are independent draws from a common distribution, and the bidders have identical roles and preferences. In the standard bidding calculation bidders are risk-neutral with quasilinear utility: they maximize expected valuation minus payment. Strategies map each bidder's privately observed value to a bid. Equilibrium in this incomplete-information setting means a Bayesian Nash equilibrium.

Take $n\ge 2$ with independent uniform values on $[0,1]$. In a first-price sealed-bid auction, if all players bid their valuations, a type $v$ earns zero whenever it wins and zero whenever it loses. But for $v>0$, bidding $v/2$ instead yields positive expected utilityTherefore truthful first-price bidding is not an equilibrium.

For the candidate uniform private-value first-price bidding equilibrium, put $\alpha =(n-1)/n$ and suppose every opponent bids $\alpha$ times its valuation. For a deviation $b\in [0,\alpha ]$, winning means that every opposing value is less than $b/\alpha$. Independence gives winning probability $(b/\alpha {)}^{n-1}$, so the type-$v$ expected utility isFor $b>0$ its derivative isFor $v>0$ it is positive before $b=\alpha v$ and negative after; for $v=0$, every positive bid has nonpositive utility and zero is optimal. Thus the maximum on $[0,\alpha ]$ is $b=\alpha v$. A bid above $\alpha$ wins with probability one but gives $v-b\le v-\alpha$, which is no better than the already considered endpoint $b=\alpha$, hence no better than $b=\alpha v$. Ties have probability zero under the continuous opposing distributions. All admissible deviations are therefore covered.

Each bidder's best response is the proposed rule, provingIts conditional expected utility is $u(v,\alpha v)=v^n/n$. With only one bidder, bidding zero is optimal and agrees with the same formal rule; the derivative argument is needed only for $n\ge 2$.

Label the two intermediate vertices $1,2$. The four outer edges have capacity $M$ and the middle edge has capacity one. The cut separating $s$ from the other vertices has capacity $2M$, and the two paths $s\to 1\to t$ and $s\to 2\to t$ can each carry $M$. Thus the maximum flow is $2M$.

A fast run of the Ford-Fulkerson algorithm chooses those two direct paths and augments by $M$ on each: it terminates in two augmentations. One augmentation cannot suffice, because every initial path has bottleneck at most $M$.

For a run with $M+1$ augmentations, first choose $s\to 1\to 2\to t$ and augment by one. The middle edge then has net flow $1$ from $1$ to $2$. Its reverse residual capacity is $1-(-1)=2$, not one. Alternate crossing paths, next $s\to 2\to 1\to t$, then $s\to 1\to 2\to t$, and so on. Each of the next $M-1$ augmentations has bottleneck two. More explicitly, after $k$ crossing augmentations, $1\le k\le M$, the total flow is $2k-1$, and the outer-edge flow totals on the pairs $(s1,2t)$ and $(s2,1t)$ are $k$ and $k-1$ in one order or the other. The middle net flow is $\pm 1$. The next opposite crossing path uses the less-loaded outer pair and has reverse-middle capacity two. Until $k=M$, its outer residual capacities are at least two.

After these $M$ augmentations, one outer pair is full and the other has one unit left. One final opposite crossing augmentation of one reaches $2M$. The total amounts are $1$, then $M-1$ copies of $2$, then $1$, giving exactly $M+1$ augmentations. For $M=1$ the middle block is empty and this gives two augmentations as well. These are explicit requested path-choice histories. In an undirected network, $M+1$ need not be a bound on every possible history: for $M=2$, choosing the crossing path, the two direct paths, and then the crossing path again gives four successive unit augmentations.

For a general undirected network, let $y_{ij}=x_{ij}-x_{ji}$ be the antisymmetric net flow. Feasibility gives $|y_{ij}|\le c_{ij}$, so the directed residual network has nonnegative capacities $c_{ij}^{\prime }=c_{ij}-y_{ij}$. For any cut $S$ with $s\in S$, $t\notin S$, conservation at the internal vertices givesThus its outgoing residual cut capacity isThe subtracted flow value is the same for every cut. Taking the minimum and applying the max-flow min-cut theorem to the original and residual networks proves the residual maximum flow is the remaining optimality gap identity

Suppose now $f^{\prime }>0$, and let $U$ consist of vertices reachable from $s$ through residual arcs of capacity at least $f^{\prime }/m$. If $t\notin U$, every outgoing arc from $U$ has capacity strictly below $f^{\prime }/m$, since its head would otherwise be reachable. At most $m$ original undirected edges cross this cut, and each supplies exactly one outgoing directed arc. Hence $C^{\prime }(U)<m(f^{\prime }/m)=f^{\prime }$, contradicting the residual minimum-cut value $f^{\prime }$. Therefore $\boxed{t\in U}$, and a widest augmenting path has bottleneck at least $f^{\prime }/m$. When $f^{\prime }=0$, the current flow is already optimal and no such path is needed.

Let $F_k$ be the remaining residual maximum flow after $k$ augmentations of the modified rule, starting from zero flow. Its chosen widest path increases the flow by at least $F_k/m$, soThis is the geometric convergence of widest-path augmentation. For $m\ge 2$, $F_k\le e^{-k/m}{f}^{\ast }$. Starting from zero with integer capacities keeps all flow values and residual optimality gaps integer. Thus $k>m\ln f^{\ast }$ makes $F_k<1$ and hence $F_k=0$, giving termination in $\boxed{O(m\log f^{\ast })}$ augmentations for $f^{\ast }\ge 2$. If $f^{\ast }=1$, one positive integer augmentation suffices; if $f^{\ast }=0$, none is required. A uniform statement is $O(m\log (1+f^{\ast }))$. With $m=1$, a nonzero flow is also completed in one augmentation, consistent with the recurrence's zero contraction factor.

Let $v:2^N\to \mathbb{R}$, $v(\varnothing )=0$, be a coalitional game with $n=|N|$. The Shapley value isEquivalently, choose a uniformly random player ordering and average each player's marginal contribution when that player joins its predecessors. The coefficient counts precisely the orderings with predecessor set $S$.

The standard axioms are efficiency, ${\sum }_i{\varphi }_i=v(N)$; symmetry, giving equal values to players with identical marginal contributions; the dummy-player property, giving ${\varphi }_i=v(\{i\})$ if every marginal contribution of $i$ equals $v(\{i\})$; and additivity, ${\varphi }_i(v+w)={\varphi }_i(v)+{\varphi }_i(w)$. The null-player form of the dummy axiom gives zero to a player contributing nothing. These properties characterize the Shapley value. They also follow directly from its formula: efficiency telescopes along each ordering, symmetry relabels orderings, constant dummy contributions average to themselves, and the sum is linear in $v$.

For balanced contributions of Shapley values, remove player $j$ from a uniformly random ordering. The resulting ordering of $N\setminus \{j\}$ is uniform, so it computes $i$'s Shapley value in the restricted game. If $j$ comes after $i$, removing it does not change $i$'s marginal contribution. If $j$ precedes $i$, and $S$ consists of $i$'s other predecessors, the difference isThere are $(|S|+1)!(n-|S|-2)!$ full orderings with exactly $S\cup \{j\}$ before $i$. ConsequentlyBoth the summand and coefficient are unchanged when $i,j$ are interchanged. ThusThe restriction keeps all coalition values for the remaining players, exactly matching the payoff comparison after a departure. The identity does not require the differences to be positive.

Now consider the coverage coalitional game formed by the finite book sets. For disjoint coalitions $S,T$, put $B(S)={\bigcup }_{i\in S}{B}_i$. ThenThus coverage is generally subadditive. It is a superadditive coalitional game precisely when the book sets are pairwise disjoint: disjointness makes the displayed formula additive, while a common book of players $i,j$ gives $v(\{i,j\})<v(\{i\})+v(\{j\})$. For example, $B_1=B_2=\{b\}$ gives values $1,1,1$ and disproves unconditional superadditivity. The printed clause must therefore have its disjointness condition apply to superadditivity as well as to core nonemptiness.

For the core of a coverage game, an allocation must satisfy efficiency ${\sum }_i{x}_i=v(N)$ and ${\sum }_{i\in S}{x}_i\ge v(S)$ for every coalition. In particular $x_i\ge |B_i|$. Summing givesThe reverse inequality always holds, with equality exactly when no book appears in two sets. Therefore overlap makes the core empty. If the sets are disjoint, $x_i=|B_i|$ gives every coalition exactly its value and is a core allocation; the singleton lower bounds and efficiency make it the only one. Hence superadditivity and a nonempty core each occur exactly in the pairwise-disjoint case.

Finally write the game as a sum over individual books. For a book $b$, let $K_b=\{k:b\in B_k\}$. Its contribution to coalition value is one if the coalition meets $K_b$, and zero otherwise. In a random ordering, player $i$ contributes this book precisely when $i\in K_b$ and is earliest among its $|K_b|$ knowers. Each knower is equally likely to be earliest. Additivity of the Shapley value therefore gives the Shapley value of a coverage gameThis formula remains valid when books overlap and the core is empty.

For a finite bimatrix game, let $A,B\in {\mathbb{R}}^{r\times s}$ be the two players' payoff matrices. A pair of mixed strategies $(p,q)\in {\Delta }_r\times {\Delta }_s$ is a Nash equilibrium ifHere ${\Delta }_r$ is the probability simplex on the first player's pure actions, and similarly for ${\Delta }_s$. The two payoff matrices need not be negatives of each other. Nash's theorem asserts that every finite two-person game has an equilibrium in mixed strategies.

We prove it using the Brouwer gain-map proof of bimatrix equilibrium. Put $u=p^{T}Aq$, $v=p^{T}Bq$ and define the positive pure-deviation gainsWrite $G={\sum }_i{g}_i$, $H={\sum }_j{h}_j$ and defineEvery coordinate is nonnegative and each player's coordinates sum to one. The map is continuous, since the payoffs and positive-part function are continuous and both denominators are at least one. Thus $T$ is a continuous self-map of the nonempty compact convex set ${\Delta }_r\times {\Delta }_s$. The Brouwer fixed-point theorem supplies a fixed point $(p,q)$.

At that fixed point the first coordinate equations give $g_i=G{p}_i$. Suppose $G>0$. For every $i$ with $p_i>0$, this makes $g_i>0$, so $(Aq{)}_i-u=g_i=G{p}_i$. But averaging the payoff excess over the support givesa contradiction. Therefore $G=0$, and every $g_i$ is zero. Each pure action has payoff at most $u$, so every mixed deviation, being a convex combination of pure actions, has payoff at most $u$ too. The same argument for $h_j=H{q}_j$ gives $H=0$ and excludes every unilateral deviation by the second player. The fixed point is therefore a Nash equilibrium, proving the stated theorem without a zero-sum assumption.

Assume $n\ge 1$ and the integer coefficient bound $U\ge 1$. There are $m(n+1)$ integers to record. Each signed integer in $[-U,U]$ can be encoded in $\lceil {\log }_2(2U+1)\rceil$ bits, so a fixed-width dense encoding needsbits, including the dimensions and bound. Its size is $\boxed{O(mn\log (U+1))}$. This is the bit-input model used for polynomial time; an arithmetic-operation count alone would not suffice.

We first construct a rational feasibility certificate for integer inequalities. Choose a feasible point and an orthant containing it, adding coordinate inequalities of the form $x_i\ge 0$ or $-x_i\ge 0$. The intersection $Q$ is nonempty. Starting at a point of $Q$, if the active constraint normals have rank less than $n$, choose a nonzero direction $d$ annihilating them. A sufficiently short move in either direction remains feasible, since every inactive constraint has positive slack. At least one direction has a finite endpoint: a nonzero coordinate of $d$ can be oriented toward the orthant boundary. Move to the first constraint met along such a direction. Its normal does not annihilate $d$, so it is independent of the previously active normals. Their rank strictly increases. In at most $n$ moves we obtain a point with $n$ independent active constraints.

At that point $Bx=d_0$ for an invertible integer $n\times n$ matrix $B$. Its rows are original constraint rows or signed coordinate rows, and $d_0$ has entries from $b$ or zero. All entries have absolute value at most $U$. By Cramer's rule,where $B_i$ replaces column $i$ by $d_0$. The Hadamard determinant inequality bounds both determinants by $(\sqrt{n}U{)}^n\le (nU{)}^n$. The denominator is a nonzero integer. Hence each coordinate has the claimed representation with numerator and denominator bounded in absolute value by $R=(nU{)}^n$. The orthant argument is needed because $P$ itself may contain lines and have no vertex. If $U=0$ is allowed literally, all coefficients and right sides vanish, and $x=0$ is feasible; the printed fraction bound then needs $U$ replaced by $\max (1,U)$, since a nonzero denominator cannot have absolute value at most zero. The bound just proved uses the customary positive coefficient bound.

Recording $n$ such fractions takes $O(n^2\log (nU))$ bits. A verifier checks that denominators are nonzero, changes their signs if needed, and verifies all inequalities by exact integer arithmetic after multiplying by positive denominators. The intermediate integers still have polynomial bit length. Thus a yes-instance has a polynomial-size, polynomial-time verifiable witness, and $\boxed{\mathrm{FP}\in \mathbf{NP}}$.

For optimization, let $c$ be rational with a finite binary encoding; clear its denominators to make it integer, which multiplies the objective by a positive constant and preserves its minimizers. All bit bounds below include the encoding length of $c$. Let $V=\max (1,{\max }_i|c_i|)$ and $B_0=nVR$.

A useful refinement of the preceding vertex argument is that if an objective is bounded below, a feasible point can be moved to an orthant vertex without increasing its objective. Choose the annihilating direction to have $c^{T}d\le 0$. If the inequality is strict, the forward feasible interval must have a finite endpoint, since otherwise the objective would be unbounded below. If $c^{T}d=0$, choose either finite endpoint supplied by the orthant. Rank increases as before. There are only finitely many such vertices across the finitely many orthants. Every feasible point therefore has one of these vertices with no larger objective; taking the least vertex value proves that a finite optimum is attained at one of them.

The Cramer representations at this optimum have one common denominator $\det B$, of magnitude at most $R$. Therefore its objective value $z^{\ast }$ has a representation with denominator at most $R$ and numerator at most $B_0$. In particular $|z^{\ast }|\le B_0$. No enumeration of orthants or vertices is part of the algorithm; they provide only polynomial-bit bounds.

Here is an exact linear optimization from a feasibility oracle. First call the assumed ellipsoid method feasibility routine on $P$; if it is empty, report infeasibility. Otherwise query feasibility with the extra inequality $c^{T}x\le -B_0-1$. A yes answer proves unboundedness below, because any finite optimum would be at least $-B_0$; an unbounded objective necessarily gives a yes answer. Thus the infeasible, unbounded and finite-optimum cases are distinguished using two feasibility calls.

In the finite case, maintain an infeasible lower threshold $-B_0-1$ and a feasible upper threshold $B_0$. Bisect the interval, querying $c^{T}x\le t$ each time. After polynomially many calls its length is less than $1/(2R^2)$, and $z^{\ast }$ lies in the resulting interval. Distinct reduced fractions with positive denominators at most $R$ differ by at least $1/R^2$, so there is only one possible value. It can be recovered in polynomial time by continued fractions: for the midpoint $t$, $|z^{\ast }-t|<1/(4R^2)\le 1/(2q^2)$, where $q\le R$ is the denominator of $z^{\ast }$. Thus $z^{\ast }$ occurs among the continued-fraction convergents of $t$. Compute those by the Euclidean algorithm and choose the unique fraction with denominator at most $R$ in the interval. If $t=z^{\ast }$, use the final exact convergent. The Euclidean algorithm and all thresholds have polynomial bit length.

Even if the feasibility routine returns only a decision, an optimal point can be recovered without assuming a witness-producing oracle. Add $c^{T}x=z^{\ast }$ and $-R\le x_i\le R$ for all $i$. This bounded optimal convex polytope is nonempty, since the optimal vertex above lies in it. Clear the denominator of $z^{\ast }$ and setAll vertex coordinates of this fixed convex polytope have denominators at most $D_0$ by the same determinant argument. Minimize $x_1$, recover its exact minimum by feasibility bisection and rational reconstruction, then fix it; do the same for $x_2$, and so on. Each restriction is an optimal face of the same original bounded convex polytope, so its vertices are original vertices. The single denominator bound $D_0$ therefore works at every step; repeated new precision bounds do not grow exponentially. After $n$ steps all coordinates are fixed to a feasible optimizer. There are polynomially many calls on polynomial-length rational instances, converted to integer inequalities by clearing denominators. Consequently linear optimization has a polynomial-time algorithm whenever linear feasibility does, with exact optimal value and optimizer, and correct reports of infeasibility or unboundedness.

Introduce nonnegative slack variables $s_1,\dots ,s_4$ and write $z$ for the objective value. The initial simplex dictionary, recovered from the original PDF rather than the corrupted converted table, isFor this minimization convention, nonnegative objective coefficients give dual feasibility. The dual simplex algorithm repairs a negative basic value while retaining those nonnegative reduced costs. If the leaving row is $x_B=b+{\sum }_j{a}_j{x}_j$, $b<0$, an entering variable must have $a_j>0$; choose the smallest ratio of its objective coefficient to $a_j$.

Choose $s_1$ to leave. Eligible columns are $x_1,x_3$, with ratios $2/1=2$ and $18/6=3$. Thus $x_1$ enters. Solving its row and substituting givesNow only $s_3$ has a negative basic value. Its only eligible entering column is $x_3$, so pivot there, with $s_3$ leaving. The resulting dictionary isSetting the nonbasic variables $s_1,x_2,s_3$ to zero gives a basic feasible solution. The final objective row also proves $z\ge 23$ for every feasible point, because its nonbasic variables are nonnegative. Hence the unique relaxed optimum is