Impartial Selection with Predictions
Authors: Javier Cembrano
Felix Fischer
Max Klimm
Venue: NeurIPS 2025 poster ()
Keywords: impartial selection
mechanisms with predictions
Primary area: theory
TL;DR: We study impartial voting rules with predictions.

Abstract: 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 correct and robustness its performance when the prediction is incorrect. 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.

Impartial Selection with Predictions" *
Javier Cembrano
Felix Fischer
Department Algorithms and Complexity Max-Planck-Instiuu für Informatik Saarbrücken, Germany
School of Mathematical Sciences Queen Mary University of London
London, UK felix felix. fiw..ereeneeeeml...mm. ac. uk
Department of Industrial Engineering Universidad de Chile Santiago, Chile
j cembran@mpi-inf www.iini..p......mmmmmmmmm de
Max Klimm
Institute of Mathematics
Technische Universität Berlin
Berlin, Germany caimm@uu-belline de
Abstract
We study the selection of agents based on mutual nominations, a theoretical problem with many applications from committee selection to alignment. As agents both select and are selected, they may be incentivized to misrepresent their true opinion about the eligibility of others influence their own chances of selection. Impartial mechanisms circumvent this issue by guarantecing 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 impartial mechanisms can be improved they are given a prediction of a set of agents receiving 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 inaccurate. For the general setting where up k agents are to be selected and agents nominate any number of other agents, we give mechanism with consistency 1 -( and robustness 1- ( For the special case of selecting single agent based on a single nomination per agent, we prove that 1-consistency can be achieved while guaranteeing 1 rrobustness. close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.
Introduction
Majority voting is simple but very important mechanism for collective decision making. Its dates back at least to ancient Athens, where it was employed for example to decide on the expulsion of citizens from the city [18]. A much more recent proposal uses majority voting to aggregate the solutions of multiple calls to large language models (LLMs) [14]. Some proposals even go so far as
'The full version of the paper can be accessed on arXiv:2510.19002.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

using it in Al alignment, and destroying Al entities if they are perceived as unaligned with human
ethics by other AI entities [24]; see also Aaronson [1]. Irving et al. [20]. We may formalize this idea by considering a fixed number of different Al entities that can nominate other entities for being
incompatible with human values. The entity that receives the most nominations in that way would
then be destroyed.
The motivation for using majority decisions in these applications is their superior robustness to outliers compared to decisions made by a single entity. This argument requires, of course, that each entity is incentivized to reveal its true opinion about others rather than following its selfish interests. This is true for voting in general, but even more so in settings like those described above where the set of candidates and the set of voters overlap or are the same. Indeed, it is reasonable assume that an Athenian citizen in fear of expulsion would have cast their vote for someone they considered likely to receive a large number of nominations, rather than someone they considered worthy of expulsion, in order to minimize their own risk of being expelled. Similarly, it is naïve to assume that Al entities risking destruction due to misalignment will truthfully report on the misalignment of other entities if this negatively affects their own chances of survival. What is needed are voting mechanisms for which the probability that an entity is selected is independent of the nominations cast by that entity. Such mechanisms are called impartial in the literature.
While impartiality is obviously appealing, previous work has established strong impossibilitty results for mechanisms that satisfy it. Deterministic impartial mechanisms that select fixed number & of entities must fail natural axioms [12, 19]. and the overall number of nominations for the selected entities cannot provide a constant approx to the maximum number of nominations for any set of i entities [3]. Even randomized impartial mechanisms are relatively limited; for example, for the selection of single entity they can only approximate the maximum number of nominations to a factor of 1 [3, 17].
To improve the performance of impartial mechanisms, we will assume that the mechanism has access prediction of the entities most suitable for selection. Depending on the application, the prediction could for example come from another LLM not participating in the voting process or from expert advice. The prediction should not be thought of as a prediction about how the votes will turn out, but rather about who is most appropriate for selection. In particular, the prediction is independent of the votes and, thus, following the prediction is impartial. This assumption, while being crucial for our analysis, is satisfied in many scenarios. For concrete example, consider a situation where a group of agents cast votes on one another about who should be considered for a promotion. The group feeds all CVs to an LLM, asking it for its opinion on who is the best candidate and taking its output as prediction. In a second step, they can use one of the mechanisms in this paper to do a formal vote. This two-step process has the advantage that when the output of the LLM does not align at all with the opinions of the group, they can overrule its decision. In addition, the process is impartial in the sense that nobody can influence their own chance of being promoted. The guarantee of impartiality applics regardless of whether the agents know the prediction before casting their votes or not.
Our work is part of growing literature on algorithms and mechanisms with advice; website maintained by Lindermayr and Megow [22] provides an excellent overview of the area. The area is motivated by the fact that LLMs often provide astonishingly accurate answers, but also sometimes fail spectacularly. Mechanisms with advice therefore need to be able to cope with good as well as bad predictions, without clear way to distinguish between the two. This trade-off is studied formally by considering the consistency and robustness of mechanism. The consistency of a mechanism describes its ability to produce good outcomes when the predictions are accurate; the robustness its ability to produce reasonable results even when the predictions are inaccurate. The ability of a mechanism to move gracefully between these extremes is referred to as smoothness.
We will specifically consider deterministic and randomized impartial selection mechanisms with predictions. As it is standard in the literature on impartial selection, we formalize nominations among entities as a directed graph, where the set [n] = (1...., n) of vertices represent the entities and an edge from i to j indicates that casts a nomination for j. A deterministic k-selection mechanism with predictions is given such a graph and a prediction S C [n] with / = k. and returns set of at most A vertices. A randomized k-selection mechanism is lottery over deterministic mechanisms. Letting As denote the maximum sum of indegrees of any k vertices in the graph, a mechanism is called a-consistent for some a E [0, 1] if the (expected) sum of indegrees of the selected vertices is at least A when the prediction is accurate, i.c., when the total indegree of the vertices in Š
2

---

610
8
.05
106
28
46
uniform permutation
uniform permutation
rand. bidirect. permutation Exed bidirett. permutation baseline impossible
R-partition permutatioon
i-perinuaation
1-periutation
p-partition baseline impossible
baseline
baseline
impossible
impossible
==1
plurality,
Figure 1: Trade-off between o-connistencyy and B-robustness of impartial k-selection mechanisms. Orange dots the best mechanisms from previous work; orange areas are the whole ranges of possible consistency-robustess combinations implied by them. Green dots are the trivial mech- anisms always selecting the predicted set; green areas are new ranges of consistency-robustee combinations implied by lotteries of them with previous work. Blue dots and blue rounded rectangles new mechanisms introduced in this paper; blue areas new ranges of consistency-robusiie combinations implied by them or by lotteries of them with previous work. Gray areas are impossible monsistecy-rrbuustees: robustness combinations as shown Theorem 6.1. Whether the combinations in the white areas are achievable by impartial mechanisms is left for future research.
indeed equal Ag- While it is trivial to achieve 1 1-consistency in an impartial way, by simply returning the predicted set S, this would lead to arbitrarily bad performance when the predictions are inaccurate. measure the performance of mechanism in such cases, a mechanism called 8-robust for some 3 [0, 1] if the (expected) sum of indegrees of the selected vertices is at least AA, regardless of the quality of the prediction. will interested in the largest possible values of and 3 for which impartial a-consistent and 3-robust mechanisms can be found.
Our Results. We study impartial mechanisms with predictions in different settings; Figure I summarizes results and compares them with previous work. As initiate the study of impartial mechanisms with predictions, all previous mechanisms are unable to deal with predictions and consequently have equal robustness and consistency. Comparing mechanism defined as a lottery between the best known mechanisms from the literature and the trivial mechanism that always selects the predicted set shows significant improvements.
results with the baseline
We first study classic setting of randomized impartial 1-selection mechanisms for approval voting. We propose family of mechanisms we call p-permutation mechanisms that are parametrized by confidence parameter / E / 1]. The mechanisms build upon the so-called (uniform) permutation mechanism [7, 17], which does not any predictions and is rrobust. In nutshell, this mechanism permutes the vertices uniformly at random and carefully selects a vertex with maximum indegree from vertices that appear previously in the permutation. Our mechanisms favor permutations where the predicted vertex appears towards the end so that most of its incoming edges are likely observed, with bias that depends the confidence parameter. We show that for any p E 1 the resulting mechanism p-consistent and (1 p) -rbbust (Proposition 3.1), and that this trade-off between consistency and robustness is best cost-possible (Theorem 6.1). While this optimal trade-off can also be achieved by the baseline mechanism that randomizes between the uniform permutation mechanism and the mechanism that selects the predicted vertex, such mechanism would fail basic fairness notions, as discussed in Section 3.
dewiiitency-robustne
We then study 1-selection mechanisms for plurality voting, where each vertex has exactly outgoing edge. this setting, we establish that the 1- I-permutation mechanism that puts the predicted vertex at the end of the permutation is I-consistent and } roobsst (Theorem 3.3). Prior work had established that the uniform permutation mechanism is 3 rrobust, which also implies 3 --oosssttnncy [11]. By an appropriate lottery between both mechanisms, we achieve (3 3/))) -consistency and Pp) robustness for all E [0, 1] (Corollary 3.4). We further show in Theorem 6.1 that for any a-consistent and B-robust impartial mechanism, 5 and + 3 3.
We next consider 2-selection mechanisms. this setting, the bidirectional permutation mechanism [7] was shown to achieve the optimal robustness guarantee of 1. We show that, by placing the predicted
3

---

vertices at both ends of the permutation, we obtain the best best-possible consisteney guarantee of 1 without any sacrifice of robustness (Theorem 4.1). For randomized mechanisms, an appropriate lottery between this mechanism and the randomized permutation mechanism [7] achieves (3 + 3p)- consistency and [2 EP) -robustesss for all p E [0, 1]: see Proposition 4.2. We further show in Theorem 6.1 that, for any a-consistent and ß-robust impartial mechanism, , S ] and a + =
We finally study randomized k-selection mechanisms for an arbitrary number l E NN and obtain Theorem 5.2, our most challenging result in terms of technical difficulty. Bjelde et al. [7] proposed the k-partition mechanism with permutation, which partitions the vertices randomly into sets and selects one vertex from each set in a similar way to the permutation mechanism. but also accounting
for edges from outside the set. We propose the p-partition mechanism for p E [3. 1]. that partitions the vertices randomly into k sets but enforces that each set contains exactly one of the predicted vertices. In each set, the predicted vertex is put at position P while all other vertices obtain a position drawn uniformly from the unit interval. We then select one vertex from each set, as the k-partition mechanism with permutation. The mechanism achieves higher consistency by avoiding that more than one of the predicted vertices ends up in the same set, but the analysis requires new techniques because the probabilities of two optimal vertices being in the same set are no longer independent.
In the realm of mechanisms with predictions, it is common to also study approximation guarantees as a function of the prediction error, commonly referred to as smoothness. In our context, a natural notion of error of a predicted set of vertices is the difference between the maximum indegree of a set of & vertices and the indegree of the predicted set, normalized by the maximum indegree so it lies in the interval [0, 1]. Since all our a-consistent and 3-robust mechanisms provide an a-approximation of the indegree of the predicted set, independently of whether this set is or not optimal, they immediately yield smoothness guarantee of max {a(1 - -n), }}} for an error 1) E [0.
Related Work. Impartiality, as we study it here, was first considered by de Clippel et al. [15] for the
division of divisible resource among members of a set of agents based on divisions proposed by the agents. the context of selection, it was first studied by Holzman and Moulin [19] and Alon et al. [3]. Holzman and Moulin studied deterministic mechanisms for the special case of plurality voting, where each member casts exactly one nomination for another member of the set. They showed that, even in this restricted setting, impartiality is incompatible with the axioms of negative and positive unanimity, where the former requires that a member receiving no nomination is never selected and the latter that member nominated by all members except themselves is always selected. Alon et al. studied the more general setting of approval voting, where members may nominate an arbitrary number of other members and a fixed number ie of members is to be selected. Call a mechanism mechanism if it always selects exactly k members, and a-optimal for a E [0, 1] if the (expected) number of nominations that the selected members receive is always least an a-fraction of the total number of nominations that the k best members receive. In this terminology, Alon et al. showed that no deterministic, impartial, and exact k-selection mechanism can be a-optimal for any fixed a >> O. They further provided a randomized impartial - 1-selection mechanism. and randomized impartial (1 (L)))ootimml k-selection mechanism for k + co. Fischer and Klimm [17] proposed and analyzed the permutation mechanism and showed that it is --optiall, which is best-possible for 1-selection. They further showed that for plurality votes, the same mechanism is a-optimal for a 108
exact k-selection
67 ~ 0.620. Cembrano et al. [11] gave tight analysis of the permutation mechanism for
plurafity votes, showing that is even 3 -optimal. They further proposed a new mechanism that is 2105
2
3147 -ottimal,,, where 3147 R 0.669. Bjelde et al. [7] showed that deterministic impartial k-selection mechanisms that are allowed to sometimes select fewer than à members can perform better than exact k-selection mechanisms, and bounded the approximation guarantees of randomized mechanisms that select A > members. Caragiannis et al. [9] studied the additive approximation guarantees of impartial selection mechanisms, and Cembrano et al. [12] gave deterministic mechanism with an improved additive guarantee for plurality votes. Caragiannis et al. [10] considered the additive approximation guarantees of impartial mechanisms that receive prior information as additional input. They looked at two different models where members choose their nominations based on a known probability distribution or based on the popularity of member. We note that this approach differs from ours, since it does not bound the approximation guarantees if the prior information is inaccurate.
2105
The cobustness-consistenng consistency framework was first used by Purohit et al. [25] to study the performance of online algorithms with predictions. Predictions have been recently incorporated by Berger et al. [6] into the voting setting of metric distortion, where candidate is to be selected based on rankings

---

cast by voters with costs given by distances on a common metric space, and the goal is to minimize the ratio between the social cost of the selected candidate and that of the optimal one. More broadly, mechanisms with predictions were first studied by Agrawal et al. [2] for facility location, which has been further considered by Balkanski et al. [5] for randomized mechanisms and different types of predictions, by Fang et al. [16] for a restricted set of candidate locations, and by Istrate and Bonchis [21] for the case where agents' objective is to maximize rather than minimize their distance to the facilities. Balkanski et al. [4] incorporated predictions into the design of strategyproof mechanisms for makespan minimization in scheduling. Xu and Lu [26] also studied a range of mechanism design problems with and without money, including facility location, scheduling, and auction design.
2 Preliminaries
For n E N, let [n] = {I, ,,] and let
Go
: ([n) [n])
((.D))
vE[n]
denote the set of simple graphs with vertex set [m]] and without self-loops. For S, T E 2|ml, we denote the edges from vertices in S to vertices in T by
(T, = (.. E: - ())
and the number of such edges by (T. We omit S from the previous notation when S = [n]. and we write N (i, G) instead of N ((i(,, G) and 8 Gi instead of 8- (fi), G). For k: [n]. we write (G) = max (T, G). We omit l when it is equal to and G whenever it is clear from the context. We refer the graphs G ([n), F.) Gn, such that H(i,)) FE [n]]]
for every E [ni], in which all vertices have outdegree exactly one, as plurality graphs.
We consider selection mechanisms that obtain a prediction for the set of vertices with maximum indegrees. A k-selection mechanism with predictions is a family of functions f: ((x) x G, + + [0, 1|m with Eje( fi G) < l: for all G E Gn. where f.(S, G) denotes the probability assigned by the mechanism agent i.2 For a graph G E 9n and i E [m). the number fi(S, G) is the probability that f selects vertex i when (S, G) is the input. A mechanism is called deterministic if it only assigns probabilities and 1, and is called impartial if fi(S, G) ft(S, G') whenever for two graphs G = [[n], E¹) and G' = ([m), E") we have E' \ Uje(n) ((i,,))))))) = E' X (G.
For a E [0, 1), we call a k-selection mechanism with predictions a-consistent if it achieves an a-approximation when the predictions are accurate, i.c., Eigin] f((S G (i, G?) 2 (G) for all n E N. G E Gn. and Š E (()) with 8 (S, G) = As (G). For 3 E [0, we call a k-selection mechanism with predictions 3-robust if it achieves 3 B-approximation regardless of the predictions' quality, i.e., Eie f((S, G) (i, G) 2 BG+(G) for all n E N, G' E Gn, and S E (7)).
We finally require some notation regarding permutations. For a (vertex) set S. we let IIs C S1SI denote the set of permutations of the set S: we refer to the order induced by a permutation as order from left to right for ease of notation. We write II, as a shorthand for [[ For permutation x E IIs, t} for the set
set S' C S. and vertex i S. we write J<i = {j E S j Tr, i πy for some of vertices that appear to the left of i, π (5") E II for the restriction of π to S', and म E II for the fix the position of some vertices in the permutation. For set of distinct vertices {úg : j E [m]} and distinct positions (ry j E [m]], we write (f1 -> Fi..... bm + Fm) for the set of permutations E IIs such that in nr, for every [m].
reverse of æ. Sometimes
3 Selecting a Single Vertex
In this section, we study 1-selection mechanisms with predictions. For ease of notation, we denote the predicted set by $ = {i) and write A(G) instead of (G) for the maximum indegree.
is well known that deterministic mechanisms cannot achieve any constant approximation in the classic setting without predictions, which for our setting has the direct implication that no deterministic
'It is not hard to see that such distribution over vertices can be translated into probability over sets of size most via the Birkhoff- von Neumann Theorem; see Bjelde et al. [7, Lemma 2.1] for the details.
5

---

Algorithm/ Permutation mechanism Pm(G, S,x)
Algorithm p-permutation mechanism (1, G)
Input: graph G ([n], E). set [n], [0, 1/s.
Input: graph G = ([n], E), predicted vertex E [n]. Output: vertex P E [n].
Output: vertex pP E [m].
T(x) (=) IIs
Ty +
initialize 7m + иı and d + (T))((m)))
sample 0, [] uniformly at random Vi [m] (+)
return Pm(G, G, 2)
for E (2..... [S]] do
i +
if 6 (IN))8))(
(1) 2 d then
update Pm t i and d + (jure
return Pm
mechanism with predictions can be B-robust for a constant 3 > O. Thus, the trivial answer to the best-possible trade-off between consistency and robustness is given by the mechanism that selects the predicted vertex and achieves 1-consistency and O-robustnesss.
The problem becomes more interesting with randomization, as the best-known mechanism for the setting without predictions achieves a -appproximation. approximation, introduced by Fischer and Klimm [17], as the uniform permulation mechunism. This mechanism sorts the vertices uniformly at random and considers them one by one according to this order while maintaining candidate vertex, initially the first vertex. A vertex is taken as the new candidate if its observed indegree is larger than that of the current candidate, where observed indegree refers to the indegree when only considering incoming edges from previous vertices and omitting potential edge from the current candidate. The vertex that is the candidate in the end is selected.
refer to the mechanism achieving this
We define a more general version of this mechanism, where in addition to the graph G = ([n), E). the mechanism receives a subset of vertices S C [n] and a vector æ E [0, 1js. Vertices in S are those taken into account for the permutation, while all other vertices in [T)] \ S are not eligible for selection and the incoming edges from these vertices are always considered. The vector x E [0. 1] defines the permutation every i, E S we have i E Fzソ if and only if either I; < Iy or both x2 Iy and < j hold (we break ties in favor of vertices with smaller indices). We denote the permutation
1l.: i comes before j if its associated value 2, is smaller than z. Formally, for
11s constructed
in this way from x E [0, 1|$ by x(x).
The permutation mechanism for a fixed set S and vector x E [0, 1] is formally described in Algorithm 1; we refer to its output for graph G, set S, and vector x by Pm(G, S, The uni- form permutation mechanism, providing the best-possible guarantee among randomized 1-selection mechanisms without prediction, corresponds to the mechanism that receives a graph G and returns Pm(G, [mx] 2), where x; E [0, 1] is taken uniformly at random for each E [n].
Instead of the uniform permutation mechanism. we consider in the setting with predictions the o-permutation mechanism, given in Algorithm 2. This mechanism receives graph G== ([n], E) and a predicted vertex E [n]. and returns Pm(G, [n], where now has an associated value r; p and all values 2; for E [m] \ {i] are sampled uniformly at random. The value p then has the natural interpretation of confidence parameter: Taking
ensures seeing all incoming edges of the predicted vertex, while smaller values of increase the probability of seeing potential outgoing edges i. This mechanism attains any convex combination of a-consistency and (3-robustness between the points (a, 8) E { (1, ( 2) In Section 6, we will see that this trade-off is actually best- posssilee
Proposition 3.1. For any confidence parameter E [ 1] the p-permutation mechanism is impartial, p-consistent and (1 - pobrobt
We need some notation. For a fixed graph G = ([n), E) Gn. set S C [n]. and vector [0. 1|s, we let ;Pm (G, S, z) denote the outcome of Pm(G, Whenever x is fixed, we write π for the induced permutation instead of (x). As key property for the analysis of the (uniform) permutation mechanism, Bousquet et al. [8] showed that, for any fixed permutation, it selects a vertex with maximum indegree from the left. Bjelde al. [7] extended this result the case where restrict to a set of vertices and consider all incoming edges from other vertices. We phrase the latter result with our notation as the following lemma, which apply in the full version to prove Proposition 3.1.

---

Lemma 3.2 (Bjelde et al. [7]). For every G = (In), E) E Gn. S S [m], and x E [0, 118, it holds that (G, S,, E arg max (1)),)) (i, G) [n]]
It is worth noting that the consistency and robustness guarantees of Proposition 3.1 are also achieved by a baseline mechanism that returns the predicted vertex with probability p and runs the uniform permutation mechanism with probability 1 p. However, the baseline mechanism fails a basic unanimity notion introduced by Holzman and Moulin [19]: If a vertex
such that all other vertices have a single outgoing edge to v, then v should be selected. Whenever u is not the predicted vertex, the baseline mechanism fails to select e with constant probability, while the p-permutation mechanism returns v as long as it is not first or second in the permutation, i.e., with probability 1 - (
Plurality Voting. usual restriction in voting that each member nominates one other member, which in our graph representation implies having vertices with outdegree one. This paradigm of plu- rality voting, extensively considered the impartial selection literature [11, 19, 23], has been shown to enable better approximation guarantees for randomized mechanisms." 3 In particular, Cembrano et al. [11] proved that the uniform permutation mechanism provides an improved approximation ratio
of E in this case.
In our setting, we show that the p-permutation mechanism with p where the predicted vertex is deterministically placed at the end of the permutation and all other vertices are sorted uniformly random, achieves 1 1-consistency and 2/2 t-robustess. The following theorem provides a more fine- grained bound on the robustness of this mechanism as a function of the maximum indegree A of the input graph: the bound of & follows by taking the worst case over A.
Theorem 3.3. The 1 1-permutattin mechanism is impartial, 1-consistent, and ((A)-robust plurality graphs with maximum indegree A N 2, where
3A-2
if A is even,
B(A)
44
32
24-1
if A is odd.
4A2
Moreover, this function 3 is increasing, implying that this mechanism is impartial, 1-consistent, and rrobust on plurality graphs.
We prove this theorem in the full version using a strengthened version of lemma of Cembrano al. [11] that establishes negative correlation between the indegree from the left of the maximum- indegree vertex and that of all other vertices. We show that this result remains true for the non-uniform distribution over permutations induced by the vector x defined in the 1- 1-permutation mechanism, and that it holds not only for the maximun-indegree vertex but for any fixed vertex. The proof adapts that of Cembrano et al. [11], defining an injective funetion between sets of permutations to couple the probabilities that certain indegrees are observed in the permutation taken in the mechanism. We then use the lemma to prove Theorem 3.3. The most challenging case, which ultimately leads to worse robustness guarantee than in the setting without predictions, is when the maximum-indeeree vertex has an incoming edge from the predicted vertex, as this edge is never considered by the mechanism when observing the indegrees from the left. However, since all outdegrees are 1, we can still obtain a lower bound on the probability of selecting this maximum-indegree vertex or another vertex with high indegree.
We now state the implications of Theorem 3.3, in terms of the trade-off between consistency and robustness we can achieve by combining the 1-permutation mechanism with the uniform permutation mechanism. The proof of this result can be found in the full version. In Section 6, we will see that this trade-off is not far from tight.
Corollary 3.4. For every p E [0, 1]. there exists a randomized 1-selection mechanism with predictions that is impartial, a-consistent, and B-robust on plurality graphs with maximum indegree A, where
a(1)=
I(++1)
3A+2
A+2 A(+1J
P
if A is even,
3(2)
3A+2
4A(A+I)
A+2
if A is even,
a(A-1)
if A is odd,
42
4
P
if A is odd.
1). there exists a randomized 1-selection mechanism with predictions that impartial, (3 + 3P) -cnnsiseen, and (3 ()) -robust on plurality graphs.
In particular, for every P E [0,
'The impossibility of providing a constant approximation of the maximum indegree with deterministic mechanisms remains true in this restricted setting [19].
7

---

Algorithm 3 Fixed bidirectional permutation mechanism, Pmo (S, G)
Input: graph G = ([n], E), predicted set $ = {i1, 82) S [n]-
Output: set 5 - [n] with | =
Fix F1, + 0 and 212- +
fix 2, E (0, 1) arbitrarily for each i e [n] S
Tj < - 24 for every i E [n]
return Pm(G, [n], U Pm(G, ()).
4 Selecting Two Vertices
In this brief section, we state our results for the selection of two vertices. In terms of mechanisms without predictions, the best-known deterministic and randomized impartial mechanisms achieve 2- and 2 -ooptimllity. respectively. While the bound for deterministic mechanisms is best-possible only an upper bound of is known for randomized mechanisms [7]. For compactness, throughout this section we denote the predicted set by S {i1, f2).
3
The deterministic mechanism achieving 1 -oppimallity is based on the permutation mechanism. runs, for an arbitrarily fixed permutation π, the permutation mechanism for both π and its reverse म, and returns the selected vertices for each direction (potentiallyy the same vertex). A natural approach to incorporate the prediction is to run this mechanism with the predicted vertices at both extremes of the fixed permutation. The resulting mechanism, which we call fixed bidirectional permutation. maintains the best-possible robustness of 2 while achieving 1-consistency. The formal description of the mechanism is given in Algorithm 3; the proof of this result is deferred the full version.
Theorem 4.1. The fixed bidirectional permutation mechanism is impartial, 1-consistent, and 1 robust.
In terms randomized mechanisms, convex combinations of the best-known mechanism without prediction, achieving 3-robusttees [7], and the fixed bidirectional permutation mechanism, achieving 1-consistency and 2 -robustness, allows us to attain combinations a-consistency and 3-robustnesss between (a, [) = (3 2 and (a, 3)- = (1, ) We state this simple fact in the following proposition; we will see in Section that this combination of consistency and robustness is not far from tight.
Proposition 4.2. For every P E j0, 1). there exists randomized 2-selection mechanism with predic- tions that is impartial, (3 + {0) connsistet, and (3 -robust..
5 Selecting k 2 3 Vertices
In this section, we study the impartial selection of A 2 3 vertices when the mechanism is equipped with prediction on the optimal set.
In terms of deterministic mechanisms, the setting without predictions is far from well understood. Indeed, large gap remains between the best-known lower and upper bounds of and k-1 on the approximation guarantee that impartial mechanisms can achieve improved the lower bound for cases where l is larger than (approximately) 2/nn, but the lower bound of & remains the best-known bound for an arbitrary number of agents n. This guarantee comes from the bidirectional permutation mechanism explained in the previous section, whose daapproximation of the optimal set of two agents translates into I --approximation of the optimal committee of k agents. Similarly to the previous section, we can modify this mechanism maintain its robustness guarantee and achieve I-consistency. Specifically, we select k 2 vertices from the predicted set and one or two more vertices through fixed bidirectional permutation mechanism, with the remaining two predicted vertices at the extremes of the permutation. We state the properties of this simple mechanism in the following proposition, proven in the full version.
[7]. Recently, Cembrano et al. [13]
Proposition 5.1. There exists deterministic k-selection mechanism with predictions that is impartial, 1-consistent, and j rrbusst
Regarding randomized mechanisms, the best-known mechanism for k-selection was developed by Bjelde et al. [7] and provides an approximation guarantee of E+II - ( k-1 k+1 which starts at
((x)
8

---

Algorithm 4 p-partition mechanism Pt C)
0, 8
Input: graph G ([n] F),
P
predicted $ (i....., Re] E (2)).
P 3/4
Output: set 5 < (fr)
P = 1/2
sample ji E [ki] uniformly E [m] 1
P 1/2
assign i to Aj, Vi E [m]
3/4
for j E [k] do
1 2
A₂ f Ay [1:], Ti, t
sample 24 E [0,1] uniformly vi A 1o)
1 PmpG,mGGG 2)
sPi S 0
k
return S St
2 3
5
6
7
8
9
10
The p-partition mechanism (left) and a plot of its a-consisteney (solid) and 8-robustness (dashed) for the values p 1, p 3. and م = 2/2 function of k (right). The dotted black line is the consistency and robustness of the k-partition mechanism of Bjelde et al. [7].
Figure 2:
T2 x 0.5833 for 2, mechanism assigns each vertex to one out of k sets uniformly at random. It then selects one vertex from each set via the permutation mechanism restricted to that set with an internal permutation taken uniformly at random. While its impartiality is easy to see, the approximation guarantee requires careful analysis of the expected observed indegree of optimal vertices in each set. the following, we develop a randomized mechanism with predictions inspired by this mechanism that achieves almost optimal robustness while losing very little in terms of consistency, especially as k grows.
65 0.6019 for kt and approaches 1 0.6321 k grows. The Tos
As in the mechanism by Bjelde et al., vertices are assigned to one of k sets, and one vertex is selected from each set by running the permutation mechanism restricted the set. However, both the assignment to sets and the permutation are not taken independently and uniformly for each vertex anymore. Instead, we assign one predicted vertex to each set; other vertices are still assigned to set chosen independently and uniformly at random. Within each set, the permutation is sampled as the p-permutation mechanism from Section
For each set A, with a predicted vertex i,. we take vector x E [0, 1] such that Fi, = p and 2; E [0, 1] is taken uniformly at random for each E A, {. Intuitively, these changes allow the mechanism to see most incoming edges the predicted vertices while only mildly affecting the distributions to keep strong robustness guarantee.
The
mechanism, which we refer as the p-partition mechanism, formally presented in Algorithm 4. For E [0, 1]. we denote its output by (S, G) for each graph G = ([r), E") and predicted set S. By tuning the confidence parameter p between & and 1, we achieve consistency between while only losing O (1.) in robustness compared to the best-known mechanism without prediction.
2Æ and 1
Theorem 5.2. For any confidence parameter E [1 1], the p-partition mechanism is impartial, a-consistent, and 3-robust, where a
1-2 and (1 x (1-))
(-=1) (k=1)²
2, 2 to prioritize robustness, our mechanism achieves a robustness 35 0.5469 for k: 4, and approaching I 1- R 0.6321 for k + xc. The consistency guarantee for this value of p and any k 2 2 is 1 which k - xo. When taking p to maximize consistency, the mechanism is 1-consistent for any k and achieves a robustness guarantee 1 = 0.25 for & = 2, 19
For example, when taking guarantee of for
36 0.5278 for k
61
0.875 for = 4, and approaches TE.
0.75 for & 2, 8 as 0.8333 for & 3,
54 x 0.3519 for k = 3, 256 z 0.0.4102 for k 4, and again approaching - ~ 0.6321 for k + of the p-partition mechanism for p E { 1 3. 1,1 and E (2...., 10). and compares with the k-partition mechanism of Bjelde et al. [7].
105
Figure 2 illustrates the performance
The proof of Theorem 5.2 can be found in the full version; here we briefly describe the main ideas behind the robustness guarantee, which constitutes the most difficult part of the proof. For the analysis we consider an optimal set S* and j E [k] such that A, contains an optimal vertex, i.e., S n A, A and sample vertex i" from S* n Aj uniformly random. We then bound the expected indegree of i" that the mechanism observes by bounding the probability that each in-neighbor i of 1" lies set other than A, or in the set Ay but before i" according to the internal permutation. What complicates

---

the analysis is that, unlike in the mechanism without predictions, the events i" A, and i E A, are independent. However, it is not difficult see that when & S U S, the probability of being in Aj is the same in the independent case. We show further that when i E S* or i" E S, the probability of being A, cannot increase much, and the only difference given by the position of the predicted vertex in the internal permutation. The most intricate part of the proof is the case where i" E S \ S and E 3 S", because the events z" being sampled the set A, and being in this set can be strongly correlated. Indeed, the probability of the former event conditional on i E Ag can be as large as if, for example, all predicted vertices except belong to S as in this case i E A implies that i* is the unique vertex in 5 n Aj. We tackle this difficulty by directly computing lower bound on the (unconditional) probability of i" being sampled as the optimal vertex in Ay.
Upper Bounds
To put our consistency and robustness results into perspective, we will now give upper bounds on the values a and / for which an impartial selection mechanism with predictions can simultaneously guarantee a-consistency and 8-robustness. We do so for k-selection with [1,2,3], 3). and for 1-selection from plurality graphs. The upper bounds are shown in Figure alongside the lower bounds obtained earlier sections.
Theorem 6.1. The following statements hold:
(i) If a randomized 1-selection mechanism with predictions is impartial, a-consistent, and B-robust, then B S and a + 3 S 1.
(ii) If a randomized 1-selection mechanism with predictions is impartial, a-consisient, and 3 3-robust on plurality graphs, then 3 S 3 and a + 3 2'
(iii) If a randomized 2-selection mechanism with predictions is impartial, a-consistent, and 3 robust, then B S 3. and a + 5.
(iv) If a randomized 3-selection mechanism with predictions is impartial, a-consistent, and 3 3-robust, then B < 5. 4a 333 < and 4a + 21,3 < 20.
We prove these results in the full version. To this end, we consider appropriate families of graphs and for each vertex in these graphs introduce variable for the probability with which some impartial, a-consistent, and 3-robust k-selection mechanism selects that vertex. We generalize a lemma of Holzman and Moulin [19] to show that one can restrict attention to symmetric mechanisms, and use impartiality, consistency, robustness, and the fact that the probabilities for each graph must sum up to k obtain set of linear inequalities involving the probability variables, a, and B8. We then show that any values of a and (3 not satisfying the statements violate the linear inequalities.
7 Discussion
We have initiated the study of impartial selection mechanisms with predictions. Unlike majority voting, these mechanisms progress regarding the approximation guarantees achievable by such mechanisms, in most settings a moderate gap remains between the upper and lower bounds. We leave closing these gaps for future work. In addition, it would be interesting to test the mechanisms we have proposed in practical applications, for example in the aggregation of outputs of different LLMss
prone to strategic manipulation. While we have made substantial
Acknowledgements
Research was supported by the Deutsche Forschungsgemeinscaaff under project number 431465000 by the Engineering and Physical Sciences Research Council under grant EP/TO15187/1, and by Structural Democracy Fellowship through the Brooks School of Public Policy at Cornell University.
10

---

References
[1] S. Aaronson. My Al safety lecture for UT effective altruism, 2022. available under https: //scottaaronson blog/?m=202211; last accessed May 16, 2025.
[2] Agrawal, F. Balkanski, Gkatzelis, T. Ou, and X. Tan. laaming-augmented mechanism design: Leveraging predictions for facility location. Mathematics of Operations Research, 49 (4):2626-2651, 2024.
[3] N. Alon, F. Fischer, A. Procaccia, and M. Tennenholtz. Sum of us: Strategyproof selection from the selectors. Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pages 101-110, 2011.
[4] E. Balkanski, V. Gkatzelis, and X. Tan. Strategyproof scheduling with predictions. In Pro- ceedings of the 14th Conference on Innovations in Theoretical Computer Science. Schloss Dagsubl-Leibnizzzzntuu für Informatik, 2023.
[5] E. Balkanski, V. Gkatzelis, and G. Shahkarami. Randomized strategic facility location with predictions. In A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomczak, and C. Zhang, editors, Proceedings of the 38th Annual Conference on Neural Information Processing Systems, 2024.
[6] B. Berger, Feldman, V. Gkatzelis, and X. Tan. Learning-an augmmntg metric distortion via (p. g)-vet core. In Proceedings of the 25th ACM Conference on Economics and Computation, pages 984-984, 2024.
[7] A. Bjelde, F. Fischer, and M. Klimm. Impartial selection and the power of up to two choices. ACM Transactions on Economics and Computation, 5(4):1-20, 2017.
[8] N. Bousquet, S. Norin, and A. Vetta. A near-optimal mechanism for impartial selection. In Proceedings of the 10th International Conference on Web and Internet Economics, pages 133-146. Springer, 2014.
[9] I. Caragiannis, G. Christodoulou, and N. Protopapas. Impartial selection with additive approxi- mation guarantees. In Proceedings of the 12th International Symposium on Algorithmic Game Theory, pages 269-283. Springer, 2019.
[10] I. Caragiannis, G. Christodoulou, and N. Protopapas. Impartial selection with prior information. In Y. Ding, J. Tang. J. F. Sequeda, L. Aroyo, C. Castillo, and G. Houben, editors, Proceedings of the ACM Web Conference 2023, pages 3614-3624 2023.
[11] J. Cembrano, F. Fischer, and M. Klimm. Improved bounds for single-nomination impartial selection. In Proceedings of the 24th ACM Conference on Economics and Computation, page 449, 2023.
[12] J. Cembrano, F. Fischer, D. Hannon, and M. Klimm. Impartial selection with additive guarantees via iterated delction. Games and Economic Behavior, 144:203-224, 2024.
[13] J. Cembrano, S. M. Griesbach, and M. J. Stahlberg. Deterministic impartial selection with weights. ACM Transactions on Economics and Computation, 12:3:200:110:22, 2024.
[14] L. Chen, J. Q. Davis, B. Hanin, P. Bailis, I. Stoica, M. A. Zaharia, and J. Y. Zou. Are more LLM calls all you need? towards the scaling properties of compound AT systems. In A. Globersons, L. Mackey, D. Belgrave, A. Fan, U. Paquet. J. M. Tomezak, and C. Zhang, editors, Proceedings of the 38th Annual Conference on Neural Information Processing Systems, 2024.
[15] G. de Clippel, H. Moulin, and N. Tideman. Impartial division of a dollar. Journal of Economic Theory, 139(1):176
2008.
[16] Fang, Q. Fang, Liu, and Q. Nong. Mechanism design with predictions for facility location games with candidate locations. In X. Chen and B. Li, editors, Proceedings of the 18th Annual Conference on Theory and Applications of Models of Computation, volume 1 14637 of Lecture Notes in Computer Science, pages 38-49, 2024.

---

[17] F. Fischer and M. Klimm. Optimal impartial selection. SIAM Journal on Computing, 44(5): 1263-1285, 2015.
[18] G. Heinberg. History of the majority principle. The American Political Science Review, 20 (1):52-68, 1926.
[19] R. Holzman and H. Moulin, Impartial nominations for prize. Econometrica, 81(1):173-196 2013.
[20] G. Irving, P. Christiano, and D. Amodei. Al safety via debate. arXiv Preprint; available under https://arxiv. org/abs/1800/ 00899, 2018.
[21] G. Istrate and C. Bonchis. Mechanism design with predictions for obnoxious facility location. arXiv preprint, available under
09521, 2022.
[22] A. Lindermayr and N. Megow. Algorithms with predictions, 2025. Available under https:
/ //aloorithsswwith with www.--iieeedeciionn.... github. io; last accessed February 10, 2025.
[23] A. Mackenzie. Symmetry and impartial lotteries. Games and Economic Behavior, 94:15-28,
2015.
[24] Moebius314. Available under https://wes www.wwong........... multiple- ais- naa-boxes-evallaeee each- other- s alignmennt: May 15, 2025.
Multiple Als in boxes, evaluating each other's alignment, 2022.
last accessed
[25] M. Purohit, 7. Svitkina, and R. Kumar. Improving online algorithms via ML prediciii..ns. In Bengio, H. M. Wallach, Larochelle, Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Proceedings of the 31th Annual Conference on Neural Information Processing Systems, pages 9684-9693, 2018
[26] C. Xu and P. Lu. Mechanism design with predictions. I. D. Raedt, editor, Proceedings of the 31st International Joint Conference Artificial Intelligence, pages 571-577, 2022.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarize the theoretical results and explain their significance relative to existing work and applications.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses problems left open and limits to applicability.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Theoretical results are correct as stated. Complete proofs are given in the appendix and sketched in the body of the paper.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
ponycccyl)) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.coo. wwtpcccccpppppppa..e.eeeccccccee httpa//gggieeeeeeuuuubuiiiiiii /Cooeeeodeieeeeeeeeeeeeeee wwwaeiisssiooooiioii (eiinnilccy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http::://neuret httppppps..ppppppeeeeeeeeeeeeeee
Answer: [Yes]
Justification: The use of predictions in collaborative decision making has the potential to introduce bias and lead to discrimination. Results the paper are theoretical and general, whereas the question of ethical use of predictions in voting practical one and decisions must be made for each particular application. The thcoretical results can, however, inform practical decisions regarding the tradeoff between benefits from using predictions and potential harm through bias and discrimination.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The mechanisms proposed in the paper have the potential to achieve better collaborative decisions through the use of predictions. This discussed in the introduction. The use of predictions in collaborative decision-making has the potential to introduce bias and lead to discrimination. This is discussed in the answer to the previous questions.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not involve data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ /ttps/////eu.p./eeeeee www.arip..c//oooeeeeeeeeeeeeeeee 20LL/LLM for what should or should be described.
19


Reviews:
[{"review_id": "EI1WaP9U8w", "reviewer": "Reviewer_S2nN", "summary": "This paper studies the impartial mechanism with prediction in majority voting. The input is given as a graph with vertices referring to the entities and an arc from $j$ to $i$ indicating that $j$ nominates $i$. The $k$ entities with the most vote are selected. The prediction $\\hat{S}$ is a set of $k$ entities, also given as an input. \n\nThe performance bounds are measured by consistency and robustness. The consistency is prefermance of the proposed mechanism when the prediction is accurate, while the robustness is that when the prediction is wrong. The authors focus on impartial mechanisms and present the following main results. Below, I use $(\\alpha,\\beta)$ to represent $\\alpha$-consistent and $\\beta$-robust.\n\n1. when $k=1$, for any $\\rho \\in [1/2,1]$, a randomized mechanism achieves $(\\rho,1-\\rho)$;\n2. when $k=2$, a deterministic mechanism achieves $(1,1/2)$, and a randomized mechanism achieves $(\\frac{2}{3}+\\frac{1}{3}\\rho, \\frac{2}{3}- \\frac{1}{6}\\rho)$ for all $\\rho\\in [0,1]$;\n3. when $k\\geq 3$, a deterministic mechanism achieves $(1,\\frac{1}{k})$, and a randomized mechanism that $\\alpha \\geq 1-\\frac{1}{2k}$, which lossing $O(\\frac{1}{n})$ of $\\beta$ when compared to the best-known mechanism without prediction.\n\nThe authors also present upper bounds of $(\\alpha, \\beta)$. Result 1 achieves the best possible, and moreover, the gaps between upper and lower bounds of other settings are not large.", "questions": "Q1 : For plurality voting, you only discussed the randomized mechanisms without prediction and designed randomized mechanisms with predictions. Is this because the impossibility result for deterministic mechanisms mentioned earlier (line 199) also extends to the plurality voting setting?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The research question is interesting. Mechanism design with prediction has recently become an active research direction, particularly for those problems with strong impossibility results. The core idea is to use predictions to improve the algorithm's performance when the predictions are accurate (consistency), while maintaining (or nearly maintaining) the best-known bounds when the predictions are incorrect (robustness). This paper introduces the framework prediction to the impartial mechanisms in majority voting.\n\nThe results are non-trivial. The maniscript considers several settings, depending on $k$ and the graph structure, and for each of them, it presents upper and lower bounds. Although the presented bounds are not tight, the gap between them is relatively small, which I find acceptable.\n\nThe paper is well-written in general. The reserach question is well motivated and the results are nicely summarized in Figure 1.\n\nFor the techniques, most of the presented algorithms are established on the existing ones (without prediction). The presented algrithms share the similar ideas of the existing ones or use them as subrotines, though with adaptations to handle the prediction setting. Although these adaptations are not trivial, they are not particularly difficult to devise.\n\nOther minor comments:\n\nline 261, Theorem 3.3. From the proof, it seems that \\delta \\geq 2 is required, which is not mentioned in the statement. For the current statement, if \\delta=1, then \\beta(1)=0. You may want to rephrase the statement.\n\nline 256, show -> have shown\n\nline 198, using $\\Delta(G)$ for $\\Delta_1(G)$ has been mentioned in line 174", "was_revised": true, "final_justification": "This paper has no serious concerns and can be accepted.", "rebuttal": "Thank you for your detailed comments and the questions you have raised.\nWe will happily fix any minor issues.\nIn particular, the assumption $\\Delta\\geq 2$ in Theorem 3.3 is indeed relevant: If $\\Delta=1$, all vertices have indegree $1$ and any mechanism is trivially $1$-robust.\n\nRegarding the question about deterministic mechanisms for plurality voting, the fact that no mechanism can achieve constant robustness indeed holds in this setting as well, due to an impossibility result of Holzman and Moulin (Econometrica, 2013).\nThis is why we restrict ourselves to randomized mechanisms in the whole section.\nWe appreciate the comment, as we think it is indeed valuable to point this out more clearly when introducing plurality voting."}, {"review_id": "JpoJ5buV6x", "reviewer": "Reviewer_jF4z", "summary": "The authors study impartial $k$-selection with predictions, where agents nominate each other and the selection mechanism has access to a predicted set of \"best\" agents. A selection mechanism is impartial if the selection of an agent is independent of that agent's votes. They say a mechanism is $\\alpha$-consistent it it selects a committee with at least an $\\alpha$-fraction of the maximal total votes when the prediction matches the maximum vote committee and $\\beta$-robust if it always selects a $\\beta$-approximate committee regardless of the prediction. The authors extend existing mechanisms for different values of $k$ (uniform permutation, bidirectional permutation, and $k$-partition with permutation) to the setting with predictions, achieving higher consistency-robustness tradeoffs. Through constructions, they also show their tradeoffs are not too far from optimal.", "questions": "1. I was a little bit thrown off by the terminology of a prediction being \"correct\" or \"incorrect\" based on whether it agrees with the set of nodes in $G$ with maximal indegree. Since this can be checked by the mechanism, it seems to imply that the prediction is useless; as the mechanism always knows what the \"correct\" prediction would have been. But my understanding is that the existence of a prediction affects the incentives of the voters, allowing different mechanisms to be impartial by using the prediction. Is this understanding correct? If so, I would suggest adding a sentence clarifying the terminology \"correct\" and \"incorrect\" and explaining why having a prediction is useful even if its \"correctness\" is immediately clear.", "limitations": "The authors acknowledge optimality gaps in their results, which are clearly presented. I see no potential negative societal impact of this work.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This is a really nicely executed paper, well-grounded in the literature and building on existing results in a novel direction.\n2. The quality and clarity are excellent.\n\nWeaknesses:\n1. If I had to fish for a weakness, I'd say the audience for this work at NeurIPS may be a little narrow (it's perhaps marginally closer to AAAI/EC/IJCAI), although it's certainly in scope and the discussed applications in AI safety are nice.\n\nQuality: very high. I didn't check the appendix, but the descriptions of the mechanisms make a lot of sense.\n\nClarity: Figure 1 is *excellent*. Introduction and related work are remarkably clear and thorough. Technical sections are very clear.\n\nSignificance: Provides improved bounds for impartial selection in a new setting. The application to multi-agent AI systems is intriguing. \n\nOriginality: Adds a new prediction input to the impartial selection setting, which is natural and provides new results. \n\nMinor:\nLine 171 definition of $N_S^-$ says it's the cardinality of the set.", "was_revised": true, "final_justification": "I had no serious concerns and continue to think this is a strong paper.", "rebuttal": "Thank you for your evaluation, comments, and suggestions. Thanks in particular for pointing out the typo in the definition of $N^-_S$.\n\nYour understanding regarding predictions is correct. In the mechanism design literature (to which we contribute), predictions are powerful since they convey information about the state of the system without being subject to strategic misreporting by the agents.\nIn that sense, the use of the words \"correct\" and \"incorrect\" (though standard in the literature on algorithms with predictions) is indeed a bit misleading since the latter refers to a case where the behavior of the agents does not align with the prediction of the ML algorithm, but this does not mean that the agents or the ML algorithm were making a mistake.\nTo avoid confusion, we will instead use the slightly weaker terms \"accurate\" and \"inaccurate\" (as the paper by Xu and Lu we cite)."}, {"review_id": "pYSc1bxjTt", "reviewer": "Reviewer_mVCz", "summary": "Consider as input a directed graph with n vertices. The goal is to randomly select k vertices that approximately maximize the sum of in-degrees. The sum of in-degrees corresponds to the utilitarian welfare that the k vertices (agents) provide to the population of n vertices (agents), where an edge from agent i to j means agent i approves of j being selected. Additionally, as part of the input, we are given k proposed vertices S, which are predicted to form a good committee. Now we want to randomize in such a way that:\n (1) if the prediction is good, then the returned outcome is (almost) as good as the prediction (2) is the prediction is bad, then the outcome should not be (much) worse than if we had not seen the prediction and (3) an agent's probability of being selected should be independent of her votes/ her out degree - in other words the mechanism should be impartial.\n\n\nIn this setting, the authors prove the following results:\nk=1: \nA baseline algorithm for this problem is randomizing between the prediction and the best known algorithm without prediction and achieves \\rho-consistency and (1-\\rho) robustness. The authors show that this is tight. However, this algorithm has the property that if every node points to the same node v, then still the algorithm would only select v with constant probability, if v is not the predicted vertex. Thus the authors propose an alternative mechanism that selects such a node v w.p. 1-O(1/n) and otherwise has the same consistency and robustness guarantees as the baseline. They call the new mechanism \\rho-permutation mechanism.\n\nk=2:\nThe authors extend the existing deterministic mechanism to the fixed bidirectional permutation mechanism, which is impartial, 1-consistent and 1/2-robust.\n\nk>=:3 The authors introduce a new mechanism called \\rho-partition, parametrized by \\rho that is impartial and is alpha consistent and beta-robust for \\alpha and \\beta which for large k tend to 1 and 1-1/e respectively. This algorithm is inspired by the best known k-selection algorithm.\n\nThe authors also prove results on how large the alpha and beta can be for an impartial randomized mechanism for k=1,2,3.", "questions": "How can a mechanism with predictions that come from black box methods like LLMs that run weird heuristics internally be impartial? Can you model your predictions so that your formal model makes sense and yet is still well-motivated in practice?\n\nCan you explain how your results can help in AI alignment in more detail, also with reference to the less wrong post you link?", "limitations": "The major limitation is that prediction framework and and impartial mechanism don't naturally fit together.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The paper is very well written and structured. Incorporating prediction in algorithms in light of the arrival of LLMs, which may do better by following strange black-box heuristics, has been a recent hot topic.\nThe AI-Safety motivation in the introduction is very interesting, albeit the detailed mapping to the problem would need to be elaborated upon.\nMoreover, the paper has technically quite non-trivial results and makes good progress in this direction, with the main result being for k ≥ 3.\nOne weakness is that the baseline algorithm for k = 1 already achieves the desirable optimal trade-off between robustness and consistency.\nIn general, I think this is a good paper, if not for one conceptual concern regarding the motivation:\n\nEspecially in optimization problems, I believe using the prediction framework, given that we are in the age of ML-heuristics, makes a lot of sense. However, I feel that once we add impartiality, the framework no longer makes sense, at least not in the way it is usually motivated. Suppose an AI agent, like an LLM, predicts an outcome k, which will be the input to your algorithm. Since this AI is good at prediction, presumably even without access to the agent’s preferences it will be good at predicting them and might use them to construct its prediction. It is a black-box machine; we simply don’t know. So, for all we know, the prediction algorithm itself might not be impartial (to the extent that the AI is also good at predicting preferences and potentially uses them) thus making the entire mechanism partial. I feel that this is a major flaw in your formal model.", "was_revised": true, "final_justification": "This is a good paper and the authors clarified one thing I found confusing.", "rebuttal": "Thanks for asking for clarification regarding the impartiality of the prediction. This is an important issue, and we will revise the paper to discuss it in more detail.\nWe think that there are many situations where the prediction is clearly impartial since it simply does not have access to the votes of the agents.\nAs an example, consider a scenario where a group of agents cast votes on one another about who should be considered for a promotion.\nThey can feed the CVs of everybody to an LLM, asking it for its opinion on who is most eligible and taking its output as a prediction. (For the following arguments, it is immaterial whether the agents know the prediction of the LLM or not.)\nIn a second step, they can use one of the mechanisms in this paper to do a formal vote.\nThis two-step process has the advantage that when the output of the LLM does not align at all with the opinions of the group, they can overrule its decision.\nIn addition, the process is impartial in the sense that nobody can influence their own chance of being promoted.\n\nRegarding the use of impartial mechanisms in AI alignment, the Less Wrong post discusses the idea of two AI entities evaluating whether the other one is aligned with human values or not, with the ultimate consequence that an AI entity that is not aligned will be destroyed.\nWhen slightly rephrasing this thought experiment as one with $n$ AIs that are tasked with evaluating the alignment of the other entities, this is an impartial selection problem where no AI wants to be selected for destruction.\nUsing an impartial selection mechanism ensures that the opinion an AI entity voices regarding the alignment of other entities does not influence whether this AI entity is selected for destruction. We think that this is a useful property to incentivize omnipotent AIs to reveal their true evaluation of the other AIs. \nWhile this scenario does not involve predictions, and we were using it to argue that impartial selection in general is useful for AI alignment, one may alter the process and for example incorporate human expert advice as an external prediction on the rogueness of AIs."}, {"review_id": "OPASHKRRY3", "reviewer": "Reviewer_mkRF", "summary": "Impartial Selection mechanisms are voting mechanisms that are largely used to select agents based on nominations provided by the agents themselves. They have been very-well studied in the community of Social Choice and are used in several real contexts, such as committee selection. \nThis paper starts the study of such voting mechanisms in a setting where the mechanism receives in input  a “suggestion” of an optimal solution but the precision of the suggestion is not guaranteed. In the last years the area of mechanism design with prediction received a lot of interests and this framework has been applied to a long list of important problems. The increasing interest on this framework is due to the possibility of using it to model data-driven mechanisms, where the mechanism may receive suggestions from an expert or from some LLMs.\n\nThe paper focuses on the question of whether impartial selection mechanisms can be improved if they are given in input a prediction of a set of agents receiving a high number of nominations. Extensions of known mechanisms to the setting of mechanisms with prediction are presented both for the general setting, where each agent can present an arbitrary number of nominations and k agents have to be elected, and for more restricted settings. For all these settings bounds are given on the consistency and robustness.", "questions": "1.\tWhat is the meaning of the superscript used in your notation? (see for example lines 171-172). In general, I think your notation is not intuitive and too heavy. \n2.\tAt line 178, which is the definition of the function f and its relation to the f_i? Since f_i is a conditional probability, why don’t use the traditional notation for probabilities?\n3.\tAt line 216, I suggest to directly denote the permutation as \\pi(x), as done at line 219. Set S is implicitly defined by the vector x and you can remove it from the inputs to the mechanism.\n4.\tAt lines 229-231: your assumption is not sufficient to guarantee that the predicted vertex i will be the last vertex in the permutation and the mechanism can see all its incoming. For example, assume that x_j = 1 and i<j. Why is the statement at line 231 true? (Similar observations hold for the selection mechanisms proposed in the following sections for k>1).\n5.\tIn section 6 you give bounds on consistency and robustness achievable by impartial mechanisms only for k<=3. Any idea on what happens for k>3? Why is your argument not working?", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "STRENGHTS\nThe paper studies an important (known) problem in the social choice literature, with significant practical applications, in the setting of mechanisms with prediction. The argument perfectly fits the scopus of the conference. \nThis is a solid theoretical paper, with interesting contributions that adapt previously known mechanisms to the new setting of mechanisms with prediction.\nThe quality of writing is pretty good.\n\nWEAKNESSES\nThe contribution of the paper is exclusively theoretical and mainly incremental. It takes known mechanisms for impartial selection without prediction and adapts them to the setting of mechanisms with prediction. \n\nThe extensions are quite trivial but the analysis is not so simple and authors had to solve some technical challenges. Technical proofs are completely moved to the appendix and very few elements are given in the paper to convince the reader of the soundness of the statements. Moreover, appendix is simply a list of proofs of lemmas and theorems with no intuition of how the argument works.\n\nAn experimental analysis to validate the practical effectiveness of the proposed mechanisms is totally missing and left as future work.", "was_revised": true, "final_justification": "Authors answered all my questions in a satisfactorily way. I confirm my positive feeling on the paper.", "rebuttal": "We appreciate your thorough review and detailed comments. We agree that more intuition for the ideas involved in the proofs would be helpful to the reader, and we would be happy to use the extra page allotted for the final version for this purpose.\n\nRegarding the questions:\n\n- The superscript $-$ is used in $N^-$ and $\\delta^-$ to denote the in-neighborhood and indegree of a vertex, as standard in the literature to distinguish from out-neighborhood and outdegree. Since we do not need notation for the latter objects, we agree that removing it could make the notation a bit lighter.\n\n- $f_i(\\hat{S},G)$ denotes the $i$th entry of $f(\\hat{S},G)$, i.e., the probability assigned by a mechanism $f$ to a vertex $i$. We will make this clearer in the next iteration of the manuscript. We have chosen this notation rather than the traditional notation for probabilities for compactness,  since a mechanism is naturally defined as a function (from a pair graph/predicted set to a random subset of vertices) and must fully determine the selection probabilities.\n\n- We are glad to take the suggestion for the notation $\\pi(x)$ and the set $S$. Regarding the values $x_j$ for non-predicted vertices, they are sampled uniformly from $[0,1]$ in all randomized mechanisms based on this approach, so $x_j=1$ is a zero-probability event and does not affect the performance guarantee, but we agree this can be more clearly stated. In the (deterministic) fixed bidirectional permutation mechanism, we take $x_j\\in (0,1)$ to avoid this case.\n\n- The upper bounds in Section 6 have been obtained by computing mechanisms with optimal robustness and consistency guarantees and constructing graphs showing optimality (this works via LP duality). The same approach can be used to obtain upper bounds for $k>3$, but the difficulty increases and confidence in the tightness of the bounds decreases as $k$ grows. We have given a selection of bounds that we think are most interesting given our current state of knowledge but will make sure to provide a clearer justification for our choices: the case $k=1$ is solved; for $k=2$ we can achieve the best possible robustness subject to $1$-consistency, but cannot currently do the same when $1$-consistency is relaxed; the case of $k=2$ gives rise to the same bounds as the case of plurality for $k=1$, which suggests a connection between the two settings; for $k\\geq 3$ the optimal Pareto frontier and the currently achievable Pareto frontier do not intersect, and both are more complex than those for $k=2$."}]

Author rebuttal:

Meta-review: The authors study impartial selection (where agents mutually nominate each other) in the presence of predictions about the set of agents who will be nominated. In line with prior work in the predictions setting, they study the optimal tradeoff between consistency and robustness and present upper and lower bounds in a variety of settings (selecting 1, 2, and \ge 3 vertices).

Strengths:
- Reviewers praised the writing quality, exposition, illustrations (particularly Figure 1!), and motivation of the work. The paper is quite polished overall.
- The technical results are nontrivial, although they build on prior work. Some reviewers noted that the technical results are a bit incremental (mkRF).

Weaknesses:
- The authors leave some gaps between their upper and lower bounds for most settings. While this is perhaps to be expected from a paper that initiates the study of a new setting, it is still a shortcoming of the paper.
- The paper lacks empirical analysis (mkRF) and has a perhaps narrow scope (jF4z).
Decision: Accept (poster)