专栏首页算法和应用Googol的双面博弈与基于样本的先知不等式
原创

Googol的双面博弈与基于样本的先知不等式

作者:José Correa,Andrés Cristi,Boris Epstein,José A. Soto

摘要:隐秘问题或Googol游戏是在线选择问题的经典模型,在过去五十年中受到了极大的关注。我们考虑问题的变体并探索其与数据驱动的在线选择的关系。具体来说,我们给出了双面都写有任意非负数的标记。这些卡被随机地放置在桌子上的不连续位置上,并且对于每张卡片,也可以随机选择可见侧面。玩家看到所有牌的可见面并想要选择具有最大隐藏值的牌。为此,玩家翻转第一张牌,查看其隐藏价值并决定是选择还是放弃它并继续使用下一张牌。

我们研究两个自然目标的算法。在第一个中,如在秘书问题中,玩家想要最大化选择最大隐藏值的概率。我们证明这可以用至少0.45292的概率来完成。在第二个中,类似于先知不等式,玩家最大化所选隐藏值的期望。我们相对于预期的最大隐藏值保证至少为0.63518。

我们的算法结合了三种基本策略。一种是当我们看到一个大于初始不可见数字的值时停止。第二个是第一次停止最后翻转的卡的值是表中当前不可见数字的最大值。第三个类似于后者,但它还要求最后一个翻转值大于其卡片另一侧的值。

我们将结果应用于具有未知分布的先知秘书问题,但可以访问每个分布中的单个样本。我们的保证改进了1-1 / e这个问题,这是目前最着名的保证,只适用于i.i.d.案件。

原文标题:The Two-Sided Game of Googol and Sample-Based Prophet Inequalities

原文摘要:The secretary problem or the game of Googol are classic models for online selection problems that have received significant attention in the last five decades. We consider a variant of the problem and explore its connections to data-driven online selection. Specifically, we are givenncards with arbitrary non-negative numbers written on both sides. The cards are randomly placed onnconsecutive positions on a table, and for each card, the visible side is also selected at random. The player sees the visible side of all cards and wants to select the card with the maximum hidden value. To this end, the player flips the first card, sees its hidden value and decides whether to pick it or drop it and continue with the next card.

We study algorithms for two natural objectives. In the first one, as in the secretary problem, the player wants to maximize the probability of selecting the maximum hidden value. We show that this can be done with probability at least0.45292. In the second one, similar to the prophet inequality, the player maximizes the expectation of the selected hidden value. We show a guarantee of at least0.63518with respect to the expected maximum hidden value.

Our algorithms result from combining three basic strategies. One is to stop whenever we see a value larger than the initialnvisible numbers. The second one is to stop the first time the last flipped card's value is the largest of the currentlynvisible numbers in the table. And the third one is similar to the latter but it additionally requires that the last flipped value is larger than the value on the other side of its card.

We apply our results to the prophet secretary problem with unknown distributions, but with access to a single sample from each distribution. Our guarantee improves upon1−1/efor this problem, which is the currently best known guarantee and only works for the i.i.d. case.

地址:https://arxiv.org/abs/1907.06001

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关于无意识匹配问题

    作者:Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

    罗大琦
  • 计算的度量集中度:最佳界限,减少量等

    作者:Omid Etesami,Saeed Mahloujifar,Mohammad Mahmoody

    罗大琦
  • 伸展树的先序和后序

    摘要:设T是二叉搜索树。我们证明了关于Splay算法行为的两个结果(Sleator和Tarjan 1985)。我们的第一个结果是通过按照T的预订或T的后序的顺序...

    罗大琦
  • Multi-Robot Collaborative Dense Scene Reconstruction Notes

    An autonomous scanning approach which allows multiple robots to perform collabor...

    无雨森
  • CentOS下redis集群安装

    环境: 一台CentOS虚拟机上部署六个节点,创建3个master,3个slave节点

    肖哥哥
  • Codeforces Round #336 (Div. 2)【A.思维,暴力,B.字符串,暴搜,前缀和,C.暴力,D,区间dp,E,字符串,数学】

    A. Saitama Destroys Hotel time limit per test:1 second memory limit per test:256...

    Angel_Kitty
  • HashMap探索01-源码注解翻译

    当时好奇HashMap与ConcurrentHashMap,在网上找资料时发现基本都是相关的源码分析,想自己看看JDK里面具体有些什么,于是有了这个系列,信马由...

    汐楓
  • redis配置详解

    ##redis配置详解 # Redis configuration file example. # # Note that in order to read ...

    joshua317
  • Docker常用软件安装之Redis

      我们首先需要在root/myredis/conf/redis.conf目录下创建redis.conf配置文件。

    用户4919348
  • RFC2616-HTTP1.1-Methods(方法规定部分—单词注释版)

    zaking

扫码关注云+社区

领取腾讯云代金券