Keyword: online-algorithm

Theorem No Deterministic Constant Competitive Ratio proved

Definition Online Single-Item (Posted-Price) Auction formalized

Theorem Sample-Then-Threshold Rule Is 1/4-Competitive proved

Example Strict Value Comparison Breaks the Competitive Guarantee proved

Theorem Truthful Bidding Is Dominant in the Online Auction proved

Example Weak Value Comparison Degrades to 1/n on the Needle Profile proved