计算机科学/离散数学研讨会2

在这次演讲中，我将首先概述TCS组合拍卖的历史，然后讨论一些最近的结果。

组合拍卖围绕以下问题展开:集合M (M)个物品，N (N)个出价人。从M的子集到实数，每个出价人i都有一个价值函数$v_i$。目标是将项目划分为$S_1，\ldots$， $S_n$最大化$\sum_i v_i(S_i)$。

我将介绍这个问题的2x2个变体:

• 计算模型(简要概述和结果声明):n方各自持有$v_i$中的一个，并且它们必须使用poly(n,m) runtime/queries/etc。找到尽可能好的近似值。
• vs.通信模型(主要焦点):n个参与者各自持有$v_i$中的一个，他们必须使用poly(n,m)通信来找到尽可能好的近似值。
• 算法设计版本(一个主要焦点):各方诚实地参与任何提议的协议。
• 机制设计版本(也是一个主要焦点):设计师可以向代理i收取$p_i$的价格。一方i将以任何他们认为最大化$v_i(S_i) - p_i$的方式行事。

我将讨论的结果样本(在不同的详细程度上):

• 对可实现近似的严格限制保证了算法。
• 维克瑞-克拉克-格罗夫斯拍卖:从精确机制设计到精确算法设计的黑盒还原。
• 最大范围拍卖:通过“类vcg”思想实现的近似保证的严格界限。
• 通过算法和机制实现的近似保证之间的分离。

本课程假定没有博弈论或组合拍卖方面的背景。