Optimal impartial correspondences

DOI10.1007/978-3-031-22832-2_11MaRDI QIDQ6167246zbMATH OpenOpenAlexFDO

Authors Javier Cembrano, Felix Fischer, Max Klimm

Publication date 4 August 2023

Published in Web and Internet Economics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.04544

zbMATH Keywords

votingmechanism designimpartial selection

Mathematics Subject Classification ID

Voting theory (91B12) Mechanism design theory (91B03)

Abstract: We study mechanisms that select a subset of the vertex set of a directed graph in order to maximize the minimum indegree of any selected vertex, subject to an impartiality constraint that the selection of a particular vertex is independent of the outgoing edges of that vertex. For graphs with maximum outdegree $d$, we give a mechanism that selects at most $d+1$ vertices and only selects vertices whose indegree is at least the maximum indegree in the graph minus one. We then show that this is best possible in the sense that no impartial mechanism can only select vertices with maximum degree, even without any restriction on the number of selected vertices. We finally obtain the following trade-off between the maximum number of vertices selected and the minimum indegree of any selected vertex: when selecting at most~$k$ vertices out of $n$, it is possible to only select vertices whose indegree is at least the maximum indegree minus $lfloor(n-2)/(k-1)floor+1$.

Recommendations

• Impartial selection with additive approximation guarantees
• Optimal impartial selection
• Impartial selection with additive approximation guarantees
• A near-optimal mechanism for impartial selection
• Impartial Selection and the Power of up to Two Choices

Cites work

• A near-optimal mechanism for impartial selection
• An axiomatic analysis of the papal conclave
• Characterizing minimal impartial rules for awarding prizes
• Impartial division of a dollar
• Impartial nomination correspondences
• Impartial nominations for a prize
• Impartial selection with additive approximation guarantees
• Incentive compatible mechanism for influential agent selection
• Optimal impartial selection
• Symmetry and impartial lotteries

Cited in

(1)

• Deterministic impartial selection with weights

This page was built for publication: Optimal impartial correspondences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167246)