Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents
Improved Prophet Inequalities for Combinatorial Welfare Maximization with (Approximately) Subadditive Agents
复制标题
使用（近似）次加性代理改进组合福利最大化的预言不等式
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Hanrui Zhang
中科院分区：
文献类型：
--
作者：
Hanrui Zhang
7我们给出了一个设计组合福利最大化的预言者不等式的框架。8用不同的ff参数实例化，我们的框架蕴含：(1)次加代理的O(logm/loglogm)-竞争预言不等式，通过项目定价改善O(Logm)上界；10(2)D-近似次加代理的O(Dlogm/loglogm)-竞争预言不等式，11其中D∈{1，.。。，m−1}测量相互补充的最大项数，12和(3)作为副产品，对于子模或分数13次加法(也称为.XOS)代理，渐近匹配最优比率。在给定对先验查询和按需查询的样本访问的情况下，我们的框架在计算上是ffi有效的。15个
7 We give a framework for designing prophet inequalities for combinatorial welfare maximization. 8 Instantiated with different parameters, our framework implies (1) an O (log m/ log log m )-competitive 9 prophet inequality for subadditive agents, improving over the O (log m ) upper bound via item pricing, 10 (2) an O ( D log m/ log log m )-competitive prophet inequality for D -approximately subadditive agents, 11 where D ∈ { 1 , . . . , m − 1 } measures the maximum number of items that complement each other, 12 and (3) as a byproduct, an O (1)-competitive prophet inequality for submodular or fractionally 13 subadditive (a.k.a. XOS) agents, matching the optimal ratio asymptotically. Our framework is 14 computationally efficient given sample access to the prior and demand queries. 15