Papers

Large language models access knowledge inconsistently across languages, but to what extent do they differ in their skill sets when interacting with different languages? This work quantifies cross-lingual skill inconsistency orthogonally from knowledge and general benchmark performance. We do this via multilingual self-play: two instances of the same model compete in a text-based game, each interacting through a different language interface. Since the model, opponent, rules, state space, and available actions remain fixed, this setting isolates the effect of language on the model's realized behavior. We build a multilingual extension to TextArena and evaluate three open-weight models across eight languages and six games covering spatial reasoning, imperfect information, resource allocation, and repeated interaction. We find that the same model can exhibit markedly different playing strength across languages, with systematic variation in win–loss margins, invalid actions, and strategic tendencies. Detailed analyses reveal language-specific failures in spatial reasoning, card-conditioned decisions, and optimal move selection. In some settings, changing only the intermediate reasoning language recovers much of the lost performance, suggesting that language can affect different stages of the decision process. These results show that skill discrepancies are a measurable major roadblock in the development of truly multilingual models. Better understanding these discrepancies can help us design models that perform more equitably across languages.

We study the sample complexity of learning near-optimal bilateral trade mechanisms. Unlike previous work on learning simple or fixed-price bilateral-trade mechanisms, we focus on mechanisms satisfying Bayesian incentive compatibility (BIC), interim individual rationality (IIR), and ex-ante weak budget balance (WBB). In other words, our target is to design a sample-based mechanism that achieves the second-best gains-from-trade benchmark. We give matching or nearly matching upper and lower bounds in three regimes. For regular product distributions on $[0,h]^2$, additive $\varepsilon$-approximation has sample complexity $\widetilde{\Theta}(h^2/\varepsilon^2)$. For multiplicative $(1-\alpha)$-approximation under the same assumptions, we find that the sample complexity is $\widetilde{\Theta}(h/(\mathrm{SB}(D)\alpha^2))$, which is benchmark-sensitive with unavoidable dependence on the second-best gains from trade $\mathrm{SB}(D)$. We also investigate unbounded distributions under a monotone hazard rate (MHR) assumption. The sample complexity depends on the ratio $\chi_\mu(D)=\mu(D)/\mathrm{SB}(D)$, where $\mu(D)$ is the sum of the buyer's expected value and the seller's expected cost.

In signaling games where a sender and a receiver have misaligned criteria, equilibrium behavior may lead to fully revealing, quantized, or randomized policies. Notably, the first arises in statistical decision theory and classical communication theoretic problems involving a fully aligned sensor and receiver, the second arises in Nash theoretic simultaneous signaling games, and the last may appear in Stackelberg type (leader-follower) Bayesian signaling games. In this paper, we investigate the Bayesian persuasion problem involving a receiver that tries to estimate the source. We show that for certain payoff structures, the equilibrium solution is such that a source observation is mapped to distinct messages with nonzero probabilities. More specifically, we completely characterize conditions under which the sender requires randomization for the Bayesian persuasion problem involving general sources with finite cardinality. In particular, regardless of whether the equilibrium solution under a deterministic policy restriction is fully revealing, quantized or noninformative, there exists a randomized sender policy that improves the sender's payoff under certain conditions characterized in the paper. Moreover, we provide an algorithmic procedure to obtain the Bayesian persuasion solution, where the algorithm compares the payoffs with finitely many posterior probability combinations. We also consider fully aligned and completely misaligned payoff structures, where the solutions respectively involve a fully revealing sender and a noninformative sender. Then, we unify these results by proving that if the sender's expected payoff with respect to posterior distributions is continuous, then the equilibrium solution involves either a fully revealing sender or a noninformative sender.

We settle the minimax-optimal alternating regret, a regret notion motivated by alternating learning dynamics in games, for both online linear optimization (OLO) and online convex optimization (OCO). For OLO over the probability simplex $\Delta_d$, we give an algorithm with $O(\log d)$ alternating regret that remains a constant for any time horizon $T$, and a matching lower bound. Our constant regret bound significantly improves previous results with $O(\log ^{2/3}d \cdot T^{1/3})$ regret [Cevher, Cutkosky, Kavis, Piliouras, Skoulakis, Viano, NeurIPS 2023, Hait, Li, Luo, Zhang, COLT 2025]. As a result, we obtain alternating learning dynamics with $O(\log d /T)$ convergence to Nash equilibria in two-player zero-sum games and $O(\log d /T)$ convergence to coarse correlated equilibria in two-player general-sum games. This is the first uncoupled learning dynamics with $O(1/T)$ convergence to CCE in two-player general-sum games, while all prior works suffer additional $\log T$ factors. For general OCO over a $d$-dimensional compact convex set, we give an algorithm with $O(d\log (1+T/d))$ alternating regret, improving the previous best of $\widetilde{O}(d^{2/3}T^{1/3})$. We also prove a matching lower bound of $\Omega(d\log (1+T/d))$, showing that the $\Omega(\log T)$ factor is unavoidable.

We consider fair allocation of indivisible goods in a setting in which agents have subjective valuation functions over the set of goods, and in addition, goods may be sold at given market prices. In this setting, a fair allocation involves {deciding which goods to sell, how to allocate the unsold goods, and how to divide the money received from the sold goods.} We adapt to this setting the definitions of share-based fairness notions, such as the maximin share (MMS) and the truncated proportional share (TPS), and comparison-based fairness notions such as EF1 and EFX (which we adapt to SEF1 and SEFX). We show the following results when the utility of each agent is additive both over goods and over money. With two agents, there are allocations that are simultaneously MMS and SEFX. With three agents, there are instances in which no allocation gives every agent more than $\frac{11}{12}$-MMS. With any number of agents, there are $\frac{2}{3}$-MMS allocations. There also are allocations that are simultaneously SEFX and $\frac{n}{2n-1}$-TPS. This latter ratio is best possible, even without the SEFX requirement.

Recent studies on social rankings in coalitional settings have introduced methods that rank individuals by lexicographically comparing vectors of their occurrences across coalitions ordered according to their strength. In this work, we focus on two such solutions: the lexicographical excellence (lex-cel) solution, which disregards coalition size, and the L^(1) solution, which additionally prioritizes smaller coalitions through a double lexicographic comparison. We investigate the combinatorial connections between these two solutions on monotonic coalitional rankings, where equivalence classes are compactly represented through sets of minimal (with respect to set inclusion) coalitions. After introducing general formulas for computing the lex-cel and L^(1) parameter vectors from these minimal coalitions, we also present worst-case running time results. Finally, to further explore the behavior of the two solutions through simulations designed to assess the distance of the rankings they produce, we show that the monotonicity assumption does not lead to actual redundancy in the rankings produced by the two solutions.

Maximizing Nash welfare over indivisible goods is a central problem in resource allocation. For additive valuations, the best-known approximation factor is roughly $e^{-1/e}\approx0.692$, and the problem is APX-hard. We study Nash welfare maximization under lexicographic valuations, where every good is worth more than the total value of all lower-ranked goods. This large-gap structure makes preferences almost ordinal, which might suggest that the problem becomes easy. We show, however, that the picture is more nuanced: although lexicographic valuations enable stronger algorithmic guarantees, they retain significant computational hardness. Our first main result is a $(1/\sqrt{2}-\epsilon)\approx(0.707-\epsilon)$-approximation algorithm for weighted Nash welfare under lexicographic valuations, improving over the inherited guarantee of roughly $e^{-1/e}$. The algorithm rounds the configuration LP for Nash welfare, for which we show a matching integrality gap of $\sqrt{2}$. Our second main contribution is an exact algorithmic polynomial time framework for ordered lexicographic instances and doubling lexicographic instances. We introduce a domination-based branch-and-prune method for which we prove a mutual-exclusion property between sibling subtrees and use a matrix-based leaf-counting argument to bound the pruned recursion tree by a polynomial when the number of agents is constant. Finally, we show that large gaps do not eliminate hardness, as Nash welfare maximization is NP-hard even for ordered lexicographic valuations, and it is NP-hard to obtain a $0.9996$-approximation even for doubling lexicographic valuations. Thus, lexicographic valuations make Nash welfare maximization easier, but not easy: they admit tighter approximation and exact algorithms in important cases, yet still require intricate techniques and preserve some of the hardness of the general additive setting.

We study multilevel fair resource allocation with tree-structured hierarchical relations among agents. At each level, the problem can be viewed locally as allocating an agent's bundle to its children, the overall allocation being a trace of this process iterated down to the leaves. Assuming that internal nodes' utilities are the utilitarian welfare of their children, and the leaves have classical additive utilities over items, we first propose multilevel adaptations of usual envy-based fairness notions (e.g., WEF1). We present three adaptations and show that the choice among them is not neutral. We prove that, under identical preferences, the three adapted envy-based notions coincide, and that the Multilevel extension of Weighted Round Robin (Chakraborty et al., 2021) (MWRR) guarantees them. We then show that under general preferences, MWRR may guarantee some notions while failing others. Finally, through experiments, we show that MWRR may still perform well even for adaptations it does not formally guarantee.

Reversible computing is a novel paradigm that has recently emerged and extends traditional forwards-only computation with the capability to execute in the reverse direction, making it possible for computation to run backwards as well as forwards. Event structures are a foundational model in concurrency theory, providing a way to understand computational processes by describing the events that occur and the relationships between them. In the literature, two structurally different approaches to associating transition system semantics with event structure models have been distinguished. One approach is based on configurations, which are sets of already executed events. The other approach is based on model residuals, which are not yet executed fragments of the model. Configuration-based transition systems appear to be primarily used for semantic representations. Residual-based transition systems are actively applied to demonstrate the consistency between operational and denotational semantics of concurrent process calculi, as well as to visualize the dynamics of models. The present paper focuses on bundle event structures with causal reversibility, which are used in the study of reversible extensions of CCS- and π-like systems. Mappings from the reversible event structure model to the two transition system semantics are developed, which made it possible to prove the isomorphism of the semantics. A category-theoretic characterization of the mappings is provided.

In truthful interval covering, each agent has a private interval of unit length, and the goal is to decide where to place a public unit interval so as to minimize the total uncovered length while incentivizing the agents to be truthful. Previous work proposed a universally strategyproof lottery over order-statistic mechanisms with approximation ratio at most $5/3$, and established a lower bound of $3/2-o(1)$ for this class of mechanisms. We close this gap by characterizing the approximation ratio of every report-independent lottery over order-statistics. In particular, we show that, for every $n\ge2$, the optimal approximation ratio for this class is $\frac32-\frac{1}{2\lfloor n/2\rfloor}$. Beyond rank lotteries, we show that every universally strategyproof randomized mechanism has approximation ratio at least $9/8$.

This paper studies a class of multi-cluster aggregative games characterized by the coexistence of cooperation and competition, where each agent's cost function depends on its own strategy and the aggregate of all agents' strategies. To address the Nash equilibrium seeking problem for such games in the non-Euclidean setting, a distributed mirror descent algorithm with gradient extrapolation is proposed over time-varying intra-cluster and inter-cluster networks. The mirror descent framework employs a general Bregman divergence as the distance measure, providing greater flexibility than Euclidean-based methods, while gradient extrapolation exploits historical gradient information to improve convergence performance. Under the restricted strong monotonicity characterized by the Bregman divergence, the convergence of the proposed algorithm is established, and it achieves the $\mathcal{O}(1/k)$ convergence rate with the appropriately selected step-size and parameters. Finally, the effectiveness of the proposed algorithm is verified by an example on the demand response of energy systems.

In a deliberative poll, once submissions outnumber what anyone will read, some mechanism chooses which arguments each voter sees, acquiring much of the decision; practice delegates it to opaque learned rankers, so a voter cannot recompute or contest the exposure that shaped their vote. We ask whether it can be a published rule over publicly recomputable evidence with parameters held by the voter, treating legibility as an admissibility condition on usable mechanisms, not an objective traded against accuracy. We formalise a poll over bipolar justification sets, judging a slate by reason coverage, the order it arrives in, and captured endorsement mass; we give seven checkable criteria for a civic recommender and a rule meeting them: a one-hop reversed endorsement flow parameterised by a relation-weight function. An agentic simulator records every slate at every vote, over about 17,000 seed-paired runs. Served slates fall 0.035 short of a label-reading ceiling upper-bounding every selection procedure, opaque ones included: any unconstrained ranker's advantage is bounded and small. On coverage alone, with non-degenerate authoring, the rule is indistinguishable from a random slate, a null due to an order-blind, charity-blind instrument; on the other two it leads at every prefix by a margin widening with adversarial pressure and dominates on mass by a factor of 3.3. Once a realistic fraction of submissions carries no reasons, the coverage margin returns and grows. Label-homogeneous flooding collapses completeness from 0.81 to 0.34 under a flat weight policy, only to 0.44 under author-count normalisation, making the weight function a security control worth 10% of completeness. The choice between ranking arms is a position on a coverage-versus-mass frontier, not a fact, the kind of choice only a legible rule can hand to the person it affects. It maps onto an open-source peer-to-peer platform.

Apportionment distributes a fixed number of legislative seats among political parties in proportion to their vote shares. Randomization can satisfy quota in every realization and exact proportionality in expectation, but these requirements determine only the parties' marginal seat distributions. We study threshold monotonicity, which requires that when every standard quota inside a coalition weakly increases and every standard quota outside it weakly decreases, the coalition's new seat total stochastically dominates its old one. We prove that Sampford apportionment satisfies threshold monotonicity, resolving the threshold-monotonicity conjecture of Correa et al. (2024). Complementing this result, we prove that no quota-respecting, ex-ante proportional method satisfies pairwise threshold monotonicity even for disjoint coalitions when there are at least seven parties. This impossibility applies whether or not the method has full support.

We introduce multi-winner voting with argumentative ballots (MVArg) and investigate theoretical properties. As our conceptual contribution, we generalise approval ballots to argumentative ballots, thereby allowing voters to express defeasible preferences over candidates. We accordingly generalise voter cohesion and justified representation axioms JR, PJR and EJR. As our theoretical contribution, we establish several key results. First, MVArg is strictly more expressive than multi-winner voting with approval ballots (MV). Second, our notions of cohesion and justified representation are conservative generalisations of their counterparts in MV. Third, the MVArg counterpart of JR can always be satisfied, whereas the counterparts of PJR and EJR cannot always be. Fourth, although verifying whether a winner set satisfies the MVArg counterpart of JR is already coNP-hard, such a winner set can be constructed in polynomial time. All definitions, propositions, auxiliary lemmas and theorems have been formalised and mechanically checked in Lean 4.

Symbolic protocol verification models the network attacker as a Dolev–Yao (DY) intruder, which does everything its knowledge permits, whether or not it serves any purpose; real adversaries instead maximise utility, attacking only when the payoff is positive. We introduce a rational Dolev–Yao attacker, a DY intruder whose actions carry costs and whose security-violating goals carry rewards, and call a protocol rationally secure when no intruder strategy achieves a violation with strictly positive utility, expressed in a weighted fragment of ATL (WATL). We prove this decidable for a bounded rational DY intruder over a finite cost-annotated concurrent game structure, characterise its complexity, and show it strictly refines DY security: some protocols are DY-insecure yet rationally secure, separated by a computable threshold. We illustrate the framework on two contrasting use-cases: an authenticated payment under session uncertainty, where a rational intruder must strategise across indistinguishable sessions and its imperfect information strictly raises the attack cost a designer must price against; and ThreeBallot, a cryptography-free scheme where we pinpoint the bribe-to-benefit ratio below which no rational coercer attacks.

Standard solution concepts for stochastic games, such as Markov perfect equilibrium and Markov coarse correlated equilibrium, are computationally difficult, and thus, standard decentralized reinforcement-learning algorithms should not generally be expected to converge to them. In this paper, we study the equilibrium generated by such algorithms. In particular, we introduce a new solution concept for stochastic games, Markov Bayes coarse correlated equilibrium (MBCCE), defined as a distribution over states and stationary policy profiles such that, after observing the state but before observing her recommended action, no player can gain by choosing a different current action, with the sampled policy profile governing play thereafter. We discuss the parallels between MBCCE and coarse correlated equilibrium (CCE) in finite normal-form games and show that MBCCE retains several of its key properties. We then introduce a corresponding regret notion, adaptive Markov coarse regret (AMCR), and show that vanishing AMCR implies that every accumulation point of the empirical distribution of realized states and policy profiles is an MBCCE. Crucially, we show that achieving AMCR reduces to two standard learning tasks: minimizing external regret at each state and accurately evaluating the current joint policy. We then prove that under mild conditions these properties hold for two natural RL algorithmic designs: a decentralized asynchronous actor–critic algorithm through a new two-timescale stochastic-approximation analysis, and a standard episodic multi-agent projected policy-gradient method. Hence, both algorithms generate approximate MBCCEs, and we establish explicit finite-time convergence rates for both.

We design and analyze randomized strategyproof mechanisms for multi-facility location under the utilitarian social-cost objective, the sum of the agents' distances to their nearest facilities. For two facilities, the Pairwise-Distance mechanism locates facilities at a pair of reported locations sampled with probability proportional to their distance. It is strategyproof on Ptolemaic spaces, including Euclidean and Hilbert spaces as special cases, and has an approximation ratio of \(4\). The resulting Hybrid-Distance mechanism is a fixed-probability mixture: it selects the classical Proportional mechanism [Lu et al., EC'10] with probability \(\lambda^*=\frac{5+4\sqrt3}{23}\) and Pairwise-Distance with probability $1-\lambda^*$. It is strategyproof on Ptolemaic spaces and has a tight approximation ratio of \(\frac{74+4\sqrt3}{23}\approx3.5186\), breaking the long-standing factor-\(4\) benchmark of [Lu et al., EC'10]. We complement the two-facility results by studying more facilities. First, for \(n\) agents and \(k=n-1\) facilities, we introduce the Inverse-Square mechanism, which omits one report with probability proportional to the inverse square of its nearest-neighbor distance and locates facilities at all remaining reports. It is strategyproof on any metric space and has an approximation ratio of \(\Theta(\sqrt{n})\), improving the previous best-known ratio of \(\frac{n}{2}\) [Escoffier et al., ADT'11]. Second, for $k$ facilities on the line, we introduce the Gap-Product mechanism, which locates facilities at \(k\) reports and weights each set by the product of the gaps between consecutive selected reports. When \(k=3\), it is strategyproof and has a \(6\)-approximation, replacing the previous \(n\)-dependent guarantee [Fotakis and Tzamos, EC'13] by a constant, whereas it is not strategyproof for any \(k\ge4\).

Consider the problem of designing a revenue-optimal auction mechanism when two heterogeneous items are sold to a single buyer having independent valuations over the items. The distributions of the buyer's valuation for the items are assumed to have densities that are positive, nondecreasing, and continuously differentiable on their support sets $[c_i,c_i+b_i]$ in the positive axis. I prove that the optimal mechanism is deterministic if at least one of the minimum valuations (i.e., either $c_1$ or $c_2$) is sufficiently high. I provide a method to calculate the threshold of $(c_1,c_2)$ beyond which the optimal mechanism is deterministic. I also provide a sufficient condition on the distributions of buyer's valuations for which the individual sale mechanism is optimal. I show that when $c_1$ is low and $c_2$ is high, it is optimal for the seller to sell item $2$ at the minimum valuation $c_2$, thus effectively reducing the problem to finding the optimal mechanism in the one-dimensional setting only for item $1$. I conjecture with promising preliminary results that this result can be extended to the three-item setting. Specifically, I conjecture that when $c_1$ and $c_2$ are low but $c_3$ is high, it is optimal for the seller to sell item $3$ at the minimum valuation $c_3$, thus effectively reducing the problem to finding the optimal mechanism in the two-dimensional setting for items $1$ and $2$.

The rapid growth of Low Earth Orbit satellite constellations has created increasing demand for efficient and scalable downlink services. Ground Station as a Service (GSaaS) provides an on-demand access model for satellite operators, but commercial GSaaS providers must schedule limited ground-station bandwidth among multiple satellites with heterogeneous data demands, overlapping visibility windows, strict deadlines, and strategic bidding behaviors. This paper studies GSaaS resource scheduling from a ground-station-centric perspective, where the provider jointly determines task admission, ground-station assignment, bandwidth allocation, and payments. Under satellite orbital dynamics, bandwidth constraints, and downlink task deadlines, maximizing the provider's revenue is NP-hard. To address this challenge, we propose STAR-GS, a truthful and feasibility-aware scheduling mechanism that combines bid-aware admission control, best-fit ground-station assignment, Earliest Deadline First (EDF)-based bandwidth scheduling, and critical-payment pricing. By integrating auction theory with schedulability analysis, STAR-GS incentivizes task owners to truthfully report their private valuations while ensuring that admitted tasks can be feasibly completed before their deadlines. Simulations using Ansys Systems Tool Kit (STK) show that STAR-GS consistently achieves higher revenue than heuristic baselines, obtains near-MILP performance with substantially lower runtime, and scales smoothly to workloads containing up to 900 tasks.

The house allocation problem is a classical one-sided matching problem that concerns the assignment of a set of $m$ houses to $n$ agents according to their preferences, where each agent is assigned exactly one house. Among the various objectives studied in this setting, envy-freeness is one of the most widely adopted fairness criteria. As envy-free house allocations do not always exist, we address this challenge by introducing subsidies and aim to compute allocations that achieve envy-freeness with minimum total subsidy. For binary instances, we show that a total subsidy of at most $(n-1)$ suffices to guarantee envy-freeness in house allocation, and this bound is tight. Building on the known NP-hardness for general utilities, we further show that computing an allocation that minimizes the total subsidy is NP-hard, even under binary utilities. However, when there are only a bounded number of types of agents with binary utilities, the problem can be solved in polynomial time. Finally, we present a polynomial time algorithm that computes the minimum subsidy required to achieve envy-freeness for two types of agents with general utilities.

Metric distortion has primarily been studied for social choice functions, which select a single winner from ordinal preferences. We extend this framework to social welfare functions, which output a ranking of $m$ candidates. We associate each voter $v$ with a monotone weight vector $\mathbf{w}_v = (w_{v1},\ldots,w_{vm})$, specifying the importance of the $i$-th position for voter $v$, and define the cost of a ranking as the position-weighted sum of their distances to the ranked candidates. This model generalizes both single-winner voting and committee selection. We consider three information regimes. First, we study the setting where the positional weight vectors are known. A natural approach recursively applies a single-winner rule with distortion $\beta$ to construct the ranking one position at a time. We show that this yields distortion at most $3\beta$ in general. This gap is not merely an artifact of the analysis: we show that no analysis based solely on per-round guarantees can certify a bound better than $2\beta$. By exploiting structural properties specific to Fractional Veto of Kizilkaya and Kempe, we show that its recursive extension achieves the optimal distortion of 3. Second, when all voters share the same unknown weight vector, recursively applying any social choice function with distortion $\beta$ achieves distortion at most $1+(\beta-1)\text{range}(\mathbf{w})$, where $\text{range}(\mathbf{w})=(w_1-w_m)/w_1$ denotes the normalized range of the common weight vector $\mathbf{w}$. Finally, we study unknown heterogeneous weights. Without further assumptions, every rule has unbounded distortion. We therefore consider two natural normalizations: unit-sum, where each voter distributes one unit of value across the ranking, and unit-top, where every voter assigns unit value to the first position. Under both models, we show that the optimal distortion is $\Theta(m)$.

Calibration requires probabilistic reports to be conditionally unbiased and reliably interpretable as probabilities. A calibration measure assigns numerical error to miscalibrated reports. Haghtalab et al. (2024) proposed an approximately truthful calibration measure for online prediction, leaving open whether exact truthfulness is compatible with completeness and soundness. We resolve this question negatively for sequential binary prediction: exact truthfulness is incompatible with completeness and soundness, even for independent outcomes. We then show that this impossibility is specific to exact truthfulness. We give two general reductions from a base calibration measure, producing additively and multiplicatively approximately truthful calibration measures, respectively. Applying the multiplicative reduction, for every $0 < \varepsilon < 1$ we construct a sound and complete calibration measure that is $(1+\exp(-T^{(1-\varepsilon)/2}/2))$-multiplicatively truthful. This improves the approximate-truthfulness guarantee of Haghtalab et al. (2024).

We study security games on attack graphs, where an adaptive attacker seeks to reach a target by sequentially attempting stochastic controls along the current attack frontier, while a defender allocates limited resources across controls to delay compromise. The attacker may choose among exponentially many attack routes and freely pivot between them as successes and failures are observed, yielding an exponentially large space of contingent attack policies. For any fixed defender allocation, we show that an optimal attacker policy on a two-terminal series-parallel attack graph is an index policy: at each step, the attacker selects an available control with the largest value of an extension of the classical Gittins index. The indices and the resulting attacker best response can be computed in polynomial time, without explicitly enumerating attack paths or contingent policies. To the best of our knowledge, this is the first optimal index characterization for adaptive attackers in security games on general series-parallel attack graphs. We further develop efficient algorithms for computing the attacker's exact utility and an exact defender subgradient, enabling deterministic first-order optimization of defensive resource allocations without sampling attack trajectories. Our framework strictly generalizes prior approaches restricted to parallel chains and out-trees, while exploiting the compositional structure of series-parallel graphs to support interpretable attacker policies and parallel computation across independent subgraphs. Experiments demonstrate that the resulting methods scale substantially better than naive explicit-state approaches while producing effective defensive allocations.

We give a randomized voting rule with expected metric distortion $5/2$, improving the previous best upper bound of $2.753$. Our rule is the equal mixture of a Maximal Lottery [CRWW24] and a lottery obtained by averaging scores in Simultaneous Plurality Veto [KK23] over time. We further show that $5/2$ is optimal within a broader family that allows profile-dependent mixing weights and arbitrary, possibly adaptive, weights over the veto process.

As an extension of existing Bayesian persuasion framework with inadequate message mechanism, we study direct recommendation when a sender is bound by an installed information policy only with probability $\rho$, the realization of binding is hidden, and the receiver does not observe the persistent structural environment. The receiver first sees a payoff-neutral, nonmanipulable calibration sample and then faces a fresh, non-certified deployment interaction. In common, the calibration law identifies only the receiver-facing reduced form, not the latent binding and discretionary kernels. We characterize type-wise $\rho$-implementability, construct the receiver's posterior over the full deployment node, and prove a static direct-following implementation theorem. After every calibration history that passes a posterior-predictive obedience test, the deployment assessment is an exact perfect Bayesian equilibrium: Bayes consistency, receiver sequential rationality, sender sequential rationality, and off-path completion are all verified. Under finite-type separation, common recommendation support, and a positive obedience margin, the test activates such an equilibrium with high probability. Our results keep statistical failure probability distinct from equilibrium approximation. Finally, we embed the original robust value frontier, support-wise linear-programming algorithm, and binary-action fractional-knapsack specialization into this implementation framework

We study temporal fair division of indivisible mixed manna. Items arrive over time and must be allocated irrevocably; an item may be a good for some agents, a chore for others, and neutral for the rest. We require the cumulative allocation after every round to be envy-free up to one item (TEF1). Although deciding whether a TEF1 allocation exists is NP-hard even for goods, we identify several tractable settings. First, with at most $k$ item types, an online cyclic rule guarantees EF$\lceil k/2\rceil$ after every item arrival. Thus, every instance with at most two types admits an online TEF1 allocation; moreover, when the numbers of agents and types are fixed, TEF1 existence can be decided in polynomial time. Second, under agreement after agent-specific scaling, provided that the scaling factors are known before arrivals begin, an online rule produces an allocation that is EF1 and Pareto optimal after every item arrival. Third, for a two-part arrival sequence with common rankings, we give a rule that is EF1 after every item arrival. Fourth, when the number of agents is fixed and values are bounded integers, we give an exact pseudo-polynomial algorithm for deciding TEF1 existence. Finally, for goods, every TEF1 allocation gives each agent at least $1/n$ of her maximin share after every round; this factor is tight even for identical valuations and two rounds. Deciding whether an exact temporal maximin-share allocation exists is NP-hard for both goods and chores, even with identical valuations, two agents, and two rounds.

We study randomized strategyproof mechanisms for locating multiple facilities on the real line. We introduce the Product-Gap mechanism, which selects $k$ reported locations with probability proportional to the product of the consecutive gaps between them and opens facilities at the selected locations. We prove that, for every $k\geq 2$, the mechanism achieves a tight approximation ratio of $2k$ for social cost. We then study its incentive properties and show that it is strategyproof in expectation for $k=2$ and $k=3$, but is not strategyproof for $k\geq 4$. In particular, the mechanism gives strategyproof $4$- and $6$-approximations for two and three facilities, respectively. Finally, for two facilities, we combine Product-Gap with the Proportional mechanism of Lu et al. We show that an optimized report-independent mixture is strategyproof and has a tight approximation ratio of $(74+4\sqrt{3})/23\approx 3.519$ on the line, improving upon the previous factor of $4$.

We study the classical and parameterized complexity of efficient connected allocation problems on graphs, where efficiency is measured by egalitarian and utilitarian welfare maximization. We first establish a sharp complexity dichotomy in the classical setting: both problems are NP-hard in general and remain hard even on very restricted graph classes such as paths, and consequently trees and cycles. In contrast, they are polynomial-time solvable on stars, but this tractability does not extend even to the case of two disjoint stars. Motivated by these boundaries, we move to the parameterized complexity framework, where we study the problem with respect to the number of agents. We obtain fixed-parameter tractability (FPT) on trees and, more generally, identify a robust phenomenon whereby tractability on a connected graph class extends to disjoint unions of graphs from that class. We further investigate the parameters treewidth and treedepth, showing that the utilitarian version is FPT for both, whereas the egalitarian version remains para-NP-hard even on graphs of treedepth two. Finally, we analyze the number of connected components and show that except for the collection of stars, the problems remain hard. For the collection of stars,while we obtain para-NP-hardness for the egalitarian case, the utilitarian case gives W[2]-hardness together with an XP algorithm.

As large language models evolve into decision-making agents, the ability to reason over preferences becomes fundamental to alignment, coordination, and collective intelligence. Yet, unlike standard benchmarks, real-world preference reasoning is inherently indeterminate: information may be incomplete, and valid solutions may not exist. We argue that indeterminacy, rather than correctness alone, is a central challenge for AI reasoning. We formalize this challenge along two axes, (i) epistemic indeterminacy, arising from incomplete, partial, or expressive preferences, and (ii) structural indeterminacy, arising from the non-existence of solutions under standard social choice concepts. Across a hierarchy of tasks, we show that state-of-the-art language models systematically fail to distinguish between determined and undetermined instances, exhibiting miscalibrated reasoning even in verification settings.

We introduce and study an online variant of the multi-agent contract model. In our model, agents arrive one-by-one and are active with a certain probability. Upon arrival of agent $i$, the principal offers a linear contract $\alpha_i$, specifying the fraction of the principal's reward transferred to agent $i$. Agents can either exert effort or not, incurring a cost if they do. The set of agents that exert effort determines the principal's expected reward through a reward function $f$. After all agents have arrived, the agents form a (pure) Nash equilibrium. As our main result we design an $O(1)$-competitive policy for submodular rewards, compared to the offline optimum. We also show that this result is tight in two ways. First, if we require that agents make decisions on the spot, then for submodular rewards any policy is $\Omega((\log n)/(\log \log n)^2)$-competitive. Second, for the broader class of XOS (a.k.a., fractionally subadditive) rewards, any online policy is $\Omega((\log \log n)/(\log \log \log n))$-competitive. The latter result reveals a surprising separation between submodular and XOS rewards: unlike related settings such as offline contract design and prophet inequalities, where constant-factor guarantees for submodular rewards extend to XOS rewards, the online contract setting separates the two classes.