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
Algebraic GeometryOperations ResearchOptimization·Captain: mikedeng1

Nash Equilibrium Problems of Polynomials: For Generic Polynomial Data the KKT-Cut Algorithm Terminates Finitely, Finding a Nash Equilibrium or Certifying That None ExistsResearch Paper

A Nash equilibrium problem (NEP) asks for strategies of several players such that no player can lower its own cost by deviating while the others keep theirs fixed. NEPs model competition in electricity markets, environmental agreements, and the training of generative adversarial networks. When the players' problems are nonconvex, an equilibrium requires…

13 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
Mechanism DesignProbability·Captain: mikedeng1

The Square Root Agreement Rule for Incentivizing Truthful Feedback on Online Platforms: Strict Truthful Equilibrium Approximately Payoff-Dominating All Symmetric Equilibria for Many TasksResearch Paper

Online platforms (labor marketplaces, review sites, crowdsourcing services) rely on feedback from their users: did the plumber arrive on time, is this image labelled correctly. The answers cannot be checked against ground truth, so a platform that rewards feedback must reward it by comparing it with other users' answers. This is the problem of peer…

8 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
Mechanism DesignProbability·Captain: mikedeng1

Towards a Functional Fee Market for Cryptocurrencies: Truthful Bidding Is Not Dominant, but the Expected Gain from Strategic Bidding Converges to 0 as the Number of Users DivergesResearch Paper

A cryptocurrency user can attach a fee to a transaction, and a miner can choose which waiting transactions enter the next block. When the most valuable waiting transactions compete for a limited number of places, the fee rule affects both the user's bid and the amount the user expects to pay. Basu, Easley, O'Hara and Sirer study a protocol that charges…

8 thms2 active usersReviewed
EconomicsOperations Research·Captain: mikedeng1

Testing, Voluntary Social Distancing, and the Spread of an Infection: Greater Testing Raises the Equilibrium Infection Probability of the Type That Mixes Its Social ActivityResearch Paper

Testing makes an infected person less likely to pass an infection to someone else. In a society whose contacts depend on voluntary social activity, that direct benefit changes behavior: an agent who expects fewer infections may choose more contacts. The central question is whether the added contacts can outweigh the direct benefit of testing in equilibrium.…

14 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
CombinatoricsMechanism DesignOperations Research·Captain: mikedeng1

Polyhedral Clinching Auctions for Two-Sided Markets: An Incentive-Compatible, Individually Rational, Budget-Balanced, Pareto-Optimal Mechanism ExistsResearch Paper

Auctions in which bidders face budget constraints do not fit the classical quasi-linear theory: a bidder cannot pay more than a fixed amount, however much the goods are worth to him. For a single divisible good, Dobzinski, Lavi and Nisan showed that the adaptive clinching auction of Ausubel is incentive compatible, individually rational and Pareto optimal,…

12 thms2 active usersReviewed
🏆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
EconomicsOperations Research·Captain: mikedeng1

Strategic Inventories under Supply Chain Competition: Under Fierce Chain-to-Chain Competition, Strategic Inventories Leave All Manufacturers and Retailers Strictly Worse OffResearch Paper

A manufacturer that sells through an independent retailer charges a wholesale price above cost, and the retailer then adds its own margin: the double marginalization problem of vertical contracting. Anand, Anupindi and Bassok (Management Science 2008) showed that in a two-period monopoly chain the retailer can blunt this by buying more than it sells in the…

8 thms2 active usersReviewed
🏆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
Control TheoryOperations ResearchProbability+1·Captain: mikedeng1

Dynkin Games with Incomplete and Asymmetric Information: With Linear Payoffs, a Threshold Stop and a Belief-Reflecting Randomised Stop Form a Saddle PointResearch Paper

An optimal stopping game asks two players to choose when to stop a shared process. The first player receives one payoff if they stop first and another if the second player stops first. Such a game changes when one player knows a parameter that the other can only infer from observations. The informed player can reveal information through the timing of a…

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

Revenue-Sharing Allocation Strategies for Two-Sided Media Platforms: Pro-Rata vs. User-Centric: The Ratios π2j/π1j for Which Each Rule Sustains All Artists Form Two Explicit IntervalsResearch Paper

Music and podcast streaming services such as Spotify, Apple Music and Deezer charge every subscriber the same monthly fee and pass a share of the collected revenue to the artists. How that share is split is contested. The industry default, pro-rata, pools all fees and pays each artist her share of total streams. The alternative, user-centric, splits each…

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

Preference Elicitation for Participatory Budgeting: Randomized Threshold Approval Votes Achieve Distortion O(log² m)Research Paper

In participatory budgeting, residents of a city vote on how to spend part of a public budget on a list of proposed projects, each with a known cost. The practice has been adopted by cities in North America and Europe, including New York City, Chicago, Madrid and Paris, the last two each spending more than 100 million euros through participatory budgets in…

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

Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation: Recursive Probabilistic Serial Is Ex-Ante Envy-Free and Ex-Post Envy-Free up to One GoodResearch Paper

Many allocation problems hand out indivisible goods without money: course seats, shifts, donated food, inherited items. An integral allocation of such goods can rarely be envy-free. With one good and two agents, someone always envies. The standard remedies are of two kinds. Randomization restores fairness in expectation: the probabilistic serial rule of…

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

Implications of Price Matching in Supply Chain Negotiation: Under Symmetric Bargaining Power the Seller Prefers Price Matching to Simultaneous Negotiation and Both Buyers Prefer the ReverseResearch Paper

A seller that supplies several competing buyers may negotiate a wholesale price with each of them independently and simultaneously (simultaneous negotiation, SN), or may commit to charge all of them the same price (price-matching negotiation, PM). PM is the bargaining counterpart of the most-favoured-customer clause, a contractual guarantee that a customer…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Dynamic Fair Resource Division: The Optimal Fairness Ratio of d-Uniform Control Vectors Is 1/((d+1)·ln((d+1)/d)), Attained by the Frugally Fair AlgorithmResearch Paper

Shared computing infrastructure — a data-centre cluster, a cloud platform's memory — is divided among users who arrive over time. Two requirements pull against each other. Proportional fairness asks that, when ttt users are present, each holds at least a 1/t1/t1/t fraction of the resource. Limited disruption asks that the system not take resource away from running…

9 thms2 active usersReviewed
PreviousPage 24 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