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

Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria 1: For Cancelable Valuations the Bluff Profile Is an Exact Pure Nash Equilibrium of Round-RobinResearch Paper

Round-Robin is the simplest allocation procedure for indivisible goods: agents take turns, in a fixed order, and at each turn the active agent takes her favourite good among those still available. Run on truthful preferences with additive valuations it returns an allocation that is envy-free up to one good (EF1), which is why it is the default baseline of…

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

Self-Preferencing and Search Neutrality in Online Retail Platforms I: Under a Low Commission, Search Neutrality Strictly Reduces Consumer Surplus When the Two Products Are Similarly PopularResearch Paper

Large retail platforms both host independent sellers and sell their own products, and they control the order in which products appear in search results. When the platform ranks its own product first regardless of relevance, it engages in self-preferencing. Regulators have treated this as a competition problem: the European Commission opened a second…

15 thms3 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Self-Preferencing and Search Neutrality in Online Retail Platforms II: At Equal Popularity, a Commission Below ρL/ρH Makes Search Neutrality Lower Consumer Surplus and Raise the Third-Party ProfitResearch Paper

Large retail platforms such as Amazon both host independent sellers and sell their own products in competition with them. The platform also controls the search ranking, the order in which products are shown to a consumer. The European Commission and the US Federal Trade Commission have examined whether platforms rank their own products ahead of rivals' (self…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Prophet Secretary Through Blind Strategies 2: No Stopping Strategy Can Guarantee More Than √3 − 1 of the Prophet's Expected Maximum in Random OrderResearch Paper

In a prophet inequality a gambler sees the realizations of independent nonnegative random variables one at a time and must decide irrevocably, at each step, whether to stop and keep the current value. Her performance is compared with that of a prophet who sees everything in advance and takes the maximum. The ratio between the two is the standard benchmark…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Product Price, Quality and Service Decisions under Consumer Choice Models II: The Oligopoly Has a Unique Nash Equilibrium, with Monopoly Qualities and Service Durations and Lower PricesResearch Paper

Firms that sell durable goods set three things at once: a price, a quality level, and the length of an ancillary service that comes free with the product, such as a warranty. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.0947) study these joint decisions under multinomial logit (MNL) demand. For a…

13 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Dynamic Pricing in the Presence of Social Learning and Strategic Consumers 3: With Social Learning, Responsive Pricing Beats Pre-Announced Pricing When Consumers Are ImpatientResearch Paper

A recurring question in revenue management with strategic consumers is whether a seller gains from price commitment. When customers are forward-looking, a seller who announces its whole price path in advance (pre-announced pricing) removes the customers' incentive to wait for a markdown the seller would otherwise be tempted to give; a seller who keeps the…

9 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Dynamic Pricing in the Presence of Social Learning and Strategic Consumers 2: Under Responsive Pricing, Social Learning Raises Optimal Expected Profit When Consumers Are Impatient or PatientResearch Paper

A firm launching a new experience good does not know how good the product is, and neither do its customers. Early buyers post reviews, and customers who wait learn from them: this is social learning (SL). Forward-looking customers anticipate this and may delay their purchase until reviews are available, which cuts into the firm's early sales. Papanastasiou…

12 thms3 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Intrinsic Robustness of the Price of Anarchy II: Outcome Sequences with Vanishing Average Regret Have Average Cost at Most the Robust Price of Anarchy Times OptimalResearch Paper

In a game, each participant chooses a strategy while the cost of that choice depends on what everyone else does. A network user may choose a route, for example, but its travel time depends on the routes chosen by other users. The price of anarchy compares the cost of self-interested outcomes with the best joint outcome. A guarantee restricted to a Nash…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

A Modern Introduction to Online Learning XIV: Optimistic FTRL Self-Play on a Smooth Convex-Concave Function Has Duality Gap at Most a Constant over TTextbook

A saddle-point problem asks one player to choose a decision that keeps a payoff small while another chooses a decision that makes it large. Such problems include two-player zero-sum games and constrained optimization written through a Lagrangian. Online convex optimization supplies a way to construct approximate saddle points from repeated play: each player…

5 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Intrinsic Robustness of the Price of Anarchy III: For Every Set of Cost Functions, Congestion Games Are Tight — the Worst-Case Pure Price of Anarchy Equals the Best Smoothness BoundResearch Paper

In a congestion game, each player chooses resources and pays a cost that depends on how many players use each chosen resource. Such games model shared facilities and network use, where independently chosen strategies can cost more in total than a coordinated choice. The price of anarchy measures this inefficiency by comparing the social cost of an…

13 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 4: Bundling k ≥ 2 I.I.D. Goods Guarantees a Fraction c/log k of the Optimal RevenueResearch Paper

A seller with several goods and a single buyer is the smallest setting in which multi-dimensional mechanism design differs from the one-good theory. For one good, Myerson's theorem (Myerson 1981) says the optimal mechanism posts a price. For two or more goods the optimal mechanism may use lotteries, may be non-monotone in the buyer's values, and is in…

15 thms3 active usersReviewed
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
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 3: Selling k ≥ 2 Independent Goods Separately Guarantees a Fraction c/log² k of the Optimal RevenueResearch Paper

A seller who knows the distributions of a buyer's values for several goods can, in principle, design a mechanism that offers lotteries and prices conditional on the buyer's reported values. Finding the best such mechanism can be difficult even with two goods. Separate selling is much simpler: choose a one-good price for each item and let the buyer decide…

12 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games 1: Every Game Has a Pure Nash Equilibrium Iff the Distribution Rules Are Generalized Weighted Shapley ValuesResearch Paper

In a cost sharing game (or, symmetrically, a revenue sharing game) self-interested players each pick a set of resources, every resource generates a welfare that depends on who uses it, and a distribution rule splits that welfare among the users. Network formation, atomic routing, coverage and distributed-control problems all fit this model (Anshelevich et…

17 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Approximate Revenue Maximization with Multiple Items 1: For Independent Groups of Goods Y and Z, Rev(Y, Z) ≤ Rev(Y) + Rev(Z) + BRev(Y) + BRev(Z)Research Paper

A seller who offers several goods to a buyer with private values has to choose a selling mechanism. For one good the optimal mechanism is known: post the best take-it-or-leave-it price (Myerson 1981). For two or more goods the optimal mechanism can be complicated: it may use lotteries, its menu may be infinite, and it may not be computable in closed form…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Online Contention Resolution Schemes with Applications to Bayesian Selection Problems 5: A (b, c)-Selectable Greedy OCRS Rounds x ∈ bP to E[f(S)] ≥ c·F(x) for Monotone Submodular fResearch Paper

Many online selection problems ask an algorithm to accept or reject items one at a time, irrevocably, while keeping the accepted set feasible: independent in a matroid, a matching in a graph, or within a knapsack budget. In Bayesian versions, such as prophet inequalities and posted-price mechanisms, a fractional point xxx of a relaxation of the feasible sets…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Online Contention Resolution Schemes with Applications to Bayesian Selection Problems 1: Every Loopless Matroid Polytope Has a (b, 1−b)-Selectable Deterministic Greedy OCRSResearch Paper

In online selection, items reveal information one at a time, and each decision to accept an item is irrevocable. A matroid constraint permits some subsets and excludes others; it covers choices such as selecting linearly independent vectors or acyclic edges. A fractional solution can assign an acceptance probability to each item, but independent activations…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs II: Posted Expected Weakly (α, β₁, β₂)-Balanced Prices Earn 1/(α(2β₁ + 4β₂)) of the Expected Welfare of ALGResearch Paper

A prophet inequality compares an online decision maker, who sees random inputs one at a time and must commit irrevocably, with a "prophet" who sees all inputs in advance. The classic single-item version (Krengel–Sucheston, Samuel-Cahn) says that a well-chosen fixed threshold earns at least half of the expected maximum. In mechanism design the same statement…

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

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs I: Expected (α, β)-Balanced Prices Scaled by α/(1 + αβ) Earn 1/(1 + αβ) of the Expected Welfare of ALGResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must decide irrevocably, with a "prophet" who sees all values in advance. The classic result of Krengel, Sucheston and Garling (1977) and Samuel-Cahn (1984) says that for a single item and independent values a single threshold earns at least half of the expected…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals III: Even for I.I.D. Variables, No Nonadaptive Threshold Rule Beats the Factor 1 − 1/eResearch Paper

In a prophet inequality, a decision maker observes random rewards one at a time and must choose without seeing future realizations. The benchmark is a prophet who sees all rewards and selects their maximum. A nonadaptive threshold rule chooses a threshold for each reward before observations begin, then accepts the first arriving reward that crosses its…

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

A Little Charity Guarantees Almost Envy-Freeness II: With Additive Valuations Such an Allocation Gives Every Agent Her Maximin Share Divided by 2 − |P|/nResearch Paper

A set of nnn agents must share a set MMM of mmm indivisible goods, each agent valuing bundles of goods by her own valuation. Two fairness notions dominate the literature. Envy-freeness up to any good (EFX), introduced by Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang (EC 2016), asks that no agent prefer another's bundle once any single good is removed…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A game-theoretic approach to computation offloading in mobile cloud computing III: Variational Solutions Are the Nash Equilibria of the Extended Cloudlet-Pricing GameResearch Paper

Mobile devices can divide work between local execution, a nearby shared cloudlet, and a remote cloud. A cloudlet has limited capacity, so one user's choice changes the delay faced by the others. Cardellini and coauthors model this as a generalized Nash equilibrium problem, in which each user's feasible choices depend on the aggregate cloudlet load. The…

8 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

On the Complexity of Nash Equilibria and Other Fixed Points 4: The Fixed Points of the Division-Free Map G_I(x)ij = max(x_ij + u_i((i:j); x−i) − t_i, 0) Are Exactly the Nash EquilibriaResearch Paper

Nash's existence theorem for finite games is a fixed-point theorem: one writes down a continuous map from the set of mixed strategy profiles to itself whose fixed points are exactly the Nash equilibria, and applies Brouwer's theorem. Nash's own map (Nash 1951) divides by 1+∑jmax⁡(0,⋅)1+\sum_j \max(0,\cdot)1+∑j​max(0,⋅), and the choice of map matters as soon as the question is…

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

On the Complexity of Nash Equilibria and Other Fixed Points 2: Block Matching Pennies Gives Every Block the Same Probability and the Matching Player Full Support in Every Nash EquilibriumResearch Paper

Reductions that prove hardness for Nash equilibrium computation encode a computation (a circuit, a fixed-point problem) into the probabilities that players put on their strategies in every equilibrium. For the encoding to be meaningful, the designer has to control how each player distributes probability across groups of strategies, independently of the…

9 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

On the Complexity of Nash Equilibria and Other Fixed Points 1: ε-Nash Equilibria Are Weak (n+1)ε-Fixed Points of Nash's Function, and Weak ε²/(4c²n³)-Fixed Points Are ε-Nash EquilibriaResearch Paper

Nash proved that every finite game has an equilibrium by exhibiting a continuous map of the set of mixed profiles into itself whose fixed points are exactly the equilibria, and applying Brouwer's fixed point theorem (Nash, 1951). Computationally, the same map is the bridge between games and fixed-point problems: complexity classes for total search problems…

11 thms3 active usersReviewed
PreviousPage 15 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