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
CombinatoricsLinear Optimization·Captain: iris

Popularity, Mixed Matchings, and Self-duality: every bipartite instance with strict preferences has a max-utility popular mixed matching {(M0,1/2),(M1,1/2)}, pure if a stable matching is perfectResearch Paper

In a two-sided matching market, applicants and jobs rank their acceptable partners, and a planner wants an assignment that is both acceptable to the participants and good for some external objective, such as total value. Stability (no applicant–job pair prefers each other to their assignments) is the classical acceptability notion, but it is restrictive:…

24 thms3 active usersReviewed
Operations ResearchOptimization·Captain: Shuze Chen

Blockchain-Enabled Deep-Tier Supply Chain Finance: Optimal direct financing and universal blockchain adoptionResearch Paper

A manufacturer can have ample cash while an upstream supplier lacks the funds needed to make production reliable. Financing that supplier through an intermediary changes both the cost of credit and the incentives to invest. Information is also uneven: a firm may know its immediate supplier's working capital without knowing the capital of a more distant…

17 thms3 active usersReviewed
Control TheoryOperations Research·Captain: Shuze Chen

Optimizing Free-to-Play Multiplayer Games with Premium Subscription: Optimal advertising and subscription pricingResearch Paper

A free-to-play multiplayer game earns subscription revenue only if players value the premium experience enough to pay for it. Yet converting free players into premium players also changes the experience of everyone else. Premium players may enjoy owning items that others lack, while free players may dislike comparisons with premium players. Advertising…

7 thms3 active usersReviewed
Complexity TheoryGraph TheoryOperations Research·Captain: Shuze Chen

Fair Division of a Graph: Maximin-share allocations on trees exist and can be computed in polynomial timeResearch Paper

An allocation of rooms to research groups may be impractical if one group receives rooms scattered throughout a building. The same issue appears when indivisible land plots must form a connected holding. In these examples, adjacency constrains which bundles can be allocated, while different participants may value the same items differently. Connected fair…

10 thms3 active usersReviewed
Operations ResearchStochastic Systems·Captain: mikedeng1

Dynamic Learning and Market Making in Spread Betting Markets with Informed Bettors: the inertial policy deters bluffing, drives the spread line to the median and has O(log T) regretResearch Paper

In a spread betting market a market maker quotes a line sss for a quantity whose outcome XXX is not yet known (a point spread in sports, a price level in finance), and bettors wager on either side of it. The market maker earns a commission on every bet and would like her line to sit at the median of XXX, where both sides are equally likely and she carries no…

19 thms3 active usersReviewed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Game of Thrones: Fully Distributed Learning for Multiplayer Bandits: Without Communication, the Game of Thrones Algorithm Has Expected Total Regret O(log^{1+δ} T)Research Paper

In a multiplayer multi-armed bandit, several agents repeatedly choose among the same finite set of arms, and two agents that choose the same arm collide and receive nothing. The model comes from cognitive radio and wireless networks: users share channels, a channel used by two users at once carries neither transmission, and the quality of a channel differs…

13 thms3 active usersReviewed
EconomicsOperations Research·Captain: mikedeng1

Multidimensional Targeting and Consumer Response: With a Small Ad Cost and a Click Cost Just Below the md-Equilibrium Threshold, Single-Dimensional Targeting Is Strictly More ProfitableResearch Paper

Firms that advertise online choose whom to target from the customer data they hold, and the industry's working assumption is that more granular data can only help: a firm that knows more about each consumer can at worst ignore the extra information. Despotakis and Yu (SSRN 3900394; Management Science, 2022, doi:10.1287/mnsc.2022.4604) show that this fails…

11 thms3 active usersReviewed
Economics·Captain: mikedeng1

Interactive Information Design: Every Information Design Game with Finite Message Sets Admits a Subgame Perfect EquilibriumResearch Paper

An information designer can change what others know without choosing their actions. When several designers disclose information at once, each designer's experiment affects the incentives faced by agents who receive messages from all of them. The resulting strategic problem appears in competing disclosures, advice, and mediated decisions. Koessler, Laclau,…

9 thms3 active usersReviewed
EconomicsOperations Research·Captain: mikedeng1

Two-Sided Platform Competition in a Sharing Economy: Which Wage Scheme Maximizes Platform Profit Is Decided by Demand- versus Supply-Side CompetitionResearch Paper

Sharing-economy platforms (ride-sharing, car-sharing, peer-to-peer lending) sit between two groups. They charge consumers a price and pay self-scheduling workers a wage, and they compete with rival platforms on both sides at once. How a platform pays its workers is a design choice that varies across the industry: some announce a fixed wage per job, some a…

9 thms3 active usersReviewed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Information Design for Congested Social Services: Optimal Need-Based Persuasion 4: Signaling Achieves the First-Best Admission Policy for All Welfare Weights Above a ThresholdResearch Paper

Social services such as public health clinics, legal aid offices and food banks are congested: users wait in a queue whose length they cannot see. Some users have no alternative (high need) and others have an outside option (low need). A provider cannot price access, but can decide what to tell arriving users about the queue. Anunrojwong, Iyer and Manshadi…

15 thms3 active usersReviewed
Linear OptimizationProbability·Captain: mikedeng1

Quantum Algorithms for Zero-Sum Games 1: With Step ε/4, Grigoriadis–Khachiyan Sampling Play Yields ε-Optimal Strategies After ⌈16 ln(nm/δ)/ε²⌉ Iterations with Probability ≥ 1 − δResearch Paper

Two-player zero-sum matrix games are the simplest model of strict competition, and computing their value is equivalent to linear programming. Many algorithms in optimization and learning (boosting, online learning with experts, approximate LP and SDP solvers) are, at their core, procedures that approximately solve such a game. For large games the cost of…

10 thms3 active usersReviewed
Economics·Captain: mikedeng1

Online Advertising, Data Sharing, and Consumer Control 1: The Ad Exchange Allows Cross-Targeting Exactly When (No Leave) and (No Leave & Snipe) Hold, and Both Advertisers Always Share Data With ItResearch Paper

Display advertising on the open web runs through ad exchanges, intermediaries that sell ad impressions on third-party publisher sites to advertisers. A large share of these ads is retargeting: an advertiser shows ads to consumers who recently visited its own website and so revealed purchase intent. Retargeting needs tracking data (a cookie or pixel placed…

12 thms3 active usersReviewed
Economics·Captain: mikedeng1

Sharing Sequentially Triggered Losses: Automated Conflict Resolution Through Smart Contracts 4: On Loss Trees the Same Four Axioms Characterize the Fixed-Fraction RulesResearch Paper

When one agent breaches a contract, the breach often forces its counterparty to breach its own contracts in turn, and the losses propagate. Supply chains are the standard example: a supplier that fails to deliver makes its customer fail to deliver to its own customers. Gudmundsson, Hougaard and Ko (Management Science 70(3), 2024) ask how the total loss of…

11 thms3 active usersReviewed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Retailer-Led Marketplaces 1: Below a Capacity Threshold the Monopolist Competes Only in the Top Marketplace Products (Mode I); Above It He Also Monopolizes Unsupplied Products (Mode II)Research Paper

Large online retailers such as Amazon run two businesses on one storefront. They sell products themselves, and they host a marketplace on which third-party sellers sell, paying the platform a percentage of their revenue. A retailer that also runs the marketplace can decide which products to sell itself, and it controls which offer most consumers see.…

16 thms3 active users
Graph TheoryOperations Research·Captain: mikedeng1

Flow Allocation Games 1: Every Unit-Ranking Game Has a Strong Equilibrium That Maximizes the Total FlowResearch Paper

Financial firms owe each other money. When some firms cannot meet their obligations, the payments that actually clear in the network are a fixed point: what a firm can pay depends on what it receives, which depends on what others can pay. Eisenberg and Noe (Management Science, 2001) introduced this clearing model under a fixed pro-rata payment rule. Later…

18 thms3 active users
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 6: With n Buyers and Dominant-Strategy Implementation, Selling Two Independent Goods Separately Earns at Least Half the Optimal RevenueResearch Paper

A seller who owns several goods and faces buyers with private values must decide how to sell them. The revenue-maximizing mechanism is known in closed form only for one good: for a single buyer it is a posted price, and for several buyers it is Myerson's optimal auction (Myerson 1981). With two or more goods the optimal mechanism may use lotteries, may be…

8 thms3 active usersReviewed
Dynamical SystemsLinear algebra·Captain: mikedeng1

Uncoupled Dynamics Do Not Lead to Nash Equilibrium 1: Near the Two-Player Unit-Disk Game Γ₀ of Section II, No Uncoupled Dynamic Is Nash-ConvergentResearch Paper

Learning in games asks whether players who adjust their strategies over time, by simple rules, end up at a Nash equilibrium. Many adaptive dynamics share one informational feature: each player's adjustment depends on the current play and on that player's own payoff function, but not on the payoffs of the others. Hart and Mas-Colell (AER 2003) call such…

14 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Cooperative Fuzzy Games 1: A Balanced Game without Side Payments Has a Nonempty Core Containing the Core of Its Fuzzy ExtensionResearch Paper

A game without side payments (an NTU game) describes cooperation in which utility cannot be transferred between players: each coalition AAA of players is assigned the set V(A)V(A)V(A) of payoff vectors it can secure on its own. The core is the set of payoffs to the grand coalition that no coalition can improve upon. Whether the core is nonempty is the basic stability…

13 thms3 active usersReviewed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design VIII: A Truthful Approximation Scheme for Bounded Scheduling with VerificationResearch Paper

Algorithmic mechanism design asks for algorithms whose inputs are held by self-interested agents: the designer can pay the agents, and must choose payments so that each agent's own interest leads it to reveal what the algorithm needs. Nisan and Ronen introduced the framework with task scheduling on unrelated machines as the running example (Nisan–Ronen 2001)…

16 thms3 active users
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

A General Framework for the Study of Decentralized Distribution Systems: A Core Allocation Rule Whose Nash Equilibrium Is First-BestResearch Paper

Retailers that sell the same product can raise their joint profit by pooling: stock left over at one location is shipped to meet unmet demand at another, and stock can be held in shared warehouses until demand is known (Eppen 1979; Eppen and Schrage 1981). When the retailers are independent firms, pooling creates two questions at once. After demand is…

10 thms3 active usersReviewed
Mechanism Design·Captain: mikedeng1

Transparency in Team ContractsResearch Paper

A principal who delegates a project often knows more about its prospects than the people whose effort makes it succeed. Revealing that information changes agents’ incentives and therefore changes the payments needed to obtain their effort. The question is whether a principal can lose substantially by disclosing everything, even when she remains free to…

26 thms2 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Structural Complexity of Matching with IndifferencesResearch Paper

Centralized school choice and other two-sided assignment systems are run by clearinghouses that announce a single outcome. When preferences contain ties (a student may be indifferent between several schools), the classical notion of stability splits into weak, strong and super stability (Irving 1994), and a deterministic rule must also say which stable…

19 thms2 active usersReviewed
Computational ComplexityLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Finding a Positive Index Nash Equilibrium is PPADS-CompleteResearch Paper

Every finite game has a Nash equilibrium, but equilibria are not all alike. In a nondegenerate two-player game, each equilibrium carries a Shapley index of +1+1+1 or −1-1−1, a local orientation that sums to +1+1+1 over all equilibria. The index is an established selection criterion: an isolated equilibrium is sustainable exactly when it has index +1+1+1 (Govindan et al.,…

38 thms2 active usersReviewed
Mechanism Design·Captain: mikedeng1

The Power and Limits of Money Burning in Bilateral TradeResearch Paper

In bilateral trade a seller owns one indivisible good and a buyer may want it. Each trader privately knows their own value. A mechanism asks both for reports and decides whether to trade and what each trader pays or receives. A mechanism is strongly budget-balanced (SBB) when the buyer's payment always equals the seller's receipt. It is weakly…

38 thms2 active usersReviewed
Analysis·Captain: mikedeng1

Tight Bounds on the Menu-Size Complexity of Approximately Optimal Auctions with Two ItemsResearch Paper

A seller offering two items to one buyer can offer lotteries as well as deterministic purchases. Describing a lottery requires two allocation probabilities and a price, and an auction may offer many such alternatives. Menu size measures how many distinct nonnull alternatives are required. The resulting question concerns the complexity of implementing a…

21 thms2 active usersReviewed
PreviousPage 5 of 13Next

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