Papers for
online platform engineers
Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.
Matroid prophet secretary algorithms beat limits of combinatorial auctions
Prophet Secretary for Matroids and XOS Valuations: A Strict Separation at $1-1/e$
Abstract: The matroid prophet-secretary problem asks an online algorithm to select an independent set of elements whose nonnegative values are drawn independently and revealed in uniformly random order. Its combinatorial-auction counterpart asks the algorithm to allocate disjoint bundles to arriving buyers with independently drawn XOS valuation functions. In both problems the distributions are known, and the benchmark is the expected offline optimum. Ehsani, Hajiaghayi, Kesselheim, and Singla (SODA 2018) give $(1-1/e)$-competitive algorithms for both settings. In this work we show that these two guarantees have different limits. For every matroid, we give a randomized $(1-1/e+\varepsilon_0)$-competitive algorithm, where $\varepsilon_0=10^{-6}$. The guarantee holds for independent nonnegative values with finite expected optimum. For explicitly given finite distributions with rational values and probabilities, the algorithm has polynomial worst-case running time in the matroid independence-oracle model. The oracle tests whether a queried set is independent. The algorithm makes $O(N^4)$ such queries in expectation and $O(N^4\log(N+2))$ in the worst case, where $N$ is the number of elements. For combinatorial auctions with XOS valuations, however, we show that $1-1/e$ is the optimal competitive ratio. We give an explicit family of finite instances showing that no online algorithm can guarantee a larger competitive ratio than $1-1/e$, even when the buyers' valuations are independent and identically distributed, every additive clause has coefficients in $\{0,1\}$, and computation is unrestricted. Thus the matroid improvement exploits structure absent from general allocation with XOS valuations.
EASformer improves app ranking by aligning user behavior and context
EASformer: Environment-Action-State Alignment for Industrial Generative Ranking
Abstract: Modern industrial ranking systems increasingly adopt generative recommendation (GR) paradigms, in which user behavior sequences and non-sequential (NS) features are tokenized and jointly modeled by Transformer-style backbones. This unified formulation provides a scalable interface for modeling long histories and heterogeneous features. However, sequence and NS representations often carry asymmetric semantics: historical representations may combine environment context with observed-action semantics, whereas candidate-side NS representations contain no observed action but incorporate richer supplementary context, such as user-item interaction features and recent behavior lists. Direct interaction between such representations can make query-key dot products compare different semantic objects, limiting meaningful cross-token interaction. To fill this gap, we propose EASformer, an Environment-Action-State disentangled architecture for industrial app ranking. EASformer constructs an explicitly aligned context environment space shared by historical and non-sequence tokens, while disentangling user actions from historical token and candidate-specific context form non-sequence tokens. Based on this aligned space, EASformer enables complementary historical action retrieval and state-conditioned action prediction. Furthermore, the disentangled design supports a Cloze-style self-supervised objective by masking historical actions and reusing the candidate prediction pathway. On an offline benchmark from a real-world industrial app marketplace, EASformer achieves an AUC of 0.89411, yielding a 0.88% relative improvement over the deployed baseline. Online A/B tests further support this advantage, with relative eCPM lifts of 1.26% and 3.94% across two real-world ranking scenarios.
Certifying limits of gain-sharing methods for online matching problems
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Abstract: 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.
Inferring missing network links from activity patterns with partial data
Inferring Hidden Structural Changes from Node-State Responses under Partial Network Observations
Abstract: Online platforms often expose activity signals even when records of the underlying connections are incomplete or delayed. These activity responses may retain indirect evidence of connections that formed during the observation period but are absent from the recorded topology. Recovering such hidden structural changes can help keep network records aligned with evolving interactions and support downstream network analysis. However, the effects of a change propagate through the network and may overlap, making state changes difficult to associate with specific connections. We propose the Hierarchical Structural Context Ranker (HSCR), which combines visible network structure with node-state changes to infer connections that have formed but remain unrecorded. By jointly modeling the topological context of state responses and associations among potential connections, HSCR converts distributed activity changes into evidence for distinguishing potential connections without prespecified dynamical equations or parameters. Experiments on five temporal-network benchmarks and a real temporal Reddit network validate its effectiveness. Across observation spans and structural-record delays, true added connections achieve a 36%-50% reduction in mean true rank relative to the corresponding best baselines. This work provides a principled way to prioritize unrecorded additions for structural verification and record maintenance in online communities, information networks, and other networked systems.
Stable decision making despite changing outcomes in time series data
Learning Deployable Causal Action Geometry under Temporal Non-Stationarity
Abstract: Learning a response law for continuous decisions from observational time series is central to many real-world decision systems, yet temporal non-stationarity poses a fundamental challenge: as outcomes drift over time, naively pooled models can conflate action effects with shifting baselines and even reverse action rankings. Even when the one-step response is identifiable, unrestricted cross-time generalization remains fundamentally ill-posed. We therefore seek the part of the response that remains stable for decisions even when outcome levels do not. We propose deployable causal action geometry: the action-response shape that remains after anchoring away action-independent level shifts on a selected link scale and profiling out positive amplitude variation. Building on this target, we develop a two-stage orthogonal estimator that first obtains cross-fitted pilot estimates of anchored responses and then performs honest profiled selection over link, representation, and shape classes. The resulting estimator admits oracle guarantees for the restricted target and, under approximate persistence, produces decision rules that remain near optimal in future periods. Experiments on synthetic data and Dominick's support the proposed target and its transfer behavior. In a randomized Taobao A/B test, the deployed system improves GMV and purchase counts by \(1.16\%\) and \(1.70\%\).
Phase-type processes improve event stream measurement and prediction accuracy
Exact Phase-Type Point Processes for Certified Measurement and Prediction of Event Streams
Abstract: Temporal point processes are used both to measure market mechanisms, for example how fast prices absorb news and how much of the reaction is the market responding to itself, and to predict the next event. We show that one algebraic object, the phase-type (Erlang-chain) state space, serves both purposes with exact likelihoods. For measurement, we build a multiscale phase-type Hawkes process whose parameters all enter linearly. Its log-likelihood is concave, and we compute the global maximum together with a Fenchel duality-gap certificate. A Markov embedding gives the response to an exogenous shock, echoes included, in closed form, and this response is stable if and only if the spectral radius of the branching matrix is below one. Applied to six markets around 670 scheduled macroeconomic releases (2022-2026) with a built-in placebo test, the model shows that the direct reaction to CPI, payrolls, PPI and the FOMC statement is absorbed in about a second, while the market's own echoes stretch half of the response to 16-137 s. For prediction, we introduce EPT-X, a neural point process that adds a history-dependent mixture-of-Erlang renewal channel to a linear Hawkes backbone. Its intensity and compensator remain in closed form, its states follow an affine recursion that trains with a parallel scan, and it can start from the certified fit of the measurement model. EPT-X has the best test likelihood on all five LOBSTER order-book streams and on Retweet and Taobao, and is level with the best published model on StackOverflow. We also find that the EasyTPP implementation of IntensityFree clamps short inter-event times before scoring, and that the gaps of the EasyTPP Amazon data are uniform on two fixed intervals.
Generative recommenders produce more trustworthy content with new technique
Generate What You Can Trust: Content Credibility in Generative Recommenders
Abstract: Generative recommendation (GR) represents items with semantic IDs (i.e., discrete token sequences) and generates target item tokens as recommendations. Despite its promising results, existing methods predominantly optimize for accuracy while neglecting the credibility of the recommendations they generate. This oversight inevitably exposes users to uncredible content (e.g., fake news) with serious societal consequences, including user distrust, reputation harm to platforms, and broader social instability. To address this critical yet underexplored challenge, we propose CreGR, the first credible GR model that jointly tackles content credibility across the two core stages of GR: tokenization and generation. In the tokenization stage, we design a new credibility-aware tokenizer that explicitly encourages the model to learn discriminative tokens respectively for credible and uncredible items, thereby disentangling credibility signals at the token level. Building on this, in the generation stage, we propose a novel accuracy-preserving and credibility-oriented generator grounded in discrete diffusion. Specifically, we introduce an asymmetric masking probability reduction strategy that selectively diminishes the contribution of tokens associated with uncredible content to the generation process, while leaving tokens encoding user preference signals unaffected so as to preserve recommendation accuracy. Experiments on three real-world datasets demonstrate the effectiveness of CreGR.
Truthful mechanism guarantees fair share of indivisible goods for agents
Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee
Abstract: We study the truthful and fair allocation of indivisible goods to $n$ strategic agents with additive valuations. Babaioff, Feige, and Manaker Morag [FOCS 2026] gave a randomized mechanism that uses only the agents' rankings of the goods, is truthful in expectation (TIE), and guarantees every agent $1/(H_{n-1}+2)=Θ(1/\log n)$ of her maximin share (MMS) in every realized allocation, where $H_{n-1}$ is the $(n-1)$th harmonic number; this is nearly the best possible with rankings alone. They conjectured that cardinal information allows TIE mechanisms to achieve a constant ex-post MMS guarantee. We confirm this conjecture: our TIE mechanism guarantees every agent at least $1/7$ of her MMS in every realized allocation; moreover, the mechanism is ex-ante envy-free and can be implemented in polynomial time. Our mechanism has two key technical ingredients, both of which may be of independent interest. The first is a truthful fractional allocation rule specifying each agent's probability of receiving each good: it favors each agent on her top $n-1$ goods and reduces her probability of receiving a good for each other agent who also ranks it among her top $n-1$ goods. The second is the balanced edge coloring: we decompose these probabilities into equally likely matchings from agents to high-value goods, those that alone meet an agent's guarantee, and balance these matchings in a fine-grained way without changing any marginal probability, so that every agent who receives no high-value good can obtain sufficient value from the remaining goods without over-allocating any good.
Matching markets achieve most trade gains with simple rules
From Bilateral Trade to Matching Markets: Sharp Gains from Trade
Abstract: 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.
Thompson sampling method improves bandit decisions with changing baselines
Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits
Abstract: Batched multi-armed bandits update on a service's own schedule, and the usual implementation carries each arm's absolute reward rate from one update to the next. When the shared level moves between batches, that memory goes stale even though the comparisons between arms may not have. Odds-Ratio Thompson Sampling (OR-TS) instead carries the joint posterior over log-odds contrasts and fits the common level afresh in every batch, marginalizing it out. This paper specifies that update, places it inside a Bayesian bandit agent with two controls, decay for how much past evidence survives an update and aggressiveness for how sharply belief becomes allocation, and evaluates it against absolute-rate memory. Across 86 public A/B series the level varies about twenty-five times more than the contrast. In prespecified synthetic environments a moving level costs absolute-rate memory five times the regret and leaves the best arm below a majority of traffic in 7 of 20 runs, against none for OR-TS. In a policy simulation built from 71 real experiments, where the contrasts are too small to resolve, expected-click differences stay within 0.1% for 58 of them, yet contrast memory still ends on the better arm more than twice as often. Where the contrasts themselves move, the bet fails, and that case is reported too.
Optimistic hedge achieves lower regret in multiplayer games
A Logarithmic Regret Bound for Optimistic Hedge in General-Sum Games
Abstract: Can simple no-regret dynamics attain smaller regret in self-play than against arbitrary adversaries? In $n$-player general-sum games, Daskalakis et al. 2021 proved an $O(n\log d_i\log^4 T)$ individual regret bound for Optimistic Hedge, which improves upon the classical $O(\sqrt T)$ adversarial regret bound. In this work, we show that Optimistic Hedge with a constant step size can further achieve $O(\sqrt n\log d_i\log T)$ individual external regret under expected loss-vector feedback. The time-averaged play consequently enjoys a coarse correlated equilibrium gap $O(\sqrt n\log d\log T/T)$, where $d=\max_i d_i$. The improvement comes from a larger admissible step size $η=Θ(1/(\sqrt n\log T))$. Our analysis proves factorial bounds on high-order differences of probability-weighted pairwise loss gaps, then applies finite-difference interpolation in a fixed Euclidean norm. These estimates sharpen the analysis of Daskalakis et al. 2021 and yield a logarithmic regret bound.