对抗全能对手的拟阵先知不等式：单样本即足够
One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究拟阵上的先知不等式问题：每个元素只需一个独立样本，作者声称即可在任意有限拟阵上获得常数竞争比。摘要表示，即使到达顺序对手能看到全部样本、全部在线取值以及算法的整个随机种子，该保证仍成立；规则无需知道取值分布，绝对竞争比为2^{-310}。研究意义在于把样本需求降到每元素一个，并强化了对手能力假设。
- 每个元素仅需一个独立样本即可构造规则
- 对手可观察样本、在线取值与算法随机种子
- 无需分布描述，声称绝对竞争比为2^{-310}
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that one independent sample per element suffices for a constant-competitive prophet inequality on every finite matroid. The guarantee holds even when the arrival-order adversary observes all samples, all online values, and the algorithm's entire random seed. The rule needs no description of the value distributions and achieves the absolute competitive ratio $`2^{-310}`$.
用户标记：未标记
固定编号：04090c43eedec02e
原文来源