arXane › Computer Science › Computer Science
Wednesday, 4 November 2026: 15 new papers, 4 cross-lists and 16 replacements in Computer Science and Game Theory (cs.GT), in arXiv's order, with full abstracts. The same papers as arXiv's own listing, set as a newspaper; every title links to arXiv.
Autobidding equilibria link advertisers' value multipliers or participation probabilities through aggregate budget and return-on-investment (ROI) constraints. We establish the exact computational complexity of finding these equilibria across several canonical settings: exact equilibrium computation is $\mathsf{FIXP}$-complete for second-price ROI pacing, budget- or ROI-constrained generalized second-price (GSP) sponsored shopping, and second-price throttling. Furthermore, approximating the equilibrium control vector in distance to a true equilibrium is $\mathsf{FIXP}_{a}$-complete when the target accuracy is provided as input.
We study indivisible goods allocated to two prescribed nonempty groups whose members have arbitrary monotone valuations. We guarantee balanced envy-freeness up to one good (EF1) for at most five agents and up to two goods (EF2) for at most nine, for any number of goods. Bundle sizes differ by at most one. The EF1 threshold is sharp: every split of six agents can fail. EF2 improves the previous five-agent guarantee. Via the connection of Kyropoulou, Suksompong, and Voudouris, these guarantees follow from chromatic bounds for $\mathrm{KG}(2n,n,r)$, whose vertices are $n$-subsets of a $2n$-set, adjacent when their intersection has size less than $r$. We prove its chromatic number is six for $r=2$, $n\ge2$, resolving Jafari and Alipour's conjecture, and at least ten for $r=3$, $n\ge4$, improving the previous lower bound of six; the known upper bound is fourteen. We show that the standard box-complex $\mathbb{Z}_2$-index bound yields exactly five and nine for $n\ge3$ and $n\ge5$, respectively. To exceed these bounds, we exploit restrictions on maps induced by colorings: a proper five- or nine-coloring must induce a nonzero homology map, yet local constraints force all generators, supported on pentagon or rook configurations, to map to zero. The ten-color proof compares integral and fractional common centers using a sharp rounding theorem for five subset constraints. A linear-time retraction from the full allocation graph onto balanced layers adds cardinality balance to known nonlinear discrepancy guarantees. For each fixed removal allowance in the guaranteed-existence range, finding a balanced fair allocation or an explicit monotonicity violation from valuation circuits is polynomial-time equivalent to finding a monochromatic edge in a circuit-specified coloring of the corresponding graph. The reverse reduction produces normalized monotone binary valuations using ordinary circuits.
The Bayes-Nash equilibria of an auction are the solutions of a variational inequality, and for standard auctions its operator fails every monotonicity notion, so the theory of monotone operators is unavailable to learning in auctions. We show what replaces monotonicity for the first-price auction: a certificate that is strong but local. For uniform values the single-population operator has an exact closed form and an exact Minty identity at the equilibrium; for two bidders its Gateaux derivative there is $L^2$-coercive with best constant exactly one in every piecewise-linear bid space with $m$ pieces, while the Minty inequality holds only on a ball whose radius decays like $m^{-5/2}$. The decay is exact: $m^{5/2}$ times the radius converges to $1/(8 \cdot 3^{1/4})$, and the worst perturbations converge to an alternating geometric profile with ratio $-(2-\sqrt{3})$. Refinement shrinks the ball, not the constant; independent learners see the same constant. For a general prior and bidder count there are two certificates, at the true equilibrium and at the equilibrium of the finite-dimensional bid space a learning algorithm runs in. The first is an explicit weight $w_F$, positive for every log-concave prior, equal to the second exactly for the value distributions $F(v)=v^a$. Otherwise the learners' certificate differs by knot masses, because the discretized equilibrium's slopes oscillate with a law proved for two and three bidders, and for four under a computer-verified bottom layer. The limit of the learners' certificate is proved in closed form, a function of the prior alone, and characterizes positivity: positive uniformly in $m$ in the limit exactly when that minimum is positive, with a known rate; for one prior at every $m$ by interval arithmetic. For more bidders the limit is conjectured. The exact identities and leading-order inequalities are machine-checked in Lean.
AI assistants increasingly participate in work that requires employees to exchange information and coordinate decisions. We study how a firm should design this communication when workers' interests conflict with each other's and the firm's. Two workers privately know local conditions and their preferred responses, while the assistant knows aggregate project conditions. The firm discloses project information before workers report and choose their own actions. Transparency improves adaptation but can undermine truthful preference reporting. When workers agree with the firm on the productive direction, coarsening project information under weak coordination can preserve useful preference reporting at a cost in forecast precision. Under strong coordination, the firm instead prefers full project disclosure and factual reports, because preference information induces costly accommodation of private objectives. Under weak coordination, a firm-optimal policy can leave workers worse off than direct exchange; requiring their acceptance can call for further coarsening. Releasing project context after reports can sustain factual communication that early release would prevent. With separate delivery decisions that cannot be revised jointly, endogenous forwarding weakly improves firm-preferred performance over unchanged forwarding and strictly improves it in some environments. Numerical comparisons show that full initial disclosure captures most gains in the aligned environments considered, while further design has greater value when workers can favor opposing directions. The results distinguish the credibility of employees' reports from their organizational value and show how disclosure timing affects both.
We study the comparison-query complexity of computing allocations that are envy-free up to one item (EF1) for $n$ agents with heterogeneous additive preferences over $m$ indivisible items. In this model, the algorithm may only query which of two bundles an agent prefers, without ever observing numerical valuations or costs. Prior work established $O(\log m)$ query bounds for at most three agents, leaving open whether query complexity logarithmic in $m$ is achievable for every fixed $n \ge 4$. We resolve this open question in the affirmative: for every fixed $n\ge2$, we design algorithms that compute EF1 allocations using $O(\log m)$ comparison queries, matching the known $\Omega(\log m)$ lower bound. Our results hold for both chores with nonnegative costs and goods with nonnegative valuations.
Quantile-based summaries, such as prediction intervals and medians, are commonly used in economic forecasting, climate science, and public health. For highly skewed samples, experimental evidence suggests that estimates of the mean can be biased toward the median, whereas estimates of the median are relatively accurate. This motivates aggregating explicitly elicited quantiles rather than reported means. We study robust aggregation of quantile reports for bounded outcomes under squared loss, minimizing worst-case regret relative to an omniscient Bayesian aggregator who knows the information structure and observes all private signals. Without restrictions on the information structure, no rule improves on the constant forecast at the range midpoint in worst-case regret. We therefore consider weak substitutes, a diminishing-returns condition on the value of information, and characterize optimal aggregation rules under this condition. For central prediction intervals with common nominal coverage $\alpha$, the optimal rule, which we call regularized simple average for prediction intervals, shrinks the average reported interval midpoint toward the range midpoint, with a weight determined by $\alpha$ and the number $n$ of experts. This optimal rule strictly improves on the constant baseline in worst-case regret when $\alpha<1/\sqrt{n}$; at or above this threshold, the constant rule is optimal. The optimal worst-case regret is minimized at a unique interior coverage level, revealing a nonmonotonic relationship between coverage and aggregation performance. For median reports, regularized simple average for medians similarly shrinks the average reported median toward the range midpoint, assigning weight $1/n$ to the reported average and strictly improving on the constant baseline in worst-case regret for every finite $n\ge2$.
We study randomized allocations (lotteries) of indivisible chores under additive costs and introduce the notion of MMS1, which requires each agent's bundle to satisfy the maximin share (MMS) bound after the removal of at most one chore. Our main result establishes that every instance admits an ex-ante proportional lottery in whose support every allocation is MMS1 and all but $o(n)$ agents satisfy MMS. Consequently, every realized allocation can be made MMS by disposing of at most $o(n)$ chores. The proposed framework further achieves ex-ante proportionality alongside ex-post $4/3$-MMS, $o(n)$-AMMS, or $1$-out-of-$d$ MMS for $d=(1-o(1))n$. These guarantees substantially improve upon state-of-the-art bounds for MMS allocation for chores with disposal or subsidy, best-of-both-worlds fairness, approximate AMMS, and ordinal MMS approximations.
We study optimal contracts when an agent allocates continuous effort subject to polymatroid capacity constraints. Effort produces a linear expected reward and incurs a cost. With binary outcomes and limited liability, the principal chooses a single reward share. For linear costs, an optimal contract can be computed in polynomial time. For quadratic costs, the agent has a unique best response computable by polynomially many submodular minimizations, yet optimizing the principal's share is NP-hard even for explicitly represented cut-based rank functions. With $n$ activities, the best-response path can have $2^{n-O(\log n)}$ breakpoints even when each reward coefficient and each rank value is an integer representable in $O(n\log n)$ bits. The construction also answers a question of Allman, Lo, and McCormick on polynomial bit length for source-sink monotone two-parameter minimum cuts. Despite this complexity, an optimal contract for quadratic costs always exists with a share of at most $1/2$. Consequently, $O(1/\varepsilon)$ best-response computations suffice for a $(1-\varepsilon)$-approximation. For rational quadratic costs on explicitly described rational polytopes containing zero, this gives a fully polynomial-time approximation scheme. More generally, a share of at most $1/p$ suffices for continuous convex costs homogeneous of degree $p>1$, on any compact convex action set containing zero. For general convex costs with an exact value and bounded-subgradient oracle, we obtain an oracle approximation scheme using approximate best responses and a supplied lower bound on positive welfare.
For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $\Omega(1/\log\log n)$ to $\Omega(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.
We study automated design of strategyproof (SP) mechanisms for randomized facility location on continuous metric graphs, with the objective of minimizing total distance. We develop methods for computing upper and lower bounds on the optimal approximation ratio achievable by SP mechanisms for a given graph and number of agents. For the lower bound, we propose a cost-preserving reduction to a finite domain that yields lower bounds for unrestricted SP mechanisms through linear programming dual certificates. For the upper bound, we introduce finite representations of mechanisms, called piecewise-linear attributions (PL attributions), that mix piecewise-linear deterministic mechanisms using affine weights on a triangulation of the report space. We show that for mechanisms represented by PL attributions, checking SP and an approximation guarantee reduces to finitely many quadratic nonnegativity tests over compact polytopes. With exact arithmetic and comparisons, each verification certifies the proposed property or returns locations where it fails. In addition, we introduce a strengthening of the incentive notion called strong strategyproofness. We show that for fixed component mechanisms and regions of a PL attribution, the strong strategyproofness requirement can be expressed by a finite number of linear constraints on the attribution coefficients. Using these theoretical results, we propose a heuristic procedure for computing an upper bound on the approximation ratio. We compute certified upper and lower bounds on several metric graphs and numerically evaluate the proposed search procedure. Lastly, we show that deterministic SP onto mechanisms on graphs are strongly strategyproof and admit PL attributions. Thus restricting attention to strongly strategyproof mechanisms admitting PL attributions loses no deterministic SP onto mechanisms.
We study randomized mechanisms for scheduling indivisible jobs on $n$ unrelated machines. Each machine is controlled by a selfish agent who privately knows its processing time for each job. A mechanism assigns every job to a machine and makes payments. We require truthfulness in expectation: no agent can increase its expected payment minus its expected processing cost by misreporting, regardless of the other agents' reports. The makespan is the maximum total processing time assigned to a machine; the objective is to minimize its expectation. We prove that the optimal approximation ratio is $(n+1)/2$ for every $n\ge7$, relative to the minimum makespan of an integral assignment. The lower bound holds for every $n$ and allows unrestricted computation and arbitrary correlations among assignments, assuming finite expected payments and a guarantee uniform over all finite job counts. The matching mechanism uses correlated rounding and runs in expected polynomial bit time on rational inputs. These guarantees hold for all finite nonnegative processing times. For two machines, we characterize the optimal approximation ratio exactly as an analytic constant, approximately $1.505995705434$, and give a mechanism attaining it. For three machines the optimal ratio is $2$. For four, five, and six machines we obtain upper bounds of $3$, $105/32$, and $29/8$, respectively, compared with the general lower bound $(n+1)/2$. The proofs for $n\ge7$ do not rely on computer-assisted certificates; the two- and three-machine results use exact rational computer-assisted certificates.
The Nisan-Ronen conjecture, a central problem in algorithmic game theory, asserts that no deterministic truthful mechanism for makespan minimization on $m$ unrelated machines can achieve an approximation ratio better than $m$. Christodoulou, Koutsoupias, and Kov\'acs resolved it in 2023, but the optimal approximation ratio achievable by randomized truthful mechanisms remained open. Recently, Anastasiadis, Christodoulou, Koutsoupias, Kov\'acs, and Schecker extended techniques from the deterministic proof to establish a $(3/2-\sqrt{2})(m-1)$ lower bound for universally truthful mechanisms with discrete support and gave a universally truthful mechanism with approximation ratio $m/2+o(m)$. For the broader class of truthful-in-expectation (TIE) mechanisms, however, the gap remained large: the best known upper bound was $(m+5)/2$, while the lower bound was only $2-1/m$. We prove a lower bound of $(m+1)/2$, determining the optimal TIE approximation ratio up to an additive constant as $m/2+\Theta(1)$. Our result also improves the leading constant in the lower bound for universally truthful mechanisms from $3/2-\sqrt{2} \approx 0.0858$ to $1/2$. Together with their $m/2+o(m)$ upper bound, our result determines the optimal approximation ratio for universally truthful mechanisms up to lower-order terms.
Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.
The distortion framework in social choice theory allows quantifying the efficiency of (randomized) selection of an alternative based on the preferences of a set of agents. We make two fundamental contributions to this framework. First, we develop a linear-programming-based algorithm for computing the optimal randomized decision on a given instance, which is simpler and faster than the state-of-the-art solutions. For practitioners who may prefer to deploy a classical decision-making rule over the aforementioned optimal rule, we develop an algorithm based on non-convex quadratic programming for computing the exact distortion of any (and the best) randomized positional scoring rule. For a small number of alternatives, we find that the exact distortion bounds are significantly better than the asymptotic upper bounds established in prior literature and lead to different recommendations on which rules to use. These results rely on a novel characterization of the instances yielding the worst distortion, which may be of independent interest.
For a fixed $\epsilon \ge 0$, let $\rho_{\epsilon, n}$ be the maximum value of $\rho_n$ such that, in every allocation instance with $m$ indivisible goods and $(1 + \epsilon)n$ agents, there is a subset of $n$ agents with the following property. The allocation instance restricted to only this subset of $n$ agents has an allocation that gives each agent at least $\rho_n$-fraction of her $n$-maximin share (MMS). When $\epsilon > 0$ we refer to $\epsilon n$ as the {\em agent redundancy}. The case $\epsilon = 0$ is the standard setting without agent redundancy, and we use $\rho_{0,n}$ and $\rho_n$ interchangeably. For allocation instances with additive valuations, % agents, it is known that $\frac{7}{9} \le \rho_n < 1-\Omega(\frac{1}{\log^2 n})$ for every $n \ge 2$ (with stronger lower bounds for small $n$). It is an open question whether $\rho_n$ tends to~1 as $n$ grows. We show that with agent redundancy, the answer to this question is positive. That is, for every $\epsilon> 0$, $\rho_{\epsilon, n}$ tends to~1 as $n$ grows. A straightforward corollary of this result is that for every $c > 0$, if the number of items satisfies $m \le (2 - c)n$, then the answer is positive also for $\rho_n$ (with no agent redundancy). Adapting our techniques to a related setting, we also improve a recent result of Ezra and Garbuz, and show that without agent redundancy, there always exists an allocation that gives $n - O(\log^2 n)$ agents their full MMS.
The geometry of constraints in variational inequalities (VIs) plays a central role in applications ranging from resource allocation and equilibrium computation to constrained optimization. Yet, its effect on computational complexity has received surprisingly little attention beyond special cases. We examine this question when the constraint set is an $\ell_p$ ball. This family of problems encompasses two of the most extensively studied classes of problems in algorithmic game theory: symmetric bimatrix games for $p = 1$ and multi-player polymatrix games for $p = \infty$. Both of these problems are known to be PPAD-complete even for affine operators. We establish a comprehensive complexity landscape for VIs over $\ell_p$ balls across the full range $p\in[1,\infty]$. First, for any $p\neq 2$, we show that finding an inverse-polynomial approximate VI solution is PPAD-complete even for affine operators. In contrast, for $p=2$, we give a polynomial-time algorithm for affine VIs, extending a classic result of Ye (1992) beyond symmetric operators. On the other hand, once the operator becomes quadratic, we establish PPAD-completeness even at inverse polynomial precision. From a technical standpoint, we develop a new toolkit for exploiting the geometry of the constraint set and the structure of the operator to characterize the complexity of equilibrium and optimization problems, which is of independent interest.
Bankruptcy rules are rules for dividing an insufficient estate among people with different claims. Existing rules assume that the claims are publicly known. When this is not the case, claimants have a strong incentive to claim more than they are due, as bankruptcy rules give larger allocations to claimants with larger claims. A remedy often used by legal systems is to make over-reporting costly by requiring evidence and imposing penalties. But this remedy also increases the legal expenses of proving true claims, which might result in under-reporting. Encouraging true reporting requires fine-tuning of the legal costs. This paper incorporates the costs of supporting both true and false claims into the bankruptcy model. Claimants incur costs for the true and false parts of their claims, with false claims costing at least as much per unit as true claims. The goal is to set cost rates that induce claimants to report their true entitlements, neither more nor less. Whether this is possible depends on the allocation rule. The proportional and constrained equal awards rules cannot guarantee truthfulness at any positive true-claim cost rate; the same holds for constrained equal losses with at least three claimants. For $N\ge2$ claimants, the rule TAL-1/N from the parameterized Talmud family induces truthfulness exactly when the true-claim cost rate is at most 1/N and the false-claim cost rate is at least 1-1/N. This rule is optimal in the sense that its truthful cost region contains that of every piecewise smooth allocation rule: it gives the legal system the maximum possible flexibility in setting the legal costs. For two claimants, TAL-1/2 (aka Contested Garment rule) uniquely attains this optimal region.
We determine the linear-equivalence classes within the two families of full weight spectrum one-orbit cyclic subspace codes. This solves the second open problem posed by Castello, Polverino and Zullo [J. Combin. Theory Ser. A 212 (2025) 106005]. For the first family, the criterion is a fractional linear transformation over $\F_q$ followed by a power of $q$-Frobenius. For the second family, it is an affine transformation over $\F_{q^2}$ together with a power of $q$-Frobenius. We use polynomial spaces over finite fields, the linear-isometry theorem for cyclic orbit codes, and trace duality. The arguments include parameters belonging to proper subfields of the ambient field.
Alternating online mirror descent (AltOMD) is a simple learning rule for zero-sum games, which improves upon simultaneous OMD numerically and theoretically. Previous work obtained $O(T^{1/3})$ and $O(T^{1/5})$ regret bounds for AltOMD, by leveraging modified-energy-function-based analyses. However, settling whether AltOMD achieves near-constant regret has remained an open question. In this paper we resolve the question of whether AltOMD achieves near-constant regret in the affirmative. In particular, we show an $O(log(T))$ regret bound on the sum of the players' external regrets for any two-player zero-sum bilinear game with compact convex strategy sets, under mild regularity assumptions on the regularizers. We verify that our assumptions hold for the negative entropy regularizer, thereby obtaining logarithmic regret for the alternating multiplicative weights updates algorithm. The regret bound also yields an $O(log(T)/T)$ duality gap bound for the averaged strategies.