CS Paper Radar

Daily listing

2026-11-19 · cs.GT

8 papers first submitted this day (UTC) in cs.GT — Computer Science and Game Theory. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

AI & Machine Learning 1

Pareto-Optimal and Strategyproof Data-Sharing Between Competitors

cs.AI cs.GT ·2026-11-19 ·Morgan Colin-Mourre, Felipe Garrido-Lucero, Patrick Loiseau
Abstract

We study data-sharing among firms competing in the same market through the quality of their predictive models. We model firms' profit through two main components, precision and market share, where the former depends on the firm's own number of datapoints and the latter depends on the endowments of all firms. We characterize Pareto-optimal contracts as those in which at least one firm receives all of the other firms' datapoints. We then propose a parametric family of data-sharing contracts and show that, under any of them, the relative market shares of all firms remain constant, eliminating the negative effect of sharing data with competitors and equalizing all firms' gains relative to the no-sharing scenario. We further show that one contract within this family satisfies both Pareto-optimality and strategyproofness against firms attempting to under-declare the size of their initial endowment. Finally, using a real-world dataset, we empirically test the gain in profit for all firms under the contract described above, and show that data-sharing is particularly beneficial when the machine learning task is harder or when firms' initial endowments are closer to homogeneous.

0.26

Theory & Algorithms 7

Safe Subgame Resolving in Multiplayer Games

cs.GT cs.AI ·2026-11-19 ·Boning Li, Longbo Huang
theorycode/data
Abstract · 44 pages

Poker and other games with hidden information are too large to solve in one pass. Strong systems compute a complete blueprint strategy offline and refine it in real time inside the reached subgame. In 2p0s games, a safety theorem guarantees that subgame resolving never increases how much an adversary can gain by exploiting the resolved strategy relative to the blueprint strategy. With three or more players acting independently, no such guarantee exists yet, and heuristic resolving can increase the profile's best-response gap. We prove the first conditional safety theorem for uncorrelated multiplayer subgame resolving, a post-hoc certificate for any delivered update. The best-response gap of the resolved profile exceeds that of the blueprint by at most four terms. Two concern the resolver: the subgame value the blueprint promised without realizing ($A_i^{S}$) and the resolver's subgame solve error ($\varepsilon_i$). The other two are the opponents' best-response gains inside the subgame over their promised values ($\sum_q M_{q}$) and a structural tax ($Θ$), which measures how much the players' total utility can change. The tax is zero in constant-sum games, including every rake-free poker variant. Constructions attain each term with equality. On three-player Leduc poker and on Kuhn poker with up to six players, resolving without a certificate raises the gap beyond a small tolerance in 12% to 100% of the updates. The certificate flags every such update and accepts 41% (Kuhn) and 86% (Leduc) of the standard resolving updates. A resolver that keeps the blueprint whenever the certificate exceeds the tolerance delivers no harmful update. The certificate needs only one best-response pass per opponent inside the subgame, so real-time multiplayer solvers that refine a blueprint can attach it as a safety check. Code is available at https://github.com/lbn187/MultiPlayerSolver

0.67

Path-Independent Deleveraging Rules

cs.GT q-fin.RM ·2026-11-19 ·Christoph Schlegel, Akaki Mamageishvili
Abstract

We characterise path-independent auto-deleveraging (ADL) rules as an extended log-exponential family. Immunity to account splitting, merging and reopening further restrict the class. Homogeneity (essentially) restricts the class to a one-parameter family ordered by both fairness and platform risk. Its split-proof members continuously interpolate between proportional division and water-filling. Among these rules, decreasing the parameter reduces risk at the cost of increasing inequality in how accounts are treated. This suggests selecting the parameter through an ex-ante calibration to a risk bound on historical data to choose a maximally fair rule subject to that bound. A counterfactual replay of Hyperliquid's ADL episode on 10 October 2025 finds that a range of intermediate parameters significantly improves on the observed allocation in both burden dispersion and subsequent risk statistics.

0.39

Uniqueness, Proximity, and Scaling in Atomic Splittable Polymatroid Congestion Games

cs.GT ·2026-11-19 ·Tobias Harks
theory
Abstract · 41 pages

We give a polynomial-time algorithm for exact equilibrium computation in atomic splittable polymatroid congestion games with integral ranks and rational player-specific affine latencies with positive slopes. The algorithm first computes equilibria of associated integer-splittable games, in which demands are allocated in multiples of a common packet size. For arbitrary polymatroid bases, no polynomial-time algorithm for these discrete equilibria was previously known. We provide such an algorithm and use progressively finer packets to recover the continuous equilibrium exactly. Our proof uses the multiple-exchange theorem of Oki and Schwarcz (2025) to obtain two exchange matchings that yield equilibrium proximity under changes of packet sizes and ranks, independently of cost coefficients. We then bound the matching deficiency caused by rank changes and construct compatible submodular rank roundings. Together these give a polynomial-time packet-halving algorithm using polynomially many submodular-function minimizations and exact rational arithmetic. The analysis rests on a uniqueness theorem of independent interest: for arbitrary real polymatroid ranks and continuously differentiable, strictly increasing, convex latencies, we prove uniqueness of equilibria, resolving a previously open problem.

0.37

Sequential Contract Design for Budgeted Crowdsourcing

cs.GT ·2026-11-19 ·Michal Feldman, Vasilis Gkatzelis, Shaul Rosner, Inbal Talgam-Cohen
benchmark
Abstract · 37 pages

A principal wishes to crowdsource a collection of tasks under a fixed compensation budget. The quality of a task's outcome is stochastic and depends on the worker's effort level. Since this effort is unobservable, the principal offers contracts to workers specifying their compensation for each possible outcome. The principal offers these contracts sequentially, using previously observed outcomes and payments to decide whom to approach next and what contract to offer. The objective is to maximize the expected value of the work produced while ensuring that total payments never exceed the budget, regardless of the realized outcomes. Contract design must therefore account both for a worker's incentives and for the budget available to incentivize others. For valuations that are additive across tasks, we characterize how the approximability of the optimal adaptive policy depends on the numbers of workers, effort levels, and outcomes. Polynomial-time constant-factor approximation is possible whenever the number of workers, effort levels per worker, or outcomes per task is constant, but impossible in general when all three are unrestricted, unless $P=NP$. We obtain tight guarantees for every fixed number of workers, establish computational hardness even in restricted settings, and obtain exact algorithms and approximation schemes in more structured settings. We also investigate simple contract structures, demonstrating both the benefits of adapting contracts to previous outcomes and the limitations of local contract rules, while identifying conditions under which a local policy achieves a constant-factor guarantee. Finally, we extend our analysis beyond additive valuations, obtaining constant-factor approximations for monotone submodular valuations with binary outcomes, including guarantees against a stronger full-knowledge benchmark under additional assumptions.

0.27

Closing Gaps in Temporal Fair Division for Chores

cs.GT ·2026-11-19 ·Nicholas Teh
Abstract

We study the fair division of indivisible chores that must be assigned in a prescribed order. The complete instance is known in advance, but assignments cannot be changed. Temporal envy-freeness up to one chore (TEF1) requires envy-freeness up to one chore after every arrival. For goods, TEF1 allocations need not exist, and deciding whether one exists is NP-hard. For chores, Elkind et al. (AAMAS 2025) showed that TEF1 allocations exist for two agents, but left open whether they always exist, conjecturing that they do not, and whether deciding their existence is hard. We resolve both questions, confirming the conjecture in a strong form: for every $n\ge3$ and every finite factor, some $n$-agent instance admits no allocation satisfying TEF1 even up to that factor. This holds even when all agents have the same multiset of individual chore costs, with nine chores sufficing for three agents. Deciding TEF1 existence is NP-complete for every fixed $n\ge3$, even when all costs lie within a factor $1+2^{-m}$ of one another, where $m$ is the number of chores. Instances without TEF1 allocations exist arbitrarily close to the uniform cost matrix with $O(n\log n)$ chores, and just nineteen for three agents. We then relate fairness to social cost. Even when a TEF1 allocation is supplied, minimizing social cost subject to TEF1 admits no polynomial-time approximation within any factor polynomial in the number of chores unless P$=$NP, already for three agents with strictly positive normalized costs. In contrast, for every fixed number of agents, we give an FPTAS for the optimal temporal EF1 factor, the smallest factor up to which TEF1 can be satisfied, whose output has social cost no larger than that of the cheapest allocation attaining this factor. Thus a slight relaxation of fairness permits a social-cost guarantee that, unless P$=$NP, no polynomial-time algorithm can provide under exact TEF1.

0.27

Proportional Representation for Almost-Solid Coalitions and the Proportional Veto Core for Rankings

cs.GT ·2026-11-19 ·Evi Micha, Fatih Erdem Kizilkaya
Abstract

A proportional ranking should give groups of voters representation commensurate with their size at every prefix. Proportionality for solid coalitions (PSC) provides this guarantee to groups whose members rank the same set of candidates above all others. How much representation should a group receive when a few outside candidates disrupt that agreement? We extend the proportional veto core to rankings through candidatewise and setwise guarantees. We show that setwise veto protection is equivalent to robust Rank-PSC under reversal of both the voters' preferences and the collective ranking. Robust Rank-PSC extends representation guarantees to almost-solid coalitions at every prefix. Each distinct outside candidate that disrupts a coalition's agreement reduces its guaranteed representation by at most one, and this bound is tight. Using reverse-sequential variants of Ordered Phragmén and STV, we construct rankings satisfying robust Rank-PSC$+$ in polynomial time. This stronger axiom preserves the guarantee after deleting any suffix of the collective ranking and restricting voters' preferences to the remaining candidates. Verifying robust Rank-PSC is coNP-complete, whereas verifying robust Rank-PSC$+$ takes polynomial time. We also introduce Rank-Aligned PJR$+$, which requires the first $r$ candidates of the collective ranking to satisfy PJR$+$ when each voter approves their top $r$ candidates. We give a polynomial-time algorithm that meets this requirement simultaneously for every $r$. For fixed-size committees, the Expanding Approvals Rule guarantees Rank-PJR$+$ but can violate robust PSC regardless of how ties are broken or payments are assigned. We give a modification that satisfies both guarantees for any prescribed committee size.

0.14

Distortion in Online Voting

cs.GT ·2026-11-19 ·MohammadHossein Ghasemi, Masoud Seddighin, Saeed Seddighin
theory
Abstract

We initiate the study of distortion in online voting, a framework that bridges computational social choice and online algorithms. In contrast to the classical offline setting, where the full election instance is known in advance, we consider a dynamic environment where a fixed set of voters is present from the beginning, but alternatives arrive sequentially over time. Upon each arrival, a mechanism must immediately and irrevocably decide whether to retain the currently selected candidate or switch to the newly arriving one, operating solely on the partial ordinal rankings induced by the underlying cardinal preferences. We provide upper and lower bounds for deterministic and randomized mechanisms under two standard cardinal preference frameworks. Utilitarian framework: For deterministic mechanisms under adversarial arrival order, we establish an $Ω(mn)$ lower bound and give an matching online algorithm with distortion at most $\frac{2}{3}m(n+\frac{1}{4})$. For randomized rules, we introduce regularity, which allows any regular, order-independent offline randomized rule to be converted into an online rule with the same expected distortion. The Harmonic voting rule satisfies this property, yielding online distortion $O(\sqrt{m\log m})$. Metric framework: For deterministic mechanisms, maintaining an alternative within a $\varphi$-weighted uncovered set guarantees distortion $2+\sqrt{5}$. We show that matching-based offline rules achieving distortion $3$ cannot be directly implemented online. We establish a lower bound of $\sqrt{13}$, even with three alternatives, and a matching upper bound for three alternatives and any number of voters. For randomized mechanisms, regularity gives an online distortion of $3-\frac{2}{n}$ via Random Dictatorship.

0.13