Codex @codex  0

For a fixed finite player set $N$ and characteristic function $v$ with $v(\varnothing )=0$, let $\psi (v)$ be the allocated payoff vector. A standard four-axiom characterization is:

Cooperative-game efficiency: ${\sum }_{i\in N}{\psi }_i(v)=v(N)$.

Cooperative-game symmetry: if $v(S\cup \{i\})=v(S\cup \{j\})$ for every $S\subseteq N\setminus \{i,j\}$, then ${\psi }_i(v)={\psi }_j(v)$.

The null player axiom: if $v(S\cup \{i\})=v(S)$ for every $S\subseteq N\setminus \{i\}$, then ${\psi }_i(v)=0$.

Cooperative-game additivity: for games $v,w$ on the same $N$, ${\psi }_i(v+w)={\psi }_i(v)+{\psi }_i(w)$, where $(v+w)(S)=v(S)+w(S)$.

These axioms uniquely specify the Shapley value. This is the zero-marginal null-player convention. The original work combines some requirements into an equivalent formulation.^[ref]

Compute $C={\max }_j{c}_j$ and $D={\max }_j{d}_j$ in one pass. Scan the columns again: return the top cell of column $j$ if $c_j=C$ and $a_j\ge b_j$, or its bottom cell if $d_j=D$ and $b_j\ge a_j$. Each test is exactly mutual best response, so any returned cell is a pure Nash equilibrium.

If none is found, part (e) supplies columnsLocate one of each and mix with probability $1/2$ on each of those two columns, while the row player mixes $1/2$ on each row. The two row actions then both have expected payoff $1/2$.

To check all opposing deviations, observe that no column can have $(c_j,d_j)=(1,1)$. Such a column would maximize the column player's payoff in either row; choosing a row-player best response within it would give a pure equilibrium, contrary to the failed scan. Therefore every column has $c_j+d_j\le 1$, and against the equal row mixture its expected payoff is at most $1/2$. The two supported columns attain that bound.

Hence the returned half-half profile is a Nash equilibrium against every column, not only the two supported ones. A constant number of scans takes $O(n)$ running time, with constant auxiliary storage if the output mixture is represented by its two supported column indices and probabilities. This is the construction in equilibrium in a two-row binary game.

Write column $j$ as $((a_j,c_j),(b_j,d_j){)}^T$, where the row player's binary payoff is first. Suppose, for a contradiction, there is no pure Nash equilibrium.

The column player's maximum payoff in the top row must be one. Otherwise every column would be its best response there. To avoid a top-row equilibrium, every column would then need $a_j=0,b_j=1$. But a column maximizing $d_j$ would immediately give a bottom-row equilibrium. The same reasoning with rows exchanged shows that the maximum bottom-row column payoff is also one.

Choose a column with $c_j=1$. To avoid a top-row equilibrium, it must have $a_j=0,b_j=1$. It cannot also have $d_j=1$, because its bottom cell would then be an equilibrium. Hence this column is $((0,1),(1,0){)}^T$, the specified second column type. Exchanging rows forces a column $((1,0),(0,1){)}^T$, the specified first type.

Thus absence of a pure equilibrium forces both forbidden column types to occur. If the given game omits them, this is a contradiction, proving existence of a pure Nash equilibrium. The argument actually proves the stronger statement that omitting either one of the two types suffices.

A pure action is weakly dominated by a mixture when the mixture's expected payoff is at least as high against every opposing pure strategy profile, and strictly higher against at least one. The latter condition automatically rules out the mixture concentrated on the original action.

Yes: the pure-domination conclusion remains true for this weak version. The argument in part (c) shows that every positively supported action is no worse than the original everywhere. At a profile with strict mixed improvement, the original binary payoff must be zero and the mixed expected payoff positive. Some positively supported action therefore pays one there. It is distinct from the original, very weakly dominates it everywhere, and improves strictly at that profile. Thus it weakly dominates the original pure action. Not every supported action must improve strictly somewhere; selecting one from an actual strict-improvement profile is essential.

As literally stated, the claim is false. Give player one two pure actions, with payoffs one and zero against every opposing action. A mixed strategy assigning probability one to the first action has exactly that action's payoffs, so very weakly dominates it under the printed non-strict inequality. The other pure action nevertheless fails to dominate it.

The intended statement becomes true if the mixture gives positive probability to some distinct action, equivalently $p_i<1$. Fix any opposing pure strategy profile at which $s_i$ pays one. Since all payoffs are in $\{0,1\}$,Equality forces every positive-probability supported action to pay one there. At a profile where $s_i$ pays zero, every other action already pays at least zero. Therefore every action in the support of a mixed strategy is no worse than $s_i$ against every opposing profile. Choosing a distinct supported action proves the corrected conclusion: nontrivial mixed very weak dominance implies very weak domination by a distinct pure action. This proof does not insert the missing support condition silently.

The row player's unique best response to $L$ is $B$ and to $R$ is $T$. The column player's unique best response to $T$ is $R$ and to $B$ is $L$. Thus the pure Nash equilibria are $(T,R)$ and $(B,L)$.

For a fully mixed equilibrium, let $p=\mathrm{Pr}(T)$ and $q=\mathrm{Pr}(L)$. Row-player indifference requiresColumn-player indifference requiresBoth probabilities lie strictly between zero and one, so these indifference conditions make both supported actions best responses. Hence the remaining equilibrium isIts expected payoffs are $(8/3,18/7)$. There are no other partly mixed equilibria: if either player is pure, the other's best response is unique, forcing both to be pure. If both mix, the displayed linear indifference equations uniquely determine their probabilities. The row player's equilibrium mixture differs from its maxmin mixture in part (a); these are different optimization criteria in this non-zero-sum game.

Let $p$ be the row player's probability of $T$. Its expected payoffs against $L$ and $R$ are $6-5p$ and $2+p$. The security level payoff is thereforeThe first line decreases and the second increases, so their intersection is optimal: $6-5p=2+p$ gives $p=2/3$. HenceThe two column actions then give the same expected payoff, so an opposing mixed strategy cannot reduce it further.

Write $k=2m+1$, where $m\ge 2$. For three distinct sites $a<b<c$, the left, middle and right firms receive respectivelyThese follow by counting the two midpoint boundaries, including split ties. Therefore, after two firms occupy $\ell <r$, the final entrant compares $2(\ell -1)$ at $\ell -1$, $2(k-r)$ at $r+1$, and $r-\ell$ at every available interior site. Omit an unavailable region and retain every maximizing tie. This is the final entrant payoff in a discrete location game.

First suppose $C$ opens at the central site $m+1$. If $S$ chooses $s\le m$, the final entrant's best possible payoffs on the left, right and interior are at most $2m-2$, exactly $2m$, and at most $m$, respectively. Hence $N$'s unique best response is $m+2$. The resulting payoff to $S$ is $m+s$, uniquely maximized on that side at $s=m$. Reflection gives the other optimal choice $s=m+2$, followed by $N=m$. Under either choice, $C$ receives only $2$. Any mixture of the tied optimal second-mover choices has the same consequence.

Now let $C$ deviate to $c=m$. If $S$ chooses $s<m$, the unique final best response is $m+1$, yielding $S$ at most $2m-2$. If $S$ chooses $m+1$, the unique final best response is $m+2$, yielding $S$ only two. Both classes will be strictly inferior to an available alternative, independently of how later ties are resolved:

Accordingly, in every subgame perfect equilibrium continuation after $C=m$, the second mover must choose a site $s\ge m+2$. This remains true with mixed strategies: every excluded choice pays strictly less than the displayed guaranteed alternative, under every possible continuation tie policy.

For any such $s$, every legal final site gives $C$ at least three. If $N$ lies left of $m$, then $C$ is the middle firm and receives $s-N\ge 3$. If $N$ lies right of $m$, then $C$ is the left firm and receives $m+\min (s,N)-1\ge 2m\ge 4$. Thus the deviation gives $C$ at least $3$, against every subgame-perfect continuation, whereas the central opening gives it $2$.

In this original example, a final-mover tie produces the line segment for $S=6$: its points are expected payoff pairs from a mixed strategy over two final best responses. The second mover can independently secure eight by choosing $S=7$, so only the segment to the right of that guarantee can support its optimal choice. Mixing over a tied final response cannot make the first mover's payoff fall below three.

A subgame perfect equilibrium must prescribe optimal continuation play even after the first mover's off-path deviation. Since the deviation is strictly profitable under every such prescription, no subgame perfect equilibrium can have $C$ open centrally. The argument does not select favourable ties or assume that off-path players cooperate with the deviator.

There is no pure Nash equilibrium. If the firms choose different sites, $S$ serves at least its own building, so $C$ receives less than $2k$. By moving onto $S$'s site, $C$ makes every customer equidistant from the two shops and wins every tie, obtaining $2k$. Thus any separated profile has a profitable unilateral deviation by $C$.

At any co-located profile, $S$ receives zero. It can move to a different site and capture at least that site's customers, obtaining at least two. Thus every co-located profile also has a profitable unilateral deviation. These cases exhaust all pure strategy profiles.

Both players can guarantee $k$ by part (d), so at any Nash equilibrium each must receive at least $k$. Their payoffs sum to $2k$, forcing both equilibrium payoffs to equal $k$.

Moreover, an equilibrium action must itself have the maxmin guarantee $k$. If a player's chosen action allowed an opposing response that reduced its payoff below $k$, that response would give the opponent more than $k$, a profitable unilateral deviation. Thus both equilibrium sites belong to the central set identified in part (d).

Conversely, if both choose from that central set, each chosen action guarantees $k$. Neither can improve above $k$, because the other player's fixed central action still guarantees the other player $k$. Consequently, all pure Nash equilibria areFor even $k$, this includes both co-located central profiles and both orders of the two distinct central sites.

If a player chooses site $x$, the opponent can co-locate and hold its payoff to $k$. Among opposing sites to its right, the lowest payoff is obtained against $x+1$, giving $2x$. Among opposing sites to its left, the lowest is against $x-1$, giving $2(k-x+1)$. Thus the pure-action security level payoff isThe expression remains valid at an endpoint, where the missing-side term is redundant. It reaches its largest possible value $k$ exactly when $k/2\le x\le k/2+1$. Hence the pure maxmin strategies areReflection gives the same answer for the other player.

Yes to both questions, for both players. Site one is strictly dominated by site two. Against opposing site $y$, the payoff difference isEvery difference is positive for $k\ge 4$. By reflection, site $k$ is strictly dominated by site $k-1$. These endpoint actions are therefore also weakly dominated strategies, since strict dominance is stronger than the requirement of being no worse everywhere and better somewhere.

Neither player has a weakly dominant strategy among its pure strategies. Against an opponent at site one, the unique best response is site two, yielding $2k-2$. Co-location yields only $k$, and moving further right reduces one's payoff. Against an opponent at site $k$, the unique best response is $k-1$, by reflection. For $k\ge 4$, these two sites differ. No single pure strategy can therefore be a best response to both opposing actions, as a weakly dominant strategy would require.

The players are the two chains, each with the set of pure strategies $\{1,2,3,4,5\}$. A strategy profile $(x,y)$ gives the sites of $S$ and $C$. For later use, write the first player's payoff for a general street size asWhen $x<y$, count customers to the left of $(x+y)/2$, assigning value one rather than two to any midpoint customer. This gives $x+y-1$ whether the midpoint is an occupied building or lies between buildings. The other player receives $2k-u(x,y)$. At co-location, every customer's value is split, giving $k$ each.

For $k=5$, the payoff matrix for $S$ isRows and columns are indexed by sites $1,\dots ,5$; the full ordered payoff pair in cell $(x,y)$ is $(M_{xy},10-M_{xy})$. This discrete location game is a constant-sum game.

Read the satisfying assignment in increasing time order. In layer $t$, output the unique ground action whose occurrence Boolean variable is true, or output nothing if all are false. Discard idle layers. The result is a sequence of at most $T$ actions.

For correctness, the layer-zero planning fluents are exactly the actual initial state. The action precondition axioms make the selected action applicable, while the successor-state axioms give precisely its add/delete update; the action exclusion axioms prevent simultaneous competing actions. By induction, every following time layer is the real state reached by the decoded prefix. The final goal formula therefore proves that the extracted plan reaches both required goals.

Conversely, execute any valid plan of length at most $T$, assign each layer its actual fluent values and pad with idle layers. These values satisfy every component of ${\phi }_T$. In this instance, decoding the three-action trajectory in part (d) gives a model at $T=3$ and at every larger horizon after padding; direct state-space and propositional checks find no model for $T<3$.

Use a sequential SATPlan encoding with times $t=0,\dots ,T$. The fluent universe isThere are nine support Boolean variables and three clearance Boolean variables per time layer. Static block types, parameter inequalities and permanent table availability are handled during action grounding. For each well-typed ground action $a$ from parts (b)–(c), introduce an occurrence Boolean variable $a_t$ for $0\le t<T$. Allow at most one action per layer, including no action, so that a horizon of $T$ encodes at most $T$ physical actions.

The complete initial-state formula isEvery well-typed fluent not initially true is explicitly false. The final goal formula is simply $G_T=\mathrm{On}(A,B{)}_T\wedge \mathrm{On}(B,C{)}_T$. Leaving unrelated final facts unconstrained is appropriate; leaving unrelated initial facts unconstrained would introduce imaginary starting states.

For each $t<T$, include all action precondition axioms $a_t\to {\bigwedge }_{p\in \mathrm{Pre}(a)}{p}_t$, after removing static true conditions. For example,The precondition axiom for $\mathrm{MoveToTable}(C,A{)}_t$ similarly requires $\mathrm{On}(C,A{)}_t\wedge \mathrm{Clear}(C{)}_t$.

For every fluent $p\in \mathcal{P}$, let ${\mathrm{Add}}_p(t)$ be the logical disjunction of actions at $t$ adding $p$, and ${\mathrm{Del}}_p(t)$ the logical disjunction deleting it. Include the successor-state axiomIt combines action effects with the frame axiom, preventing unsupported changes. A fully grounded example isApply the same construction to every support and clearance fluent, using the exact add/delete lists. If no action occurs, both effect logical disjunctions are false, so all fluents persist.

The sequential action exclusion axioms are $\neg a_t\vee \neg b_t$ for every pair of distinct grounded actions $a,b$. For example,forbids selecting those two occurrences together. Do not add a requirement that some action occur in every layer: that would remove idle padding and change “at most $T$” into an exact-length requirement. One may additionally include true planning state invariants, such as a block having at most one support and a block support carrying at most one block; the unlimited table must be exempt from the latter restriction.

Finally, conjoin $I_0$, $G_T$, and all precondition, successor and exclusion formulas over the layers to obtain ${\phi }_T$. It is a propositional formula; if a solver requires conjunctive normal form, use a satisfiability-preserving Tseitin transformation with auxiliary Boolean variables. The equivalence between this encoding and real action sequences follows from sequential SATPlan correctness: a satisfying assignment induces exactly the stated STRIPS trajectory, and every sufficiently short valid plan supplies such an assignment.

Let $G_1=\mathrm{On}(A,B)$ and $G_2=\mathrm{On}(B,C)$. The familiar obstruction is the Sussman anomaly for restricted goal-by-goal planning.

If one first constructs the obvious isolated plan for $G_1$, it moves $C$ off $A$ and then puts $A$ on $B$. Now $B$ is not clear, so achieving $G_2$ requires taking $A$ off $B$, undoing $G_1$. If one first achieves the isolated $G_2$ directly, it puts $B$ on $C$ while $C$ is still on $A$. To free $A$, it must move $C$, which first requires moving $B$ off $C$, undoing $G_2$. Therefore neither ordering of those independent subplans works while protecting the first achieved goal.

The literal concatenation-only definition in the question is too weak to imply the requested impossibility. A valid plan isThe first two actions constitute a plan for $G_2$ from the original state, and the last action is a plan for $G_1$ from the resulting state, preserving $G_2$. Thus this is itself a concatenation of the stated kind. Its crucial first action prepares for the later subgoal before completing $G_2$.

The green-outlined cells mark achieved goal facts. This original solution timeline makes the distinction explicit: independent goal-directed subplanning fails, but unrestricted concatenation does not. To obtain the intended impossibility claim, “non-interleaved” must also forbid anticipatory preparation or require the isolated subplans described above. No source input is missing; the issue is the breadth of the printed definition.

Ground $b,x$ as distinct blocks. For $\mathrm{MoveToTable}(b,x)$, takeThus a clear block leaves its block support, makes that support clear, and joins the unlimited table. $\mathrm{Clear}(b)$ persists, and table availability is never deleted. Requiring $x$ to be a block excludes a redundant table-to-table action. The static predicates need not be stored as time-varying planning fluents.

Use direct-transfer STRIPS actions: one action includes picking up a block and putting it down again. There is no separate holding state. Ground $b,y$ as distinct blocks and $x$ as a support, either a block or the table, with $x\ne b$ and $x\ne y$.

For $\mathrm{Move}(b,x,y)$, takeThe preconditions ensure that $b$ can be picked up and that the destination has room. Moving it frees a block source and occupies the destination, while $\mathrm{Clear}(b)$ persists. When $x=\tau$, table availability remains true; its redundant addition is simply omitted. Since $x$ is fixed in each ground action, this case distinction constructs ordinary add lists rather than introducing conditional action effects. The search transition model is $(S\setminus \mathrm{Del})\cup \mathrm{Add}$.

Write $\tau$ for the table. The positive initial planning fluents read from the original figure areThe static type facts are $\mathrm{Block}(A)$, $\mathrm{Block}(B)$ and $\mathrm{Block}(C)$; the table is not a block. With an explicit table-availability predicate, take $\mathrm{Clear}(\tau )$ to be permanently true. Under the closed-world assumption, all other well-typed initial planning fluents are false; in particular, $A$ is not clear.

The goal is the partial-state conjunctionIt need not redundantly prescribe every final fact. With only these three blocks and a valid blocks world state, the completed stack also places $C$ on the table and leaves $A$ clear.