{"id":"openai-math/One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary","pdf":"https://github.com/openai/math/blob/main/preprints/One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026/final.pdf","url":"https://github.com/openai/math/tree/main/preprints/One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026","tags":["online-algorithms","prophet-inequality","matroids"],"score":0,"title":"One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary","domain":"Theoretical computer science","family":"111","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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}`$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{},"formalized":false,"family_title":"One-sample matroid prophet inequalities against an almighty adversary"}