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
🏆Completed
Complexity TheoryOperations Research·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 3: Trimming an Approximate Nash Equilibrium Yields a Well-Supported OneResearch Paper

The complexity of computing a Nash equilibrium is usually studied for an approximate equilibrium, because an exact equilibrium of a game with three or more players can require irrational probabilities. Two approximation notions are in use, and results proved for one do not automatically transfer to the other. Daskalakis, Goldberg and Papadimitriou (SIAM J.…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

The Price of Anarchy of Finite Congestion Games V: The Mixed Price of Anarchy of the Average Social Cost Is at Most (3+sqrt 5)/2Research Paper

When many self-interested users share resources whose cost grows with use (links of a network, servers, machines), each user picks the option that is cheapest for them given what the others do, and the resulting equilibrium can be worse for the group than a centrally planned allocation. The price of anarchy, introduced by Koutsoupias and Papadimitriou (STACS…

7 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Blackwell Approachability and No-Regret Learning are Equivalent 3: An Efficient Forecaster Whose (ℓ1, ε)-Calibration Rate Is at Most √(2/(εT))Research Paper

A forecaster announces, each day, a probability that it will rain; afterwards nature reveals whether it did. The forecaster is calibrated if, on the days on which it announced roughly 30%, it rained roughly 30% of the time, and likewise for every other announced value. Calibration is a minimal consistency requirement for probabilistic forecasts, used in…

11 thms4 active usersReviewed
🏆Completed
CombinatoricsMechanism DesignOperations Research+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 2: Sequential Posted Prices e/(e−1)-Approximate the Optimal Revenue under a Partition Matroid ConstraintResearch Paper

A seller who knows the distributions of buyers' values can maximise expected revenue with Myerson's optimal mechanism (Myerson 1981): collect bids, compute virtual values, serve a feasible set of maximum virtual surplus, and charge threshold payments. Real sellers seldom run such auctions. They post prices: a buyer is offered a take-it-or-leave-it price and…

21 thms4 active users
🏆Completed
CombinatoricsMechanism DesignOperations Research+1·Captain: mikedeng1

Multi-parameter Mechanism Design and Sequential Posted Pricing 1: Sequential Posted Prices 2-Approximate the Optimal Revenue under a Matroid ConstraintResearch Paper

A seller who must decide whom to serve among several buyers with private values can, in principle, run Myerson's revenue-optimal mechanism: collect bids, compute virtual values, serve the feasible set of largest virtual surplus, and charge threshold payments (Myerson 1981). In practice sellers rarely do this. Retail, ticketing and online platforms mostly…

21 thms4 active users
🏆Completed
Complexity TheoryOperations Research·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 1: Approximate Fixed Points of Nash's Map Are Approximate Nash EquilibriaResearch Paper

A finite game describes several decision makers whose payoffs depend on everyone's choices. A Nash equilibrium is a collection of choices at which no single player can improve their expected payoff by changing strategy alone. Equilibrium existence is a classical result, but a computational argument needs to connect an object that can be approximated…

7 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Theory of Games and Economic Behavior V: All Solutions of the Essential Zero-Sum Three-Person GameTextbook

The solution concept of von Neumann and Morgenstern — today usually called a stable set — was the first general answer to the question of what a rational outcome of a many-player cooperative game should be. It was introduced in Theory of Games and Economic Behavior (1944), and Chapter VI of that book states it exactly (§30) and then tests it on the smallest…

16 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior IX: Solutions for Acyclic RelationsTextbook

The solution concept of von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944) is defined from two ingredients: a set of imputations and a domination relation between them. A solution is a set of imputations that is internally stable (no member dominates another) and externally stable (every non-member is dominated by some member). In…

13 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VIII: Characteristic Functions of General n-Person GamesTextbook

The theory of Theory of Games and Economic Behavior (von Neumann and Morgenstern, 1944; 3rd ed. 1953) rests on one object: the characteristic function v(S)v(S)v(S), the amount a coalition SSS of players can secure for itself whatever the other players do. For zero-sum nnn-person games, Chapter VI defines v(S)v(S)v(S) and proves (25.3.1 and 26.1.1) that the set functions…

15 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VII: Simple Games, Weighted Majorities and the Main Simple SolutionTextbook

Many collective decisions are taken by coalitions that either carry the vote or do not: committees, legislatures, shareholder meetings, councils with weighted votes. In such a situation the only aim of a participant is to be part of a coalition that wins, and nothing is left to bargain about except the division of the prize inside the winning coalition.…

13 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Theory of Games and Economic Behavior IV: The Characteristic Function of a Zero-Sum n-Person GameTextbook

Chapter VI of von Neumann and Morgenstern's Theory of Games and Economic Behavior (1944; 3rd ed. 1953) opens the general theory of zero-sum games with more than two players. The authors propose to describe everything that can be said about coalitions, compensations between partners and fights between coalitions through one numerical object, the characteristi…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior III: Mixed Strategies, the Minimax Theorem and Good StrategiesTextbook

A zero-sum two-person game in normalized form is a real matrix H(τ1,τ2)\mathcal H(\tau_1, \tau_2)H(τ1​,τ2​): player 1 chooses a row τ1\tau_1τ1​, player 2 simultaneously chooses a column τ2\tau_2τ2​, and player 2 pays player 1 the amount H(τ1,τ2)\mathcal H(\tau_1, \tau_2)H(τ1​,τ2​). Matrix games are the base case of non-cooperative game theory, the prototype of every minimax statement in optimization,…

11 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Theory of Games and Economic Behavior I: Numerical Utility from the Axioms of Preference and MixtureTextbook

Game theory as von Neumann and Morgenstern built it measures every outcome by a single number, the utility a player attaches to it, and combines those numbers linearly when an outcome is uncertain: a lottery that yields uuu with probability α\alphaα and vvv with probability 1−α1-\alpha1−α is worth α v(u)+(1−α) v(v)\alpha\,\mathrm v(u) + (1-\alpha)\,\mathrm v(v)αv(u)+(1−α)v(v). Every later chapter of T…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Information Sharing in a Supply Chain with a Common Retailer 2: Under Production Economy the Retailer Earns Weakly More from Sequential Information Contracting and the Manufacturers from ConcurrentResearch Paper

Large retailers hold point-of-sale and loyalty-card data that their suppliers cannot observe, and many of them sell access to it through data-sharing programs; others share the same data for free, or with only some suppliers (Shang, Ha & Tong 2016, §1). When two competing manufacturers sell through one common retailer, sharing a demand signal with a…

19 thms4 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design I: MinWork Is a Strongly Truthful n-Approximation Mechanism for Task Scheduling on Unrelated MachinesResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested parties. Each party reports its private data, the algorithm computes an outcome, and payments are arranged so that no party gains by misreporting. Nisan and Ronen introduced the field in Algorithmic Mechanism Design (Games Econ. Behav. 35, 2001). Their running example…

9 thms4 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders IV: A Truthful Value-Query Mechanism for Subadditive BiddersResearch Paper

In a combinatorial auction a seller offers several indivisible items at once, and bidders value bundles of items rather than items one at a time. Allocating the items to maximize total value is the central optimization problem of the area, and it arises in spectrum licensing, procurement and transport contracting (Cramton, Shoham and Steinberg, Combinatorial…

8 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

The Assignment Game I: The Core 2: The High-Price and Low-Price Corners of the CoreResearch Paper

A two-sided market in which each seller owns one indivisible good (a house, in the paper's example) and each buyer wants at most one is the simplest model in which prices emerge from bargaining between individuals rather than from a supply curve. Shapley and Shubik, The Assignment Game I: The Core (Int. J. Game Theory 1 (1971)), treat this market as a…

7 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Calibrated Learning and Correlated Equilibrium III: A Randomized Forecast Calibrated against Every OpponentResearch Paper

A forecaster who announces "70% chance of rain" is calibrated if, among the days on which that number was announced, it rained on about 70% of them. Dawid (The well-calibrated Bayesian, JASA 1982) proposed calibration as the minimal requirement of an honest probability forecaster. Oakes (Self-calibrating priors do not exist, JASA 1985) showed that no…

10 thms4 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

Calibrated Learning and Correlated Equilibrium I: Calibrated Forecasts with Best Responses Converge to the Set of Correlated EquilibriaResearch Paper

A correlated equilibrium (Aumann 1974) is a joint distribution over the players' strategy profiles such that no player gains by deviating from the strategy the distribution recommends to them. It is the equilibrium notion that learning dynamics in repeated games most naturally reach, and a basic question in learning in games is which simple rules, played…

15 thms4 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Bargaining under Incomplete Information I: Class A Equilibrium Offer Strategies Satisfy the Linked Differential EquationsResearch Paper

A buyer and a seller negotiate over a single indivisible good. Each knows how much the good is worth to them, but not how much it is worth to the other side. Whether the two will trade, and at what price, then depends on how each party shades its offer to exploit the other's uncertainty. Chatterjee and Samuelson (Bargaining under Incomplete Information,…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Subjectivity and Correlation in Randomized Strategies I: Subjective Mixed Equilibria of Two-Person Games Have Objective PayoffsResearch Paper

Classical non-cooperative game theory randomizes with objective, independent devices: each player spins a private wheel whose odds everyone agrees on. Aumann's 1974 paper (doi:10.1016/0304-4068(74)90037-8) asks what changes when the randomizing events are ordinary events of the world, about which players may hold different subjective probabilities and may…

9 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

Markovian Decision Processes with Uncertain Transition Probabilities I: The Max-Min Policy-Iteration Algorithm Terminates at a Max-Min Optimal Pure Stationary PolicyResearch Paper

Howard's finite Markovian decision process (MDP) models a controller who, at each instant, observes the state of a system, chooses a decision, collects a reward and moves to a random next state with known transition probabilities. Howard's policy-iteration algorithm computes an optimal policy, and the model has been applied to inventory control, equipment…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Stochastic Orders IX: The PQD and Supermodular OrdersTextbook

The first eight chapters of Shaked and Shanthikumar's Stochastic Orders (Springer, 2007) compare single random variables — location, variability, convexity. Chapter IX turns to a different question: given two coordinates of a random vector, how strongly do they tend to move together? "Large values of X1X_1X1​ go with large values of X2X_2X2​" is a qualitative…

5 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Supermodularity and Complementarity V: Existence of Equilibrium in Supermodular GamesTextbook

Existence of equilibrium is the first question any model of strategic interaction must answer, and the classical answer — Nash's theorem via Kakutani's fixed point theorem — asks for a convex, compact strategy space and continuous payoffs. Many of the models economists actually use do not have that: a firm's technology set can be discrete or irregular, and…

11 thms4 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: Shuze Chen

Algorithmic Game Theory I: Existence of Nash EquilibriumTextbook

The strategic-form game is the basic object of noncooperative game theory, and the Nash equilibrium — a profile of randomized strategies from which no player benefits by deviating unilaterally — is its central solution concept. Nash proved in 1951 that every game with finitely many players and finite strategy sets has such an equilibrium (Nash, Non-cooperati…

10 thms4 active usersReviewed
PreviousPage 5 of 21Next

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