ALT Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems. Despite their importance, the complexity of finding approximate solutions has remained unresolved for a wide range of approximation parameters. We settle this question by establishing a tight threshold at ε=1/6. Specifically, we prove that ε-GCircuit is PPAD-complete for every constant 0<ε<1/6, even when restricted to four gate types, and polynomial-time solvable for every constant ε≥1/6. This closes the gap between the previously known hardness bound of 1/10 and the polynomial-time solvability bound of 1/2. We further investigate the relaxation in which a fraction δ of the gates may be violated. We establish polynomial-time solvability of (ε,δ)-GCircuit for every constant ε>0 and δ>1/5, and of the fan-out-one formulations of δ-Pure-Circuit for every constant δ>1/8. These results follow from a decomposition theorem for directed graphs of maximum in-degree two a

ALT The goal of this paper is to distill insight around the trade-offs present on Bayesian equilibria of transaction fee mechanism (TFM) design under n multiple concurrent proposers (MCP). We conceptualize a technical toolkit that unlocks the analysis of hard-to-characterize equilibria of finite Bayesian MCP TFM games by examining sequences of joint user–proposer mixed equilibria as the number of users increases and keeping the relative congestion ρ that they cause fixed in the sequence limit. We first consider the popular mechanisms of "pay-once" (which charges transactions its bid only once regardless of the duplicate copies that end up being included by proposers) and "pay-per-inclusion" (PPI in short, which charges a transaction for each copy that appears). We prove that PPI is efficient in the limit of equilibria sequences, and incentivizes users to route to only one proposer. We characterize m users' asymptotic behavior in PPI even in finite markets varying with O(√m), where we show

ALT The metric distortion framework asks voting rules to elect a candidate close to the voters using only their rankings. SimultaneousPluralityVeto elects from the plurality veto core and achieves the optimal worst-case distortion of 3, but it is not Pareto-efficient: it can declare a tie between two candidates even when every voter prefers one of them. Removing Pareto-dominated candidates afterward would break the convexity of tied winner sets. We instead introduce regularization, which adds a small ε to every candidate's weight, restoring Pareto-efficiency. To study its effect on distortion, we introduce the rank score veto core, whose candidate weights come from a positional scoring vector s, and prove that its distortion lies in [1 + 2(||s||- sₘ), 1 + 2||s||]; we conjecture that the lower bound is tight. A fixed ε can increase distortion, but letting ε depend on the number of voters preserves the distortion guarantee of the original veto core. Regularized SimultaneousPluralityVeto thus

ALT For every fixed ε∈(0,1) and η∈[0,1), we prove that computing an (ε,η)-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH, even in symmetric binary-payoff games with a constant number of players. The games are given by complete payoff tables, and the player count depends only on the tolerances. The weak approximate Nash equilibrium allows at most an η fraction of players to gain more than ε by deviating unilaterally. The main technical result is an unconditional error-amplification reduction from bimatrix games. For every fixed δ∈(0,1), it transforms a rational bimatrix game with payoffs in [0,1] into a symmetric binary-payoff game with a polynomial-size complete table and a player count depending only on δ,ε,η. Every (ε,η)-weak approximate equilibrium of the constructed game yields a δ-approximate Nash equilibrium of the bimatrix game. Construction and recovery take polynomial time in their explicit inputs. Combining this reduction with the

ALT We give the first unconditional family of polynomial-time algorithms that breaks the 1/3 approximation barrier for symmetric bimatrix games. For every fixed δ>0, an algorithm in this family computes a symmetric (1-1/√2+δ)-approximate Nash equilibrium, improving on the previous best guarantee of (1/3+δ) due to Kontogiannis and Spirakis [2011].

ALT Web platforms organize collective work, including content review and community maintenance, that imposes heterogeneous effort costs on participants. Fairly distributing these burdens while leaving as few tasks unassigned as possible is a natural objective for the design of such platforms. We study this through the maximin share (MMS) allocation problem with chore disposals under nonnegative additive costs. Our goal is to minimize the number of unassigned chores while guaranteeing every agent her MMS benchmark from the original instance. We prove that, for every instance with n ≥ 4 agents, at most n-3 chore disposals suffice. We improve the bound of 2m/11+n disposals established by Barman et al. (2025), where m is the number of chores, and eliminate the dependence on m. For four agents, we obtain a tight bound: one disposal always suffices, whereas known instances admit no complete MMS allocation (Ezra and Garbuz, 2026). We also prove the same result for goods: n-3 duplications suffice

ALT Mean-Payoff Games (MPGs) form an interesting family of deterministic, infinite-duration, zero-sum, turn-based games played by two players on a finite weighted directed graph. The goal of the players is to minimize, respectively maximize, the limiting average of the costs of the edges on an infinite path constructed by the two players. The complexity of solving MPGs is a long-standing open question. The decision problem associated with these games is known to be in NP\cap co-NP, and even UP\cap co-UP, yet the problem is not known to be in P. This is one of the simplest combinatorial problems with such a status. A full solution of an MPG gives the value of each vertex of the game, along with a pair of optimal strategies for the two players. (Each player has a succinct positional optimal strategy.) The problem of finding optimal strategies for the players given the values of all vertices is known as the strategy recovery problem. We describe a simple reduction from the problem of solving

ALT How can a shared resource be allocated without money when agents have private, stochastic demands that can be queued for a while, and may behave strategically, or even adversarially? We introduce a paradigm for non-monetary online resource allocation called Sampled Pairwise Externality Compensator (SPEC). Our objective is to guarantee each agent a large fraction of its ideal utility: an individual benchmark corresponding to serving the highest-valued fraction of its demand permitted by an equal share of capacity. We seek guarantees that hold regardless of other agents' behavior, including potentially adversarial and collusive behavior. Our approach builds on the idea of pairwise externality compensation, making it computationally efficient by replacing exact calculations of future externalities with sampled estimates. The central insight is that local mixing, exploited through coupled simulations, allows these estimates to be computed efficiently while preserving robust utility guarant

ALT We study simple auctions for one additive buyer whose values for m items are independent. Write REV for optimal revenue, SREV and BREV for the revenues from separate selling and grand bundling, and BSPA₂ for grand-bundle second-price revenue with two independent bidders. For independent regular items, we prove REV≤BSPA₂≤2BREV. This establishes tight approximation and competition guarantees for bundling under regularity and answers an open question from Beyhaghi et al. (EC 2025). For general independent items, we prove REV ≤ SREV + π²⁄₆BREV ≤ 2.645 max{SREV, BREV}. This improves the previous approximation factors of 6 from Babaioff, Immorlica, Lucier, and Weinberg (FOCS 2014, JACM 2020) and 5.2 from Ma and Simchi-Levi (AISTATS 2021). On the lower bound side, we construct an instance in which prices for three disjoint bundles earn more than 2.11max{SREV,BREV}, improving the previous lower bound of 2 from Rubinstein (ITCS 2016). We also show that exact recovery of one buyer's optimal reve

ALT General-sum games are more challenging than fully cooperative or adversarial settings because agents may deceive or exploit one another. Achieving high social welfare requires sustained cooperation, while a single defection can drive agents toward a welfare suboptimal Nash equilibrium. Moreover, assuming access to other agents' rewards or internal states is often unrealistic and implicitly introduces additional cooperation into the setting. To address this issue, we introduce Reciprocal Q-Augmentation (RQA), a method that uses a latent-variable opponent model to augment the Q-function with estimates of how one's actions affects other agents. RQA allows agents to learn both cooperative and defective policies using only their own Q-function. We show that, in social dilemmas, agents that all follow the cooperative policy of RQA learn to cooperate faster and reach higher levels of cooperation than fully cooperative algorithms. Moreover, a single RQA agent that switches appropriately betwee

ALT Blockchain participation games model costly entry, random selection, and threshold success; their retraction variants charge completion costs only to selected contributors. We study committee tasks requiring operators to reserve computing or communication capacity before assignment, so preparation costs are incurred even when capacity remains unused. Users choose abstention, bare registration without preparation, or binding commitment to contribute if selected. Success requires sufficiently many selected contributors, creates public value, and may trigger separate rewards for registration and verified contribution. We characterize all pure Nash equilibria under homogeneous selection and analyze ordering under heterogeneous selection. The results distinguish free-riding on public value from registration that earns rewards without productive commitment; more frequently selected users can choose bare registration while less frequently selected users contribute. Our main result characteriz

ALT We consider the metric distortion framework for voting, where n voters and m candidates are embedded in an unknown metric space. A voting rule selects a candidate using only voters' ordinal preferences, and its distortion is the worst-case ratio between the social cost of the selected candidate and the minimum social cost. We study how round complexity trades off against total communication in deterministic voting protocols with low distortion. Deterministic rules can achieve the optimal distortion of 3 in one round by eliciting complete rankings using Θ(nmlog m) bits, while a direct sequential implementation of PluralityVeto achieves the same distortion using only O(nlog m) bits but requires Θ(n) rounds. Our main result is TreePluralityVeto, a deterministic voting protocol that, for every r≥ 2, achieves distortion at most 2r-1 using at most r rounds and O(nlog m+n s¹/⁽ʳ⁻¹)log s) bits of total communication, where s = min{n, m}. The protocol runs PluralityVeto on a hierarchical partiti

ALT We aim to design revenue-maximizing single-item auctions that are deterministic, strategy-proof, and ex post individually rational — the quintessential fundamental model for optimal mechanism design. While Myerson's seminal work solved this model for independent bidders, straightforward extensions to correlated settings often result in non-monotonic, and therefore non-strategy-proof allocations. Critically, optimal allocation design for correlated bidders is NP-hard to approximate, rendering theoretical optimality guarantees in this domain computationally intractable. We establish a new standard of empirical rigor for this theoretically hard model by proposing an empirical pipeline. We synthesize neural interpolation of Myerson's greedy allocation based on marginal profits (the correlated variant of virtual valuation), formal neural verification to enforce exact strategy-proofness, and a constructive repair procedure. Empirically, our method is highly effective, consistently achieves n

ALT The United States allocates representatives to each state in proportion to its population, while many parliamentary democracies select representatives from party lists in proportion to the number of votes each party receives. In both settings, the legislature's small size necessitates rounding to the nearest whole number of seats. Recent work has shown a plethora of ways to randomly round seat shares to achieve perfect ex ante fairness. As a result, party (state) i may have a larger number of votes (population) than party j but receive fewer seats. In this case, we say that party i envies party j. We investigate the extent to which such envy is avoidable. Specifically, we seek to design apportionment rules that minimize the expected number of envious pairs (i, j). If the expectation is zero, we say that the seat allocation is envy-free. On the negative side, we show that any n-party apportionment rule that ignores lower quotas (the floors of the deserved number of seats for each party)

ALT How does post-training change cooperation during repeated interaction? Within each of seven released model lineages, we compare pretrained (Base), supervised fine-tuned (SFT), and subsequent preference- or reward-optimized (Aligned) checkpoints across seven social dilemmas. Copies of each checkpoint play one another for 200 rounds, with visible history limited to the last two or forty rounds. The memory curse refers to lower cooperation when agents can see more past rounds. Our central finding is that post-training amplifies this decline. Averaged across the six binary-action games, expanding visible history reduces cooperation at every SFT and Aligned checkpoint. At each post-trained stage, these declines exceed Base's in six of seven lineages. Most of this average amplification is already present at SFT. With long history, both post-trained stages also cooperate less than Base on average in each binary-action game. In the symmetric binary games, their fitted cooperation rates fall mo

ALT We prove that for additive valuations, not every pure Nash equilibrium of the Round-Robin mechanism induces an allocation that is envy-free up to one good (EF1) with respect to the agents' true valuations. This corrects an earlier claim of Amanatidis et al. (WINE 2021; Math. Oper. Res. 2024). On the positive side, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an allocation that is 1/2-EF1 and proportional up to one good (PROP1). We prove the approximate EF1 guarantee through a potential function comparing two executions, and the proportionality guarantee via a deviation that preserves the agent's most valuable goods. We also give a family of Round Robin equilibria showing that it is not possible to have a strictly better guarantee than 2/3-EF1 for all equilibria.

ALT Automated market makers (AMMs) are central to decentralized exchanges, but their reserve curves make mechanism design different from classical double auctions. We study a batch double auction with buyers, sellers, and a liquidity-nondecreasing AMM: post-trade reserves must have weakly larger product than the initial reserves. Each user has two-dimensional private information: a unit value and a demand or supply quantity. User trades clear at one uniform price subject to AMM feasibility. The objective is user-side trading volume, benchmarked against the optimal feasible individually rational (IR) uniform-price allocation. We give a randomized uniform-price mechanism based on binary quantity buckets. It randomly chooses one of three clearing modes: peer-to-peer matching, AMM sales to buyers, and seller sales to the AMM. Every deterministic realization of the mechanism is ex-post feasible and satisfies IR and weak quantity incentive compatibility: conditional on any quantity report, truth

ALT We study the inverse problem of recovering unknown parameters governing the dynamics and rewards of Mean Field Games (MFGs) from partial observations of population trajectories, made stochastic by common noise. The observer seeks to recover a consistent parameter θ via Bayesian inference, facing the challenge that evaluating the likelihood requires solving a new Nash equilibrium (NE) for each candidate θ. Due to common noise, the mean-field evolution is stochastic and equilibrium policies are population dependent, which makes solving for each parameter computationally expensive. To overcome this, we introduce the Bayesian-Extended Mean Field Game (BE-MFG), whose single NE simultaneously encodes equilibrium policies for all parameters, enabling efficient learning of the conditional density of mean-field trajectories. We formalize parameter consistency and identifiability in MFGs with common noise and investigate conditions under which consistent parameter recovery is guaranteed. On thre

ALT Duverger's law states that plurality elections tend to concentrate support on two candidates. Pivotal-voter models typically derive this from aggregate uncertainty about votes, so that two-candidate competition emerges in the limit of large electorates. We instead propose a model for a fixed, finite population. A poll reveals the current support counts, and each voter best responds under trembling-hand beliefs, assuming that every other voter may deviate with a small probability. Starting from truthful votes, we show that a single update typically suffices for the dynamics to converge to a stable profile in which every voter supports her preferred candidate among the two poll leaders. For any number of candidates and any full-support tremble belief, a four-vote lead of the runner-up over all lower candidates suffices; for three candidates, a lead of two suffices. As a consequence, under random preferences, Duverger's law emerges after one update with probability 1-O(N⁻¹/²). While these

ALT Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compressed into a smaller collection of rankings. This can also be seen as a combination of two fundamental social choice frameworks: ranking aggregation and multiwinner voting. We propose three proportionality notions that capture different types of representation in this setting: positional proportionality, pairwise proportionality, and proportionality for solid coalitions (PSC). On the one hand, we show that positional proportionality and PSC are always satisfiable for any input rankings and target compression size, and a desired output can be found in polynomial time. On the other hand, we prove that pairwise proportionality cannot be satisfied in general, but can nevertheless be attained when the input rankings are single-peaked or single-crossing.