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
Control TheoryProbability·Captain: mikedeng1

A Probabilistic Weak Formulation of Mean Field Games and Applications 1: When the Hamiltonian's Maximizer Sets Are Convex, the Mean Field Game in Weak Formulation Has a SolutionResearch Paper

Mean field games (MFGs) describe Nash equilibria of stochastic differential games with a very large number of symmetric players, each of whom interacts with the others only through the empirical distribution of their states (and, in this paper, of their controls). They were introduced independently by Lasry and Lions and by Huang, Malhamé and Caines around…

16 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Centralized and Competitive Inventory Models with Demand Substitution 1: The Competitive Substitution Game Has a Nash Equilibrium, Unique and Globally Stable When Substitution Rates Sum Below OneResearch Paper

A retailer that carries several substitutable products, such as brands of the same item or sizes of the same garment, must choose stock levels before demand is known. When a product runs out, some of its customers buy another product instead. Inventory models with this demand substitution go back to McGillivray and Silver (1978, INFOR 16(1)) and Parlar and…

8 thms2 active usersReviewed
🏆Completed
Dynamical SystemsLinear algebra·Captain: mikedeng1

Uncoupled Dynamics Do Not Lead to Nash Equilibrium 2: Near Jordan's Three-Player Game Γ₀ of Section III, No Uncoupled Dynamic Is Nash-ConvergentResearch Paper

A central question of the theory of learning in games is whether simple adaptive behavior leads players to a Nash equilibrium. Many natural dynamics — fictitious play, best-reply dynamics, replicator dynamics — fail to converge in some games, and the failures are usually exhibited one dynamic at a time. Hart and Mas-Colell (AER 2003) asked a structural…

6 thms2 active usersReviewed
Machine LearningProbability·Captain: mikedeng1

A Simple Adaptive Procedure Leading to Correlated Equilibrium 1: Under Regret-Matching (2.2), the Empirical Distributions of Play Converge Almost Surely to the Set of Correlated EquilibriaResearch Paper

A correlated equilibrium (Aumann 1974) is a probability distribution over strategy profiles of a game such that no player gains by deviating from a recommended strategy, given the recommendation. It is the solution concept of choice when players can condition on common signals, and its set is a convex polytope defined by linear inequalities, which makes it…

17 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 7: Without Gross Substitutes a Market with Two Firms and Three Workers Has No Core AllocationResearch Paper

In a labor market where firms hire sets of workers and salaries are negotiated pair by pair, the natural stability notion is the core: an assignment of workers to firms, with salaries, that no firm and group of workers can improve upon by agreeing among themselves. Kelso and Crawford (Econometrica 50 (1982) 1483–1504) proved that the core is nonempty, and…

13 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 5: An Entering Firm Leaves Every Worker at Least as Well Off, and a Departing Worker Leaves Every Firm No Better OffResearch Paper

Adding a firm changes the offers available to workers; removing a worker changes the pool from which firms hire. In markets with salary bargaining, those changes can alter both assignments and pay. Kelso and Crawford asked whether the direction of the change can nevertheless be predicted at the outcome selected by their salary-adjustment process. Their 1982…

6 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Potential Games 4: An Efficient Solution Is the Shapley Value on the Subgames of v If and Only If the Participation Game Γ(ψ, c, v) Is a Potential GameResearch Paper

The Shapley value (Shapley 1953) is the most widely used single-valued solution of cooperative games with transferable utility. It is usually justified axiomatically, from cooperative principles. A recurring question in game theory, sometimes called the Nash program, asks whether cooperative solution concepts can also be recovered from the strategic…

13 thms2 active usersReviewed
Markov ChainProbability·Captain: mikedeng1

The Evolution of Conventions III: In 2 × 2 Games with Two Strict Equilibria, the Generically Stable Equilibria of Adaptive Play Are the Weakly Risk Dominant OnesResearch Paper

Many games have several strict Nash equilibria, and equilibrium analysis alone does not say which one a population will settle on. Harsanyi and Selten (1988) proposed risk dominance as a selection criterion for 2×22\times22×2 games: of two strict equilibria, select the one whose basin is "larger" in a precise payoff sense. That criterion is axiomatic. H. Peyton…

45 thms2 active usersReviewed
🏆Completed
CombinatoricsMechanism Design·Captain: mikedeng1

Strategy-Proofness and Arrow's Conditions 3: With Indifference Allowed, a Strategy-Proof Voting Procedure with at Least Three Possible Outcomes Is DictatorialResearch Paper

A committee that chooses one alternative by voting would like a procedure under which nobody gains by misreporting their preferences. Gibbard (Econometrica 41, 1973) and Satterthwaite (J. Econ. Theory 10, 1975) showed that, once at least three outcomes are possible, the only voting procedures with this property are dictatorial. The theorem is the starting…

6 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Incentive Compatibility and the Bargaining Problem II: Every Equilibrium of Every Choice Mechanism Yields an Incentive-Feasible Allocation, F** = F*Research Paper

An arbitrator who must choose among collective options for a group of players usually does not know the players' private characteristics. The arbitrator can only ask, and a player who expects to profit from a false answer may give one. Before designing any procedure, the arbitrator therefore needs to know which expected-payoff allocations can be reached at…

6 thms2 active usersReviewed
🏆Completed
AnalysisOperations ResearchProbability·Captain: mikedeng1

Values of Large Games II: Oceanic Games 2: Oceanic Values Are Limits of Values of Finite Weighted Majority GamesResearch Paper

Weighted voting models assign a coalition a win when its combined vote reaches a quota. The Shapley value measures a player's contribution by averaging the change it makes when added to every possible predecessor coalition. This is straightforward to define for a finite list of voters, but a voting body may contain a few major holders and a very large…

8 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 6: When Workers Are Alike in Production, Gross Substitutes Is Equivalent to Nonincreasing Returns to WorkersResearch Paper

Kelso and Crawford's 1982 Econometrica paper studies a labor market in which firms hire sets of heterogeneous workers at individually negotiated salaries. Their existence results for the core and for competitive equilibrium, and the convergence of their salary-adjustment process, all rest on one hypothesis about each firm's technology, the gross-substitutes…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Monotone Comparative Statics I: The Argmax Is Monotone Nondecreasing in (t, S) If and Only If f Is Quasisupermodular in x and Has the Single Crossing Property in (x; t)Research Paper

An optimization problem often changes when a parameter changes: a price rises, a constraint expands, or a strategic environment shifts. Comparative statics asks whether the optimal choice moves in a predictable direction. The usual numerical tools, such as derivatives, can be unavailable when choices form a discrete set or the objective is neither smooth…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Potential Games 1: A Game Is an Exact Potential Game If and Only If I(γ, u) = 0 on Every Simple Closed Path of Length 4Research Paper

In a strategic game, each player evaluates a change in their own strategy using that player's own payoff. These incentives need not point in a common direction. A potential game is a case in which one real-valued function records every player's payoff change under a unilateral deviation. This common function lets questions about incentives be expressed as…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsMechanism Design·Captain: mikedeng1

Strategy-Proofness and Arrow's Conditions 2: Strategy-Proof Voting Procedures Correspond One-to-One to Social Welfare Functions Satisfying CS, NNR and IIAResearch Paper

Two impossibility theorems frame the theory of collective choice. Arrow's theorem (1951) says that a rule aggregating individual preference orderings into a social ordering, subject to a short list of reasonable conditions, must be dictatorial. The Gibbard–Satterthwaite theorem (Gibbard 1973, Satterthwaite 1975) says that a voting procedure selecting a…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsMechanism Design·Captain: mikedeng1

Strategy-Proofness and Arrow's Conditions 4: With Indifference Allowed, a Social Welfare Function Satisfying CS, NNR and IIA Is DictatorialResearch Paper

A social welfare function turns the rankings of the members of a committee into one ranking for the committee. Arrow's general possibility theorem (Arrow, 1951/1963) shows that, once there are at least three alternatives, no such rule satisfies a short list of conditions that each look harmless unless it follows a single member's ranking. The theorem is the…

6 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

The Fair Division of a Fixed Supply Among a Growing Population: WPO, Anonymity, Scale Invariance, Continuity and Population Monotonicity Characterize the Kalai–Smorodinsky SolutionResearch Paper

Axiomatic bargaining theory asks which rule should divide a set of feasible utility vectors among a group of agents, and answers by listing properties a reasonable rule must have and determining the rules that have them. Nash's solution (Nash 1950) and the Kalai–Smorodinsky solution (Kalai and Smorodinsky 1975) are the two classical answers for a fixed set…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

An Iterative Method of Solving a Game: For Every Vector System, min U(t)/t and max V(t)/t Converge to the Value of the GameResearch Paper

A finite two-person zero-sum game is given by a real pay-off matrix, and its value can be computed by linear programming. In 1949 George W. Brown proposed a much simpler procedure, now called fictitious play: each player in turn plays a best pure reply to the accumulated play of the opponent so far, and the running averages are read off as estimates of the…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

Graphs and Cooperation in Games: The Unique Fair Allocation Rule, the Shapley Value of the Graph-Restricted Game, Is Totally Stable for Superadditive GamesResearch Paper

Classical cooperative game theory assumes that any coalition of players can form and coordinate. In many settings cooperation is mediated by pairwise relationships: communication lines, contracts, alliances, or trade links. Roger Myerson's discussion paper Graphs and Cooperation in Games (Northwestern University, 1976; published in Mathematics of Operations…

18 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables I: A Median Threshold Rule Achieves EX* ≤ 2E⁺X_τResearch Paper

In a finite stopping problem, a decision maker observes rewards one at a time and must accept one without seeing the future. A fully informed observer takes the maximum. This comparison is often called a prophet inequality. The abstract bound that an optimal stopping rule can secure at least half the expected maximum does not say how to choose a simple…

9 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems VIII: Single-Controller Stochastic Games — a Dual Pair of Linear Programs Gives the Value and Stationary Optimal PoliciesTextbook

A two-person zero-sum stochastic game (also called a Markov game) is a Markov decision problem with two decision makers who pull in opposite directions: at every time point both players choose an action simultaneously, one player pays the other, and the system moves to a random next state whose law depends on the current state and both actions. Stochastic…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts X: Under Forced Compliance, Options Contracts with Shares λ_l and min{λ_h, λ̂_h} Separate the Two Demand Types and Coordinate CapacityTextbook

A manufacturer launching a new product often depends on a single supplier for a critical component, and the supplier must build capacity before demand is known. The manufacturer usually knows more about demand than the supplier does: her sales force, market research and order history give her a forecast the supplier cannot verify, and she has a reason to…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Supply Chain Coordination with Contracts IX: An Internal Market at the Shadow Price w(α, Q) Allocates Output Optimally, and Paying Its Expectation per Unit Induces the Optimal Effort e°Textbook

In most contracts of the supply chain coordination literature the transfer payments are fixed when the contract is signed: a wholesale price www, a buy-back rate bbb, a revenue share ϕ\phiϕ. Some settings need payments that respond to information arriving after signing, such as realized demand at several retailers and realized production output. Fixing the…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Supply Chain Coordination with Contracts VIII: In the Two-Location Base-Stock Model the Linear Transfers (39)–(41) Make the Optimal Base Stocks the Unique Nash EquilibriumTextbook

In a supply chain with stock at two locations, a supplier holds inventory that replenishes a retailer, and the retailer serves customers. Each firm sets its own inventory level to minimize its own cost. The retailer bears only part of the cost of customer backorders, and the supplier bears none of the retailer's holding cost, so their incentives differ. The…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Supply Chain Coordination with Contracts V: With Market-Clearing Prices the Best Wholesale Price Earns θ/(2(1 + θ)) or θ/8, Below the (1 + θ)/8 a Full-Refund Buy-Back AttainsTextbook

A supplier that sells through many competing retailers usually worries that competition among them pushes orders too high, because each retailer ignores the demand it takes from the others. Deneckere, Marvel and Peck (1997) identified the opposite failure. When the retail price is set by the market after demand is realized, retailers who hold too much stock…

11 thms2 active usersReviewed
PreviousPage 29 of 34Next

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