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
Mechanism DesignOperations Research·Captain: iris

In Congestion Games, Taxes Achieve Optimal Approximation: Taxes From the Poisson Relaxation of Minimum Social Cost Have Price of Anarchy at Most the Worst Hardness Factor sup ρ_ℓResearch Paper

In an atomic congestion game (Rosenthal, 1973) each of NNN agents chooses a set of resources, such as the edges of a route, and the cost of a resource depends on how many agents use it. Selfish choices are inefficient: the price of anarchy (Koutsoupias and Papadimitriou, 1999) compares the social cost of the worst equilibrium with the minimum social cost, and…

39 thms4 active usersReviewed
Computational ComplexityEconomicsOperations Research·Captain: iris

The Complexity of Pacing for Second-Price Auctions: Finding an Approximate Pacing Equilibrium Is PPAD-HardResearch Paper

Online advertising platforms sell billions of impressions through auctions, and most advertisers face a budget for a whole campaign rather than for a single auction. Ad platforms handle this with budget pacing: each advertiser's bids are scaled down by a multiplier so that spending tracks the budget. When every advertiser paces at once, the multipliers…

26 thms4 active usersReviewed
Mechanism DesignOperations Research·Captain: iris

The Pareto Frontier of Inefficiency in Mechanism Design: Second-Price Mechanisms with Relative Reserves Exactly Attain the PoA/PoS Frontier of Anonymous Task-Independent SchedulingResearch Paper

Scheduling tasks on unrelated machines is the problem with which algorithmic mechanism design began (Nisan and Ronen, 1999). The machines are selfish: each one knows its own processing times and may misreport them, and a mechanism must allocate the tasks and pay the machines so that the makespan stays low. For two decades the field studied truthful…

36 thms4 active usersReviewed
EconomicsOperations Research·Captain: iris

Constrained Trading Networks: Under an Integral Polymatroid Constraint on Trades, the Efficient-Allocation Relaxation with Separable M♮-Concave/Linear Valuations Has an Integral OptimumResearch Paper

In a trading network agents sit at the vertices of a directed multigraph and every arc is a bilateral trade: its source sells, its sink buys, and an outcome records how many copies of each trade are executed. When valuations satisfy a gross-substitutes condition (M♯^\sharp♯-concavity), competitive equilibria exist and efficient outcomes can be computed by a…

26 thms4 active usersReviewed
Control TheoryProbabilityReinforcement Learning+1·Captain: iris

Exploration Noise for Learning Linear-Quadratic Mean Field Games: With Common Noise, the Tilted Geometric Fictitious Play Converges to the Equilibrium at Rate ϖ−nexp⁡(C/ε2)\varpi^{-n}\exp(C/\varepsilon^2)ϖ−nexp(C/ε2)Research Paper

A mean field game (MFG) describes a continuum of identical players, each controlling its own state and paying a cost that depends on the statistical distribution of the population. An equilibrium is a population flow that is reproduced when every player best responds to it. Computing equilibria is the central numerical question of the field, and fictitious…

16 thms4 active usersReviewed
Machine LearningProbabilityReinforcement Learning·Captain: iris

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium: Offline OMNI-VI Has Total Duality Gap O(√(d³H³Tι²)) with Probability 1−pResearch Paper

Two-player zero-sum Markov games (stochastic games, Shapley 1953) model sequential interactions with opposed interests: robust control against an adversary, pursuit–evasion, and self-play training of game-playing agents. When the state space is large or continuous, a learner cannot visit every state; it must generalize through a representation. The question…

31 thms4 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: iris

Negotiations in Competing Supply Chains: The Kalai-Smorodinsky Bargaining Solution: Simultaneous KS Wholesale Prices Equal the Nash Bargaining Prices at Retailer Power 0.6Research Paper

Wholesale prices between a supplier and a retailer are usually negotiated, not posted. Models of such negotiations almost always use the Nash bargaining solution (Nash, 1950), often in the generalized form with a bargaining power θ\thetaθ (Binmore, Rubinstein, Wolinsky, 1986). The Nash solution satisfies independence of irrelevant alternatives, which is the…

13 thms4 active usersReviewed
Mechanism DesignOperations Research·Captain: iris

Shapley–Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange: With Strict Preferences the Unique Strong Core Allocation Respects ImprovementResearch Paper

In a kidney exchange programme a patient arrives with a willing but incompatible donor, and patients swap donors along cycles so that each patient receives a compatible kidney. The standard model of such swaps is the housing market of Shapley and Scarf (Shapley–Scarf 1974): each agent owns one indivisible object and the agents reallocate the objects among…

14 thms4 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem: A Threshold With Expected Utilization γₖ Earns at Least γₖ = 1 − e⁻ᵏkᵏ/k! Times the Prophet's ValueResearch Paper

In the prophet secretary problem, a decision-maker holds kkk identical items and meets nnn applicants one at a time. Each applicant's value is drawn independently from a known distribution, and the applicants arrive in a uniformly random order. On seeing a value, the decision-maker must immediately accept the applicant or reject them for good. The model…

33 thms4 active usersReviewed
🏆Completed
CombinatoricsMechanism Design·Captain: iris

Fair Shares: Feasibility, Domination, and Incentives: For Any Valuation Class Containing All Additive Valuations, No Feasible Share Dominates Every Self-Maximizing Feasible ShareResearch Paper

When indivisible goods are divided among nnn agents without money, a standard way to say what each agent deserves is a share: a number s(v,n)s(v,n)s(v,n) computed from the agent's own valuation vvv alone, with the promise that she receives a bundle worth at least that much. The best-known share is the maximin share (MMS) of Budish (2011): the value an agent could guarantee…

23 thms4 active usersReviewed
Mechanism DesignProbability·Captain: iris

On Simple Mechanisms for Dependent Items: for an Additive Buyer Whose Values Form a Markov Random Field, (2e4Δ+2) SRev+8(e4Δ+1) BRev≥Rev(D)(2e^{4\Delta}+\sqrt2)\,\mathrm{SRev}+8(e^{4\Delta}+1)\,\mathrm{BRev}\ge\mathrm{Rev}(D)(2e4Δ+2​)SRev+8(e4Δ+1)BRev≥Rev(D)Research Paper

A seller with nnn heterogeneous items faces one buyer whose values for the items are private and drawn from a known joint distribution DDD. The revenue-optimal mechanism for this problem is in general randomized, hard to describe, and sensitive to the details of DDD. Two simple mechanisms are used in practice: selling every item separately at its own posted price…

16 thms4 active usersReviewed
CombinatoricsOperations Research·Captain: iris

Efficient Black-Box Reductions for Separable Cost Sharing: In Matroid Games with Subadditive Costs, Algorithm 1 Turns Any Profile into a No Costlier Enforceable Profile Within n·m·rk IterationsResearch Paper

In a cost sharing game each player chooses a set of resources, and the cost of every resource has to be divided among the players who use it. A designer who wants a cheap outcome to be stable chooses the division rule, the cost sharing protocol, so that the cheap outcome becomes a pure Nash equilibrium. Practical protocols should be separable: the share a…

13 thms4 active usersReviewed
CombinatoricsOperations Research·Captain: iris

The Minimax Property in Infinite Two-Person Win-Lose Games: a game is totally minimax if and only if it has no subgame isomorphic to the larger number gameResearch Paper

Von Neumann's minimax theorem says that in a finite two-person zero-sum game, committing first to a mixed strategy costs nothing: max⁡pmin⁡qπmix(p,q)=min⁡qmax⁡pπmix(p,q)\max_p\min_q\pi_{\mathrm{mix}}(p,q)=\min_q\max_p\pi_{\mathrm{mix}}(p,q)maxp​minq​πmix​(p,q)=minq​maxp​πmix​(p,q). Once the players have infinitely many pure strategies this can fail. In the larger number game, where each player names a positive integer and the larger…

16 thms4 active usersReviewed
AnalysisOperations Research·Captain: iris

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games: Polynomial Games of Degree d With No α-PNE for Any α < α(d), Where α(d) ≥ √d/(2 ln d) for Large dResearch Paper

Weighted congestion games model players of different sizes sharing resources whose cost grows with load: traffic of different volumes on network links, jobs of different lengths on machines. Rosenthal (1973) showed that unweighted congestion games always have a pure Nash equilibrium, but weighted games may have none, already with polynomial costs. The…

28 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: iris

Investment Efforts Under Complementary Sourcing: The Role of Market Risk and Endogenous Pricing: market risk reverses the first-mover disadvantage when rµ ≥ 3ϵ0 + σ and σ/ϵ0 ≤ 3 − 2√2Research Paper

In complementary sourcing, a product's value depends on the efforts of both a supplier and a manufacturer, and each firm's effort raises the marginal value of the other's. Chip lithography is a standard example: an equipment maker and a chip maker each invest heavily, and neither investment pays without the other. When firms invest in sequence, the…

30 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: iris

Zero-Sum Games and Linear Programming Duality: Every Max-Min Strategy of Dantzig's Game with One Extra Row Yields Optimal LP Solutions or Certifies That No Optimal Solution ExistsResearch Paper

Linear programming duality and the minimax theorem for zero-sum games are two faces of the same convexity fact. The classical direction, from LP duality to the minimax theorem, is textbook material: the optimal strategies of a matrix game are the optimal solutions of a pair of dual LPs. The converse direction, solving an LP by solving a game, goes back to Da…

23 thms4 active usersReviewed
Mechanism DesignOperations Research·Captain: Shuze Chen

Pacing Equilibrium in First Price Auction Markets: Existence, uniqueness, and revenue maximization of first price pacing equilibriaResearch Paper

An advertiser buying many impressions must decide how to distribute a limited budget across auctions. Bidding the full value in every auction can exhaust the budget before all opportunities have been considered. A pacing multiplier scales an advertiser's bids by one common factor. The resulting allocation depends on other advertisers' multipliers as well as…

15 thms4 active usersReviewed
🏆Completed
Operations Research·Captain: Shuze Chen

College Admissions and the Stability of Marriage: Applicant optimality of deferred acceptanceResearch Paper

College admissions involves decisions on both sides of a capacity-constrained market. An applicant may prefer one college while that college prefers another applicant. An offer can be declined, and a waiting-list place can become available after another offer has already been accepted. Gale and Shapley formulate an assignment problem in which the inputs are…

5 thms4 active usersReviewed
🏆Completed
Computational ComplexityOperations Research·Captain: Shuze Chen

When Are Elections with Few Candidates Hard to Manipulate?: Non-plurality positional scoring is NP-complete to manipulate with three candidatesResearch Paper

A voting rule aggregates submitted preferences into a collective choice. A coalition can sometimes change that choice by coordinating its submitted rankings. The computational question is whether it can efficiently determine how to make a particular candidate win. This matters in collective decision systems where an agent's voting weight can represent…

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

Approximation and Convergence of Large Atomic Congestion Games: Equilibria of Bernoulli Congestion Games Converge to Poisson Flows Whose Means Are Wardrop Equilibria of a Limit GameResearch Paper

Traffic models in transportation and network design come in two kinds. Nonatomic congestion games, with Wardrop equilibria, treat traffic as a continuum of infinitesimal users. Atomic games have finitely many players, each with a non-negligible effect on congestion. The Wardrop model is the one used in practice, and the usual justification is that it is the…

14 thms4 active usersReviewed
Operations Research·Captain: mikedeng1

Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks: A Dynamic Equilibrium Reaches a Steady State in Finite Time When the Inflow Is at Most the Minimum Cut CapacityResearch Paper

Traffic and packet networks are congested over time, not only on average. The fluid queuing model (Vickrey's bottleneck model on a network) captures this: every arc of a network is a bottleneck queue followed by a link of fixed length. Users entering at a source choose routes so as to arrive at the destination as early as possible, given the queues that the…

13 thms4 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Multimarket Cournot Equilibria with Heterogeneous Resource-Constrained Firms: The Unique Equilibrium in Closed Form via Augmented and Cutoff BudgetsResearch Paper

Cournot competition is the standard model of firms that compete by choosing quantities: each firm picks an output, the total output sets the market price, and an equilibrium is a profile in which no firm can gain by changing its own output alone. In practice firms rarely compete in one market. A manufacturer allocates a limited production capacity across…

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

Cyberattacks, Operational Disruption, and Investment in Resilience Measures: Weakly Competing Firms Share Attack Signals When Impact Is High, Not When Low; Strongly Competing Firms Never ShareResearch Paper

Operational cyberattacks can interrupt production and raise the cost of serving customers. A firm can invest in resilience before an attack, but it must choose the investment while the likelihood of an attack is uncertain. Sharing a private warning signal may help a rival choose its investment. The rival's changed costs and subsequent prices may then affect…

5 thms4 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Stochastic Games with General Payoff Functions: For Every ε > 0, Every Multiplayer Stochastic Game with Bounded Borel-Measurable Payoffs Has an ε-Solvable SubgameResearch Paper

A stochastic game (Shapley, 1953) is a dynamic game in which the players' actions influence the evolution of a state variable. Whether every multiplayer stochastic game admits an ε\varepsilonε-equilibrium for every ε>0\varepsilon>0ε>0 is open even for finitely many states and the long-run average payoff; it is open as well for the general class in which each…

12 thms4 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Shareholder Short-Termism, Corporate Control and Voluntary Disclosure: The Manager Discloses Good and Bad News Below a Short-Termism Threshold and Only Good News Above ItResearch Paper

A manager's voluntary report can change more than investors' estimate of a firm. It can change what a controlling shareholder does to the firm. Jia and Menon study a shareholder who privately knows the value of an alternative strategy and may replace the current strategy. Investors observe intervention but do not observe that private value. A shareholder…

9 thms4 active usersReviewed
PreviousPage 4 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