Game theory

Game theory studies strategic interaction among decision makers.

A player maximizes the worst payoff it can receive against the other player's actions. Allowing the opponent to mix does not lower the worst payoff beyond a pure action, since the payoff is linear in that mixture. A security level payoff is an individual guarantee, not generally a Nash equilibrium payoff.

The essential two-person bargaining domain consists of a compact convex set of feasible utility vectors $F$, a disagreement point $d\in F$, and at least one feasible vector strictly exceeding $d$ coordinatewise. The Nash bargaining solution selects a jointly feasible improvement using a rule characterized by Pareto efficiency, bargaining symmetry, positive affine invariance in bargaining and bargaining independence of irrelevant alternatives.

A payoff is individually rational for a Nash bargaining problem when neither player receives less than its disagreement point payoff. Essentiality permits strict improvement for both. Maximizing a positive Nash product therefore selects a strictly individually rational payoff.

If an admissible smaller feasible set with the same disagreement point contains the original chosen vector, deleting the other outcomes must leave the choice unchanged. The Nash bargaining solution satisfies this axiom because its unique product maximizer remains feasible.

Transforming each utility by an independent positive affine map must transform the chosen payoff by the same map. The Nash product changes only by a positive factor, so the Nash bargaining solution has this invariance.

When the feasible payoff set and disagreement point are invariant under interchange of players, the solution must give both players the same payoff.

For an essential Nash bargaining problem, maximizing the Nash product gives a unique vector: on positive gains its logarithm is a strictly concave function. The rule satisfies the four bargaining axioms, and the supporting triangle for Nash bargaining proves their converse characterization. The nonessential case requires additional conventions, since a zero product may have many maximizers.

Normalize a positive Nash product maximizer and the disagreement point to $(1,1)$ and zero. The first-order product inequality along every feasible segment places the transformed set in $z_1+z_2\le 2$. Compactness allows a symmetric containing triangle with finite lower coordinate bounds. Bargaining symmetry and Pareto efficiency choose $(1,1)$ in that triangle; bargaining independence of irrelevant alternatives transfers this choice to the original normalized set. Positive affine invariance in bargaining then proves the full characterization.

The product of the two players' gains over the disagreement point is maximized over the individually rational feasible set in the Nash bargaining solution. Positive affine changes of utility multiply this product by a positive constant and leave the selected payoff correspondence unchanged after transforming coordinates.

The disagreement point specifies each player's payoff if bargaining fails. It supplies the baseline from which the Nash product measures gains. In a game-based example it may be set to the vector of security level payoffs; this choice must be recomputed when the underlying payoff matrices change.

Cooperative game theory studies what groups of players can achieve together and how their joint value can be allocated. A transferable utility game assigns a real value to each coalition. The core of a cooperative game asks which allocations no coalition can improve upon; the Shapley value averages marginal contributions across player orderings.

A finite transferable utility game gives each coalition $S\subseteq N$ a real value $v(S)$ that its members can distribute among themselves. The usual normalization is $v(\varnothing )=0$. An efficient payoff vector $x$ satisfies ${\sum }_{i\in N}{x}_i=v(N)$. Simple cooperative games model winning coalitions with values zero and one; convex cooperative games model increasing marginal contributions.

Duality assigns a coalition the grand-coalition value less the value of its complement. For a normalized transferable utility game, the dual is normalized and taking the dual twice recovers the original game. A player's dual marginal contribution at predecessor set $S$ equals its original contribution at the complementary predecessor set in $N\setminus \{i\}$. This preserves the Shapley value.

When the imputation set is nonempty, the nucleolus is the unique imputation lexicographically minimizing the vector of excesses of a coalition sorted decreasingly. It minimizes the largest complaint first, then subsequent complaints among ties. It can be computed through successive linear programs that minimize the current maximum excess and retain constraints fixed by prior stages. Its uniqueness is the standard nucleolus theorem. If the core of a cooperative game is nonempty, the nucleolus belongs to it; an empty core does not preclude a nucleolus.

The prenucleolus uses the same sorted excesses of a coalition but minimizes over all efficient payoff vectors, without imposing individual rationality. It can differ from the nucleolus when coalition values are not superadditive. Any computation must state which domain is used rather than silently relaxing imputation inequalities.

An imputation is an efficient, individually rational allocation in a transferable utility game. Its total is the grand-coalition value and each player receives at least its singleton value. The set is nonempty exactly when $v(N)\ge {\sum }_{i}v(\{i\})$, and is then compact. This individual-rationality condition distinguishes the nucleolus from the prenucleolus.

A player's marginal contribution to a coalition is the increase in its value when that player joins. In a convex cooperative game, marginal contributions increase with the preceding coalition. Averaging contributions across player orderings gives the Shapley value.

A coalition is a subset of the players in a transferable utility game, considered as a group that can act together. The game assigns it value $v(S)$. The core of a cooperative game constrains the total payoff assigned to every coalition, while a marginal contribution measures the value gained by adding one player.

The excess measures a coalition's complaint against an allocation: a positive excess means its own attainable value exceeds its assigned total. The core of a cooperative game requires every excess to be nonpositive at an efficient allocation. The nucleolus lexicographically minimizes the decreasingly sorted excess vector over imputations.

A transferable utility game is convex when its coalition-value function is supermodular. Equivalently a player's marginal contribution cannot decrease when the preceding coalition grows. The implication follows by applying the displayed inequality to $A\cup \{i\}$ and $B$ with $A\subseteq B$, $i\notin B$; the reverse implication follows by adding successive marginal inequalities. This property concerns coalition values, not geometrical convexity of a strategy space.

Increasing marginal contributions imply $m_i^{\pi }\ge v((S\cap P_i)\cup \{i\})-v(S\cap P_i)$ for $i\in S$. Summing telescopes to ${\sum }_{i\in S}{m}_i^{\pi }\ge v(S)$, while efficiency follows by telescoping over the full ordering. Hence every marginal contribution vector is in the core of a cooperative game. The core is a convex set, so their average, the Shapley value, is in it too. This gives an elementary proof of nonemptiness and stability for a convex cooperative game.

The core consists of efficient payoff vectors for which each coalition receives at least its own attainable value. Thus no coalition can improve every member's payoff by leaving. It is a convex set defined by linear constraints, but can be empty. Every convex cooperative game has a nonempty core because each marginal contribution vector belongs to it.

The Shapley value averages each player's marginal contribution over uniformly random player orderings. Exactly $|S|!(n-|S|-1)!$ orderings have $S$ immediately before player $i$, giving the formula. The values sum to $v(N)$ by telescoping each ordering. In a simple cooperative game this is the probability of being pivotal. For a convex cooperative game, Shapley value belongs to the core of a convex game guarantees a stable allocation as well.

Complementing predecessor sets within $N\setminus \{i\}$ preserves their Shapley value weights, since the factorials $|S|!$ and $(n-|S|-1)!$ interchange. For the dual coalitional game, the corresponding marginal contribution equals the original contribution at that complementary set. Hence the values coincide. The same bijection gives ${\varphi }_i(v)={\sum }_{S}w(S)(v(N\setminus S)-v(S))$.

For a player ordering $\pi$, $P_i$ is the set before player $i$, and the displayed entries form its marginal contribution vector. Their sum is $v(N)-v(\varnothing )$. The Shapley value is the average of these vectors. In a convex cooperative game, increasing marginal contributions make each such vector satisfy every coalition constraint of the core of a cooperative game.

A weighted voting game assigns player weights and a threshold, and declares coalitions winning when their total weight passes that threshold. The strict $>t$ convention is equivalent to quota $t+1$ for integer weights; another common convention writes a weak inequality directly. Nontrivial examples are simple cooperative games. Having nonnegative weights does not guarantee a convex cooperative game: two-of-three majority supplies a counterexample.

A simple cooperative game is a monotone transferable utility game in which each coalition either loses, with value zero, or wins, with value one. In the usual nontrivial convention the empty coalition loses and the grand coalition wins. The Shapley value is then the probability that a player changes a losing coalition into a winning one when players enter in uniformly random order.

Two strategies are payoff-equivalent for a player when they give that player the same payoff against every strategy of the opponents. If every player's payoff is also unchanged, replacing one by the other preserves the game outcomes entirely. This is distinct from weakly dominated strategies, whose definition requires a strict comparison somewhere.

A normal-form game specifies each player's strategy set and their payoff for every strategy profile. In a finite two-player game these data form a bimatrix game; if the two payoffs always sum to zero, one payoff matrix describes the matrix game. The representation specifies choices and incentives, without a temporal order of observed moves.

A strategy profile that is a Nash equilibrium in every subgame, including those outside the realized play path. In finite sequential games, backward induction constructs such profiles by solving continuation games before earlier decisions. When a stage is an all-pay contest, its solution can involve mixed strategies.

A sequential model in game theory in which a leader commits to an action before a follower observes it and chooses a best response. The leader anticipates the follower's response when optimizing. With private follower information, the leader maximizes its expected payoff over follower types. The resulting solution is a Stackelberg equilibrium.

A solution of Stackelberg competition in which the follower chooses a best response after each observed leader action and the leader optimizes given those responses. Indifference may require a specified response or leader-selection convention; it cannot be silently treated as a strict inequality. In a sequential private-value all-pay contest, the leader's objective is $vF(b)-b$.

Contest theory studies how prize allocation rules and effort costs influence strategic effort investment, participation, and the resulting Nash equilibria or Bayesian Nash equilibria. Unlike a sale in which only the winner pays, an all-pay auction charges every participant for its effort.

A finite sequence of all-pay contests in which each stage awards one prize and its winner leaves. Losing players remain eligible for later stages. A player can receive at most one prize, while its effort costs are incurred whenever it participates. Subgame perfect equilibrium accounts for both the immediate prize and the value of remaining eligible.

With ordered values $v_1>\cdots >v_k$ and $r<k$ prizes remaining, define $C_r=(1-\delta ){\sum }_{j=2}^r{\delta }^{j-2}{v}_j+{\delta }^{r-1}{v}_{r+1}$. In the recursively constructed discounted subgame perfect equilibrium, it is the second active player's effective prize and the effort-support upper endpoint. The highest player's utility is $v_1-C_r$. The coefficients form a convex combination, so $C_r\ge v_{r+1}$, allowing lower-player deviations to be bounded.

As $\delta \uparrow 1$, both active players' effective prizes in every nonfinal subgame tend to the marginal valuation $v_{r+1}$. The two-player complete-information all-pay equilibrium then gives each a winning probability $1/2$. In the final stage, actual valuations determine the asymmetric winning probabilities. Taking this limit from discounted equilibria specifies the continuation selection instead of independently choosing an undiscounted game equilibrium.

For $m<n$ prizes and ordered distinct valuations, the discounted-equilibrium limit gives $x_1=1-2^{-m}{v}_{m+1}/v_1$ and $x_i=1-2^{-(m-i+2)}{v}_{m+1}/v_i$ for $2\le i\le m$. A player must lose its successive fair nonfinal contests and then the asymmetric final contest to receive no prize. The marginal player's probability is $m-{\sum }_{i=1}^m{x}_i$, and lower players have probability zero.

If $J_i(S,r)$ is a player's net expected utility with remaining players $S$ and $r$ prizes, losing the current stage to player $j$ gives baseline $\delta J_i(S\setminus \{j\},r-1)$. This baseline includes later prize values and later effort costs. Subtracting it from the immediate prize value gives an effective prize in a sequential contest. Discounting must be applied to utilities, rather than to winning probabilities.

Relative to losing against a particular rival, the gain from winning now is the current value minus discounted continuation utility. In an elimination contest this is $A_i=v_i-\delta J_i(S\setminus \{j\},r-1)$. When the relevant losing baseline is fixed, current effort incentives reduce to a two-player complete-information all-pay equilibrium. In general, the baseline can depend on which rival wins; that dependence must be verified before using a single effective prize.

Two players pay their invested efforts regardless of outcome. A leader invests first, and a follower observes that effort before deciding. With ties favoring the follower and unit costs, a follower of value $u$ matches leader effort $b$ when $u>b$, and otherwise declines. For a continuous follower cumulative distribution function $F$, the leader wins with probability $F(b)$ and has payoff $vF(b)-b$.

Every optimal leader bid satisfies $b(v)\le v$, because bidding zero guarantees payoff zero and winning probability is at most one. Hence $F(b(v))\le F(v)$. With identically distributed independent continuous valuations, the probability integral transform gives $\mathbb{E}F(V)=1/2$. The leader's unconditional winning probability is therefore at most $1/2$, even when some high leader types have a conditional advantage. This argument does not depend on selecting a unique optimum.

With follower distribution $F$, a leader of value $v$ chooses $b\in \arg {\max }_{0\le b\le 1}\{vF(b)-b\}$. If $F$ is a concave function, the objective is concave and an interior optimum satisfies $v{F}^{\prime }(b)=1$. Endpoint derivatives handle zero or maximal effort. Zero effort guarantees nonnegative payoff, so every optimum satisfies $b\le vF(b)\le v$.

If a concave leader objective $vF(b)-b$ is constant over an interval, all efforts there are best responses, but they can have different winning probabilities. A flat positive-density interval of $F$ produces this at the type $v=1/F^{\prime }$. Thus strict threshold statements must distinguish strict concavity from a selection such as the smallest maximizing effort. For an atom-free type distribution, the specified threshold type has zero ex ante probability.

For increasing concave $F$, write $q=F^{-1}(1/2)$. Under the smallest-maximizer convention, the leader wins with probability greater than $1/2$ exactly when $v>1/F^{\prime }(q)$. The sign of $v{F}^{\prime }(q)-1$ places the maximizer before or after $q$. At equality, concavity alone permits a flat interval of optima; strict concavity or an explicit selection is needed for the strict comparison at that type.

For positive total effort, a proportional allocation contest awards player $i$ the prize with probability $b_i/{\sum }_j{b}_j$, or gives it that proportion of a divisible prize. A convention is needed at zero total effort. This allocation is different from the discontinuous highest-effort rule of an all-pay auction.

An all-pay contest with allocations $x_i=b_i/({\sum }_j{b}_j+\delta )$ includes fixed outside effort $\delta \ge 0$. A player with unit effort cost has payoff $v_i{x}_i-b_i$. The outside effort represents an ineligible fixed competitor and may leave some prize probability unallocated to eligible players. At equilibrium, a player is active exactly when its value exceeds total eligible effort plus outside effort.

For ordered positive valuations, rank $j$ is active exactly when $\delta <v_j(2-j+{\sum }_{i<j}{v}_j/v_i)$. These ranks form a prefix, and the number active is the largest qualifying rank, or zero if none qualifies. This follows by evaluating the decreasing equilibrium equation ${\sum }_i(1-S/v_i{)}_{+}-1+\delta /S=0$ at $S=v_j$. Strict inequality excludes zero-effort boundary players.

With $k>0$ active players of harmonic mean valuation ${\bar{v}}_k$, unit-cost Nash equilibrium effort satisfies $R+\delta =\frac{{\bar{v}}_k}{2k}[(k-1)+\sqrt{(k-1{)}^2+4k\delta /{\bar{v}}_k}]$. Sum the active-player first-order equations $b_i=(R+\delta )(1-(R+\delta )/v_i)$ to obtain the quadratic. If $\delta$ is at least the largest valuation, no one is active and $R=0$. With no outside effort, at least two players must be active.

With values $v_i>0$ and effort costs $b_i^2$, the unique pure Nash equilibrium has the efforts displayed above. Interior first-order conditions give $v_i{b}_j/(b_1+b_2{)}^2=2b_i$, hence $b_1/b_2=\sqrt{v_1/v_2}$ and $(b_1+b_2{)}^2=\sqrt{v_1{v}_2}/2$. Against a positive rival effort, each payoff is a strictly concave function, so these conditions identify global best responses. On the axes, lowering a positive uncontested effort or adding a sufficiently small effort at the zero tie rules out equilibrium.

Players choose efforts in several all-pay contests at the same time. With additive quasilinear utility and no shared effort budget, a player's expected payoff is the sum of its per-contest payoffs. An entry restriction couples the choices of contests even though the subsequent effort optimization is separable.

Consider $n\ge 2$ identical players, prizes $w_j>0$, unit effort costs, and exactly two entries per player. The symmetric equilibrium omission probabilities $q_j$ sum to one. The common per-contest payoff is $u=({\sum }_j{w}_j^{-1/(n-1)}{)}^{-(n-1)}$, and the unconditional rival distribution on $0\le b\le w_j-u$ is $G_j(b)=((b+u)/w_j{)}^{1/(n-1)}$. Conditional on entry, its distribution function is $(G_j(b)-q_j)/(1-q_j)$. Choosing the omitted contest according to $q$ and sampling the two active efforts independently gives a symmetric equilibrium with expected payoff $2u$. These formulas determine the marginal laws; they do not determine the dependence between a player's two efforts.

If contest rewards and costs add, a fixed deviation's expected payoff depends on each rival's per-contest marginal distributions, rather than on dependence between that rival's efforts across contests. Replacing the conditional independent sampling of two active efforts by another copula with the same conditional marginals therefore preserves every deviation payoff. Consequently it preserves the Nash equilibrium, even when the new joint strategy distribution is different. This explains why unique participation probabilities and bid marginals need not imply a unique full mixed strategy.

For a prize of value $w$, let $G(b)$ be the probability that a rival is absent or enters with effort at most $b$. When rivals act independently and have no atoms at positive efforts, effort $b>0$ wins with probability $G(b{)}^{n-1}$. If a player mixes over an interval of best responses, its payoff on that interval is constant, so $G(b)=((b+u)/w{)}^{1/(n-1)}$. If the absence probability is $q$ and the active effort support starts at zero, then $u=w{q}^{n-1}$.

A rank-order contest awards a sequence of prizes according to the ranks of efforts, while every player incurs its own effort cost. With an independent private values model, an increasing symmetric bidding function orders efforts in the same way as valuations.

Suppose values are nonnegative, the rank-order expected prize allocation $a$ is increasing and differentiable, and $a(\underline{v})=0$. With unit effort cost and zero effort at the lowest type, the symmetric equilibrium effort is $b(v)=va(v)-{\int }_{\underline{v}}^{v}a(t)dt$. A true type $v$ imitating type $z$ receives utility $va(z)-b(z)$, whose derivative in $z$ is $(v-z)a^{\prime }(z)$. It increases up to $v$ and decreases afterwards, proving the best response property. This is the interim payment identity specialized to an all-pay contest.

Let $V_{[1]}\ge \cdots \ge V_{[n]}$ be descending order statistics, with $w_n=0$ and nonnegative decreasing prizes. Decompose the prize vector into awards of $w_k-w_{k+1}$ to each of the best $k$ players. The corresponding truthful multi-unit auction charges each winner the next value $V_{[k+1]}$. Its total payment is $k(w_k-w_{k+1})V_{[k+1]}$. Revenue equivalence transfers the expected payment to the all-pay contest, because the interim allocations and lowest-type utilities coincide. Summing the layers proves the formula.

With $n$ independent uniform types, $m<n$ equal prizes of scale $w(m/n)$ and unit effort costs, a symmetric Bayesian Nash equilibrium has total expected effort $R_m=m(n-m)w(m/n)/(n+1)$. The all-pay effort identity yields $b(v)=w(m/n){\int }_0^{v}t{q}_m^{\prime }(t)dt$. The allocation derivative is a Beta distribution density with parameters $n-m,m$, so integration gives the formula.

For prize scale $w(x)=x^{-\alpha }$, total effort is proportional to $h(x)=x^{1-\alpha }(1-x)$ on the feasible grid $x=m/n$. If $\alpha \ge 1$, one prize is optimal. For $0<\alpha <1$, $h$ increases up to $x_{\ast }=(1-\alpha )/(2-\alpha )$ and then decreases, so the optimal feasible integer is among $\lfloor n{x}_{\ast }\rfloor$ and $\lfloor n{x}_{\ast }\rfloor +1$. Remove infeasible candidates and compare their objective values. No definition at $x=0$ is needed.

For $n$ players with independent valuations having a continuous distribution function $F$, a type $v$ occupies rank $k$ when exactly $k-1$ rivals have higher values. Multiplying this binomial distribution by the rank prize $w_k$ and summing gives $a(v)$. Ties occur only on zero-probability events when the valuation law is atomless.

A prize allocation rule assigns winning probabilities or divisible prize shares to a profile of efforts. In an all-pay auction, the greatest effort wins; a proportional allocation contest instead assigns shares continuously according to relative effort. The rule is essential data of a contest model.

A winning probability is the probability that a specified participant receives the prize, conditional on the submitted efforts and the allocation rule's randomization.

A Bayesian game gives players private information about their types, a probability model for that information, and strategies depending on the player's own type. A private-value auction with uncertain other valuations is a Bayesian game.

A Bayesian Nash equilibrium consists of type-dependent strategies such that every type maximizes its conditional expected payoff given the other players' strategies and the type distribution. It is a Nash equilibrium in the strategic description whose actions are whole contingent strategy functions. Auction incentive comparisons can test a deviation by imitating another type's equilibrium bid.

Mechanism design chooses allocation and payment rules while accounting for how agents' information and incentives affect their reports. Social choice theory studies collective choice from preferences, while auction design also uses monetary transfers.

A mechanism specifies participants' available messages, an allocation rule, and any payment rule. Mechanism design chooses these rules to achieve an objective while respecting participants' incentive compatibility and individual rationality.

In a single-parameter mechanism, player $i$ has one private scalar value $v_i$, receives an allocation amount $x_i$, and has quasilinear utility $v_i{x}_i-p_i$. The allocation-payment relation is governed by incentive compatibility and the interim payment identity.

For an absolutely continuous valuation distribution with density $f(v)>0$, its virtual valuation is $v-(1-F(v))/f(v)$. The virtual-surplus revenue identity converts expected incentive-compatible payments into expected allocations weighted by virtual valuations. A regular prior makes this quantity nondecreasing.

Virtual surplus weights allocation amounts by the corresponding virtual valuations. Under the hypotheses of the virtual-surplus revenue identity, maximizing it subject to implementability and feasibility yields a revenue-optimal mechanism when lowest-type utilities can be normalized to zero.

For an independent private values model, let $X_i(v)$ and $P_i(v)$ be interim allocation and payment. The interim payment identity gives $P_i(v)=v{X}_i(v)-U_i({\underline{v}}_i)-{\int }_{{\underline{v}}_i}^v{X}_i(t)dt$. Applying Fubini's theorem to reverse the order of integration yields $\mathbb{E}{\int }_{{\underline{v}}_i}^{V_i}{X}_i(t)dt=\int X_i(t)(1-F_i(t))dt$. Subtracting this term from $\int v{X}_i(v)f_i(v)dv$ proves the identity. Interim individual rationality bounds the lowest-type utilities below by zero.

In a public-project single-parameter mechanism, all players receive the same binary allocation. For independent regular priors and voluntary participation with zero outside utility, maximizing virtual surplus means providing the project exactly when ${\sum }_i{\varphi }_i(v_i)\ge 0$. The allocation is monotone in each value, so critical-value payments implement it with dominant-strategy incentive compatibility and ex post individual rationality. For independent uniform values on $[0,1]$, the condition is ${\sum }_i{v}_i\ge n/2$, with winning payment $\max \{0,n/2-{\sum }_{j\ne i}{v}_j\}$.

A valuation distribution is regular when its virtual valuation is a nondecreasing function of value. This is an auction-theory condition, not the unrelated regularity notions used elsewhere in mathematics.

A direct revelation mechanism asks agents to report their types directly, then computes allocation and payments from those reports. Being direct does not itself imply strategyproofness; the allocation and payment rules must supply the incentive guarantee.

An equilibrium outcome of a mechanism can be reproduced by asking for types and then sending the messages prescribed by the original equilibrium strategies. Truthful reports are then a Bayesian Nash equilibrium: a profitable false report would induce a profitable original deviation. This reduces optimization over indirect mechanisms to direct revelation mechanisms with Bayesian incentive compatibility, under the same information and participation assumptions.

The pivot form chooses a reported-welfare-maximizing allocation and charges each agent the maximum welfare achievable by the others without that agent minus the others' welfare in the chosen allocation. With quasilinear utility, truthful reporting is a dominant strategy because the first term in the payment depends only on other reports. For two identical items and three unit-demand bidders, each winner pays the lowest reported valuation and the loser pays zero.

Incentive compatibility makes the prescribed truthful or type-dependent strategy optimal under the specified solution concept. Dominant-strategy incentive compatibility holds for every other report profile; Bayesian incentive compatibility compares expected utilities over the other agents' types.

Dominant-strategy incentive compatibility means truthful reporting maximizes a player's utility for every fixed profile of the other reports. It is the monetary-mechanism version of strategyproofness and implies Bayesian incentive compatibility under any independent prior.

A monotone binary allocation is made truthful by charging its winning threshold, truncated below at the lowest allowed value, and charging zero to losers. The displayed integral formula sets the lowest type's utility to zero. To check it, hold the other reports fixed: a type above the threshold benefits from winning at that price, while a type below it benefits from losing. At a threshold, either deterministic tie choice is compatible with indifference.

Truthful reporting is Bayesian incentive compatible when every type maximizes its expected utility over the other players' types by reporting truthfully. In an independent private values model, the displayed inequality uses the same interim allocation and payment functions for every possible true type.

Individual rationality means participation yields at least the outside-option utility, normalized here to zero. A risk-neutral zero-value bidder with nonnegative payments and no positive-valued allocation must have zero expected payment and utility if participation is individually rational.

Ex post individual rationality requires nonnegative participation utility at every realized profile of types. A truthful threshold allocation with its critical-value payment satisfies this condition for nonnegative valuations.

Interim individual rationality requires a nonnegative expected participation utility for each private type, averaging over the other types with the player's conditional beliefs. It differs from requiring nonnegative utility at each realized profile, which is ex post individual rationality.

An auction allocates goods using submitted messages and a specified payment rule. Private-value auctions model each bidder's valuation as its own private information. Equilibrium bids depend on the allocation and payment rules, not only on valuations.

In a standard all-pay auction, every player pays its bid or effort cost, and the highest bid receives the prize. With a value $v_i$, unit effort cost, and winning probability $x_i(b)$, player $i$ has quasilinear utility $v_i{x}_i(b)-b_i$. Equal highest bids require an explicit tie rule.

For effective prizes $A_1\ge A_2>0$ and unit effort costs, equilibrium effort CDFs on $[0,A_2]$ are $G_1(b)=b/A_2$ and $G_2(b)=1-A_2/A_1+b/A_1$. The weaker player has an atom at zero. Incremental utilities are $A_1-A_2$ and zero, and winning probabilities are $1-A_2/(2A_1)$ and $A_2/(2A_1)$. Direct payoff indifference and exclusion of larger bids verify the Nash equilibrium. A further player with effective prize at most $A_2$ cannot profit by entering against these distributions.

Each bidder submits one private bid; the highest bidder wins and pays its own bid, while losers pay nothing. A multi-unit version can award one item to each of the highest bidders, each paying its own bid. In a monotone symmetric equilibrium, a bidder can imitate another type's bid when checking incentive constraints.

For a risk-neutral single-parameter bidder with incentive-compatible type reports, interim utility satisfies $u^{\prime }(\theta )=G(\theta )$ wherever the winning probability is continuous. Consequently expected payment is determined by allocation probabilities and the utility of the lowest type. The common normalization $u(0)=0$ must be justified, not obtained from allocation alone.

Two auctions with the same interim allocation probabilities and the same lowest-type utilities have the same interim expected payments under the usual risk-neutral single-parameter incentive conditions. Equal realized payments are not required. This conclusion follows directly from the interim payment identity.

A private-value auction gives each bidder its own value for receiving an item; the value is determined by its own type rather than by another bidder's information. An independent private values model also assumes independence between types.

A bidder with unit demand values receiving one item but obtains no additional value from extra identical units. Selecting two winners means awarding one item to each of two bidders, not two units to one bidder.

This model assigns independent private valuation types to the bidders. Symmetry adds identical type distributions and bidder roles. These assumptions determine interim winning probabilities from the valuation distribution in a monotone symmetric equilibrium.

A mechanism or social choice function is strategyproof if truthful reporting is a weakly dominant strategy: for every true type and every collection of other reports, no misreport yields strictly higher utility or a strictly preferred outcome. This is stronger than merely requiring truthful reports to form a Nash equilibrium.

If a strategyproof social choice function selects $a$, raising $a$ in one agent's order without moving any formerly lower alternative above it preserves the outcome. A different outcome would make one of the changes between the old and new reports a profitable deviation. Arbitrary changes among alternatives wholly above or wholly below $a$ are allowed.

With a finite set of at least three alternatives and unrestricted strict preference orders, every onto deterministic strategyproof social choice function is a dictatorship in social choice. Restricting to two alternatives or to a restricted preference domain removes essential hypotheses.

For an onto strategyproof rule on unrestricted strict preference orders, rank-raising monotonicity implies unanimity and respect for unanimous pairwise preference. Promote each alternative pair to the top two positions in all reports. The selected member depends only on each voter's comparison of that pair. These binary choices form a strict transitive social order: a directed three-cycle would contradict the rule's choice when that triple is placed above all other alternatives, because the chosen member must win both of its binary comparisons. The original outcome is the top of this order. This creates a social ordering with pairwise independence without presuming it as an axiom of the original choice rule.

For two voters and at least three alternatives, pairwise unanimity, pairwise independence and transitivity force the binary social ordering from strategyproof choice to follow one fixed voter. If voter one wins a conflict $a$ against $b$, use profiles $(a>b>c,b>c>a)$ and $(c>a>b,b>c>a)$ to show it also wins $a$ against $c$ and $c$ against $b$. Repeating this implication yields both directions of every pair. If the initial conflict instead follows voter two, exchange the roles. The social choice, being the top of that ordering, is a dictatorship in social choice. This proves the two-voter case of the Gibbard-Satterthwaite theorem.

For two agents and a strategyproof social choice function, if an alternative is selected when one agent ranks it first and the other ranks it last, it is selected whenever the first agent ranks it first, whatever the other agent reports. Changing the first agent's order preserves its attainable top choice; changing the second agent's order cannot offer it an improvement over a selected bottom alternative.

Social choice theory studies how individual preferences determine a collective decision. A social choice function selects one alternative from a preference profile; strategyproofness asks whether agents can benefit by misrepresenting their preferences.

A Condorcet winner defeats every other alternative by a strict majority in pairwise voting. It is unique when it exists. For an odd electorate with single-peaked preferences, the median peak is a Condorcet winner: alternatives on either side lose to the majority whose peaks lie at or beyond the median in the other direction. With an even electorate ties may prevent a strict winner.

A weak Condorcet winner is never defeated by a strict pairwise majority, allowing ties. For even electorates with single-peaked preferences, all alternatives between the two middle peaks have this property. A single-valued selection requires a tie convention; arbitrary tie selection is not automatically strategyproof.

A strict preference order is single-peaked on an axis when moving away from its most preferred alternative along either one side of the axis makes alternatives less preferred. Comparisons between opposite sides need not follow symmetric physical distance. A profile is single-peaked when all voters' orders share such an axis. This restricted domain admits the median voter rule, unlike the unrestricted-domain conclusion of the Gibbard-Satterthwaite theorem.