Cover Image

Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Liu, Junyan, Chen, Ziyun, Wang, Kun, Luo, Haipeng, Ratliff, Lillian J.
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms Computer Science and Game Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Prophet Secretary and Matching: the Significance of the Largest Item
by: Chen, Ziyun, et al.
Published: (2024)

Combinatorial Stationary Prophet Inequalities
by: Patel, Neel, et al.
Published: (2023)

Prophet Inequalities with Cancellation Costs
by: Ekbatani, Farbod, et al.
Published: (2024)

Simultaneous Swap Regret Minimization via KL-Calibration
by: Luo, Haipeng, et al.
Published: (2025)

Matching with Nested and Bundled Pandora Boxes
by: Bowers, Robin, et al.
Published: (2024)

Multi-Unit Combinatorial Prophet Inequalities
by: Chawla, Shuchi, et al.
Published: (2025)

Threshold Testing and Semi-Online Prophet Inequalities
by: Hoefer, Martin, et al.
Published: (2023)

Optimal Single-Choice Prophet Inequalities from Samples
by: Rubinstein, Aviad, et al.
Published: (2019)

Pandora's Box Problem With Time Constraints
by: Amanatidis, Georgios, et al.
Published: (2024)

Single-Sample Prophet Inequalities via Greedy-Ordered Selection
by: Caramanis, Constantine, et al.
Published: (2021)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
by: Rubinstein, Aviad
Published: (2016)

Static Pricing for Single Sample Multi-unit Prophet Inequalities
by: Nuti, Pranav, et al.
Published: (2024)

Improved Mechanisms and Prophet Inequalities for Graphical Dependencies
by: Livanos, Vasilis, et al.
Published: (2024)

Pandora's Box Problem with Order Constraints
by: Boodaghians, Shant, et al.
Published: (2020)

Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach
by: Livanos, Vasilis, et al.
Published: (2024)

Pandora's Problem with Combinatorial Cost
by: Berger, Ben, et al.
Published: (2023)

Prophet Inequalities: Competing with the Top $\ell$ Items is Easy
by: Molina, Mathieu, et al.
Published: (2024)

Prophet and Secretary at the Same Time
by: Kehne, Gregory, et al.
Published: (2025)

Trading Prophets with Initial Capital
by: Azar, Yossi, et al.
Published: (2025)

Improved Algorithms for Contextual Dynamic Pricing
by: Tullii, Matilde, et al.
Published: (2024)

Prophet Upper Bounds for Online Matching and Auctions
by: Soto, José, et al.
Published: (2024)

Trading Prophets: How to Trade Multiple Stocks Optimally
by: Rajput, Surbhi, et al.
Published: (2025)

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
by: Rubinstein, Aviad, et al.
Published: (2026)

Stochastic Online Correlated Selection
by: Chen, Ziyun, et al.
Published: (2024)

High-Dimensional Calibration from Swap Regret
by: Fishelson, Maxwell, et al.
Published: (2025)

Strategizing against No-Regret Learners in First-Price Auctions
by: Rubinstein, Aviad, et al.
Published: (2024)

Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability
by: Collina, Natalie, et al.
Published: (2024)

Contextual Learning for Stochastic Optimization
by: Heuser, Anna, et al.
Published: (2025)

Online Learning for Uninformed Markov Games: Empirical Nash-Value Regret and Non-Stationarity Adaptation
by: Liu, Junyan, et al.
Published: (2026)

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising
by: Ali, Dildar, et al.
Published: (2025)

Regret Bounds for Competitive Resource Allocation with Endogenous Costs
by: Chai, Rui
Published: (2026)

Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection
by: Chen, Liyan, et al.
Published: (2024)

Improved Parallel Algorithms for EF1 Allocations
by: Gowda, Kishen N, et al.
Published: (2026)

Computing Optimal Regularizers for Online Linear Optimization
by: Gatmiry, Khashayar, et al.
Published: (2024)

Equilibria, Efficiency, and Inequality in Network Formation for Hiring and Opportunity
by: Dwork, Cynthia, et al.
Published: (2024)

Revisiting Fair and Efficient Allocations for Bivalued Goods
by: Liu, Hui, et al.
Published: (2026)

Maximizing social welfare among EF1 allocations at the presence of two types of agents
by: Ma, Jiaxuan, et al.
Published: (2025)

Strategic Facility Location via Predictions
by: Chen, Qingyun, et al.
Published: (2024)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?
by: Wang, Zhonghao, et al.
Published: (2026)