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 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
🏆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
🏆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
🏆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
🏆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
🏆Completed
Markov ChainOperations Research·Captain: mikedeng1

Trust and Reciprocity in Firms’ Capacity Sharing: A Non-Trivial Trading-Favors Equilibrium Exists if and only if Each Firm’s Discounted Return on a Favor Exceeds Its Opportunity and Service CostResearch Paper

Service firms with idle capacity often turn away customers while a nearby competitor sits idle, and the reverse happens an hour later. Sharing capacity would help both, but contracting on every transfer is costly, and monitoring the partner's state is usually impossible. Informal arrangements in which favors are returned rather than paid for are a natural…

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

Sequential Mechanisms with Ex Post Individual Rationality: The Revenue-Optimal Dynamic Mechanism Is Built by Backward Induction on Cumulative Surplus-Utility Tradeoff FunctionsResearch Paper

Many goods are sold to the same buyer repeatedly: advertising impressions, cloud capacity, seasonal tickets. The buyer's value for each sale is learned only shortly before it, and a seller who knows the distribution of future values can extract more revenue with a dynamic mechanism, one whose terms on later days depend on what the buyer reported earlier.…

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

The Informational Role of Buyback Contracts: The Most Efficient Separating Equilibrium Exists, and the Less Risky Manufacturer Signals by Lowering Both Wholesale and Returns PricesResearch Paper

A buyback contract lets a retailer return unsold goods to a manufacturer at an agreed returns price. The promise changes the retailer's willingness to order before demand is known. If the manufacturer may fail to honor it, the retailer must also judge how credible the promise is. Wang, Gurnani, and Subramanian study what the contract's wholesale and returns…

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

Report-Dependent Utility and Strategy-Proofness: The True Ranking Is Optimal for Every Decreasing Report-Dependent Utility If and Only If No Ranking Raises the Probability of a Top-r MatchResearch Paper

Deferred acceptance and top trading cycles are strategy-proof: submitting one's true preference ranking is optimal whatever the other participants do (Roth, 1982). School-choice and residency-match systems around the world use them for this reason. Yet laboratory and field data show participants misreporting systematically, most often by leaving popular…

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

How Should We Score Athletes and Candidates: Geometric Scoring Rules: A Scoring Rule Is Independent of Unanimous Winners and of Unanimous Losers if and only if It Is a Geometric Scoring RuleResearch Paper

Season-long sports competitions (the biathlon World Cup, Formula One, the motorcycle Grand Prix, golf's FedEx Cup) rank athletes by adding up points awarded for the positions they take in individual races. The same mechanism, under the name positional scoring rule, is one of the oldest objects of social choice theory: Borda's rule, plurality and…

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

Negative Advertising and Competitive Positioning: When Negative Advertising Is Permitted, There Is an Equilibrium in Which the Entrant Co-Locates and Both Firms Prioritize Positive AdvertisingResearch Paper

Negative advertising (comparative advertising that points to a rival's flaw) is used both in product markets and in political campaigns, and its regulation differs across jurisdictions: until the 1990s it was not permitted in numerous countries of the European Union (Anderson and Renault, 2009). Many models of advertising take the products' positions as…

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

Extended Producer Responsibility for Pharmaceuticals: End-of-Pipe Control Maximizes Total Welfare for Medicines with High Health Benefit, High Collection Cost and High Environmental DisutilityResearch Paper

Unused prescription medicines create disposal and public health costs, while a patient may use less medicine than a doctor prescribes. A regulator can make the pharmaceutical producer collect unused medicine, or charge a fee on dispensed medicine and use the proceeds to fund collection. These two policies charge the producer for different quantities. Alev,…

17 thms2 active users
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Robust Bidding in First-Price Auctions: How to Bid Without Knowing What Others Are Doing: Under Variation in Bidding the Unique Minimax Loss Bid Equalizes Both Maximal Losses and Increases in nResearch Paper

First-price sealed-bid auctions are used for procurement contracts, treasury securities, timber, and, since 2019, most display advertising. The classical advice for how to bid comes from Bayes–Nash equilibrium: each bidder knows the distribution of the others' values, and everyone plays the equilibrium. Practitioners rarely have that information. In a…

11 thms2 active usersReviewed
🏆Completed
EconomicsProbability·Captain: mikedeng1

Does Competition Improve Analysts’ Forecast Informativeness?: Competition Lowers Informativeness Exactly When Payoffs Are Convex in Rank, Signals Are Correlated and Prior Uncertainty Is HighResearch Paper

Sell-side analysts are ranked against each other. Published rankings, such as Institutional Investor's annual "All-Star" ranking cited in the paper, and the career outcomes tied to them, reward an analyst for being more accurate than peers, not only for being accurate. A common intuition holds that such competition disciplines analysts and makes their…

32 thms2 active users
🏆Completed
Operations Research·Captain: mikedeng1

Implementing Environmental and Social Responsibility Programs in Supply Networks Through Multiunit Bilateral Negotiation: A Log-Cost Shortest Path Tree Maximizes the Retailer's GainResearch Paper

Retailers sometimes ask every supplier in a production network to meet a common environmental or social responsibility standard. A program can fail to produce its expected value if even one firm declines to participate. The retailer therefore needs a way to pass commitments and payments through the network, including to suppliers with whom it has no direct…

5 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Linear Program-Based Approximation for Personalized Reserve Prices: Rounding the Profile LP Earns a (1 + 2(√2 − 1)e^(√2 − 2))⁻¹ ≈ 0.684 Fraction of the Optimal Eager Second-Price RevenueResearch Paper

Online advertising exchanges sell most impressions through second-price auctions with reserve prices. A seller who has logged the bids of many past auctions wants reserves that would have earned the most revenue on that history. When the bids are drawn i.i.d. from a distribution, the revenue-optimal reserves on a large sample approximate the revenue-optimal…

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

The Buck-Passing Game: Every Deterministic Buck-Passing Game Has a Prior-Free Pure Nash EquilibriumResearch Paper

In a buck-passing game, each participant chooses who will receive a task, burden, or token next. The eventual share of time spent holding it depends on every participant's choice. This makes a small network into a game: a local change of one outgoing edge can alter the long-run burden across an entire part of the network. Cominetti, Quattropani, and…

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

Procurement Mechanisms with Post-Auction Pre-Award Cost-Reduction Investigations: Symmetric Suppliers Earn Weakly Higher Ex Ante Profits When Investigations Precede the AwardResearch Paper

Large manufacturers procure components by competitive bidding, and many of them also run cost-reduction investigations: the buyer's engineers visit a supplier's plant and look for process changes that lower the cost of the contracted part. The savings are passed to the buyer as a lower contract price. In practice such investigations usually happen after the…

8 thms2 active usersReviewed
PreviousPage 15 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