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
Operations ResearchProbability·Captain: mikedeng1

Search for an Immobile Hider on a Binary Tree with Unreliable Locational Information: The Value Is 2qμ + (p − q)D, Attained by the Recursive Hider Distribution and the Favoring-Bias SearcherResearch Paper

Search games model a Searcher looking for an object or a person whose location is chosen adversarially: a lost hiker, a mine, a hidden explosive device, a fugitive. In the classic search game on a tree, a Hider stands still at a point of a tree network, and a Searcher starts from the root and moves at unit speed. The payoff is the time to find the Hider. Gal…

8 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Internal Capital Allocation, Voluntary Disclosure, and Investment Efficiency: When a Multi-Divisional Firm Beats Two Stand-Alone FirmsResearch Paper

Conglomerates and stand-alone firms finance projects differently. A multi-divisional firm runs an internal capital market: headquarters raises funds externally and then decides which division gets them. A stand-alone firm must raise capital project by project. A long line of work in corporate finance asks when the internal market is more efficient: Stein (19…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Exact Penalization of Generalized Nash Equilibrium Problems: Under a Slater-Type Condition, Every Equilibrium of the ℓq-Penalized Nash Game Solves the Generalized Game for All Large PenaltiesResearch Paper

In a generalized Nash equilibrium problem (GNEP) each player's feasible set depends on the strategies of the other players. Such coupled constraints arise wherever players share a resource: transmission capacity in electricity and telecommunication markets, emission caps in environmental games, track time in railway pricing, road capacity in transportation…

8 thms2 active usersReviewed
Mechanism DesignOperations Research·Captain: mikedeng1

Budget-Management Strategies in Repeated Auctions: At Symmetric System Equilibria, Reserve Pricing Earns at Least the Profit of Thresholding, and Thresholding at Least That of Bid ShadingResearch Paper

Online advertising platforms sell impressions through repeated auctions, and advertisers typically buy them under a budget: a cap on what they spend over a campaign. Because the advertisers cannot re-optimize their bids in every auction, the platform usually manages their budgets for them, adjusting how each advertiser participates so that spending tracks…

12 thms2 active usersReviewed
Algebraic TopologyCombinatorics·Captain: mikedeng1

Envy-Free Division of Multilayered Cakes: For a Prime-Power Number q of Groups with m ≤ q ≤ n, a Feasible Contiguous Group-Birthday Envy-Free Multi-Division by q − 1 Long Knives ExistsResearch Paper

Envy-free cake cutting asks for a division of a divisible resource, modelled as the interval [0,1][0,1][0,1], among agents with individual preferences so that no agent prefers another agent's share to its own. For a single cake and contiguous pieces, the existence of envy-free divisions goes back to Stromquist (1980) and to Su's Sperner-lemma proof (1999).

7 thms2 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Coordinating Project Outsourcing Through Bilateral Contract Negotiations: Bargaining Powers Under Which Each Contract Form Coordinates a Single-Task ProjectResearch Paper

Large projects such as buildings, infrastructure and software systems are routinely outsourced. The client who owns the project pays a subcontractor to execute it, and the subcontractor privately chooses how hard to work. Faster work costs him more, while the benefit of early completion goes mainly to the client. The paper notes that the fixed-price and cost…

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

Coordination for Assembly: With at Most M − 1 Feedback Periods, the Subgame-Perfect Secure Equilibrium Has Every Contractor Exert the Minimum Effort in Every PeriodResearch Paper

Assembly projects such as aircraft programs or large software releases split work among several contractors, each responsible for one component. The finished product can only be as advanced as its least-developed component, so the contractors play a minimum-effort game (also called a weakest-link game): the project's value depends on the minimum of the…

5 thms2 active usersReviewed
Linear OptimizationMechanism DesignOperations Research·Captain: mikedeng1

Spatio-Temporal Pricing for Ridesharing Platforms: The STP Mechanism Is Subgame-Perfect Incentive Compatible, Welfare-Optimal, Envy-Free and Core-Selecting from Any HistoryResearch Paper

Ridesharing platforms set prices and dispatch drivers over a road network whose demand changes within minutes: a stadium empties, rush hour starts, a neighbourhood goes quiet. Drivers are not employees. They may decline a dispatch, drive somewhere else, or stop working, and the platform pays no one in advance for staying in place. Prices that look only at…

25 thms2 active usersReviewed
Machine LearningOptimization·Captain: mikedeng1

Greedy Adversarial Equilibrium: An Efficient Alternative to Nonconvex–Nonconcave Min-Max Optimization: Every Bounded Function with Lipschitz Hessian Has a Greedy Adversarial EquilibriumResearch Paper

Min-max problems min⁡xmax⁡yf(x,y)\min_x\max_y f(x,y)minx​maxy​f(x,y) model two-player zero-sum games and appear across machine learning and operations research: adversarial training of classifiers, generative adversarial networks, and robust optimization against an adversarial perturbation. When fff is convex in xxx and concave in yyy, von Neumann's minimax theorem gives a saddle point, and…

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

Forewarned Is Forearmed? Contingent Sourcing, Shipment Information and Supplier Competition: Contingent Sourcing Makes Both Suppliers Weakly Better Off but Can Make the Buyer Worse OffResearch Paper

Firms that source from a low-cost but unreliable supplier often hedge with a second, reliable supplier. A recent development is that buyers can now track a shipment in transit (temperature loggers for perishables, GPS and inspection reports) and learn, before the selling season, whether the cheap order has been damaged. With that information the buyer can…

10 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningReinforcement Learning·Captain: mikedeng1

V-Learning—A Simple, Efficient, Decentralized Algorithm for Multiagent Reinforcement Learning: Independent V-Learning Finds a Coarse Correlated Equilibrium with Gap O((H²S/K)Ξ(A,K/S,ι) + √(H⁵Sι/K))Research Paper

In multi-agent reinforcement learning several agents act in a shared, changing environment, each pursuing its own reward. The standard model is the Markov game (stochastic game), going back to Shapley (1953). When agents learn from experience rather than from a known model, the natural target is an equilibrium of the game, and the natural question is how…

10 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Information Disclosure and Promotion Policy Design for Platforms: Under Myopic Pricing, the Long-Run Average Optimal Consumer Surplus Equals the Concavification of the Best Confounding SurplusResearch Paper

Online marketplaces decide which products to show first. A promotion puts a seller's product in front of consumers who will not search further, so it changes both the seller's sales and the surplus of the consumers who see it. A seller who is uncertain about the market sets prices from the sales they observe, and the platform's promotion decisions shape…

13 thms2 active usersReviewed
Graph TheoryProbability·Captain: mikedeng1

Pure Nash Equilibria and Best-Response Dynamics in Random Games: Best-Response Dynamics Reaches a Pure Nash Equilibrium for All Large N When the Tie Probability Is SmallResearch Paper

A pure Nash equilibrium (PNE) of a game is a strategy profile from which no player gains by a unilateral deviation. Unlike mixed equilibria, pure equilibria need not exist, and even when they do they can be hard to find: computing an equilibrium is PPAD-complete in general (Daskalakis, Goldberg & Papadimitriou 2009). The simplest learning procedure that…

15 thms2 active usersReviewed
🏆Completed
EconomicsLinear OptimizationOperations Research·Captain: mikedeng1

Fully Polynomial-Time Approximation Schemes for Fair Rent Division: Algorithm 1 on the Slope-Rounded Instance Halts in Polynomially Many Iterations with an ε-Envy-Free SolutionResearch Paper

Housemates who share a house must decide who gets which room and how the total rent is split. A solution pairs an assignment of rooms to agents with a rent for each room, and it is envy-free if no agent prefers another room at that room's rent. Envy-free rent division is the textbook example of fair division with money and is the mathematical core of…

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

Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location: The Coordinatewise Median with Predictions Is √(2c²+2)/(1+c)-Consistent and √(2c²+2)/(1−c)-RobustResearch Paper

Learning-augmented algorithms use a machine-learned prediction to perform better when the prediction is accurate, while keeping a worst-case guarantee when it is not. The two guarantees are called consistency (performance under a correct prediction) and robustness (performance under an arbitrary prediction). Agrawal, Balkanski, Gkatzelis, Ou and Tan (arXiv:2…

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

Optimal Priority-Based Allocation Mechanisms: In a Regular Market, Deferred Acceptance Implements Every Feasible Budget Set Probability Matrix, and DA-STB Exactly the Nested-Within-Segment OnesResearch Paper

School districts, public housing authorities and refugee resettlement agencies allocate scarce items (school seats, apartments, slots) without prices. Most such systems are priority-based: each applicant receives a priority, possibly depending on observable characteristics such as neighborhood or sibling status, and a mechanism such as deferred acceptance…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationProbability·Captain: mikedeng1

From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation: Quasi-Arithmetic Pooling Is the Unique Report Maximizing the Worst-Case Profit Over Sub-Contracted ExpertsResearch Paper

Forecast aggregation asks how to combine several experts' probability forecasts for the same event into one forecast. The two classical answers are linear pooling (average the probability vectors) and logarithmic pooling (average the log-probabilities and renormalize). Neither is justified by the way forecasts are usually evaluated: with a proper scoring…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

Approximate Nash Equilibria in Large Nonconvex Aggregative Games: existence of a 2H((√q+1)MΔ/n)^γ-pure Nash equilibrium, built by Shapley–Folkman disaggregation of the convexified gameResearch Paper

Many large-population systems are modelled as aggregative games: each agent's cost depends on its own decision and on an average of everybody's decisions. Examples are electric-vehicle charging and demand response, where a household's cost depends on its own consumption profile and on the aggregate load through the electricity price, and congestion and…

12 thms2 active usersReviewed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Tractable Equilibria in Sponsored Search with Endogenous Budgets: bidding valuations shaded by 1 + r_j with slack budgets is an ε-approximate equilibrium in large marketsResearch Paper

Sponsored-search platforms sell ad impressions through auctions in which advertisers submit both per-impression bids and a budget that caps their total spend. The platform then decides which auctions to run, subject to everybody's budget. Most auction theory treats budgets as exogenous constraints. In practice an advertiser chooses the budget, and…

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

Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online: GenSm-Main Is a Universally Truthful, Individually Rational, Budget-Feasible 505-Approximation MechanismResearch Paper

A buyer with a fixed budget wants to hire a team from a pool of sellers, each of whom knows privately what participating would cost them. The buyer values teams through a set function and pays each hired seller. The sellers are strategic: they report whatever cost serves them best. A budget-feasible mechanism decides whom to hire and what to pay so that…

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

Mean Field Equilibrium: Uniqueness, Existence, and Comparative Statics: Ergodic Kernels Increasing in the Own State and Decreasing in the Population State Allow at Most One Mean Field EquilibriumResearch Paper

Dynamic games with many players, such as dynamic oligopolies with investment, industry dynamics models, and heterogeneous-agent macroeconomic models of Bewley–Aiyagari type, are rarely tractable through Markov perfect equilibrium: the number of population states a player must track grows too fast with the number of players. Mean field equilibrium (MFE)…

11 thms2 active usersReviewed
Mechanism DesignOperations Research·Captain: mikedeng1

Fair-Share Allocations for Agents with Arbitrary Entitlements: Every Additive Instance Has an Allocation Giving Each Agent max{3/5, 1/(2−b_i)} of Her AnyPrice ShareResearch Paper

Fair division of indivisible goods asks how to split a set of items among agents who value them differently, with no money changing hands. Many allocation problems are not symmetric: partners in a venture hold different stakes, heirs inherit different fractions of an estate, and countries or departments receive budgets in proportion to size. Such settings…

12 thms2 active usersReviewed
Control TheoryOperations ResearchStochastic Systems·Captain: mikedeng1

Investment in the Common Good: Free Rider Effect and the Stability of Mixed Strategy Equilibria: A Mixed Strategy Two-Stage Subgame Perfect Equilibrium Survives Moderate AsymmetryResearch Paper

Many goods are maintained by several parties at once: a shared infrastructure, a fishery, an industry's reputation, a public research base. Each party bears the full cost of its own investment while every party enjoys the benefit, so each prefers that someone else pay. This free rider problem is classically studied as a war of attrition, and continuous-time…

17 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Selling Assets: Are Sellers Better Off with Strong Buyers?: Under Free Entry, a More Dominant Strong Buyer Lowers the Seller's RevenueResearch Paper

A seller who can attract a buyer with a higher valuation might expect a higher auction price. That intuition holds when the number of competing buyers is fixed. If other buyers must pay to learn their valuations and decide whether to enter, a stronger buyer can instead cause some of them to stay out. Marquez and Singh study this response in a second-price…

7 thms2 active usersReviewed
Dynamic ProgrammingEconomics·Captain: mikedeng1

Asset Dissemination through Dealer Markets: The Strategies Built from the Collected Demand Function Form a Rank-Free EquilibriumResearch Paper

Many assets, such as corporate and municipal bonds, securitized products and new issues, trade over the counter: there is no central exchange, and an asset reaches its final buyers through a sequence of bilateral trades between dealers. Empirical work on these markets documents intermediation chains, in which a block of securities passes through several…

12 thms2 active usersReviewed
PreviousPage 23 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