深入探讨Espresso共享序列市场的设计

在本文中，我将呈现一些关于 Espresso 共享排序市场设计的思考和沉思^1，以及与该设计空间相关的一些挑战。你可以在 https://learnblockchain.cn/article/13364 阅读原始 Espresso 的设计文章。

注意：非常感谢 Terry @ EclipseLabs 分享关于 Espresso 的笔记。我的分析在很大程度上受到与他的讨论的启发。

Espresso 共享排序市场设计

Espresso 市场设计 是一种复杂的机制，旨在促进一个市场，在该市场中，rollups 可以向排序者（提案者）出售排序的时间段。该市场设计利用拍卖理论、组合优化和经济激励等概念，以实现高效、去中心化和稳定的 rollup 区块排序。以下是数学模型和相关关键组件的高层概述。

组合拍卖模型

• 概述：Espresso 市场设计的核心是组合拍卖，在该拍卖中，排序者为在特定时间段内对多个 rollups 的排序权利进行出价。该拍卖旨在允许排序者对 rollup 的组合进行出价，将它们视为互补品，这意味着一起排序多个 rollups 的价值大于单独排序它们的价值。

• 拍卖阶段：

  • 出价阶段：排序者对不同的 rollup 组合提交出价，所有出价都是公开的，并且需要预付款。这一设置确保了出价的可信性，并且排序者拥有支持其出价所需的资金。
  • 分配阶段：拍卖的结果通过选择最大化总出价值的组合集来决定。从数学上讲，这涉及找到一个将 rollups 划分为组合的方案，该方案最大化每个组合的最高出价的总和，同时满足每个 rollup 恰好包含在一个组合中的约束。
  • 排序阶段：每个组合的获胜排序者随后被授予在指定时间段内对相应 rollups 进行排序的权利。

• 数学表述：

  • 设 $n$ 为 rollups 的数量。
  • 每个 rollup $i$ 具有储备价 $r_i$。
  • 对于任何组合 $B \subseteq [n]$ 的 rollups，设 $b(B)$ 为该组合的最高出价。
  • 拍卖旨在找到一个分区 $\Pi = {B_1, \dots, B_k}$，以最大化总出价值：

$$\Pi^* = \arg\max{\Pi} \sum{B \in \Pi} v(B)$$

其中，$v(B)$ 对于一个组合 $B$ 的定义为：

$$v(B) = \max(b(B), r_i) \quad \text{如果 } B = {i} \text{ (单独组合)}$$

并且

$$v(B) = b(B) \quad \text{如果 } |B| \geq 2$$。

• 挑战：寻找最佳分区的问题是组合性的，在一般情况下可能计算效率低下。然而，在实际设置中，只有有限的组合可能在经济上是可行的，这可以简化问题。

减轻垄断的抽奖机制

• 拍卖问题：纯组合拍卖的一个潜在缺点是，单一投标者可能通过持续获胜来主导市场，导致垄断。
• 引入抽奖：为了解决这个问题，Espresso 引入了一种抽奖机制，在该机制中，排序者为每个组合购买抽奖票。然后，从抽奖票持有者中随机选择每个组合的获胜者，获胜的概率与所购票数成正比。
• 数学模型：
  • 设 $t_{\text{max}}$ 为某个组合售出的最大票数。
  • 每张票的价格 $p_B$ 根据前几轮的需求动态调整，类似于以太坊中的 EIP-1559 机制。如果需求高，下一轮的票价上调；如果需求低，票价下调。
  • 每个排序者在抽奖中的预期收入由其票数的比例份额给出：

$$\text{预期收入} = \frac{\text{购买的票数}}{\text{售出总票数}} \times \text{组合价值}$$

• 稳定性：抽奖机制有助于实现更广泛的排序权利分配，减少垄断风险，确保市场结构的去中心化。

收益分配

• 目标：确保 rollups 参与市场的收益好于独立排序。

• 收益分成：如果 rollup 包含在一个组合中，它至少会获得其独立组合的最高出价。共享排序带来的额外收益（即当 rollup 是组合的一部分时）按单独出价的价值比例分配。

• 数学模型：

  • 如果 rollup $i$ 是组合 $B$ 的一部分，则其支付为：

$$\text{支付给 Rollup } i = \max(b_i, ri) + \frac{b(B) - \sum{j \in B} bj}{\sum{j \in B} b_j} \times b_i$$

• 此处，$b_i$ 为仅包含 rollup $i$ 的单独组合的最高出价，$b(B)$ 为整个组合 $B$ 的最高出价。

激励相容性与效率

• 激励相容性：Espresso 市场并不声称完全激励相容，因为在复杂组合环境中，同时实现 DSIC（主导策略激励相容）和效率比较棘手。然而，该设计旨在通过利用重复互动和平滑的价格调整来尽可能接近效率。
• 效率：该设计试图确保排序权利分配给最重视这些权利的人，这通常与实现有效结果相一致。

防止垄断与抵制审查

• 抽奖设计与市场的重复性质结合，旨在防止任何单一排序者主导市场。即使是在高出价者中，排序权利的随机分配也引入了不可预测性和多样性，促进了去中心化及抵抗审查的能力。

最后看法与拍卖结算

与拍卖中的“最后看”相关的战略出价问题可能严重削弱拍卖过程的效率和公平性。顺序拍卖，或在最后确定前允许出价被揭示的拍卖，尤其容易受到这种操控。使用 密封投标拍卖 或实施 VCG 机制 是应对这些问题的有效方法。这两种方法鼓励诚实出价，防止策略性晚出价，并确保拍卖结果在社会上是高效的，最大化收入和福利。

让我们研究一个示例，理解“最后看”如何运作以及如何减轻其影响。

顺序拍卖中的战略出价

让我们考虑以下描述的场景。我们有三个待拍卖的项目（例如 rollup 区块）：$A$、$B$ 和 $A+B$（A 和 B 的组合）。这些项目的出价分别用 $b_A$、$bB$ 和 $b{A+B}$ 表示。

假设拍卖是顺序的，或允许在过程中揭示出价（如 Espresso 市场设计文档所描述）。这创造了一个环境，其中具有“最后看”的参与者可以根据从其他参与者的出价中获得的信息，战略性地调整他们的出价。这种出价形式高度战略性，可能导致多种低效：

情境设置：

• 投标者 1 为项目 $A$ 出价 $b_A = 10$。
• 投标者 2 为项目 $B$ 出价 $b_B = 8$。
• 投标者 3 为组合 $A+B$ 出价 $b_{A+B} = 25$。

战略性最后出价：

• 假设另一个投标者，投标者 4，可以在提交自己的出价之前观察这些出价。知道组合的出价 $b_{A+B} = 25$，投标者 4 可能会为项目 $B$ 提出新出价 $b'_B = 14.9$。
• 投标者 4 的目标是仅以高出投标者 2 的出价，但又不会超过使获得 $A+B$ 更好的价值。

结果：

• 对于投标者 4：通过出价 $b'_B = 14.9$，投标者 4 赢得 $B$ 而不超过组合 $A+B$ 的出价。对投标者 4 来说，捕获的盈余最大化，因为他们只支付了足够的出价，以超越投标者 2，但低于从 $A+B$ 中的边际上升。

• 对其他投标者：投标者 1 可能会在未来的拍卖中出价更低，因为他们知道可以策略性地被超越，而投标者 3 可能会调整他们的策略或干脆避免参与，从而减少总体拍卖收入和效率。

数学表述：

• 让我们定义 $B$ 的边际利益为 $\Delta B$，表示将 $B$ 添加到组合中时的价值增加。我们可以将其表达为：

$$\Delta B = b_{A+B} - b_A$$

在示例中，$\Delta B = 25 - 10 = 15$。如果投标者 4 策略性出价 $b'_B = 14.9$，他们实际上捕获了整个盈余 $ \Delta B - b_B$，通过仅超越 $b_B$ 而不达到组合阈值。

影响：

• 减少收入：拍卖者收取的收入减少，因为战略性出价降低了竞争，导致只接近第二高出价的出价。
• 低效：分配可能没有社会效率，因为参与者根据自己判断他人出价会出多少钱，调整策略，而不是根据他们的真实价值。

密封投标拍卖解决方案

为应对“最后看”引起的战略出价问题，一种有效的方法是实施 密封投标拍卖。在这种形式中，所有出价是同时提交的，参与者不知道其他人的出价。在所有出价提交后，它们被揭示，最高出价者获胜。

密封投标拍卖机制：

• 每个投标者在不知道其他人出价的情况下提交他们对所感兴趣项目的出价 $b_i$。
• 赢得拍卖的则是出价最高的投标者，但出价仅在提交后才被揭示。

数学表述：

• 假设有 $n$ 个投标者。项目 $A$ 的中标出价 $b^*$ 为：

$$bA^* = \arg \max{b_i} b_i$$

同样适用于 $B$ 和 $A+B$。

优势：

• 无战略调整：由于所有出价同时提交且不知晓其他投标者的出价，投标者无法在最后时刻战略性调整其出价。这往往导致更诚实的出价，反映出真实的估值。
• 收入增加：密封投标形式通常会导致拍卖者的收入更高，因为投标者倾向于接近他们的真实估值出价，知道他们不能通过策略性超越他人。

社会福利最大化：

• 密封投标拍卖更可能导致社会高效的结果，因为投标者被鼓励在没有担忧被他人超越的情况下揭示自己的真实估值。

VCG（Vickrey-Clarke-Groves）拍卖

VCG 拍卖机制是另一种解决顺序或最后一瞥拍卖中所识别问题的方法。

VCG 的机制：

• 在 VCG 拍卖中，每个投标者提交一个密封出价，最高出价者获胜。 然而，获胜的投标者支付的是他们给其他投标者带来的机会成本，而不是他们自己的出价。这一付款结构确保投标者有动机如实出价。

数学表述：

• 假设投标者 $i$ 以出价 $b_i$ 成为拍卖的受益者。他们支付的价格 $p_i$ 是其他投标者本来会赢得的最高出价之和，如果投标者 $i$ 没有参与：

$$pi = \sum{j \neq i} b_j^{\text{第二高}}$$

例如，如果投标者 1 以 $b_1 = 25$ 的价格赢得 $A+B$，但次高的组合出价为 $b_A = 10$ 和 $b_B = 14.9$，那么投标者 1 的支付为 $p_1 = 24.9$。

好处：

• 激励相容性：VCG 机制是 主导策略激励相容（DSIC） 的，这意味着无论其他人怎么做，出价如实报出是最佳策略。
• 社会效率：通过确保投标者支付机会成本，拍卖鼓励社会高效的结果，使得商品分配给最重视它们的人。

减轻战略操控：

• 对最后看的毫无优势：由于投标者被激励如实出价，即使他们能够查看其他出价，也不会受益于低出价或高出价，相对其真实价值。

组合选项的动态定价

在 Espresso 执行票（ET）模型的背景下，投标者可以为单个项目（例如 $A$ 或 $B$）或项目组合（例如 $A+B$）购买票。拍卖机制允许动态定价，其中每张票的价格可能会根据需求和其他因素而变化。这里的挑战有两个方面：

• 估值复杂性：投标者必须评估赢得单个项目与组合项目的价值。
• 随机选择：中奖出价的选择是随机的，为决策过程增加了一层概率不确定性。

数学表述

设：

• $p_A$、$pB$ 和 $p{A+B}$ 分别表示 $A$、$B$ 和组合 $A+B$ 的票价。
• $V_A$、$VB$ 和 $V{A+B}$ 分别是投标者赋予赢得 $A$、$B$ 和 $A+B$ 的估值。
• $\text{Pr}(A)$、$\text{Pr}(B)$ 和 $\text{Pr}(A+B)$ 表示在这些选项中投标者赢得 $A$、$B$ 和 $A+B$ 的概率。

投标者 $i$ 的预期效用可以表示为：

$$\mathbb{E}[U_A] = \text{Pr}(A) \cdot V_A - p_A$$

$$\mathbb{E}[U_B] = \text{Pr}(B) \cdot V_B - p_B$$

$$\mathbb{E}[U{A+B}] = \text{Pr}(A+B) \cdot V{A+B} - p_{A+B}$$

估值和效用计算

组合的估值：

组合 $A+B$ 的估值 $V_{A+B}$ 通常不是可加的。可能存在协同（或抑制）效应，其中：

$$V_{A+B} \neq V_A + V_B$$

这可能是由于互补性，$A$ 和 $B$ 一起提供的价值大于其各自部分之和。

预期效用：

鉴于选择的不确定性，投标 $A$、$B$ 或 $A+B$ 的预期效用依赖于估值和胜利的概率。这些概率 $\text{Pr}(A)$、$\text{Pr}(B)$ 和 $\text{Pr}(A+B)$ 由所购买的票的数量和竞争决定。

例如，如果投标者为 $A$ 购买了 $t_A$ 张票，则赢得 $A$ 的概率可以建模为：

$$\text{Pr}(A) = \frac{t_A}{T_A}$$

其中 $T_A$ 是为 $A$ 售出的总票数。对 $B$ 和 $A+B$ 同样适用。

预期效用函数可以重新写为：

$$\mathbb{E}[U_A] = \frac{t_A}{T_A} \cdot V_A - p_A$$

$$\mathbb{E}[U_B] = \frac{t_B}{T_B} \cdot V_B - p_B$$

$$\mathbb{E}[U{A+B}] = \frac{t{A+B}}{T{A+B}} \cdot V{A+B} - p_{A+B}$$

动态定价：

价格 $p_A$、$pB$ 和 $p{A+B}$ 是动态的，并可能根据需求变化。如果为 $A$ 购买的票数增加，票价 $p_A$ 可能会在下一轮上涨，以反映更高的需求。

从数学上讲，动态定价可以建模为：

$$p_A(t_A) = p_A(0) + \alpha \cdot (t_A - \bar{t}_A)$$

其中 $\alpha$ 是价格调整因子，$t_A$ 是所购票数，$\bar{t_A}$ 是目标票数。类似的方程适用于 $pB$ 和 $p{A+B}$。

这引入了一层额外的策略，投标者必须预测票价可能如何根据自己和其他投标者的出价行为变化。

Espresso 的定价机制可以建模为分段函数，根据与预定义目标 $t$ 相对的售出数量调整票价。该机制遵循两个阶段的方法：

常价阶段（售出 $0$ 到 $1.5t$ 张票）：

• 在第一个 $1.5t$ 张票阶段，票价保持不变。初始票价设为 $p_s$。
• 数学表达：

$$p(t) = p_s \quad \text{当 } 0 \leq t \leq 1.5t$$

线性价格增加阶段（售出 $1.5t$ 到 $2t$ 张票）：

• 在售出 $1.5t$ 张票后，票价线性增加，直到售出 $2t$ 张票。
• 在此阶段的价格函数可以表示为：

$$p(t) = p_s + \left( \frac{2p_s - p_s}{0.5t} \right) \cdot \left( t - 1.5t \right)$$

简化得到：

$$p(t) = p_s + \frac{p_s}{0.5t} \cdot (t - 1.5t)$$

这简化为：

$$p(t) = p_s \cdot \left(1 + 2(t - 1.5t) / 0.5t\right)$$

• 这一线性关系持续到 $t$ 达到 $2t$，价格上限为 $2p_s$。

因此，完整的价格调整函数为：

$$p(t) = \begin{cases} p_s & \text{如果 } 0 \leq t \leq 1.5t \ p_s \cdot \left(1 + 4\left(\frac{t - 1.5t}{0.5t}\right)\right) & \text{如果 } 1.5t < t \leq 2t \end{cases} $$

投标者的优化问题

投标者必须决定为每个选项（即 $A$、$B$ 或 $A+B$）购买多少票，以最大化其预期效用。这一决策受到以下因素的影响：

• 他们对项目或组合的估值。
• 当前票价。
• 预期竞争（即其他已售出票的数量）。

投标者的目标可以构建为优化问题：

$$\max_{t_A, tB, t{A+B}} { \mathbb{E}[U_A], \mathbb{E}[UB], \mathbb{E}[U{A+B}] }$$

受制于：

$$t_A, tB, t{A+B} \geq 0$$

$$t_A \cdot p_A + t_B \cdot pB + t{A+B} \cdot p_{A+B} \leq \text{预算}$$

其中“预算”是投标者愿意花费的总金额。

贝叶斯纳什均衡（BNE）：

在贝叶斯环境中，每个投标者会对其他投标者的策略形成信念。BNE 是在给予信念的情况下，每个投标者的策略是对其他人策略的最佳回应。

均衡策略将满足：

$$\sigmaA^{*} = \arg \max{\sigma_A} \mathbb{E}[U(\sigmaA | \sigma{-A})]$$

$$\sigmaB^{*} = \arg \max{\sigma_B} \mathbb{E}[U(\sigmaB | \sigma{-B})]$$

$$\sigma{A+B}^* = \arg \max{\sigma{A+B}} \mathbb{E}[U(\sigma{A+B} | \sigma_{-(A+B)})]$$

每个投标者估算其优化的票购买策略，同时考虑赢得拍卖的直接效用及其行为对未来几轮价格的影响。

进一步探索与研究

算法和 AI 投标代理：

考虑到手动解决优化问题的复杂性，开发 算法投标代理 或 AI 代理 来实时计算最佳投标策略是一个强有力的选择。这些代理将考虑动态定价、胜利的概率以及其他投标者的可能策略。

实验验证：

可以使用模拟来验证理论模型。通过使用算法投标者运行模拟拍卖，研究动态定价如何影响市场结果，以及均衡策略是否在实践中显现。

设计稳健的拍卖机制：

进一步的研究可以探讨可抵御动态定价和组合选项引入的复杂性的拍卖机制设计。这可能包括设计价格以更可预测的方式调整的机制，或者向投标者提供有关价格如何演变的更多信息。

我们将以一些严格的深度处理这些任务。这里的目标不仅是提出对 Espresso 设计现有动态定价模型的改进建议，同时为扩展此工作的数学框架和研究议程提供详细讨论。

Espresso 市场设计的扩展

Espresso 市场设计已经融合了一种分段定价机制，平衡了稳定性与根据需求动态调整的需要。然而，当前模型可以通过引入额外因素来扩展和改进，例如时间敏感的投标策略、价格调整的平滑机制，以及投标者之间的信息不对称考虑。以下，我们将研究这些扩展、数学模型，并阐明如何系统地分析和测试它们。

将时间纳入模型

概念解释：

当前的定价模型在某种意义上是静态的，因为它没有明确考虑拍卖过程的时间动态。通过引入时间因子 $t_{phase}$，我们可以建模投标者如何可能战略性地调整购买时间，以优化自己的效用，特别是在拍卖从常价阶段转向线性提价阶段时。

数学建模：

设 $t$ 表示自拍卖开始以来经过的时间。时间因子 $t_{phase}$ 是一个阈值，用于决定拍卖何时从常价阶段转向线性提价阶段。

• 阶段 1（常价阶段）：在转变之前，即 $t < t_{phase}$ 时，对应常价阶段。此期间价格为：

$$p(t) = ps \quad \text{当 } t < t{phase}$$

• 阶段 2（线性提价阶段）：在转变时间 $t_{phase}$ 之后，价格线性增加：

$$p(t) = ps \cdot \left(1 + 4\left(\frac{t - t{phase}}{0.5t}\right)\right) \quad \text{当 } t{phase} \leq t \leq t{max}$$

这里 $t_{max}$ 是对应售出所有 $2t$ 张票的最大时间。

投标者策略：

投标者现在可以在他们的策略中考虑出价的时机。预期效用函数变为时间相关的：

$$\mathbb{E}[U_A(t)] = \frac{t_A(t)}{T_A(t)} \cdot V_A(t) - p(t)$$

其中 $t_A(t)$ 表示在时间 $t$ 购买的票数，$T_A(t)$ 是此时可用的总票数。

未来研究工作：

时间敏感投标策略的优化：

• 开发并解决优化问题，最大化投标者通过战略性时间调整出价的预期效用，考虑预期阶段转变。
• 使用动态编程来确定最佳时机策略 $t^*$，最大化效用函数。

实证验证：

• 进行模拟拍卖环境实验，观察时间敏感投标策略如何影响拍卖结果，特别是在不同 $t_{phase}$ 分布下。

探索价格平滑机制

概念解释：

当前的分段线性定价机制在 $1.5t$ 点引入了急剧的价格转变。虽然这个设计目的明确，但在转变点可能导致投标者行为的急剧变化。为减少潜在的波动，我们可以探讨平滑机制，例如二次或指数的价格增加。

数学建模：

二次价格提升：

• 将阶段 2 中的线性函数替换为二次函数：

$$p(t) = p_s \cdot \left(1 + \beta \left(\frac{t - 1.5t}{0.5t}\right)^2\right) \quad \text{当 } 1.5t < t \leq 2t$$

• 这里，$\beta$ 是决定价格增加曲率的缩放因子。

指数价格提升：

• 或者，使用指数函数来平滑转变：

$$p(t) = p_s \cdot e^{\gamma (t - 1.5t)} \quad \text{当 } 1.5t < t \leq 2t$$

• $\gamma$ 是增长速率参数，控制价格增加的斜率。

投标者策略：

使用平滑机制，投标者的效用函数变得更复杂。对于二次情况：

$$\mathbb{E}[U_A(t)] = \frac{t_A(t)}{T_A(t)} \cdot V_A(t) - p_s \cdot \left(1 + \beta \left(\frac{t - 1.5t}{0.5t}\right)^2\right)$$

对于指数情况下：

$$\mathbb{E}[U_A(t)] = \frac{t_A(t)}{T_A(t)} \cdot V_A(t) - p_s \cdot e^{\gamma (t - 1.5t)}$$

未来研究工作：

比较分析：

• 进行分段线性、二次和指数模型的比较分析，以确定哪种平滑机制在投标者行为、市场效率和收入最大化方面产生最佳结果。
• 研究不同的 $\beta$ 和 $\gamma$ 值对投标者均衡策略的影响。

市场稳定性影响研究：

• 研究每种平滑机制对市场稳定性的影响。例如，二次增加是否导致平滑的价格变化，从而促使投标者行为更可预测？

模拟研究：

• 在模拟拍卖环境中实现这些模型，观察不同平滑功能如何影响投标模式、市场动态和总体拍卖效率。

不对称信息的高级均衡分析

概念解释：

在许多现实世界的拍卖中，并非所有的投标者都有相同的信息。有些人可能更好地估计价格转变何时发生，或更准确预测其他人的投标策略。这种信息的不对称可能显著影响投标行为和拍卖结果。

数学建模：

BNE 中的不对称信息：

• 假设有些投标者对 $t_{phase}$ 或其他投标者估值的分布有更准确的信息。我们将这些投标者称为知情投标者，而其他则为无知投标者。
• 设 $\theta_i$ 表示投标者 $i$ 的类型，其中 $\theta_i$ 表示他们的信息水平。具有更高 $\thetai$ 的投标者对 $t{phase}$ 有更好的估算或更多对其他人估值的了解。

在不对称信息下的均衡策略：

• 知情与无知投标者的预期效用函数可以以此形式写出：

$$\mathbb{E}[U_A(t | \theta_i)] = \frac{t_A(t | \theta_i)}{T_A(t)} \cdot V_A(t | \theta_i) - p(t | \theta_i)$$

• BNE 策略现在取决于类型 $\theta_i$，导致知情投标者与无知投标者的策略有所不同。

未来研究工作：

均衡分析：

• 分析在不对称信息下的 BNE。确定知情与无知投标者之间的均衡策略如何不同，以及这对拍卖结果的影响。

福利分析：

• 研究不对称信息对社会福利的影响。更知情的投标者是否会导致更高效的结果，还是为较少知情的参与者创造不利条件？

实证测试：

• 进行实证研究或实验，以验证理论预测。例如，分析信息不对称如何在实践中影响投标行为，以及拍卖机制能否调整以减轻负面影响。

参考文献

• 原文链接： github.com/thogiti/thogi...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～