game-theory.
41 of 1538 NOTE documents. Back to the full index.
| # | Title | Summary | Status |
|---|---|---|---|
| NOTE-037 v2 | Debreu 1952, a social equilibrium existence theorem | Debreu proves existence of an equilibrium for an “abstract economy” (generalized game), in which each agent’s feasible set A_ι(ā_ι) depends on the others’ actions. The conditions: each action set 𝔄_ι is a contractible polyhedron; A_ι has a closed graph with non-empty compact values; f_ι is continuous on the graph into the extended reals; the value function φ_ι(ā_ι) = max f_ι is continuous; and each best-response set M_ā_ι is contractible. The proof applies the Eilenberg–Montgomery/Begle fixed-point theorem to the product best-response map. A Remark replaces the joint continuity of φ_ι with continuity (lower hemicontinuity) of A_ι plus a compact graph. A Corollary gives a saddle-point theorem that contains Kakutani’s and von Neumann’s. | Read |
| NOTE-395 | Hindriks & Guala — Institutions, rules, and equilibria | Institutions are correlated equilibria of coordination games with several equilibria, represented by the players as rules. Searle’s constitutive rules are derived from a regulative rule by coining a term that splits it into a base rule and a status rule; the term is conservative and eliminable, so constitutive rules add a name and cognitive economy, not a new kind of fact. The derivation is shown for one toy institution and asserted in general. The reply adds that normativity needs no constitutive rules, because a right is a bundle of other people’s regulative obligations. | Read |
| NOTE-404 | The Logic of Animal Conflict | Five strategies for contests with dangerous weapons, simulated 2,000 times per pairing with payoffs +60 win, −100 serious injury, −2 per scratch, up to +20 for brevity. Hawk is not an ESS; Retaliator is called one though Mouse ties it, so by the paper’s own second condition it is only neutrally stable. In a war of attrition no pure strategy is stable; the exponential mixture p(x) = (1/v)e^(−x/v) is. Individual selection can explain limited war. No Hawk–Dove game, no ownership. | Read |
| NOTE-408 | Curry 2016, morality as cooperation: a problem-centred approach | The founding statement of morality-as-cooperation. Nonzero-sum game theory gives seven cooperation problems (kin, coordination, exchange, hawk and dove contest displays, division, possession), and their solutions are said to be what morality is. Each domain gets an animal case, a human case and quotations from moral philosophers. No data are reported. The sharpest content is the predictions on pp. 39–40: non-cooperative behaviour is morally neutral, no culture moralizes “aesthetics or nutrition”, and religious morality and food taboos will turn out cooperative. | Read |
| NOTE-409 | Five Rules for the Evolution of Cooperation | A four-page review. Five mechanisms, each with a b/c threshold derived from a 2×2 game: kin selection r > c/b, direct reciprocity w > c/b, indirect reciprocity q > c/b, network reciprocity b/c > k, group selection b/c > 1 + n/m. For kin, network and group mechanisms the same condition makes cooperators ESS, risk-dominant and advantageous; for the reciprocities RD and AD need more. Derivations are in the unread supplement; the review itself proves nothing. | Read |
| NOTE-411 | The Evolution of Cooperation | TIT FOR TAT won Axelrod’s two tournaments (14 entries plus random, 200 moves; 62 entries, expected 200 moves) and went to fixation in an ecological replay. Against it, only ALL D or alternation need be checked, so no strategy does better iff w ≥ (T−R)/(T−P) and w ≥ (T−R)/(R−S). ALL D is stable for all w; kinship or a cluster with enough in-cluster interactions lets reciprocity in, and a nice stable strategy resists clusters. ALL C ties with TIT FOR TAT, so stability is neutral, not strict. | Read |
| NOTE-443 | Précis of Breakdown of Will | Hyperbolic discounting makes preference reverse with delay alone, so a person is a population of interests that forestall one another. Will is the recursive bundling of choices by treating each as a precedent, which gives an intertemporal repeated prisoner’s dilemma and makes Kavka’s toxin rational to drink. The same recursion predicts legalism, “lapse districts”, motivated misperception and compulsive over-control, and premature satiation of appetite limits what will can do for emotional reward. | Read |
| NOTE-554 | List — Three kinds of collective attitudes | Aggregate attitudes: a rule or market summarises members’ attitudes; proposition-wise supervenience; no direct role; rationality contingent (majority beliefs on p, q, p∧q can be inconsistent, Table 1). Common attitudes: all hold, with common awareness; enriched proposition-wise supervenience; coordination; consistent by unanimity. Corporate attitudes: a group agent’s; holistic supervenience, like non-reductive physicalism; action-guiding; rationality presupposed. Three lessons of near-independence; Table 2 summarises. | Read |
| NOTE-563 | Beyond Markets and States: Polycentric Governance of Complex Economic Systems | Ostrom’s retrospective. Polycentric arrangements, many formally independent decision centres, can outperform single hierarchies. Long-surviving common-pool resource institutions share eight design principles, not specific rules. In experiments communication and self-chosen sanctions sustain cooperation, and in the field local monitoring predicts outcomes. No single regime type is a panacea. | Read |
| NOTE-613 | That’s what she (could have) said | Recursive Bayesian speaker–listener reasoning yields specificity implicatures but cannot derive Horn’s principle from utterance costs alone; letting the agents be uncertain about the lexicon breaks the symmetry, so costlier signals go to less likely meanings in one-shot games without equilibrium refinements, and two online games with novel symbols show people drawing both implicatures without prior conventions. | Read |
| NOTE-646 | Combining contextuality and causality | Extends sheaf-theoretic contextuality to causal scenarios by an enabling relation on measurements and a game reading: Nature’s deterministic strategies, which may depend on causal history, replace the event sheaf, and the Abramsky–Brandenburger definitions then go through. Recovers flat contextuality and causal Bell scenarios, and expresses adaptive MBQC by Experimenter strategies. The strategy presheaf is not a sheaf: compatible deterministic local strategies can have no gluing or several. | Read |
| NOTE-717 | Kamenica & Gentzkow — Bayesian Persuasion | With a common prior and a sender who commits to a signal the receiver sees, any distribution of posteriors whose mean is the prior can be induced, so the sender’s best value is the concave closure of its posterior-value function at the prior (Corollary 2). A fully informed, fully rational receiver can be moved; at the optimum she is indifferent whenever she acts for the sender. The paper never cites Blackwell, does not analyse manipulation, and has the receiver know the design. | Read |
| NOTE-795 | Handfield et al. — Cooperative Dilemmas in Rational Debate | Two debaters move through a Betz-style space of truth assignments, each moving minimally when refuted, with payoff u = w·v − d (true beliefs against changes of mind). At moderate truth weights the truth-optimal equilibrium is asymmetric: one debater argues boldly and the other free-rides with a compromise strategy, a snowdrift dilemma. At low weights, or with error, both exit. In a narrow borderline region of mixed equilibria, raising the weight on truth lowers collective accuracy. A two-person model, n = 3 propositions, and every result is numerical. | Read |
| NOTE-1033 | Kleinberg and Raghavan — Algorithmic monoculture and social welfare | Two firms each hire the best available candidate by either a private noisy ranking or one shared algorithmic ranking. If, at equal accuracy, a second mover prefers an independent ranking (preference for the first position) and is better off after a less accurate competitor (preference for weaker competition), then for every human accuracy there is a more accurate algorithm that both firms strictly prefer to use, yet both are worse off, and so is welfare, than if neither used it. The Mallows model meets the conditions for every candidate distribution; Gaussian and Laplacian random utility models meet them for three candidates; Plackett–Luce never does. | Read |
| NOTE-1034 | Bergemann and Morris — Information design, a unified perspective | A designer who can commit to how players are informed, but not to what they do, can attain exactly the Bayes correlated equilibria: joint distributions of states and actions in which no player, told his recommended action, wants to deviate. The set is a polytope given by linear obedience constraints, so information design is a linear program over it. Read literally there is a designer; read metaphorically the set bounds what any information structure could produce. More prior information shrinks the set. Public signals serve a designer who wants correlated actions, private ones the reverse. Its two-firm example with strategic substitutes misstates the optimal rule for the parameters it assumes. | Read |
| NOTE-1116 | Flows and Decompositions of Games: Harmonic and Potential Games | A finite game is read as a flow, the unilateral payoff differences on the graph of strategy profiles, and the Helmholtz decomposition of that flow splits the game uniquely into potential, harmonic and nonstrategic parts. Potential games are those with no harmonic part. Harmonic games, the pure-conflict part, generically have no pure equilibrium. The nearest potential game is a closed-form l2 projection. | Read |
| NOTE-1132 | Soma et al. — The hive mind is a single reinforcement learning agent | A short theoretical paper with simulations. In an infinite, well-mixed population, imitation of success has the expected update of Cross Learning, and the weighted voter model of the honey-bee waggle dance that of Maynard-Cross Learning, the Maynard-Smith replicator dynamic. The population’s type distribution is the policy of a stateless bandit agent, each member is one parallel sample of it, and no member learns. The authors keep the biology partial and the simulations qualitative. | Read |
| NOTE-1139 | Miller, Resnick and Zeckhauser — Eliciting informative feedback: the peer-prediction method | A mechanism-design paper with proofs and a worked example. A center with no ground truth pays each rater a strictly proper scoring rule applied to the posterior over a reference rater’s report implied by her own report. Truth-telling is a strict Nash equilibrium, payments can be scaled to buy effort and balanced among raters, and coarse reports can be elicited for two types. Uninformative equilibria remain, and collusion, risk aversion, unelicited private signals and trust in the center are left as limits. | Read |
| NOTE-1140 | Kaisers & Tuyls — Frequency adjusted multi-agent Q-learning | A short algorithmic paper with plotted experiments. The selection–mutation model of Boltzmann Q-learning (Tuyls et al. 2003, 2005) assumes every Q-value changes at rate α; in Q-learning only the chosen action’s does, so its expected change carries a factor x_i, and Q-learning departs from the model depending on initialization. A frequency-adjusted update removes the factor and matches the model. Three 2×2 games, one temperature, no quantitative measure of fit. | Read |
| NOTE-1141 | Son et al. — QTRAN: learning to factorize with transformation | Defines Individual-Global-Max (IGM): per-agent values factorise a joint value when the profile of individual argmaxes is the joint argmax. Additivity and monotonicity are sufficient conditions; QTRAN trains the sum of individual values plus a state value to equal the joint value at the greedy profile and bound it elsewhere, which is sufficient and, up to rescaling, necessary. Every single-state matrix game satisfies IGM; VDN and QMIX missed the optimum in 177 of 310 random 3×3 games. | Read |
| NOTE-1142 | Hart & Mas-Colell — A simple adaptive procedure leading to correlated equilibrium | A theorem with a proof. Regret matching, switching from one’s last action to each alternative with probability proportional to the positive regret for not having made that switch in the past, drives the empirical joint distribution of play almost surely to the set of correlated equilibria when every player uses it. Regrets vanish exactly when the empirical distribution approaches that set. A stylized variant is analysed by Blackwell approachability; the main procedure needs inertia and needs players to see one another’s past play. | Read |
| NOTE-1143 | Balduzzi et al. — Open-ended learning in symmetric zero-sum games | A framework paper with an algorithm and two small experiments. Symmetric zero-sum games between parametrized agents split into transitive and cyclic parts relative to a measure on agents. In a cyclic game an individual’s performance is meaningless, so evaluation moves to populations: the value of the game between them, which is invariant to redundant members, and the convex hull of their evaluation rows. Training each supported agent on what it beats grows that hull. | Read |
| NOTE-1144 | Sato & Crutchfield — Coupled replicator equations for the dynamics of learning in multiagent systems | A four-page letter. Two agents choose by softmax over reward memories that decay at rate α; with learning slow relative to play, each agent’s choice distribution follows a replicator dynamic in the other’s play plus α Σ_j x_j log(x_j/x_i), a pull towards uniform play. Without decay the system is conservative, Hamiltonian in zero-sum games; with decay it is dissipative. Rock–scissors–paper simulations show tori, Hamiltonian chaos, heteroclinic transients, limit cycles and chaotic attractors. Derivation plus numerics, no data. | Read |
| NOTE-1146 | Czarnecki et al. — Real world games look like spinning tops | A hypothesis paper with theorems and sampled empirical games. Where players can signal n bits before the outcome is settled, every win–loss pattern on 2ⁿ strategies occurs, so cycles are astronomically long. Nash clustering layers any symmetric zero-sum game, and beating a whole cluster guarantees climbing. Sampled games show cluster size peaking at middling strength. The body says the geometry is not proved, the abstract says it is. Two of the smaller results have defective statements or proofs. | Read |
| NOTE-1148 | Yang et al. — Mean field multi-agent reinforcement learning | An algorithms paper with a convergence proof and three experiments. Each agent’s Q-function is approximated by its interaction with the mean action of its neighbours, which makes many-agent RL tractable for hundreds of homogeneous agents. Mean field Q-learning converges to a Nash Q-value under strong assumptions, learns Gaussian Squeeze with 500 and 1000 agents where baselines fail, matches MCMC on a 20 × 20 Ising model, and wins a 64-versus-64 battle game. | Read |
| NOTE-1149 | Börgers & Sarin — Learning through reinforcement and replicator dynamics | A short theoretical paper. One Bush–Mosteller learner with payoffs in (0, 1), Cross’s model, moves in expectation as a population under the discrete replicator step, and in the continuous-time limit follows the Taylor replicator dynamic at any finite time. For every learning speed, though, the discrete process is absorbed in a pure strategy profile with probability one. With negative payoffs a probability-matching force enters beside a replicator force. Proofs are by Euler’s method and Norman’s theorems on slow learning; the negative-payoff limit is stated with its proof omitted. | Read |
| NOTE-1150 | Foerster et al. — Learning with opponent-learning awareness | A LOLA learner maximises its return after the opponent’s anticipated naive gradient step and differentiates through that step, adding a second-order term to its gradient. Two exact-gradient LOLA learners reached tit-for-tat-like reciprocity in the memory-one iterated prisoner’s dilemma where naive learners ended at mutual defection, and settled at the mixed equilibrium of iterated matching pennies where naive learners did not converge. A policy-gradient version cooperated in the Coin Game, less reliably with a learned model of the opponent. | Read |
| NOTE-1151 | Leibo et al. — Multi-agent reinforcement learning in sequential social dilemmas | A descriptive simulation study. It defines sequential social dilemmas, Markov games whose learned cooperative and defecting policies give social-dilemma payoffs, and runs independent deep Q-learners on two two-player games. Scarcity and costly conflict produce aggression in Gathering; group benefit produces joint hunting in Wolfpack; and network size moves defection in opposite directions in two games that both embed a Prisoner’s Dilemma. | Read |
| NOTE-1152 | Foerster et al. — Counterfactual multi-agent policy gradients | A centralised critic Q(s, τ, u) trains decentralised actors, and each agent’s action is scored against the critic’s average over its own alternatives under its own policy, the others’ actions fixed. The baseline does not change the expected gradient. On StarCraft micromanagement with a narrow field of view it beat independent and central-V/QV actor-critics on four maps. The counterfactual is the critic’s estimate, not a simulation, and it values alternatives the agents sometimes take. | Read |
| NOTE-1153 | Wolpert & Tumer — Optimal reward functions in distributed reinforcement learning | Members of a collective each run a reinforcement learner on a private utility, and the designer wants the world utility G maximised. A private utility is factored when it orders a member’s own alternatives, others fixed, as G does; this holds exactly when it is an increasing function of G given what the member cannot affect. The Wonderful Life Utility, G minus G with the member’s effect set clamped, is factored and easier to learn than G. In a 60-agent bar problem, clamping to the average action did best, clamping to absence nearly as well, G worst. | Read |
| NOTE-1154 | Rashid et al. — QMIX: monotonic value function factorisation | Per-agent values Q_a(τ^a, u^a) are combined into a joint Q_tot by a mixing network whose weights, generated from the state, are kept non-negative, so ∂Q_tot/∂Q_a ≥ 0. Then the individually greedy actions form a greedy joint action and agents can act on their own values. It represents more than a sum and learned the optimum of a two-step game that a sum misses; it cannot represent a joint value in which one agent’s best action depends on the others’ current actions. | Read |
| NOTE-1155 | Balduzzi et al. — Re-evaluating evaluation | A methods paper with two short applications. It reads evaluation data as antisymmetric matrices. Elo is then the row mean of the log-odds, exact when they are curl-free and movable by copies, and the Schur decomposition gives a multidimensional Elo. Nash averaging scores agents and tasks against the maximum-entropy Nash equilibrium of a zero-sum meta-game. Its proved invariance covers exact copies, and only when that equilibrium is unique. A checked counterexample shows what happens otherwise. | Read |
| NOTE-1156 | Omidshafiei et al. — α-Rank: multi-agent evaluation by evolution | A methods paper with theory and applications. Agents are ranked by the stationary distribution of a finite-population, rare-mutation Fermi imitation chain on pure profiles, unique at every finite α. As α grows its transitions become those of Markov-Conley chains, the sinks of the better-response graph, which the paper ties to chain components of the replicator flow. The limit of the ranking is not characterized, and it is not invariant to copies. | Read |
| NOTE-1159 | Kwon and Perchet — Blackwell approachability with partial monitoring: optimal convergence rates | Approachability of a polytope (reduced to the negative orthant) under partial monitoring, where the decision maker sees only a random signal whose law is known, can be achieved at rate O(T^-1/3) in expected distance for general signals and O(T^-1/2) when the signal law does not depend on the decision. The general algorithm lifts the problem to an auxiliary full-information approachability problem that is linear in the flags, and keeps a uniform exploration floor γ ∝ T^-1/3 so that the flags can be estimated by importance weighting. | Read |
| NOTE-1162 | Lattimore and Szepesvári — Cleaning up the neighborhood: a full classification for adversarial partial monitoring | Completes the classification of finite partial-monitoring games against oblivious adversaries to every game, degenerate and duplicate actions included: 0 with no neighbouring pair, Θ̃(√n) locally observable, Θ(n^2/3) globally but not locally observable, Ω(n) otherwise. The missing piece is NeighborhoodWatch2, which redistributes probability onto degenerate actions in proportion to the neighbours they lie between and has a high-probability √n bound. It corrects Bartók et al.’s T^2/3 lower-bound proof, whose separating direction ignored the degenerate actions’ signals. The preprint, not the published text, also says the earlier localisation argument exchanged an expectation and a maximum. RelExp3 gives point-locally observable games an asymptotic constant depending only on K_loc, F and log K, and a factor linear in F is shown to be necessary. | Read |
| NOTE-1164 v2 | Bartók, Foster, Pál, Rakhlin and Szepesvári — Partial monitoring: classification, regret bounds and algorithms | For finite partial-monitoring games the minimax regret takes exactly four rates: 0 with one non-dominated action, Θ̃(√T) when every pair of neighbouring actions is locally observable, Θ(T^2/3) when the game is globally but not locally observable, and Θ(T) otherwise. The conditions are linear algebra on loss and signal matrices: a loss difference must lie in the span of the row spaces of the signal matrices of the actions allowed to estimate it. The stochastic classification covers every game; the adversarial one covers non-degenerate games only. | Read |
| NOTE-1279 | Activating the legacy motive mitigates intergenerational discounting in the climate game | A climate collective-risk game with 30 groups of six. When saving the group’s endowments paid the players the next day, 9 of 10 groups reached the target; when it paid for trees for future generations, 2 of 10 did; with three messages added to activate the legacy motive (death awareness, the powerlessness of future generations, and paying forward a past generation’s sacrifice), 7 of 10 did. Each message raised investment. The messages restored a fair-share norm rather than extra giving. No manipulation checks and no control message, so which mechanism worked is unknown. The authors call the legacy motive a way of leveraging self-interest. | Read |
| NOTE-1288 | Team Reasoning and Intentional Cooperation for Mutual Benefit | Theories of social preference can always fit an observed choice by positing a preference for it, and their non-trivial forms cannot represent trust: on Rabin’s intention-based preferences, (send, return) in a Trust Game cannot be common knowledge in equilibrium. Team reasoning can, but Bacharach’s version maximizes a team utility that trades members off and needs no assurance. Sugden’s Schema of Cooperative Team Reasoning aims at a mutually beneficial practice, in which each member gains over her maximin payoff, and binds only when there is reciprocal reason to believe the others endorse it. A market exchange in each party’s interest can then be intended as cooperation for mutual benefit. | Read |
| NOTE-1410 | Akkoyunlu, Ekanadham and Huber — Some constraints and tradeoffs in the design of network communications | A design paper on interprocess communication in networks of sequential processes: complete status of a transaction is impossible in an arbitrary distributed facility and, with time-outs, even in a reliable one, and the insertion property forces the system to withhold status. Its Appendix states, as a story of gangsters and a messenger who may be mugged, that no finite exchange over a lossy channel brings two parties to know they agree a message got through, with a shortest-sequence proof. That is the coordinated attack problem in substance, three years before Gray (1978), framed as mutual knowledge of delivery. | Read |
| NOTE-1427 | Apt — Potential Games (slides) | Apt’s slides define exact, ordinal and generalized ordinal potentials and the finite improvement property, and state, crediting Monderer and Shapley 1996, that a finite game has a generalized ordinal potential if and only if it has the FIP; one direction is proved and the converse sketched by counting improvement sequences. A two-by-two game with the FIP and no ordinal potential shows the equivalence cannot be with ordinal potentials. | Read |
| NOTE-1436 | Putnam — Diplomacy and domestic politics: the logic of two-level games | Models international negotiation as two linked games: a chief negotiator bargains abroad (Level I) over a deal that must be ratified at home (Level II), so agreement is possible only where the domestic win-sets overlap. Win-set size depends on domestic preferences and coalitions, ratification institutions and the negotiator’s strategy, and its effects are two-edged: a small win-set is a bargaining advantage and a risk of involuntary defection. Synergistic linkage, reverberation and the negotiator’s own veto follow. Nothing in it makes the time horizons of a polity’s parts decide which part holds authority. | Read |