Finding Competitive Equilibria in Online Marketplaces with Platform Fees, Taxes, and Subsidies
Taihei Oki, Ryosuke Sato
AI 速览：研究在带平台费、税费、补贴等分段线性转移的多单位交易网络中，如何用升价算法计算最小均衡价格向量与均衡配置。
We study equilibrium computation in multi-unit trading networks with valuations satisfying generalized full substitutes and agent- and transaction-specific piecewise-linear transfer functions. These transfers model platform fees, taxes, subsidies, and membership discounts in online marketplaces. Our ascending procedure raises prices at different rates and reaches the minimum equilibrium price vector in finitely many iterations, each implementable in strongly polynomial time under our oracle and arithmetic models. An equilibrium allocation can then be recovered efficiently. The method extends primal-dual techniques developed for ascending auctions to handle complementarities between purchases and sales through a submodular flow formulation. In single-seller markets with substitutes and complements, our framework also extends the double-track auctions of Sun and Yang (2009) and Shioura and Yang (2015) to bidder- and good-specific transfers.
From signaling to interviews in random matching markets
Maxwell Allman, Itai Ashlagi, Amin Saberi, Sophie H. Yu
AI 速览：研究在带面试后冲击的集中式随机匹配市场中，申请人向有限数量偏好对象发送信号如何减少面试并影响临时稳定性。
In two-sided labor markets, interviews precede matches. Rising interview volumes in medical residency markets have motivated signaling mechanisms that let applicants express interest in a limited number of partners. We study how signaling reduces interviews in centralized random matching markets with post-interview shocks. We focus on interim stability, which ensures that agents do not regret not interviewing with each other. A matching is almost interim stable if it becomes interim stable after removing a vanishing fraction of agents. We consider markets with $n$ agents in which agents on the short side, long side, or both sides signal their top $d$ preferred partners. An interview occurs whenever at least one party signals the other. When the probability of a nonnegative interview shock is bounded away from zero and $d=ω(1)$, short-side signaling leads to almost interim stable matchings. Long-side signaling can fail in strongly imbalanced markets when pre-interview scores outweigh interview shocks. In balanced markets without interview shocks, both-side signaling fails to achieve almost interim stability when $d=o(\log n)$. For larger $d \ge Ω(\log^2 n)$, under the same probability condition, short-side signaling achieves perfect interim stability, while long-side signaling can fail in imbalanced markets. We extend these findings to propose a signaling mechanism for multi-tiered random markets and identify conditions for incentive compatibility. A technical contribution is the analysis of a message-passing algorithm for stable matchings on trees, together with local availability certificates used to study interim stability on general graphs.
First-Order Bilevel Optimization for Non-truthful Auction Design
Shing-Hei Ho, April Niu, Ellen Vitercik, Kai Wang
AI 速览：将非真实拍卖设计建模为含多个策略跟随者的 Stackelberg 博弈，提出全一阶算法优化收益并给出非渐近收敛保证。
Automated mechanism design has enabled the learning of complex auction mechanisms using neural networks. However, designing non-truthful auctions remains challenging because bidders' equilibrium strategies depend on the auction mechanism and thus evolve as the mechanism is optimized. In this work, we formulate auction design as a Stackelberg game with multiple strategic followers and develop a fully first-order algorithm for revenue optimization in non-truthful auctions. We establish non-asymptotic guarantees for hypergradient approximation and show that, under standard smoothness and strong-monotonicity assumptions, our method reaches an $O(ε)$-stationary point using $\tilde{\mathcal{O}}(ε^{-2})$ first-order oracle calls. Experiments on symmetric and asymmetric single-item auctions, as well as multi-item auctions, show that our method converges faster than second- and zeroth-order baselines and scales better as the number of bidders increases. Our method also discovers auctions that achieve revenue close to truthful baselines. These results provide a scalable framework for automated mechanism design beyond truthful auctions.
We study a dynamic game where an expert sends probabilistic forecasts to a decision-maker. The decision-maker verifies these forecasts using a calibration test based on past data. How should the expert send forecasts to maximize her payoff while passing the test? For a stationary ergodic process, we characterize the optimal forecasting strategy by reducing the dynamic game to a static persuasion problem. Calibration restricts long-run forecast distributions to mean-preserving contractions of the distribution of truthful forecasts. We compare the payoffs attainable by an informed and uninformed expert, providing a benchmark for the value of information. Finally, we consider a decision-maker who uses a mean-based learning strategy and show that the expert can guarantee at least the calibration benchmark and sometimes strictly more.
The Limits of Price Discrimination When the Market Is Unknown
Irfan Tekdir
AI 速览：在仅知可能价值集合、不知具体价值分布的情况下，刻画市场与市场分割所能产生的消费者剩余与生产者剩余组合。
Bergemann, Brooks, and Morris (2015) characterize the consumer and producer surplus pairs that segmentation can produce when the distribution of values is known. I fix only the set of possible values and characterize the pairs that some market and some segmentation can produce. They form a convex polygon. Its outer edge is the largest efficient surplus a market can have when its uniform-price profit is capped, net of that profit, and truncated equal-revenue markets attain it. At the values no segmentation is needed; strictly between two values, reaching the frontier requires splitting a market into two extremal markets. With a continuum of values up to $\bar{v}$, consumer surplus is at most $π\ln(\bar{v}/π)$ when producer surplus (the seller's profit) is $π$, this bound is reached without segmentation, and no market gives consumers more than $\bar{v}/e$.
Wenhao Wang, Aditya Saraf, Lioba Heimbach, Kushal Babel, Fan Zhang
On high-throughput, low-fee blockchains, a qualitatively new form of maximal extractable value (MEV), spam MEV, has emerged: searchers submit large volumes of speculative transactions, whose profitability is resolved only at execution time. On major rollups, it can consume more than half of block gas, even though only a small fraction of probes ultimately results in a trade. Despite growing awareness of this phenomenon, there is no principled framework for understanding how blockchain design parameters shape its prevalence and impact. We develop such a framework, modeling spam transactions competing for on-chain opportunities under a competitive equilibrium that drives their profits to zero, and deriving equilibrium spam volumes as a function of block capacity, minimum gas price, and the transaction fee mechanism. Empirical evidence from Base and Arbitrum is consistent with several predictions of the model: spam grew sharply as block capacity was scaled up and fell when minimum gas prices were introduced. Our analysis yields three main insights. First, spam is always costly: when block capacity is scarce, it displaces users and drives up gas prices; as block capacity grows, it increasingly consumes execution resources, raising network externality, i.e., the cost of provisioning and processing blocks. We show that spam takes an increasing share of each additional unit of block capacity, so capping it before all users are included creates a favorable trade-off: forgoing a small amount of user welfare eliminates disproportionate spam and externality. Second, we extend the analysis to approximate priority fee ordering and show that it can reduce spam by making earlier block positions more expensive, as spammers pay more to reach early block positions. Third, as user demand grows and blockspace is scaled accordingly, spam's share of block capacity plateaus rather than growing indefinitely.
Despite their practical significance, modern AI systems pose significant societal risks, including toxicity, malicious use, and misinformation. Their mitigation depends not only on technical feasibility but also on the incentives of firms that develop and deploy these systems. We show how profit maximization shapes safety investment in an AI supply chain with an upstream LLM provider and several competing downstream firms. In our game-theoretic model, we derive the market-driven level of safety investment and compare it with the levels that maximize industry profit and market welfare. We find that downstream competition generally induces downstream firms to invest more in safety than the industry-profit-optimal level. By contrast, the upstream provider may underinvest relative to these benchmarks because it is not fully compensated for the surplus from safety investments. Finally, we analyze how different regulatory interventions affect the participants' incentives and profits, and the resulting levels of model safety.
User Equilibrium (UE) is the standard representation of the so-called routing game in which drivers adjust their route choices to arrive at their destinations as fast as possible. Asking whether UE is strong has, so far, been meaningless for human drivers, who do not form coalitions because of technical and behavioral constraints. Here, we demonstrate that this will not necessarily hold for Connected Autonomous Vehicles (CAVs), which can communicate and collaborate to form routing coalitions by exploiting adaptive signal control. Within game-theoretical formulations of Nash Equilibria, we provide a methodological framework and report the novel phenomena through a carefully designed toy-network example, in which we identify so-called \emph{clubs} emerging in different CAV penetration rates and adaptive traffic-light configurations. We detail one such club where three CAVs deviate from the UE and benefit (arrive faster). The formation of such a club has negative consequences for other users (who are not invited to join and must now travel longer) and for the system (making it suboptimal and disequilibrated), thereby triggering adaptation dynamics. These findings raise questions about equity in future mixed-autonomy traffic systems.
We prove the following asymptotically tight lower bound for $k$-color discrepancy: For any $k \geq 2$, there exists a hypergraph with $n$ hyperedges such that its $k$-color discrepancy is at least $Ω(\sqrt{n})$. This improves on the previously known lower bound of $Ω(\sqrt{n/\log k})$ due to Caragiannis et al. (arXiv:2502.10516). As an application, we show that our result implies improved lower bounds for group fair division.
We study multidimensional online generalized assignment under nonstationary arrivals, motivated by resource allocation for large language model agent services. Providers may commit model and tool allowances to agent tasks upon admission, reserving budgets for their internal execution loops. Each request is rejected or accepted with an irrevocable assignment to one compatible server, earning reward and consuming a vector of its nonreplenishing budgets. Arrivals are independent with known, potentially time-varying type distributions. Scalar reductions can discard feasible combinations of requests with complementary resource requirements. To maximize expected reward, we develop Vector-Aware Best-Fit, which combines linear-programming-guided candidate routing with calibrated acceptance while retaining vector feasibility. Relative to the expected clairvoyant offline optimum, its guarantee improves on scalar reduction in the multidimensional case and has the best possible inverse-dimensional order. With an appropriate acceptance parameter, the proposed policy attains the optimal competitive ratio on all-heavy instances, where every feasible assignment consumes more than half of at least one resource budget. We further develop two heuristics that retain its performance guarantee. Computational results show that the heuristics perform well against benchmarks in most tested settings, especially when capacity is scarce relative to demand.
We study routing games in which competing mediators recommend routes to fixed nonatomic populations. Each mediator chooses a randomized flow allocation to minimize its population's expected travel cost, subject to users having no conditional expected gain above a tolerance $ε$ from disregarding their recommendations. We define a fragmented obedient equilibrium (FOE) by combining user obedience with mediator optimality, and establish existence under a lower-hemicontinuity assumption on the obedient policy correspondences. Under affine edge latencies and independent mediator sampling, we derive an exact reformulation in first and second flow moments that preserves best responses and equilibrium profiles. Every feasible moment pair admits a finitely supported realizing policy. When the network has at most four routes, each mediator's best-response problem is an exact semidefinite program. A numerical illustration on the Braess network shows that relaxing obedience can reduce FOE costs, while gaps relative to the social optimum and optimal obedient pooling can persist.
Classical theory predicts that irrational traders lose money to rational traders and are eventually driven out of the market. Yet noise trading, herding, and heuristic trading persist even in highly developed markets. We model a financial market as an ecology of two trading-behavior types, relatively rational (R) and boundedly rational (N), whose composition evolves under replicator dynamics according to relative performance. Each type's fitness depends on the share of the other type and on frictions. When the interaction is complementary, that is, rational traders profit from the mispricing created by boundedly rational traders while the latter benefit from the liquidity and price correction supplied by the former, and when the difference in frictions is moderate, a unique interior composition exists and is globally asymptotically stable: bounded rationality persists endogenously. When the interaction is antagonistic, the same point becomes a tipping threshold between two one-type regimes. Comparative statics show that lowering the costs of disciplined trading, as algorithmic and AI-based trading does, shifts the composition toward rational trading continuously but does not eliminate bounded rationality unless the cost advantage exceeds an explicit threshold.
Muchnik's paradox says that enumerable betting strategies are not always reducible to enumerable strategies whose bets are restricted to either even rounds or odd rounds. In other words, there are outcome sequences x where an effectively enumerable strategy succeeds, but no such parity-restricted effectively enumerable strategy does. We characterize the effective Hausdorff dimension of such $x$, showing that it can be as low as 1/2 but not less. We also show that such reals that are random with respect to parity-restricted effectively enumerable strategies with packing dimension as low as $\log\sqrt3$. Finally we exhibit Muchnik's paradox in the case of computable integer-valued strategies.
In a duopoly with captive and contested consumers, I characterize every pair of consumer and producer surplus that can arise under some market composition and some public segmentation, and construct a market that produces each pair. The set is lens-shaped. At any level of industry profit, consumers do worst when captive and contested consumers are perfectly separated and best in an unsegmented market in which the two firms have equally many captives. A market with unequal captive bases and some contested consumers cannot reach this upper frontier under any segmentation. Between Bertrand competition and monopoly, the frontier itself lies strictly below what consumers would get if everyone paid a single deterministic price yielding the same profit. Firms must randomize, and with downward-sloping demand the resulting price dispersion lowers consumer surplus.
Modern Security Operations Centers struggle with delayed manual incident response, enabling adversaries to advance through the Cyber Kill Chain during early stage reconnaissance. While classical game theoretic defense models optimize strategic resource allocation, they rely on static utility matrices that fail to adapt to dynamic telemetry. This paper presents an integrated, metrics driven decision engine that bridges quantitative risk parameterization and continuous automated response time. Common Vulnerability Scoring Systems exploitability parameters are mapped to attacker success probabilities and evaluate defender log distributions via Factor Analysis of Information Risk Monte Carlo simulations. Real time SIEM logs streams are modeled as Poisson process arrival rates, dynamically updating defender posterior threat belief through sequential Bayesian filtering. A closed form threshold is derived by framing the interaction as a dynamic Bayesian Stackelberg game, where the expected unmitigated risk exceeds proactive containment cost. Parameterized against empirical data from the 2023 MGM Resorts and Caesars Entertainment cyber incident, simulation results demonstrate that the engine suppresses transient background noise while triggering automated SOAR network isolation within seconds of adversarial probing. Multi parameter sensitivity analysis confirms that the decision boundary dynamically adjusts to live perimeter vulnerability, offering a control theoretic foundation for sub minute automated threat containment.
Julian Chingoma, Davide Grossi, Feline Lindeboom, Jan Maly
The study of approval-based committee voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin-Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P = NP), but both can be on the Candidate Interval and Voter Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show that Local DR performs well on multiple empirical measures of diversity.
Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya Sharma
We study a pricing game in markets with budget-constrained buyers, where each seller offers a single good at a price she sets, and each buyer chooses a utility-maximizing bundle subject to her budget. We consider both the rivalrous setting, such as markets for physical goods, and the non-rivalrous setting, such as markets for datasets. Pure Nash equilibria often fail to exist in this game. However, Nash equilibrium assumes that the other sellers keep their prices fixed when one seller deviates, whereas in practice, sellers harmed by a price change may respond, for example, by matching the new price. We propose a new equilibrium notion called Response-Aware Rational Equilibrium (RARE). At a RARE, every deviation by a seller can be deterred by a response from the other sellers, in which no responder earns less than she did right after the deviation. Every Nash equilibrium is a RARE. Assuming that buyers' purchases (among their optimal choices) change continuously with prices, we show that a RARE always exists for rivalrous goods, and for non-rivalrous goods when buyers have equal budgets. Moreover, the RARE that we construct extracts the buyers' entire budget. For non-rivalrous goods with unequal budgets, we show that an approximate RARE exists, where a deviating seller can increase her revenue by a factor of at most $b_{\mathrm{avg}}/b_{\min}$, the ratio of the average budget to the minimum budget. Our proof uses two nested applications of the KKM lemma. We also study a natural dynamic in which sellers repeatedly raise their prices to earn the revenue that they could guarantee themselves by deviating, and show that it reaches an approximate RARE, with additive error $δ$, within $\lfloor B/δ\rfloor$ rounds, where $B$ is the buyers' total budget. The main results of this paper are formally verified in the Lean 4 proof assistant (https://github.com/sharmaeklavya2/dm-rare).
John S. McAlister, Nina H. Fefferman, Tadele A. Mengesha
Coordination games with explicit spatial or relational structure are of interest to economists, ecologists, sociologists, and others studying emergent global properties in collective behavior. When assemblies of individuals seek to coordinate action with one another through myopic best response or other replicator dynamics, the resulting dynamical system can exhibit many rich behaviors. Here we seek to understand these coordination dynamics in the non-atomic setting by use of a nonlinear, nonlocal diffusion equation framework. For this class of nonlocal equations, we prove existence and uniqueness for the initial value problem in the free boundary case and, with certain conditions on the underlying game theory, we go further and prove a maximum principle, weak regularity results, and a characterization of asymptotic behavior. Additionally, with the help of several numerical results, we present several modeling results, characterizing stationary solutions both rigorously and through numerical experiments.
Principal-agent hypothesis testing studies statistical contracts in which a principal rewards an agent according to data the agent generates. Existing work focuses on the single-shot setting, where the agent produces a single dataset. We extend the framework to sequential settings, where evidence accumulates over time, rewards may be deferred to the end or disbursed incrementally, and the agent may stop the contract at a strategically chosen stopping time. We call a contract null-deterring if no ''null agent'' (those whose data-generating distribution lies in the null hypothesis) can profit in expectation under any stopping rule, and our main conceptual result shows that such contracts are characterized by e-processes. We then turn to the agent's best response and identify the optimal stopping rule through the Snell envelope of the reward process. We develop simpler, more interpretable approximations that often require the agent to have only partial knowledge of its distribution.
Janik Bürgermeister, Julius Durmann, Martin Bichler, Mete Şeref Ahunbay, Bary Pradelski, Marco Scarsini
We study equilibrium learning in discretized Bayesian games, focusing on first-price auctions as a testbed for gradient-based learning dynamics under private information. While the symmetric independent private values model admits a unique Bayesian correlated equilibrium (BCE) in the continuous limit, standard convergence guarantees for gradient-based learners do not apply: classical no-regret theory predicts convergence only to Bayesian coarse correlated equilibria (BCCE), which can remain large and far from the competitive equilibrium even under fine discretizations. To bridge this gap, we introduce the notion of Bayesian semicoarse correlated equilibrium (BSCCE), an equilibrium concept that refines BCCE by restricting deviations to probability-preserving transformations consistent with projected gradient dynamics. We provide a linear programming characterization of BSCCE with polynomially many variables and constraints and establish the inclusion hierarchy $BCE \subseteq BSCCE \subseteq BCCE$. Our main finding is that the BSCCE set contracts in many cases as the discretization of the Bayesian game is refined. Even with priors for which BCCE fails to concentrate, the diameter of the BSCCE polytope shrinks toward zero, indicating convergence to the unique continuous-game Bayes-Nash equilibrium. These results provide a principled explanation for the observed robustness of gradient-based learning in discretized Bayesian games, showing that these dynamics select a smaller equilibrium set than standard no-regret theory predicts.
Bisimulation metrics offer a principled notion of task-relevant state similarity in reinforcement learning, but existing constructions and methods are largely confined to discounted MDPs, where contraction arguments ensure well-defined fixed points and downstream guarantees. We develop a unified foundation for bisimulation metrics in undiscounted settings, that is total- and average-reward problems, by replacing the standard operator-centric view with a game-centric one: we interpret prior metric operators as Bellman-Shapley operators of zero-sum turn-based games and define metrics as the corresponding game value functions, yielding unique definitions even when $γ=1$. This game-theoretic foundation facilitates transfer of dynamic-programming theory and algorithms. We also use this game-centric perspective to characterize how metric finiteness depends on structural properties of the underlying MDP and motivate certain directed metrics that remain finite in weakly communicating MDPs. We further introduce an abstract framework for modifying the games' action spaces, allowing general transition coupling sets, that recovers many existing metrics and guides new constructions. Finally, we prove that these metrics bound total-reward and, when the optimal gain is state-independent, optimal relative value differences. We also provide error and suboptimality guarantees for aggregation-based planning in total- and average-reward settings.
Time-series forecasters are ranked almost entirely by accuracy metrics, but a forecast's decision value, its effect on the downstream decision, need not track accuracy and is rarely measured. This problem compounds as large language model (LLM) agents increasingly consume forecasters as tools, mediating them through stochastic, opaque policies. We present Vendster, an evaluation arena measuring how a forecaster's bias and prediction-interval width change the outcome of a buyer--vendor discount negotiation between two LLM agents. In the reference instance Vendster-M5, sampling base demand patterns from the M5 dataset, we evaluate two frontier-closed LLM families (Claude Opus 4.6 and GPT-5.6 Sol) and two open ones (DeepSeek-V3.2 and Qwen3-235B-A22B). Model-generated forecasts raise sales target attainment by up to +17 percentage points (p<0.001), yet standard forecast evaluation metrics such as relWQL and MASE do not predict negotiation outcomes at a statistically significant level. To isolate the causal structure, we substitute in synthetic forecasts with controlled bias and interval width. Under-prediction bias significantly improves outcomes for agents that react more to the forecasts---dose-response slopes -0.387 and -0.416 (p<0.001). Interval width has no statistically significant effect at zero bias. These findings indicate that the direction of forecast bias and agent forecast-reactivity are more strongly associated with downstream outcomes than forecast accuracy. Vendster is fully customizable and released under CC BY-NC 4.0 at https://github.com/amazon-science/Vendster.
Renzhe Xu, Haotian Wang, Xingxuan Zhang, Bo Li, Peng Cui
In this paper, we present the Proportional Payoff Allocation Game (PPA-Game), which characterizes situations where agents compete for divisible resources. In the PPA-game, agents select from available resources, and their payoffs are proportionately determined based on heterogeneous weights attributed to them. Such dynamics simulate content creators on online recommender systems like YouTube and TikTok, who compete for finite consumer attention, with content exposure reliant on inherent and distinct quality. We first conduct a game-theoretical analysis of the PPA-Game. While the PPA-Game does not always guarantee the existence of a pure Nash equilibrium (PNE), we identify prevalent scenarios ensuring its existence. Simulated experiments further prove that the cases where PNE does not exist rarely happen. Beyond analyzing static payoffs, we further discuss the agents' online learning about resource payoffs by integrating a multi-player multi-armed bandit framework. We propose an online algorithm facilitating each agent's maximization of cumulative payoffs over $T$ rounds. Theoretically, we establish that the regret of any agent is bounded by $O(\log^{1 + η} T)$ for any $η> 0$. Empirical results further validate the effectiveness of our online learning approach.
Model distillation has become a major concern in the rapidly growing generative AI discourse. In its simplest form, distillation is the phenomenon where smaller firms can use data distilled from transcripts of conversations with powerful proprietary closed-weight models to train their own models, thus achieving reasonably high model quality but at much lower costs. Besides the legitimate safety and security concerns associated with distillation, another major issue is how it can also distort marketplace outcomes. This motivates us to initiate an exploration of the problem from an economic theory lens. We consider a setting with two players: an incumbent and a distilling competitor and characterize how the incumbent's model characteristics drive the incentives around how much the competitor should distill. We also consider the impact of distillation on key market outcomes like user-side surplus and the incumbent's utility. Our key contribution, however, is to study interventions for preventing or limiting distillation attacks. In this context, we study two settings: i) when it is possible, with a certain probability (which grows in the extent of distillation conducted), to detect an attack on the incumbent's model; and ii) when a distillation attack cannot be reliably detected. In the first setting, we show that penalty-based regulations can be very effective in completely deterring distillation, although it can have potentially adverse effects on market competition and user surplus. In the latter setting, we show that the incumbent can use self-distillation as a mitigation strategy. Importantly, the effectiveness of self-distillation depends on how cost-efficiently the incumbent can deploy a new self-distilled model on the market. On the positive side, self-distillation can preserve market competition thus protecting user surplus to some extent.
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 equilibria exist, BRD appears to be biased toward the higher-performance ones. This evidence also demonstrates that further investigation into a more robust metric for multiagent optimization solutions is warranted and pushes us to understand whether the bias toward better equilibria hold in more general cases.
A perfectly divisible cake is to be divided among a group of agents. Each agent is entitled to a share between zero and one, and these entitlements are compatible in that they sum to one. The mediator does not know the preferences of the agents, but can query the agents to make cuts and appraise slices in order to learn. For each entitlement profile, we provide a lower bound on the number of queries that the mediator requires to construct an allocation that respects the entitlements regardless of preferences. If one of the entitlements is irrational, then the mediator requires an arbitrarily large number of queries.
Anne Moll-Elsborg, Oskar Bohn Lassen, Francisco Camara Pereira
International climate policy requires coordination among countries whose mitigation decisions impose local costs but generate global benefits. Classical game-theoretic and integrated assessment approaches can study these incentives, but typically rely on prescribed behavioural assumptions or equilibrium concepts. Recent work has therefore explored Multi-Agent Reinforcement Learning as a way to model climate-policy cooperation as an emergent outcome of repeated strategic interaction. We extend an existing MARL climate framework with a multi-stage negotiation mechanism in which agents propose agreements, accept or reject commitments, and face penalties for non-compliance. This allows us to study how agreement design affects learned mitigation behaviour, compliance, and climate outcomes. In an idealized setting with four homogeneous agents, we find that non-binding agreements do little to overcome free-riding, while moderate non-compliance penalties improve cooperation and reduce warming. However, excessively strong penalties discourage ambitious commitments, revealing a trade-off between enforcement and participation. We position the framework as a methodological contribution for testing agreement design rather than a predictive model of real negotiations.
We study the compatibility of envy-freeness up to one good (EF1) and Pareto optimality (PO) beyond additive valuations. For two agents with monotone submodular valuations, we prove that a $2/3$-EF1+PO allocation always exists, while for every $α>3/4$, an $α$-EF1+PO allocation may fail to exist even for unweighted coverage valuations. A six-good EF1+PO counterexample resolves the longstanding exact existence question negatively. Exact EF1+PO does exist when one agent has a monotone submodular valuation and the remaining agents have identical additive valuations. For two agents, we also establish tight EF$k$+PO item thresholds of $4k+1$, $2k+1$, and $3k+1$ for two submodular agents, two subadditive agents, and one subadditive and one additive agent, respectively. Finally, deciding whether an EF$k$+PO allocation exists is NP-hard for every fixed integer $k\ge1$, even for three agents with unweighted coverage valuations, one of whom has an additive valuation.
Fariba Dehghan, Sebastian Stein, Vahid Yazdanpanah, Stephanie Gauthier
Online resource allocation faces two coupled challenges: (1) allocating scarce resources efficiently under uncertain future demand, and (2) ensuring that agents report task valuations and requirements truthfully (strategyproofness). Reinforcement Learning (RL) adapts allocation decisions through experience but does not necessarily ensure strategyproofness. Existing strategyproof RL uses a linear allocation rule, which limits the resource interactions it can represent. Neural mechanism design methods offer greater expressiveness, but provide only approximate incentive guarantees. Against this background, we introduce the first strategyproof deep RL mechanism for online resource allocation. It integrates three novel components: (i) a monotonic neural network that learns nonlinear interactions by construction (higher reported value cannot reduce acceptance, while a longer reported duration or larger resource requirement cannot increase it); (ii) a generalised critical payment: the lowest accepted value, with all other inputs fixed; and (iii) training by either RL or imitation of an existing rule. Together, monotonicity and the critical payment ensure strategyproofness and individual rationality, while the neural rule provides flexibility and imitation improves training efficiency. Empirically, on a four-resource stream with two partner pairs that a linear difference cannot represent, the neural rule achieves 97.8% of an offline welfare upper bound, compared with 93.8% for a linear learner and 89.0% for first-come, first-served, closing 65% and 80% of the remaining optimality gap, respectively. Moreover, imitation reaches 97.5% in only 261 seconds, about 89 times faster than RL.
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 associated failure modes, guardrails we built, and our hypotheses. We additionally evaluate our model over 13,200 Monte Carlo games against 11 synthetic opponent archetypes, an ablation of the opponent-modeling layer, and an extensive analysis of 9,337 live-game messages in which moral rhetoric framing in the persuasion setting is strongly correlated with whether the buyer purchased ($χ^2=616.7$, $p \approx 3.7\times10^{-132}$), surviving controls for quality, round, and configuration.