One-sample matroid prophet inequalities against an almighty adversary at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

One-sample matroid prophet inequalities against an almighty adversary

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	algorithms, speed	Levels:	1
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.4 out of 5 (5,537 votes)

>>> How to Play <<<

One-sample matroid prophet inequalities against an almighty adversary. For every finite matroid known in advance, gives a distribution-independent online rule using one independent sample per element and earning a universal constant fraction of the expected offline optimum. Values are independent and nonnegative, with finite expected optimum. The guarantee holds even when the arrival-order adversary sees all samples, values, and the rule's entire random seed; no polynomial-time implementation is asserted.

>>> Level Select <<<

LEVEL 1 One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary

released 2026-09-23 | 1 theorem · 15 lemmas · 17 proofs · 12,591 words | PLAY LEVEL 1 » (pdf)

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}$.

More Theoretical computer science Games!
A factor-two approximation for shortest common superstring	Exponential state costs for two-way automata	Fourier transforms below $n\log n$ HOT!	Polynomial mixing of graph switches with prescribed degrees
A counterexample to the quadratic sensitivity conjecture	The complexity of Weisfeiler–Leman refinement	Generalized star height at most three	Sharp homogeneous depth-five complexity of matrix products

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600