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
EconomicsOperations Research·Captain: mikedeng1

Economics of Social Media Fake Accounts 1: A Purely Profit-Driven Platform Optimally Chooses Zero Antifake EffortResearch Paper

Fake accounts (purchased followers, likes and engagement) are a large part of influencer marketing on social media, and platforms say they invest in detecting and removing them. Huang and Liu (Management Science 71(10), 2025) model this market as a signaling game. An influencer of unknown quality buys fake followers to look popular, consumers decide whether…

9 thms4 active usersReviewed
🏆Completed
Convex OptimizationDynamical Systems·Captain: mikedeng1

Learning in Games via Reinforcement and Regularization 1: Under Regularized Reinforcement Learning, Every Iteratively Dominated Strategy Becomes ExtinctResearch Paper

A basic test of any model of learning in games is whether it respects strict dominance: a strategy that does worse than another against every behaviour of the opponents should eventually be abandoned, and, after it is gone, so should every strategy that becomes dominated in what remains. For the replicator dynamics of evolutionary game theory this is…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

Fast Convergence of Regularized Learning in Games I: If Every Player Runs Optimistic FTRL with Step Size 1/(2(n−1)), the Sum of All Players' Regrets Is at Most 2n(n−1)RResearch Paper

When the players of a game repeatedly adjust their strategies with no-regret learning algorithms, the empirical distribution of play converges to a coarse correlated equilibrium, and in smooth games the average social welfare approaches the price-of-anarchy guarantee of the game (Roughgarden 2009). For generic no-regret algorithms such as Hedge the…

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

Intrinsic Robustness of the Price of Anarchy I: Every Coarse Correlated Equilibrium of a Smooth Game Has Expected Cost at Most the Robust Price of Anarchy Times OptimalResearch Paper

The price of anarchy (POA) of a game measures how much selfish behaviour costs: it is the ratio between the largest cost of an equilibrium and the cost of an optimal outcome, for a nonnegative objective such as the sum of the players' costs. Since Koutsoupias and Papadimitriou (1999) and Roughgarden and Tardos (2002), POA bounds have been proved for…

12 thms4 active users
🏆Completed
Complexity Theory·Captain: mikedeng1

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria: An (ε, δ)-WeakNash of a Bipartite Polymatrix Game Yields a (√ε(√ε + 5), δ)-Well-Supported WeakNashResearch Paper

Computing an approximate Nash equilibrium of a two-player game is one of the central questions of algorithmic game theory. For a constant approximation ϵ\epsilonϵ, the algorithm of Lipton, Markakis and Mehta runs in quasi-polynomial time nO(log⁡n/ϵ2)n^{O(\log n/\epsilon^2)}nO(logn/ϵ2), and for a long time it was unknown whether polynomial time is possible. A. Rubinstein, Settling…

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

Approximate Revenue Maximization with Multiple Items 2: Selling Two I.I.D. Goods Separately Guarantees at Least e/(e + 1) ≈ 73% of the Optimal RevenueResearch Paper

A seller with several goods can sell them one at a time or offer a mechanism that links allocation and payment across goods. Separate selling asks the seller to solve a one-good pricing problem for each item. A general mechanism can offer lotteries and menus whose outcomes depend on the buyer's whole valuation vector. The difference matters because the…

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

Approximate Revenue Maximization with Multiple Items 5: Bundling Is Optimal for Two I.I.D. Goods Whose Density on [a, ∞) Satisfies x f′(x) + (3/2) f(x) ≤ 0Research Paper

A seller with several goods and a single buyer of unknown, additive valuation faces the multi-dimensional revenue maximization problem. For one good the answer is classical: by Myerson's theorem (Myerson 1981) a single posted price is optimal. For two or more goods no such simplification exists in general: optimal mechanisms may randomize, may offer menus…

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

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals I: Under Random Arrival Order, Nonadaptive Thresholds Earn a 1 − 1/e Fraction of E[max Xᵢ]Research Paper

In a prophet inequality, a gambler sees prizes one at a time and must decide when to stop, while a prophet knows every realization and takes the largest. A stopping guarantee compares the gambler’s expected prize with the prophet’s. The order of arrival changes the problem: here the prizes are independent but can have different distributions, and every…

12 thms4 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals II: For I.I.D. Variables, Adaptive Thresholds Achieve E[max Xᵢ] ≤ β*·E[X_t] with β* ≈ 1.341Research Paper

A prophet inequality compares a gambler who sees nonnegative random rewards X1,…,XnX_1,\ldots,X_nX1​,…,Xn​ one at a time, and must accept or reject each on arrival, with a prophet who knows all values in advance and simply takes max⁡iXi\max_i X_imaxi​Xi​. For independent and identically distributed (i.i.d.) rewards the question is the best constant β\betaβ such that some online rule always…

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

A Little Charity Guarantees Almost Envy-Freeness III: With Additive Valuations, Donating the Pool to an Unenvied Agent Yields a 4/7-Groupwise-Maximin-Share AllocationResearch Paper

When indivisible goods are shared among people, comparing each person's bundle with another person's bundle is only one way to judge fairness. A second test asks whether a group could repartition the goods it collectively received so that one of its members would reliably obtain more. Groupwise maximin share (GMMS) makes this test for every subgroup. It…

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

A Little Charity Guarantees Almost Envy-Freeness I: Under Monotone Valuations an EFX Allocation Exists Whose Unenvied Pool Has Fewer Goods Than There Are Unenvied AgentsResearch Paper

Allocating indivisible goods fairly is difficult because a single good can change how an agent compares two bundles. Exact envy-freeness can be impossible (one good, two agents), so the field works with relaxations. Envy-freeness up to any good (EFX) requires each agent to prefer her own bundle to every other agent's bundle after any one good of that other…

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

A game-theoretic approach to computation offloading in mobile cloud computing II: The VI Map of the Offloading GNEP Is Monotone When the Cloudlet Is Not OverloadedResearch Paper

Mobile devices run applications whose computational demand often exceeds what a battery-powered processor can serve with acceptable delay. Computation offloading sends part of the work elsewhere: to a cloudlet, a small cluster of servers one wireless hop away, or to a distant cloud reached through the wide-area network. When many users share one cloudlet,…

10 thms4 active usersReviewed
Differential GeometryOperations Research·Captain: mikedeng1

Inefficiency of Nash Equilibria: For an Open Dense Set of C² Payoffs, Nash Equilibria Are Finite, an Efficient One Has a Player at a Vertex, and a Strong One Has at Most One Player off a VertexResearch Paper

That noncooperative play usually wastes something is part of the folklore of game theory, with the Prisoner's Dilemma as its emblem: each player's best reply leads to an outcome that both would trade for another. Pradeep Dubey's paper turns this folklore into a theorem about smooth games. For games whose payoffs are twice continuously differentiable, and…

13 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Quality in Supply Chain Encroachment II: Under Quality Differentiation the Direct Channel Carries the High-Quality Product, the Manufacturer Gains and the Retailer LosesResearch Paper

Manufacturers increasingly sell directly to consumers while continuing to supply independent retailers, a practice known as supply chain encroachment. The direct channel competes with the retailer for the same consumers, and the conventional advice for easing that conflict is to sell different products in the two channels. Ha, Long and Nasiry (MSOM 18(2),…

18 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 2: Randomized Inexact Best Response Reaches an ϵ-NE in Explicitly Bounded Expected SG StepsResearch Paper

Many noncooperative problems in communication networks, power markets and supply chains are stochastic Nash games. Each player minimizes an expected cost that depends on its own decision and on the decisions of its rivals, and the expectation can only be sampled, not evaluated. A natural distributed way to compute an equilibrium is the best-response scheme:…

21 thms4 active usersReviewed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 3: Asynchronous Inexact Best Response with Delays Reaches an ϵ-NE in Explicitly Bounded SG StepsResearch Paper

Many equilibrium problems in operations research have the form of a stochastic Nash game: each of NNN players minimizes an expected cost that depends on the strategies of the others, and the expectation can only be sampled. The paper's introduction lists applications in generation-capacity and power markets and in communication networks (Abada, de Maere…

19 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games 1: Synchronous Inexact Best Response Reaches an ϵ-NE in Explicitly Bounded Projected SG StepsResearch Paper

Many equilibrium problems in operations research, such as networked Cournot competition, power markets and communication networks, are stochastic Nash games: each player minimizes an expected cost fi(xi,x−i)=E[ψi(xi,x−i;ξ)]f_i(x_i,x_{-i})=\mathbb E[\psi_i(x_i,x_{-i};\xi)]fi​(xi​,x−i​)=E[ψi​(xi​,x−i​;ξ)] that depends on the rivals' strategies and on a random vector ξ\xiξ whose law is accessible only through samples. B…

13 thms4 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 1: Every Finite Game Decomposes Uniquely into Potential, Harmonic and Nonstrategic ComponentsResearch Paper

Potential games (Monderer and Shapley, 1996) are the finite games whose incentives are captured by a single function on strategy profiles: every unilateral change of strategy changes the deviator's payoff by exactly the change of a common potential. They have pure Nash equilibria, and natural learning dynamics such as better-reply and fictitious play…

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

How Bad is Selfish Routing? 2: With Linear Latency Functions the Cost of a Nash Flow Is at Most 4/3 Times the Optimal CostResearch Paper

In a road or communication network, each user picks a route to minimize its own delay, without regard to the delay it imposes on others. The outcome is an equilibrium that is in general not socially optimal: Braess's paradox shows that adding a road can make every user worse off, and Pigou's two-link example shows that selfish users can incur a third more…

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

Consumer Returns Policies and Supply Chain Performance 2: Under Consumer Returns, the Differentiated Buy-Back with b − l = s Coordinates the Supply Chain and Gives the Retailer a Share φResearch Paper

Retailers in many categories accept returns of products that are not defective: a consumer buys, learns whether the product suits them, and may send it back for a refund. Returns of this kind are a large cost item in retailing, and the refund a retailer offers is an operational decision on a par with its price and its stocking quantity. Xuanming Su, Consumer…

12 thms4 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: mikedeng1

A Simple Adaptive Procedure Leading to Correlated Equilibrium 2: Playing an Invariant Vector of the Regret Matrix (3.1) Drives Every Regret R_t(j,k) to Zero Almost SurelyResearch Paper

A correlated equilibrium (Aumann, 1974) is a probability distribution over the strategy profiles of a game such that no player gains by deviating from the strategy it recommends. It is the natural solution concept for repeated play by adaptive agents, because the set of correlated equilibria is a polytope described by linear inequalities and, as Hart and…

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

Asymptotic Calibration: The Regret-Balancing Randomised Forecast on the Grid {0, 1/k, …, 1} with k ≥ 1/ε² Is ε-Calibrated against Every Adaptive NatureResearch Paper

A probability forecast is useful only when its stated frequencies bear a stable relation to outcomes. If a forecaster repeatedly announces a 70% chance of rain, calibration asks whether rain occurs on about 70% of those days. This is a minimal reliability requirement for probabilistic prediction, even though calibration alone does not rank every pair of…

14 thms4 active usersReviewed
🏆Completed
CombinatoricsMechanism Design·Captain: mikedeng1

Strategy-Proofness and Arrow's Conditions 1: A Strict Voting Procedure with at Least Three Possible Outcomes Is Strategy-Proof Iff It Is DictatorialResearch Paper

A committee that chooses one alternative by voting would like a voting procedure under which no member can gain by misreporting their preferences. Such a procedure is called strategy-proof. Gibbard (Econometrica 41, 1973) and Satterthwaite (J. Econ. Theory 10, 1975) proved independently that, once at least three outcomes are possible, the only…

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

Incentive Compatibility and the Bargaining Problem I: The Incentive-Feasible Set Is Compact and Convex, and the Generalized Nash Bargaining Solution over It Exists and Is UniqueResearch Paper

An arbitrator choosing an outcome for several people can ask them about their preferences, but the answer to that question may affect the outcome. A person who expects to gain from a false report may give one. Roger Myerson's 1979 paper puts this incentive problem inside a bargaining model: the arbitrator may randomize over collective choices, and an…

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

Comparison of Threshold Stop Rules and Maximum for Independent Nonnegative Random Variables II: For I.I.D. Variables the Constant 2 Is Best Possible over Threshold RulesResearch Paper

A prophet inequality compares two observers of a sequence of nonnegative random variables X1,…,XnX_1, \dots, X_nX1​,…,Xn​. The prophet knows all values in advance and collects Xn∗=max⁡(X1,…,Xn)X_n^* = \max(X_1, \dots, X_n)Xn∗​=max(X1​,…,Xn​). The gambler sees the values one at a time and must decide, irrevocably, when to stop and collect the current value. For independent variables the gambler's optimal…

11 thms4 active usersReviewed
PreviousPage 6 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