Econ Papers Daily / 期刊论文
组合约束下的公正选择
Impartial selection under combinatorial constraints
摘要
Impartial selection problems are concerned with the selection of one or more agents from a set based on mutual nominations from within the set. To avoid strategic nominations of the agents, the axiom of impartiality requires that the selection of each agent is independent of the nominations cast by that agent. This paper initiates the study of impartial selection problems where the nominations are weighted and the set of agents that can be selected is restricted by a combinatorial constraint. We call a selection mechanism \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-optimal if, for every instance, the ratio between the total sum of weighted nominations of the selected set and that of the best feasible set of agents is at least \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha$$\end{document}. We show that a natural extension of a mechanism studied for the selection of a single agent remains impartial and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/4$$\end{document}-optimal for general independence systems, and we generalize upper bounds from the selection of multiple agents by parameterizing them by the girth of the independence system. We then focus on independence systems defined by knapsack and matroid constraints, giving impartial mechanisms that exploit a greedy order of the agents and achieve approximation ratios of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/3$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/2$$\end{document}, respectively, when agents cast a single nomination. For graphic matroids, we further devise an impartial and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/3$$\end{document}-optimal mechanism for an arbitrary number of unweighted nominations.
中文摘要
公正选择问题关注的是基于集合内部成员相互提名，从一个代理集合中选出一个或多个代理。为避免代理进行策略性提名，公正性公理要求每个代理的入选与该代理所投出的提名无关。本文开创了对提名具有权重、且可被选出的代理集合受到组合约束限制的公正选择问题的研究。若对于每一个实例，被选集合的加权提名总和与最佳可行代理集合的加权提名总和之比至少为\(\alpha\)，则称选择机制为\(\alpha\)-最优。我们证明，针对单个代理选择所研究的一种机制的自然扩展，对于一般独立性系统仍保持公正性，并且是\(1/4\)-最优的；我们还通过独立性系统的围长对多代理选择中的上界进行参数化，从而推广了这些上界。随后，我们聚焦于由背包约束和拟阵约束定义的独立性系统，给出了利用代理贪心顺序的公正机制，并且当代理投出单个提名时，分别达到\(1/3\)和\(1/2\)的近似比。对于图拟阵，我们进一步设计了一种公正且\(1/3\)-最优的机制，适用于任意数量的无权提名。