Game Theory Papers

ALT We study experimental results of best response dynamics (BRD) in randomly generated weighted action networked multiagent optimization problems where agent utility is the agent's marginal contribution to the system objective. We compare those results to the Price of Anarchy (PoA) established in the literature for marginal contribution and to the expected value of randomly choosing from the available equilibria. PoA is used as a metric to describe the performance of various solutions to multiagent optimization problems, but the utility of this metric may be overrated if such worst-case instances are rare in practice. Our study provides evidence to support this doubt, showing that simple best response mechanics tend to out perform the PoA prediction and a uniform random equilibrium selection, even when agents are unable to observe all other agents' actions. In the process of seeking a more ideal metric, we discover that BRD appears to perform better than average. That is, when multiple eq

ALT We describe the agent we submitted to the GLEE Competition, which plays bargaining, negotiation, and persuasion games against a shared pool of human and AI opponents. The agent is built around three central components: a classical game-theoretic solver to compute numeric moves, an online Bayesian layer to estimate opponent archetypes, and a language model to write accompanying messages. We utilize Rubinstein bargaining for bargaining, Faratin concession for negotiation, and Kamenica–Gentzkow disclosure for persuasion, and adapt those models to live opponents using two separate layers: a Bayesian estimate of the opponent's hidden discount factor, reservation value, or signaling reliability, and a Thompson sampling bandit over five moral-foundation framings coupled with an evidence-intuition spectrum to establish message register. Most of the development effort went into the recurring problem that theoretically optimal policies perform poorly in certain live settings; we report associate

ALT Token systems support repeated service exchange without monetary transfers, but their viability depends on the stability of token balances. We study token systems with compatibility constraints among agents. A requester is randomly sampled in each period, and only a few randomly sampled agents are available to provide service. We establish a necessary and sufficient condition for stability and show that the minimum-token rule, which selects the available provider with the lowest token balance, achieves the optimal stability region. We then apply this stability criterion to a random token system generated from stochastic block models with uniformly sampled requesters. We tightly characterize the stability regime by identifying two obstructions to stability: insufficient service opportunities for a group of communities or for an individual agent.

ALT We consider T repeated second-price auctions across n pacing bidders with i.i.d. item arrivals, and show that it is computationally impossible for all bidders to achieve no-regret simultaneously while satisfying their respective budget or return-on-investment constraints. Therefore, in the prominent internet auction systems where buyers simultaneously deploy pacing algorithms or automated bidding agents, we cannot hope to achieve joint no-regret guarantees in general. We establish a deterministic relationship that high variance in online bidding systems implies high regret. By showing that one can extract a pacing equilibrium from a low-variance system, we prove PPAD-hardness of attaining joint no-regret. For several widely used bidding algorithms, we also show evidence from dynamical systems and numerical simulations that they can indeed display high-variance behavior through cycling, even on simple market instances.

ALT Miner extractable value (MEV) poses a persistent challenge for blockchain ecosystems. It arises from the fact that a block builder can exploit its unilateral control over transaction inclusion and ordering to extract profit, potentially at users' expense. Recent work has explored consensus-aided mechanism design to mitigate MEV. This approach combines generic consensus-layer guarantees with application-layer mechanisms that use these guarantees to address application-specific MEV problems. Prior work exemplifies this approach for automated market makers (AMMs). When the consensus layer offers fair sequencing, which orders transactions according to their arrival times, their proposed mechanism achieves incentive compatibility (IC) and weak local efficiency (wLE). Informally, IC rules out profitable strategic deviations by users and builders. Meanwhile, wLE ensures that after execution, any order willing to trade at the initial price cannot benefit from further trade with the pool at the

ALT The adaptive clinching auction of Dobzinski, Lavi, and Nisan (FOCS'08) is a cornerstone of mechanism design with budget-constrained bidders, and it has since inspired a broad range of extensions to substantially richer market settings. Adaptive clinching enjoys compelling guarantees: it is Pareto optimal, and truthful bidding is a dominant strategy whenever budgets cannot be overreported. In many real-world environments, however, identities are cheap to create, making resilience to Sybil attacks an additional requirement. Whether the guarantees of adaptive clinching survive when a bidder can split its budget across fake identities has remained open. We introduce a generalized framework for adaptive clinching and prove that it satisfies Sybil-robust incentive compatibility: a bidder cannot benefit from splitting into any finite number of identities with arbitrary value reports, provided their aggregate reported budget does not exceed the bidder's enforceable true budget. Sybil resilienc

ALT Recent work has shown that, in zero-sum games, an optimizer can extract Ω(√T) strategic surplus—cumulative payoff above the minimax benchmark—against noiseless no-regret learners with a constant step size. However, in practice, learners often act on perturbed payoff scores and use decaying learning rates ηₜ. Since existing extraction mechanisms rely on exact scores, a natural question is whether noise shields the learner from exploitation and eliminates surplus altogether. We address this question for the widely used class of Follow-the-Regularized-Leader (FTRL) algorithms. Under standard regularity conditions, we establish three results, none of which assumes independence of the noise. First, under summability conditions, passive play of a strategy fixed independently of the horizon earns at most constant surplus. Second, we design a new mechanism that exploits the learner's noise-dependent response: a clairvoyant optimizer who knows the update rule and the limiting mean response secu

ALT We study facility location in multidimensional normed spaces with the objective of minimizing social cost, the sum of agents' distances to their nearest facility. A deterministic mechanism selects k facility locations based on the reports of n agents and is strategyproof (SP) if no agent can reduce her distance by misreporting her location. We establish optimal approximation ratios and impossibility results. For a single facility in the Euclidean plane, we prove that the optimal approximation ratios among deterministic SP mechanisms are exactly those obtained by Goel and Hann-Caruthers [SCW 2023] for the coordinate-wise median (CM): √(2(n²+1))/n+1 for odd n≥3 and √2 for even n≥4. We remove the anonymity assumption from their optimality result. However, CM is not always optimal in non-Euclidean spaces: we give an SP mechanism that minimizes social cost exactly in ℓ∞ᵈ, whereas CM has a tight uniform approximation ratio of 2 already in the plane. We then consider two facilities in ℓₚ spac

ALT The inefficiency of decentralized resource allocation is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well-established. To mitigate the effects of selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibria. However, standard Coordination Mechanisms assume unknown, adversarial demand, restricting positive results mainly to specialized networks such as parallel links. We address this limitation by studying learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand. We study general atomic and non-atomic congestion games with polynomial latency functions of degree d. Our main positive result is a learning-augmented coordination mechanism t

ALT Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payof

ALT We study how learning algorithm design shapes equilibrium selection in infinite-horizon discounted Markov games with finite states and actions. Each episode, players choose smooth best responses to beliefs about opponents' policies, test them using noisy observations, and resample rejected beliefs or explore at rates determined by increasing transformations of their discounted values. We show that stochastically stable states induce approximate stationary Nash equilibria maximizing the minimum transformed discounted value across players, with transformations governing which players selection favors. In repeated games with bounded recall of noisy public signals, longer recall weakly increases the selected minimum transformed value. In repeated Cournot games, every stochastically stable state induces an approximate public perfect equilibrium whose minimum discounted profit across firms exceeds the Cournot-Nash benchmark. Collusion is therefore inevitable under these conditions and learni

ALT We study the computational complexity of clairvoyant strategy optimization against a known online learner in finite-horizon repeated games. In general-sum games with bounded payoffs, unless P=NP, no polynomial-time optimizer can achieve a reward within cT of the reward of the optimal pure-action sequence for an absolute constant c>0, even when allowed to output explicitly represented mixed strategies at every round. Our hardness result strengthens prior work along two complementary axes: it extends to a broader class of learning dynamics, including widely used mean-based algorithms, answering an open question of Assos, Dagan, and Rajaraman (2025) for learners beyond multiplicative weights; and it permits mixed outputs while retaining the weaker pure-sequence benchmark. Thus, neither mixed strategies nor algorithmic specificity removes the computational obstruction in general-sum games. In sharp contrast, zero-sum games exhibit the reverse phenomenon: deterministic pure actions suffice

ALT The Hylland-Zeckhauser (HZ) mechanism provides a market-based approach to one-sided matching, making efficient equilibrium computation central to its implementation. Bi-valued utilities admit a strongly polynomial-time algorithm [VY], whereas with four values per buyer, the problem is PPAD-hard under inverse polynomial approximation [CCPY]. To understand the tractability boundary, we study two extensions of the bi-valued case: a third linear utility value and separable concave utilities with two common marginal slopes. For every fixed rational a∈(0,1), we prove that computing a normalized additive εₐ/N-equilibrium in an N-buyer HZ market is PPAD-hard for some constant εₐ>0, even when all utilities belong to the same prescribed set {0,a,1}. This resolves the main question left open by [VY, CCPY]: whether three utility values already suffice for PPAD-hardness. Using the same market gadgets, we show that hardness at a specified constant accuracy on the recognizable family generated by our

ALT In token-priced language model services, users can see the prompts they submit and the answers they receive, but may also pay for internal reasoning and candidate answers that are not shown in the final response. This paper develops a three-party service model to study how charging for this intermediate computation shapes providers' decisions and social welfare. Users purchase answers from a model firm that pays an execution cloud, with either supplier controlling the computation budget. The model separates user billing from upstream payments and identifies when metered pricing encourages excessive generation, when fixed service prices restrict valuable computation, and how responsibility for execution costs changes these choices. A LiveCodeBench study measures answer quality, latency, token use, and resource consumption across five model deployments, with numerical billing comparisons for the three covered by archived tariffs. At equal average charges on the reference workload, the ca

ALT We study welfare maximization in a contract model with m principals who privately value a public project's success and n agents whose costly effort is unobservable. Contracts induce truthful dominant strategies for principals and equilibrium effort by agents, maximizing the expected total value of eligible principals. We develop three tools: a broker that separates payments from principals and payments to agents, an extension of Myerson's Lemma characterizing dominant-strategy incentive compatibility (DSIC), and a black-box reduction to budget-constrained single-principal contract design. When the success probability is a strictly monotone XOS function of agents' actions, these tools yield three results. First, a deterministic DSIC contract achieves a constant approximation against a benchmark that qualifies every principal and maximizes success probability using budget ∑ⱼ vʲ, but may violate budget balance (BB). Second, against benchmarks with budgets at least the largest principal va

ALT Follow the regularized leader (FTRL) is a foundational algorithm in online learning whose regret properties have been extensively studied for decades. However, in stark contrast to mirror descent—and gradient descent in particular—the convergence of FTRL to first-order stationary points in constrained nonconvex optimization was not well understood. In this paper, we show that continuous-time FTRL can fail to converge even asymptotically in infinitely smooth constrained optimization problems: its Karush-Kuhn-Tucker (KKT) gap can remain bounded away from zero indefinitely. This is especially surprising in light of the fact that continuous-time FTRL guarantees a monotonic improvement of the objective value. As a result, we establish that non-convergent behavior of no-regret dynamics—which besets general variational inequality problems—can occur even in potential systems. From a technical standpoint, our construction relies on an infinitely differentiable function where the gradient flow d

ALT We study fair division of uncertain items, where the utility of each item is a random variable whose realization is observed only after the allocation is determined. This uncertainty creates a distinction between ex-ante fairness, evaluated before utilities are realized, and ex-post fairness, evaluated after realization. We examine to what extent these two notions are compatible. We first identify conditions under which ex-ante envy-free allocations maximize ex-post envy-freeness probability. These include two-agent instances where utilities toward the same item follow the same distribution from a convolution-power family. For an arbitrary number of agents, we establish analogous optimality results when the common generator is non-atomic or log-concave. Beyond convolution-power families, we derive approximation guarantees for ex-ante envy-free allocations relative to the optimal ex-post envy-freeness probability under log-concave or symmetric utilities. We also study the computational

ALT We study online fair division of indivisible goods among n agents with frequency predictions: before any good arrives, the algorithm learns the multiset of each agent's values for the goods, but neither the arrival order nor which values of different agents belong to the same good. Neoh et al. (ICML 2026) showed that such predictions allow every share-based guarantee that is achievable offline, and left open whether a positive approximation of envy-freeness up to one good (EF1) is possible. We show that deterministic online algorithms can guarantee 1/2-EF1 for three agents and (3-√5)/2-EF1 for four agents, whereas for five or more agents, no online algorithm can guarantee any positive approximation of EF1, even with n+1 goods and identical predictions. Together with the known result for two agents, a positive approximation of EF1 is therefore possible if and only if n≤4. We also rule out any positive approximation of EFX for three or more agents, even when the valuations take only two

ALT Benade et al. (EC 2024) introduced a semi-random model for non-additive fair division in which each agent starts with an arbitrary base valuation over bundles of items and independently permutes the item names uniformly at random. While they proved that envy-free allocations exist with high probability as the number of items grows for n = 2 agents, they left open whether the same holds for n > 2 agents. We resolve this open question in the affirmative: for any fixed number of agents n and any number of items m divisible by n, an envy-free allocation exists with probability 1 - o(1) as m → ∞. Our proof combines the second moment method with a connection to the (small-set) expansion of generalized Johnson graphs, which may be of independent interest.

ALT As AI agents reshape Web search and advertising, platforms can monetize information that improves decisions. We study information pricing for sequential search among independent alternatives with nonobligatory inspection: the buyer may select any alternative without buying its report. We show that a common fee maximizes static revenue for identical priors, resolving a uniform-pricing conjecture. Our results also establish that exact optimization is NP-hard for heterogeneous binary priors. Despite this hardness, our polynomial-time static pricing algorithm achieves a 3-approximation to the information surplus. More generally, a common static fee approximates optimal adaptive revenue within a logarithmic factor in the number of alternatives. This guarantee is asymptotically tight.