Papers

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

We show that computing a Nash equilibrium is CLS-complete for linear network congestion and network coordination games. As a result, finding a KKT point of a bilinear polynomial is CLS-complete.

We often learn from multiple sources that convey information in different ways. How informative is it to know the source of a signal, and how is this informativeness shaped by the distribution of sources? We extend the standard (binary-state, binary-signal) Blackwell experiment model by introducing a commonly known distribution over signaling schemes, representing the distribution of information sources. We compare learning under two information models: source-aware, where decision makers observe a signaling scheme and its realization (e.g., raw reviews, search results), and source-blind, where only the signal realization is observed (e.g., aggregate ratings, LLM-generated summaries). We show that a mean-preserving spread in the distribution of signaling schemes translates into Blackwell dominance for source-aware decision makers, implying they are "risk-loving" in information sources. In contrast, it has no impact on source-blind decision makers. When learning from repeated draws of signaling schemes, source-blind decision makers learn more slowly. However, as long as the average signaling scheme is $\varepsilon$ away from being completely uninformative, source-blind learning can match source-aware learning by using at most $O(1/\varepsilon)$ times more data.

General Game Playing across arbitrary games from rules alone remains challenging due to differing algorithmic requirements across game classes and strict decision-time constraints. Rather than hand-designing search heuristics for specific domains, can we leverage Large Language Models (LLMs) to discover general game-playing algorithms? Because language models can propose and refactor structured code, they provide an expressive proposal engine for exploring the space of algorithmic designs. We introduce a multi-agent LLM meta-learning system to co-evolve game-agnostic procedural search mechanisms in C++ alongside domain heuristics synthesized directly from game rules. Controlling the compute budget, we benchmark the discovered mechanisms across more than 400 diverse environments, including OpenSpiel training and held-out games, procedural simulation engines, and games with deep neural policy-value representations trained via PPO. Evaluated via AlphaRank stationary distributions and Soft Condorcet Optimization (SCO) against 15 established MCTS baselines, the discovered search mechanisms consistently achieve top-tier ratings and pairwise ballot majorities over most baselines across independent evolutionary runs, generalizing to unseen human-designed and procedurally synthesized games and remaining competitive with baselines on frozen neural network representations.

Market microstructure studies how trading rules turn orders into prices and allocations. Those rules have been rebuilt repeatedly: for floor traders, electronic limit order books and high-frequency trading, batch auctions and dark pools, blockchains run by automated market makers and block builders, and now AI agents that discover, pay for, and compete over resources. This survey traces that evolution through one question: can a market allocate scarce goods efficiently and fairly without participants revealing everything they know and want? Each technological shift moved the binding constraint of market design from trader rationality to speed, to control over transaction ordering, to the dimensionality of what participants can report. Impossibility results persist; only their cost moves. We review evidence on high-frequency trading, trading venues, automated market makers, extractable value and algorithmic collusion, and identify allocation as the missing layer of the agent-commerce protocol stack.

Learning from human preference data is the dominant route to aligning language models with human values. In linear social choice, where rewards are linear in a fixed feature representation of prompt-response pairs, Ge et al.[2024] show that fitting such a reward by minimizing any non-decreasing convex loss, including BTL, fails PO and PMC. Moreover, no rule that reads only the majority relation can satisfy PO once the output is required to be linearly induced. We ask what it costs to enforce these axioms anyway. To this end, we relax the linear model to allow per-candidate slack. We compute the relaxed linear reward with the smallest total slack that satisfies the axioms with a margin $\eta$, the minimum required difference between two reward values. Our solution satisfies the axioms under no assumptions about the voters or how comparisons were collected. We bound the optimal total slack by $O(1)$ when $\eta$ is at most $O(\frac{1}{m^2})$ for $m$ candidates. Furthermore, we exhibit an instance that forces this bound, concluding that the rate is tight up to constants. In practice, the no. of candidates far exceeds the feature dimension, and only a linear reward can be evaluated on unseen responses. We therefore introduce a new method that charges the linear part for each comparison it gets wrong. It simultaneously minimizes the total slack and the no. of violations, with a parameter $\lambda$ trading off between them. We show that the total slack is monotone but saturating in $\lambda$: raising it reduces the violations of the deployed linear reward and increases the slack, yet the slack stays below $(\eta+\Delta\sqrt{d})\lfloor m^2/4\rfloor$, where $\Delta$ and $d$ are the diameter and dimension of the features, respectively. Experiments on both synthetic and real-life preference data corroborate our theory and show that the linear reward output by our method beats linear BTL.

Single-token typed-decision models answer a schema question by reading the logits of a few one-letter answer codes at a single position: they are fast and return a probability for every allowed answer, but they are trained with plain cross-entropy that ignores most of the structure in their training data. We study such a model whose data is curated as contrastive pairs—two contexts that differ in one edited fact that flips the answer—each carrying a machine-checked certificate that deleting the decisive sentence makes the fact unknown. We propose PACT, which turns this structure into four training terms that need no new annotation: a difference-in-differences margin over each pair that is invariant to any shared logit offset, a permutation-consistency term against answer-code position bias, an evidence-necessity term on certificate-verified ablated contexts, and an ordinal transport cost for rubric fields, plus a three-parameter contextual temperature. On a frozen 324-item holdout with three seeds, PACT matches the published recipe in accuracy ($84.6\%$ vs. $85.2\%$; McNemar $p \ge 0.50$ at every seed) while giving the lowest position bias of all runs (answer flips under relabelling $9.8\%$ vs. $13.8\%$) and the lowest ordinal error on rubric fields (MAE $0.232$ vs. $0.311$). Against a control with the same optimiser and schedule but cross-entropy only, PACT is significantly more accurate at two of three seeds, halves the seed-to-seed spread and lowers NLL by $26\%$. Seed-matched ablations and pre-specified falsification tests locate these gains precisely: no single term raises raw accuracy, and the method's value lies in robustness and stability rather than headline accuracy. Code, data splits, trained adapters, and all run records are available at https://github.com/BennyLinntu/PACT-Pairwise-Anchored-Calibrated-Tuning-for-Single-Token-Typed-Decisions.

Alternating gradient descent-ascent (AltGDA) is a simple and practically effective method for solving finite two-player zero-sum matrix games. However, the theory of AltGDA remains limited: existing results either apply only to unconstrained settings or require restrictive assumptions on the equilibrium in constrained settings. We show that AltGDA converges globally at an $O(1/T)$ ergodic rate in every finite two-player zero-sum matrix game. Unlike prior results, our guarantee holds for every initialization and every horizon $T$: the uniform averages of the AltGDA iterates satisfy an $O(1/T)$ duality-gap bound. Our proof is inspired by numerical results obtained using a novel performance estimation programming (PEP) framework for Lyapunov function search over compact convex sets. Additionally, we provide simple counterexamples showing that the last-iterate duality gap of AltGDA does not converge to zero. This justifies why averaging of iterates is indeed necessary to achieve an $O(1/T)$ rate. We have formalized and machine-checked our global ergodic convergence result in Lean 4.

A pricing page can walk the posted price up to the last amount a buyer still accepts, a recommender can hold back a better item for a barely acceptable promoted one, and a classifier can shift its boundary once applicants change their features. The system predicts the response and then picks the menu that serves its own objective, so the surplus above the user's cutoff is taken. Playing the single best action publishes that cutoff, while noise on actions the user would never take throws away payoff and teaches the platform that a worse menu is still acceptable. We study unpredictable near-optimal policies (UNOP), which mix uniformly on near-best actions that remain individually rational. The mixture is a commitment about the response. On a finite price grid, when the best sure-demand price strictly out-earns the randomized band, a seller who already knows the curve posts below the band, and the purchase that occurs is deterministic. Knowing that curve is not the same as predicting the next draw. The mixture can be learned and the optimizer can match its best response, while the user's payoff stays higher because the mixture changes which action is targeted. In pricing and in policy-aware recommendation this leaves more surplus than greedy play when the platform optimizes against the curve and more than one action is acceptable. The gain goes away under quality ranking, a singleton near-optimal set, a wrong utility estimate, or a short-horizon explorer. That is also where mixing should be turned off if the other side is trying to cooperate.

In this paper, we prove the existence of an envy-free up to one item (EF1) division for a discrete chore. Our approach builds on the powerful framework of Simmons-Su, which leverages Sperner's lemma to guarantee the existence of a simplex corresponding to a sequence of similar fractional divisions, ensuring that each agent is satisfied with a different bundle. Bilò et al. [2022] introduced a rounding technique that converts the fractional divisions into a connected integral EF1 division for goods when there are at most four agents, and this method was later extended by Igarashi [2023] to accommodate any number of agents. However, these rounding techniques for goods do not directly apply to chores because the definitions of EF1 differ in the two settings. To overcome this asymmetry, we modify the existing rounding techniques and show that connected EF1 divisions exist for a discrete chore.

Artificial Intelligence as a Service (AIaaS) composition is an emerging research area that enables clients to combine multiple AI services to meet complex requirements. A recent extension of this paradigm is collaborative AIaaS composition, where multiple AI services are combined to create a unified solution. Research in this field requires datasets with service descriptions, composition requests, and corresponding composition solutions. However, no dataset contains all this information specifically for collaborative AIaaS composition. Existing datasets target traditional web services or sequential AI workflows and lack the AI-specific attributes required for realistic collaborative composition. To address these challenges, we present a collaborative AIaaS composition dataset containing 25,900 AIaaS services from multiple providers across 12 AI task families, along with 10,000 collaborative service requests. We further develop a Multi-Armed Bandit (MAB)-based collaborative composition algorithm that determines the composability of candidate service combinations prior to composition. Experimental results demonstrate that the dataset supports realistic collaborative AIaaS composition evaluation and related research in service recommendation, selection and QoS prediction. The dataset and implementation are publicly available at: https://github.com/deepakkanneganti9/CAIaaS

We study equilibrium joining strategies in an M/M/1-type queueing system with strategic customers operating in a two-phase random environment described as a continuous-time Markov process. Strategic customers, upon arrival, choose whether to join or to balk based on available information and anticipated utility, considering the trade-off between reward from service and waiting cost. Four observation scenarios are analysed: fully observable (both queue length and environment phase are disclosed to a customer upon arrival), queue-only observable, environment-only observable, and fully unobservable. In each case, equilibrium joining strategies are analysed. In the environment-only observable and fully unobservable cases, explicit solutions and equilibrium conditions are derived under rapid oscillations and under very slow transitions between environment phases.

We study the reallocation of indivisible objects among agents who may hold initial endowments and may be indifferent between objects. Each agent has her own set of admissible objects, and a matroid constraint specifies which combinations of assigned objects are feasible. The model contains the housing market, house allocation with newcomers who hold no endowment, and the assignment of students to schools under matroidal constraints at each school. For this model, we introduce the top-class trading cycles mechanism (TCTC), which extends the top trading cycles mechanism (TTC) to matroid constraints and weak preferences. When a trading cycle is selected, TCTC fixes each agent's top indifference class rather than a specific object and postpones the choice within the class to the end. TCTC is individually rational, Pareto efficient, and weakly group-strategy-proof on the full domain of weak preferences, and it runs in polynomial time. When preferences and reports are strict, TCTC is strongly group-strategy-proof. Together with a known impossibility result, our theorem establishes a maximal domain of school-by-school constraints for individual rationality, Pareto efficiency, and strategy-proofness.

We study the problem of fairly allocating $m$ indivisible goods among $n$ agents who arrive online, under the notion of maximin share (MMS) fairness. Fair allocation with online arrivals is notoriously challenging: prior work achieves constant-factor MMS guarantees only when agents' preferences belong to a set of valuation functions known in advance, while no guarantees were known without such prior information. We develop a new randomized online algorithm for additive and submodular valuations, that we call Single-or-Sample, and that achieves a constant-factor approximation to MMS simultaneously for all agents, with constant probability. The algorithm requires no prior knowledge about the agents' valuations, and works against adversarial (oblivious) inputs. We further establish a fundamental tradeoff between approximation and success probability. Specifically, for any $c \ge 1$, no online algorithm can guarantee a $1/c$-approximation to MMS with probability exceeding $1 - 1/c^2$, even for binary additive valuations. This rules out constant MMS with probability asymptotically closer to $1$ than a constant. For XOS, the lower bound is much stronger: no algorithm can achieve even $1/\log\log n$-MMS to all agents with a constant probability. We complement this lower bound with an algorithm for the regime $c\in \Omega(\log n)$, namely $1/c$-MMS to all agents with probability $(1-O(1/c))$, and show that this tradeoff is tight for XOS. Our constant-factor algorithm introduces several new ideas, combining greedy submodular maximization with randomized allocation and single-item reduction. A key technical ingredient is a new approach for analyzing iterative sampling without replacement. We develop concentration bounds that apply to a broad class of adaptive processes with complex dependencies across elements and rounds, which may be of independent interest.

Transaction fee mechanisms (TFMs) allocate scarce block space in blockchains. Prior work focuses on incentive compatibility (IC): honest behavior maximizes the payoff of each strategic player. We introduce rational-harm proofness (RHP), which rules out deviations that harm honest participants without reducing the deviator's utility relative to honest behavior. IC alone does not exclude such costless harm: in a second-price auction, a losing bidder can raise the winner's payment without changing its own payoff. For finite block capacity k, we characterize TFMs satisfying RHP alongside user incentive compatibility (UIC) and miner incentive compatibility (MIC). In the plain model, where a single miner implements the auction, we prove a tight tetrilemma: no TFM simultaneously achieves positive miner revenue, UIC, MIC, and RHP against miner-user coalitions, while any three are jointly achievable. In the MPC-assisted model, where a committee of miners implements the auction using multi-party computation, we construct a randomized TFM with positive miner revenue satisfying UIC, MIC, and RHP against users, miners, and miner-user coalitions containing at most k users. Randomness is necessary to confirm transactions under congestion: any deterministic TFM satisfying UIC and user RHP in this model confirms no transactions when the number of submitted bids exceeds k. Finally, IC and RHP are incomparable for every strategic role in both models: mechanisms can satisfy either property without satisfying the other. These results extend transaction fee mechanism design beyond incentives to protection against costless harm.

We present Potential-Dominant Operator Splitting (PDO-Split), a real-time generalized Nash equilibrium solver for constrained dynamic multi-agent problems with potential-dominant structure. PDO-Split targets the computational bottleneck in game-theoretic model predictive control, where repeatedly solving the equilibrium KKT system becomes costly as the number of agents increases. We introduce a class of gamma-potential-dominant games, in which the potential (or cooperative) structure dominates the competitive interactions between the agents. We show that this structure allows PDO-Split to use the potential component as a preconditioner while incorporating the competitive component through iterative refinement. We establish convergence guarantees and exploit the symmetry of the potential component through a reusable LDL^T factorization to accelerate the linear solvers. We evaluate PDO-Split across several practical multi-agent planning problems, including eight-car racing and six-vehicle ramp merging, achieving substantially improved runtime and convergence rate over existing DDP-based and Newton-based methods, especially with a larger number of agents. The algorithm is also experimentally validated on miniature autonomous race car platforms, demonstrating the approach's real-time capability.

Newton methods efficiently find Generalized Nash Equilibria (GNE) in dynamic games by solving for the KKT necessary conditions. These methods are fast and can support multi-agent Model Predictive Control (MPC) for highly dynamic robots. However, a small KKT residual alone does not certify that the returned solution satisfies the second-order sufficient conditions for a local GNE. In this paper, we propose an efficient numerical method to verify the second-order sufficient conditions (SOSC) for a local GNE. We connect the inertia of the agent KKT matrix with the positive definiteness of the reduced Hessian of the cost function, projected onto the null space of the constraints. Furthermore, we introduce an inertia-corrected update step that improves convergence to local GNEs by destabilizing strict saddle points with weak cross-agent coupling. Our main contribution is a fast Newton solver for Constrained Dynamic Games that provides efficient optimality checking. Through numerical benchmarks, we demonstrate the proposed solver's runtime and convergence performance in practical multi-agent planning problems. We also validate the solver's real-time capabilities in physical experiments using a platform of miniature autonomous race cars.

We consider the fair division problem with indivisible goods and study the following decision problem: given a fair division instance, does there exist an allocation that is envy-free and efficient? We consider two efficiency criteria: Pareto-optimality and social welfare optimality. We provide a complete landscape on the computational complexity of this decision problem, with the number of agents ranging from $2$ to $\infty$, both additive valuations and general valuations, and the more restricted class of $k$-ary valuation functions (where an item's marginal value is restricted to $\{0,1,\ldots,k-1\}$ for some constant $k\geq2$). One interesting observation is that many versions of the above-mentioned decision problems fall into the “gap” between the first and the second levels of the polynomial hierarchy. Specifically, assuming the polynomial hierarchy does not collapse to the first level (i.e., assuming $\text{NP}\neq\text{coNP}$), these problems are in $(\Sigma_2^{\text{p}}\cap\Pi_2^{\text{p}})\setminus(\text{NP}\cup\text{coNP})$. In particular, we provide a fine-grained complexity analysis across different parameter regimes, including the number of agents and the choice of valuation models. Depending on different parameters, many problems admit different complexity classifications, ranging from the intermediate classes $\Theta_2^{\text{p}}$ and $\Delta_2^{\text{p}}$ between the two levels to $\Sigma_2^{\text{p}}$-completeness. Finally, De Keijzer et al. show the $\Sigma_2^{\text{p}}$-completeness of the decision problem when considering Pareto-optimality as the efficiency criterion with additive valuations. Our main results extend this result to more restricted settings, such as instances with a constant number of agents or $3$-ary valuation functions, which resolves the open problem given by Bouveret and Lang.

Private and encrypted mempools hide pending transactions to stop sandwich attacks and other forms of maximal extractable value (MEV), but what they hide is rarely everything: a transaction's pair, direction, and a coarse range for its size can still leak. How much leakage makes sandwiching pay? We answer exactly for a fee-free constant-product automated market maker, the pricing rule behind Uniswap v2. Traders observe an interval containing the victim's size and bid in a first-price auction for the right to sandwich it, and the winning front-run must keep the victim's trade executable at every size in the interval. The answer turns on the smallest size consistent with the leak. It alone determines the feasible front-runs, the largest feasible front-run is optimal for pointwise, expected, and worst-case profit alike, and the guaranteed profit has a closed form. When execution is costly, a privacy layer that wants to rule out sandwiches profitable at every consistent size may therefore reveal anything about the size except a lower bound above an explicit threshold; the upper end of the range is irrelevant. With two or more symmetric traders, every pure-strategy perfect Bayesian equilibrium of the auction hands the entire expected net rent to the auctioneer. If the direction is hidden too, no non-contingent first leg front-runs both possible directions, while post-trade arbitrage can survive even perfect pre-trade hiding.

We study fundamental information-theoretic limits of robust stochastic optimization when the distribution is known only through its exact moment sequence. We develop a unified framework that produces families of distinct distributions sharing all moments yet inducing radically different optimal decisions, thereby establishing strong impossibility results for a range of decision problems under moment ambiguity. Our approach gives two explicit constructions: a binary and an $N$-way construction showing that distributions with identical moment sequences can nevertheless exhibit arbitrarily different quantiles, order-statistics and threshold regions, forcing incompatible optimal actions. These families of distributions yield, in fact, strong impossibility results across several stochastic optimization problems. First, for the newsvendor problem, moment equivalence causes quantile ambiguity, inducing any fixed or randomized order quantity to fail arbitrarily badly. Second, for revenue maximization, no deterministic or randomized posted pricing scheme can secure a nontrivial approximation relative to the full-information benchmark. Third, for the secretary with cardinal observations setting, the worst-case robust value over all exact moment disclosures is exactly the classical $1/e$ finite-horizon value as opposed to the celebrated result of $0.58$ success probability with full-information by Gilbert and Mosteller (J. Am. Stat. Assoc., 1966). We also recover and expand upon the recent impossibility result of Correa et al. (STOC, 2026) for prophet inequalities with moment knowledge. Indeed, exact moment knowledge can yield at best a $\Theta(1/\log n)$ competitive ratio, even when competing against relaxed benchmarks based on expected $r$-th order statistics or when the algorithm is allowed to select $r$ items.

We study gains from trade in matching markets with independent private values and costs, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. A second-best guarantee for finite bilateral trade extends without loss to matching markets with independent Borel priors, arbitrary downward-closed feasibility, and finite expected first-best gains. For bounded buyers with monotone hazard rates and arbitrary bounded sellers, we determine the exact worst-case ratio of second-best to first-best gains, approximately $0.72490721$. For binary buyers and sellers with at most $m$ types, we determine the exact ratio for every $m$, including $8/9$ when $m=2$ and a limit of $4/5$ as $m$ grows. Both families of bounds are tight already in bilateral trade.

We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.

Slashing is commonly argued to secure proof-of-stake blockchains by confiscating the stake of misbehaving validators. The usual justification is that, without slashing, validators can solicit an equivocation attack by signing conflicting blocks: if enough others join, the attack succeeds; otherwise, the attempt incurs no loss. Slashing is intended to make such attempts costly and thereby guarantee the security of applications whose economic value is comparable to the bonded stake. This rationale, however, rests on heuristic arguments rather than a formal game-theoretic guarantee. We challenge this rationale by constructing a risk-free coordination protocol for rational validators under algorithmic slashing. We show that the prescribed strategy profile, in which rational validators solicit other validators to equivocate, constitutes an ex post Nash equilibrium, even when validators do not know in advance how many others will participate. The equilibrium holds for any gain $\epsilon>0$ from successful equivocation, however small relative to the bonded stake. Thus, slashing alone does not guarantee economic security proportional to the value of bonded stake. Our results expose a fundamental limitation of algorithmic slashing. Whereas conventional collateral arrangements in many real-world scenarios can rely on external enforcement, for example through courts, algorithmic slashing depends on the same consensus process that the attackers control. These findings call for a formal analysis of slashing's security, rather than overly simplistic arguments drawn from financial systems with independent enforcement.

AI-assisted job-search tools have become increasingly popular by making it easier to find and apply to jobs. But by making it easier for applicants to generate and tailor application materials, they can also reduce how informative those materials are about applicant fit. We study this tradeoff in a hiring market where applicants differ in experience and latent match quality and firms use noisy application materials to decide whom to screen. We ask how AI affects downstream screening and hiring, and which applicants are most adversely affected. As application materials become less informative, a Bayesian firm rationally relies more heavily on coarse observables such as prior experience. Among the four applicant types defined by experience and compatibility for the job, inexperienced-compatible applicants are the most exposed: they lack observable experience and lose the individualized information that could distinguish them from other inexperienced candidates. When screening is costly, these changes can also generate inefficient screening failures in which firms screen no applicants or screen only experienced applicants. We then show that multistage hiring can arise as an endogenous firm response: a relatively inexpensive intermediate assessment allows firms to acquire new evidence of fit before costly full screening. This can restore screening opportunities that disappear under one-stage hiring and give inexperienced-compatible applicants a path to screening. Our results show how AI can shift the central friction in hiring from submitting applications to obtaining credible evaluation, creating entry barriers for high-fit workers without prior experience. Multistage hiring can endogenously arise in response, restoring evaluation opportunities that would otherwise disappear and helping preserve market functioning.

We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.

We study a matching mechanism where agents and objects are described by features rather than complete rankings. A single spectral projection reduces the problem to a one-dimensional sort, computable in O(N log N) time. We prove that on descaled features and preferences, our algorithm obtains the exact Nash Social Welfare (NSW) optimum within the projected space, with an unconditional utilitarian-welfare guarantee and a conditional NSW guarantee. The proposed mechanism is stable against exogenous noise but not strategy-proof; we provide an explicit profitable misreport. On an agentic AI shopping application, the diagnostics correctly anticipate both a success and a failure case. A 100-instance robustness study confirms the findings.

We study a partial-participation variation of the Hotelling-Downs model. Voters each have a cost to vote, and only vote when the comparative gain from their preferred candidate exceeds the cost. Under this model the median voter theorem breaks, and we study the extent of polarization under equilibria in different voters and cost distributions. We find that the main predictor of polarization is the reverse-hazard-rate of the cost distribution, indicating that the driver of polarization under our model is the willingness of voters to respond to changes in positions of candidates. We then extend the model by adding parameters governing alienation and candidate competitiveness, showing that our results are robust even when taking into account other realistic factors.

The study of approval-based committee (ABC) voting has so far focused predominantly on proportional representation. The canonical notion of diverse representation, based on the Chamberlin–Courant score, counts the number of voters with at least one representative in the committee, making it an individualistic notion. We develop a more comprehensive theory that instead requires the representation of many groups of voters, grounding it in the justified representation (JR) axiom, which we strengthen in two directions. First, we study the existing axioms of Strong JR (SJR) and Semi-Strong JR (SSJR), which consider the same cohesive groups as JR but demand stricter representation. We show that neither can be optimized efficiently on general domains (unless P=NP), but both can be on the Candidate Interval domain. Second, to capture the unique and defining opinions of a group, we introduce Distinctive Representation (DR) and its local optimization variant, Local DR. We address satisfiability and computation time, and show (Local) DR to be distinct from known proportionality and diversity axioms. Experiments on real-world and synthetic data show Local DR performs well on multiple empirical measures of diversity.

We study how much revenue a seller can lose by restricting attention to selling separately or grand bundling, in the setting of a single additive buyer with independent item values. Although revenue-optimal mechanisms can require lotteries and infinite menus, Babaioff, Immorlica, Lucier, and Weinberg showed that the better of these two simple formats always achieves a constant fraction of optimal revenue. We prove that $\mathrm{OPT} \le 3.52 \max\{\mathrm{SREV}, \mathrm{BREV}\}$, where $\mathrm{SREV}$ and $\mathrm{BREV}$ are the optimal revenues from selling separately and grand bundling, respectively. This improves the previous best-known approximation factor of $5.2$ due to Ma and Simchi-Levi and narrows the gap to the known lower bound of $2$.

When an informed adversary shares the audience of a constrained signalling channel, the signal that best protects the truth is the signal that best describes it. On 108 confirmatory items, the adversary-robust optimum aligns exactly with the salience pole from prior work. Across a 200,000-item pool, the two differ on only 2,748 items — lying exactly where the prior salience-to-Bayes coordinate is undefined. Where defined, robustness is achieved by moving from Bayesian discrimination entirely to salience. We show this by introducing an adversary to a forced-choice task (abstracted from Deception: Murder in Hong Kong). The adversary knows the target, observes the signal, and argues for the strongest wrong answer using a persuasion budget, $\beta$. As $\beta$ grows, the optimal signal shifts from the posterior-maximizing option to the margin-maximizing one; at $\beta = 0$, the game reproduces the original oracle model with a listener temperature of $\tau = 1$. This effect is real: 18.2 percent of the pool has an optimum that shifts under a finite budget, and each item's critical budget is exact. This coincidence structurally limits empirical evaluation. Two adversary framings change the chosen option of seven language models on 30 to 77 of 108 items against an exact no-effect rate. Yet, no measurement can determine whether this movement is toward the adversary-aware optimum or toward salience, because the two options are identical. This is a structural limit, not a null result. The diagnostic check is cheap: before evaluating adversary-awareness, verify whether the robust target coincides with a heuristic target on the evaluation items.