In briefProves that checking membership in the tournament equilibrium set is PSPACE-complete
SummaryThis paper studies the tournament equilibrium set (TEQ), a voting rule proposed by Schwartz in 1990 that relies on pairwise majority comparisons and is defined recursively. It proves that deciding whether a given alternative belongs to TEQ is PSPACE-complete, closing the gap between the previously known NP-hardness and PSPACE membership. The hardness holds even when every nonempty subtournament has a unique minimal retentive set. The paper also shows how the complexity changes with the bound on the number of dominators.
WhyThe authors prove TEQ membership is PSPACE-complete, even under hereditary uniqueness, and give a fuller dominator-bound complexity classification for tournament solutions.
In briefSubmodular secretary problem: tight 1-1/e for monotone objectives, and a ratio strictly between 1/e and 1/2 in general
SummaryThe paper studies the submodular secretary problem with a cardinality constraint, where elements arrive in random order and must be accepted or rejected irrevocably to maximize a nonnegative submodular function over sets of at most k elements. For monotone objectives, the optimal competitive ratio tends to exactly 1-1/e as k grows, achieved by an algorithm using at most 4n+1 value queries. For general objectives, the optimal limiting ratio is shown to lie strictly between 1/e and 1/2, using a new technique called eligibility attenuation.
WhyThe authors give a tight 1-1/e ratio for monotone objectives with one algorithm, and improve general objectives to a value strictly between 1/e and 1/2 via eligibility attenuation.
Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi et al.
In briefFictitious play for agents using nonlinear risk-based evaluation in 2×2 games
SummaryThis paper studies nonlinear fictitious play, where agents evaluate each action with a possibly nonlinear functional of the opponent's payoff distribution rather than maximizing expected payoff. The authors identify a single-crossing property that preserves the classical geometry of fictitious play in 2×2 games and analyze convergence geometrically even when this property fails. They show that in a 2×3 game, convergence can fail even in continuous time when the two-action player uses conditional value-at-risk. They also give a finite-crossing condition that ensures convergence in general 2×n games.
In brief"Sowing the Seeds of Intractability: Kalah is PSPACE-complete" — a proof that deciding a forced win in the sowing game Kalah is PSPACE-complete as board size grows
SummaryThis paper studies Kalah, a classic two-player sowing game in the mancala family, with the number of pits per side treated as part of the input. It shows that deciding whether a designated player can force a win from an arbitrary position is PSPACE-complete. The proof introduces an intermediate game, Line Kalah, reduces quantified Boolean formulas to it, and embeds the line positions into Kalah with both stores empty.
WhyThe authors prove that deciding forced wins in generalized Kalah is PSPACE-complete via a reduction from QBF through an intermediate Line Kalah problem, valid under both capture conventions and bonus
In briefPACER: Managing GPU Power Overshoots for Machine Learning Workloads
SummaryThis paper examines intra-GPU performance variability caused by brief power excursions, which occur when GPU power temporarily exceeds its rated limits. The authors are the first to characterize how large and how frequent these overshoots are, finding them especially common in machine learning workloads with short, power-hungry kernels. They design hardware and firmware mechanisms to make power management more consistent and reduce this variability. Across popular workloads, the approach improves performance by 3-12% over state-of-the-art GPU power management and comes within 3% of an oracular solution.
In briefLearning dynamics of a spatial game on resource landscapes
SummaryThis paper introduces the influencer's game, a spatial game in which players occupy positions in a trait space and receive shares of resources based on their relative influence at each trait point. The authors show that a unique symmetric Nash equilibrium exists when the influence kernel is strictly log-concave, and they analyze how stability depends on kernel parameters, player count, and resource distribution shape. Beyond the equilibrium analysis, the paper identifies stability thresholds and bifurcation types, and it supports the results with real-world resource data and multi-agent reinforcement learning experiments.
WhyThe authors introduce a new spatial game, prove a unique symmetric equilibrium, derive a stability threshold and bifurcations, and test with real data and reinforcement learning.
In briefBroadcast Instead of Copying: Removing Weight HBM from Datacenter LLM Inference
SummaryThis paper proposes Optical Broadcast Memory (OBM), a hierarchical fiber architecture that replaces an earlier optical fiber loop memory design for serving large language models. A central memory server continuously broadcasts model weights, and inference nodes passively tap the data stream using receive-only co-packaged optics. Evaluated at 80,000 accelerators, the approach eliminates petabytes of HBM while matching or exceeding an HBM-based system in throughput and energy per token.
