通过问答找到各方都接受的随机选择方案，降低沟通成本。
Learning Unanimously Acceptable Lotteries via Queries
- 用二元反馈机制逐步试探可行的随机分配方案
- 可确定是否存在全员认可的方案，或证明不可能
- 适合需要多方共识的高风险决策场景
许多高风险的人工智能部署必须满足所有利益相关方的最低可接受标准。当从有限选项中进行随机选择时，问题转化为：是否存在一种方案组合（彩票），使所有利益相关方均认为其可接受？本文研究一种查询模型，算法提出彩票并仅获得“接受”或“拒绝”的二元反馈。我们提出了确定性和随机性算法，能够找到一个全员认可的彩票，或证明其不可行；自适应策略可避免询问所有利益相关方的约束，而随机化进一步降低了预期的查询成本。我们在最坏情况下给出了下界分析，表明对利益相关方数量呈线性依赖、对精度要求呈对数依赖是不可避免的。最后，我们设计了基于学习的增强算法，利用自然形式的先验信息（如可能起决定作用的利益相关方或有希望的彩票），在预测准确时显著降低查询复杂度，同时保持最坏情况下的保证。
原文摘要 · Abstract (English)
Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。