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.

Wed 4 NovData Structures and AlgorithmsComputer Science and Game Theory
The gist
This paper studies two related online problems where you have to choose elements or bundles arriving one by one, with values drawn from known distributions. The authors show it is possible to slightly outperform the previously best known success rate for matroid problems by using new algorithms. However, they prove that for combinatorial auctions with a specific kind of valuation called XOS, you cannot do better than the old benchmark. This reveals a fundamental difference between these two types of problems, related to the structure they have.
Open → 2611.06891v1

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.

Tue 20 OctArtificial Intelligence
The gist
Online systems that recommend apps need to understand what users want by looking at both their past actions and other related information. The authors found that mixing these different kinds of information directly can confuse the system because they mean different things. They created EASformer, a method that separates and aligns these pieces better so the system can predict what users want more accurately. Tests with real app data and live experiments showed small but meaningful improvements in ranking and revenue.
Open → 2610.27691v1

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.

Tue 13 OctData Structures and AlgorithmsComputer Science and Game Theory
The gist
This paper studies how well a certain math method can prove guarantees about online matching problems, where you pair items arriving one by one. The method shares matching gains between matched items based on their ranking, but the authors show that for some types of graphs with low connectivity, this method cannot fully explain how well a common algorithm performs. They find exact limits of the method’s guarantees in simple cases and show the gap shrinks as the graph becomes more connected. Their work identifies when this proof approach is tight and when it falls short.
Open → 2610.17545v1

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.

Mon 12 OctSocial and Information Networks
The gist
Sometimes networks, like online social sites, don't have complete records of who connected with whom, especially when things change quickly. The authors introduce a method called HSCR that looks at how users’ activities change and uses what is known about the network to guess which new connections have been made but not recorded. This helps keep the network’s record accurate even when direct connection data is missing or delayed. They tested HSCR on several synthetic and real datasets and found it ranks true new links better than existing methods.
Open → 2610.16934v1

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\%\).

Mon 12 OctMachine Learning
The gist
This paper addresses the problem of making good decisions when the effects of actions change over time and outcomes shift in ways that can confuse simple models. The authors focus on finding the part of the response to actions that stays consistent even as overall outcome levels drift. They develop a new method that carefully separates stable action effects from shifting baselines and variations, enabling reliable decision rules that work well now and in the future. Their approach was tested on simulated data, a retail dataset, and a real-world online shopping platform, showing practical improvements.
Open → 2610.16644v1

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.

Sat 10 OctMachine Learning
The gist
Measuring and predicting when events happen over time, like market reactions, is tricky because reactions can echo and overlap. The authors use a math tool called phase-type processes to model these events exactly, allowing clear measurement and reliable prediction. They show this method works well to understand market moves after economic news and outperforms existing methods for predicting various event streams. Their approach also provides guarantees on the quality of the model fit.
Open → 2610.14948v1

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.

Mon 5 OctInformation Retrieval
The gist
Generative recommendation systems suggest items using sequences of tokens, but they often focus only on accuracy, sometimes recommending untrustworthy content like fake news. The authors present a new approach called CreGR that improves trustworthiness by teaching the system to recognize and separate credible from uncredible content tokens. Then, during the generation of recommendations, the system reduces the influence of tokens linked to untrustworthy items without hurting accuracy. Tests on real datasets show that this method makes recommendations both accurate and more credible.
Open → 2610.05670v1

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.

Mon 28 SeptComputer Science and Game Theory
The gist
The paper studies how to fairly divide indivisible items among people who value them differently and may act strategically. Previous work showed it’s possible to guarantee each person a fair share based only on their rankings, but that share decreases as the group grows. The authors confirm a prediction that knowing exact values lets you do better: their method ensures everyone gets at least one-seventh of their fair share, and no one envies others before the division. This method runs efficiently and uses randomness cleverly to be truthful and fair.
Open → 2609.35670v1

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.

Fri 25 SeptComputer Science and Game Theory
The gist
This paper explores how much benefit can be gained from trading things when many buyers and sellers match up, each with their own private values. The authors find exact limits on how efficient trade can be under certain fairness and incentive constraints, even when there are many types of buyers and sellers. Their results expand known insights from simple one-on-one trades to complex markets where multiple matches happen. They measure precisely how close practical trade outcomes come to the best possible trade outcomes.
Open → 2609.30702v1

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.

Thu 17 SeptMachine Learning
The gist
This paper looks at how computers decide between multiple options when the overall success rate changes over time. The usual methods remember each option’s absolute performance, which can get outdated if conditions shift. The authors propose a new method called Odds-Ratio Thompson Sampling that focuses on comparing differences between options instead, refreshing the shared baseline regularly. Their tests show this new method makes better decisions when conditions vary and avoids misleading memory problems. However, when the differences between options themselves change a lot, this method does not help.
Open → 2609.19709v1

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.

Thu 17 SeptComputer Science and Game Theory
The gist
This work looks at how players can get better at making decisions in games where multiple people compete and cooperate. It shows that a specific learning method called Optimistic Hedge can learn faster and make fewer mistakes over time compared to previous approaches. The authors prove this by using a new mathematical analysis that allows the method to use a larger learning step. This improvement means players’ average strategies stabilize closer to an equilibrium faster than before.
Open → 2609.19677v1