给预测的高票人选加权重，能显著提升公平选人机制的准确性。
Impartial Selection with Predictions
- 基于对高票候选人的预测，设计新型公平选择机制。
- 预测准确时性能接近最优，错误时仍保持约58%效率。
- 特别适合需兼顾精准与鲁棒性的选举或委员会选拔场景。
我们研究基于相互提名的代理人选择问题，该问题在委员会选举和人工智能对齐等领域有广泛应用。由于代理人在被选择的同时也参与选择他人，可能通过虚假提名来影响自身入选概率。公平机制通过确保某代理人的入选与其自身提名无关来避免此问题。以往研究已建立公平机制性能的严格下界，以衡量其逼近最高提名数代理人的能力。本文研究若机制获得一组接收最多提名代理人的预测，其性能可提升多少。具体地，我们分析了机制的一致性（预测正确时的表现）与鲁棒性（预测错误时的表现）。在最多选出k个代理人的通用情形下，我们提出一种机制，一致性为1−O(1/k)，鲁棒性为1−1/e−O(1/k)。在每人仅提名一次、选出单个代理人的特例中，可实现1-一致性与1/2-鲁棒性。与先前结果对比表明，几乎最优的一致性可几乎不牺牲鲁棒性而达成。
原文摘要 · Abstract (English)
We study the selection of agents based on mutual nominations, a theoretical problem with many applications from committee selection to AI alignment. As agents both select and are selected, they may be incentivized to misrepresent their true opinion about the eligibility of others to influence their own chances of selection. Impartial mechanisms circumvent this issue by guaranteeing that the selection of an agent is independent of the nominations cast by that agent. Previous research has established strong bounds on the performance of impartial mechanisms, measured by their ability to approximate the number of nominations for the most highly nominated agents. We study to what extent the performance of impartial mechanisms can be improved if they are given a prediction of a set of agents receiving a maximum number of nominations. Specifically, we provide bounds on the consistency and robustness of such mechanisms, where consistency measures the performance of the mechanisms when the prediction is accurate and robustness its performance when the prediction is inaccurate. For the general setting where up to $k$ agents are to be selected and agents nominate any number of other agents, we give a mechanism with consistency $1-O\big(\frac{1}{k}\big)$ and robustness $1-\frac{1}{e}-O\big(\frac{1}{k}\big)$. For the special case of selecting a single agent based on a single nomination per agent, we prove that $1$-consistency can be achieved while guaranteeing $\frac{1}{2}$-robustness. A close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。