Game Theory Papers

ALT We study the allocation of indivisible items to buyers with additive values drawn from independent distributions. The objective is consumer surplus net of burnt payments. We consider artificial-currency mechanisms: buyers receive personalized budgets of a currency worthless outside the mechanism and use them to bid across items. The better of separate selling and artificial-currency mechanisms provides a 3-approximation to optimal consumer surplus. The guarantee holds at every Bayes–Nash equilibrium, without equilibrium selection. Both branches are necessary: either alone may capture only a vanishing share of the optimum. The proof decomposes benchmark surplus into a stable part captured by artificial currency and a variation covered by separate selling.

ALT We prove that at least half of the first-best gains from trade can always be achieved in multidimensional two-sided markets with additive values and costs and arbitrary downward-closed feasibility constraints. The guarantee is achieved by a mechanism satisfying Bayesian incentive compatibility, interim individual rationality, and strong budget balance, and is tight already in single-item bilateral trade. Types are independent across agents, while the coordinates of each agent's type may be arbitrarily correlated. Feasibility constraints may couple trades across items and agents. This extends the known tight one-half guarantee for single-item bilateral trade. Our proof develops a new application of the Cai–Devanur–Weinberg duality framework. We show that the objective of every feasible dual is at least half of the first best. Strong duality then yields the guarantee without characterizing an optimal mechanism or dual. The key observation is that every feasible dual induces continuous-ti

ALT Adversarial risk analysis (ARA) informs decision-makers when facing intelligent opponents and uncertain outcomes, enabling an analyst to model beliefs about the opponents' preferences, capabilities, beliefs, and the strategic calculations that opponents employ. Major applications cover reliability and risk analysis of critical infrastructures in presence of adversarial threats. In such domains, ARA mitigates typical common knowledge assumptions of standard game-theoretic approaches. However, ARA entails complex modelling and computations. To alleviate these, we explore its combination with fully probabilistic design (FPD), a control theory methodology supporting an agent in choosing the decision distribution that achieves the outcomes with a distribution closest to its ideal. We use FPD to model and forecast the opponent's decisions within an ARA setting and present how to handle security games within this ARA-FPD framework, covering both single and multiple stage problems.

ALT Many alignment methods, most notably reinforcement learning from human feedback (RLHF), train reward models by minimizing a loss on pairwise comparisons of model responses. Inspired by principle-guided methods such as Constitutional AI, we treat each principle as a voter that compares responses according to that principle, for example, preferring the more helpful or less toxic response. We represent these voters as linear directions in a fixed embedding space, a simplifying assumption motivated by the Linear Representation Hypothesis. In this linear social choice model, Ge et al. (2024) showed that an optimal linear reward model can violate Pareto optimality (PO): From the principles-as-voters lens, this means a response A can be less helpful and more toxic than B, yet still receive a higher reward. We ask whether richer reward models or changes to comparison data can recover PO within loss-based training. We show that PO can still fail for polynomials of any fixed degree and one-hidde

ALT We study the fair allocation of indivisible items to agents with budget constraints and additive valuations. Each agent compares its own bundle with the subsets of another bundle that fit its budget. An allocation is envy-free up to one item (EF1) if, for every agent and every nonempty subset under comparison, removing an item of maximum value to that agent eliminates its envy. We require EF1 both between agents and towards the charity, which contains all unallocated items. EF1 allocations exist, but computing them in polynomial time has remained open even for homogeneous valuations. We resolve this problem with a polynomial-time algorithm for EF1 allocations under heterogeneous valuations. We also prove that detecting an EF1 violation is NP-complete. Equivalently, checking whether a given allocation is EF1 is coNP-complete. Finally, we give polynomial-time algorithms for envy-freeness up to any item (EFX) both when each agent's valuation is proportional to item size and when each agen

ALT Human agents in non cooperative games often exhibit non rational behaviour. Prospect theory provides a behavioural framework to capture how agents perceive gains and losses under risk, but, its incorporation into games typically leads to non concave and non convex utility functions, making equilibrium computation challenging. In such cases, it is difficult to obtain algorithms that have global convergence behaviour. This paper proposes a learning algorithm which uses minorization-maximization (MM). Under a proximal Polyak-Lojasiewicz (PL) condition on the potential function, we establish global convergence of the algorithm to a potential-maximizing Nash equilibrium. We further show how the structure of the MM minorizer can be used to enable a distributed implementation of the algorithm. With additional noise injection, the individual updates of the agents can be obscured, while still ensuring global convergence.

ALT We identify a homological barrier to stable learning of local Nash equilibria, also known as first-order Nash equilibria (FONE), in constrained non-concave differentiable games. We consider continuous deterministic learning dynamics that fix every FONE point and aim to attract all initial conditions to the full FONE set. We show that this convergence guarantee is impossible when the target set has nontrivial positive-degree cohomology, such as that arising from a loop, and the state space is compact and contractible. We exhibit this barrier in a simple non-concave quadratic zero-sum game on a box whose exact FONE set consists of a diagonal six-edge loop and an isolated point. Consequently, no such dynamics can make the full FONE set a stable global attractor. We further show that degree two is the minimal polynomial degree at which this barrier can arise and extend the construction to obtain nontrivial homology in arbitrarily high degrees. Finally, we establish that the barrier persist

ALT We study the complexity of computing competitive equilibria in Fisher markets with divisible chores and positive rational disutility coefficients and earning requirements. For linear disutilities, we prove that exact equilibrium computation is CLS-complete. In particular, the problem remains CLS-hard even when the earning requirements are binary in 1 and 2ᵏ, where k is an integer. We prove hardness by encoding the first-order conditions of a box-constrained quadratic program in equilibrium prices and earning flows, using a compact minimum-cost flow construction. For convex constant-elasticity-of-substitution (CES) disutilities, exact equilibrium prices may be irrational. We formulate the problem of finite-precision equilibrium price computation, in which we seek rational prices with a certified market clearing error at most a given rational tolerance encoded in binary. We prove that this problem is CLS-complete for every fixed rational exponent ρ>1. To prove this hardness, we encode a

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