英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

在线拍卖和广义秘书问题

引言

假设您决定使用以下程序出售物品（比如您的车）。人们一次来到您的车库，评估您的车，并出价从您那里购买。每个人只能提交一个出价，并且在收到要约后，您必须立即决定是接受还是拒绝。决定接受或拒绝哪些出价的最佳策略是什么？在不同的建模假设下，这个问题有不同的答案。我们是否假设出价构成最坏情况序列，随机序列或其他内容？如果出价是随机序列，卖家是否有关于出价值的先前信息？出价顺序与其价值之间是否存在相关性？如果有的话，我们如何模拟投标人的战略行为？

建模频谱的一个极端是在线算法[Borodin and El-Yaniv 1998]中假设最坏情况输入的传统方法。该观点导致非常悲观的界限：没有用于从n个出价的序列中选择一个出价的在线算法（随机或确定性）可以实现比最优收益的O（1/n）分数更好的。另一个极端是根据已知的分布独立地和相同地分配（i.i.d.）的一系列出价。在这种情况下，可以使用动态编程在多项式时间内计算最优策略。

由于第一个极端导致不必要的悲观界限，而第二个极端导致卖方过多的知识，因此在两个极端之间调查模型是很自然的。两个自然候选模型表明自己。（1）出价为i.i.d. 来自未知的分布。（2）对手可以决定出价的价值，但不能决定出示给卖方的顺序。前一种模式类似于机器学习和人工智能中经常采用的方法。实际上，它由第二个模型包含，因为序列可以通过首先从（未知）分布中挑选多组值，然后随机置换它们来确定。

回到销售汽车的目标，我们现在可以正式说明问题如下：

给定随机顺序的n个数字序列，设计用于挑选序列的一个元素的在线算法，以最大化所选元素的期望值。

以这种方式说，问题非常类似于着名的秘书问题：设计用于挑选随机排序序列的一个元素的算法，以最大化挑选整个序列的最大元素的概率。实际上，虽然这两个问题有不同的目标（优化所选元素的期望值与优化选择最大元素的概率），但很明显，秘书问题的解决方案立即产生了一种算法，用于从中选择一个投标。随机排序的出价序列。

前面的例子表明，秘书问题，更一般地说，最佳停止问题与在线拍卖密切相关，并且可以对所选的预期值产生令人惊讶的强有力保证。本文的其余部分调查了该领域的各种最新结果和开放性问题，这些问题自然而然地源于对文章开头提出的单项拍卖应用的一般化和变化的思考。

许多拍卖场景涉及出售多个项目。例如，卖方可以将k个相同的物品以在线方式出售给投标人。在进一步的概括中，投标人可能需要不止一个项目。此方案自然会为网站上的广告展示或人力或机器资源的拍卖建模。它为拍卖提供了在线背包问题的风格。
（2）投标人所需项目集之间的相互作用也可以采用更复杂的形式。自然的例子包括寻求在多个可能的行程中的一个上购买座位的航空旅行者，或者寻求购买多个电影或放映中的一个的票的电影观众。正如我们在下面更详细地描述的那样，这些和几个其他场景自然地被铸造为约束可以共同接受的出价组的拟阵结构。
（3）在拍卖场景中，早期的收入或销售往往比后者更有价值。考虑到问题的时间依赖性，研究时间贴现收入的普遍化以及它对在线拍卖可能产生的预期价值的影响是很自然的。
（4）众所周知，如果投标人允许他们以更便宜的价格购买物品，他们可能会歪曲他们对物品（或其他参数）的真实估价。设计真实拍卖，其中自利竞标者没有动机撒谎，是拍卖设计的一个重要领域。在线拍卖的背景下，激励调整的问题同样有效且重要。

从最初的秘书问题和我们的一般框架工作的正式轮廓开始，我们探讨了上面讨论的四种概括中的每一种。大多数证据将被省略或概述，并且可以在引用的文献中找到。

秘书问题

由于以下激励应用，设计在线算法以优化随机排序序列中选择最大元素的概率的问题传统上称为秘书问题。想象一下，你管理一家公司，你想聘请一个n个申请人的秘书。你非常热衷于雇佣最优秀和最聪明的人。不幸的是，在你采访他之前，你不能说出一个秘书有多好，你必须在面试时决定是否提出要约。由于您的决定是不可撤销的，您必须先聘请一位秘书，然后才能观察尚未接受访谈的申请人的质量。聘请最佳秘书的概率可以给出什么样的保证？

对于某些直觉，让我们考虑只有三个申请人的特殊情况。您可以轻松地保证雇用最好的秘书，概率为1/3：只需随意聘请秘书。你能做得更好吗？事实上，你可以。我们的想法是以随机的顺序采访秘书，并使用第一秘书的质量为您雇用的人设定标准。也就是说，如果三个申请人是Alice，Bob和Charles，那么

1. 随意选择申请人，爱丽丝说，并采访她但不雇用她。让她的品质成为v_A。
2. 随机选择剩下的申请人之一，鲍勃，并观察他的质量vB。如果Bob比Alice好，即v_Bge;v_A，请雇用Bob。否则，雇用第三个申请人Charles。

概率为1/3，您碰巧首先采访了第二好的申请人，在这种情况下，您肯定会雇用最好申请人。此外，概率为1/6，您首先采访最差的申请人，然后采访最佳申请人，在这种情况下，您还会聘请最佳申请人。因此，这种策略有雇用最佳申请人的概率1/2！Lindley [1961]和Dynkin [1963]证明了这种策略在n个申请人的环境中的概括产生了接近最佳秘书的概率接近1 /easymp;0.37，这是最好的保证.4最优策略 非常简单：在没有做出任何招聘决定的情况下，对第一批m/n/e申请人进行面试，然后雇用下一位质量超过第一名申请人的申请人。如果你在没有雇用任何人的情况下到达序列的最后，那么无论如何雇用最后一位申请人。

因为秘书算法选择概率至少为1 / e的随机排序序列中的最大元素，所以相同的算法也可以用于具有随机排序的投标的单项目拍卖，以选择其预期值为至少是最高出价的1 / e倍。该因子1 / e对于原始秘书问题和具有随机排序的出价的在线单项目拍卖是最佳的，尽管在后一种情况下其最优性不容易从其在前一种情况下的最优性。

统一框架

我们考虑的所有问题都可以在以下共同框架中描述，该框架扩展了秘书问题的“在线单项目拍卖”解释。所谓元素的地面集合U对应于投标人，并且子集Isube;2U（在收容下关闭）的集合描述了可以同时接受其投标的投标人集合。（这些也称为可行集。）例如，在单项拍卖的情况下，我是具有至多一个元素的集合的集合。对于广告印象竞价，我是所有集合S的集合，其总请求展示次数总计最多为总可用展示次数。

每个元素xisin;U具有非负值v_x。 我们希望设计在线算法，其中U和I的结构在开始时是已知的，而元素及其值以随机顺序一次一个地显示。在呈现每个元素时，算法必须决定是选择还是拒绝它，受以下约束：

1. 选择或拒绝的决定是不可逆转的。
2. 必须在序列中的下一个元素出现之前做出决定。
3. 所选元素的集合必须始终属于我。

算法的收益通常是输入序列和算法选择的函数。我们将主要讨论这样一种情况，即选择集合S时，算法获得的支付是其元素的值的总和，v(S) = P xisin;S^vx。（文献中已经考虑了支付的替代定义，包括本文后面讨论的时间折扣秘书问题。）用S^lowast;isin;I表示集合最大化v（S^lowast;，我们说算法是alpha;竞争的 如果E[v（S）]le;1/伪路v（对于所有可能的估值函数，则v。对所有排序（排列）和算法的可能随机选择进行预期。这些一起确定集合S.

我们将这一类问题称为广义秘书问题。这些问题与原始秘书问题之间存在重要差异。 在秘书问题本身中，目标（雇用最佳申请人）是一个有序标准，即它仅取决于申请人的相对质量而不取决于归属于他们的任何数值。在我们在此考虑的扩展中，目标是根据数值v_x定义的。

迄今为止所讨论的大多数扩展的最着名的解决方案涉及一种简单的算法思想，其已经在上述秘书算法中预示。算法等待一些规定的时间t并观察最有价值的可行子集Ssube;{1，，，t}。然后，如果他们在想象解决方案S上“改进”（在某种意义上），则选择其他元素。直观的解释是算法在做出任何决策之前试图“感受市场”。因此，它们也与定价算法具有相似性，定价算法使用投标人的子集来确定其他投标人的价格（参见，例如，[Goldberg等人，2001]）。

K-CHOICE秘书问题

当我们考虑出售k个相同的项目而不仅仅是一个时，我们会导致秘书问题的以下扩展：设计一个在线算法，用于从随机顺序中呈现的n个非负数中挑选k，以最大化它们的预期总和。就上述形式框架而言，这对应于I由具有k个或更少元素的U的所有子集组成的情况。

当k = 1时，我们已经看到最优竞争比是e。最佳竞争比率如何随k变化，最佳算法是什么样的？也许最自然的算法考虑以下Dynkin算法的推广：

1. 观察第一个lfloor;n/erfloor;元素。
2. 记住这些第一个lfloor;n/erfloor;中最好的k个元素，并称之为T集。
3. 每当元素到达的值大于T中的最小值元素时，选择该元素并从T中删除最小值元素。

Babaioff等人[2007]，通过一个复杂的计数论证表明，对于k的所有值，该算法的竞争比率不低于e，而不仅仅是k = 1.稍微修改的算法产生相同的竞争比率，更简单的证明。 然而，常数e远非最优，因为kKleinberg[2005]表明，最优竞争比率从上面以1 C/radic;k为界，从下面以1 C/radic; k为界。k对于某些常数clt;C。使用递归算法获得上限。它将序列划分为初始段和大致相等长度的最终段，递归地从初始段中选择至多k/2个元素，并设置等于初始段的第（k/2）个最大元素的阈值。随后，它选择满足此阈值的最终段的所有元素，直到耗尽其分配的k选项。

卡纳菲克秘书问题

假设您正在运行官方超级碗网站，该网站有一个横幅广告位。您知道，在超级碗日，该网站将获得一定数量的展示次数（例如，5000万），并且您希望将这些展示的广告位销售给广告客户。每个广告客户都会收到一些展示次数和他愿意支付的价格的请求。您必须决定是否接受请求，但当然，承诺给不同广告客户的总展示次数不能超过5000万次。如果所有广告商同时到达，则确定接受哪些请求（以最大化收入）的问题是背包问题的实例。如果广告客户以随机顺序上网，我们会将此问题称为背包秘书问题。就上述形式主义而言，每个元素xisin;U的权重w_xgt;0（在我们的超级碗广告示例中，w_x是x请求的5000万次印象中的一小部分），包含总权重的集合不超过1。

众所周知，背包问题是NP完全的，并且它承认FPTAS以及简单的2近似。另一方面，在线背包问题在任何非平凡的乘法因子内是不可接受的。有几篇论文涉及不同假设的在线和随机背包问题[Kleywegt和Papastavrou 1998;迪恩等人。2004;Lueker 1995; Marchetti-Spaccamela和Vercel lis 1995; Buchbinder和Naor 2005]。背包秘书问题在这些问题中是独一无二的，因为成本/价值对的集合是任意的。 我们假设元素以随机顺序到达，而不是对这些对的分布做出假设，而不是假设在线背包问题的不可接近性。

在这个假设下，我们能够将2近似算法适用于我们的设置，以产生具有针对背包秘书问题的恒定竞争比的算法。像往常一样，该算法在不接受任何请求的情况下观察到一定比例的请求。它按请求的值密度v_x/w_x对请求进行排名，并根据采样请求的值密度设置阈值。 在观察到请求序列的初始段之后，算法接受基于标准的元素，该标准主要取决于它们的值密度是否超过阈值。但是，必须通过一些“调整”来增强算法，以适应重量如此之大以至于它们需要背包容量的恒定分数的请求。有关详细信息，请参阅[Babaioff等人的文章]。2007年]。 所提出的算法存在（10e）-竞争性，但背包秘书问题的最优竞争比仍然未知。

马克思司法部长问题

我们到目前为止在本文中描述的每个广义秘书问题都承认了一个持续竞争的算法。 不幸的是，情况并非总是如此。Babaioff等人。[2007]展示了一个广义秘书问题，其中没有算法的竞争比率优于Omega;（log n / log log n）。除了前面讨论的问题之外，还有哪些其他广义的广义秘书问题会让算法具有恒定的竞争比率？一个很有希望的可能性是Matroid秘书问题[Babaioff等人]。在其中，地面集U和可行子集I构成了matroid6结构。许多自然的在线拍卖场景都属于Matroid秘书问题的框架。

1. k-选择秘书问题产生统一的拟阵，其中独立集合恰好是最多k的所有基数集。
2. 上述例2中提到的电影票拍卖可以如下形式化。给n个客户提供价值v_x和m可能的电影，以及指示每个客户会感兴趣的电影的二分图。在每部电影的已知座位容量下，找到最大总价值的客户子集，谁都可以看电影同时他们的选择。由此产生的所有匹配客户都是独立的拟阵被称为横向拟阵。
3. 上面例2中提到的航空公司旅行设置可以形式化如下：每个旅行者，值v_x，寻找从源到目的地的路径，并且每个边缘具有已知的有限容量。目标是在不违反容量限制的情况下，路由一组具有最大总价值的乘客。只要所有来源都相同，所得到的结构就是拟阵，称为类囊体。
4. 在拍卖环境中具有较少自然动机的众所周知的拟阵由图形拟阵组成，其中客户对应于图的边缘，并且目标是选择最大总值的非循环集。

拟阵以非常自然的方式与秘书问题有关。考虑如果我们在广义秘书问题的定义中放松约束1会发生什么，通过规定拒绝一个元素的决定仍然是不可逆转的，但是稍后可以撤销选择一个元素的决定。（约束2和3仍然是强制执行的。特别是，算法不允许接受不可行的集合，然后拒绝它的一些元素。）对于原始的秘书问题，现在有一个明显的算法总是选择最佳元素：只要

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[20028]，资料为PDF文档或Word文档，PDF文档可免费转换为Word