We study dependence measures between two discrete random variables. The measures vanish at independence and satisfy the data processing inequality (DPI): stochastic post-processing of one variable cannot increase dependence. We ask which such measures admit an exactly unbiased estimator from a fixed finite number of i.i.d. samples, a property equivalent to being polynomial in the joint probabilities. We distinguish fixed-alphabet DPI, which preserves the alphabet size of the variable being processed, from dimension-changing DPI. Under one-sided fixed-alphabet DPI, every measure with a continuously differentiable extension to a neighborhood of the closed probability simplex vanishes whenever one processed state has zero probability. If the processed alphabet is larger than the other alphabet, the measure is identically zero. If it has $n$ states and the other alphabet has at least $n$, every nonzero polynomial measure has degree at least $2n$ and requires at least $2n$ samples for unbiased estimation. Both bounds are attained by the Gram determinant. Under one-sided dimension-changing DPI, every family with the same boundary regularity is identically zero. These results yield sharp task bounds for multi-task peer prediction. For two agents with $n$ signals each, $2n$ tasks are necessary and sufficient for nontrivial expected payments that vanish for independent reports and cannot increase under memoryless stochastic garbling. Under these requirements, unequal signal-space sizes force the larger-alphabet agent's expected payment to vanish identically for any finite number of tasks.
Edge computing service deployment requires the Network Operator (NO) and Service Providers (SPs) to coordinate investment and resource allocation under uncertain demand. This paper develops an audit-based service management framework for daily coalition formation with fixed capacity and service-level agreement (SLA) reservations. A two-stage coalitional game separates infrastructure investment from operational participation. Demand follows a Geometric Random Walk (GRW), and SPs apply an ordered admission and suspension rule using reported marginal contributions. With the NO held fixed, the operational coalition value is submodular; mandatory reservations can produce negative Shapley payoffs. We derive a separable benchmark, compute operational Shapley allocations, and give a sufficient condition for convergence to an individual equilibrium. A probabilistic audit mechanism provides a conditional daily truthfulness guarantee under verified settlement and enforceable penalties. For five service classes over three years, the reference run gains 12.4% over static grand-coalition membership and recovers 94.6% of the full-information optimum. Across 30 runs, the median gain is 13.3%. Sensitivity tests examine policy parameters, capacity and alternative demand models. The gain depends on capacity and update order; abundant capacity can make the admission rule underperform static membership.
We study robust repeated contextual pricing, where valuations depend linearly on the features. At each round $t\in[T]$, a seller observes a context, posts a price, and receives only a possibly corrupted binary sale feedback. When the seller knows an upper bound $C$ on the number of corrupted rounds, we design an algorithm with regret $\mathcal O(Cd+d^2\log T)$, where $d$ is the context dimension. This is the first guarantee for robust contextual pricing that separates the dependence on the corruption budget $C$ from the horizon $T$, closing the problem left open by Gupta, Guruganesh, Paes Leme, and Schneider (2025). In this work, we go even further by developing a randomized algorithm that attains regret of order $\mathcal{O}(Cd+d^2\log T+d\log^2T)$ with high probability, without knowing the number of corrupted rounds $C$. Finally, we show that randomized algorithms that do not know $C$ cannot guarantee regret of order $\mathcal{O}(C)+o(\log^2 T)$ with high probability, even in the one dimensional non-contextual case.
Angel M. González-Rueda, Iago Núñez Lugilde, Jose L. Crespo-Vazquez, Tarek Alskaif
This paper proposes a cooperative game-theoretical framework for the financial settlement of real-time deviations in Community-Based Local Energy Markets (CB-LEMs). The real-time settlement process is modeled as a transferable-utility cooperative game, and the resulting Real-Time Local Energy Market (RTLEM) game is shown to be superadditive and balanced. We analyze two game-theoretical allocation mechanisms, the Shapley value and the nucleolus, and evaluate their efficiency, individual rationality, coalitional rationality, and temporal-aggregation properties. We subsequently compare these mechanisms with a settlement rule based on proportional imbalance responsibility. The three mechanisms are efficient and individually rational, but only the nucleolus is guaranteed to satisfy coalitional rationality for every RTLEM instance. The proposed framework is demonstrated using real-world data from a residential energy community in Amsterdam, showing the trade-offs among the three allocation mechanisms in terms of surplus distribution, coalitional stability, interpretability, and computational requirements.
We study local coordination on finite graphs, equivalently, the ability of randomized local protocols with independent private randomness to produce highly correlated outputs at neighboring vertices. Hutchcroft, Rospuskova, and Tamuz (2026) showed that if such local coordination can be achieved with low cost, then the graph admits a low-cost leader profile, or equivalently an appropriate bounded-radius decomposition, with a square-root loss in the cost. We substantially improve this bound for unbiased binary outputs. If the average disagreement is $\varepsilon$, we construct a leader profile of cost $O(\varepsilon\log(1/\varepsilon))$. The key ingredient is an information-theoretic influence measure: after fixing an ordering of the independent information sources, we assign to each binary output the increments of mutual information revealed along that ordering. For two outputs that disagree with probability $p$, the corresponding measures are within binary entropy $h(p)$ in total variation. Combined with a grand coupling theorem, this yields the improved bound. We also show that a universal linear bound is impossible. We construct graphs with binary local profiles of cost $O(\varepsilon)$ for which every leader profile has cost $$ Ω\!\left(\varepsilon\sqrt{\log(1/\varepsilon)}\right). $$ The construction uses weighted majority functions and can be implemented as an action-symmetric Nash equilibrium, giving a negative answer to the question of HRT whether leader equilibria are always optimal up to a constant factor. Finally, we show that the binary assumption is essential: for general real-valued outputs, the square-root dependence of the HRT theorem is sharp up to a universal constant.
Over-the-Air Federated Learning (OTA-FL) improves communication efficiency by exploiting waveform superposition over wireless Multiple-Access Channels (MAC). However, client heterogeneity, fading, energy constraints, and participation imbalance can degrade both fairness and aggregation accuracy. Existing Pareto-oriented fair OTA-FL schemes may still suffer from large aggregation distortion when highly weighted clients experience poor channel conditions. This paper proposes DisC, a game-theoretic distributed client selection framework for fairness-aware, channel-aware, and energy-efficient OTA-FL. Each client selects its participation level by maximizing a utility that captures Pareto fairness importance, learning relevance, OTA distortion, energy consumption, and delay. We show that DisC admits a Nash equilibrium and can be formulated as an exact potential game, where stable equilibria correspond to locally optimal OTA-FL operating points. DisC therefore offers a distributed, incentive-compatible alternative to centralized client selection under wireless and resource constraints.
People face the problem of classifying objects into categories while aggregating their opinions. We axiomatically study such a classification aggregation problem with multiple memberships, meaning that each individual assigns one category to every object, whereas the resulting classification may assign more than one category. Under the natural settings and axioms (i.e., Independence and Supportiveness), each of our new axioms -- Responsibility, Split Stability and Rejection Stability -- characterises what we call the junta rules. The rules assign a category to an object exactly when some member of a fixed coalition does so. The coalitions that can secure an assignment form a grill, a topological structure implied by an ultrafilter. Hence, the study parallels the literature on Arrow's theorem characterised by the decisive coalition structures. An infinite population setting is also investigated to clarify the differences among the axioms.
Classical Bayesian persuasion assumes that an information designer can condition signals on the entire state. We propose persuasion by parts. In this model, the receiver's payoff from acting is $X = \sum_{i=1}^n X_i$ for independent coordinates $X_1,\ldots,X_n$ observed by separate sources. The designer commits in advance to a product experiment, in which each source $i$ can condition its signal only on $X_i$. Given the signals, the receiver computes her posterior mean $y$ of $X$ and acts with probability $g(y)$, where $g\colon \mathbb{R} \to [0,1]$ is a nondecreasing function. The designer aims to maximize the probability of action. Let $V_{\mathrm{prod}}(g)$ and $V_{\mathrm{joint}}(g)$ be the supremum probabilities of action under persuasion by parts and under joint persuasion, respectively. When the designer knows $g$, we show $$ V_{\mathrm{prod}}(g) \;\ge\; c\,V_{\mathrm{joint}}(g)^2 \qquad\text{for every nondecreasing } g\colon \mathbb{R} \to [0,1], $$ where $c > 0$ is an absolute constant independent of $n$ and the prior; the exponent $2$ is tight. When $g$ is unknown, we construct a product experiment $Π$ from the prior alone, whose probability of action $V_Π(g)$ satisfies $$ V_Π(g) \;\ge\; c_\varepsilon\,V_{\mathrm{joint}}(g)^{2 + \varepsilon} \qquad\text{for every } \varepsilon > 0 \text{ and every nondecreasing } g\colon \mathbb{R} \to [0,1], $$ where $c_\varepsilon > 0$ depends only on $\varepsilon$.
Dominant Resource Fairness (DRF) is a resource allocation scheme, addressing the problem of fair allocation of multiple resource types among users with heterogeneous demands for different types of resources. Based on Max-min Fairness, which is a well-established algorithm in the literature for allocating resources in single resource type scenarios, DRF generalises the main principle of maximising the minimum share given to any user to the multiple resource case. It has a number of desirable properties, such as Sharing Incentive, Envy-Freeness, Pareto Efficiency, and Strategy Proofness, that make it preferable over alternatives, and as such, it is widely adopted in distributed systems. In the present study, we revisit the original study and analyse the structure of the algorithm in closer view. The main contribution is an alternative algorithm, which approximates the DRF allocation in linear time, significantly improving over the original algorithm's pseudo-polynomial runtime. We name the new algorithm Precomputed Dominant Resource Fairness (PDRF), after its main working principle. We provide bounds for approximating the original algorithm, and critically evaluate the agreements of aforementioned properties, comparing DRF and PDRF over them. It turns out that there is an adversarial strategy which forces DRF to unfairly allocate more resources to users who submit inflated demands. PDRF, on the other hand, favouring smaller demands, penalises such adversarial behaviour and creates incentive for users to submit their minimal demands.
Anh Duc Nguyen, Ioannis Anagnostides, Brian Hu Zhang, Tuomas Sandholm
Alternating updates, that is, where each player is updated in turn, tend to typically perform better in regret matching algorithms than simultaneous updates. Alternation within the regret matching family has long been a central ingredient of practical solvers for zero-sum games. Yet our theoretical understanding is lagging behind. In this paper, we address this gap by developing a systematic way of analyzing such algorithms. Our framework centers on an alternating analog of the RVU property that we introduce, which we use to obtain the optimal $T^{-1}$ average-iterate convergence within this family. In particular, we establish this for two simple variants of predictive regret matching$^+$: i) increasing-regret predictive regret matching$^+$ and ii) half-prediction regret matching$^+$. Interestingly, we find that half prediction is the unique prediction multiplier that satisfies our alternating RVU property, giving it a strong theoretical justification. Going beyond average-iterate convergence, we refine our framework to obtain $T^{-1/2}$ best-iterate convergence and further establish convergence of their strategy profiles to a single Nash equilibrium, without assuming equilibrium uniqueness. We go on to establish separations between alternating and simultaneous updates, including a game in which half-prediction regret matching$^+$ converges under alternating updates but fails to converge in terms of the last iterate under simultaneous updates. This provides theoretical support for the empirical observation that alternation can stabilize learning dynamics. Finally, experiments on 15 game benchmarks demonstrate that the strong theoretical properties of the half-prediction mechanism translate to strong practical performance, being on par with state-of-the-art solvers.
We study proportional fairness in graphical resource allocation, where agents are vertices, indivisible items are edges, and each item must be allocated to one of its two endpoints. It has been proved that PROP1 orientations always exist and PROPx orientations may not, but it has remained open whether the intermediate relaxations PROPm and PROPavg (both can be satisfied without graphical constraints) can always be satisfied. In this paper, we resolve this gap. We prove that PROPm orientations always exist for goods on multigraphs and can be computed efficiently. The guarantee extends to chores and a mixture of goods and chores. In sharp contrast, we show that PROPavg orientations need not exist, even for simple graphs with binary valuations, and that deciding their existence is NP-complete. We further quantify the efficiency loss of PROPm: for goods, the price of PROPm is exactly $2$, which is one of the few settings where a constant bound on the price of fairness can be obtained. We complement these results with hardness results for welfare optimization under PROPm and for the existence of orientations that are simultaneously PROPm and Pareto optimal.
There is growing experimental evidence that $Q$-learning agents can learn to charge supracompetitive prices. We ask when such behavior persists, whether it emerges, and which strategies support it. In a repeated pricing game in which firms condition on the previous period's price profile, we give conditions on the learned action values under which supracompetitive prices become an absorbing state once experimentation ends. We then show that under softmax exploration these conditions are reached with positive and explicitly bounded probability, both from a random and from an all-zero initial $Q$-table. In the latter case firms lock in supracompetitive prices because they never learn that undercutting pays; the same mechanism can lock in the competitive price, so the long-run outcome is selected by the exploration path. Finally, we give sufficient conditions on the learned table under which the induced strategy is naive collusion, a grim trigger strategy or an increasing-price strategy; grim trigger strategies are subgame perfect under a standard discounting condition, whereas naive collusion is generally not an equilibrium.
We consider online learning in bilateral trade on platforms such as Uber, Airbnb, and eBay. In each round, a platform posts a payment to a seller and a price to a buyer, both with private valuations, and observes only whether trade occurs. Its objective is to maximize cumulative gains-from-trade, the sum of the differences between buyers' and sellers' valuations across completed trades. We measure the platform's performance by its regret against the best fixed common price. Financial self-sufficiency motivates global budget balance (Bernasconi et al., 2024), which allows profits from some trades to subsidize others, provided that the final balance is nonnegative. Such financial planning should also account for the time value of money: profits earned earlier can accumulate interest, providing additional funds for future subsidies. Motivated by this observation, we introduce global budget balance with interest, under which a platform starting with no funds can use both trading profits and accrued interest to finance subsidies. For a horizon of $T$ rounds and a fixed exponent $θ\ge0$, we consider the per-round interest rate $r_T = T^{-θ}$. We study two classic valuation models, adversarial and correlated i.i.d., and obtain tight bounds on regret against the best fixed common price in both. As the interest rate grows, optimal regret in each model drops from $\tildeΘ(T^{3/4})$ to $\tildeΘ(T^{5/7})$. The intermediate rates differ: $\tildeΘ(T^{3θ/4})$ for adversarial valuations when $20/21 < θ< 1$, and $\tildeΘ(T^{(2θ+3)/7})$ for correlated i.i.d. valuations when $1 < θ< 9/8$. Finally, as an extension, we study $α$-regret, with approximation factor $α\ge1$, for adversarial valuations against the best feasible distribution over price pairs, and show that the optimal competitive ratio rises from 2 to 3 as interest strengthens.
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui
We prove that computing a complete contiguous $\varepsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations. The hardness holds even when $\varepsilon$ is given in unary, and even when every density takes only the values $λ$ and $2λ$ for some $λ>0$ common to all agents and has at most six breakpoints. As a consequence, computing an exact contiguous envy-free allocation is also PPAD-complete, even under the same density restrictions. Our key ingredient is to assign prices to the pieces so that, in every approximately envy-free allocation, all prices are nearly equal, regardless of how the pieces are assigned to the agents. We further show that, for every fixed integer $c\ge1$, computing a contiguous allocation of indivisible goods on a path that is envy-free up to $c$ goods (EF$c$) is PPAD-complete for additive valuations, and this remains true even for $c=\lfloor m^α\rfloor$ with any fixed rational $0<α<1$, where $m$ is the number of goods. This hardness holds even for binary valuations in which each good is valued by exactly one agent and all agents value the same number of goods. All these results extend to chores. Our results answer three open questions at once: whether contiguous envy-free cake cutting is PPAD-hard for additive valuations, the complexity of computing contiguous EF1 and EF2 allocations of goods on a path, and the corresponding question for EF1 allocations of chores.
Today, most people obtain AI inference by buying it from a small number of organizations that run large data centers, while many GPUs owned by individuals and small institutions sit idle for much of the day. Bitcoin showed that strangers can contribute resources under shared rules and receive checkable rewards, but it relies on an asymmetry: proof-of-work is expensive to produce and cheap to verify. Useful inference has no such asymmetry. We propose the Open Inference Market (OIM), which replaces the missing asymmetry with an economic mechanism. A worker delivers a result without knowing whether it will be audited; its unsettled earnings serve as collateral during a challenge window; and confirmed cheating forfeits all of it. We call this principle earnings as collateral. In a simplified model we show three things. The number of audits needed for deterrence is a constant per worker per day, independent of the worker's throughput, so the audited share falls as the network gets busier. A new worker can join with a short period of intensive auditing and a very small bond. And whether the mechanism works at all depends only on the ratio of the audit judge's false-flag rate to its detection rate. Under example parameters, about 0.3 replays per worker per day are enough to make cheating unprofitable for a rational worker. On this basis we lay out a path that hands four powers back to participants one at a time: owning compute, writing history, judging work, and releasing value. A compute center need not be a building; it can be a protocol that anyone can join.
The arboricity of a graph is the minimum number of forests required to cover all its edges. In this paper, we examine arboricity from a game-theoretic perspective and investigate cost-sharing in the minimum forest cover problem. We introduce the arboricity game as a cooperative cost game defined on a graph. The players are edges, and the cost of each coalition is the arboricity of the subgraph induced by the coalition. We study properties of the core and propose an efficient algorithm for computing the nucleolus when the core is not empty. In order to compute the nucleolus in the core, we introduce the prime partition which is built on the lattice of maximum-density edge sets. The prime partition decomposes the edge set of a graph into a non-prime set and a partially ordered collection of prime sets defined from minimal densest minors and their invariant precedence relation. Moreover, edges from the same set of the partition always have the same value in a core allocation. Consequently, when the core is not empty, the prime partition significantly reduces the number of variables and constraints required in the linear programs of Maschler's scheme and allows us to compute the nucleolus in polynomial time. Besides, the prime partition provides a graph decomposition analogous to the celebrated core decomposition and the density-friendly decomposition, which may be of independent interest.
Yuanchen Brian Tang, Jiaxin Song, Bhaskar Ray Chaudhury, Ruta Mehta
We study the stability of data exchange among competing firms. Unlike tangible goods, data is non-rival: sharing it does not deprive the giver of its use. On one hand, competing firms-- often operating as machine-learning-driven predictors that collect observations from a shared environment to solve similar tasks-- can improve their predictive accuracies from pooling data. On the other hand, they compete for market share, which may depend on their relative predictive performance. This raises the central question of this paper: can there be a stable data exchange in such competitive environments? We formalize this via a model of $n$ firms exchanging fractions of their datasets, with predictive performance feeding into market competition. We adopt core stability as our solution concept, accounting for externalities via worst-case responses by non-participating firms. Our main results reveal a sharp contrast driven by demand structure: (i) in fully rational markets, where customers flock entirely to the top-performing firm, a core-stable exchange always exists for any monotone continuous prediction functions; (ii) in partially rational markets with logit-style demand, core-stable exchanges may fail to exist-and even approximate cores can be empty. Our impossibility results suggest that internal profit-sharing within coalitions can restore stability in partially rational markets. We formalize this intuition by showing that when co-operating coalitions equally redistribute market-share revenues among members, a core-stable data exchange exists. Finally, we propose a natural exchange dynamic and demonstrate empirically that it converges to a core-stable data exchange in fully rational markets on simulated instances derived from real datasets.
We study approximate Nash equilibria in nonatomic congestion games, with the goal of understanding how much the social cost can change when the equilibrium condition is relaxed. We consider $ε$-approximate Nash equilibria ($ε$-NE), in which each player uses a strategy whose cost is at most $1 + ε$ times the minimum available cost. We compare the social costs of $ε$-NE and exact Nash equilibria. This lets us quantify, for example, how much a navigation app can reduce total travel time when drivers tolerate routes slightly slower than the fastest available route. For degree-$d$ polynomial latencies in both general nonatomic congestion games and single-commodity routing games on series-parallel networks, we give tight lower and upper bounds on the relative change in social cost from an exact Nash equilibrium to any $ε$-NE, with matching instances for every $ε$. For small $ε$, the largest possible relative reduction and increase in general congestion games are both $Θ(\sqrt{dε})$, independently of the number of resources and populations. In contrast, on series-parallel networks of depth $h$, the largest possible relative reduction is $Θ(hε)$, while the largest possible relative increase is known to be $ε$. For the classes of games we study, these results give a tight and quantitative characterization of the possible changes in social cost and establish a separation between general and series-parallel networks.
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.