ALT 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,

ALT 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 ε-approximate Nash equilibria for inverse-exponentially small ε. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one res

ALT 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.

ALT 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

ALT 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 OPT ≤ 3.52 max{SREV, BREV}, where SREV and 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.

ALT We study the online allocation of indivisible goods among n agents, where each good must be allocated immediately and irrevocably upon arrival. Against an adaptive adversary, Neoh and Teh [2026] proved that no algorithm can guarantee a positive approximation to proportionality up to one good (PROP1) that is independent of the number of goods, and the same holds for proportionality up to k goods (PROPk) for any fixed k. We instead consider an oblivious adversary, which fixes the input in advance. Choo et al. [2026] showed that the uniformly random allocation returns a Θ(1/log(n/δ))-PROP1 allocation with probability at least 1-δ. We improve this to Ω(1/log{log(n/}δ)); our algorithm does not take δ as input, so the same algorithm achieves this bound for every δ∈(0,1). Moreover, with the same probability, a variant of our algorithm gives every agent almost her bundle, and even without adding any good when no single good is too valuable relative to this share. In contrast, for envy-freeness

ALT Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of

ALT Opinion formation in online networks involves changes in both beliefs and social ties. Analytical models make it possible to study equilibrium and social cost, but usually represent communication as a fixed numerical update. LLM-driven agents offer a language-based alternative, yet their convergence and collective efficiency remain unclear. We develop the Hybrid Coevolutionary Opinion Game (H-COG), combining cost-minimizing Friedkin-Johnsen agents (Type-C) and Phi-4 language agents (Type-L) in a dynamically rewired K-nearest-neighbor network. We initialize 50 agents with opinions drawn from 5,199 Reddit comments on gun control and abortion. The comments are scored on a continuous [-1,+1] scale using a fine-tuned RoBERTa regressor, and a mixing parameter sets the proportion of each agent type. The experiments cover nine population compositions, three initial network topologies, and two topics. All 540 runs meet the convergence criterion within the simulation horizon. Under Type-L updati

ALT Customers often specify acceptable time intervals for receiving a service. When service on a date entails a fixed activation cost, overlapping intervals allow joint service and cost sharing. Customers may nevertheless conceal flexibility by reporting a smaller interval, affecting both operating cost and its allocation. We ask whether an operator can select a core allocation at every reported profile without making concealment profitable. We establish sharp population boundaries for preventing such coalitional reductions. When intervals may be narrowed from either end, a core-selecting rule preventing such reductions exists if and only if there are at most three customers. With four or more customers, impossibility holds even under Pareto contraction-proofness, which excludes deviations making every contracting customer weakly better off and at least one strictly better off. The impossibility persists when each contracting customer conceals only an arbitrarily small fraction of her feas

ALT The design of credible auctions—mechanisms where a revenue-maximizing auctioneer has no incentive to deviate from the protocol—faces a fundamental cryptographic barrier when the auctioneer controls shill bidders. While a natural approach is to use Secure Multi-Party Computation (MPC) to remove the trusted auctioneer, the impossibility of fair coin flipping of Cleve (1986) implies that monolithic MPC protocols grant the auctioneer a "free option": they can learn the auction's outcome and unilaterally abort if the revenue is unsatisfactory. Cryptographic commitments with ex-ante penalties mitigate this abort asymmetry, but no finite penalty suffices for heavy-tailed distributions. We circumvent this barrier by introducing the MPC Decomposition Principle. Rather than encrypting the entire mechanism, we use MPC strictly as an information-restriction tool. We isolate the winner determination problem into a minimal MPC gadget that computes and reveals the winner's identity but no payment inf

ALT Citizens' assemblies are deliberative bodies intended to form a microcosm of the population. Organizers rely on quota-based stratification and must decide which attributes define resemblance to the public. Yet meeting every quota can still leave a dimension citizens value unrepresented. We study this attribute-selection problem in general-purpose and climate-focused assemblies through randomized conjoint experiments. We find that demographic attributes matter for perceived representation, but political alignment and context-specific attributes such as climate concern exert a stronger influence. When both are shown in a climate-focused setting, each remains influential, with political alignment having the larger estimated marginal effect. We also examine the omission of a relevant stratification attribute. Panels stratified on demographics, even with political alignment included, match the observed pool's climate-concern distribution no better than uniform random samples. These results

ALT We present JEV-Star, a StarCraft II controller that defeats the strongest non-cheating built-in AI, Lv7, by combining fast JEV action selection with persistent GPT-6 planning. The combined system wins four full games at Lv5–Lv7, including two Lv7 victories with different seeds, while retaining a median JEV response time of 0.422 seconds. Mean estimated model cost across these games is USD 3.71 per game: USD 0.15 for JEV and USD 3.56 for GPT-6. We compare this system with an initial JEV-only controller in full-game macro control and multi-unit micromanagement. The standalone controller reaches a 20-minute limit against Lv2 without expanding. Across 35 battle maps with three episodes per map and controller, the combined system raises mean enemy elimination from 16.50% to 37.69% and wins from 3 to 7 out of 105. Replay frames and decision logs document resource reservation, persistent economic goals, and stable army objectives in successful full games. The results demonstrate a practical d

ALT We present JEV-Star, a StarCraft II controller that defeats the strongest non-cheating built-in AI, Lv7, by combining fast JEV action selection with persistent GPT-6 planning. The combined system wins four full games at Lv5–Lv7, including two Lv7 victories with different seeds, while retaining a median JEV response time of 0.422 seconds. Mean estimated model cost across these games is USD 3.71 per game: USD 0.15 for JEV and USD 3.56 for GPT-6. We compare this system with an initial JEV-only controller in full-game macro control and multi-unit micromanagement. The standalone controller reaches a 20-minute limit against Lv2 without expanding. Across 35 battle maps with three episodes per map and controller, the combined system raises mean enemy elimination from 16.50% to 37.69% and wins from 3 to 7 out of 105. Replay frames and decision logs document resource reservation, persistent economic goals, and stable army objectives in successful full games. The results demonstrate a practical d

ALT We study Bulow-Klemperer-style competition complexity in two-sided double auctions with m unit-demand buyers drawn i.i.d. from F_B and n unit-supply sellers drawn i.i.d. from F_S. When m ≥ n and buyer valuations first-order stochastically dominate seller costs (F_B ≽_FSD F_S), we prove that recruiting just two additional sellers enables Seller Trade Reduction (STR), a prior-independent mechanism, to achieve expected Gains From Trade (GFT) at least the first-best GFT of the original market. When the buyer side is the smaller side of the market (m ≤ n), an analogous result holds for Buyer Trade Reduction with 2 additional buyers. This resolves open questions of Babaioff, Goldner, and Gonczarowski (SODA 2020) and Cai, Liaw, Mehta, and Zhao (STOC 2024). We complement our upper bound by showing that this uniform bound is optimal: already for m = n = 1, no prior-free mechanism (deterministic or randomized) that is dominant-strategy incentive-compatible, individually rational, and weakly budg

ALT Digital platforms increasingly rely on automated budget-management systems to regulate participation across allocation opportunities. A common tool is multiplicative pacing, which scales buyers' bids so that campaign-level budgets are spent gradually. Although pacing is operationally simple, its aggregate behavior depends on the underlying mechanism. In first-price single-item auction markets, pacing enjoys strong structural and computational properties that often fail in second-price auctions. It is unclear whether these properties extend to richer platform mechanisms. We develop a unified theory of pacing equilibria across a hierarchy of mechanisms. We first show that, even in first-price position auctions, the market-equilibrium interpretation of the single-item benchmark can fail. We then identify bid-maximizing pay-your-bid mechanisms as a broad class in which pacing equilibria exist, are unique, and admit an Eisenberg-Gale-type convex-program characterization. This implies effici

ALT Increasingly, resource allocation games are being proposed to model team coordination in denied communication environments. Of particular interest is understanding the impact of communication denial on the quality of emergent team coordination. In this work, we consider the situation with an arbitrary communication network and use the Price of Anarchy to quantify the quality of emergent behavior. Our main result is a computationally efficient algorithm that calculates a minimal communication network that has the same performance guarantee as the full information case. Additionally, we provide efficient algorithms that compute a Nash and a strict Nash equilibrium in the full information setting. Finally to support these algorithms, we provide sufficient conditions for the existence of a strict Nash equilibrium, characterize strict Nash equilibria across all communication networks, and show that each strict Nash equilibrium in the full information case has a necessary and sufficient set

ALT Personalized AI memories, defined as persistent decision-relevant states distilled by platforms from long-run human-AI interaction, are increasingly portable, provenance-certifiable, and tradable. Provenance answers the question of origin, but it does not settle who holds which rights over a memory, nor how wider deployment affects its future supply. We develop a unified model in which memory use is non-rival, while refresh, the maintenance of continued validity, is relationally co-produced by the represented individual and the platform. Even assuming perfect provenance and complete information, the model still yields a set of inherent limitations. First, there is an extraction ceiling: decision value is bounded by lived experience. Second, a rights-separation theorem shows that no budget-balanced ownership assignment can make both co-producers residual claimants, and that control rights and cash-flow rights operate on distinct margins. Third, a depletion result indicates that reach-ex

ALT In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of n agents who arrive sequentially, with values drawn independently from a known distribution. When an agent arrives, their value is revealed, and the algorithm must immediately allocate the item or continue. The usual objective is utilitarian welfare: the expected value of the recipient. Guarantees for this objective extend to allocating m indivisible items to sequentially arriving agents with i.i.d. additive values. Utilitarian welfare, however, ignores how expected utility is distributed across agents. Motivated by a rich literature in fair division, we instead evaluate an online rule by its generalized p-mean welfare, which includes utilitarian welfare at p=1, Nash welfare (the geometric mean of utilities) at p=0, and egalitarian welfare (the minimum utility) as p→-∞. When the number of items is large, we show that this many-item fair-division problem is captured exactly by a single-item prophet

ALT We study strategic disclosure of the action space in principal-agent contracting, where an agent selects a disclosed action set to shape the principal's perception of her capabilities before contract design. Unaware of the strategic disclosure, the principal designs a revenue-optimal contract as if the disclosed action set were complete and accurate. We consider two variants distinguished by cost verifiability. When costs are unverifiable, the agent can extract the entire first-best surplus, leaving the principal with zero revenue. When costs are verifiable, we characterize the agent's optimal disclosure strategy in binary-outcome settings and, more generally, when the principal is restricted to linear contracts, reducing the agent's problem to a two-variable convex optimization problem. We prove that the agent can secure utility of at least a 1/e fraction of the first-best surplus, which also yields a 1/e welfare guarantee under optimal disclosure. While the principal's revenue can be

ALT Bimatrix games may have an exponential number of mixed Nash equilibria if both dimensions of the game are allowed to grow. Bounds on their maximal number give structural insights that have been used to construct hard-to-solve games. We show new sharp or asymptotically sharp bounds on the (polynomial) number of equilibria for generic games where one dimension of the game is fixed and the number of strategies of the other player grows. These results go beyond the hitherto studied square games. Our methods employ combinatorial properties of polytopes, and recent obstructions that relate to the graph of those polytopes. For n≥5, we construct 3× n games that have all 2n+1 vertices of the best-response polytope as equilibrium strategies, proved using a simple case of the 4-color theorem for planar graphs. Generic 4× 5 games are shown to have at most 17 equilibria, using computer calculations with existing datasets for all combinatorial types of the relevant polytopes. For d× n games, we cons