论文标题
非自适应催化先知的不平等现象
Non-Adaptive Matroid Prophet Inequalities
论文作者
论文摘要
我们研究了非适应性算法，用于矩阵先知不平等。自2012年[KW12]引入阈值以保证对先知的紧密2及阈值以来，已经考虑了Matroid先知的不平等现象。但是，该算法是自适应的。 [CHMS10]和[FSZ16]的其他方法使用了具有可行性限制的非自适应阈值。但是，这意味着当项目无法获得附加的可行性约束时，将项目的阈值更改为无穷大，因此该算法并不是真正的非适应性。先知不平等的主要应用是在拍卖设计中，非自适应价格具有重要优势：它们转换为符合订单的张贴价格，对于将先知不平等转化为多维买家的真实机制至关重要。现有的Matroid先知不平等不足以解决此应用。我们提出了第一个非自适应恒定因素先知的先知不平等，用于图形曲霉。
We investigate non-adaptive algorithms for matroid prophet inequalities. Matroid prophet inequalities have been considered resolved since 2012 when [KW12] introduced thresholds that guarantee a tight 2-approximation to the prophet; however, this algorithm is adaptive. Other approaches of [CHMS10] and [FSZ16] have used non-adaptive thresholds with a feasibility restriction; however, this translates to adaptively changing an item's threshold to infinity when it cannot be taken with respect to the additional feasibility constraint, hence the algorithm is not truly non-adaptive. A major application of prophet inequalities is in auction design, where non-adaptive prices possess a significant advantage: they convert to order-oblivious posted pricings, and are essential for translating a prophet inequality into a truthful mechanism for multi-dimensional buyers. The existing matroid prophet inequalities do not suffice for this application. We present the first non-adaptive constant-factor prophet inequality for graphic matroids.
