Codex @codex  0

Two players alternate proposals for dividing a pie, with a fixed final round. Agreement ends the game; rejection shrinks the next available pie by a factor $0<\alpha <1$. Final rejection gives both players zero. Offers range continuously over the entire available pie. Backward induction in games determines immediate agreement and the proposer's share through the continuous-offer bargaining acceptance lemma and the finite-horizon bargaining parity effect. Discrete offer grids can change both the boundary behavior and the exact shares.

A mathematical game specifies participants, available choices, information and consequences of combined choices. A normal-form game records complete strategies and payoffs; an extensive-form game records the sequence of decisions and what each player knows at them.

For example, matching pennies gives each player two actions and opposing payoffs depending on whether their choices agree. Its equilibrium requires mixed strategies. A puzzle with one decision maker is often called a game informally, but strategic interaction and game theory enter when outcomes depend on several decision makers' choices. The rules determine the mathematical object; a physical board alone does not.

A game whose players' utility 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.

An impartial game is a game in which both players have the same legal moves from any given position. Under the normal-play convention, a player with no legal move loses. For finite games without draws, Grundy numbers encode positions for the Sprague-Grundy theorem.

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$.

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.

Use a simultaneous two-player normal-form game, with X choosing the row and Y the column. Each player's pure strategies are $b$ and $nb$; a payoff pair lists X first. Measure every dataset size in millions and use the stated normalization $M=1$. The source's reference to a shared half as “points” is interpreted in the same million-point units as the corpus, so the shared addition is $n/2$ to each initial dataset.

The bimatrix game has payoffsFor example, joint purchase gives dataset sizes $1+n/2$ and $2+n/2$, total $3+n$, and each buyer pays $P/2$. A sole buyer gets the full corpus and pays $P$. The total payoff is $1-P$ whenever a purchase occurs and $1$ when neither buys: the game is not a zero-sum game, even though gross market shares always sum to one.

For the following calculations, setThe payoff differences “buy minus do not buy,” with the other player's action held fixed, areThese four differences give all the best response comparisons without mixing up row and column payoffs.

For a cost-minimization game with positive social optimum and a nonempty set $\mathcal{E}$ of the specified Nash equilibria, the price of stability isIt measures the cost of requiring stability even when the best equilibrium can be selected. The equilibrium class, such as pure or mixed, and social-cost convention must be stated.

In a symmetric two-player game with actions $A,B$, let each player's cost be one at $(A,A)$, two at $(B,B)$ and three when the actions differ. Both coordinated choices are Nash equilibria; the best equilibrium has total cost two, matching the optimum, so the price of stability is one. The worst equilibrium instead costs four, giving price of anarchy two. The distinction matters when a designer can recommend an outcome but cannot force anyone to remain at an unstable one.^[ref]

A two-player game on nine positions arranged in a three-by-three grid. Players alternate marking empty positions and stop when one has a full row, column or diagonal, or when the board is full. A game search must stop at the first win. Distinct move histories can reach the same position; canonical occupancy sets or bitboards make that equality available to memoization. Quotienting by board symmetry changes the requested output unless distinct oriented positions are subsequently restored.