ALT Generative AI interfaces can insert sponsored content at multiple points in an answer, where click-through rates (CTRs) depend on the advertiser-position pair. Under the cascade model, users read ads sequentially and stop after their first click, so both ad assignment and display order affect welfare. For arbitrary pair-specific CTRs, Balseiro et al. (WWW 2026) gave a 4/(1-ε)-approximation whose monotonicity has not been established, and a monotone O(log m)-approximation for m candidate positions. Earlier truthful constant-factor mechanisms require factorized CTR models and do not apply. Whether monotonicity is compatible with a constant-factor approximation in this general setting was left open by that work. We give a polynomial-time mechanism for arbitrary pair-specific CTRs and any limit on displayed ads that is truthful and individually rational in expectation and achieves a 2-approximation to optimal cascade welfare. Our mechanism selects an advertiser-position matching and a desi

ALT Many high-stakes collective problems, e.g., climate mitigation and pandemic response, share a structure in which risk materializes unless a group threshold is met. This threshold is often uncertain, but uncertainty can be reduced at a cost. We study this information cost tradeoff in an evolutionary game theoretic model of social learning in the collective-risk dilemma, where individuals must cooperate to reach a possibly uncertain threshold to prevent collective loss. Individuals may pay a fixed cost to observe the threshold's true value and condition their cooperation on it. Across four threshold priors, we characterize risk levels at which cooperative equilibria emerge and show that low cost information increases group success. However, this effect is reversed at higher costs. We define a private value of information and show that information is worth buying only when it is considerably cheaper than contributing. When purchased information is shared with the group, the cooperative ti

ALT In large language model (LLM)-based multi-agent systems, reported confidence increasingly determines the allocation of scarce downstream attention, computation, and decision influence. This makes reporting strategic: an agent may overstate the relevance of its contribution even when its underlying belief is well calibrated. Existing calibration methods largely assume passive reporting and therefore do not address strategic incentives created when confidence determines downstream allocation. We formulate strategic calibration as a reporting-layer incentive problem and propose the Audited Pivot Scoring Mechanism (APSM). APSM offsets platform-controlled allocation benefits, uses inverse-propensity-weighted sparse audits, charges the Clarke pivot externality, and applies a strictly proper score. Under the stated model assumptions, truthful reporting is the unique expected-utility best response. We also characterize approximate execution and the audit-variance trade-off. Calculator-free exp

ALT Position auctions require assigning advertisers to positions and determining their display order. Under cascade behavior, earlier clicks prevent users from reaching later placements, coupling the click probabilities of selected advertisements. Existing methods achieve constant-factor welfare approximation and monotone logarithmic-factor approximation separately, leaving open whether both guarantees can be attained simultaneously. The difficulty is that welfare-preserving rounding need not maintain the monotonicity of individual click-through rates required for truthful bidding. We resolve this problem by developing a polynomial-time randomized mechanism that achieves a factor-6 welfare approximation and truthfulness in expectation for arbitrary public advertiser-position click probabilities. The mechanism optimizes a reach-weighted linear relaxation and converts its solution into feasible ordered allocations through matching decomposition, probability-bounded grouping, and calibrated a

ALT Permissionless blockchains use transaction fee mechanisms to allocate the resources that transactions consume, such as execution, data bandwidth, and state creation. Recent blockchain designs explore pricing these resources separately rather than through a single unit. We study this shift on Ethereum, whose roadmap moves in stages from a one-dimensional fee mechanism to a multi-dimensional one. We build a demand model for the three resources, calibrated from Ethereum's 2025 block-capacity increases, and find that state creation is the most price-responsive. We then evaluate both mechanisms at higher block capacity, combining the model with transaction-level metering reconstruction and block-level simulation. Under a one-dimensional mechanism, state creation determines the fee and suppresses execution throughput. Adjusting how state is metered can align resource usage under constant demand, but a single fee cannot track all resources when demand varies, leaving all underutilized. A mult

ALT In AI-assisted service systems, the server can choose how much processing effort to spend on each job, which we call the service depth. Deeper reasoning improves output quality but occupies the server longer and increases congestion, and the realized processing time remains random because AI models are probabilistic and tasks vary in complexity. We study the joint design of service depth and priority in a single-server queue whose customers differ in delay sensitivity, with the goal of maximizing social welfare. For each customer type, the decision maker chooses a priority level and a service depth, and service times are exponential with mean equal to the chosen depth. With two customer types and linear service values, we characterize the centralized optimum. Counterintuitively, it prioritizes the patient type and gives it a smaller service depth when patient customers are sufficiently prevalent. When delay sensitivity is private, however, incentive compatibility requires the impatient

ALT A common measure of the quality of a voting rule is the social welfare of the alternatives it elects. Prior work shows that, when voter utilities are drawn from a neutral distribution, expected utilitarian welfare is maximized by a positional scoring rule. We extend this approach to the power mean family of welfare functions, which includes utilitarian, Nash, and egalitarian welfare as special cases. We show that, across the power mean family, a deterministic positional scoring rule (PSR) is asymptotically optimal for expected social welfare among all social choice functions and we characterize this rule for a broad class of utility distributions. We further show that, among randomized PSRs, plurality uniquely maximizes expected social welfare for all power means. Experimentally, we find that optimal score vectors often yield substantially higher welfare than canonical score vectors. On highly structured utility distributions, optimal score vectors take on novel shapes unlike existing

ALT We study optimal intervention design problems aimed at minimizing the aggregate volatility in network systems. We consider linear network equilibrium models arising in network games, production networks, and opinion dynamics, where exogenous shocks hitting a few nodes can propagate through the network and cause detrimental systemic effects. Focusing on idiosyncratic shocks, we first identify a general network centrality measure that determines the amplification factor of the variance of each node's shock to the aggregate system volatility, and show that, in relevant special cases, it reduces to Katz-Bonacich, cycle, and concentration centralities. We then consider a system planner who can attenuate the shocks on the nodes, subject to a budget constraint, so as to minimize the aggregate volatility. We solve this problem analytically and show that its solution has a water-filling-type structure: for low budget, the intervention is concentrated on the node(s) maximizing a quantity ωᵢ that

ALT We study capacity modification in the Hospitals/Residents problem with Couples, in which hospital capacities and a stable matching are jointly determined. Exact and Cutoff integer programming formulations are developed for the resulting problem. We assume that, for each couple, either both members are matched or neither is. For arbitrary strict preferences, every instance admits a stable matching after changing each hospital capacity by at most two. Total capacity increases by at most one, and this bound is tight. Under sub-responsive and sub-complete couple preferences, a stable matching exists after adding at most one position to each hospital. The total number of additions is at most the number of couples, and this bound is also tight. Computational experiments show that Exact formulations are modestly faster at fixed capacities, whereas Cutoff formulations perform substantially better in the minimum repair experiments and attain higher completion rates in markets with up to 30,000

ALT Designing optimal auctions for allocating public infrastructure-such as airport slots and energy resources-is challenging due to interdependent resources and complex side-constraints. While the Vickrey-Clarke-Groves (VCG) auction guarantees maximum welfare, it cannot maximize revenue or accommodate the multi-objective trade-offs inherent in public infrastructure systems. We propose a differentiable, constraint-aware framework for combinatorial auction design that enables end-to-end learning of fractionally feasible, approximately strategy-proof mechanisms. Our primary contribution is a combinatorial constraint enforcement technique that ensures fractional feasibility by construction, bypassing the need for penalty-based approximations. We introduce CAGraph, a novel graph-based architecture designed to capture dependencies between items and bidders, alongside CANet and CAFormer as deep learning baselines, for combinatorial settings. We also provide a Matching Pursuit-inspired decomposit

ALT It is well-known that under nominal communication, where agents are able to share information with one another, game-theoretic methods provide system-level performance guarantees in multiagent cyber-physical human systems such as distributed resource allocation. However, approaches that depend on communication are frequently not robust when communication is compromised. While randomized decision-making can prevent arbitrarily poor outcomes under compromised communication, these performance guarantees often do not improve when communication abilities are restored. Thus, it remains unclear whether a single approach can perform well under nominal communication and remain robust under compromised communication. In this paper, we study whether a system operator can inform agents about how much they should randomize their choice when selecting actions in order to balance performance across both settings. We show that for any scenario (e.g., a multiagent resource allocation instance), there e

ALT We study an intermediary that buys nonperishing items from arriving sellers and sells them to arriving buyers, subject to limited storage. Sellers and buyers arrive according to independent Poisson processes. The intermediary pays and charges the same fixed item prices, aiming to maximize long-run gains from trade: buyer value minus seller cost. Our benchmark may choose allocations directly, has unlimited storage, and must purchase each unit before allocating it. Its optimal long-run gain rate equals the value of a linear program of average purchase and allocation rates, with or without knowledge of future arrivals. For buyers whose bundle values are maxima of nonnegative additive valuations (XOS), we compute static common prices that guarantee half of this benchmark for arbitrary finite item capacities, even one storage slot per item, regardless of how ties are resolved without using future arrivals. The prices are computable in polynomial time using demand and supporting-value querie

ALT We study task assignment under adverse selection and moral hazard. In the single-task setting, agents privately know their types, which determine their success probabilities and effort costs. Based on the agents' reported types, the principal selects an agent to perform the task and offers a success-contingent payment. Although optimal Bayesian contract design is generally computationally intractable and Myerson's characterization does not directly extend to settings with hidden actions and multidimensional private information, we show that the single-task problem admits a simple Myerson-style characterization. Our key insight is that incentive constraints depend only on the ratio between effort cost and success probability. We characterize an optimal mechanism and show that it can be computed in polynomial time. We also establish a tight Θ(1/(NK)) worst-case bound on the ratio between the optimal profit and the full-information benchmark, where N is the number of agents and K is the n

ALT Generative AI assistants are becoming an advertising medium, embedding sponsored content in their answers. This setting departs from classical position auctions in two ways: an ad's click-through rate depends on the passage that hosts it, and because users stop at their first click, earlier ads take clicks from later ones. This competition for clicks makes truthfulness delicate: a higher bid can reshape the allocation and put a competitor ahead of the bidder, reducing the bidder's clicks. Existing mechanisms either attain a constant fraction of the optimal welfare (advertisers' total click value) but are not known to be truthful, or are truthful but their welfare guarantee degrades as the number of passages grows. We achieve both even when the answer and its editorial order are fixed before bidding. Assuming each ad's click-through rate when reached is known and unaffected by omitting other ads, we give a computationally efficient mechanism that is truthful in expectation and attains a

ALT We propose a market-making game played among N ≥ 2 strategic market makers and a single non-strategic representative trader. In a continuous quote space, standard finite-game arguments do not apply, while non-convex and discontinuous payoffs rule out classical continuous existence results and complicate learning. Nonetheless, we characterize pure-strategy Nash equilibria (PSNEs) and show that at least one PSNE always exists under minimal assumptions on the underlying asset value distribution, and that the equilibrium bid-ask spread widens strictly with asset value volatility. To obtain a tractable learning framework, we discretize prices and, under an additional regularity condition, show that the time-averaged play of no-internal-regret learners approaches the continuous Nash price envelope as the tick size vanishes. Finally, we empirically validate our theoretical results through numerical simulations.

ALT We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although th

ALT Iterative combinatorial auctions are used in spectrum allocation, transportation, and industrial procurement, but rounds are costly. We introduce FastCombo, a deep reinforcement learning approach to sequential price discovery. Bayesian pricing has sharply reduced auction rounds even against subgradient benchmarks tuned with hindsight for each instance, but relies on a one-step objective and repeated online inference and optimization. We prove that greedily maximizing immediate clearing probability can require arbitrarily more rounds in expectation than an informative policy, even with the true valuation distribution known. FastCombo learns price policies offline, assigning credit to queries for the future decisions they enable and producing each online price update with a single neural-network forward pass. We formulate the objective of minimizing expected rounds to clearing in single-minded auctions as a partially observable Markov decision process and train a recurrent bidder-item gr

ALT Transactions differ in how their value changes with execution time and relative position. Ethereum's EIP-1559 lets them compete through fee fields, but a fee bid gives no enforceable claim to an earlier position in the block, and no way to express willingness to accept a later one. Its base fee is a hard admission floor. We introduce temporal liquidity markets (TLM), a framework for crossing complementary temporal requirements: transactions seeking early-region execution (consumers) can fund transactions that opt into exclusion from that region (providers). Selected consumers complete within the early region and are ordered among themselves by authorization density, both validator-checked. In our block-local EIP-1559 extension, providers may be admitted below the base-fee floor. Under TLM regulation, funding-conditioned and capacity-capped provider gas is excluded from the ordinary EIP-1559 controller input. Counting it there instead raises the base fee and displaces ordinary demand at

ALT We give a bounded envy-free cake-cutting protocol for any number n of agents in the Robertson–Webb model, with a short, self-contained, and elementary correctness proof. The protocol uses 2ᴼ⁽ⁿˡᵒᵍⁿ) queries. Most ingredients are already known and well understood in the fair division literature; our main contribution is a simpler organization of these ideas into a protocol whose complete description and proof fit in a few pages.

ALT We give an algorithm for computing an \eps-approximate fixed point of any d-dimensional nonexpansion with respect to the ℓ∞ norm in time log(1/\eps){ᴼ⁽ˡᵒᵍ²ᵈ)}. At its core, our method uses a boosting argument to geometrically shrink a search region. Among other consequences, our algorithm implies that simple stochastic games can be solved in quasipolynomial time.