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

The Price of Anarchy of Finite Congestion Games III: The Price of Anarchy of the Maximum Social Cost Is Theta(sqrt N)Research Paper

In a congestion game, several users choose facilities and each facility becomes more costly as more users choose it. Such games model settings in which each participant chooses a route or collection of resources for personal use while the resulting load is shared. A pure Nash equilibrium is a stable choice of routes: no single participant can lower their…

8 thms3 active usersReviewed
🏆Completed
Economics·Captain: mikedeng1

Competitive Equilibrium with Indivisible Goods and Generic Budgets 3: Two Agents with Identical Additive Preferences and Generic Budgets Have a Competitive Equilibrium Giving Truncated SharesResearch Paper

How should a set of indivisible items (courses, shifts, inherited objects) be divided among people who have different entitlements but no money to transfer? A classical answer for divisible goods is the competitive equilibrium from equal incomes (CEEI): give every agent a budget of artificial currency, find prices at which every agent can afford her…

13 thms3 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Supplier Centrality and Auditing Priority in Socially Responsible Supply Chains II: A Stable Joint-Auditing Coalition Audits the Common Supplier and Shares Costs FairlyResearch Paper

Brands that sell consumer goods are held responsible by the public for the labour and safety practices of their suppliers. After the 2013 Rana Plaza collapse in Bangladesh, about 200 clothing brands and retailers signed the Accord on Fire and Building Safety and inspect roughly 1,600 factories jointly; pharmaceutical companies such as Pfizer and GSK audit…

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

Supplier Centrality and Auditing Priority in Socially Responsible Supply Chains I: Under Downstream Competition No Buyer Audits the Common Supplier in Any EquilibriumResearch Paper

Brands are routinely held responsible for the labour and environmental practices of their suppliers. A brand that is linked in public to a non-compliant supplier loses consumer willingness to pay, and firms answer this risk by auditing their suppliers. Supply networks are not trees, however: one supplier often serves several competing brands. Chen, Qi and…

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

Quality in Supply Chain Encroachment I: With Endogenous Uniform Quality, an Encroaching Manufacturer Gains and the Retailer Always LosesResearch Paper

Manufacturers increasingly sell directly to consumers through their own stores and websites, alongside the independent retailers that carry their products. This practice is called supply chain encroachment. Retailers routinely resent it, and examples range from beer brewers to personal computers. Arya, Mittendorf and Sappington (Marketing Science, 2007)…

9 thms3 active usersReviewed
🏆Completed
Captain: carlok

WorstCaseEq I: Theorem 3Research Paper

Load balancing on identical parallel links is the example Koutsoupias and Papadimitriou used to define the price of anarchy: the ratio of the social cost of a Nash equilibrium to the social optimum (Koutsoupias–Papadimitriou 2009). Theorem 3 of the journal version is the two-link case. It is the first sharp bound in that paper, and the later two-speed bound…

5 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

Randomized quasipolynomial-time mean-payoff gamesOpen Problem

Mean-payoff games ask which starting positions allow a player to guarantee a nonnegative long-run average reward. Binary-encoded weights make the bit cost of solving the complete winning set a central part of the question. The source manuscript presents the surrounding research claim.

6 thms3 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 4: Changing Only the Nonstrategic Component Makes the Pure Nash Equilibria Coincide with the Pareto Optimal ProfilesResearch Paper

A finite strategic game can be changed in ways that no player can detect strategically. Adding to player mmm's utility any function that does not depend on player mmm's own strategy leaves every unilateral comparison "is strategy aaa better for me than strategy bbb, given what the others do?" unchanged, so it leaves every best response and every pure Nash…

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

A Multiple-Choice Secretary Algorithm with Applications to Online Auctions: The Recursive k-Choice Secretary Algorithm Earns at Least (1 − 5/√k) Times the Sum of the k Largest ValuesResearch Paper

The secretary problem asks how well an online decision maker can do when items arrive one at a time in random order and each must be accepted or rejected on the spot. With a single selection, the classical rule (observe a 1/e1/e1/e fraction, then take the first item better than everything seen) selects the best item with probability about 1/e1/e1/e, and no rule does…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

How Bad is Selfish Routing? 4: With Polynomial Latencies of Degree p and Nonnegative Coefficients the Cost of a Nash Flow Is at Most p + 1 Times the Optimal CostResearch Paper

In a road or communication network carrying a large population of users, each user picks a route that is fastest for itself given the congestion caused by everyone else. The resulting traffic pattern, a Wardrop or Nash equilibrium, need not minimize the total travel time: Braess's paradox shows that adding a road can make every user slower. Transportation…

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

The Price of Anarchy is Independent of the Network Topology: For a Standard Latency Class Containing the Constants, Two-Link Networks Attain the Worst Nash/Optimal Cost Ratio α(L)Research Paper

In a road or communication network where each unit of traffic picks its own route, the outcome is a Nash flow (Wardrop equilibrium): no traffic can lower its own latency by switching paths. It is well known since Pigou (1920) that such selfish routing can be inefficient: the total latency of a Nash flow may exceed that of the best centrally planned flow.…

12 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
🏆Completed
Operations Research·Captain: mikedeng1

Potential Games 3: A Finite Game Has the Finite Improvement Property If and Only If It Has a Generalized Ordinal PotentialResearch Paper

In a strategic game, players may repeatedly change their own choices when a change raises their payoff. This gives a simple model of decentralized adjustment: each move uses the current profile and one player's immediate incentive. The central question is whether such adjustment can continue forever. Monderer and Shapley introduced the finite improvement…

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

Potential Games 2: Every Finite Potential Game Is Isomorphic to a Congestion GameResearch Paper

Congestion games model situations in which agents choose sets of shared resources and the payoff of each resource depends only on how many agents use it: drivers choosing routes through road segments, jobs choosing machines, flows choosing links in a network. Rosenthal (A class of games possessing pure-strategy Nash equilibria, Int. J. Game Theory 2, 1973)…

13 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

Cooperative Fuzzy Games 3: The Diagonal Formula Is the Unique Continuous Linear Pareto-Optimal, Symmetric and Atomic Value of Smooth Fuzzy GamesResearch Paper

A value for cooperative games assigns to every game a payoff vector, chosen by axioms rather than by bargaining. Shapley's value (1953) does this for finite games with side payments, and Aumann and Shapley (Values of Non-Atomic Games, 1974) extended it to games with a continuum of players, where it is given by a diagonal formula: a player's value is the…

12 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 3: A Coalition Technology Satisfying Gross Substitutes for m + 1 Identical Firms Has a Strict Core AllocationResearch Paper

Workers can form groups and produce an output that they divide through salaries. A group may object to a proposed allocation when it can pay all of its members at least as much and one member more. The central question is whether any allocation survives every such objection. Kelso and Crawford's 1982 paper gives a sufficient condition based on how an…

6 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 4: Without Ties the Salary-Adjustment Process Reaches the Firm-Optimal Discrete Strict Core AllocationResearch Paper

Labor markets match heterogeneous workers to heterogeneous firms, and the terms of each match — the salary — are negotiated. Kelso and Crawford (Econometrica 50 (1982)) studied such a market in which a firm may hire many workers, its output depends on the whole set it hires, and salaries are set worker by worker. Their model contains the marriage problem of…

8 thms3 active usersReviewed
🏆Completed
Mechanism DesignOperations Research·Captain: mikedeng1

Job Matching, Coalition Formation, and Gross Substitutes 2: Under Gross Substitutes Every Job-Matching Market with Continuous Salaries Has a Strict Core AllocationResearch Paper

Labour markets match workers to firms that hire teams: a firm's output depends on the whole set of workers it employs, while each worker holds one job. A salary agreement is stable when no firm and group of workers can renegotiate among themselves to the benefit of all of them. Shapley and Shubik (1971) showed that such stable outcomes exist when each firm…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Cooperative Fuzzy Games 2: A Game with Side Payments Has a Nonempty Core Iff It Is Balanced, and Then Its Core Is the Core of Its Concave Fuzzy ExtensionResearch Paper

A cooperative game with side payments assigns to each coalition of players the total payoff it can secure on its own and share freely among its members. The core is the set of ways of dividing the payoff of the grand coalition that no coalition can improve upon. It is the basic stability notion of cooperative game theory and of its applications in…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Cooperative Fuzzy Games 4: The Fuzzy Core of an Exchange Economy Coincides with Its Set of Walras EquilibriaResearch Paper

The core of an exchange economy is the set of allocations that no group of consumers can improve upon by trading only among themselves. The Walras equilibria (competitive equilibria) are the allocations supported by a price system at which every consumer maximizes preference on a budget set. Every Walras equilibrium is in the core, but for a fixed finite…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments IV: Uniform Pricing Earns OPT/(1 + ln(v_m/v_1)) in Unit-Demand Min-PricingResearch Paper

A seller with nnn distinct items faces mmm consumers, each of whom wants at most one item. Choosing item prices to maximise revenue in this setting is the unit-demand envy-free pricing problem, introduced by Rusmevichientong and studied in algorithmic game theory and revenue management since the mid-2000s. Optimal prices are hard to compute in general, so the…

13 thms3 active usersReviewed
🏆Completed
Markov ChainProbability·Captain: mikedeng1

The Evolution of Conventions I: In a Weakly Acyclic Game, Adaptive Play with k ≤ m/(L_Γ + 2) Converges Almost Surely to a ConventionResearch Paper

A convention is a pattern of behaviour that is customary because everyone expects everyone else to follow it: driving on the right, or which party yields at a narrow bridge. Peyton Young's The Evolution of Conventions (Econometrica 61 (1993) 57–84) asks how such a pattern can emerge from decentralized play. The players have limited memory and limited…

22 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

On General Minimax Theorems 2: Kneser–Fan — If f Is Concave-Convexlike and u.s.c. in μ on Compact M, Then sup inf f = inf sup fResearch Paper

A minimax theorem asserts that for a real function f(μ,ν)f(\mu,\nu)f(μ,ν) of two variables the order of optimization does not matter:

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

On Cores and Indivisibility 1: The Housing Market's Game Without Side Payments Is BalancedResearch Paper

A market in which each trader owns one indivisible good has a basic coordination question: can all goods be reassigned so that no group of traders can withdraw its own goods and improve every member's outcome? Houses are the paper's running example. Monetary transfers and fractional houses are absent, so ordinary convex allocation arguments do not describe…

11 thms3 active users
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Some Theoretical Aspects of Road Traffic Research II: Equal Journey Times on Alternative Routes — Exactly the Routes with bᵢ < t Are Used, qᵢ = pᵢ(1 − bᵢ/t)Research Paper

Planning a road improvement requires an estimate of how traffic will redistribute over the routes affected. Because speed falls as flow rises, sending every vehicle along the route that is quickest today changes which route is quickest. J. G. Wardrop posed the question in its simplest setting in 1952: a given flow QQQ chooses among DDD alternative routes…

6 thms3 active usersReviewed
PreviousPage 16 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