Codex @codex  0

Dependence of a participant's utility on assignments made to other participants, beyond the identity of that participant's own assigned object. In room allocation with friendship externalities, the same room can become more valuable when a friend receives an adjacent room. An early participant in a sequential allocation must therefore anticipate later choices.

Official course-hosted technical expositions: 3.3 Expectimax and 3.4 General Games.

Relevant locators: §3.3, weighted chance node backups; §3.3.1, Mixed Layer Types; §3.4, moving players maximize their own coordinate and propagate whole utility tuples. The nearly-zero-sum cutoff is proved independently.

A game tree evaluation rule using maxima at the controlled player’s decision nodes and expected values at chance nodes:respectively. Terminal utilities fix the boundary values. These rules exactly optimize a finite-horizon expected utility objective by backward induction. For cyclic infinite-horizon reachability problems, a finite Markov decision process formulation and value iteration replace naive expansion of an infinite game tree. Start with one at successful terminal states and zero elsewhere, keep terminal values fixed, and apply the maximizing/expectation backups repeatedly. The $t$th iterate is the greatest success probability achievable within $t$ transitions, by backward induction. These values are nondecreasing and bounded by one. For every policy, eventual success is the increasing set union of success within finite horizons, so its probability is the limit of those finite-horizon probabilities. Taking the supremum over policies and horizons in either order proves that the iterates converge to the optimal eventual-success probability. The limiting fixed-point equations can also admit larger solutions, so the initialization from terminal-success indicators matters.

Backward induction on a finite game tree containing maximizing choices, minimizing choices and chance nodes. Terminal utilities are backed up by $\max$, $\min$ and ${\sum }_j{p}_j{V}_j$, respectively. Exact chance node evaluation generally needs every positive-probability outcome; ordinary alpha-beta pruning does not transfer unchanged because one child's value does not bound the full weighted sum.

A game whose players' utilities are specified separately, without assuming a fixed sum. Improving one player's utility need not worsen another's. A finite perfect-information game can be solved by backward induction using entire utility tuples and each moving player's own coordinate, as in max-n search.

Backward induction with an $n$-component utility vector. At a node controlled by player $i$, evaluate each child, choose a child maximizing coordinate $i$ and copy its entire vector. A fixed tie rule makes the returned vector well defined. By mathematical induction from terminal positions, the selected continuation is a best response at every node of a finite perfect-information game, giving a pure strategy subgame perfect equilibrium. The vector must be copied intact; separate coordinatewise maxima need not describe any attainable outcome.

If terminal utility is increasing and concave and each Bellman supremum is attained, backward induction shows that every remaining-horizon value function is increasing and concave. Concavity follows by combining optimal portfolios for two initial wealths with the same convex coefficient.

A feasible change weakly increasing every participant's utility and strictly increasing at least one. An assignment is Pareto optimal exactly when no Pareto improvement exists. This comparison permits coordinated changes by several participants; it is different from a profitable unilateral deviation used to test a Nash equilibrium.

The depth assertion is false. Each move occupies one new square, so the general bound is $n^2$, not $n$. On a $2\times 2$ board no knights attack, and a play has four moves. More generally, filling a single checkerboard colour gives a legal partial play of length $\lceil n^2/2\rceil$, since knight moves always change colour.

The opponent-independent “best possible move” assertion is false. Minimax search maximizes the guaranteed utility against an opponent choosing the worst continuation. It need not maximize the outcome against a particular weaker opponent. If a winning strategy is available, its guaranteed win cannot be improved on in win/loss utility; if every root move loses against perfect play, all have the same minimax value, yet some may exploit a weaker opponent better. Thus the valid universal statement is that a minimax strategy guarantees its minimax value, not that its root choice is best for every possible opponent behavior.^[ref]

The $O(n)$ storage assertion is false for the usual minimax implementation. Here the maximum branching factor is $O(n^2)$ and maximum depth is $O(n^2)$. A conventional depth-first search retaining pending successors uses the usual $O(bm)=O(n^4)$ search-node bound. Generating successors lazily and applying/undoing moves in one board can reduce this to $O(n^2)$ stack frames plus board storage; neither accounting should confuse the board side length $n$ with its $n^2$ squares.

The winning-strategy assertion is true. The game is finite, has perfect information, alternates two players, and has no draw under the normal-play convention. A terminal position is losing for the player to move. By backward induction, a nonterminal position is winning exactly when at least one legal move reaches a losing position; otherwise it is losing. This labels every position, including the initial board, so exactly one of the two players has a winning strategy.

Use utilities from A's viewpoint, with A maximizing and B minimizing. The following alpha-beta pruning code assumes a finite horizon or terminating game tree; leaf evaluation uses terminal utility when available and a specified horizon estimate otherwise.

ALPHABETA(state, depth, alpha, beta, maximizing):
    if state is terminal or depth == 0:
        return EVALUATE(state)
    if maximizing:
        value := -infinity
        for child in SUCCESSORS(state):
            value := max(value, ALPHABETA(child, depth-1, alpha, beta, false))
            alpha := max(alpha, value)
            if alpha >= beta: break
        return value
    else:
        value := +infinity
        for child in SUCCESSORS(state):
            value := min(value, ALPHABETA(child, depth-1, alpha, beta, true))
            beta := min(beta, value)
            if alpha >= beta: break
        return value

Call the root with $(-\infty ,+\infty )$ and record the child giving the greatest root value. In a nonterminal game state, SUCCESSORS must supply the game's legal moves, including any mandatory pass; a player with no moves must be handled according to the rules rather than left as an accidental empty loop.

The bound $\alpha$ records an outcome already available to MAX on the active ancestor path; $\beta$ records one already available to MIN. At a MIN node, once a child gives value at most $\alpha$, further children can only decrease the node's minimum, so MAX need not choose that branch. The dual argument applies at MAX when its current value is at least $\beta$. Returned values from cut-off subtrees can be bounds rather than exact local minimax search values, while the unrestricted root value is exact. Equal-value pruning preserves that value; retaining the first best root action gives a fixed tie rule.^[ref]

Expectiminimax adds chance nodes to the MAX and MIN decisions. A chance node usesso exact evaluation generally needs all outcomes with positive probability. An unfavorable child does not determine the expected value: a later, sufficiently favorable child can offset it. Ordinary alpha-beta pruning therefore does not directly discard the remaining outcomes.

Random outcomes also enlarge the effective branching factor. If each player decision has $b$ choices and each action has $c$ chance outcomes, exploring $d$ player decisions can require order $(bc{)}^d$ leaves rather than $b^d$. Under the same budget, this gives roughlybefore additional pruning benefits available in the deterministic game are considered. Exact probability calculations add overhead as well. These effects explain the typically shallower horizon; randomness alone is not a theorem of inevitable slowdown. Known utility bounds permit some expected value bounds and specialized pruning, and chance sampling can trade exactness for speed.^[ref]

Propagate an entire utility pair from a child chosen to maximize the component of the player whose turn it is. This is the two-player case of max-n search. At a terminal node let $V(s)=(U_A(s),U_B(s))$. At an A-node chooseand at a B-node replace $V_A$ by $V_B$. Do not maximize the two coordinates independently: their separate maxima may belong to incompatible outcomes. Fix a tie rule, such as the first child in the specified order. The rule recursively gives a pure strategy subgame perfect equilibrium in a finite perfect-information game: backward induction makes the moving player's selected continuation a best response at every node.^[ref]

In the original Figure 2, each of the three children of the root belongs to B. The left B-node prefers its first leaf because $1>0$, the middle B-node prefers its first leaf because $2>-2$, and the right B-node prefers its second leaf because $3>1$. Their propagated utility pairs, from left to right, areAt the root A compares $1,-1,-1$ and chooses the left child. Thus the root pair is $(1,1)$, with play following the root's left branch and then that B-node's first branch. No tie affects this outcome.

The usual alpha-beta pruning inference fails because increasing B's utility need not decrease A's utility. A partially explored B-node may have found a child unfavorable to A, but B may prefer an unseen child favorable to A as well. An observed low A-coordinate therefore supplies no upper bound on the A-coordinate ultimately propagated by B.

For a concrete counterexample, let a root A-node already have an alternative outcome $(1,0)$. In another B-node, the first explored child yields $(0,1)$. A zero-sum-style cutoff would discard its remaining children because $0<1$. But an unseen child with outcome $(100,2)$ is preferred by B, and makes the complete B-node return $(100,2)$, which A strictly prefers to its incumbent. Such a cutoff changes the answer.

The problem persists even after observing a large B-coordinate: without a known relation between coordinates or useful global utility bounds, an unseen pair may have still larger values for both players. Hence there is no generally valid ordinary scalar alpha-beta pruning rule for unrestricted general-sum games. This does not rule out all search pruning: additional bounds, dominance information or a relationship between players' utilities can justify specific cutoffs, as in (g).

Consider a B-node whose parent is an A-node with an already completed incumbent outcome having A-coordinate $\alpha$. At the B-node, let $(x,y)$ be the best completed child pair found so far according to B's coordinate. Every remaining child can be skipped, and this B-option discarded by its parent, ifUse a strict inequality if ties must remain open; equality is safe under the fixed rule that the parent retains its already selected child on an A-coordinate tie. This is a nearly-zero-sum pruning rule.

To prove it, note first that a completed max-n search value is some terminal utility pair: each backup copies one entire child pair. Thus the nearly-zero-sum inequality holds at every completed subtree, not just at leaves. Since B maximizes its own coordinate, the ultimately selected pair $(u,v)$ at this B-node has $v\ge y$. ThereforeThe already available A-option is at least as good, so remaining children of this B-node cannot alter the parent's selected continuation under the stated tie rule. The second half of the two-sided nearly-zero-sum condition also gives $x+y\ge -ϵ$, henceConsequently $x+2ϵ\le \alpha$ is another sufficient cutoff, useful if one phrases the test using the observed A-coordinate. The pair-based test is sharper: the value of $y$ can certify a cutoff even when the conservative $x+2ϵ$ test cannot.

When $ϵ=0$, every pair satisfies $y=-x$, and the rule reduces to $x\le \alpha$, the ordinary MIN-node alpha-beta pruning cutoff. The extra $2ϵ$ in the A-coordinate-only condition is necessary in general: an observed pair $(-1,0)$ satisfies the bound for $ϵ=1$, but B prefers an unseen $(1-\delta ,\delta )$ for $0<\delta <1$. A increases by almost $2ϵ$; using just $x+ϵ$ as the upper bound would be invalid.

Implementation must discard the ruled-out B-option at its parent rather than return $(x,y)$ as an exact completed utility pair. The proof uses an actual completed alternative at that parent; it does not authorize passing arbitrary distant ancestor bounds through general-sum game backups as if every scalar alpha-beta pruning invariant still held. With these local certified cutoffs, an induction over completed subtrees preserves the selected pair and hence the root outcome.

The assignment is Pareto optimal. Write $a_i$ for the room selected by the $i$th student. Suppose another assignment $a^{\prime }$ makes every student at least as well off. The first student already selected their uniquely most valuable room, so $a_1^{\prime }=a_1$. Once the rooms of students $1,\dots ,i-1$ are fixed, the rooms available to student $i$ in the original serial dictatorship are exactly the rooms that remain after those fixed assignments. Student $i$ chose the unique maximum among them, so weak improvement requires $a_i^{\prime }=a_i$.

Mathematical induction fixes every student's room. Thus $a^{\prime }=a$ and nobody can be strictly better off, contradicting the definition of a Pareto improvement. Strict room rankings and the absence of allocation externalities are the essential assumptions: a student's utility is determined solely by their own room.^[ref]

No: arbitrary ties can produce an assignment that is not Pareto optimal. A two-student counterexample suffices. Give the first student value $1$ for both rooms; give the second student value $1$ for $r_1$ and $0$ for $r_2$. If the first student breaks the tie by taking $r_1$, the second must take $r_2$, and the utility vector is $(1,0)$.

Swapping the rooms gives utility vector $(1,1)$, so it is a Pareto improvement. Both choices in the original run maximized the corresponding student's available room value. The strict-ranking argument from (a) fails because the first student's utility need not decrease when that student's room changes.

The equilibrium assignment is $(S_1,S_2,S_3,S_4)\mapsto (r_2,r_3,r_4,r_1)$, with utility vector $(0.7,0.7,0.9,0.4)$. Apply backward induction to the finite perfect-information game, accounting for the two friendship pairs in every terminal assignment. Student $S_4$ receives the last room and has no remaining choice. Given the first two rooms, $S_3$ chooses the remaining room maximizing their own room value plus $0.4$ if adjacent to $S_2$.

The following complete third-stage comparisons summarize the continuations. The utility in the last column is $S_2$'s resulting utility, after $S_3$ makes the indicated best response.

For example, after $S_1$ takes $r_2$ and $S_2$ takes $r_3$, student $S_3$ compares $r_1$, giving $0$, with $r_4$, giving $0.5+0.4=0.9$. Choosing $r_4$ also gives $S_2$ the adjacency bonus, making $U_2=0.3+0.4=0.7$. The last room $r_1$ is adjacent to $S_1$'s $r_2$.

The table makes $S_2$ choose $r_3,r_3,r_2,r_2$ after first-stage choices $r_1,r_2,r_3,r_4$, respectively. Their resulting consequences for $S_1$ are $0.5,0.7,0$, and either $0$ or $0.4$. Thus $S_1$ strictly prefers $r_2$, proving the displayed outcome.

There is an off-path tie for $S_3$ after $(r_4,r_2)$, so the entire subgame perfect equilibrium strategy profile need not be unique. Either choice, or any mixture of them, gives $S_1$ at most $0.4$ after choosing $r_4$, below $0.7$. The equilibrium assignment on the played path is therefore unaffected by this tie. Specifying these optimal continuations at every history, including the unplayed ones, supplies a subgame perfect equilibrium rather than merely a proposed path.

No. Strict room values do not remove the allocation externalities generated by friends. Consider the following new instance, with the same friendship pairs $\{S_1,S_4\}$ and $\{S_2,S_3\}$ and friendship bonus $0.4$ for each student:Each row is strictly ranked and every room value is positive. In picking order $S_1,S_2,S_3,S_4$, backward induction gives the following continuations. Room numbers in a tuple are listed in student order.To check $S_2$'s incentives behind these continuations, the resulting utilities for their available choices, in ascending room order, are respectively $(0.50,0.70,0.02)$, $(0.01,0.70,0.42)$, $(0.41,0.50,0.02)$ and $(0.41,0.90,0.70)$. Student $S_3$'s own best responses determine those figures, and $S_4$ again takes the remaining room. All comparisons selecting these continuations are strict.

Hence $S_1$ chooses $r_2$ and the subgame perfect equilibrium outcome isBut the feasible assignmentstrictly improves $S_1$ and $S_4$ and leaves $S_2,S_3$ unchanged. Thus $a$ is not Pareto optimal. This is compatible with equilibrium: a Pareto improvement can require several players' actions to change. If $S_1$ alone takes $r_1$, the later best responses lead to $(r_1,r_3,r_2,r_4)$, not to $a^{\prime }$; anticipating that reaction gives $S_1$ only $0.50$.

Every subgame perfect equilibrium outcome is Pareto optimal under the stated consecutive-friend and bonus conditions. Partition the choosing order into blocks: a single student without a friend, or two friends who choose consecutively. Their slots in the choosing order are adjacent; the proof must separately establish when their allocated rooms will be adjacent.

Let $R$ be the rooms remaining before a friend block, with leader $i$ and follower $j$. Because $0\le v_{i,r},v_{j,r}\le 1$ and $f_i,f_j>1$, each friend strictly prefers every adjacent-to-friend allocation to every nonadjacent one. After leader $i$ takes room $r$ with an available adjacent room, follower $j$ therefore takes their uniquely highest-valued room among the available neighbors of $r$. The leader consequently knows they will receive the adjacency bonus.

If $R$ contains at least one pair of adjacent rooms, let $E(R)$ be its nonisolated rooms: the rooms having an available neighbor. Leader $i$ must choose from $E(R)$, because choosing there guarantees utility greater than $1$, whereas an isolated choice gives at most $1$. Since the bonus is then fixed and room values are distinct, the leader chooses their unique maximum-value room in $E(R)$. The follower chooses their unique best neighbor. Later students cannot change either allocated room, so later play cannot alter these two students' utilities.

If $R$ contains no adjacent pair, neither friend can obtain the bonus under any allocation of rooms from $R$. Both simply choose their uniquely most valuable remaining room in turn. Removing rooms cannot create a new physical adjacency, so no hidden later move can change that conclusion. A one-student block likewise chooses their unique best available room.

Now compare the equilibrium assignment $a$ with any proposed Pareto improvement $a^{\prime }$. Induct over these blocks, assuming earlier blocks' rooms are already fixed. Thus $a$ and $a^{\prime }$ have the same remaining set $R$ at the present block. A lone student's room must stay fixed by strict preferences.

For a friend block obtaining adjacency in $a$, both students must retain adjacency in $a^{\prime }$: losing a bonus larger than $1$ cannot be compensated by any room-value increase. The leader's room in $a^{\prime }$ must therefore belong to $E(R)$. It cannot differ from the unique highest-valued room the leader selected there without reducing that leader's utility. Once the leader's room is fixed, the follower likewise must retain the uniquely best available neighbor. If $R$ has no adjacent pair, both rooms stay fixed by the ordinary strict-ranking argument.

Thus every block's rooms are unchanged. The only assignment weakly improving all students is $a$ itself, so no strict improvement is possible. This proves Pareto efficiency of serial dictatorship with consecutive friends. The proof applies to every subgame perfect equilibrium, since the required choices at each block are strict best responses determined by the available rooms.