Papers

We study the online allocation of indivisible goods among $n$ agents, where each good must be allocated immediately and irrevocably upon arrival. Against an adaptive adversary, Neoh and Teh [2026] proved that no algorithm can guarantee a positive approximation to proportionality up to one good (PROP1) that is independent of the number of goods, and the same holds for proportionality up to $k$ goods (PROP$k$) for any fixed $k$. We instead consider an oblivious adversary, which fixes the input in advance. Choo et al. [2026] showed that the uniformly random allocation returns a $\Theta(1/\log(n/\delta))$-PROP1 allocation with probability at least $1-\delta$. We improve this to $\Omega(1/\log\log(n/\delta))$; our algorithm does not take $\delta$ as input, so the same algorithm achieves this bound for every $\delta\in(0,1)$. Moreover, with the same probability, a variant of our algorithm gives every agent almost her bundle, and even without adding any good when no single good is too valuable relative to this share. In contrast, for envy-freeness up to one good (EF1), we show that, for every $\alpha\in(0,1]$, every randomized algorithm has an input on which its probability of returning an $\alpha$-EF1 allocation is at most $e^{-\Omega(n)}$. For envy-freeness up to any good (EFX), this probability is at most $1/n!$ with only $n+1$ goods, a bound that is optimal within a factor of $(n+1)/2$. For the maximin share (MMS), this probability is at most $5/6$, however small $\alpha$ is. Allowing more removals gives a positive envy-freeness guarantee: allocating each good to a uniformly random agent among those with positive values achieves, with high probability, an approximation factor arbitrarily close to one for envy-freeness up to logarithmically many goods, and logarithmically many goods are necessary for this rule.

Benchmarking and routing platforms increasingly act as intermediaries connecting large language model providers with end-users. However, providers on these platforms typically use a fixed price per token, preventing users from achieving the most competitive price for their tasks. In this work, we design a procurement platform where token prices for each task are driven by provider competition, enabling users to secure competitive pricing for guaranteed quality levels. To this end, the platform sequentially routes queries via a reverse second-price auction that incentivizes model providers to truthfully bid their best estimate of the average cost to serve a user's query. As it routes queries, the platform learns the quality offered by each provider and progressively routes queries to the most cost-competitive provider among those meeting a desired quality threshold. To validate our design, we conduct experiments with multiple LLMs from the Llama and Qwen families on popular mathematical reasoning and question-answering benchmarks. The results show that the pricing margin of the most cost-competitive provider on our platform varies significantly—from $10\%$ to $71\%$—depending on the task and quality threshold. This suggests a substantial inefficiency in the current fixed-price market, and it demonstrates that our platform may enable users to capture maximum savings whenever competitive market conditions permit.

Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

Online discussion of political and gender-related issues is often heated, and when opinions in a network draw closer, the convergence is readily taken as genuine consensus. Whether it carries a cost is a question existing methods cannot answer: coevolutionary opinion formation games measure the Price of Anarchy (PoA) of agents that update by numerical rules, while simulations with large language model (LLM) agents report only descriptive indices. We introduce the Hybrid Coevolutionary Opinion Game (H-COG), in which analytical and LLM-driven agents share one network, choose their neighbors by opinion similarity in every round, and hold stances drawn from real Reddit comments on gun control and abortion. To our knowledge, H-COG is the first framework to place Friedkin-Johnsen best-response agents and LLM agents in one coevolutionary game and to measure the social cost and PoA of LLM-driven populations. We prove that on any fixed network, given the LLM agents' opinions, the analytical agents' opinion stage has a unique equilibrium and the social optimum has a closed form, and that the convergence guarantee of Chen et al. for optimistic gradient ascent carries over to H-COG. All runs converge structurally. LLM-driven populations are less polarized yet have about five times the PoA of analytical ones; half of the gap comes from agents being pulled away from their own prior positions, a distance we prove must carry a cost whenever expressed opinions are more concentrated than intrinsic ones. Echo chambers form under every composition and grow out of the rewiring rule rather than the initial topology. Opinions in these populations draw closer largely because agents give up their own positions.

Customers often specify acceptable time intervals for receiving a service. When service on a date entails a fixed activation cost, overlapping intervals allow joint service and cost sharing. Customers may nevertheless conceal flexibility by reporting a smaller interval, affecting both operating cost and its allocation. We ask whether an operator can select a core allocation at every reported profile without making concealment profitable. We establish sharp population boundaries for preventing such coalitional reductions. When intervals may be narrowed from either end, a core-selecting rule preventing such reductions exists if and only if there are at most three customers. With four or more customers, impossibility holds even under Pareto contraction-proofness, which excludes deviations making every contracting customer weakly better off and at least one strictly better off. The impossibility persists when each contracting customer conceals only an arbitrarily small fraction of her feasible interval. The boundaries change when either the earliest or latest acceptable date of every customer is verifiable. With common verified dates, equal sharing is core-selecting and prevents such reductions for any population size. When verified dates may differ, the boundary rises to five: such a rule exists for up to five customers, whereas with six or more no core-selecting rule prevents the contracting customers from reducing their combined payment. Under Pareto contraction-proofness, however, core selection is possible for every population size on either one-sided domain. Finally, the relaxations needed for approximate core selection and coalitional contraction-proofness must grow with population size.

The design of credible auctions—mechanisms where a revenue-maximizing auctioneer has no incentive to deviate from the protocol—faces a fundamental cryptographic barrier when the auctioneer controls shill bidders. While a natural approach is to use Secure Multi-Party Computation (MPC) to remove the trusted auctioneer, the impossibility of fair coin flipping of Cleve (1986) implies that monolithic MPC protocols grant the auctioneer a "free option": they can learn the auction's outcome and unilaterally abort if the revenue is unsatisfactory. Cryptographic commitments with ex-ante penalties mitigate this abort asymmetry, but no finite penalty suffices for heavy-tailed distributions. We circumvent this barrier by introducing the MPC Decomposition Principle. Rather than encrypting the entire mechanism, we use MPC strictly as an information-restriction tool. We isolate the winner determination problem into a minimal MPC gadget that computes and reveals the winner's identity but no payment information. This qualitative restriction mathematically bounds the information leaked upon an abort. By combining this gadget with sequential revelation and finite economic penalties, we design the Sequential Revelation Auction (SRA). We prove that bounding the information leakage strictly bounds the value of the free option, showing that a penalty of $k \geq \sum_{i=1}^n Rev(F_i)$ is sufficient for credibility, and tight: for equal-revenue distributions, every smaller penalty admits a profitable deviation. Using constant-round MPC, the SRA resolves an open question of Akbarpour and Li (2020) and Ferreira and Weinberg (2020) by providing a constant-round, incentive-compatible, revenue-optimal credible auction for all product distributions with vanishing revenue tails

Citizens' assemblies are deliberative bodies intended to form a microcosm of the population. Organizers rely on quota-based stratification and must decide which attributes define resemblance to the public. Yet meeting every quota can still leave a dimension citizens value unrepresented. We study this attribute-selection problem in general-purpose and climate-focused assemblies through randomized conjoint experiments. We find that demographic attributes matter for perceived representation, but political alignment and context-specific attributes such as climate concern exert a stronger influence. When both are shown in a climate-focused setting, each remains influential, with political alignment having the larger estimated marginal effect. We also examine the omission of a relevant stratification attribute. Panels stratified on demographics, even with political alignment included, match the observed pool's climate-concern distribution no better than uniform random samples. These results suggest that representation on a relevant topic-specific attribute cannot always be recovered through correlated demographic or political quotas, and may therefore require explicit stratification. Finally, we ask whether representation preferences can be learned from the observed profiles. We compare predictive models, from simple, interpretable matching rules to a learned metric and a respondent-conditioned utility model. Both learned models predict choices for respondents excluded from training with substantial accuracy, revealing generalizable structure without fully capturing these judgments. Together, these findings guide attribute selection in citizens' assemblies: designers should consider political and topic-specific dimensions alongside demographics, avoid assuming correlated proxies protect omitted dimensions, and use predictive models to diagnose how profiles shape representation choices.

We present JEV-Star, a StarCraft II controller that defeats the strongest non-cheating built-in AI, Lv7, by combining fast JEV action selection with persistent GPT-6 planning. The combined system wins four full games at Lv5–Lv7, including two Lv7 victories with different seeds, while retaining a median JEV response time of 0.422 seconds. Mean estimated model cost across these games is USD~3.71 per game: USD~0.15 for JEV and USD~3.56 for GPT-6. We compare this system with an initial JEV-only controller in full-game macro control and multi-unit micromanagement. The standalone controller reaches a 20-minute limit against Lv2 without expanding. Across 35 battle maps with three episodes per map and controller, the combined system raises mean enemy elimination from 16.50% to 37.69% and wins from 3 to 7 out of 105. Replay frames and decision logs document resource reservation, persistent economic goals, and stable army objectives in successful full games. The results demonstrate a practical division between inexpensive, subsecond decisions and longer-horizon planning. The comparison evaluates complete systems; concurrent interface improvements mean that planning's contribution is not isolated by a controlled ablation. Code is available at https://github.com/sc2musa/Jev_Star

We study Bulow-Klemperer-style competition complexity in two-sided double auctions with $m$ unit-demand buyers drawn i.i.d. from $F_B$ and $n$ unit-supply sellers drawn i.i.d. from $F_S$. When $m \ge n$ and buyer valuations first-order stochastically dominate seller costs ($F_B \succeq_{\mathrm{FSD}} F_S$), we prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a prior-independent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market. When the buyer side is the smaller side of the market ($m \le n$), an analogous result holds for Buyer Trade Reduction with 2 additional buyers. This resolves open questions of Babaioff, Goldner, and Gonczarowski (SODA 2020) and Cai, Liaw, Mehta, and Zhao (STOC 2024). We complement our upper bound by showing that this uniform bound is optimal: already for $m = n = 1$, no prior-free mechanism (deterministic or randomized) that is dominant-strategy incentive-compatible, individually rational, and weakly budget-balanced can match the first-best GFT by recruiting only one additional seller.

Matching mechanisms differ in how much of an agent's preference ranking must be determined and reported to obtain a particular object. A mechanism is singleton-attainable (SA) if every object that an agent can obtain through some report can also be obtained by reporting only that object as acceptable. With an SA mechanism, once an attainable object has been identified, the agent need not rank or report any other object. Singleton-attainability identifies a distinct dimension in matching theory and market design: transparent access to attainable outcomes, separate from incentives, stability, welfare or equity. We establish general conditions for SA and derive its strategic implications. Top-lift invariance and truncation invariance together imply SA, while strategyproofness and stability each imply SA. By contrast, no Pareto improvement over a strategyproof, individually rational, and non-wasteful mechanism is SA. In particular, every Pareto improvement over Deferred Acceptance violates SA. We introduce report width, which measures how many acceptable objects may have to be reported to obtain an object. SA mechanisms have report width one. Report width is unbounded for a large class of efficient mechanisms that Pareto-improve Deferred Acceptance. Stable selection with report-induced priorities has width one when priorities are monotone and maximal width under reverse priority dominance. Rank-welfare maximization has width one when the outside-option rank is fixed and maximal width when it is report-dependent. These results reveal a structural divide, which we call the width dichotomy: across all mechanisms and families in our classification and all structural classes we study, report width is either one or unbounded.

Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies efficient computation, Pareto-efficiency, and liquid-welfare guarantees, enabling pacing integration into large-scale optimization-based allocation routines. Finally, for abstract mechanisms satisfying a payment monotonicity condition, we prove equilibrium existence by smoothing discontinuities. With additional conditions and appropriate tie-breaking, we obtain uniqueness, revenue maximality among budget-feasible pacing vectors, and shill-proof implementability, and provide convergent budget-adjustment dynamics for approximate equilibria. Overall, many favorable properties of first-price pacing extend beyond single-item auctions under appropriate mechanism-level conditions.

In temporal voting, a fixed set of voters makes a collective decision in each of several rounds, and proportionality requires that groups with shared interests be represented across these decisions. Full justified representation (FJR) is among the strongest proportionality axioms known to be satisfiable in this setting, since it allows different members of a group to be satisfied by different selected candidates. However, whether an FJR outcome can be computed in polynomial time has remained open. We resolve this question by introducing temporal FJR+, a strengthening of both FJR and extended justified representation+ (EJR+) that can be computed and verified in polynomial time. The axiom measures a group's agreement in each round by the largest number of its members who approve a common candidate, and requires some member to attain the integer part of the group's proportional share of its best attainable average satisfaction, with a shortfall of at most one unit when this share is an integer. We show that verification reduces to counting approvals among the voters below each satisfaction threshold. For computation, we observe that local search for Proportional Approval Voting (PAV) can stop at an outcome violating FJR. Somewhat counterintuitively, the remedy is to subtract a small multiple of the minimum voter satisfaction from the PAV score: every FJR+ violation then admits a single-round change whose improvement guarantees polynomial running time. We further show that temporal FJR+ is strictly stronger than FJR and EJR+ combined, and coincides with lower quota on party-list preferences. Finally, temporal FJR+ and multiwinner FJR+ are incomparable in general, but coincide when approvals are static and each candidate-round pair is treated as a separate candidate.

The objective of this article is to provide design principles and a software architecture for enabling interaction between humans and multiple agents in simulated dynamic worlds. This connects the current era of general artificial intelligence (AI/AGI) with the proliferation of transformer-based conversational agents and the increased computational capabilities. Given an overview of current and previous multi-agent theories of mind (socially and affectively-aware agents), the existence of an integrative design of agent interactions with themselves and with humans must be crucial for understanding how to create sustainable and governance in future human-agent reasoning systems. In this work is presented a software "AGIMUD" that integrates: A. socially-aware reasoning and emotion in agent behavior and interaction, B. a design of human multimodal scheme for human users, artificial agents and simulated worlds, and C. distributing the AI processing through the network to enable multiple autonomous agents. These integrations allow the dynamic world recreation as multi-user dungeons (MUDs) where both agents and humans can interact simultaneously in real time. Find the code online in https://github.com/dberga/AGIMUD.

Increasingly, resource allocation games are being proposed to model team coordination in denied communication environments. Of particular interest is understanding the impact of communication denial on the quality of emergent team coordination. In this work, we consider the situation with an arbitrary communication network and use the Price of Anarchy to quantify the quality of emergent behavior. Our main result is a computationally efficient algorithm that calculates a minimal communication network that has the same performance guarantee as the full information case. Additionally, we provide efficient algorithms that compute a Nash and a strict Nash equilibrium in the full information setting. Finally to support these algorithms, we provide sufficient conditions for the existence of a strict Nash equilibrium, characterize strict Nash equilibria across all communication networks, and show that each strict Nash equilibrium in the full information case has a necessary and sufficient set of communication links that induce it. We conclude by giving an execution time experiment of the proposed algorithm and examine several example games.

Social norms cannot be identified from behavior alone: the same cooperative equilibrium may reflect shared expectations, strategic incentives, or simple imitation. Yet in multi-agent large language model systems, prior work largely treats behavioral convergence as evidence of norm emergence. In this work, we introduce an evaluation framework that measures agents' reported empirical and normative expectations in addition to behavioral convergence. Through controlled ablations, we test the effect of expectation elicitation and isolate two collective mechanisms central to theories of norm formation—social learning through interaction and social selection through network-based group formation. We further test the stability of these resulting dynamics under adversarial disruption across four LLM families. We find that eliciting expectations increases cooperative contributions, while social learning stabilizes behavior, and social selection reliably identifies cooperators but provides limited behavioral reinforcement. Following disruption, normative expectations and behavioral coordination recover differently. Together, these results show that similar cooperative outcomes can arise from different underlying social processes. By making expectations observable, our framework allows us to attribute each mechanism's contribution separately, offering designers of multi-agent systems a principled basis for selecting the social processes that sustain cooperation.

Personalized AI memories, defined as persistent decision-relevant states distilled by platforms from long-run human-AI interaction, are increasingly portable, provenance-certifiable, and tradable. Provenance answers the question of origin, but it does not settle who holds which rights over a memory, nor how wider deployment affects its future supply. We develop a unified model in which memory use is non-rival, while refresh, the maintenance of continued validity, is relationally co-produced by the represented individual and the platform. Even assuming perfect provenance and complete information, the model still yields a set of inherent limitations. First, there is an extraction ceiling: decision value is bounded by lived experience. Second, a rights-separation theorem shows that no budget-balanced ownership assignment can make both co-producers residual claimants, and that control rights and cash-flow rights operate on distinct margins. Third, a depletion result indicates that reach-expanding policies such as portability, interoperability, and competition raise current access but shrink the long-run memory stock. Fourth, we offer a formal comparison between memory ownership as it ought to be (subject-held) and as it is (platform-held); the welfare ranking reduces to two measurable quantities, both dominated by interior renewable-claim bundles. Finally, endogenous-quality and market-formation results show that uncompensated markets pollute their own raw material, that transparency and compensation are complements, and that the de facto platform-ownership regime is self-perpetuating. On the design side, the analysis points to separated provenance, performance, and permission credentials; compensation indexed to quality-deployment; and portability and salience, rather than nominal ownership, as the binding policy margins.

In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of $n$ agents who arrive sequentially, with values drawn independently from a known distribution. When an agent arrives, their value is revealed, and the algorithm must immediately allocate the item or continue. The usual objective is utilitarian welfare: the expected value of the recipient. Guarantees for this objective extend to allocating $m$ indivisible items to sequentially arriving agents with i.i.d.\ additive values. Utilitarian welfare, however, ignores how expected utility is distributed across agents. Motivated by a rich literature in fair division, we instead evaluate an online rule by its generalized $p$-mean welfare, which includes utilitarian welfare at $p=1$, Nash welfare (the geometric mean of utilities) at $p=0$, and egalitarian welfare (the minimum utility) as $p\to-\infty$. When the number of items is large, we show that this many-item fair-division problem is captured exactly by a single-item prophet problem evaluated by the $p$-mean of agents' expected utilities. We characterize this single-item problem: every online rule is weakly Pareto dominated by a quantile-threshold rule, and an optimal egalitarian rule equalizes agents' expected utilities. We prove that for every $n$, the online optimum is at least $\Gamma\approx0.7059$ times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every $p\le1$. Further, for egalitarian welfare, the optimal ratio converges to $\Gamma$ as $n\to\infty$. Thus, asymptotically, optimizing egalitarian rather than utilitarian welfare costs only about four percentage points relative to the classical utilitarian ratio of $0.7451$. Finally, when $m=n$, the worst-case competitive ratio converges to zero as $n\to\infty$ for every $p\le0$, showing that the large-item assumption is necessary.

We study strategic disclosure of the action space in principal-agent contracting, where an agent selects a disclosed action set to shape the principal's perception of her capabilities before contract design. Unaware of the strategic disclosure, the principal designs a revenue-optimal contract as if the disclosed action set were complete and accurate. We consider two variants distinguished by cost verifiability. When costs are unverifiable, the agent can extract the entire first-best surplus, leaving the principal with zero revenue. When costs are verifiable, we characterize the agent's optimal disclosure strategy in binary-outcome settings and, more generally, when the principal is restricted to linear contracts, reducing the agent's problem to a two-variable convex optimization problem. We prove that the agent can secure utility of at least a $1/e$ fraction of the first-best surplus, which also yields a $1/e$ welfare guarantee under optimal disclosure. While the principal's revenue can be arbitrarily small compared to the first-best surplus, when the ratio of maximum to minimum expected reward among non-null base actions is at most $L$, we establish a revenue guarantee of $\Theta(1/\log L)$ relative to the first-best surplus. We also compare utilities and welfare under strategic disclosure with their counterparts in the canonical model. Finally, we extend the agent's $1/e$ utility guarantee to general outcome spaces without restricting the principal to linear contracts. Our results show how strategic action-space disclosure changes the distribution of surplus while preserving a constant-factor welfare guarantee under the agent's optimal disclosure.

In the one-round discrete Voronoi game a multiset $V$ of $n$ voters on a line is given; player P places $k$ facilities, player Q then places $\ell$, and each voter is won by the nearer facility, ties going to P. P wins if it keeps at least $n/2$ voters. In the vocabulary of competitive location this is the absolute $(\ell|k)$-centroid problem on a path with unit demands, and the responder's problem is the $(\ell|X_k)$-medianoid, whose closed form on a path – the sum of the $\ell$ largest of at most $2k$ explicit marginals – is due to Spoerhase and Wirth. We record this structure, with complete proofs, and draw two consequences that we believe are new. First, we compute the value of the game against a single responding facility, $\Gamma_{k,1}(V)$, together with an optimal strategy for P, in $O(n\log n)$ time for arbitrary positive real demands and every $k$. This improves the $O(kn\log^2 n)$ bound of Lazar and Tamir for the absolute $(1|k)$-centroid on a path. Second, we study the facility advantage $k^*(\ell)$, the least $k$ for which P wins every instance against $\ell$ facilities. We prove $k^*(\ell)\le 2\ell-1$, exhibit instances proving $k^*(\ell)\ge\ell+1$ for $2\le\ell\le6$ (an exact, computer-assisted proof resting on a half-integer discretisation), determine $k^*(1)=1$ and $k^*(2)=3$, and show that on uniform instances $k=\ell$ already suffices, so the extremal instances are weighted and Q wins them by a single voter. We conjecture $k^*(\ell)=\ell+1$ for all $\ell\ge2$.

Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For $n\ge5$, we construct $3\times n$ games that have all $2n+1$ vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic $4\times 5$ games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For $d\times n$ games, we construct games where all but a fraction of $O(1/n)$ of the maximum number of vertices are equilibrium strategies.

Braess paradox is a well-known phenomenon that originates when latency at Wardrop equilibrium in traffic networks decreases because of removing edges. The possibility of having the paradox was called vulnerability by Roughgarden in 2006 and was characterized later on by graph-theoretical notions, both for undirected and for directed graphs. In this paper we provide an algorithm for the incremental case of checking vulnerability for dynamically evolving graphs. The crucial idea to keep the amortized cost linear for every edge addition is that we do not need to run the vulnerability algorithm on the whole graph, but only on a well-identified subgraph, determined by the edge that we are adding. Overall, to add m edges, we pay a cost of O(m2); this aligns with the O(m2) cost of the state-of-the-art static algorithm for vulnerability.

We study the computational complexity of fundamental algorithmic problems – membership testing, separation, valid-inequality testing, and linear optimization – over polytopes and cones arising from cooperative games (also known as pseudo-Boolean functions). A central obstacle in the study of such problems is that a general cooperative game on $n$ players requires $2^n$ values, so the input size is $2^n$ for a game with $n$ players, making these computational tasks theoretically trivial. Restricting to $k$-additive games reduces the input size to $O(n^k)$, making such games a natural target for meaningful questions about the existence of efficient algorithms. On the positive side, we give an explicit extended formulation of size $O(n^k)$ for the core of $k$-additive $k$-monotone games, allowing all four problems to be solved by a single polynomial-size linear program – in particular, circumventing the ellipsoid method that is needed when building from earlier tractability results of Deng and Papadimitriou, or of Edmonds. For the cone of $k$-additive $(k{-}1)$-monotone games, we give a complete characterization of its extreme rays and derive the same $O(n^k)$ bound on extension complexity, yielding a geometry-based proof and generalization of a result of Billionnet and Minoux. On the negative side, we show that for $l \leq k-2$ the cone of $k$-additive $l$-monotone games is computationally intractable: membership testing is not in NP (unless NP\,=\,coNP), valid-inequality testing is NP-complete, and extension complexity is at least $1.5^n$. Our hardness results yield, as a special case, a result of Crama and of Gallo and Simone. Furthermore, our hardness results also explain the lack of any good characterization of the extreme rays of the cone of $k$-additive $(k{-}2)$-monotone games.

We consider sequential Plurality elections in which each voter may abstain or vote for a single candidate. Each voter assigns utilities to all candidates; for each voter, this induces a (weak) order over the candidates. Ties are resolved uniformly at random, and voting has a small positive cost, so that a voter prefers to abstain when their vote cannot change the election outcome. We consider a variant of this model where, for each voter, we additionally specify a prefix of her ranking, so that she is only allowed to vote for a candidate from that prefix (or abstain). We prove that for this variant of the model, deciding whether a designated candidate is among the election winners in a subgame-perfect equilibrium of the associated extensive-form game is PSPACE-complete. This partially resolves an open problem from the work of Desmedt and Elkind [2010].

Moving target defense (MTD) against advanced persistent threats (APTs) in industrial control systems (ICS) has well-established game-theoretic formulations, but their practical value hinges on equilibrium computation, which faces two gaps: full-rank value iteration is prohibitively expensive at industrial scale, and the resulting defense strategies admit no certified robustness against adversarial perturbations. We first reveal that the attack and defense influence matrices of ICS dynamics are intrinsically low-rank: APTs infiltrate through a handful of entry points and MTD reconfigures only a few components per cycle. Our theory makes four contributions. First, an augmented gradient matrix certifies that the low-rank structure propagates through the non-smooth Bellman operator of the zero-sum stochastic game, so that every Bellman target lies near a low-dimensional subspace and low-rank truncation incurs an explicit error bound (Lemma 1, Theorem 1). Second, we propose the Dynamical Low-Rank Nash Equilibrium algorithm, named DLR-NE, which augments the rank-r search space each iteration, regularizes the core matrix spectrum, and retracts via truncated SVD, and prove that it converges geometrically to a neighborhood whose error decomposes into five physically interpretable sources (Theorem 2). Third, its per-step cost is O(nr^2), a Theta(n/r^2) speedup over full-rank value iteration (Theorem 3). Fourth, a single weight trades accuracy against a certified sensitivity bound of the induced defense strategy under core-matrix perturbations (Corollary 1). Six experiments on a nonlinear power-system testbed confirm each prediction, with 94% parameter compression at 2.3% utility loss. All experimental data and code are publicly available.

Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. The nondegeneracy promise can be removed if nonregular equilibria are also accepted: finding either a regular Nash equilibrium of index +1 or a nonregular Nash equilibrium in an arbitrary rational bimatrix game is also PPADS-complete. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].

Two-round legislative elections are decided not only by first-round vote shares, but by how voters whose preferred party did not advance redistribute their votes among the surviving candidates. We develop a principled model of this transfer process, grounded in multi-dimensional ideological embeddings derived from the Chapel Hill Expert Survey, and apply it to French legislative elections. Calibrated on the 2017 and 2022 elections, the model is evaluated on the unusually complex 2024 contest, in which three ideologically distinct blocs reached the second round simultaneously, achieving 90.34 percent constituency-level accuracy. We show that ideological proximity alone explains the large majority of vote transfers, that a simple left-right axis is insufficient to capture the relevant distances, and that the structural configuration of the 2024 electorate was far less favorable to the far right than pre-election forecasts suggested.

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-\delta$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $\Omega(\log n)$, uniformly over $\delta\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.

We study second- and higher-order methods for solving smooth monotone variational inequalities (MVI). Monteiro and Svaiter (SIAM J. Optim., 2012) showed that a second-order method, NPE, converges at a rate of $\mathcal{O}(T^{-1.5})$. For convex-concave minimax optimization, a subclass of MVI problems, Chen, Liu, Luo, and Zhang (COLT 2025) recently improved this rate to $\tilde{\mathcal{O}}( T^{-1.75})$. However, the result has a substantial gap compared to the lower bound of $\Omega(T^{-2.5})$ established by Chen et al. (2026). In this paper, we propose a novel second-order method that achieves the optimal rate of $\mathcal{O}(T^{-2.5})$. Our algorithm also extends to higher-order methods: for any integer $ p \ge 1$, we obtain a $p$th-order method with a convergence rate of $\mathcal{O}(T^{-(3p-1)/2})$, matching the known lower bounds and therefore establishing optimal rates across all orders.

Many modern systems involve the strategic interaction of multiple agents. In such settings, observed actions typically reflect equilibrium behavior under utilities that are only partially known. Recovering these hidden utilities from data - the central goal of inverse game theory - is key for prediction, counterfactual analysis, and mechanism design. However, existing approaches based on inverse variational inequalities are highly sensitive to noisy and inconsistent equilibrium observations, thus limiting their applicability. In this paper, we resolve this issue by introducing a game-theoretic suboptimality loss that measures the aggregate utility gain players could obtain by unilaterally deviating from an observed strategy profile. First, we show that this loss is convex and admits an efficient decomposition into player-wise best-responses. Second, we show this loss is sandwiched between the predictability loss and the inverse variational inequality loss, making it a tractable surrogate for equilibrium prediction. Third, we develop a mirror descent algorithm to minimize it and demonstrate on a heterogeneous networked Cournot competition that our approach remains accurate under noisy observations and inconsistent equilibrium data while inverse variational inequality methods produce degenerate estimates.

This paper investigates the constrained existence problem for subgame perfect equilibria (SPEs) in multiplayer graph games. In the proposed framework, each player has a preference relation over the set of plays, assumed to be $\omega$-recognizable. Equivalently, he has a preference relation over a finite set of payoffs, and the set of plays with the same payoff is $\omega$-regular, for each payoff. This generic framework avoids the need to focus on specific payoff functions. We show that the constrained SPE existence problem is EXPTIME-complete, as well as for Nash equilibria (NEs).