A Value for n-Person Games

Reference: Shapley, L. S. (1953). A Value for n-Person Games. In H. W. Kuhn & A. W. Tucker (eds.), Contributions to the Theory of Games, Volume II, Annals of Mathematics Studies 28, pp. 307–317. Princeton University Press. DOI · Open access PDF (RAND P-295)

Summary

Shapley asks a deceptively simple question: given a cooperative game in characteristic-function form — a set of players N and a function v assigning each coalition S ⊆ N the total payoff v(S) it can guarantee itself — how much is a seat in the game worth to each player before it is played? He seeks a value: a single number φ_i(v) for each player i representing a fair, a-priori assessment of what that player can expect. Rather than derive the value from a bargaining process, Shapley pins it down axiomatically, imposing three conditions any reasonable notion of fairness should satisfy and then proving that they leave exactly one possibility.

The axioms are: (1) Efficiency / carrier — the values distribute the whole worth of the game, Σ_i φ_i(v) = v(N), and dummy players outside every carrier receive nothing; (2) Symmetry — the value is invariant under relabelling players, so two players who make identical marginal contributions to every coalition receive equal value (equals are treated equally); (3) Additivity — for two independent games, φ(v + w) = φ(v) + φ(w). Shapley’s theorem is that a unique function satisfies all three, and it has the closed form

φ_i(v) = Σ_{S ⊆ N\{i}} [ |S|! (n − |S| − 1)! / n! ] · ( v(S ∪ {i}) − v(S) ).

The formula has a vivid interpretation: imagine the players joining the grand coalition one at a time in a random order, every one of the n! orders equally likely; each player’s value is their expected marginal contribution — the extra worth they bring to the coalition of those who arrived before them, averaged over all arrival orders. This makes fairness operational: each player is credited exactly for what, on average, they add. The Shapley value became the canonical solution concept for fair division, cost allocation (the Shapley–Shubik power index, airport cost-sharing), and — decades later — machine-learning attribution (SHAP feature importances, Data Shapley for data valuation) and fair credit assignment among cooperating agents.

Key Ideas

Characteristic-function game: a game reduced to (N, v) with v(∅) = 0, where v(S) is the worth a coalition S can secure; individual strategies are abstracted away.
Value as an a-priori assessment: φ_i(v) measures a player’s expected worth before play, not the outcome of a specific bargain — a normative allocation rule, not a positive prediction.
Three fairness axioms uniquely determine the value: efficiency (full distribution + dummies get zero), symmetry (equal treatment of interchangeable players), and additivity (linearity across combined games).
Marginal-contribution formula: the value equals the average of a player’s marginal contribution v(S ∪ {i}) − v(S) taken over all n! orderings of the players.
Null / dummy player: a player who adds nothing to any coalition receives zero — a corollary of the axioms, encoding “no reward without contribution”.
Symmetry ⇒ equal pay for equal work: players who are substitutes in every coalition get identical value; this is the axiom that makes the value a fairness concept.
Foundational reach: underpins cost-sharing, voting power (Shapley–Shubik), the Shapley–Folkman results’ economic cousins, and modern SHAP / Data-Shapley attribution.

Connections

Conceptual Contribution

Claim: There is exactly one way to fairly divide the total worth of a cooperative game among its players such that the division is efficient, treats interchangeable players identically, and is additive across independent games — and it credits each player with their expected marginal contribution over a random arrival order.
Mechanism: Model the game by its characteristic function v; impose the efficiency/carrier, symmetry, and additivity axioms; prove a uniqueness theorem; derive the weighted-marginal-contribution formula and its random-ordering interpretation.
Concepts introduced/used: Shapley Value, Cooperative Game Theory, Characteristic Function Game, Marginal Contribution, Fair Division, Credit Assignment, Efficiency axiom, Symmetry axiom, Additivity axiom, Dummy/null player.
Stance: foundational technical paper (axiomatic solution concept).
Relates to: The cooperative-game counterpart to the non-cooperative Nash Equilibrium and to Vickrey’s second-price auction — where Vickrey aligns a winner’s payment with the externality they impose, Shapley distributes the whole surplus by average externality. In multi-agent systems the Shapley value is the canonical tool for fair reward / credit allocation among cooperating agents (cost-sharing, contribution-based payouts, and — in ML — SHAP feature attribution and Data Shapley), making it a natural formal backbone for the fairness questions raised by Deals Among Rational Agents and the cooperation dynamics studied in The Evolution of Cooperation. Its axiomatic style — pin the object down by the properties it ought to have — mirrors the foundational moves in Convention - Lewis and The Strategy of Conflict.

Tags

#game-theory #cooperative-game-theory #shapley-value #fair-division #credit-assignment #mechanism-design #foundations

Backlinks

Linked Pages

The Strategy of Conflict

Reference: Schelling, T. C. (1960). The Strategy of Conflict. Harvard University Press, Cambridge MA. (Reprinted 1980 with new preface.) Harvard UP page · Internet Archive borrow (book; no full-text OA.)

Summary

Schelling reframes game theory as the theory of strategic interdependence — the analysis of decision-making in situations where each party’s best move depends on what they expect the others to do, including in situations of mixed conflict and cooperation. The book opposes the prevailing post-von-Neumann emphasis on zero-sum games and pure conflict; Schelling’s central observation is that almost all real strategic situations have both conflict and cooperation elements, and the interesting analytic work is in the cooperation-within-conflict structure. The book’s most enduring concept is the focal point (or Schelling point): in a coordination problem with multiple equilibria, parties converge on the equilibrium that is salient — distinguished by some feature that “stands out” in the shared cultural / informational background. Schelling demonstrated this experimentally: subjects asked to meet a stranger in New York City on a particular day, with no prior communication, overwhelmingly converged on Grand Central Terminal at noon. There is no equilibrium-selection argument in classical game theory that picks Grand Central; saliency does. Other lasting contributions include the analysis of credible commitment (binding oneself in advance can be a strategic asset, not a constraint); the concept of the threat that leaves something to chance; precommitment via burning bridges; tacit bargaining; and an early treatment of arms-race dynamics. The book inaugurated the modern study of bargaining, conflict resolution, and coordination — and won Schelling the 2005 Nobel Prize in Economics. For agent communication, the central inheritance is the focal-point concept: when explicit communication is impossible or noisy, agents coordinate on salient features of their shared situation. Lewis’s <em>Convention</em> (1969) is its philosophical companion.

Key Ideas

Strategy is interdependent decision: the right object of study is the situation in which each party’s payoff depends on others’ actions, not the isolated decision-theoretic agent.
Mixed-motive games: real conflicts almost always combine conflicting and shared interests; pure-conflict zero-sum games are a degenerate special case.
Focal points / Schelling points: in coordination problems with multiple equilibria, parties converge on the equilibrium that is salient in the shared informational and cultural background. Salience is not derivable from the payoff structure alone — it depends on context, history, prominence, simplicity.
Credible commitment as strategic asset: a party that can publicly bind itself in advance often does better than one with full strategic flexibility, because the binding rules out outcomes the other party would prefer to avoid. Burning bridges, hostage-taking, automatic-response systems, and unilateral declarations are concrete devices.
The threat that leaves something to chance: an irrevocably probabilistic threat (a “doomsday machine” with random triggering, a brinksmanship strategy) can credibly deter when a deterministic threat could not — because the threatener does not control whether it will be carried out.
Tacit bargaining: parties can coordinate on outcomes without explicit communication by relying on shared salience and convention.
Arms-race stability vs instability: Schelling distinguishes situations in which arms accumulation reduces incentives to strike first (stabilising) from those in which it increases them (destabilising) — the foundational analysis behind nuclear deterrence theory.

Connections

Conceptual Contribution

Claim: Strategy is the analysis of interdependent decision-making in mixed-motive (conflict + cooperation) situations; the right concepts include credible commitment, focal-point convergence under saliency, the threat that leaves something to chance, and tacit bargaining. These are not derivable from classical zero-sum game theory.
Mechanism: Reframing of game theory as theory of strategic interdependence; experimental and conceptual demonstrations of focal-point coordination; analysis of commitment devices and probabilistic threats; case studies in industrial bargaining, nuclear deterrence, racial integration, and traffic.
Concepts introduced/used: Focal Point, Schelling Point, Tacit Coordination, Credible Commitment, Threat Leaving Something to Chance, Mixed-Motive Game.
Stance: foundational research monograph (Nobel-Prize-winning).
Relates to: Direct philosophical and analytical companion to Lewis 1969 — both treat the equilibrium-selection problem in coordination games, with Lewis emphasising the social-philosophical structure of mutual expectation and Schelling emphasising the cognitive structure of saliency. The two together supply the foundation for every analysis of how shared meaning, currency, social roles, and (now) ACL semantics arise without explicit agreement. In MAS, the focal-point concept underlies role assignment without communication, emergent coordination conventions in ad-hoc teamwork, and the whole study of zero-shot coordination in MARL. In the ACL evolution programme (Toward Automated Evolution of ACLs, Towards Automating the Evolution of Linguistic Competence), focal points appear implicitly as the salient features that drive lexicon convergence. In LLM-agent settings, focal-point reasoning is one of the principal mechanisms by which agents coordinate without protocols — and a primary attack surface, since what is salient to an LLM is shaped by training data in adversarially exploitable ways.

Tags

#game-theory #schelling #focal-points #coordination #bargaining #foundations #credible-commitment

Convention - Lewis

Convention: A Philosophical Study

Reference: Lewis, D. K. (1969). Convention: A Philosophical Study. Harvard University Press, Cambridge MA. (Reprinted 2002, Blackwell.) SEP entry on Convention · Wiley publisher page (book; no full-text OA.)

Summary

Lewis offers the first rigorous game-theoretic analysis of how shared conventions — including, paradigmatically, the conventions of language — arise and sustain themselves among rational agents without explicit agreement. The book opens by defining a coordination problem: a situation in which several agents have multiple equilibria available, all parties prefer reaching some equilibrium to none, and they are largely indifferent (or have non-conflicting preferences) over which equilibrium they reach. Lewis’s central thesis is that a convention is a regularity in behaviour that is one solution to a coordination problem, sustained by mutual expectation — each party expects the others to follow the regularity, expects the others to expect them to follow it, and so on up an infinite hierarchy that Lewis was the first to formalise as common knowledge. The book applies this analysis to driving conventions (drive on the right vs left), signalling, currency, and at length to language: the conventions of meaning are coordination equilibria sustained by mutual expectation in a population of speakers; semantic content is what would be the case if the convention were followed. Lewis’s framework supplies the philosophical foundation for every later treatment of emergent and negotiated meaning — emergent-communication research in MAS and deep learning, the ACL evolution programme, and the language-games tradition (Wittgenstein operationally, Steels formally) all proceed in the conceptual space Lewis defined. The common-knowledge construction is independently a foundational result for distributed-systems theory (Halpern & Moses 1990) and game theory (Aumann 1976).

Key Ideas

Coordination problem: a strategic situation with multiple Pareto-comparable equilibria where no party prefers a non-equilibrium outcome and the parties’ preferences over equilibria largely coincide. The classical examples — driving side, meeting place — generalise to language, money, social roles.
Convention as a self-sustaining regularity: a regularity R is a convention iff (i) almost everyone conforms to R, (ii) almost everyone expects almost everyone else to conform to R, (iii) almost everyone prefers conforming on the assumption that others conform, and (iv) some alternative regularity could have been the convention instead (no party of the convention is intrinsically preferred).
Common knowledge: the infinite hierarchy of mutual expectation that sustains a convention — A knows that B follows R; A knows that B knows that A follows R; and so on. Lewis was the first to give a formal account of this in social terms; the construction was rediscovered by Aumann in game theory and Halpern–Moses in distributed systems.
Salience and precedent as convention selectors: when multiple equilibria are available, salient features (Schelling’s focal points, see The Strategy of Conflict) and historical precedent select among them. There is no rationality-driven argument for which equilibrium becomes conventional; the answer is contingent on saliency.
Language as convention: meaning is what would obtain if the convention were followed. Truth-conditions, communicative force, and reference are all conventionally fixed — but the convention is not arbitrary, it is sustained by everyone’s expectation that everyone else will use words a particular way.
Conventions vs explicit agreements: Lewis argues that explicit agreement is neither necessary nor sufficient for convention — many conventions arise without agreement (precedent does the work) and many agreements never become conventions (because mutual expectation does not develop).
Population vs pair: conventions are population-level facts; one cannot have a convention with a single partner. Mutual expectation must extend across the relevant community for the regularity to be convention-grade.

Connections

Conceptual Contribution

Claim: Conventions — including the conventions of language — are best analysed as solutions to coordination problems sustained by mutual expectation (formally, common knowledge) in a population of rational agents. There is nothing arbitrary about the convention’s function, but the particular regularity that becomes conventional is contingent on salience, precedent, and historical accident.
Mechanism: Game-theoretic analysis of coordination problems with multiple equilibria; definition of convention via four clauses (conformity, mutual expectation, conditional preference, alternativeness); explicit construction of common knowledge as an infinite hierarchy of expectations; application to driving conventions, signalling, currency, and at length to language semantics.
Concepts introduced/used: Coordination Game, Convention (Lewis), Common Knowledge (Convention), Mutual Expectation, Focal Point (via dialogue with Schelling), Salience, Precedent, Convention vs Agreement.
Stance: foundational philosophical monograph.
Relates to: Direct philosophical foundation for every later treatment of emergent meaning and negotiated language: Steels’ language games are operational realisations of Lewis’s coordination-problem analysis with explicit interaction protocols; Lazaridou et al. and the deep-learning emergent-communication line train neural agents to converge on Lewis-style conventions in referential games. The ACL-evolution programme (Toward Automated Evolution of ACLs, Towards Automating the Evolution of Linguistic Competence) treats the ACL itself as an evolving Lewis-convention. Lewis’s common-knowledge construction is independently the foundation of Halpern & Moses 1990 in distributed systems and Aumann (1976) in game theory — distributed protocols and conventional language share the same mathematical object. The framework also clarifies what is at stake in the Mentalistic Semantics vs Public Semantics debate in ACLs: Lewis-style conventions are public-semantics objects (mutual-expectation regularities) but their stability depends on something close to mentalistic conditions (each agent’s expectations about others’ beliefs), so the two semantic families are dual aspects of the same phenomenon rather than competitors. Why AI Agents Communicate In Human Language revisits Lewis from the LLM-agent angle: natural language is a particular Lewis-convention (a contingent equilibrium) and not necessarily the optimal one for inter-agent coordination.

Tags

#convention #coordination #common-knowledge #lewis #philosophy-of-language #foundations #emergent-meaning

The Evolution of Cooperation

Reference: Axelrod, R. (1984). The Evolution of Cooperation. Basic Books, New York. (Revised 2006 with new afterword by Axelrod and a foreword by Richard Dawkins. Underlying conference papers: Axelrod, R. & Hamilton, W. D. (1981). The Evolution of Cooperation. Science 211(4489), pp. 1390–1396.) Science 1981 DOI · Internet Archive borrow (book)

Summary

Axelrod investigates how cooperation can arise and persist among self-interested agents in the absence of central authority — by running computer tournaments of strategies for the iterated prisoner’s dilemma (IPD). In the one-shot prisoner’s dilemma, defection is the dominant strategy and rational play leads both parties to a Pareto-inferior outcome. Axelrod’s central question is whether iteration changes the picture. He invited game theorists to submit strategies; in two tournaments (1979 and 1980, the second much larger and including strategies designed to exploit the first round’s lessons) tit-for-tat — submitted by Anatol Rapoport, only four lines of code (cooperate on the first move, then copy the opponent’s previous move) — won both. The book’s analytic contribution is identifying why. Axelrod isolates four properties of successful IPD strategies: niceness (never defect first), retaliation (punish defection promptly), forgiveness (return to cooperation as soon as the opponent does), and clarity (be predictable so the opponent can learn to cooperate with you). He proves an evolutionary-stability result: a population of tit-for-tat players cannot be invaded by any non-cooperative strategy if the discount factor (probability of further interaction) is sufficiently high. The book extends the analysis to historical case studies — most famously the live-and-let-live system in WWI trench warfare — and to biological evolution of cooperation in symbiosis and group selection. Axelrod’s framework supplies the foundation for mechanism-design approaches to multi-agent cooperation, the theoretical underpinning of trust-and-reputation systems, and the contemporary literature on cooperative AI.

Key Ideas

Iterated prisoner’s dilemma changes everything: in repeated play with sufficient probability of further interaction, cooperation is rationally sustainable; the shadow of the future makes defection costly.
Tit-for-tat wins both tournaments: the simple strategy of cooperating first, then copying the opponent’s previous move, beats much more sophisticated strategies because it is nice (avoids unprovoked defection), retaliatory (punishes promptly), forgiving (returns to cooperation immediately), and clear (transparent enough that opponents can learn to cooperate).
Four properties of successful strategies: nice (never defect first), retaliating (defect immediately if opponent defects), forgiving (cooperate again as soon as opponent does), clear (recognisable as a tit-for-tat-like strategy).
Evolutionary stability: a population of tit-for-tat players resists invasion by non-cooperative mutants when the discount factor w is high enough (w > (T - R) / (T - P) for the standard payoffs). Cooperation is an evolutionary attractor, not just an analytical curiosity.
Cluster invasion: a small cluster of tit-for-tat players in a sea of all-defect can invade the population if the cluster is large enough that within-cluster interactions dominate cross-cluster interactions — explaining how cooperation can emerge from a non-cooperative starting point.
Trench warfare in WWI: extensive case study of how live-and-let-live systems emerged in static trench positions where the same units faced each other repeatedly — a real-world iterated prisoner’s dilemma in which tit-for-tat-like strategies emerged spontaneously and were eventually suppressed only by the introduction of artillery and unit rotation that reduced the “shadow of the future.”
Recommendations for promoting cooperation: enlarge the shadow of the future (longer-term relationships, more frequent interactions), change the payoffs (reduce the temptation to defect), teach reciprocity, improve recognition (allow opponents to remember each other), enhance retaliation capabilities.

Connections

Conceptual Contribution

Claim: Cooperation among self-interested agents arises and persists in the absence of central authority when interactions are iterated with sufficient probability of further interaction. The successful strategies are nice, retaliating, forgiving, and clear; tit-for-tat is the simplest example. A population of tit-for-tat players is evolutionarily stable; small clusters of cooperators can invade non-cooperative populations.
Mechanism: Two open computer tournaments of IPD strategies; analysis of why tit-for-tat won; isolation of the four properties of successful strategies; evolutionary-stability and cluster-invasion theorems with explicit conditions on the discount factor; case studies (WWI trenches, biological symbiosis); concrete recommendations for institutional design.
Concepts introduced/used: Iterated Prisoners Dilemma, Tit-for-Tat, Reciprocity, Shadow of the Future, Niceness/Retaliation/Forgiveness/Clarity, Evolutionary Stability (in IPD), Cluster Invasion.
Stance: foundational research monograph in cooperative game theory and behavioural economics.
Relates to: Foundational for the trust-and-reputation programme in MAS — Review on Computational Trust and Reputation Models and Inter-Agent Trust Models - A Comparative Study systematise the engineering descendants of Axelrod’s tit-for-tat-with-memory across dozens of computational trust models. Conceptual companion of Lewis (1969) and Schelling (1960) in establishing how cooperation/coordination arise without central authority — the three together supply the standard reading list for emergent-cooperation work in MAS. In the LLM-agent era, the IPD setting is the standard testbed for evaluating cooperative AI; the four properties (nice/retaliating/forgiving/clear) translate directly into design criteria for multi-agent LLM coordination protocols, and the clarity property is particularly relevant to the Why AI Agents Communicate In Human Language critique — natural-language strategies are hard to recognise as tit-for-tat-like, so the cooperation-supporting mechanisms Axelrod identified are weakened. The Cooperative AI research programme (Dafoe et al. 2020) is an explicit modern continuation of Axelrod’s project for the multi-agent LLM era.

Tags

#game-theory #cooperation #axelrod #iterated-prisoners-dilemma #tit-for-tat #reciprocity #foundations #trust

Deals Among Rational Agents

Reference: Rosenschein, J.S. & Genesereth, M.R. (1985). Proceedings IJCAI-85, Los Angeles, CA, pp. 91–99. Source file: rosenschein-genesereth-deals-among-rational-agents.pdf. URL

Summary

Rosenschein and Genesereth present a game-theoretic framework for interactions between intelligent agents with potentially disparate goals. They drop the “benevolent agent” assumption that pervaded early DAI and ask instead: what can purely rational, self-interested agents achieve through communication? The answer is given via payoff matrices, rational offer groups, and binding deals — coalitions of joint moves that no rational agent should unilaterally reject.

They prove that communication, modelled as exchanging offer groups, lets rational agents coordinate on jointly optimal outcomes that are unreachable without communication. The results are illustrated on Prisoner’s Dilemma, multiple-best-plan, and similar bargaining games, showing that binding promises transform defection-prone situations into cooperation. The paper is an early formal bridge between game theory, distributed AI, and agent communication.

Key Ideas

Rejects the benevolent-agent assumption; models agents as utility-maximisers with private goals.
Rational move = a move no agent should ever be persuaded to abandon given common knowledge of rationality.
Offer group = set of joint moves an agent is willing to commit to; deal = intersection of accepted offer groups.
Theorems: existence of non-null rational offer groups; lower bounds on guaranteed payoffs; a Group Rationality Theorem showing communication can dominate no-communication outcomes.
Shows rational cooperation in the Prisoner’s Dilemma once binding deals are available.

Connections

Conceptual Contribution

Claim: Communication among rational, non-benevolent agents can be given a precise game-theoretic semantics in which binding offers transform achievable payoff sets.
Mechanism: Payoff matrices + rationality assumptions (minimal/separate/unique move rationality) + rational offer groups whose intersections define enforceable deals.
Concepts introduced/used: Rational Offer Groups, Binding Deal, Benevolent Agent Assumption, Individual Rationality, Group Rationality.
Stance: foundational/formal (game-theoretic).
Relates to: Shoham’s Agent-Oriented Programming cites this work as one of the key precursors for modelling agent societies without assuming shared goals; AGENT-0’s “commit” primitive is the programming-language analogue of the binding deals formalised here. The paper also foreshadows Negotiation protocols, auction-based coordination, and modern Mechanism Design for MAS.

Tags

Counterspeculation Auctions and Competitive Sealed Tenders

Counterspeculation, Auctions, and Competitive Sealed Tenders

Reference: Vickrey, W. (1961). Counterspeculation, Auctions, and Competitive Sealed Tenders. The Journal of Finance, 16(1), pp. 8–37. DOI · Open access PDF (Princeton)

Summary

Vickrey provides the first systematic game-theoretic analysis of auction formats and proves the result that established the field of mechanism design: in a sealed-bid second-price auction (now called the Vickrey auction), the dominant strategy for each bidder is to bid their true valuation. The proof is short and constructive: bidding above one’s value risks winning at a loss; bidding below risks losing an item one would have profitably won; bidding exactly one’s value is weakly better than any other bid against any opponent strategy. The auction is therefore strategy-proof: bidders need not engage in counter-speculation about what other bidders will do, because their best response is independent of the other bidders’ strategies. Vickrey also analyses the four classical auction formats — English (ascending open-cry), Dutch (descending open-cry), first-price sealed-bid, second-price sealed-bid — proves the revenue equivalence of English and second-price (with rational bidders), and the corresponding equivalence of Dutch and first-price. The paper inaugurates mechanism design as the formal study of how to construct strategic interactions whose equilibria yield desired outcomes — in particular, truth-telling equilibria. Vickrey won the 1996 Nobel Prize for this and related work; the Vickrey-Clarke-Groves (VCG) family generalises the second-price auction to multi-item and combinatorial settings, and underpins almost all sponsored-search auctions, spectrum auctions, and modern auction-based resource allocation. For multi-agent systems, Vickrey is the canonical truthful mechanism: a setup in which agents need not strategise about each other to play optimally, eliminating the regress of theory-of-mind reasoning that Pact-style choreographies otherwise require.

Key Ideas

Sealed-bid second-price auction: each bidder submits a sealed bid; the highest bidder wins but pays the second-highest bid (the highest losing bid). The pricing rule is the key innovation.
Truth-telling is a dominant strategy: bidding one’s true valuation v_i is weakly optimal against every opponent strategy. Bidding above risks paying more than v_i; bidding below risks losing an item worth more than the price one would have paid. Independent of opponents’ beliefs and strategies.
Strategy-proofness as a design property: a mechanism is strategy-proof iff truth-telling is a dominant strategy for all participants. Strategy-proof mechanisms eliminate the counterspeculation burden — agents need not model each other.
Revenue equivalence (special case): English and second-price auctions yield the same expected revenue with rational bidders; Dutch and first-price likewise. (The full Revenue Equivalence Theorem, due to Myerson 1981 and others, generalises far beyond these four.)
Inefficiency of first-price auctions: in first-price sealed-bid, bidders shade their bids below true valuation by an amount that depends on beliefs about other bidders — strategic, but not necessarily efficient. The second-price design eliminates this distortion.
Foundations of mechanism design: the paper establishes the conceptual programme of designing games whose equilibria yield socially desirable outcomes, with truth-telling as one canonical objective. VCG (Clarke 1971, Groves 1973) generalises second-price to multi-item and combinatorial settings using the same incentive principle.
Why second-price works: the price a winner pays is the externality they impose on the rest of the bidders — the value the next-best bidder would have obtained had the winner not been there. Aligning private cost with social externality drives truthful behaviour.

Connections

Conceptual Contribution

Claim: A sealed-bid auction in which the winner pays the second-highest bid makes truth-telling a dominant strategy for every bidder. Mechanism designers can therefore construct auctions in which agents need not strategise about each other to play optimally — the counterspeculation burden is eliminated. This launches the formal study of mechanism design: constructing games whose equilibria yield desired outcomes.
Mechanism: Sealed-bid auction with second-price pricing; explicit dominance argument for truthful bidding; comparison of English / Dutch / first-price sealed-bid / second-price sealed-bid auctions; establishment of revenue equivalence between English and second-price; analysis of bid-shading in first-price auctions.
Concepts introduced/used: Vickrey Auction, Second-Price Auction, Truthful Mechanism, Strategy-Proof, Counterspeculation, Mechanism Design, Revenue Equivalence, Externality-aligned pricing.
Stance: foundational technical paper (Nobel-Prize-winning).
Relates to: Foundational paper for the entire field of Mechanism Design (Hurwicz, Maskin, Myerson, Roth — five Nobel Prizes between them); the Vickrey-Clarke-Groves family (Clarke 1971, Groves 1973) generalises second-price to combinatorial and multi-item settings and is the analytical core of all major sponsored-search and spectrum auctions. In MAS, Vickrey auctions appear as the canonical truthful resource-allocation mechanism — used in agent-based market designs since the 1980s, in cloud-computing resource auctions, and in academic LLM-agent negotiation testbeds. Conceptually, the strategy-proofness property eliminates the theory-of-mind regress that motivates Pact’s level-ℓ bounded-rational solver: when the mechanism is strategy-proof, bidders’ best moves do not depend on their beliefs about others, so the recursion collapses to depth 1. This is one of the strongest design principles for agent-coordination protocols: prefer mechanisms in which truth-telling is a dominant strategy over mechanisms requiring strategic reasoning. Vickrey’s analysis of revenue equivalence also frames the larger trade-off in protocol design between individual rationality (each agent prefers participating to not) and efficiency (the mechanism produces a socially-optimal allocation) — the same trade-off Deals Among Rational Agents (Rosenschein & Genesereth 1985) takes up for general multi-agent deal-making.

Tags

#mechanism-design #vickrey #auctions #truthful-mechanism #strategy-proof #game-theory #foundations

Nash Equilibrium

A strategy profile from which no player can gain by unilaterally deviating. In multi-agent systems with communication failures, the set of Nash equilibria reached by best-response dynamics can include arbitrarily poor outcomes — the core negative result of the Gopalakrishnan et al. resilience analysis.

In this vault

Credit Assignment

(page does not exist)

Fair Division

(page does not exist)

Marginal Contribution

(page does not exist)

Characteristic Function Game

(page does not exist)

Cooperative Game Theory

(page does not exist)

Shapley Value

(page does not exist)

Mechanism Design

The branch of game theory that designs interaction rules so that self-interested agents, acting in equilibrium, produce a desired social outcome; applied in ACL evolution to shape negotiation protocols that reach efficient linguistic conventions.

In this vault

Toward Automated Evolution of ACLs

Cost Sharing

(page does not exist)

A Value for n-Person Games

Summary

φ_i(v) = Σ_{S ⊆ N\{i}} [ |S|! (n − |S| − 1)! / n! ] · ( v(S ∪ {i}) − v(S) ).

Key Ideas

Characteristic-function game: a game reduced to (N, v) with v(∅) = 0, where v(S) is the worth a coalition S can secure; individual strategies are abstracted away.
Value as an a-priori assessment: φ_i(v) measures a player’s expected worth before play, not the outcome of a specific bargain — a normative allocation rule, not a positive prediction.
Three fairness axioms uniquely determine the value: efficiency (full distribution + dummies get zero), symmetry (equal treatment of interchangeable players), and additivity (linearity across combined games).
Marginal-contribution formula: the value equals the average of a player’s marginal contribution v(S ∪ {i}) − v(S) taken over all n! orderings of the players.
Null / dummy player: a player who adds nothing to any coalition receives zero — a corollary of the axioms, encoding “no reward without contribution”.
Symmetry ⇒ equal pay for equal work: players who are substitutes in every coalition get identical value; this is the axiom that makes the value a fairness concept.
Foundational reach: underpins cost-sharing, voting power (Shapley–Shubik), the Shapley–Folkman results’ economic cousins, and modern SHAP / Data-Shapley attribution.