Papers

An agentic market is a decentralized serving-time market where AI agents bid to claim each user prompt. An agent's bid is based on its expected value for the prompt, which is the expectation of the reward for its response minus its inference costs. First-price auctions (FPAs), in which the highest bidder pays its bid and receives the prompt, are a natural way to allocate prompts in such a market, since they are simple and transparent to run, and do not require central knowledge of private capabilities and costs. However, FPAs are not truthful: participants may bid less than their true value in the hope of a larger profit, and the prompt may then be allocated to someone other than the bidder who values it the most. This welfare loss is quantified by the $\textit{price-of-anarchy}$ (PoA). In this paper, we argue that agentic markets are likely to possess features that reduce the price-of-anarchy. The first is a $\textit{competitive floor}$, which occurs when multiple bidders usually value the prompt above some baseline share of the optimal welfare (e.g., because the best models are often distilled into cheaper alternatives, which perform similarly). We show that competition among them then limits the welfare loss, which can be driven to zero as the floor rises. The second feature is $\textit{near-independence}$ of values after conditioning on the prompt, which occurs when most of the predictable variation in the expected value is determined by the difficulty of the prompt. As the value distribution approaches conditional independence, we can derive an efficiency guarantee that approaches a factor of $1 - 1/e^2$ of the optimal welfare. Thus, both features give rise to welfare lower bounds that are significantly better than the well-known general case of $1 - 1/e$. We validate these results empirically using auctions with strategic bidders simulated on the EmbedLLM prompt routing dataset.

Opponent histories can mislead after behavioral shifts. SafeAdapt-Poker formulates budgeted adaptation under opponent shift as a dual-counterfactual sequential-control problem using only information available before each decision. At each decision the controller asks two distinct questions: what local downside a deviation from the frozen anchor would induce under matched legal continuations, and what future adaptation value would be lost by consuming part of the remaining deviation budget now. The first question is answered by a monotone strategic-risk model over deviation intensity; the second by a paired budget-state continuation model that prices current budget consumption. The controller selects among support-preserving candidate deviations by trading immediate adaptation value against these two quantities, a pathwise cumulative-KL ledger bounds total anchor-relative deviation, and a finite family of frozen controllers is screened on complete paired calibration sessions before held-out interaction. A finite-candidate perturbation bound shows that the allocation objective degrades continuously with continuation-value estimation error. Evaluation covers exact-game exploitation and safety, four opponent shifts, local-risk calibration, delayed-opportunity allocation, direct opportunity-value estimation, value-error robustness, factorial mechanism attribution, budget sensitivity, abstract-HUNL cross-play, and player/time-held-out public-history behavior. On exact Leduc the full controller attains a matched weak-pool gain of +0.0718 with a worst-opponent delta of -0.0126, raises delayed-opportunity capture from 0.6318 under myopic allocation to 0.7841 under the same session budget, and reaches +42.7 mbb/hand in abstract-HUNL cross-play; the retained public-history screen reports 0.5820 action accuracy and 0.9277 log loss versus 0.5039 and 0.9778 for a public prior.

Pairwise comparison data are a standard supervision signal in preference learning, but disagreement in such data can reflect stable latent heterogeneity, ephemeral stochasticity, or non-binary responses hidden by a forced-choice interface. We study which of these semantic distinctions are identifiable from the feedback channel itself. We introduce a nonparametric latent semantic model with three querywise quantities: aggregate directional preference $\mu_q$, persistent disagreement $\tau_q$, and non-binary mass $\alpha_q$. Under the anonymous binary channel, we prove an exact semantic fiber theorem: $\mu_q$ is point-identified, whereas $(\tau_q, \alpha_q)$ vary over an explicit feasible region compatible with the same binary law. Same-annotator repeats identify $\tau_q$ through a covariance identity, abstention-enabled feedback identifies $\alpha_q$ directly, and together they point-identify the full semantic triple. We also derive finite-sample estimators, nonasymptotic concentration bounds, and semantics-aware action-recovery guarantees, and validate the theory on theorem-matched synthetic data.

We study the route-set allocation problem between end nodes in capacity-constrained flow networks with transfer costs. We introduce an origin–destination (OD) bidding language, in which a participant bids for bounded conic combinations of inlet–outlet–quantity licences and the mechanism performs the routing through a network-flow optimising winner-determination problem. We then study payment rules for the OD mechanism. Under a restricted model with openly and uniformly priced sources and bidders who are indifferent to the source of the gas, the Vickrey–Clarke–Groves (VCG) payment is core-stable; the key structural fact is that in this regime some optimal aggregate flows never use a physical pipe in both directions, so the winner-determination problem reduces to a single-commodity network flow whose value is submodular in the set of active bidders. If source access is allowed to depend on the individual consumer – a realistic feature, e.g. when gas deals are embedded in bilateral political bargaining – the reduction fails and VCG payments may lie strictly outside the core. For this general model we propose a dual (nodal) pricing rule derived from the shadow prices of the flow-conservation constraints, and prove it is always core-stable, at the cost of dominant-strategy incentive compatibility. Illustrative examples accompany each result.

In a repeated Stackelberg security game, a defender commits in every round to a randomized allocation of its resources, and an attacker, drawn from a set of types, best-responds. Existing no-regret guarantees assume that the defender knows this set of types in advance. We drop this assumption: the set of types is unknown, and its size is at most $K_{\max}$, an upper bound that the defender is not told. We show that what can be learned then depends on what the defender observes. If it observes the type of each attacker, an algorithm that adds types to its list as they appear achieves regret $\tilde O(nK_{\max}\sqrt{T})$ over $T$ rounds with $n$ targets, the same $\sqrt T$ rate as with known types, at an extra factor of only $\sqrt{K_{\max}}$ and without ever using $K_{\max}$. If it observes only the attacked target and types come from an infinite universe, no algorithm has sublinear regret: in a fixed three-target game every algorithm suffers regret at least $T-2$, even against a single attacker type, because it cannot tell which type it faces. If, in addition, it is told every $B$ rounds which types have appeared so far, sublinear regret returns, at $\tilde O(nK_{\max}^{4/3}T^{2/3}+K_{\max} B)$. The first term is the rate of the partial-information learner we use, and we show that the additive cost of the delay cannot be avoided.

We resolve the problem of unweighted online stochastic matching with a known arrival law by establishing its optimal competitive ratio. For Poisson arrivals, we achieve $1-e/e^e\approx0.8206$, matching the upper bound of Chierichetti, Giacchini, Panconesi, and Vattani [ICALP 2025]. For exactly $n$ i.i.d.~arrivals, we obtain the same guarantee up to an additive $O(n^{-1/2})$ loss. Our key technical contribution is an exact correspondence between Poisson matching and exponential scheduling, preserving both online performance and the expected offline optimum. To prove the latter, we show that the distribution of the maximum of a random supermodular set function is determined by its joint distributions along chains of nested sets, a result of independent interest. This reduces the analysis to chains, where classical Poisson–exponential duality applies. The offline equivalence extends to arbitrary nonnegative edge weights. We then design a posterior allocation policy for exponential scheduling and use the correspondence to transfer its optimal competitive guarantee to online matching. Additionally, we show that the optimal competitive ratio under an unknown arrival law is strictly lower than $1-e/e^e$, establishing a strict separation between the known and unknown arrival models.

We study proportional cake cutting under an equal-length constraint, where each of $n$ agents must receive a bundle of length exactly $1/n$ that is worth at least $1/n$ to that agent. Our main result determines the exact worst-case number of cuts needed to guarantee such an allocation, namely $2n-2$ for every $n$. This improves on the previously known quadratic upper bound. The proof combines the constrained necklace-splitting theorem with a recursive assignment argument based on Hall's theorem. The same bound extends to the stronger requirement of envy-freeness when $n$ is a prime power, and an $O(n^{1.525})$ upper bound holds for arbitrary $n$. We then ask whether such allocations can be computed. We first show that no deterministic protocol in the Robertson–Webb model terminates after finitely many queries on every instance and always returns an exact equal-length proportional allocation, even for two agents with identical valuations. For every $\varepsilon>0$, however, $O(n^2/\varepsilon)$ queries suffice to produce an allocation in which every agent receives a bundle of length exactly $1/n$ and value at least $1/n-\varepsilon$, again using at most $2n-2$ cuts. Finally, we augment the Robertson–Webb model with two-knife queries. We show that recursive balanced halving attains the optimal bound of $2n-2$ cuts when $n$ is a power of two. For arbitrary $n$, we give a procedure using $O(n\log n)$ cuts.

Proof-of-Stake (PoS) systems offer a scalable and energy-efficient alternative to Proof-of-Work (PoW). The economic security of PoS relies critically on incentivizing broad and meaningful participation through well-cali\-brated staking reward mechanisms. We study Ethe\-reum's effective-balance rules as a mechanism-design problem in which the protocol chooses a reward coefficient, an activation threshold, and a maximum effective balance, and validators respond in the induced propor\-tional-allocation game. For fixed participating validators and identity counts, we establish a unique Nash equilibrium in validator-level total stakes. When validators can split or merge their visible identities, each candidate identity structure must be evaluated after the market re-clears. Restructuring incentives therefore depend on post-reset payoff comparisons that account for all validators' stake responses. For an illustrative simulation, we construct address-level budget proxies from Beacon Chain deposits and withdrawals, Lido staking flows, Etherscan balances, and calibrated synthetic agents. With illustrative cost coefficients, lowering the reserve price from 32 ETH to 30 ETH increases active identities by 5.922% and total effective stake by 0.098%.

We prove that computing a complete contiguous $\varepsilon$-envy-free cake allocation is PPAD-complete for normalized rational piecewise-constant additive valuations. The hardness holds even when $\varepsilon$ is given in unary, and even when every density takes only two values, which are the same for all agents, and is piecewise constant with at most six breakpoints. As a consequence, computing an exact contiguous envy-free allocation is also PPAD-complete, and the hardness holds under the same restrictions on the densities. Our key ingredient is to assign prices to the pieces so that, in every approximately envy-free allocation, all prices are nearly equal, regardless of how the pieces are assigned to the agents. We further show that, for every fixed integer $c\ge1$, computing a contiguous EF$c$ allocation of indivisible goods on a path is PPAD-complete for additive valuations, and the hardness holds even for binary valuations in which each good is valued by exactly one agent and all agents value the same number of goods.

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

We examine the value of information in extensive-form decision problems: the largest multiplicative gain that a decision maker can obtain from an information refinement, taken over all payoff environments. This measures the structural importance of information disentangled from any particular payoff specification, and generalizes the notion of value of recall recently introduced by Berker et al. (AAAI'25). We establish a unifying characterization of the value of information under any information refinement, uncovering an intriguing connection to the maximum fractional chromatic number over a certain family of conflict graphs. We then employ our characterization to elucidate the complexity of two central information refinements. First, for the value of perfect information in perfect-recall decision problems, we find that the relevant conflict graphs are cographs, so the fractional chromatic number collapses to the clique number. Even though the clique number is tractable for a given cograph, we show that the additional layer of optimization (over the family of graphs) makes computing the value of perfect information NP-complete. On the positive side, we prove fixed-parameter tractability in terms of the degree of imperfect information. Second, for the value of recall in imperfect-recall decision problems (with no absentmindedness), we first show that the value of recall can realize the fractional chromatic number of any graph. Interestingly, this implies that, unlike the value of perfect information, the value of recall can take fractional values. Building on this reduction, we then establish S2P-completeness. This addresses questions left open by Berker et al. (AAAI'25)—both on the characterization and the complexity of the value of recall—and shows that computing the value of recall is strictly harder than the value of perfect information.

Assigning routine tasks to cheaper large language model (LLM) providers can reduce generation cost, but switching providers may require processing accumulated context again. Keeping dependent tasks with the same provider can instead reuse eligible context. Graph-based workflows therefore couple routing decisions across tasks. Independent providers may also privately know their real-time unit costs and strategically misreport them. We formulate this routing problem as a single-parameter procurement auction and propose STAR (Strategy-proof Topology-aware Agent Routing), which minimizes virtual-cost-weighted graph workloads. Its allocation rule and payments, computed by integrating workload over possible cost reports, make truthful reporting utility-maximizing regardless of other providers' reports and cover each truthful provider's execution cost. With independent cost distributions and non-decreasing virtual costs, STAR additionally minimizes the user's expected total payment to providers. Controlled synthetic experiments separate the execution-cost benefit of topology awareness from the payment benefit of virtual-cost optimization: the former grows with fan-out and transferred payload, while the latter increases gradually along the tested prior-shape heterogeneity path. A paired sensitivity study quantifies how payment savings vary with prior misspecification while strategy-proofness is preserved.

We study packet routing in queuing systems where queues act as selfish, myopic agents that use no-regret learning algorithms to select servers with unknown service rates. To model the small buffers used in data centers, we assume that each server has a single-packet buffer. Even such a tiny buffer already captures the features of buffering: routers can exploit multiple servers while accepted packets remain in service, but packets can occupy servers for multiple rounds, complicating future service and learning. We first analyze a single queue routing packets to $m$ buffered servers with service rates $\mu_1, \dots, \mu_m$. This setting is equivalent to an instance of the recharging bandits problem with geometric recharge. We prove that any no-regret learner achieves a long-run average throughput of at least the Hamacher sum of the server rates, and that this bound is tight. Consequently, a single no-regret queue is stable if and only if its arrival rate is below the Hamacher sum of the server rates. Moreover, comparing against an optimal policy, we show that any no-regret learner is at least $0.77$-competitive, which is also tight. We then study multi-queue systems where $n$ queues with arrival rates $\lambda_1, \dots, \lambda_n$, each at most $\lambda_{\max}$, compete for service from $m$ buffered servers. We show that the smallest overprovisioning factor that guarantees the system to be stable under high-probability no-regret learning is $\frac{1}{1-\lambda_{\max}}$. Equivalently, in terms of the total arrival and service rates, the condition $\sum_{i=1}^n \lambda_i < (1-\lambda_{\max})\sum_{j=1}^m \mu_j$ is sufficient, and sometimes necessary, for stability under no-regret learning. In particular, for $\lambda_{\max} = 1/2$, this improves the upper bound of Abel et al. (EC 2026) from $3$ to $2$, matching their lower bound and resolving their open question.

We study the fair allocation of indivisible items among $n$ agents with additive valuations (or costs) using the fairness notion of maximin share (MMS). Since MMS allocations do not always exist when $n > 2$, one direction in the literature has been to identify special classes of instances in which exact MMS allocations can be guaranteed. We show that, when items can be divided into two types of chores, MMS allocations always exist and can be computed in polynomial time using a novel geometric approach inspired by prior work in job scheduling. We further discuss how our technique extends to instances with two types of goods, as well as mixed instances consisting of one type of objective good and one type of objective chore.

Regret matching (and its variants) and counterfactual regret minimization are central algorithms in practice for normal-form and extensive-form game solving. Yet these have historically lacked the stronger theoretical convergence guarantees available to optimistic and extra-gradient methods. Recent work introduced IREG-PRM+, a regret matching variant which does have strong theoretical convergence guarantees. However, it relies on a simultaneous, extra-gradient update. IREG-PRM+ is an instance of the more general IR-PRM framework, where empirically optimistic and alternating updates often have better performance. However, the prior extra-gradient analysis does not extend to these cases. We introduce a new approach that covers both settings. For simultaneous and alternating IR-PRM+ in finite two-player zero-sum matrix games, previous-utility prediction recovers the constant-regret and convergence-rate guarantees previously obtained with extra-gradient prediction: external regret bounded independently of T, an O(T^{-1}) average duality gap, and an O(T^{-1/2}) best-current-iterate gap. Moreover, the current duality gap vanishes and the current profile converges to the Nash equilibrium set. The key step bounds the component of consecutive strategy movement not controlled by the existing IR-PRM+ regret inequality using the relative growth of the nondecreasing regret-vector norm rho_t. Coupling this bound across the two players yields recurrences whose effective coefficient scales as 1/(rho_t^X rho_t^Y), preventing unbounded norm growth. We extend the analysis to finitely many simplex learners under a weighted Minty condition and, through the corresponding CFR variant IR-PCFR+, recover analogous guarantees for finite two-player zero-sum perfect-recall extensive-form games under the same full-reach condition as prior work.

The resilience and censorship resistance of a blockchain depend on where the validators and proposers of that blockchain physically operate. We study the economic incentives behind this location choice, both with a single proposer and with multiple concurrent proposers. Formally, we study a game where proposers first choose locations and then compete in a first-price auction for an opportunity whose common value is driven by information from geographically dispersed sources. A single proposer minimizes variance-weighted delay, locating at a weighted median of the sources and co-locating with any dominant one. By contrast, with two proposers, information both observe equally early earns no rent, and each proposer's expected profit is proportional to the standard deviation of the information it receives before its rival. We show that the location game admits the jointly unobserved variance as an ordinal potential, so global solutions of a weighted two-median problem are equilibria. With two sources, one proposer locates at each, however weak one is. With more proposers and at least as many sources, equilibrium locations are distinct under regular bidding. Multiple concurrent proposers thus do more than limit any single proposer's control over inclusion: by rewarding exclusive rather than shared information, they create an economic force toward geographic decentralization.

We study the complexity of computing approximate first-order Nash equilibria in min-max optimization problems with one dimensional min and max players and product constraints. For black-box access to the objective, we prove that any algorithm requires $\Omega(1/\sqrt{\epsilon})$ queries to find an $\epsilon$-first-order Nash point. In the white-box setting, we establish CLS-hardness by reducing from End-of-Potential-Line. These results show that even the simplest min-max setting with one dimensional min and max players is at least as hard as CLS and therefore does not admit polynomial-time algorithms unless $\mathsf{CLS}\subseteq \mathsf{P}$.

Relying on manipulable characteristics to target the allocation of resources is fraught with difficulties. Naively optimal rules lead to falsification and allocative inefficiency. Optimizing the rule for allocative efficiency while accounting for falsification typically induces falsification, at a heavy cost to the agents. Moreover, falsification generates negative externalities. We characterize optimal falsification-proof rules under a broad range of falsification technologies. We also provide an honesty condition under which they solve the unconstrained problem of a planner who maximizes a weighted sum of allocative surplus and agents' welfare.

We prove that the last iterate of Optimistic Follow-The-Regularized-Leader (OFTRL) converges at a linear rate to a Nash equilibrium in multiplayer harmonic games. Our result holds under a mild game-regularity condition and for a large family of regularizers, including entropy, Tsallis, and log-barrier. Our analysis is based on a dual perspective of OFTRL: we prove that the interaction between optimism and the global structure of harmonic games leads to the dissipation of an energy function along the dual iterates, for which we establish tight quantitative bounds. Our result also holds for the Extragradient FTRL variant.

We study a class of strategic hypothesis testing problems in which a principal aims to allocate resources among competing agents who possess data or data-generating mechanisms that may be relevant to the principal's goals. Each agent can pay a participation cost to opt into a statistical contract, in which case they generate data from a private distribution and receive an allocation based on a predetermined (and publicly known) mechanism. Each agent is either "null" or "non-null" and the principal's goal is to design the contract to limit the allocation to the former while maximizing transactions with the latter. Using e-values, we define a "continuous-closure," a set of allocations which prevents null agents from profiting in expectation and provides post-hoc risk control for general loss functions under arbitrary dependence. When the loss is the fraction of resources allocated to null agents, the region admits polynomial-time linear optimization. We also give explicit, interpretable closed-form approximations, and we analyze participation from a non-null agent's perspective, giving conditions under which entry into the contract is profitable. Finally, we extend the framework to support online arrival of the agents, in which case the principal has to make irrevocable on-the-fly decisions, and provide a method which gives time-uniform error-control in this setting.

Deep reinforcement learning agents in partially observable competitive games must act on beliefs about an unseen opponent's intent. We study a spatial opponent model: a transformer trained with hindsight-relabelled opponent goals that outputs a subgoal heatmap from the opponent's observed trajectory, fused early into a dueling double DQN. In symmetric constant-sum foraging games with partial observability, the module stabilises training. Plain TD(0) DQN suffers degenerate seeds in three of four one-step configurations, whereas the opponent-model agent never collapses and, wherever training succeeds, recovers the majority of the symmetric game value. Transfers zero-shot to a foraging opponent unseen by the learner, with a positive goal advantage over the baseline, and loses this edge exactly where an information argument predicts: against a full-information tracking adversary whose intent is the learner itself, and on resource-dense maps where both agents saturate. A blindfold ablation, zeroing the heatmap at deployment, decomposes the advantage into two mechanisms: training-time stabilisation, which dominates where the credit assignment is hard and survives blinding on the dense map, and deployment-time inference, whose reliance shrinks as fog thins on the sparse map. We conclude that opponent-goal inference is a stability-and-transfer mechanism whose value is governed by measurable boundary conditions: visibility (fog thickness), opponent intent, and resource density.

Freshness shapes an LLM decision at the moment it is made; the action it commits to is latent, carried out later, in a changing world. We therefore introduce a timestamp theory of decision validity and a decision ledger that realises it. Six timestamps define a decision; a freshness ceiling bounds what up-to-date evidence guarantees at action time, placing the remaining risk in information published afterwards. Accuracy then factorises into two capabilities: routing, which delivers that information to affected decisions before their revision deadlines, and temporal judgment, which reads it for the time of action. The ledger is persistent state holding each decision's times, evidence and background knowledge, indexed by watch conditions written at decision time. Controlled decision streams with exact labels confirm four predictions across five LLMs, from 8B to frontier scale: freshness alone yields exactly the accuracy the ceiling predicts; models act on decisive news once it arrives, so accuracy follows routing; the ledger's index sets what routing reaches, and watch conditions reach indirect dependencies at low exposure; and the remaining errors concern when a change takes effect. Freshness makes a decision right when it is made; routing and temporal judgment keep it right when it is carried out.

We study a truthful facility location problem in which agents have private positions in a metric space and known approval preferences over two distinct facilities. Each agent incurs a cost equal to her total distance from the facilities she approves. The goal is to locate the facilities at a given set of candidate locations so as to approximately minimize either the social cost or the max cost, while incentivizing the agents to report their positions truthfully. This problem was previously studied for line metrics and deterministic mechanisms. We first settle the approximation ratio of deterministic mechanisms for the social cost on the line by establishing a lower bound of $7$, matching the upper bound from previous work, and show that randomization leads to a strict improvement. For the max cost, we show that the previously known optimal deterministic guarantee of $3$ remains tight even for universally strategyproof mechanisms. We then turn to general metric spaces. For deterministic strategyproof mechanisms, we obtain tight approximation ratios of $2n-1$ for the social cost and $5$ for the max cost. We also show that randomization yields substantial improvements for both objectives: for the social cost, we obtain a tight characterization, while for the max cost we establish nearly matching upper and lower

Plurality-voting ensembles aggregate the predictions of multiple base classifiers and output the most voted class, with ties typically broken at random. Despite the simple aggregation rule, attributing the impact of each base classifier to the ensemble's predictions is far from straightforward. That is, a single base classifier's impact depends on how it interacts with the votes of all other classifiers in the ensemble, for example, in resolving ties, and not only on its own predictions. We address the attribution problem using established tools from cooperative game theory, studying the Banzhaf and Shapley power indices for new games modeling plurality voting and random tie-breaking, for binary and multiclass classification settings. Computing power indices is, in general, intractable. Surprisingly, our methods, collectively named ENPOWER, enable the exact computation of Banzhaf and Shapley values in linear time for the binary classification setting and in low-degree polynomial time for the multiclass setting. The algorithms in ENPOWER rely on new combinatorial formulations of the Banzhaf and Shapley indices, yielding closed-form solutions for the binary case and ordinary generating function representations for the multiclass case. We validate empirically the methods in ENPOWER demonstrating their high applicability, providing attribution values not captured by existing methods. We apply the attribution of ENPOWER to: ensemble pruning and prompt-based ensembling of vision-language models.

We study a problem that unifies two major generalizations of popular matchings in the one-sided preference model. In a bipartite graph in which each vertex, or applicant, on one side has preferences over the adjacent vertices, a matching is called popular if it does not lose a head-to-head election against any other matching. Since the seminal work of Abraham, Irving, Kavitha, and Mehlhorn, who gave the first polynomial-time algorithm for finding a popular matching, numerous generalizations of the popular matching problem have been investigated. Two prominent directions are weighted popular matchings, in which each applicant is assigned a voting weight, and popularity problems under matroid constraints. The former admits a polynomial-time algorithm due to Mestre, while the most general form of the latter is the popular common independent set problem, for which a polynomial-time algorithm is given by Kavitha, Makino, Schlotter, and Yokoi. In this paper, we introduce the weighted popular common independent set problem, which simultaneously generalizes weighted popular matchings and popular common independent sets. Our main result is the first polynomial-time algorithm for this problem. A key ingredient of the algorithm is a solution-independent characterization of weighted popular common independent sets, which we establish in this paper. As consequences of our algorithmic result, we obtain polynomial-time algorithms for several previously unresolved problems, including weighted popular matchings with matroid constraints and weighted popular branchings.

The randomized primal-dual framework of Devanur, Jain, and Kleinberg (SODA 2013) splits each unit matching gain between endpoint dual variables according to the matched offline rank. The gain-sharing function affects the certificate but not Ranking's decisions. Keeping the splitting rule and expected edgewise feasibility criterion fixed, we define certifying capacity as the strongest uniform guarantee obtainable by functional optimization over a prescribed function class. Its shortfall from Ranking's actual competitiveness is the certifying gap. We study unweighted online bipartite matching under adversarial arrivals on graphs with online degree at most $d$ and on $d$-regular graphs. The optimized protocol is tight on both degree-one classes and in the unrestricted setting, but has a strictly positive gap on both degree-two classes, even over all measurable nonnegative complementary splits. In both degree-two settings, we determine Ranking's exact competitiveness and the exact certifying capacity over nondecreasing gain-sharing functions. For general $d$, we optimize over nondecreasing, right-continuous functions $f:[0,1]\to[0,1]$ with $f(1)=1$, using their probability-measure representation. Both the certifying capacity and actual competitiveness converge to $1-1/e$ in both instance families as $d\to\infty$. The resulting gap is at most $1/(2ed)+O(d^{-2})$ for online degree at most $d$; on $d$-regular graphs, it vanishes but is at least $(1/(2e)-o(1))/d$. These results distinguish function-class restrictions from limitations of the fixed protocol and motivate tighter randomized primal-dual frameworks.

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their values from independent distributions. We give a universally truthful, polynomial-time $(2+\eps)$-approximation mechanism using $O(\log\!\log m)$ samples from each distribution. The approximation factor is tight even for a single item and without the incentive constraints, due to the classic prophet inequality. Compared to the previous state-of-the-art with the same guarantees [Dütting–Kesselheim–Lucier–Reiffenhäuser–Singla (FOCS 2024)], our running time is exponentially faster, and our sample complexity is doubly-exponentially lower, resolving two explicit open problems by Dütting et al. * Using the same techniques, we also obtain improved mechanisms in the secretary and offline versions, where the values are worst-case, and buyers are processed in either random order (secretary) or without any timing restrictions (offline). After a long line of works, the state of the art in both models is an $O((\log\!\log m)^2)$-approximation due to [Assadi–Kesselheim–Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log\!\log m)$. We indeed obtain an $O(\log\!\log m)$-approximate universally truthful mechanism for the secretary and offline models.

We study the unit-demand pricing problem under min-buying behavior, where customers purchase the lowest-priced item that yields non-negative utility. In contrast to the quasi-linear model, we show that uniform pricing becomes substantially more effective under min-buying. First, we study symmetric environments. We show that for min-buying customers with independent and identically distributed valuations, a uniform price across items is optimal. We then extend this optimality result to all valuations drawn from exchangeable and affiliated distributions. However, uniform pricing is not optimal in all symmetric environments: for min-buying customers we construct an exchangeable and non-affiliated valuation distribution for which the gap between uniform pricing and optimal item pricing is logarithmic in the number of items. This gap is tight and matches the worst-case gap in the quasi-linear setting. Next, we consider asymmetric environments in which valuations are independent but not identically distributed. When these valuations are regular and customers are min-buying, we show that a uniform price guarantees approximately 69.86% of the optimal item-pricing revenue and this is tight. Overall, our results highlight that the value of non-uniform pricing substantially diminishes, and often disappears entirely, under more conservative demand models in which customers engage in satisficing behaviors such as min-buying.

We investigate the growth trajectory of online platforms operating as market makers in two-sided matching markets. Their expansion, often referred to as the “chicken-and-egg dilemma” in the literature, poses an inherent challenge: service providers find value in joining the platform because of the presence of customers, while customers are drawn to the platform by the availability of service providers. Much of the existing literature addresses this expansion challenge through either a static market-clearing lens or aggregate dynamic models, emphasizing how network externalities shape a platform's growth trajectory and equilibrium size. These approaches do not fully capture how gradual growth must be implemented through server-level admission, assignment, and compensation decisions. Embedded in this growth process are intertemporal participation constraints that the platform must satisfy to attract and retain forward-looking servers. To explicitly account for the stochastic dynamics of a platform's gradual growth, we model the system as a Markov process. Potential servers and customers arrive according to Poisson processes, and customer demand is non-decreasing in the number of active servers. Under mild conditions, we characterize the platform's optimal admission, assignment, and compensation policies. The platform admits servers at the maximum feasible rate until it reaches an endogenous target size, which can be smaller than the static market-clearing optimum. In the baseline model, seniority-based compensation acts as an operational substitute for financially subsidized growth: instead of using upfront subsidies to induce early server participation, the platform uses future cash flows to reward early servers for joining when demand is limited and for helping the platform reach later, higher-demand states.

I study a dynamic pricing problem in which a seller with limited inventory must sequentially price a perishable product for arriving customers with heterogeneous valuations. The key difficulty lies in balancing immediate sales against future opportunities under capacity constraints and stochastic customer valuations. I propose a simple, interpretable, and asymptotically optimal dynamic pricing algorithm, called Dynamic Run-Out Pricing (DROP), that adjusts prices in real time based on current inventory and anticipated future demand. Under the assumption that customers' valuations follow bounded or exponential distributions, our theoretical results show that DROP's expected revenue converges to the optimal revenue as market size grows. Unlike traditional notions of near-optimality, where the ratio of the algorithm's revenue to the optimal revenue converges to 1, I show that the absolute difference between the two revenues converges to 0 as the market size increases, underscoring the algorithm's effectiveness. Furthermore, I extend our analysis to heavy-tailed valuation distributions, specifically the Pareto distribution, where standard run-out heuristics severely underprice inventory by ignoring the value of waiting for extreme valuations. To correct this, I introduce the Tail-Aware DROP (TA-DROP) heuristic, which intentionally inflates prices to protect inventory, and I prove that it restores asymptotic optimality with a strict polynomial convergence rate.