{"ID":23507403,"CreatedAt":"2026-09-18T02:21:44.056544415Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20696","arxiv_id":"2609.20696","title":"A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities","abstract":"We study prophet inequalities under intersections of $q$ partition matroids, where an online algorithm irrevocably selects elements with independent nonnegative values drawn from known distributions and revealed in an adversarial order. We prove an $Ω(q/\\log q)$ lower bound on the competitive ratio. Together with the known $O(q)$ upper bounds, this resolves, up to a logarithmic factor, the optimal dependence on $q$, an open question posed by Correa, Cristi, Fielbaum, Pollner, and Weinberg (IPCO 2022) and Saxena, Velusamy, and Weinberg (ITCS 2023). Our construction also yields an $Ω(d/\\log d)$ lower bound for $d$-single-minded auctions, where buyers request fixed bundles of at most $d$ unit-capacity items. Our construction and analysis build on the \"big-decisions-first\" framework of Rubinstein and Singla (STOC 2026).","short_abstract":"We study prophet inequalities under intersections of $q$ partition matroids, where an online algorithm irrevocably selects elements with independent nonnegative values drawn from known distributions and revealed in an adversarial order. We prove an $Ω(q/\\log q)$ lower bound on the competitive ratio. Together with the k...","url_abs":"https://arxiv.org/abs/2609.20696","url_pdf":"https://arxiv.org/pdf/2609.20696v1","authors":"[\"Dimitris Fotakis\",\"Charalampos Platanos\",\"Thanos Tolias\"]","published":"2026-09-17T17:00:18Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}