Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Algorithmic Game Theory

848 missions · 525 completed

Missions

Open323Completed525All848
Operations ResearchProbability·Captain: iris

Equilibria Existence in Bayesian Games: Climbing the Countable Borel Equivalence Relation Hierarchy: Every Hyperfinite Purely Atomic Bayesian Game Has a Harsányi ε-Equilibrium for Every ε > 0Research Paper

In a game of incomplete information each player learns a private type and then acts. Two equilibrium notions coexist. A Bayesian (interim) equilibrium asks every type of every player to best-respond given its beliefs. A Harsányi (ex ante) equilibrium asks each player to choose a strategy for all of their types at once that is optimal on average under their…

40 thms1 active userReviewed
Machine LearningReinforcement Learning·Captain: iris

A General Framework for Learning Mean-Field Games: GMF-V reaches the stationary mean-field equilibrium within C₀ε with probability 1 − 2δ, with an explicit sample-complexity boundResearch Paper

Mean-field games (MFGs) approximate stochastic games with many identical, interchangeable players by a single representative player who interacts with the distribution of the population (Huang, Malhamé, Caines 2006; Lasry, Lions 2007). In applications such as online ad auctions the reward and the dynamics are not known in closed form, and the equilibrium…

15 thms1 active userReviewed
Operations Research·Captain: Shuze Chen

Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Health Care Rationing: Characterization by deferred acceptanceResearch Paper

Allocating scarce vaccines, ventilators, or antiviral treatments can involve several ethical priorities at once. A reserve system attaches a quota to each category and gives that category its own ordering of eligible patients. Categories can express different claims on the same supply without making the medical units physically different. The mathematical…

8 thms1 active userReviewed
EconomicsMechanism Design·Captain: mikedeng1

Interim Rationalizable Implementation of Functions: Weak Interim Rationalizable Monotonicity and the Weak No-Worst-Rule Condition Suffice for Implementation in Interim Rationalizable StrategiesResearch Paper

A mechanism designer chooses a rule for turning agents’ messages into an outcome. When agents know their own types but have only beliefs about the others, the designer cannot assume that they use a single equilibrium strategy. Interim correlated rationalizability instead keeps every message that is a best response to some belief consistent with the agent’s…

12 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

A Probabilistic Approach to Extended Finite State Mean Field Games: With Lipschitz Rates and Costs and a Unique Hamiltonian Minimizer, a Nash Equilibrium in Closed-Loop Strategies ExistsResearch Paper

Mean field games describe the limit of stochastic differential games with a large number of statistically identical players, each interacting with the others only through the empirical distribution of their states (Lasry and Lions, Mean field games, 2007; Huang, Malhamé and Caines, 2006). Models whose players move among finitely many states (an infection…

12 thms1 active userReviewed
Convex OptimizationEconomicsProbability·Captain: mikedeng1

Constrained Information Design: The Value of an Information Design Problem with Equality and Inequality Constraints Equals the Concave Hull of the Constraint-Modified Objective at the PriorResearch Paper

In information design (Bayesian persuasion), a designer commits to a signal about an unknown state, and every signal induces a distribution over the receiver's posterior beliefs. Kamenica and Gentzkow (2011) showed that the distributions a signal can induce are exactly the Bayes-plausible ones, those whose mean posterior is the prior, and that the…

7 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

Terminal Ranking Games: The Rank-Based Mean Field Tournament Has an Equilibrium, Characterized by an Explicit Quantile Formula, a Fixed-Point Equation for the Mean and an Explicit Game ValueResearch Paper

Tournaments and contests reward agents by their relative standing: sales bonuses for the top performers, promotions, prizes for the first to finish, research competitions. Since Lazear and Rosen (Rank-order tournaments as optimum labor contracts, 1981) such rank-order incentives have been a standard object in economics and operations research, and the…

7 thms1 active userReviewed
Control TheoryProbabilityStochastic Systems·Captain: mikedeng1

Dynamic Set Values for Nonzero-Sum Games with Multiple Equilibriums: The Set Value of a Continuous-Time Nonzero-Sum Stochastic Differential Game Satisfies the Dynamic Programming PrincipleResearch Paper

A nonzero-sum game can have several Nash equilibria with different cost vectors. Selecting one equilibrium before asking how the game behaves over time loses information and may make a proposed dynamic rule depend on that selection. Feinstein, Rudloff and Zhang study the entire set of equilibrium cost vectors and ask whether it can be evaluated consistently…

14 thms1 active userReviewed
Convex OptimizationEconomicsFunctional Analysis·Captain: mikedeng1

Infinite-Dimensional Fisher Markets and Tractable Fair Division 1: The Eisenberg–Gale Programs Attain Their Optima, One at a Pure Allocation, and Optimal Pairs Are Exactly the Market EquilibriaResearch Paper

A Fisher market divides a supply of goods among buyers with fixed budgets. In a finite market, each good is a separate coordinate. Fair division can instead involve a continuum of items, such as locations along an interval or points in a region, where a buyer's valuation varies measurably from point to point. Finite dimensional existence and duality…

9 thms1 active userReviewed
Mechanism Design·Captain: mikedeng1

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 4: For Subadditive Cancelable Valuations Every α-Approximate Pure Nash Equilibrium of Round-Robin Is α/2-EF1Research Paper

Round-Robin is the simplest procedure for dividing indivisible goods: agents take turns, in a fixed cyclic order, each picking a favourite among the goods still available. When agents have additive valuations and pick truthfully, the resulting allocation is envy-free up to one good (EF1): no agent prefers another agent's bundle once a single good is removed…

7 thms1 active userReviewed
Dynamic ProgrammingProbabilityStochastic Systems·Captain: mikedeng1

Approximate Markov-Nash Equilibria for Discrete-Time Risk-Sensitive Mean-Field Games 2: The Mean-Field Equilibrium Policy Is an ε-Markov-Nash Equilibrium of Every Large Enough N-Agent GameResearch Paper

Games with many interacting agents, such as traffic participants, users of a shared communication channel or firms in a market, are rarely solvable exactly: a Nash equilibrium of an NNN-player stochastic game requires each agent to track the whole population, and its computation grows with NNN. Mean-field game theory replaces the population by its limiting…

16 thms1 active userReviewed
Dynamic ProgrammingProbabilityStochastic Systems·Captain: mikedeng1

Approximate Markov-Nash Equilibria for Discrete-Time Risk-Sensitive Mean-Field Games 1: A Risk-Sensitive Mean-Field Game with Compact Actions and Weakly Continuous Kernel Has a Mean-Field EquilibriumResearch Paper

Mean-field games describe large populations of identical agents who interact only through the distribution of their states. Each agent solves a stochastic control problem in which the population appears through a deterministic flow of distributions, and an equilibrium requires that this flow coincide with the distribution the agents generate themselves. The…

15 thms1 active userReviewed
Graph TheoryProbabilityStochastic Systems·Captain: mikedeng1

A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes II: Large-Graph Limits of the Equilibrium Through the Laplacian Eigenvalue DistributionResearch Paper

Mean field games describe large populations of agents who interact symmetrically: every agent sees the same average of all the others. Many populations interact instead along a network, where each agent responds only to its neighbours. Lacker and Soret (arXiv:2005.14102v2, 2021; Math. Oper. Res. 2022) study a linear-quadratic stochastic differential game on…

17 thms1 active userReviewed
Graph TheoryProbabilityStochastic Systems·Captain: mikedeng1

A Case Study on Stochastic Games on Large Graphs in Mean Field and Sparse Regimes III: The Mean Field Game Control Is an ε-Nash Equilibrium on Any Finite Graph, With ε_v ∝ deg(v)^(-1/2)Research Paper

Mean field games (MFGs) describe the limit of symmetric stochastic differential games as the number of players tends to infinity, when every player interacts with the empirical distribution of all the others. Their main practical use is the converse direction: an equilibrium of the limiting game supplies a simple, decentralized control that is an approximate…

14 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 4: In the Mean-Sign Game the Sign Feedback Is an ε_n-Nash Equilibrium and the Mean Converges in Law to ½δ_{H⁺}+½δ_{H⁻}Research Paper

Mean field games describe the limit of symmetric stochastic differential games with nnn players as n→∞n\to\inftyn→∞. A basic question of the theory is which mean field equilibria are limits of Nash equilibria of the nnn-player games. For closed-loop equilibria, in which each player's control may depend on the states of all players, this question was open in general…

12 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 2: Every Strong MFE Is the Limit in Law of Markovian ε_n-Nash Equilibria of the n-Player GamesResearch Paper

Mean field games (Lasry–Lions 2006, Huang–Malhamé–Caines 2006) describe Nash equilibria of stochastic differential games with very many symmetric players. In this description each player interacts with the others only through the empirical distribution of their states. The mean field game is meant to be the limit of the nnn-player games as n→∞n\to\inftyn→∞. Making…

13 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 1: Empirical Measure Flows of Closed-Loop ε_n-Nash Equilibria Are Tight and Every Limit in Law Is a Weak MFEResearch Paper

Mean field games (MFG) were introduced by Lasry and Lions (2007) and by Huang, Malhamé and Caines (2006) as limits of stochastic differential games with many symmetric players. The model is only meaningful if equilibria of the nnn-player games actually converge to equilibria of the limit game. That convergence depends on what information the players use. For o…

17 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 3: Under Convexity Every Markovian ε-Nash Equilibrium Is a Closed-Loop ε-Nash EquilibriumResearch Paper

In an nnn-player stochastic differential game each player controls the drift of its own diffusion and is rewarded through a running and a terminal payoff that depend on its own state and on the empirical distribution of all states. A player's strategy can be closed-loop (path-dependent), reacting to the whole observed history of all states, or Markovian (in…

9 thms1 active userReviewed
Control TheoryProbability·Captain: mikedeng1

A Probabilistic Weak Formulation of Mean Field Games and Applications 3: Distributed Controls from a Mean Field Game Solution Form an ε_n-Nash Equilibrium of the n-Player Game, ε_n → 0Research Paper

Mean field games (MFGs) were introduced by Lasry and Lions (Jpn. J. Math. 2007) and by Huang, Malhamé and Caines (Commun. Inf. Syst. 2006) as limits of stochastic differential games with many symmetric players whose interaction runs through the empirical distribution of their states. An MFG is a fixed point problem for one representative player facing a…

14 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

From the Master Equation to Mean Field Game Limit Theory: Large Deviations and Concentration of Measure 2: Nash Equilibrium Empirical Measure Flows Satisfy a Weak LDP Under Common NoiseResearch Paper

A mean field game describes the Nash equilibria of nnn symmetric players whose states interact only through their empirical distribution, in the limit n→∞n\to\inftyn→∞. The law of large numbers for the equilibria — convergence of the empirical measure of the nnn-player equilibrium to the mean field equilibrium — was proved in the diffusion setting by Cardaliaguet,…

23 thms1 active userReviewed
Optimal TransportProbabilityStochastic Systems·Captain: mikedeng1

From the Master Equation to Mean Field Game Limit Theory: Large Deviations and Concentration of Measure 1: Without Common Noise, n-Player Nash Equilibria Concentrate Dimension-FreeResearch Paper

A large stochastic game has one state process per player. Each player's feedback changes with the empirical distribution of all states, so a finite population remains coupled even when the idiosyncratic Brownian motions are independent. A useful quantitative question is whether a statistic of the entire collection of equilibrium trajectories can deviate…

12 thms1 active userReviewed
ProbabilityStochastic Systems·Captain: mikedeng1

Probabilistic Analysis of Mean-Field Games 2: The Mean-Field Strategies Form an ε_N-Nash Equilibrium of the N-Player Game, with ε_N ≤ cN^{−1/(d+4)}Research Paper

Mean-field games were introduced by Lasry and Lions (2007) and by Huang, Malhamé and Caines (2006) as limits of stochastic differential games with many symmetric players, each interacting with the others only through the empirical distribution of their states. The limit replaces a game of NNN coupled players by one representative player facing a deterministic…

18 thms1 active userReviewed
Mathematical LogicProbability·Captain: martelus trismortuus

Online problems as Abramsky–Jagadeesan games: memoryless 2-taxi is not competitiveOpen Problem

Online algorithms are usually analysed as a game between an algorithm and an adversary who issues requests. The platform already hosts several such missions: competitive analysis of the kkk-taxi problem, optimal stopping and prophet inequalities, bandits. Each defines its own players, strategies and adversaries from scratch. For example, …

27 thms0 active usersReviewed
PreviousPage 13 of 13Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me