CA——Optimal-Auction-Design论文阅读

Background

• 本文是论文Optimal Auction Design, 1981的阅读笔记
• 本文参考了：Optimal Auction Design 最优拍卖论文笔记, CSDN
• 《拍卖理论》第五章也有相关证明（表示符号不同，问题定义和推导结果相同）

Introduction

• Tips：论文的机制也称为 Myerson 拍卖（迈尔森拍卖）机制
• 论文针对单物品拍卖下，Seller 如何获得最大的收益的问题
  • 单物品拍卖即一个 Seller 有一个物品（Object）, 多个竞价者（Bidder）参与拍卖
• 论文提出一种单物品拍卖下，保证DSIC的收益最大化的机制
  • Tips：单物品拍卖下，二价拍卖是社会福利最大化的DSIC拍卖机制，但不是收益最大化拍卖
  • Tips：单物品拍卖下，假设竞拍者私有估值独立同分布，则带保留价的二价拍卖是等价于Myerson拍卖

Basic Definitions and Assumptions

（本节阐述基本定义和假设）

• 约定一个Seller 准备出售某个商品 (Object)，有 \(n\) 个 Bidders。每个Bidder \(i\) 对该Object有一个估计的价值 \(t_i\) (\(i\) ‘s value estimate)，也即其最大可承担的竞价

• 名词约定：

  • 假设 \(t_i\) 的上下限为 \(a_i, b_i\)， 竞拍者 \(i\) 的私有估值分布（value estimate distribute）即出价分布函数为 \(f_i\)， \(f_i(t_i) > 0\)，而且 \(f_i\) 为一个在区间 \([a_i, b_i]\) 上连续的函数

  • 对应的累计密度函数 \(F_i\) 即： \(F_i(t_i) = \int_{a_i}^{t_i} f_i(s_i)d s_i\) \(F_i(t_i)\) 也是Seller 对竞拍者Bidder \(i\) 的竞价 \(f_i(s_i) \le t_i\) 的估计概率

  • \(T\) 表示Bidders 对估计价值 \(t_i\) 的所有可能组合： \(i [a_1, b_1] \times [a_2, b_2] \times .. \times [a_n, b_n] \)

  • \(T_{-i}\) 表示除去Bidder \(i\) 之外对所有bidders 的估计价值的组合之和 \(T_{-i} = \mathop{\times}\limits_{j \in N, j \neq i}[a_j, b_j] \)

  • 假设所有 \(n\) 个竞价者是相互独立对随机变量，即其联合概率分布为所有 \(f_i(t_i)\) 的乘积 \(f_t = \prod \limits_{j \in N} f_j(t_j)\)

  • 各个竞拍者出价独立的两个主要因素【如何理解？】：

    • 1，偏好不确定，此时竞拍者 \(i\) 了解到对竞拍者 \(j\) 的出价信息不影响 \(i\) 去修改自己的出价，
    • 2，对商品的质量（价值）的估计不确定 (quality uncertainly)，此时竞拍者 \(i\) 了解到对竞拍者 \(j\) 的出价信息后会修改自身的出价

  • 假设存在 \(n\) 个出价调整函数 \(e_j\) : \([a_i, b_i]\)， \(e_j(t_j)\) 表示其他竞拍者 \(i\) 获知到竞拍者 \(j\) 对商品的价值估计 \(t_j\) 后修改自身出价的调整幅度（注意，这里假设了知道竞拍者 \(j\) 的出价信息后，任何一个非 \(j\) 竞拍者修正自己出价的幅度都是相同的 \(e_j(t_j)\) ），即竞拍者出价变为 \(t_i - e_j(t_j)\) 。一般假设 \(e_j(t_j) = 0\) 即对竞拍者知道其他竞拍者的估值后不影响自己的原始出价。如果 \(i\) 获知了全部 \(t = (t_1,..,t_n)\) 的出价信息后， \(i\) 将修改其对商品的估计价值为（公式 2.7）：
    $$
    \begin{align}
    v_i(t) = t_i + \sum \limits_{j \in N, j \neq i}e_j(t_j)
    \end{align}
    $$

    • 相应的，Seller 获得N个竞价者对出价后重新调整其对自身的估价为（公式 2.8）：
      $$
      \begin{align}
      v_0(t) = t_0 + \sum \limits_{j \in N}e_j(t_j)
      \end{align}
      $$
    • 一般假设： \(e_j(t_j)\) 为0

小结：

• \(f(t_i)\) 即竞拍者 \(i\) 对商品的价值估计为 \(t_i\) 的概率分布函数
• \(v_i(t)\) 即竞拍者 \(i\) 考虑其他竞拍者对商品的价值估计后，修正的价格估计

Feasible Auction Mechanisms

（本节阐述可行性拍卖机制的基本条件）

• 以直接报价机制(direct revelation mechanisms) 为例展开

• 给定估计报价 \(t = (t_1,..,t_n)\)， 直接报价机制的支出函数outcome functions \((p,x)\)，其中 \(p_i(t)\) 即竞拍者 \(i\) 商品竞拍成功的概率， \(x_i(t)\) 即此时 \(i\) 给Seller 的期望付费金额

• 约定Seller 和所有竞拍者都是中性风险倾向的，对商品有各自的独立的收益函数(utility function)，竞拍者 \(i\) 的期望效用函数是 （公式 3.1）：

  $$
  \begin{align}
  U_i(p,x,t) = \int_{T_{-i}} \left( v_i(t)p_i(t)-x_i(t) \right) f_{-i}(t_{-i})dt_{-i}
  \end{align}
  $$

  • 其中 \(dt_{-i} = dt_1…dt_{i-1}dt_{t+1}dt_n\)
  • 其中 \(f_{-i}\) 即竞拍者 \(i\) 和 Seller 估计除去 \(i\) 之外的各竞拍者的出价的联合概率分布（独立，独立分布的乘积），之所以不包含自身的出价概率分布函数，是因为假定竞拍者已经按给定的出价 \(t_i\) 以给定的概率 \(p_i\) 获得商品为一确定性事件
  • 解释： 即竞拍者对商品本身估计的价值收益 \(v_i(t)p_i(t)\) - 竞拍者为这个商品付出的成本 \(x_i(t)\) 的累计积分

• 与之相对应，Seller 对这次竞拍的期望收益为 （公式 3.2）：
  $$
  \begin{align}
  U_0(p,x) = \int_{T}\left( v_0(t)\left(1-\sum_{j \in N}p_j(t)\right) + \sum_{j \in N}x_j(t)\right)f(t)dt
  \end{align}
  $$

  • 其中 \(dt_{i} = dt_1…dt_n\)
  • 解释：即庄家不出售商品时，自身对其的价值估计为 \(v_0\)，不出售的概率为 \(1-\sum_{j \in N}p_j(t)\)，则不出售收益部分 \(v_0(t)\left(1-\sum_{j \in N}p_j(t)\right) \) + 出售商品时从竞拍者处获得的支付收益 \(\sum_{j \in N}x_j(t)\) 的累计

• 我们的最优化问题目标就是最大化 \(U_0(p,x)\) (定义见：公式3.2），同时对 \((p, x)\) 有一些约束条件：

  • 公式3.3：（概率约束 probability constraints） 由于每次只有一个商品拍卖，所以有 ：
    $$
    \begin{align}
    \sum_{j \in N}p_j(t) \le 1 \quad \text{and} \quad p_i(t) \ge 0, \quad \forall i \in N, \forall t \in T
    \end{align}
    $$

  • 公式3.4：（个体理性约束 individual-rationality constraints）由于Seller不能强制竞拍者参加，所以需要保证每个竞拍者参与进来的收益非负才有动力参加，即 ：
    $$
    \begin{align}
    U_i(p,x,t_i) \ge 0, \quad \forall i \in N, \forall t_i \in [a_i, b_i]
    \end{align}
    $$

  • 假设竞拍者有隐瞒自己的估计从而期望获得额外收益，这时候应该保证诚实报价的状态是一种纳什均衡状态。假设竞拍者 \(i\) 声称 \(s_i\) 是他的声称估计而 \(t_i\) 是他的真实估价，那么他的期望效益函数为：
    $$
    \begin{align}
    \int_{T_{-i}} \left( v_i(t)p_i(t_{-i}, s_i)-x_i(t_{-i}, s_i) \right) f_{-i}(t_{-i})dt_{-i}
    \end{align}
    $$

  • 说明：竞拍者 \(i\) 获得物品的概率变成受两个因素的影响 \(p_i(t_{-i}, s_i)\)，为拍得商品支付的成本 \(x_i\) 也是 \(x_i(t_{-i}, s_i)\)

  • 公式3.5： （激励相容约束 incentive-compatibility constraints）从而，为保证每个竞拍者都没有动力隐瞒报价，需要满足如下的激励相容的条件（隐瞒后的期望收益更小）：
    $$
    \begin{align}
    U_i(p,x,t_i) \ge \int_{T_{-i}} \left( v_i(t)p_i(t_{-i}, s_i)-x_i(t_{-i}, s_i) \right) f_{-i}(t_{-i})dt_{-i}, \quad \forall i \in N, \forall t_i \in [a_i, b_i], \forall s_i \in [a_i, b_i]
    \end{align}
    $$

  • 论文称满足以上3个条件的拍卖机制是可行的feasible。that is, if the seller plans to allocate the Object according to p and to demand monetary payments from bidders according to x, then the scheme can be implemented, with all bidders willing to participate honesty.

• 在一个一般性的拍卖中，每个Bidder有一些候选策略 \(\Theta_i\)， 以及其对应的收益函数：
  $$
  \begin{align}
  \hat{p}: \Theta_1 \times … \times \Theta_n \rightarrow \mathbb{R}^n \quad \hat{x}: \Theta_1 \times … \times \Theta_n \rightarrow \mathbb{R}^n
  \end{align}
  $$

• 一个拍卖机制auction mechanism 涉及到各个竞拍者使用的一系列strategic plans 参与游戏中。a strategic plan即一个 \([a_i, b_i] \rightarrow \Theta_i\) 的规则函数， \(\Theta_i\) 即当竞拍者对商品的估价是 \(t_i\) 时采取的竞拍策略。Direct revelation mechanisms直接报价机制即 \(\Theta_i = t_i\) 。

• 定理1：给定任何的可行拍卖机制，总存在一个等价的可行的直接报价机制，可以给Seller和所有竞拍者带来与之相同的收益

小结：可行拍卖的3个条件：竞拍成功的概率非负、竞拍者的效用函数非负(挣的比花的多)、激励相容(鼓励说真话)

Analysis of the problem

*（本节展开拍卖机制的更多属性，确定具体的竞拍标准和计费标准） *

• 定义Bidder \(i\) 在 \((p,x)\) 的拍卖机制下，当 \(i\) 的估价是 \(t_i\) 时竞拍成功的条件概率为 （公式4.1）：
  $$
  \begin{align}
  Q_i(p,t_i) = \int_{T_{-i}}p_i(t)f_{-i}(t_{-i})dt_{-i}
  \end{align}
  $$
  • 如何理解？
• 此处省略许多推导…

Optimal auctions in the regular case

(本节给出正则问题下的最优拍卖机制)

• 对任意竞拍者 \(i\)，定义新的变量（其他地方也称为虚拟估值）：
  $$
  \begin{align}
  c_i(t_i) = t_i -e_i(t_i) - \frac{1-F_i(t_i)}{f_i(t_i)}
  \end{align}
  $$
  • 如果对所有竞拍者 \(i\)，均有 \(c_i(t_i)\) 是 \(t_i\) 的严格单调递增函数，则称原始问题为正则问题
  • 算法博弈论中也称满足 \(v - \frac{1-F(v)}{f(v)}\) 是关于 \(v\) 的非减函数的分布 \(F\) 为正则分布。在实际应用中，一般假设 \(e_j(t_j) = 0\) 。 \(e_j(t_j)\) 表示其他竞拍者 \(i\) 获知到竞拍者 \(j\) 对商品的价值估计 \(t_j\) 后修改自身出价的调整幅度（注意，这里假设了知道竞拍者 \(j\) 的出价信息后，任何一个非 \(j\) 竞拍者修正自己出价的幅度都是相同的 \(e_j(t_j)\) ），即竞拍者出价变为 \(t_i - e_j(t_j)\) 。一般假设 \(e_j(t_j) = 0\) 即对竞拍者知道其他竞拍者的估值后不影响自己的原始出价
  • 正则的分布包括：正太分布(normal distribution)，对数正太分布(lognormal distribution)，均匀分布(uniform distribution)，指数分布(exponential distribution)
    • 对数正态分布的介绍可参考对数正态分布（Log-Normal Distribution）
    • 指数分布的介绍可参考指数分布（定义、期望、方差）
  • 非正则的分布包括：多峰分布和长尾分布
• 正则问题的最优拍卖机制对应的分配规则为：
  $$
  \begin{align}
  p_i(t) > 0 \quad \text{implies} \quad c_i(t_i) = \max \limits_{j \ in N}\left(c_j(t_j) \right) \ge t_0
  \end{align}
  $$
  • 个人理解：上述公式包含下面几个逻辑：
    • 分配函数：将商品卖给 \(c_i(t_i)\) 最大的人，实际实现时可以采用按照 \(c_i(t_i)\) 排序的方式实现
      • 对应到广告中，则可以用 \( RankScore_i = c_i(bid_i^{cpc}) * CTR \) 排序
      • 考虑GMV时，也可以扩展为用 \(RankScore_{i} = c_i(bid_i^{cpc}) * CTR + k \cdot GMV\) 排序
    • 保留价：当所有人的虚拟估值都低于Seller 对商家的估值 \(t_0\) 时，流拍。在广告系统中，广告位不卖出去一般没有收益（忽略不出广告带来的用户体验提升），即估值为0，也就是 \(t_0=0\)，此时保留价一般定义为，对任意竞拍者 \(i\)，有 \(Bid_{reserve} = c_i^{-1}(t_0) = c_i^{-1}(0)\)
• 正则问题的最优拍卖机制对应的支付规则为：
  $$
  \begin{align}
  x_i(t) = p_i(t)v_i(t) - \int_{a_i}^{t_i}p_i(t_{-i}, s_i)ds_i
  \end{align}
  $$
  • 其中 \(v_i(t) = t_i + \sum \limits_{j \in N, j \neq i}e_j(t_j)\)
  • 个人理解：上述公式包含下面几个逻辑：
    • 直观解释支付规则：竞拍者 \(i\) 的支付价格为其对商品估值（修改后的估值）减去 其出价较低时累计概率和【如何理解减去累计概率和是表达声明，是不是写错了？】
  • 由于 \(v_i(t) = t_i + \sum \limits_{j \in N, j \neq i}e_j(t_j)\)，原始支付规则可进一步转化为：
    $$
    \begin{align}
    x_i(t) = p_i(t)\left( t_i + \sum \limits_{j \in N, j \neq i}e_j(t_j)\right) - \int_{a_i}^{t_i}p_i(t_{-i}, s_i)ds_i
    \end{align}
    $$
• 进一步定义如下新变量 \(z_i(t_{-i})\) ：
  $$
  \begin{align}
  z_i(t_{-i}) = \inf\{s_i|c_i(s_i) \ge t_0 \quad \text{and} \quad c_i(s_i) \ge c_j(t_j), \forall j \neq i\}.
  \end{align}
  $$
  • 个人对上述新变量 \(z_i(t_{-i})\) 的理解：
    • \(z_i(t_{-i})\) 是一个满足下列条件的 \(s_i\) 的最小值：
      • 满足 \(s_i\) 的虚拟估值 \(c_i(s_i)\) 大于Seller对商品估值 \(t_0\)
      • 满足 \(s_i\) 的虚拟估值 \(c_i(s_i)\) 大于等于其他所有竞拍者的真实估值对应虚拟估值 \(c_j(t_j)\)
    • 论文原文： \(z_i(t_{-i})\) is the infimum of all winning bids for i against \(t_{-i}\) . (\(z_i(t_{-i})\) 是 竞拍者 \(i\) 对 \(t_{-i}\) 的所有出价的下确界值)
    • \(z_i(t_{-i})\) 本质上是除竞价者 \(i\) 以外的 \(c_j(t_j)\) 最高的值 \(c_{j^*}(t_{j^*}) = \max \limits_{j \neq i} c_j(t_j)\) 对应的逆函数值 \(c_i^{-1}(c_{j^*}(t_{j^*}))\) 和 \(c_i(t_0)\) 的最大值
    • 也就是说，对于任意的竞价者 \(i\)， \(z_i(t_{-i})\) 是在其他商家出价为 \(t_{-i}\) 时， \(i\) 获胜的最低出价，也是其获胜后的计费价格
  • 当修正函数为0（即 \(e_i(t_i) = 0\) ），则可以得到：
    $$
    \begin{align}
    x_i(t) &= z_i(t_{-i}) \\
    &= \max \left \{c_i^{-1}(t_0), \max \limits_{j \neq i} c_i^{-1}(c_j(t_j))\right\} \\
    &= c_i^{-1}\left(\max\left\{t_0, \max \limits_{j \neq i} c_j(t_j)\right\}\right) \\
    \end{align}
    $$
    • 实际使用时，若 \(RankScore_{i} = c_i(bid_i^{cpc}) * CTR + k \cdot GMV\)，则是：
      $$
      \begin{align}
      x_i(t) &= z_i(t_{-i}) \\
      &= c_i^{-1}\left(\max \left\{t_0, \frac{RankScore_{next} - k \cdot GMV}{CTR}\right\}\right)
      \end{align}
      $$
  • 进一步地，如果问题是正则的，且是对称的（即所有竞拍者的估值分布是一样的）那么有：
    $$
    \begin{align}
    x_i(t) =z_i(t_{-i}) = \max \left \{c_i^{-1}(t_0), \max \limits_{j \neq i} t_j \right \}.
    \end{align}
    $$
    • 公式理解：
      • 当所有竞拍者的估值分布一致时（即 \(\forall i,j\)，有 \(F_i = F_j = F\) ），此时 \(c_i = c_j = c\) 成立， \(c_i^{-1}(c_j(t_j)) = c^{-1}(c(t_j)) = t_j\) 成立
      • 此时表示，如果问题是正则且对称的，那么带保留价的二价拍卖(\(Bid_{reserve} = c_i^{-1}(t_0)\))就是最优机制
• 分配规则也可表示为：
  $$
  \begin{align}
  p_i(t_{-i},s)=
  \begin{cases}
  0& 1 \ if \ s_i \gt z_i(t_{-i}), \\
  1& 0 \ if \ s_i \lt z_i(t_{-i}).
  \end{cases}
  \end{align}
  $$
  • 分配规则的理解：
    • 如果一个竞拍者 \(i\) 的出价大于除他以外的所有竞拍者的虚拟估值最大值的逆且大于Seller对商品估值的逆，则获胜
    • 更直观的理解：虚拟估值 \(c_i(s_i)\) 最高的竞拍者获胜，若最高虚拟估值低于Seller对商品估值（ \(t_0\) ），则流拍
• 计费规则也可表示为：
  $$
  \begin{align}
  x_i(t)=
  \begin{cases}
  0& z_i(t_{-i}) + \sum \limits_{j \in N, j \neq i}e_j(t_j) &\ if \ p_i(t)=1, \\
  1& 0 &\ if \ p_i(t)=0.
  \end{cases}
  \end{align}
  $$
  • 其中 \(\sum \limits_{j \in N, j \neq i}e_j(t_j)\) 通常为0，故更简洁的计费规则形式为：
    $$
    \begin{align}
    x_i(t)=
    \begin{cases}
    0& z_i(t_{-i}) &\ if \ p_i(t)=1, \\
    1& 0 &\ if \ p_i(t)=0.
    \end{cases}
    \end{align}
    $$

小结

• Myerson拍卖问题的建模为：
  $$
  \begin{align}
  \max U_0(p,x) &= \int_{T}\left( v_0(t)\left(1-\sum_{j \in N}p_j(t)\right) + \sum_{j \in N}x_j(t)\right)f(t)dt \\
  s.t. \sum_{j \in N}p_j(t) \le 1 \quad \text{and} \quad p_i(t) \ge 0 &, \quad \forall i \in N, \forall t \in T \\
  U_i(p,x,t_i) \ge 0 &, \quad \forall i \in N, \forall t_i \in [a_i, b_i] \\
  U_i(p,x,t_i) \ge \int_{T_{-i}} \left( v_i(t)p_i(t_{-i}, s_i)-x_i(t_{-i}, s_i) \right) f_{-i}(t_{-i})dt_{-i} &, \quad \forall i \in N, \forall t_i \in [a_i, b_i], \forall s_i \in [a_i, b_i]
  \end{align}
  $$

• 若以上问题为正则问题（即当对任意的竞拍者 \(i\)，对商品的估值分布 \(F_i\) 是正则函数）时，有最优拍卖机制 \((p,x)\) 为：

  • 原始形式：

    • 分配规则 \(p\) ：
      • 按照 \(RankScore_i = c_i(t_i) = t_i - \frac{1-F_i(t_i)}{f_i(t_i)}\) 对竞拍者进行排序，取 \(RankScore_i\) 最高的竞拍者 \(RankScore_i^*\)
      • 若 \(RankScore_i^*\ \ge t_0\) （等价于 \(t_{i*} \ge c_{i^*}^{-1}(t_0)\) ），则竞拍者 \(i^*\) 获胜，否则流拍
    • 支付规则 \(x\) ：
      $$
      \begin{align}
      x_i(t) &= z_i(t_{-i}) \\
      &=c_i^{-1}\left(\max\left\{t_0, \max \limits_{j \neq i} c_j(t_j)\right\}\right)
      \end{align}
      $$

  • 在真实广告系统中，往往需要考虑 \(GMV\) 等指标，此时一般可定义 \(RankScore_{i} = c_i(bid_i^{cpc}) * CTR + k \cdot GMV\)，则

    • 分配规则是：
      • 按照 \(RankScore_{i} = c_i(bid_i^{cpc}) * CTR + k \cdot GMV\) 对竞拍者进行排序
      • 取 \(RankScore_i\) 最高的竞拍者 \(i^*\)，其对应的排序分数为 \(RankScore_i^*\)
      • 若 \(\frac{RankScore_{i^*} - k \cdot GMV}{CTR} \ge t_0\) （等价于 \(bid_{i^*}^{cpc} \ge c_{i^*}^{-1}(t_0)\) ），则竞拍者 \(i^*\) 获胜，否则流拍
        • 注意：当竞拍者的出价分布不同时，其对应的保留价也不同，一般广告中实现时会考虑数据稀疏问题等，将同以区域(一般为蜂窝粒度)商家出价分布假定为独立同分布的，即同一区域内所有商家保留价相同
    • 支付规则是：
      $$
      \begin{align}
      x_i(t) &= z_i(t_{-i}) \\
      &= c_i^{-1}\left(\max \left\{t_0, \frac{RankScore_{next} - k \cdot GMV}{CTR}\right\}\right)
      \end{align}
      $$

Optimal auctions in the general case

(本节给出一般情况下的最优拍卖机制)

The independence assumption

Implementation

其他讨论

• 缺点：
  • 无法避免Bidders串谋调低价格
  • 可能出现Seller雇佣托儿太高价格（即保留价）【Seller没有动力吧】
  • 无法避免同一个Bidder用多个身份竞拍【Bidder没有动力吧】