跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+907新增论文
+744其中 AI 相关
+108已有论文修订
+94新增 AI 导读

arXiv 最近完成扫描:2026-11-19 06:59 · 全站最近入库:2026-11-19 06:59各信源进度 →

统计口径与数据新鲜度

统计 2026-11-18 12:07 — 2026-11-19 12:07(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-19 06:59最近发现新增版本:2026-11-19 06:59库内论文最新更新时间:2026-11-18 08:00

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

26,871 已收录论文22,375 AI 相关8,156 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 4 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-19 06:57(北京时间)
新论文 · v1arXiv:2611.22923

A short proof of the 1-1/e performance of RANKING on the complete upper triangular instance

Giovanni Montanari, Nadav Merlis, Simon Mauras, Vianney Perchet

原文摘要

The randomized online bipartite matching algorithm RANKING of Karp, Vazirani and Vazirani (1990) matches, asymptotically, a fraction $1-1/e$ of the vertices of the complete upper triangular (CUT) instance. We give a short proof of this fact that looks at the final matching from the offline side. A single observation drives the argument: the first $k$ arrivals can distinguish the offline vertices $v_k,\ldots,v_n$ only through their ranks. As a consequence, whether $v_k$ is matched is decided by a uniform draw among the remaining ranks, and the number of matched vertices among $v_1,\ldots,v_k$ is a Markov chain with explicit transition probabilities. A linear differential equation, solved by hand, gives the limiting profile of this chain, and the constant $1/e$ appears where the matching probability reaches one.

cs.DS

版本更新 · v2arXiv:2606.30118

Effective Horizons for Prophet Inequalities with Discounted I.I.D. Rewards

Jung-hun Kim, Vianney Perchet

原文摘要

We study prophet inequalities for $n$ i.i.d. base rewards subject to multiplicative discounts across $S$ phases. For equal-length phases and a common discount factor $\widetildeγ$, we characterize the optimal competitive ratio of single-quantile policies as $n\to\infty$ with $S$ and $\widetildeγ$ fixed. The resulting sharp guarantee describes the dependence on the phase parameters: it recovers $1-1/e$ without discounting and approaches $1/2$ in the worst-case regime. We also establish a distribution-free comparison that bounds the discounted prophet by a fractional i.i.d. maximum with effective horizon $B$, the sum of the discount weights across all observations. The comparison yields acceptance probability $1/B$, determined only by the phase profile. This calibration attains the canonical optimum even among single-quantile policies that may choose their acceptance probability using the known base distribution. The comparison also gives guarantees for heterogeneous discounts and unequal phase lengths. A complementary optimal-stopping upper bound establishes the same limiting optimum of $1/2$ for arbitrary stopping rules in the canonical model. Finally, the same effective-horizon calibration sets acceptance probability $1-\widetildeγ$ under infinite-horizon geometric discounting. This explicit quantile rule attains Boshuizen's (1994) known optimal worst-case ratio $1/(1+\widetildeγ)$ without solving a Bellman equation.

cs.GT · cs.DM · cs.DS · econ.TH · math.OC

版本更新 · v2arXiv:2610.32503

Pareto-optimal Non-Clairvoyant Scheduling with Predictions

Ziyad Benomar, Vianney Perchet

原文摘要

We study preemptive single-machine non-clairvoyant scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\varepsilon$ is achievable with robustness $\varepsilon^{-1/2}+\frac16+O(\sqrt\varepsilon)$, whereas all previous algorithms required robustness $Θ(1/\varepsilon)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions. Furthermore, we give a simple randomized algorithm, using predicted sizes, with consistency $1+\varepsilon$ and robustness $(3\varepsilon)^{-1/2}+O(1)$, strictly below the deterministic frontier. The question of determining the Pareto-optimal frontier among randomized algorithms remains open.

cs.DS · cs.GT

版本更新 · v3arXiv:2406.15680

校准预测与说服

Calibrated Forecasting and Persuasion

Atulya Jain, Vianney Perchet

AI 速读 基于摘要

研究专家在决策者用基于历史数据的校准检验验证预测时,如何发送概率预测以最大化自身收益。

econ.TH · cs.GT

查看原文摘要

We study a dynamic game where an expert sends probabilistic forecasts to a decision-maker. The decision-maker verifies these forecasts using a calibration test based on past data. How should the expert send forecasts to maximize her payoff while passing the test? For a stationary ergodic process, we characterize the optimal forecasting strategy by reducing the dynamic game to a static persuasion problem. Calibration restricts long-run forecast distributions to mean-preserving contractions of the distribution of truthful forecasts. We compare the payoffs attainable by an informed and uninformed expert, providing a benchmark for the value of information. Finally, we consider a decision-maker who uses a mean-based learning strategy and show that the expert can guarantee at least the calibration benchmark and sometimes strictly more.