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

Optimal Electricity Imbalance Pricing for the Emerging Penetration of Renewable and Low-Cost Generators: Optimal Pricing Makes Full Commitment an Equilibrium with Minimum Expected Deadweight LossResearch Paper

Electricity is traded in two stages. In a day-ahead market generators commit quantities for a delivery period; at delivery, deviations between committed and actual production are settled in a real-time imbalance market at an imbalance price. As the share of wind and solar grows, the generators with the lowest marginal cost are also those with the largest…

12 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: iris

Best of Both Worlds Ad Contracts: Guaranteed Allocation and Price with Programmatic Efficiency: The Market-Maker Contract Strictly Raises Revenue and Welfare at Unchanged Utilities and EfficiencyResearch Paper

Display advertising is sold in two ways. Reservation contracts guarantee an advertiser a volume of impressions at a fixed price, negotiated in advance. Programmatic auctions (ad exchanges) sell impressions one at a time, efficiently, but at a price and with an allocation that the advertiser does not know in advance. Advertisers with fixed campaign budgets…

18 thms2 active usersReviewed
Graph TheoryOperations Research·Captain: iris

Coordination Games on Weighted Directed Graphs: on an open chain of m cycles of v nodes, improvement paths of length at most 3vm³ reach a Nash equilibrium from every joint strategyResearch Paper

In a coordination game on a graph, every player is a node and chooses a colour, and a node is rewarded for agreeing with its neighbours. These games model the adoption of a common standard, clustering, and the stabilisation of distributed protocols. When the graph is directed, the dynamics change sharply. A node is paid only by its in-neighbours and pays…

11 thms2 active usersReviewed
EconomicsOperations Research·Captain: iris

Blockchain Adoption in a Supply Chain with Manufacturer Market Power: the manufacturer's incremental welfare is strictly positive, and all parties adopt whenever the cost does not exceed itResearch Paper

A manufacturer that sources from several suppliers faces a recall problem. When a defect is reported and the source cannot be traced, every unit on the shelf is recalled, including goods from suppliers who did nothing wrong. A shared ledger that records provenance changes this: only the defective batch needs to be recalled. A Walmart case study reports…

16 thms2 active usersReviewed
EconomicsOperations Research·Captain: iris

Algorithms for Persuasion with Limited Communication: in symmetric instances some optimal k-signal scheme has a sender-optimal s-Pareto collection of recommendation pointsResearch Paper

Bayesian persuasion (Kamenica and Gentzkow, 2011) studies a sender who knows the state of the world and commits to a randomized signaling policy before a receiver acts. In the classical model the sender may send as many distinct messages as the receiver has actions, and by the revelation principle an optimal policy simply recommends an action. In many…

9 thms2 active usersReviewed
Mechanism DesignOperations Research·Captain: iris

Non-Truthful Position Auctions Are More Robust to Misspecification: The α-GSP Mechanism Has an Efficient Nash Equilibrium Whenever the α-VCG Mechanism DoesResearch Paper

Search engines sell the ad slots next to their results in position auctions: advertisers bid, the highest bidder gets the top slot, the second highest the next one, and so on. A slot higher on the page is clicked more often, and the ratio of click rates between slots is described by a vector of relative position values. The textbook truthful mechanism,…

13 thms2 active usersReviewed
EconomicsMechanism DesignOperations Research·Captain: iris

Pick-an-Object Mechanisms: an individually rational rule is pick-an-object implementable in perfect ex-post equilibrium iff it is strategy-proof and monotonically discoverableResearch Paper

Many allocation procedures used in practice — school choice, university admissions, course allocation — are run as one-shot direct mechanisms: every participant submits a full ranking, and an algorithm such as deferred acceptance or top trading cycles computes the assignment. Sequential alternatives, in which participants repeatedly pick one option from a…

8 thms2 active usersReviewed
EconomicsOperations Research·Captain: iris

Educational Inequality and Reservation Policy in Developing Markets: the inequality-eliminating seat transfer has a closed form and strictly exceeds the welfare-maximizing transferResearch Paper

Many developing countries reserve college seats for disadvantaged students, and how large the reservation should be is a live policy question: in 1993 the Supreme Court of India capped reservations at 50% of seats. Bao, Ni and Singh (SSRN 3772113, version of May 30, 2023; published in Management Science, doi:10.1287/mnsc.2021.00249) build an equilibrium…

56 thms2 active usersReviewed
CombinatoricsMechanism DesignOperations Research·Captain: iris

Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings: the unique legal set of assignments is the set of stable assignments of a subinstanceResearch Paper

Stable assignments are the standard output of centralized school choice, but insisting on stability can leave many students worse off than necessary (Faenza–Zhang, §1). Morrill (2016) proposed legality as a relaxation motivated by legal standing: a student who forms a blocking pair has a complaint only if the remedy, the assignment of that student to that…

19 thms2 active usersReviewed
EconomicsOperations Research·Captain: iris

Algorithmic Transparency with Strategic Users: when a firm strictly prefers a transparent hiring algorithm, region by region in the agents' cost planeResearch Paper

Firms increasingly screen job applicants, borrowers and customers with algorithms built on observable features. Regulators and the public ask for these algorithms to be made transparent, and firms often resist, arguing that agents who know the algorithm will game it. Wang, Huang, Jasin and Singh (arXiv:2008.09283, 2020; published in Management Science,…

38 thms2 active usersReviewed
Economics·Captain: iris

Commitment Against Front-Running Attacks: the commit-reveal protocol has an equilibrium without front running iff βπ ≤ c, and otherwise every equilibrium carries a front-running threatResearch Paper

On public blockchains, pending transactions wait in a public mempool before a block includes them. Anyone who sees a profitable transaction there can send a competing one with a higher fee and have it executed first. This is front running. It is a large, measured source of losses on decentralized exchanges and in other smart contracts (Daian et al., 2020).…

21 thms2 active usersReviewed
Mechanism DesignOperations Research·Captain: iris

Capacity Games with Supply Function Competition: under submodularity, at-cost bids with marginal-contribution margins are a supply-chain-optimal Nash equilibriumResearch Paper

A buyer facing uncertain demand often secures supply in two stages: it first reserves capacity from several suppliers, and after demand is observed it decides how much of the reserved capacity to use. Electricity procurement (reserve markets), contract manufacturing and logistics all have this shape. In practice each supplier quotes a reservation price for…

11 thms2 active usersReviewed
EconomicsMechanism DesignOperations Research·Captain: iris

Parallel Lotteries: Insights from Alaskan Hunting Permit Allocation: every k-ticket lottery equilibrium allocation is (2 − 1/k)-trade efficientResearch Paper

Alaska allocates scarce big-game hunting permits through a draw in which each applicant may buy up to six tickets and spread them across the permit lotteries of her choice; an applicant drawn in several lotteries keeps the permit she ranks highest. Designs of this kind, parallel lotteries, are simple to run and give applicants freedom to express intensity…

15 thms2 active usersReviewed
Operations ResearchStochastic Systems·Captain: iris

A Mean Field Games Model for Cryptocurrency Mining: With Exponential Utility the Equilibrium Is Unique and Explicit, Every Miner Hashing at the Constant Rate KMw(r;γ)/(c(1+M)²)Research Paper

Proof-of-work blockchains such as Bitcoin pay a reward to whoever first solves a hashing puzzle. The protocol adjusts the difficulty so that rewards arrive at a roughly constant rate for the system as a whole, about one every ten minutes, and a miner's chance of winning the next reward is proportional to its share of the total hash rate. Mining is costly…

13 thms2 active usersReviewed
Operations Research·Captain: iris

Deferred Acceptance with Compensation Chains: every DACC algorithm stops at a stable matching, and every stable matching is the outcome of some DACC algorithmResearch Paper

The deferred acceptance algorithm of Gale and Shapley (1962) finds a stable matching in a two-sided market, but only one side proposes, and the result is the stable matching that side likes best. Other stable matchings, such as the median stable matchings of a market, are out of its reach. A decentralized process in which both men and women make offers, in…

24 thms2 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: iris

Prophet Matching with General Arrivals: a 0.337-competitive prophet inequality for online weighted matching with edge arrivals in general graphsResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must accept or reject each irrevocably, with a "prophet" who sees all values in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) guarantees half of the prophet's expected value. Since the work of Hajiaghayi, Kleinberg and Sandholm…

19 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: Shuze Chen

Optimal Matchmaking Strategy in Two-Sided Marketplaces: Lower bounds on communication for stable matchmakingResearch Paper

A platform may know the services its users seek and offer while still lacking the preferences that determine whether a particular match is worthwhile. Learning those preferences requires communication. A lower bound on that communication would distinguish a limitation of one search algorithm from a limitation shared by every platform design. Peng Shi's Optim…

8 thms2 active usersReviewed
Operations Research·Captain: Shuze Chen

Platform Preannouncement Strategies: The Strategic Role of Information in Two-Sided Markets Competition: Formal preannouncement under strong taste preferencesResearch Paper

A platform release can attract both customers and developers. A customer's valuation depends on the number of other customers and the available applications, while a developer values access to customers. Before adoption, those numbers are expectations. Announcing features can influence these expectations, but communicating information costs money and also…

6 thms2 active usersReviewed
Operations Research·Captain: Shuze Chen

Duopoly Competition with Network Effects in Discrete Choice Models: Exactly two asymmetric equilibriaResearch Paper

Network effects make a product more attractive when other customers use it. In a market with two otherwise identical products, that feedback raises a concrete question: must an equilibrium still exist in which the firms attract equal market shares? Chen and Chen's Proposition 4 identifies a regime in which the answer is negative. At sufficiently low common…

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

Multiplicative Pacing Equilibria in Auction Markets: Every Pacing Game Admits a Second Price Pacing EquilibriumResearch Paper

Internet advertising markets sell impressions, clicks and conversions one auction at a time, and most advertisers attach a budget to a whole campaign. Bidding one's full value until the budget runs out is suboptimal: the buyer drops out early and misses later auctions that may offer the same value at a lower price. A widely used remedy is multiplicative…

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

Competition Between Two-Sided Platforms Under Demand and Supply Congestion Effects: Surge Pricing Lowers Customer and Raises Driver Utility, and Near the Base Market Size Beats Fixed Prices for BothResearch Paper

Ride-hailing platforms such as Uber and Lyft raise prices when demand spikes, a practice known as surge pricing. The practice is controversial: customers see higher fares, and it is not obvious that anyone but the platform gains. Bernstein, DeCroix and Keskin (MSOM 2020; author version SSRN 3250224) study two competing platforms whose customers dislike…

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

Algorithms for Max-Min Share Fair Allocation of Indivisible Chores: Greedy Round-Robin Gives Every Agent at Least (2 − 1/N) Times Her Max-Min Share, and the Factor Cannot Be ImprovedResearch Paper

Many allocation problems distribute work rather than benefits: household and office tasks, teaching loads, shifts, maintenance duties, or jobs assigned to parallel machines. Each item is a chore, which every agent would rather not receive, and chores cannot be split. Under indivisibility an exactly fair split usually does not exist, so the fair-division…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

New Combinatorial Insights for Monotone Apportionment: House-Monotone and Quota-Compliant Apportionments Are the Seat Counts of Extreme Points of a Network Flow LP with Lookahead Φ(p, H)Research Paper

An apportionment method distributes the HHH seats of a house among nnn states in proportion to their populations. Exact proportionality is impossible with integer seats, so methods are judged by axioms. Two axioms date back to the debates over the seats of the US House of Representatives. Quota compliance asks that each state receive its exact proportional…

8 thms2 active usersReviewed
EconomicsOperations Research·Captain: mikedeng1

Solving Strong-Substitutes Product-Mix Auctions: Allocate Splits the Target Bundle into Demanded Bundles within |J|·C(n+1,2) IterationsResearch Paper

The product-mix auction was developed in 2007–8 for the Bank of England (Klemperer 2010) to sell many differentiated goods (loans against different qualities of collateral) in a single round. Each bidder submits a list of simple bids, each naming a price for every good and a quantity, and the auctioneer chooses prices and allocations that respect every bid.…

19 thms2 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

Decomposition of Games: Some Strategic Considerations: Duplicating a Strategy Commutes with the (μ,γ)-Decomposition into Potential, Harmonic and Nonstrategic ComponentsResearch Paper

A finite game can be split into simpler pieces. Candogan, Menache, Ozdaglar and Parrilo (Math. Oper. Res. 36 (2011)) showed that the space of finite games is the direct sum of potential, harmonic and nonstrategic games: potential games have pure equilibria and well-behaved learning dynamics, harmonic games generalize matching pennies, and nonstrategic games…

18 thms2 active usersReviewed
PreviousPage 22 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