<p>We study mechanisms that select a subset of a set of agents based on nominations among them. The goal is to maximize the minimum number of nominations received by any selected agent, subject to an impartiality constraint that the selection of a particular agent must be independent of the nominations cast by that agent. For situations where each agent casts at most <i>d</i>&#xa0;nominations, we give a mechanism that selects at most <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(d+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> agents and only selects agents who receive a maximum number of nominations or the maximum number of nominations minus one. We then show that this is best possible in the sense that no impartial mechanism can only select agents receiving a maximum number of nominations, even without any restrictions on the number of selected agents. We finally establish the following trade-off between the maximum number of agents selected and the minimum number of nominations for any selected agent when there are no constraints on the number of nominations each agent can cast: when selecting at most&#xa0;<i>k</i> agents out of <i>n</i>, it is possible to only select agents that receive at least the maximum number of nominations minus <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\big \lfloor \frac{n-2}{k-1} \big \rfloor +1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">⌊</mo> </mrow> <mfrac> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> <mrow> <mi>k</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> <mrow> <mo maxsize="1.2em" minsize="1.2em" stretchy="true">⌋</mo> </mrow> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimal impartial correspondences

  • Javier Cembrano,
  • Felix Fischer,
  • Max Klimm

摘要

We study mechanisms that select a subset of a set of agents based on nominations among them. The goal is to maximize the minimum number of nominations received by any selected agent, subject to an impartiality constraint that the selection of a particular agent must be independent of the nominations cast by that agent. For situations where each agent casts at most d nominations, we give a mechanism that selects at most \(d+1\) d + 1 agents and only selects agents who receive a maximum number of nominations or the maximum number of nominations minus one. We then show that this is best possible in the sense that no impartial mechanism can only select agents receiving a maximum number of nominations, even without any restrictions on the number of selected agents. We finally establish the following trade-off between the maximum number of agents selected and the minimum number of nominations for any selected agent when there are no constraints on the number of nominations each agent can cast: when selecting at most k agents out of n, it is possible to only select agents that receive at least the maximum number of nominations minus \(\big \lfloor \frac{n-2}{k-1} \big \rfloor +1\) n - 2 k - 1 + 1 .