“密码学自我选择”是PoS区块链协议中常见的领导者选择原语。该概念最初在Algorand [CM19]中得到普及，他们还观察到该协议可能是可操纵的。[FHWY22]提供了一种具体的操纵方法，对于任何规模的权益证明者来说都是严格有利可图的（并且还证明了操纵获利的上限）。另外，[YSZ23，BM24]则独立开展了对共识协议中不可检测的有利操纵的研究，重点关注比特币PoW最长链协议的经典自私挖矿策略[ES14]。他们设计了一种自私挖矿变体，对于足够大的矿工来说是严格有利可图的，但对旁观者来说与例行延迟无异（也就是说，足够大的利润最大化矿工可以使用他们的策略来严格获利，而在其它网络用户看来，所有人都诚实，但是体验到了稍微更高的延迟。这避免了由于攻击检测而对基础加密货币的价值造成负面影响的风险）。我们研究了在[CM19]中引入并在[FHWY22]中研究的规范密码学自我选择领导者选择协议的有利操纵的可检测性，并确定对于任何持有总股份的$\alpha < \frac{3-\sqrt{5}}{2} \approx 0.38$的玩家，每个严格有利可图的操纵都是统计上可检测的。具体而言，我们考虑一个只看到每轮的随机种子（不需要看到任何其他玩家的广播）的旁观者。我们表明，当任何玩家正在有利可图地操纵协议时，随机种子序列的分布与任何由于诚实的权益证明者离线或超时（对于诚实超时的自然样式化模型）而可能产生的分布不一致。

公平分配是将一组物品公平地分配给代理的问题。其中最受欢迎的公平概念之一是无嫉妒（EF），要求没有代理人会嫉妒另一个人的分配。当物品是不可分割的时，EF概念就不再存在，而EFX成为其最强的放宽条件之一。EFX分配的存在可以说是公平分配中最大的未解问题。最近，Christodoulou，Fiat，Koutsoupias和Sgouritsa（EC 2023）展示了在图形估值的情况下EFX分配的存在，其中实例由图形表示：节点是代理，边是物品，每个代理只评估其相邻边缘。另一方面，他们证明了检查每个边缘分配给其相邻顶点的EFX方向的存在的NP难度，并要求对展示EFX方向的图形进行表征，而不考虑分配的估值。在本文中，我们在回答他们的问题方面取得了重大进展。我们引入了强EFX可定向图的概念——无论代理人如何估值边缘，都具有EFX定向的图。我们展示了这个属性与图$G$的色数$\chi(G)$之间的惊人联系。特别地，我们展示了$\chi(G)\leq 2$的图形是强EFX可定向的，而$\chi(G)>3$的图形则不是强EFX可定向的。我们提供了$\chi(G)=3$的强EFX可定向和非强EFX可定向图的示例以证明其紧密性。最后，我们对二进制估值进行限制，给出了强EFX可定向性的完整表征。

我们在亚加性估值的广泛类别下建立了公平与效率之间的兼容性，通过 Nash Social Welfare (NSW) 来捕捉。我们证明，对于亚加性估值，总是存在一个部分分配，它是无嫉妒的（EFx），并且在最优解的至少一半处具有 NSW；这里，最优性是在所有分配中考虑的，无论是否公平。我们还证明了，对于亚加性估值，总是存在完全分配，它是无嫉妒的（EF1），并且也实现了最优 NSW 的 $1/2$ 近似。我们的 EF1 结果解决了 Garg 等人提出的一个开放问题（STOC 2023）。此外，我们开发了一个多项式时间算法，它以任意分配 \~A 作为输入，返回一个 NSW 至少为 \~A 的 $1/3$ 的 EF1 分配。因此，我们的结果意味着，在亚加性估值中，EF1 标准可以同时在多项式时间内（使用需求查询）达到对最优 NSW 的常数因子近似。以前已知的在 $n$ 个代理人中在 EF1 和最优 NSW 下的最佳近似因子是 $O(n)$，我们将这个界限提高到 $O(1)$。 已知 EF1 和完全 Pareto 效率（PO）与亚加性估值不兼容。与这一负面结果相对应，当前的工作表明，我们只需要考虑 $1/2$ 近似因子，就可以恢复兼容性：在亚加性估值下，EF1 可以与 $\frac{1}{2}$-PO 结合实现。因此，我们的结果是一个通用工具，可以将任何有效结果转换为公平结果，只需稍微降低效率。

我们证明，在单参数机制设计环境中，唯一既不浪费、又对称、又激励兼容、又防止 Sybil 攻击的机制是对称的二价拍卖，并且需要使用对称的平局处理方式。因此，如果存在私人信息，抽奖或其他不总是分配给最高价值竞标者的机制，则不具备防止 Sybil 攻击或不具备激励兼容性。

在本文中，我们研究了婴儿命名这个高度竞争的领域。通过做出几个极其合理的假设（即父母是近视眼、完全知情的代理人，仅根据名字的独特性来选择名字），我们创建了一个模型，它不仅易于处理和简洁，而且完全捕捉了现实世界。然后，我们通过数值实验以及对大型语言模型工具的分析来扩展我们的研究。最后，我们讨论了未来研究的方向。

本文研究了多智能体强化学习（MARL）算法是否可以用于理解迭代组合拍卖，因为这些算法最近在其他几个领域已经表现出实证成功。迭代组合拍卖在高风险环境下广泛使用，例如频谱拍卖。这样的拍卖很难分析，使得投标人很难确定如何行事，设计者难以优化拍卖规则以确保高收入或福利等期望结果。研究发现，MARL确实可以有助于拍卖分析，但有效部署并不容易。本文首先描述了建模决策，使得生成的游戏具有可处理性，同时不会牺牲重要特征，例如不完美的信息或投标人之间的不对称性。我们还讨论了如何避免各种MARL算法的陷阱，如何克服验证收敛的挑战，以及如何生成和解释多个均衡。我们通过使用该方法来评估时钟拍卖的特定规则变更来说明其潜力，发现由于投标人行为的复杂变化而导致显著不同的拍卖结果。