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.

ALT Round Robin (RR) is a simple and widely used picking sequence mechanism for allocating indivisible goods, known to guarantee envy-freeness up to one item (EF1) when preferences are additive. Despite being manipulable (meaning that agents may have an incentive to strategically misreport their preferences), it is known to always admit at least one pure Nash equilibrium. In this paper, we study an iterated variant of RR, in which agents observe the outcome of the mechanism at each iteration and may revise their reported preferences through a best-response dynamics. We first consider a full-information setting, where agents observe both the outcome and the reported preferences of all the agents. In this setting, we show that cycles can occur even under strong restrictions on the manipulations carried out by the agents. We nonetheless identify a natural restriction (item-preserving swaps), under which convergence to a pure Nash equilibrium is guaranteed to exist for any number of agents and

ALT Language-model agents are increasingly deployed to act on behalf of people in settings where individual decisions shape shared outcomes. We examine whether five production models adapt their contributions to changing risks and partner behaviour, or instead follow a relatively fixed strategy. In a collective-risk dilemma game (CRG), six players contribute to a shared pool over ten rounds; if the pool falls short of its target, a catastrophe may destroy their remaining resources. Four models contributed approximately an equal share at every positive risk level, and four of the five also contributed when risk was zero, even though contributing could not improve their payoff. Explicitly stating that only the agent's own payoff mattered reduced zero-risk contributions for most models, while a more neutral prompt did not. Several models correctly identified which action offered the higher expected payoff at different risk levels, yet their contributions changed little. Against fixed partners

ALT Digital marketplaces increasingly earn revenue from transaction commissions and seller-facing data services. Sellers may purchase data to increase revenue or avoid competing with an informed rival. We examine how consumer disclosure rights shape these motives and the platform's incentive to provide data. We develop a game-theoretic model of a commissioned platform, two differentiated sellers, and privacy-sensitive consumers. Data generates value through bilateral sales-revenue gains and competition threats arising from asymmetric access. Under mandatory collection, the platform can monetize defensive adoption, even when bilateral personalization reduces seller revenue. Under voluntary disclosure, anonymous purchasing and strictly positive privacy costs make unilateral disclosure unattractive in the baseline. Exclusive access thus yields no usable information, restores sellers' no-data rejection payoffs, and eliminates defensive fees. Profitable provision therefore requires nonnegative

ALT We study the optimal design of a self-financing event, a problem that requires balancing the recruitment of costly, positive-value participants with revenue-generating agents who may impose negative values on the event. We introduce a novel two-sided mechanism design framework with plus agents equipped with private costs and positive impact, and minus agents with private values and negative impact upon inclusion in the event, to maximize the overall quality of the event under a budget-balanced (BB) constraint so that the designer does not run a deficit. We conduct a comprehensive study on the theory of optimal event curation on various utility functions. For additive utility, we fully characterize the optimal incentive-compatible Bayesian mechanism under both the ex-ante and ex-post BB constraints. For submodular utility, we propose an ex-ante BB mechanism that achieves a constant-factor approximation to the optimal Bayesian mechanism.

ALT AI services are prone to moral hazard, as model providers can silently route requests to cheaper, lower-quality models, and the inherent stochasticity of model outputs makes this degradation hard to detect. Contract theory addresses moral hazard by designing payment rules that reward high-quality outputs and prevent strategic overcharging. However, existing frameworks assume interactions of fixed duration, whereas AI services are typically consumed through subscriptions and pay-as-you-go APIs that users can terminate at any time based on observed performance. We show that this flexibility can break standard contracts, opening them up to abuse by either the providers or users. To address this, we extend contract theory to account for unknown exit rules. We formalize the problem as a Principal-Agent game, and show that budget-optimal contracts in this setting are proportional to anytime-valid hypothesis tests based on likelihood-ratio e-values. We give an efficient algorithm for computin

ALT Indivisible resources allocated in advance may need to be reallocated when capacity reductions make existing assignments infeasible, yet monetary compensation is often impractical or undesirable. We develop a sequential resource reallocation scheme using reusable artificial credits, where agents hold pre-existing resource rights and have heterogeneous marginal valuations over time blocks. Capacity reductions produce fractional endowments, which our closed-credit scheme resolves into indivisible final allocations. We model agents' intertemporal preferences through a predicted-value-to-go function and characterize conditions ensuring that their optimal demand is non-increasing in price. We propose an ascending-auction mechanism that partitions agents into subgroups and uses the minimum subgroup market-clearing price as a common transaction price. We show that the mechanism preserves non-myopic individual rationality and weak nontrader neutrality. Moreover, we establish Pareto efficiency

ALT We present a scalable framework for solving multi-step tasks through a decentralized market of self-interested agents. Prior theoretical work demonstrated that agents organized through sequential auctions can converge to a globally optimal policy in a Markov decision process (MDP), but relied on the restrictive assumption of the existence of perfect clones as a model of perfect competition. In reality, exact clones drive agent profit to zero, violating the natural risk-reward incentives of participants. Conversely, we empirically demonstrate that the opposite extreme, absence of competition, also leads to market failure and value extraction collapse. Between these two extremes, we investigate how heterogeneous agents can survive in markets that span the critical middle ground of imperfect competition. To be profitable, agents learn to strategically shade bids to secure positive individual profit margins, while still ensuring that the marketplace functions effectively enough so that col

ALT Our understanding of turn-based stochastic games is reminiscent of our understanding of linear programming in the 1970s. Instead of the simplex method, we have two families of algorithms - policy iteration and value iteration - which work well in practice but are known to run in exponential time on some input instances, and we still lack an algorithm that runs in polynomial time on all instances. A recent result by Loff and Skomra showed that, for deterministic discounted and mean-payoff games played on an ergodic graph, a variant of policy iteration runs in smoothed polynomial time. This offered an explanation of why policy iteration performs well in practice, analogous to Spielman and Teng's explanation for the simplex method. In this paper, we drop the ergodicity assumption: we show that their policy iteration algorithms run in smoothed polynomial time for any game graph. We do this by defining a condition number that naturally generalizes theirs, showing that sufficiently-perturbed

ALT Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching⁺ (RM⁺) update, and a seemingly minor implementation choice accounts for much of its practical speed: alternating the two players' updates, so that the second player responds to the strategy the first player just produced. A widely repeated intuition explains why: seeing the opponent's fresh strategy should act like optimism. We treat this intuition as a testable hypothesis about deterministic two-player zero-sum self-play dynamics and find that its canonical additive form fails an information-matched test. On an analytic witness family we compare alternating RM⁺ against a one-sided predictive RM⁺ that receives the same information channel each round and differs only in where the fresh signal enters, a persistent regret state versus a transient prediction term. Our main result is a dichotomy theorem that reduces trajectory separation to the recurrence of exact-vertex play by

ALT Understanding the objectives that drive agents' behavior is crucial in strategic environments, where multiple agents interact and adapt to one another. This challenge arises in domains such as cybersecurity, autonomous driving, and online markets, where agents' underlying incentives are typically unknown and must be inferred from their observed behavior. Inverse reinforcement learning (IRL) provides a natural framework for this problem, but extending IRL to strategic multi-agent settings introduces a fundamental challenge: a reward that explains observed behavior does not necessarily induce optimal strategies when used for decision-making. In this work, we study this problem through the lens of strategic identifiability, and show that learning from a fixed policy pair can be insufficient to strategically identify rewards, independent of the number of expert samples K. Motivated by this, we introduce an active IRL algorithm for two-player repeated Stackelberg games, in which the leader

ALT Repeated Bertrand competition is a stringent benchmark for algorithmic pricing: in homogeneous-goods markets, standard learning procedures typically select the stage-game Nash outcome with prices near marginal cost. We show that LLM pricing agents can escape this benchmark, depending on deployment decisions. LLMs outperform standard online learners through faster adaptation, but this advantage largely disappears against full-information learners. An extracted surrogate algorithm illustrates how LLMs in specific deployments profit from regularly undercutting slower learners. Agents that post one price every period from raw market histories that include rival prices can sustain supracompetitive regimes in self-play. Agents that periodically emit probability distributions from summarized histories of their own profits instead move toward the competitive region in self-play. Markets mixing these interfaces can generate dynamic regimes in which LLMs establish a high-price anchor and regular

ALT The Value Problem for weighted timed games, an extension of timed automata with weights and adversity, consists in determining, given a weighted timed game with a reachability objective and a rational threshold, whether or not the value of the game exceeds the threshold. This problem is known to be undecidable for weighted timed games, i.e., there is no algorithm that can compute the value exactly. A natural alternative is to approximate the value; however, the Approximation problem is also undecidable in general. In this paper, we prove that the Approximation problem is decidable in 4-ExpTime for weighted timed games whose executions are time-bounded.

ALT Accord is an arbitration oracle on Solana. Any Solana program can create an application specific court (i.e. subaccord) and file disputes. A random jury of a specialized, stake-weighted juror pool reviews encrypted evidence and votes under commit–reveal. Jurors that vote with the final ruling earn fees and slashed stake. Jurors that vote against it lose stake. Appeals grow the panel stepwise from 3 to 31 jurors, which raises both the cost of maintaining a captured verdict and, under certain conditions, the probability of a correct majority. Each pool defines its own collateral mint and its own fee mint, so the economics can fit the application. This paper elaborates the mechanism, the incentive model, the residual trust assumptions, and the differences to the established court on EVM, Kleros. We further discuss implementation details that are Solana specific.

ALT An agentic market is a decentralized serving-time market where AI agents bid to claim each user prompt. An agent's bid is based on its expected value for the prompt, which is the expectation of the reward for its response minus its inference costs. First-price auctions (FPAs), in which the highest bidder pays its bid and receives the prompt, are a natural way to allocate prompts in such a market, since they are simple and transparent to run, and do not require central knowledge of private capabilities and costs. However, FPAs are not truthful: participants may bid less than their true value in the hope of a larger profit, and the prompt may then be allocated to someone other than the bidder who values it the most. This welfare loss is quantified by the price-of-anarchy (PoA). In this paper, we argue that agentic markets are likely to possess features that reduce the price-of-anarchy. The first is a competitive floor, which occurs when multiple bidders usually value the prompt above som

ALT Pairwise comparison data are a standard supervision signal in preference learning, but disagreement in such data can reflect stable latent heterogeneity, ephemeral stochasticity, or non-binary responses hidden by a forced-choice interface. We study which of these semantic distinctions are identifiable from the feedback channel itself. We introduce a nonparametric latent semantic model with three querywise quantities: aggregate directional preference μq, persistent disagreement τq, and non-binary mass αq. Under the anonymous binary channel, we prove an exact semantic fiber theorem: μq is point-identified, whereas (τq, αq) vary over an explicit feasible region compatible with the same binary law. Same-annotator repeats identify τq through a covariance identity, abstention-enabled feedback identifies αq directly, and together they point-identify the full semantic triple. We also derive finite-sample estimators, nonasymptotic concentration bounds, and semantics-aware action-recovery guaran