Game Theory Papers

ALT We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using 2³ⁿˡᵒᵍ₂ⁿ⁺ᴼ⁽ⁿ) queries and cuts. For both cake and chores, a Las Vegas protocol uses O(n²¹log²(2n)) expected queries and O(n²⁰log²(2n)) expected cuts. Conversely, every exact protocol with fixed positive success probability requires Ω(n²) expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

ALT We study welfare maximization under envy-free contracts, where a principal assigns tasks and offers success-contingent payments to heterogeneous agents with hidden effort. For unit-demand agents, we establish a sharp complexity boundary: the problem is polynomial-time solvable when each agent is interested in at most two tasks, but NP-hard with at most three interests. Our algorithm analyzes tree-structured dependencies among forced assignments and reduces optimization to maximum-weight independent set in a perfect graph. When agents may receive multiple tasks, no polynomial-time constant-factor approximation exists unless P=NP. Finally, with homogeneous success probabilities and rewards, we establish a welfare- and revenue-preserving equivalence between unit-demand contract design and envy-free pricing. This yields polynomial-time welfare maximization without restricting interests, while revenue maximization remains NP-hard.

ALT Autonomous research systems can produce convincing manuscripts whose scientific value is difficult to verify, while automated reviewers can reward the appearance of completeness. We examine how this gap can become a self-reinforcing threat to the research community. In a two-population evolutionary game, authors choose between acceptance-oriented and exploratory research, and reviewers choose between proxy evaluation and careful assessment. Cheaper acceptance-oriented production can increase review pressure, making proxy assessment more attractive; proxy assessment can in turn strengthen the incentive to produce reviewer-compatible work. We derive conditions under which this feedback sustains a stable regime that rewards publication success while reducing the scientific value of accepted work. An analytical basin boundary explains why the same institutional rules can support either this regime or exploratory research with careful review. Numerical illustrations show how publication cou

ALT We study first-order learning dynamics in Bayesian signaling games, a minimal extensive-form model of strategic interaction under asymmetric information. In these games, a Sender observes a private type and chooses a signal, after which a Receiver forms a posterior belief and selects an action. This Bayesian belief update makes the induced learning field fundamentally different from the affine game-gradient fields of normal-form games. Empirically, we find a sharp dichotomy: standard online learning algorithms reliably converge to strict Perfect Bayesian Equilibria (PE), but not to non-strict ones. We show that this behavior cannot be explained by the global geometric conditions commonly used to prove last-iterate convergence, such as monotonicity or the Minty variational inequality. Indeed, these conditions can fail even in binary signaling games. Instead, we identify the relevant local geometry. Our main result characterizes variational stability in finite signaling games: a PE is va

ALT Carbon farming offers a promising path to improve farmer livelihoods, mitigate climate change, and make farming sustainable. However, smallholder farmers, who dominate agriculture in developing economies, face structural barriers to participating in carbon farming due to high certification costs, limited landholdings, and limited budgets available to them. In this paper, we develop a cooperative game-theoretic framework to study how coalition formation can enable viable and profitable participation of smallholder farmers in carbon farming. Our approach explores three components: (i) Solo Portfolio Optimization (SPO), which determines an optimal portfolio of carbon farming practices that individual farmers can adopt under budget constraints; (ii) Joint Portfolio Optimization (JPO), which computes the maximum total economic surplus achievable through the formation of farmer coalitions; and (iii) surplus allocation among participating farmers in a principled way using cooperative game-the

ALT We study the dynamic pricing problem, where a firm sells a product to T myopic customers and their values are independent samples from an unknown value distribution F. With posted prices, the firm only sees whether each customer buys, and the minimax regret is widetilde Θ(T²/3) [KL03]. A menu instead offers several options, each selling the product with some probability at some expected payment. Infinitely many menu options allow the seller to fully reveal customer values, reducing the regret to Θ(√ T). How many options are needed? Perhaps surprisingly, a second menu option suffices, achieving the same regret as infinite menus (up to log factors). This holds broadly: without knowing any property of F, our algorithm with two menu options attains tilde O(√ T) regret in general, tilde O(T¹/3) regret for monotone-hazard-rate distributions, and tilde O(T^d/(d+1)) instance-dependent regret when d∈(0,1) is a suitable notion of "dimension". All are optimal even with infinite menus. Moreover, w

ALT This paper performs a robust analysis of welfare (i.e., the price of anarchy) in multi-unit first-price auctions with independent private values and unit-demand bidders. We employ a smoothness framework (see) to analyze the price of anarchy when supply is large. The main barrier to analysis in this framework is a worst-case bid distribution that establishes a lower bound on the price of anarchy of 1- ¹⁄ₑ. We show that such worst-case distributions cannot arise in equilibrium when agents' values satisfy a mild density lower bound condition. This characterization leads to novel asymptotic lower bounds. In particular, the price of anarchy for ε-approximate equilibrium as the number of units goes to infinity is at least 1-Θ(εlog ((1/ε))). Our analysis relies on a key structural property of equilibrium bid distributions: for a welfare analysis in any multi-unit first-price auction, it is without loss to analyze (approximate) equilibria with no atoms. In addition to this, we establish contin

ALT We study elections with ranked ballots and general feasibility constraints, which indicate which sets of candidates are allowed as outcomes. We introduce the first proportionality axiom for this general setting and show that it extends the established notions from specific models that fit our general framework. We extend the Solid Coalition Refinement (SCR) rule to general constraints and prove that it satisfies our axiom exactly for matroid constraints. Although the naive implementation of SCR involves a step that is computationally intractable for weak orders, we show that in practical cases it can be implemented in polynomial time or efficiently in FPT time. We also illustrate limitations of this rule for approval ballots and provide its first empirical evaluation.

ALT Leaderboards are a popular way to compare large language model (LLM) capabilities and can influence how model developers invest resources. We ask when competition on leaderboards leads developers to produce models with similar capability profiles, which we call monoculture, or similar performance levels. We study this by formulating leaderboard competition as a game in which model developers invest resources across capabilities to maximize their win rate. We show that similar production functions can induce similar capability profiles, while comparative advantage can sustain distinct capability profiles. We then study convergence in performance levels and show that diminishing returns can lead to an increasingly crowded competitive frontier. Using data from LM Arena and OpenRouter, we find that developers improve more in categories where they lag competitors, while still retaining category-specific advantages. At the same time, we find that the frontier of models becomes increasingly c

ALT We present a unified potential method for contextual search and bilateral trade with one-bit feedback and obtain order-tight algorithms for both problems. Our framework starts from a Bayesian perspective in which the unknown target (for contextual search) and the unknown pair of valuations (for bilateral trade) are sampled from a known prior distribution. In that model, the decision maker bases its prediction on the posterior distribution, obtained by conditioning on feedback received in previous rounds. For Bayesian contextual search, we present an algorithm with a total loss bounded by O(Tr √ Σ), where Σ is the covariance matrix of the target's prior; and for contextual bilateral trade, our algorithm's regret is bounded by O(Tr √Σ_S+Tr √Σ_B), where Σ_S and Σ_B are the covariance matrices of the seller's and buyer's valuations. We then use ideas from this Bayesian setting and adapt a “dual” of this trace-square-root potential to the classical worst-case setting, where the target and v

ALT Learning to profit from trade requires learning both sides of a market: what a seller is willing to accept and what a buyer is willing to pay. We study repeated bilateral trade, where an intermediary posts a purchase price to a seller and a sale price to a buyer whose valuations are drawn from an unknown joint distribution. Trade occurs only if both parties accept their respective prices, in which case the intermediary earns the difference between the two prices. The intermediary observes only whether trade occurs, without observing either valuation. We show that learning both sides of the market is no harder, in terms of regret, than learning just one. Specifically, we design an algorithm achieving regret Õ(T²/³) against the best fixed pair of prices, matching, up to logarithmic factors, the classical lower bound for one-dimensional dynamic pricing. Our result shows that the classical one-dimensional regret rate survives the transition to two dimensions, raising the question of wheth

ALT A game may have, for each target below its value, a finite controller meeting that target, yet no finite controller attaining the value itself. We study finite stochastic games with a hard specification that must hold on every supported execution, including paths of probability zero. Max uses a pure finite controller; Min may use any pure public-history strategy. We distinguish three numerical questions: can a supplied target be met, can the unspecified optimum be attained, and what is one exact value? For explicit hard and Boolean soft Streett conditions, the strict and non-strict supplied-threshold problems are coNP-complete, attainment of the unsupplied supremum is mathrm Pᴺᴾ-complete, and one exact reduced fraction is FPᴺᴾ-complete under polynomial metric reductions. The proofs preserve both the value and its finite attainability when fixing a single opponent, and encode adaptive queries without computing unknown subgame values. The same construction yields matching value-compariso

ALT Generalized Nash equilibrium (GNE) problems model self-interested agents coupled through their costs and shared constraints, and arise throughout control applications that allocate a scarce common resource. Such problems typically admit a continuum of equilibria, so any implementation must select one. This selection is not neutral: it decides how the cost of the shared constraint is distributed among the agents, a decision often expected to be fair. The variational GNE (v-GNE), which charges all agents a uniform shadow price, is the conventional choice and is frequently advocated as fair. Through the lens of comparability from social choice theory, we show that the GNE set itself requires no inter-agent comparability of costs, whereas the v-GNE implicitly assumes cardinal unit comparability, one of the stronger notions. We then introduce the fair GNE (f-GNE), which selects an equilibrium by explicitly optimizing a fairness metric matched to the comparability at hand, and give construct

ALT Ordinal information is central to tasks ranging from conference peer review to Reinforcement Learning from Human Feedback for large language models. In many such settings, there is no objective ground truth against which reports can be directly verified, making incentive-compatible elicitation challenging. Peer-prediction mechanisms have been designed to achieve truthful elicitation despite the lack of ground-truth verification. However, existing peer-prediction methods do not provide incentives for agents to truthfully compress rich private information (e.g. reviews) into coarser ordinal reports (e.g. rankings) requested by the mechanisms. We propose a simple ordinal peer-prediction mechanism that rewards agents based on pairwise agreement, measured by Kendall tau. Under a broad class of Bayesian Stochastically Order Consistent models—which includes classical models such as Mallows and Thurstone—we prove that truthful reporting is stochastically dominant, and strongly truthful under i

ALT Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a Õ(T⅔) regret rate, which is nearly tight even if the valuations are

ALT This paper formulates a generic distributed nonsmooth optimization problem subject to edge-based equality constraints, local inequality constraints characterized by general convex functions, as well as globally coupling constraints including affine equality and nonlinear inequality. The terminal goal is to minimize the sum of local non-differentiable convex functions and proximable nonsmooth convex composite terms attached to linear operators, over networked multi-agent systems. This formulated framework not only applies in complex practical problems but also reduces to existing distributed optimization structures. To cope with technical issues caused by local linear mappings, potential multiple nonsmooth functions and coupling nonlinear constraints, we first derive a new local first-order condition, and further present a novel fully distributed optimization algorithm based on variable decompositions and proximal operators. Specifically, the proposed algorithm allows each agent to upda

ALT In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of Õ(ε⁻²) that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learn

ALT Convex cooperative games have a nonempty core and admit an efficient construction of core allocations. However, economically natural local frictions may violate convexity. We study the core of 3-distant convex games, which permit violations of convexity only between closely related coalitions. Although the core of such a game may be empty, we establish a simple necessary and sufficient condition for its nonemptiness. We also develop a strongly polynomial-time combinatorial algorithm for finding a core allocation whenever one exists. Finally, we demonstrate the applicability of the framework to oligopolistic competition with merger synergies and profit allocation of joint production with complementary inputs.

ALT In contract design, the principal is often better informed about the project's chances of succeeding than the agents. To incentivize effort, the principal has two main tools: first, to design a contract, sharing part of the project's success among the agents; second, to design a (Bayesian) persuasion scheme, selectively sharing information with the agents. In this work we are interested in the optimal combination of both these tools. We tackle the joint problem through the prism of simplicity vs. optimality, and establish a stark dichotomy: The simple disclosure scheme of full transparency achieves a tight 4/3-approximation to the optimal combination of information disclosure and team contract, when the team's production function is submodular. In contrast, full transparency can be arbitrarily far from optimal when production is supermodular. The techniques that we develop to bound the gap for submodular functions, also yield a new deterministic polynomial-time approximation algorithm

ALT We study approximate EFX allocations of indivisible chores under nonnegative additive costs. Exact EFX allocations need not exist in general. We develop a polynomial-time algorithm that computes a complete (3+ε)-EFX allocation for any rational 0<ε≤1, improving the previous approximation guarantee from a factor depending on the number of agents to a constant. The algorithm extends to EFkX, achieving a (2+1/k+ε)-approximation for every integer k≥1. For instances with relatively few chores, the polynomial-time BRBI algorithm gives stronger guarantees. It finds exact EFkX allocations when m≤2kn and achieves a factor of at most 2-1/k when m≤(3k-1)n. In particular, k=1 and m≤2n give exact EFX. We further show that the approximation factor 2+1/k is asymptotically tight for our main algorithm. We also construct a four-agent, ten-chore instance in which every complete allocation has EFX approximation factor at least 11/10, improving upon the 20/19 lower bound for submodular costs even under add