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
CombinatoricsOperations Research·Captain: mikedeng1

Theory of Games and Economic Behavior VI: Splitting Sets and the Decomposition Partition of a GameTextbook

Chapter IX of von Neumann and Morgenstern's Theory of Games and Economic Behavior asks when a game played by many participants is really several separate games played side by side. The authors' motivation (41.1) is methodological: the general theory of the nnn-person game becomes unmanageable as nnn grows, and one way to gain insight into large games is to…

16 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Value of Information in Bayesian Routing Games II: Equilibrium Adoption Rates of Information Systems Are the Minimizers of the Equilibrium PotentialResearch Paper

Traffic information systems (TIS) such as navigation apps send drivers private, noisy signals about the state of the road network: incidents, weather, closures. When several such systems coexist, their subscribers act on different information, and the congestion each population experiences depends on how all of them route. A question then arises for…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Information Sharing in a Supply Chain with a Common Retailer 1: Under Production Diseconomy the Retailer Earns More from Sequential Information Contracting and the Manufacturers from ConcurrentResearch Paper

Retailers hold point-of-sale data that their suppliers cannot observe, and large retailers sell access to it through data-sharing programs (Costco's CRX, Walmart's Retail Link and similar programs). When one retailer carries the substitutable products of two competing manufacturers, sharing its demand information is a strategic decision: a manufacturer who…

17 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design VII: Compensation-and-Bonus Based on a Non-Optimal Approximation Algorithm Is Not TruthfulResearch Paper

Algorithmic mechanism design studies optimization problems whose inputs are held by self-interested agents: the algorithm must compute a good solution and, through payments, make it in each agent's interest to report its input honestly. Nisan and Ronen introduced the field with the problem of scheduling tasks on unrelated machines, where each machine is an…

5 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchOptimization·Captain: mikedeng1

Algorithmic Mechanism Design III: No Additive Truthful Mechanism Achieves a c-Approximation for Task Scheduling for Any c < nResearch Paper

Algorithmic mechanism design studies optimization problems whose inputs are held by self-interested agents: an algorithm must not only compute a good solution but also pay the agents so that reporting their data truthfully is in their own interest. Nisan and Ronen introduced the field in Algorithmic Mechanism Design (Games Econ. Behav. 35, 2001) with task…

8 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Bargaining under Incomplete Information III: Trade Probability and Expected Profits in the Uniform Linear EquilibriumResearch Paper

A buyer and a seller negotiate over a single indivisible good. Each knows what the good is worth to them but not what it is worth to the other side, and each shades their offer to exploit the other's uncertainty. Chatterjee and Samuelson (Bargaining under Incomplete Information, Operations Research 31(5), 1983) modelled this as a one-shot game in which both…

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

Strategic Inventory and Supplier Encroachment: For Any Positive Holding Cost the Buyer Withholds Strategic Inventory When the Direct Selling Cost Is Just Below 5/6, at Total Holding Cost Below 11/72Research Paper

Two strategic levers shape the balance of power between a manufacturer and the retailer that resells its product. The first is strategic inventory: a buyer that orders more than it sells today, and carries the surplus into the next period, weakens the supplier's leverage over tomorrow's wholesale price. Anand, Anupindi and Bassok (Management Science 2008)…

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

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders III: A Greedy Price-Update Algorithm Is a 2-Approximation for XOS BiddersResearch Paper

In a combinatorial auction a set of mmm items is sold to nnn bidders who value bundles of items rather than single items. Spectrum auctions, procurement of transportation lanes and the allocation of cloud resources all have this form, and the central algorithmic question is how to allocate the items so as to maximize the social welfare, the sum of the bidders'…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders II: Clause-Based Randomized Rounding for XOS BiddersResearch Paper

In a combinatorial auction a seller offers mmm indivisible items to nnn bidders, each of whom values bundles of items rather than single items. Allocating the items so as to maximize the total value (the social welfare) is the central optimization problem of the area: it models spectrum auctions, procurement and resource allocation, and it is NP-hard and hard…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders I: LP Rounding for Subadditive BiddersResearch Paper

In a combinatorial auction a seller offers mmm indivisible items to nnn bidders, each of whom values bundles of items rather than single items. Allocating the items to maximize total value is the basic welfare problem of spectrum auctions, procurement and resource allocation, and it is the running example of algorithmic mechanism design. For general valuations…

12 thms2 active usersReviewed
🏆Completed
Mechanism DesignOperations ResearchProbability·Captain: mikedeng1

Bargaining under Incomplete Information II: The Linear Equilibrium of the Sealed-Offer Rule for Uniform ValuesResearch Paper

A buyer and a seller negotiate over one indivisible good. Each knows the good's worth to themselves but not to the other side, so each shades their offer to exploit the other's uncertainty, and some mutually profitable trades fail. Chatterjee and Samuelson (Bargaining under Incomplete Information, Operations Research 31(5), 1983) modelled this as a one-shot…

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

Monotonic Solutions of Cooperative Games 2: The Shapley Value Is the Unique Symmetric Strongly Monotonic Allocation ProcedureResearch Paper

Cost and benefit allocation problems arise whenever several parties share a joint undertaking: towns building a common water supply, divisions of a firm sharing overhead, users of a multi-purpose reservoir. They are modelled as cooperative games, and a rule that divides the joint value among the players is an allocation procedure. The standard such rule,…

15 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Existence of an Equilibrium for a Competitive Economy I: Equilibrium Exists When Every Consumer Can Trade Every GoodResearch Paper

Walras (1874) described an economy as a system of simultaneous equations, one per market, and argued that a set of prices clearing all markets exists because the number of equations equals the number of unknowns. Counting equations proves nothing, and the question of whether competitive equilibrium exists at all remained open for eighty years. Wald…

16 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

A Supply Chain Theory of Factoring and Reverse Factoring 1: The Supplier's Equilibrium Choice Among Recourse, Non-Recourse and Reverse FactoringResearch Paper

Small and medium-sized suppliers that sell to large retailers typically ship first and are paid weeks or months later. Until the invoice is paid, the supplier's cash is trapped in accounts receivable, while production has to be financed up front. Factoring (selling or pledging the receivable to a financial intermediary for immediate cash) and reverse…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On Minimizing a Convex Function Subject to Linear Inequalities II: Optimality Conditions for the Sum of the Largest Linear FormsResearch Paper

In 1955 E. M. L. Beale showed how Dantzig's simplex method, which was built for linear objectives, can be carried over to certain nonlinear convex objectives that are minimized subject to linear inequalities (Beale 1955). Section 4 of that paper treats one such objective: the sum of the ttt largest of a set of ggg linear forms. Beale's motivation comes from the…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 1: Threshold Purchasing Policies under Contingent PricingResearch Paper

Retailers of fashion and seasonal goods sell at a premium price early in the season and mark the remaining stock down later. When customers anticipate the markdown, some of them who would buy at the premium price instead wait, trading a lower price against the risk that the item sells out and against the decline of their own valuation over the season. How…

5 thms2 active usersReviewed
Operations ResearchProbability·Captain: mikedeng1

Subjectivity and Correlation in Randomized Strategies II: Subjective Events Let Both Zero-Sum Players Beat the ValueResearch Paper

In a two-person zero-sum game with objective randomization, whatever one player gains the other loses: the value vvv of the game is the most player 1 can guarantee and the least player 2 can hold him to, and no arrangement between the players can give player 1 more than vvv and player 2 more than −v-v−v at the same time. Aumann's 1974 paper (doi:10.1016/0304-4068(74…

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

School Choice: A Mechanism Design Approach 2: The Top Trading Cycles Mechanism with Type-Specific Quotas Is Strategy-ProofResearch Paper

Many US school districts assign children to public schools centrally. Each family ranks the schools. Each school ranks the children by priority, which is set by state or local law (siblings, walking distance, a lottery). A procedure then turns these rankings into an assignment. Abdulkadiroğlu and Sönmez (Columbia Economics Discussion Paper 0203-18, 2003;…

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

School Choice: A Mechanism Design Approach 1: The Top Trading Cycles Mechanism Is Strategy-ProofResearch Paper

Public school districts in many US cities let families rank schools and then assign seats by a centralized procedure. Each school has a limited number of seats, and state or local law gives some students priority at some schools, for example for a sibling already enrolled or for living within walking distance. Abdulkadiroğlu and Sönmez (Columbia Economics…

9 thms2 active usersReviewed
🏆Completed
Complexity TheoryOperations Research·Captain: mikedeng1

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities II: An Exact 3-Cover Exists iff the Constructed Market Has an EquilibriumResearch Paper

Market equilibrium is the central solution concept of general equilibrium theory: prices at which every agent buys a utility-maximizing bundle and supply meets demand. Arrow and Debreu (1954) proved that equilibria exist under mild conditions on endowments and utilities, and a line of work in algorithmic game theory asks how hard it is to compute them. For l…

12 thms2 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities I: Fisher Markets with an Equilibrium Have Rational Equilibrium Prices of Polynomial Bit SizeResearch Paper

A Fisher market is the simplest model of a market in which prices are set by supply and demand: buyers bring money, sellers bring goods, and a price vector is an equilibrium when every buyer, spending her money optimally at those prices, leaves every good exactly sold out. Computing equilibria is one of the central questions of algorithmic game theory,…

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

Incentives in Teams: The Own Profit Incentive Structure Is an Optimal Incentive Structure for a ConglomerateResearch Paper

An organization whose members hold private information faces two problems at once. The first is the team problem of Marschak and Radner: choose the rules by which members observe, communicate and decide so as to maximize the expected payoff of the organization as a whole (Marschak–Radner 1972). The second is the incentive problem: a member who is paid by…

7 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

The Theory and Practice of Revenue Management V: CompetitionTextbook

Revenue management is practised by firms that compete: airlines matching fares while allocating seats, retailers ordering stock and then pricing to clear it, hotels protecting rooms for late high-paying guests. Chapter 8 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) surveys the economics behind these situations: monopoly…

8 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Fundamentals of Supply Chain Theory VIII: Supply Chain ContractsTextbook

A retailer facing uncertain single-period demand and buying from a supplier at a wholesale price orders less than the two of them together would want. The reason is not irrationality but incentives: the retailer bears the whole cost of unsold stock while the supplier collects a margin on every unit ordered, so each party marks up its own cost and the…

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

Supermodularity and Complementarity VI: The Core of a Convex GameTextbook

A cooperative game with side payments models a set of economic agents who can form coalitions and split the proceeds. The central question is stability: is there a way to split the total payoff among all the players so that no subset of them would do better by breaking away and acting on its own? The set of such stable splits is the core, introduced by…

11 thms2 active usersReviewed
PreviousPage 31 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