Papers

Minimum-cost spanning tree game (MSTG) is a cooperative game played on an undirected edge-weighted graph $(G,w)$ representing the network, where each vertex corresponds to a player and each edge has an associated cost~$w$. A distinguished vertex $s \in V(G)$ represents the supply or source. For any coalition of players $S$, the characteristic cost function $c(S)$ is defined as the minimum cost of a spanning tree with respect to $w$, connecting exactly the vertices in $S \cup \{s\}$. In this paper we study the computational complexity of deciding core membership for MSTG. In general, deciding whether a given allocation is in the core is coNP-hard~(Faigle et al.,International Journal of Game Theory,1997). We study the core recognition problem under the name MSTG Core Non-Membership. We extend the hardness to graphs which are very close to being planar. On the positive side, we present several algorithmic results within the framework of parameterized complexity. We show that MSTG Core Non-Membership is fixed-parameter tractable when parameterized by the support size of the allocation. Turning into structural parameters of graphs, we show that the problem admits an FPT algorithm parameterized by treewidth and signed neighborhood diversity. Last but not least, we investigate kernelization. While in general graphs, under standard complexity-theoretical assumptions, MSTG Core Non-Membership does not admit a polynomial kernel parameterized by the vertex cover number, we design a cubic kernel in planar graphs. Furthermore, in general graphs, we obtain quadratic kernel for signed neighborhood diversity and linear kernel for the parameter feedback edge number.

We study gains from trade (GFT) in two-sided matching markets with independent private types and arbitrary downward-closed feasibility constraints. The second-best benchmark is the maximum expected GFT achievable by a Bayesian incentive compatible, interim individually rational mechanism that is strongly budget balanced at every report profile. These constraints generally preclude attaining the first-best GFT and raise the question of how much efficiency must be lost. We prove that the second-best GFT is at least one half of the first-best GFT in every such matching market. This recovers and generalizes the recent $1/2$ guarantee for bilateral trade by Liu et al. (2026) to markets with multiple buyers and sellers and arbitrary downward-closed feasibility constraints. Together with their matching lower bound for bilateral trade, our result establishes a tight worst-case ratio of $1/2$ for this general class of matching markets. Our proof builds on the virtual-GFT framework of Brüstle et al. (EC 2017) to reduce the problem to a one-parameter Lagrangian. The main step is a geometric, edge-by-edge analysis based on first-best edge-selection regions, combined with a randomized contraction in rank space.

The classical perceptron cycling theorem of Block and Levin \cite{BlockLevin1970} bounds correction sequences whose selected updates come from a finite set and have nonpositive inner product with the current state. We prove a robust variant for additive trajectories $z_{k+1}=z_k+u_k$, for all integers $k\geq0$, with increments in a finite set $U\subset E$, where $E$ is a finite-dimensional real inner-product space and $0\in\conv U$. Let $A\colon E\to E$ have positive-definite symmetric part, without requiring symmetry, and let $B\geq0$. If each $u_k$ is a $B$-approximate minimizer of $u\mapsto\ip{Az_k}{u}$ over $U$, then $\sup_{k\geq0}\norm{z_k}\leq C(1+\norm{z_0}+B)$, with $C=C(E,U,A)$ independent of the initial state, $B$, and all admissible update choices. We derive two algorithmic consequences. The first is an $O(k^{-1})$ last-iterate norm bound for harmonic vertex-returning Frank–Wolfe for affine strongly monotone variational inequalities on polytopes with relatively interior solutions. It extends the quadratic Frank–Wolfe/herding guarantee of Bach, Lacoste-Julien, and Obozinski \cite[Section~4.2]{BachEtAl2012} to nonsymmetric affine operators. The second consequence concerns oblique relaxation for linear inequalities. Greedy corrections through a fixed matrix with positive-definite symmetric part remain bounded even for inconsistent systems. In particular, for a square matrix $G$ with positive-definite symmetric part, repeatedly increasing the coordinate corresponding to a most-violated inequality of $Gx\geq b$ terminates at an exactly feasible point after finitely many unit corrections. This remains true under bounded additive selection errors, provided the stopping test uses the true inequalities.

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

We study a fractional assignment setting where $n$ objects are to be assigned to $n$ agents with unit capacity, and each agent specifies an ideal distribution over the objects. Unlike in classic random assignment, these ideal distributions are not necessarily degenerate, as agents may prefer a mixture of objects rather than any single object. We assume that agents seek to minimize the $\ell_1$ distance between their ideal distribution and the distribution they receive, which is equivalent to maximizing the overlap between the two distributions. We propose two mechanisms, one based on water filling (WF) and the other on quadratic programming (QP), and show that both mechanisms are utilitarian-optimal (and hence Pareto efficient), envy-free, strategyproof, and satisfy equal treatment of equals. Moreover, we highlight a distinct advantage of each mechanism: while the WF mechanism satisfies the stronger property of group-strategyproofness, the QP mechanism is more robust in terms of egalitarian overlap welfare.

The COVID-19 pandemic has had profound impacts on global health, social structures, and economies. It disproportionately affected lower socioeconomic groups and those reliant on interaction-based jobs. Regulatory bodies faced the challenge of designing policies that preserve public health while limiting disruption to economic stability and productivity. Epidemiological models such as SIR and agent-based models (ABMs) have been used to study disease dynamics and the socioeconomic impacts of disease and interventions. Population-level models often simplify individual heterogeneity, while detailed ABMs can become computationally expensive as the numbers of agents and interactions increase. We propose ABM-SIRTEM, a hybrid model that incorporates occupation categories, economic productivity, and welfare at the individual level while dynamically modeling compliance with government interventions. We calibrate the model against historical positive and negative test counts from four U.S. states and examine the resulting compliance dynamics. This framework provides a basis for studying the interaction between disease spread and socioeconomic behavior in pandemic-response planning.

Uniformly rotated coordinate-wise median chooses a random orthonormal coordinate system, takes a median in each coordinate, and maps the resulting point back to the Euclidean plane. We determine its exact worst-case expected approximation ratio when social cost is the $L_p$ norm of the agents' Euclidean distances and $1<p<2$. The ratio is \(\frac{2^{2-1/p}}{\pi}\int_0^{\pi/2}(\cos^p\theta+\sin^p\theta)^{1/p}\dd\theta\). This expression was previously established as a lower bound by Chan, Lin, and Wang; our contribution is the matching upper bound. The proof establishes a strengthened coordinate-wise median inequality relative to an arbitrary reference point. Its right-hand side is linear in a sum of direction-dependent norms, which permits direct averaging over rotations without the loss incurred by passing through a $p$th-moment bound. We give all auxiliary inequalities and a self-contained proof of tightness using the established two-cluster-and-outlier construction. The upper bound holds for every finite profile and every measurable choice within the coordinate median intervals, while odd-size profiles suffice for the matching lower bound. The result characterizes this fixed mechanism, rather than the optimal approximation ratio among all randomized strategyproof mechanisms.

Through long-term observation and time series analysis of Bitcoin and Ethereum, we found the similarity in long-term consistent price trends, especially in the weekly K-line. We denoised and smoothed the historical data of their prices, and further derived the periodicity of their price change trends and the timing of buying and selling. We have for the first time proposed that the full application of central bank digital currencies (CBDC) is a key signal for investors to reduce their holdings of cryptocurrencies or even exit the market. In addition, we proposed momentum opening/closing prices to replace the traditional nominal opening/closing prices to accurately describe the price trends of the 24/7 financial trading market. We found that the cryptocurrency market can be regarded as a relatively independent financial market, thereby designing a safer and more efficient arbitrage strategy.

Moving from geographically fragmented to pooled waiting lists in deceased-donor organ transplantation can improve efficiency, but it raises concerns about regional fairness and participation incentives. This paper studies Pareto gains from such transitions in a multi-class queueing model with impatient agents, perishable items, and a tractable homogeneous compatibility friction. Unlike standard approaches that focus on static match quality or ignore regional incentives in dynamic settings, our analysis identifies dynamic risk pooling as the main source of Pareto improvements for regions: pooling reduces organ waste due to stochastic supply-demand fluctuations, temporal mismatches, and random compatibility outcomes. Although this dynamic surplus theoretically permits Pareto improvements, a purely utilitarian policy that treats all patients equally across regions often fails to deliver them when regions are asymmetric. In such cases, utilitarian redistribution extracts too many organs from high-supply regions and violates their participation constraints. To resolve this conflict, we show that the set of achievable utilities can be described by mixtures of static priority index policies. Building on this structure, we propose the Constrained Pareto Frontier Search (CPFS), a polynomial-time procedure that computes an approximately optimal allocation policy with arbitrarily small participation-constraint violations. The results suggest that, by adjusting priority indices to keep redistribution within the gains from pooled supply, demand, and compatibility risk, policymakers can attain global efficiency while preserving local participation incentives.

Travel demand forecasting is essential for evaluating large-scale infrastructure projects, yet the traditional sequential four-step process can produce inconsistencies across trip distribution, mode choice, and traffic assignment. Although combined models address these inconsistencies, their practical use has been limited by simplified behavioral assumptions, computational burden, and the lack of a unified parameter-estimation framework. We propose a convex programming approach that integrates destination, mode, and route choices within a hierarchical extended logit model. The optimal primal solution characterizes the joint travel-demand equilibrium, while the optimal dual variables recover taste coefficients, alternative-specific constants, and destination- and mode-level scale parameters. The model captures mode correlations through nested logit and route overlap through path-size logit. Its convex structure provides global optimality guarantees and enables efficient solution using off-the-shelf conic solvers. Observed travel patterns are incorporated through moment and conditional-entropy constraints, while the route-level dispersion parameter is calibrated separately using partial link counts. Numerical experiments on eight benchmark networks demonstrate the scalability and computational efficiency of the formulation.

The matroid secretary problem asks an online algorithm to select a high-weight independent set from elements arriving in uniformly random order, with immediate and irrevocable decisions. Singla (2026) recently gave a $4$-competitive algorithm for arbitrary matroids using only the number of elements and independence queries on already-arrived elements. Following his approach of maintaining a dynamically updated reference set, we introduce random deletions and a time-dependent acceptance rule, improving the competitive ratio to $C_*\approx3.1462$ in the same information model, where $C_*-\log C_*=2$. Our ordinal algorithm accepts every element of a fixed canonical optimum with probability exactly $1/C_*$ and uses $O(n^2)$ independence queries. The algorithm maintains a greedy reference solution, protects only accepted elements, and randomly deletes unaccepted reference-basis elements. A time-dependent acceptance rule makes the accepted set, conditional on the reference set, an independent thinning of its greedy basis. The resulting guarantee has a direct analytic proof.

This paper investigates market competition among wireless service providers (SPs) that serve customers using shared spectrum. Prior work has analyzed such markets through models of competition with congestible resources, capturing both the congestion-sensitive nature of wireless spectrum and the effects of spectrum sharing on service quality. These models typically assume that the market demand function is known, enabling SPs to optimize pricing or quantity decisions under either Bertrand or Cournot competition. In contrast, we consider a setting in which the demand function is initially unknown and must be learned over time. We model this learning process using multi-agent reinforcement learning (MARL), allowing competing SPs to learn market dynamics while adapting their competitive strategies. Although MARL has shown strong performance in a variety of economic settings, recent work has demonstrated that it can also give rise to tacit collusion among self-interested agents. We therefore examine whether similar collusive behavior emerges in shared-spectrum markets and how its prevalence depends on the mode of competition (price versus quantity) and the choice of MARL algorithm. Our results provide insight into the interaction between learning dynamics, market structure, and spectrum sharing, with implications for both wireless market design and the deployment of learning-enabled decision-making systems.

This paper is the first work at the intersection of game theory and property testing, giving algorithms and lower bounds for efficiently testing whether an allocation mechanism is incentive compatible (IC). We propose distinguishing whether a mechanism is $\epsilon$-far from being IC, i.e., when it observes many monotonicity "violations." Conceptually, inspired by the literature on Boolean function monotonicity testing, we construct a tester for discrete single-parameter allocation rules. Technically, our work is the first to consider monotonicity testing of vector-valued functions on the hypergrid. We give a $\tilde{O}(n/\epsilon)$-query algorithm to test whether a function (representing n-player allocation mechanisms) is coordinate-wise monotone versus $\epsilon$-far from it. We also show a matching lower bound: the class of coordinate-wise monotone vector-valued functions on a Boolean hypercube or hypergrid requires $\tilde{\Omega}(n/\epsilon)$ queries to test whether it is $\epsilon$-far from monotonicity, and this holds even if the tester is two-sided and allowed to make adaptive queries. Finally, we extend our upper bound to and give a tester of the same query complexity for pricing functions of allocation mechanisms. This requires overcoming the technical challenge that the path in function space to the closest IC mechanism may involve interdependent changes to both the price and the allocation rule.

At edge price $\alpha=1$, we construct an infinite family of pure Nash equilibria of the unilateral max-distance network creation game with $\PoA\ge2^{\sqrt{\log_2 n}-O(\log\log n)}$. Together with the known upper bound, this gives $2^{\Theta(\sqrt{\log n})}$ along the constructed sequence of population sizes. We subdivide every edge of the bipartite double cover of a distance-uniform graph with large diameter constructed by Lavrov, Loh and Messegué, and let each subdivision vertex buy its two incident edges. A distance calculation rules out every profitable unilateral deviation. The equilibria are not strict. We also give a short proof that the price of anarchy is constant for every polynomially vanishing edge price.

We study online allocation problems where $n$ requests over $m$ resources arrive in an adversarial order and must be served immediately and irrevocably. This framework captures both Online Resource Allocation, where the goal is to maximize value subject to resource budgets, and Online Load Balancing, where the goal is to minimize the makespan. We seek $(1\pm\epsilon)$-competitive algorithms in the large-budget or large-makespan regime. We consider a sampling model that generalizes the following two well-studied sampling models. In the Single-Sample Prophet Inequality ($\mathsf{SSPI}$) model, request $t$ is drawn from an unknown distribution $\mathcal{D}_t$, and the algorithm is given one independent sample from each $\mathcal{D}_t$ before the online phase. In the $p$-$\mathsf{Sample}$ model, the requests are adversarial, but a uniformly random $p$-fraction is revealed upfront as training data. Although near-optimal algorithms are known in the easier random-order model ($\mathsf{RO}$), where the requests arrive in a uniformly random order, prior algorithms for $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$ were problem-specific and incurred substantially worse dependencies on $\epsilon$, $m$, and $n$. Our main contribution is a general framework that converts $\mathsf{RO}$ algorithms into algorithms for the $p$-$\mathsf{Preview}$ model, a model that generalizes both $\mathsf{SSPI}$ and $p$-$\mathsf{Sample}$. As consequences, we obtain near-optimal bounds for Online Resource Allocation, generalized Online Load Balancing, and online mixed packing-covering problems in these adversarial-order sampling models, significantly improving the bounds of [Ghuge, Singla, Wang (STOC'25)] and [Gupta and Molinaro (SODA'26)].

We study an optimal intervention problem for linear threshold models. This is a popular class of dynamical network systems whereby a number of agents, identified with the nodes of a graph, strategically change their binary action (0 or 1) according to a threshold rule. Specifically, an agent adopts action 1 if and only if the fraction of its neighbors in the interaction graph that do so is greater than or equal to a prescribed threshold. Assuming that a planner can modify the agents' thresholds at a cost equal to the aggregate threshold increase, we study the minimum intervention cost needed to ensure global convergence to the all-1 configuration. Our main contribution is the introduction of a new graph-theoretic quantity, called oriented path number, that is the minimum number of disjoint paths needed to cover the graph that can be oriented to form a directed acyclic graph. When thresholds are all equal to 1/2, the optimal cost is shown to coincide with the oriented path number, whereas, in the general case, it turns out to be the main ingredient of a bound on the optimal intervention cost.

We give deterministic and uncoupled learning dynamics for finite multiplayer general-sum games under full-information feedback that achieve constant individual swap regret in self-play, independent of the horizon $T$. With $n$ players and at most $m$ actions each, every player's individual swap regret is $O(\sqrt n\,m\log m\log^{5/2}(nm))$ at every finite horizon. The dynamics use the classical Blum-Mansour framework with optimism. Each player predicts the deviation gains, uses these predictions to update a row-stochastic transition matrix, and plays its stationary distribution. Our new ingredients include a tailored row normalization map and a two-scale higher-order predictor. An adversarially robust variant, obtained through a generic common-prefix switching wrapper, preserves the self-play bound up to a universal constant and guarantees individual swap regret at most $7\sqrt{mT\log m}$ in the adversarial setting.

Sequential deliberation is a mechanism for collective decision making: at each round, a uniformly randomly selected pair is asked to revise a collective outcome, which then becomes the input for the next round. Existing theory by Fain et al.~\cite{fain2017sequential} treats the current outcome solely as the disagreement alternative in bargaining. Yet the existing outcome might also carry social influence and anchor participants' positions toward the status quo. In this paper, we introduce anchored sequential deliberation. At each round, two participants with bliss points $U$ and $V$ shift their positions toward the previous outcome $O_{t-1}$ with anchoring strength $0\leq \lambda<1$. They then bargain using $O_{t-1}$ as the disagreement alternative. For the sake of analysis, we assume that the decision space is one-dimensional, the anchoring effect is linear, and participants use Nash bargaining. The update simplifies to $O_t=(1-\lambda)Med\{U,V,O_{t-1}\}+\lambda O_{t-1}$. Our analysis reveals a trade-off. Through a coupling of two outcomes, we find that the process contracts in $1$-Wasserstein distance with a factor of at most $\frac{1+\lambda}{2}$, which implies that stronger anchoring slows mixing. On the other hand, stationary distortion weakly decreases with $\lambda$, although the worst-case distortion remains $\frac{1+\sqrt{2}}{2}$ for every feasible $\lambda$. We also identify a unique deliberative fixed point, at which the expected movement is zero, and prove that the stationary distribution concentrates around it as $\lambda$ increases. For symmetric populations, we further provide a tighter bound on the stationary variance around this fixed point. For the uniform distribution, we establish upper and lower bounds on stationary distortion, both of which approach $1$ as $\lambda$ increases.

The return-on-investment (ROI) constraint is central to many auctions, particularly in online advertising, where a bidder is unwilling to pay more than a fixed fraction of the value obtained. We study truthful and revenue-maximizing auctions for ROI-constrained bidders. We first characterize truthful auctions when both valuations and ROI constraints are private, showing that the allocation rule uniquely determines the payment rule. Building on this characterization, for multiple bidders we introduce $\sigma$-increment mechanisms that resemble Myerson's optimal mechanism~\cite{journals/mor/Myerson81}; as $\sigma$ vanishes, these mechanisms become asymptotically optimal among deterministic truthful mechanisms, and their revenue approaches at least a $1/\bar r$ fraction of the optimal expected revenue over all truthful mechanisms, where $\bar r$ is the largest possible ROI constraint. In the single-bidder setting, we prove that every truthful auction can be replaced by a convex pricing function with weakly higher payments for every type, and we derive the optimal pricing functions when either the valuation or the ROI constraint is public.

In social dilemma games, additional rewards or punishments have been studied as means of promoting cooperation. Therefore, it is important to investigate the ideal situation, in which such an additional payoff would change the game. In this study, we investigated the symmetric solution of the Bellman optimality equation for a repeated harmony game. The calculations showed that three types of symmetric solutions exist. One of them corresponds to the trivial All-C strategy, and another to the Win-stay Lose-shift strategy of the prisoners dilemma game. The nontrivial behavior of the strategy corresponding to the last solution is also discussed in detail. In addition, we numerically investigated which strategy the agents actually learn by the reinforcement learning algorithm.

This paper extends the fixed-point bundle framework for finite-dimensional variational inequalities (VIs) from the simplex domain to the product-of-simplex domain, which is directly applicable to solving Nash equilibria. The fixed-point bundle for VIs on the product-of-simplex domain reveals a composite fiber bundle structure. The key innovation is to construct an equivalent VI on the simplex domain and establish the equivalence between the two fixed-point bundle frameworks via a fiber bundle isomorphism. Exploiting this geometric equivalence, the predictor-corrector path-following algorithm for the VI on the product-of-simplex domain is shown to inherit the convergence guarantee of the simplex-domain framework, namely, global convergence with linear gap reduction near solutions. Numerical experiments on 5600 randomly generated instances with dimensions ranging from 2-player 128-action to 128-player 2-action demonstrate robust performance. The algorithm converges in every tested instance.

We study participatory budgeting with additive utilities. We introduce a selection rule based on utility-weighted harmonic entropy and a cost penalty, and prove that it returns budget-feasible outcomes satisfying core-up-to-one.

The maximin share (MMS) guarantee has become one of the central fairness benchmarks for allocating indivisible items. Since Kurokawa, Procaccia and Wang~[EC'14, JACM'18] showed that exact MMS allocations need not exist, a substantial literature has developed around the existence and computation of approximate MMS allocations, including the recent work of Heidari, Kaviani, Seddighin, and Shahrezaei [SODA'26]. In contrast, a basic complexity question posed more than a decade ago by Bouveret and Lemaître [JAAMAS'16] has remained unresolved: how hard is it to decide whether an exact MMS allocation exists? For additive valuations, Lonc and Truszczynski [JAIR'20] showed that the problem belongs to the class $\Delta_2^P$ (also known as $P^{NP}$), but no hardness result was known. For the more general class of 2-additive valuations, Bouveret and Lemaître established NP-hardness, leaving a substantial gap to the $\Delta_2^P$ upper bound. Moreover, the complexity of MMS existence for additive and $k$-additive valuations was posed as open questions. For additive goods, we prove that deciding the existence of an MMS allocation is $\Delta_2^P$-complete, settling the complexity of this longstanding problem. We also prove weak coNP-hardness for three agents, thereby establishing a precise dichotomy with the known existence guarantee for two agents, and strong coNP-hardness when the number of agents is unrestricted. Moreover, the strong hardness construction produces an inverse-polynomial gap in the optimal MMS approximation ratio, ruling out an FPTAS for approximating this ratio unless P=NP. We conclude by showing that all these results for goods extend to the chores setting through a polynomial-time transformation that preserves MMS existence.

Long-running AI agents create a control problem: each action they take changes the state, which in turn affects the trajectory of future actions. If the agent is not fully aligned, then guaranteeing safety requires approving consequential actions before allowing them to be executed. But requiring human approval at every step makes attention a bottleneck. Delegating review to other AI agents raises the same alignment problem: the reviewers may themselves be misaligned. We identify a condition on a reviewing panel that is weaker than individual alignment yet necessary and sufficient for a guarantee that the principal fares at least as well in expectation as under a designated baseline policy. Each reviewer agent reports whether an action proposal made by a proposer agent improves its own utility relative to the baseline. We show that a threshold rule tolerating $k$ disapprovals is safe exactly when, after any $k$ reviewers are removed, the principal's utility can be written as a nonnegative combination of the remaining reviewers' utilities, plus a term that is nonnegative on every feasible proposal. We call this property $k$-robust coalitional alignment. The characterization lifts to sequential control: in a discounted MDP with an arbitrary proposer agent, safety at every state is both necessary and sufficient for the induced policy to match or improve on the baseline. When reviewers vote strategically, full-panel coverage in reward-function space guarantees that every Nash equilibrium is safe under the unanimous approval rule; in contrast, more permissive thresholds can admit unsafe equilibria even when reviewers are individually aligned. Experiments with existing reviewer models show that collective review can remain sound without an aligned individual, even when some disapprovals are tolerated.

We study the fair division of indivisible goods under pure differential privacy, continuing the line of work initiated by Manurangsi and Suksompong. For $n$ agents with nonnegative additive utilities over $m$ goods and a fixed privacy parameter, we give an entry-private algorithm that, with high probability, achieves consensus envy-freeness up to $O(\sqrt n+\log^3 m)$ goods. This substantially improves the dependence on $n$ over the previous $O(n\log m)$ guarantee for ordinary envy-freeness, while providing the stronger consensus guarantee. A key ingredient is a private algorithm for multicolor discrepancy, which may be of independent interest. Our algorithm may require exponential time. We also obtain substantially stronger guarantees under additional structure: when all item values belong to a public alphabet of size $D$, we give a polynomial-time entry-private algorithm achieving ordinary envy-freeness up to $O(\operatorname{polylog}(mD))$ goods with high probability. Finally, we prove an $\Omega(\log n)$ lower bound on the number of goods that must be removed to achieve ordinary envy-freeness under entry privacy, for sufficiently many goods, even with binary utilities.

We revisit reconfiguration in the fair allocation of indivisible goods, where the goal is to transform one fair allocation into another through a sequence of exchanges while preserving fairness at every step. Our focus is on the hierarchy of envy-freeness up to $k$ goods (EF$k$). We show that for any fixed $k$, two EF1 allocations with the same size vector need not admit a reconfiguration path whose intermediate allocations satisfy EF$k$. This impossibility persists even when the two allocations arise from standard EF1 approaches: the envy cycle elimination algorithm or the maximum Nash welfare solution. In contrast, we prove that allocations with the same size vector produced by recursively balanced picking sequences, including round-robin, are always connected via a path that maintains EF2. We also show that deciding whether an EF1 reconfiguration path exists is NP-hard for any fixed number of agents. Furthermore, we complement these exchange-based results by studying a more permissive model that also allows transfers, establishing additional connectivity guarantees.

We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a good or a chore by different agents. We focus on the fundamental fairness notion of proportionality. Since proportional allocations need not exist in this setting, we allow monetary subsidies to restore proportionality while minimizing the total subsidy. When each item's (dis)utility is bounded by 1, a total subsidy of at least \tau(n) \approx n/4 may be necessary. For goods-only or chores-only instances, the best previously known upper bound was n/3-1/6 due to Wu and Zhou~(2024). We close this gap by proving that a total subsidy of at most \tau(n) always suffices, thereby establishing the tight subsidy bound. Our results hold even in the more general setting of weighted mixed manna, resolving an open question posed by~Wu et al. (2023) and Garg et al. (2026). The allocation also satisfies weighted proportionality up to one item (WPROP1). Our proof develops a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) fixed-point theorem, extending the KKM framework to share-based fairness notions. Finally, we design a polynomial-time algorithm to compute such allocations for any fixed number of agents.

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let $d$ be the dimension, $K$ be the menu size, and $T$ the time horizon. For $2\le K\le d$, we prove an upper bound $\widetilde O(K^{1/4}\sqrt{dT})$. When $T\ge d^2$, we further prove a lower bound $\Omega(K^{1/4}\sqrt{dT})$. Thus, for $T\ge d^2$ and $2\le K\le d$, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on $K$ is optimal. Compared with the previous $\widetilde O(\sqrt{dKT})$ bound, our upper bound improves the dependence on $K$ by a factor of $K^{1/4}$. For $K\ge d$, we prove an upper bound $\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)$ and a lower bound $\Omega\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)$. Here, $\widetilde O_{d,T}$ omits logarithmic factors only in $d$ and $T$. In particular, for polynomially large $K\ge d$, the upper and lower bounds both scale as $d^{3/4}\sqrt T$ up to logarithmic factors, improving the standard $\widetilde O(d\sqrt T)$ rate by a factor of $d^{1/4}$. As $K$ grows further, the regret smoothly recovers the $d\sqrt T$ scale once $\log K$ reaches order $d$.

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-\Omega((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall, an exponential improvement on the logarithmic scale of $n$. For chores, we construct instances in which every allocation gives some agent cost at least a $1+\Omega((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.

We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $\alpha$-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error $\alpha$. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov $\alpha$-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.