# incentivecompatible_classification__d0af13d3.pdf

The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20)

Incentive-Compatible Classification

Yakov Babichenko, Oren Dean, Moshe Tennenholtz Technion Israel Institute of Technology Haifa, Israel

We investigate the possibility of an incentive-compatible (IC, a.k.a. strategy-proof) mechanism for the classification of agents in a network according to their reviews of each other. In the α-classification problem we are interested in selecting the top α fraction of users. We give upper bounds (impossibilities) and lower bounds (mechanisms) on the worst-case coincidence between the classification of an IC mechanism and the ideal α-classification. We prove bounds which depend on α and on the maximal number of reviews given by a single agent, Δ. Our results show that it is harder to find a good mechanism when α is smaller and Δ is larger. In particular, if Δ is unbounded, then the best mechanism is trivial (that is, it does not take into account the reviews). On the other hand, when Δ is sublinear in the number of agents, we give a simple, natural mechanism, with a coincidence ratio of α.

1 Introduction There are many situations in which peer agents have binary, directed interactions with each other, and in which one side can rate his experience from the interaction, or rather rate the other agent. The following are just a few examples: 1. E-commerce sites in which buyers might also be sellers (e.g., ebay.com, amazon.com). 2. Academic paper reviewers for a conference might themselves be authors of papers submitted to the same conference. 3. Employees in an organisation are sometime asked to fill out a sociometric overview of their fellow friends. In all of the above examples, a coordinator/manager is classifying the agents in the system according to the reviews they received. In the e-commerce example, the top-rated sellers will appear higher and more frequently in search results; the academic conference will only accept a certain toprated portion of the papers. Employees with higher sociometric results have better chances at a promotion. A natural problem arises in order to maximize one s relative rating,

This project has received funding from the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (grant agreement no 740435). Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

it is a dominant strategy in these situations to give a harsh critique to all interactions. In this paper, we model the agents and their interactions as a directed network and ask whether it is possible to offer an incentive-compatible (IC) mechanism to select a subset which represents the top-rated ( worthy ) agents. We measure the quality of a mechanism as the resemblance between the selected set of the mechanism and the set of top-rated agents, in the worst case. We investigate the relation between the quality of the best possible mechanism to two parameters: (i) the maximal number of reviews a single agent can issue (the maximal out-degree in the network, denoted Δ), and (ii) the fastidiousness of the system (the relative size of the selected set, denoted α).

Our contribution

In this paper we investigate the existence of an αclassification IC mechanism in weighted networks. Weighted networks without any limitation were not considered before as a framework for selection mechanisms ((Kurokawa et al. 2015) considered only Δ-regular weighted networks; the assumption of Δ-regularity somewhat simplifies the optimisation criterion since in this case the optimisation for average in-weights is equivalent to the optimisation for the sum of in-weights.). The most significant novelty of our model is the consideration of mechanisms which classify the agents to worthy and unworthy , in contrast to previous works which only considered k-subset selection (k-selection) mechanisms. Our optimisation criterion is the coincidence between the mechanism s classification and the ideal classification. The difference from k-selection is two-fold. First, we do not know the exact size of the set which we need to select. Second, we try to select as many of the right (truly worthy) agents and not the wrong agents regardless of how high their in-degree is; this is very different from k-selection, which just looks for a subset with high in-degree (even if it is completely disjoint to the optimal subset). We prove upper and lower bounds on the quality of the best possible IC classification mechanism. We chart the behaviour of these bounds as a function of Δ and α. We show that as Δ grows (agents are allowed to review many others), the possibility of an IC classification mechanism narrows down until for large values of Δ the best mechanism is one of the two trivial mechanisms: select all the agents as wor-

thy, or select every agent independently with probability 1/2. We show the reverse behaviour with α: as we lower α (the system is more picky about its worthy-classified agents), the quality of the best possible IC classification mechanism decays to zero. On the other hand, for fixed α and for Δ which is negligible with respect to the number of agents, we provide a mechanism with a positive quality. The idea behind this mechanism is based on a well-known practice to partition the agents into three subsets: absolutely worthy, borderline, and absolutely unworthy. Unlike the well-known practice, our mechanism suggests to classify an agent into these categories after ignoring his reviews on others. This makes the mechanism IC, but complicates the performance analysis of the mechanism. Previous works (e.g. (Alon et al. 2011), (Kurokawa et al. 2015)) showed the existence of an optimal k-selection mechanisms when k is large (say k = ω(1) or k = ω(Δ) with regard to the number of agents). As explained above, these mechanisms only select a k-subset of agents with high indegree, while an α-classification mechanism needs to select as many of worthy agents and not unworthy agents. This extra predicament shows in the results as we bound the quality of any IC mechanism away from 1 (i.e., for any α < 1 there is no ideal IC classification mechanism). This also shows the significance of our mechanism which, under reasonable assumptions, selects not only good agents but the right agents. The graphs in Figure 1 summarize our main findings. Graph (a) shows our bounds on the quality of any IC mechanism as a function of α when Δ is negligible with respect to the number of agents. The grey dashed line is the ideal mechanism. The upper bound (red line) shows that for any α < 1, there is a gap between the best possible mechanism and the ideal mechanism, and this disparity is larger for lower values of α. The blue line denotes the quality of our proposed mechanism, and so the green area is what we know about the possible value of the quality of the best IC mechanism. Graph (b) shows the quality of any IC mechanism as a function of α when Δ is not bounded. Here the upper and lower bounds coincide to a single line, that is, we know what is the best possible quality for any value of α.

Figure 1: Our bounds for the quality of an IC classification mechanism as a function of α. In (a) Δ = o(n). The red/blue graphs denote our upper/lower bounds and the green area denotes the known feasible quality range. In (b) Δ = n 1. The single green graph is the quality of any IC mechanism.

Related work There have been in the past decade quite a few works on IC (sometimes called strategyproof or impartial) selection mechanisms in networks. The most similar model to ours is (Kurokawa et al. 2015). In that paper the authors considered the k-selection in a weighted Δ-regular network (that is, every agent has Δ out-edges and Δ in-edges), where k and Δ are constants. They considered IC mechanisms which try to optimize the average in-weights of the selected set. Their main result is a probabilistic mechanism which is optimal when Δ is negligible with respect to k. Other papers on this subject only consider unweighted networks, which can be seen as a special case of the weighted networks with weights in {0, 1}. These works can be divided into two flavours: (a) Optimisation works which try to optimize the total indegree of the selected agent or set of agents. Examples of this group are Alon et al.; Fischer and Klimm; Bjelde, Fischer, and Klimm; Bousquet, Norin, and Vetta (2011; 2014; 2017; 2014). Another example is Babichenko, Dean, and Tennenholtz (2018) in which the authors try to optimize the progeny of the selected agent. These works differ in several parameters of the problem, such as deterministic/probabilistic mechanisms; exact selection (selected set must be of size k) or inexact selection (selected set is of size at most k); and the subfamily of networks considered (all networks/m-regular networks/acyclic networks/etc.). (b) Axiomatic works which define a set of axioms and investigate the possibility/impossibility of mechanisms that fulfil maximal subsets of these axioms. Examples of this group are Holzman and Moulin; Mackenzie; Aziz et al. (2013; 2015; 2016). In (Altman and Tennenholtz 2008) the authors considered the possibility of complete ranking mechanisms under certain axioms. Paper organization. In Section 2, we formally present our model and main results. In Section 3, we prove our impossibility (upper bound) propositions (Propositions 10 and 11). These proofs rely on an extension of our model to a symmetric, probabilistic mechanism; this extension is formally defined in the beginning of Section 3. In Section 4, we present and prove a mechanism with a positive quality when the number of reviews of a single agent is negligible with respect to the number of agents (Proposition 12). In Section 5, we conclude and discuss our results.

2 Model and main results Let N = [n] be a set of n agents.1 We represent the interactions between the agents as a directed graph, G(N, E); thus an edge (x, y) means that agent x interacted with agent y and is allowed to review this agent. Let Ein(x), Eout(x) be the sets of in-edges and out-edges of x, respectively. We assume that each agent in the network is in control of the weights of

1We assume n is large as we are generally interested in results which are asymptotic in n. For the same reason we habitually drop floors and ceilings for easier reading.

his outgoing edges. These weights, which are real numbers in the interval [-1,1],2 represent the reviews of the source agent for the target agents. Thus, the reviews of agent x N for his interactions are {we|e Eout(x)}. After all agents submitted reviews on their interactions,3 we get a weighted, directed graph; from now on we assume all the edges of G are weighted. Based on the reviews that agent x received, {we|e Ein(x)}, we define his score and his relative ranking in the system. The score of agent x is the average of weights on Ein(x):

e Ein(x) we

|Ein(x)| , Ein(x) = ,

0, Ein(x) = . (1)

The ranking of agent x is the number of agents who strictly have a better score than him: r(x, G) = |{y N|s(y, G) > s(x, G)}|.4 For a given real parameter α (0, 1) we consider as worthy the subset of agents who are in the top α-ranking:5

Iα(G) = {x N|r(x) < αn }.

Notice that the size of Iα(G) is at least αn, but might be higher in case of ties. For instance, in the empty graph, Iα(G(N, )) = N for all α. We denote by Iα(G) = N\Iα(G), the subset of unworthy agents. Our goal is to offer an IC mechanism which selects a set which is as similar as possible to the subset of worthy agents. Formally, let G(n) be the family of all [-1,1]-weighted, directed networks on n nodes and let P(N) be the power set of N.

Definition 1. A classification mechanism is a function M : G(n) P(N).

The set M(G) is the subset of agents which the mechanism M classifies as worthy in the network G. We denote by M(G) = N\M(G) the subset classified as unworthy by the mechanism. Notice that the definition of a mechanism depends on n through its dependence on G(n) and N. We abuse notation and regard a single mechanism M as if it represents a series of mechanisms one for every natural n. The IC requirement means that an agent s classification is not influenced by his own reviews; that is, changing the weights on the out-edges of an agent does not alter his classification.

Definition 2. A classification mechanism M is incentivecompatible if for every n N, G, G G(n), x N, such that: E(G) = E(G ) and e E\Eout(x), we(G) = we(G ),

x M(G) x M(G ).

2A review of 0 is the neutral review. For example, an agent with all-zero in-edges is rated in the same way as an agent with no in-edges (see the definition of s( ) in (1)). 3We can set a zero-weight on all interactions which were not reviewed (see Footnote 2), hence we may assume w.l.o.g. that all interactions have been reviewed. 4From now on, when G is clear from the context, we just write s(x), r(x). 5We think of α as the selectiveness of the system: a lower value for α means that the tag of being worthy is more prestigious.

To define a measure for the quality of the mechanism, we first define a measure of coincidence between M(G) and Iα(G):

C(M(G), Iα(G)) =

1, x (M(G) Iα(G)) (M(G) Iα(G)),

1, otherwise. (2)

In other words, C(M(G), Iα(G) gives one point for every agent that M(G) classified correctly and takes one point for every agent which was classified erroneously; the result is normalised by the number of agents.6 This measure can be somewhat simplified to get,7

C(M(G), Iα(G)) =

1 n (|((M(G) Iα(G)) (M(G) Iα(G)))| |M(G) Iα(G)|)

n (|N\(M(G) Iα(G))| |M(G) Iα(G)|)

n |M(G) Iα(G)|.

Our main theorems imply that the possibility of an IC mechanism which guarantees a fixed level of coincidence depends on two parameters. The first is α. The second is the maximal out-degree in the network (i.e., the maximal reviews an agent can issue), denoted by Δ. Intuitively, if Δ is high, then an unworthy agent might use his influence on the score of Δ worthy agents to improve his ranking and be considered worthy. If α is relatively low, then these manipulations might influence a large portion (or all) of the worthyclassified agents, which makes it harder to find an IC mechanism with high coincidence measure. Our results will show that this intuition is indeed correct. Let G(n, Δ) be the family of all networks on n nodes with maximal out-degree Δ. The quality of a mechanism for given α, Δ, is the limit when n goes to infinity of the worst case of the coincidence measure:

Qα,Δ(M) = lim n min G G(n,Δ) C(M(G), Iα(G)). (3)

We will prove upper and lower bounds on Qα,Δ for any IC classification mechanism.

Main results

We start by defining two trivial IC mechanisms. Trivial means that they classify the nodes without any regard to the edges weights. Let MN be the complete mechanism, i.e., MN (G) = N for all G G(n).

Proposition 3. For any α, Δ, Qα,Δ(MN ) = 2α 1.

6Other measures might be appropriate for different applications. We discuss two of these alternatives in Section 5. The main conclusions from our results stay the same in these variations. 7The operator is the exclusive or .

Proof. Since |N Iα(G)| = |Iα(G)| = n |Iα(G)| n(1 α), we get that for any graph,

C(MN (G), Iα(G)) = 1 2

n |N Iα(G)| 1 2n(1 α)

Our second trivial mechanism, M1/2, selects every node to be worthy with probability 1/2, independently. We use here the concept of a probabilistic mechanism intuitively; in the beginning of Section 3, we formally extend our model to include this kind of mechanism. Mechanism M1/2 correctly classifies nodes x with probability 1/2, hence Qα,Δ(M1/2) =

0 for all α, Δ. Our first result is a strong impossibility, saying that when Δ is large, one of the two trivial mechanisms is the best possible.

(a) For α 1

2 and Δ 2(1 α)n, Qα,Δ = 2α 1.

(b) For α < 1

2 and Δ = (1 o(1))n, Qα,Δ = 0.

Proof. This is a direct consequence of Proposition 3, our observation for M1/2 and Proposition 11.

Our second result is a non-trivial, yet quite natural, mechanism with a better quality than the complete mechanism, provided Δ = o(n). The idea behind this mechanism is to recognize three subsets of agents: absolutely worthy, absolutely unworthy, and borderline. The first two subsets contain those agents who will not be able to change their classification, no matter what their reviews will be. The fact that Δ is negligible guarantees that the absolutely worthy and absolutely unworthy sets will include a large portion of the true worthy and unworthy subsets, respectively. The mechanism then classifies the absolutely worthy agents as worthy and the absolutely unworthy as unworthy. If we allow the mechanism to be probabilistic, we can select each of the borderline agents to be worthy with probability 1/2; this strategy assures that these agents will not hurt the quality (but will not help it either). We also provide a deterministic version of this mechanism which always classifies correctly almost half of the borderline agents. The following theorem summarises our knowledge when Δ = o(n).

Theorem 5. For any α and Δ = o(n), α Qα,Δ 1

Proof. The lower bound comes from an analysis of the above-described probabilistic mechanism; see Proposition 13. We also prove the existence of a deterministic version of this mechanism in Proposition 12. The upper bound is proved in Proposition 10.

3 Impossibilities As promised, we start by extending our model to include probabilistic mechanisms. A probabilistic mechanism assigns each node a probability of being worthy.

Definition 6. A probabilistic classification mechanism is a function Mp : N G(n) [0, 1].

To get a concrete selected set from a probabilistic mechanism, we select each node independently with his assigned probability. In other words, the probability of subset X N to be selected under mechanism Mp in the graph G is

Pr[X|Mp(G)] =

x X Mp(x, G)

x/ X (1 Mp(x, G)). (4)

The IC requirement translates to the requirement that an agent cannot influence his own selection probability. Definition 7. A probabilistic classification mechanism Mp is incentive-compatible if for every n N, G, G G(n), x N, such that: E(G) = E(G ) and e E\Eout(x), we(G) = we(G ), Mp(x, G) = Mp(x, G ). The coincidence of Mp(G) with Iα(G) is naturally extended using expectation over the selected set:

C(Mp(G), Iα(G)) =

X P (N) Pr[X|Mp(G)]C(X, Iα(G))

X P (N) Pr[X|Mp(G)]

1, x (X Iα(G)) (X Iα(G))

1, otherwise.

Changing the summation order and inserting (4) we get,

C(Mp(G), Iα(G)) =

X P (N\{x})

Mp(y, G), y X

1 Mp(y, G), y / X

Mp(x, G) (1 Mp(x, G)), x Iα(G)

(1 Mp(x, G)) Mp(x, G), x Iα(G).

X P (N\{x})

Mp(y, G), y X

1 Mp(y, G), y / X = 1,

C(Mp(G), Iα(G)) = 1

x N (2Mp(x, G) 1)

1, x Iα(G) (5)

= Iα(G) Iα(G)

x N Mp(x, G)

1, x Iα(G). (6)

The quality of a probabilistic mechanism can now be defined exactly as in (3):

Qα,Δ(Mp) = lim n min G G(n,Δ) C(Mp(G), Iα(G)).

From Definitions 6 and 7 and the coincidence definition above, it is clear that the IC (deterministic) mechanisms for which we initially defined our problem are a special case of IC probabilistic mechanisms. Hence we may prove our upper bounds (i.e., impossibilities) for probabilistic mechanisms. We furthermore show that it is enough to consider a subfamily of symmetric, IC, probabilistic mechanisms. Definition 8. A probabilistic mechanism Mp is symmetric if for any network G G(n) and two isomorphic nodes x, y N, Mp(x, G) = Mp(y, G).

Claim 9. Let Mp be any IC, probabilistic, classification mechanism. Then there is an IC, symmetric, probabilistic classification mechanism M p with Qα,Δ(M p) Qα,Δ(Mp).

Proof. Let S(N) be the set of permutations over N. For π S(N), let Gπ be the graph which is isomorphic to G under the automorphism defined by π. We define the mechanism M p:

M p(x, G) = 1

π S(N) Mp(π(x), Gπ). (7)

Mechanism M p is clearly IC, since Mp is IC and otherwise the calculation above is irrelevant of any of the weights in G. It is also symmetric, since for two isomorphic nodes, x, y, the following two sets of the couples are exactly the same:

{(π(x), Gπ)|π S(N)} = {(π(y), Gπ)|π S(N)}.

It remains to show that the quality of M p is at least that of Mp. Planting (6) into (7) and changing the summation order we get that for any G,

C(M p(G), Iα(G)) =

Iα(G) Iα(G)

π S(N) Mp(π(x), Gπ)

1, x Iα(Gπ)

1, x Iα(Gπ)

= Iα(G) Iα(G)

x N Mp(π(x), Gπ)

1, x Iα(Gπ)

1, x Iα(Gπ)

Let Q = Qα,Δ(Mp). For any ϵ > 0, there is n0 such that for all n > n0 and for all G G(n, Δ), C(Mp(G, Iα(G))) Q ϵ, which means that

x N Mp(x, G)

1, x Iα(G) Q ϵ Iα(G) Iα(G)

Hence, C(M p(G), Iα(G)) Q ϵ. Since this is true for any ϵ, we get that Qα,Δ(M p) Q.

We are now ready to prove our two impossibility propositions which imply the upper bounds of Theorems 4 and 5.

Proposition 10. For all α, Δ, Qα,Δ 1

Proof. Let v be a distinct node. Partition N\{v} into three sets, A, B, C, of sizes (1 α)n

2 , αn 1, respectively. Let G be the network in which every node in A B has an out-edge to v, and C is a cycle. Set the weights on the edges from A to v to be 1, the weights on the edges from B to v to be 1 + 1 (1 α)n, and the weights on C to be 1. For any

a A, b B, c C their scores are: s(c) = 1, s(a) = s(b) =

0, and s(v) = |A| + |B|( 1 + 1/(1 α)n)

|A| + |B| = 1 2(1 α)n > 0.

Hence Iα(G) = C {v}. Let M be an IC, probabilistic and

symmetric classification mechanism. By symmetry, we may denote M(a, G) = μ for any a A. Using (5) we get that,

C(M(G), Iα(G)) 1

n ((1 2μ)|A| + |B| + |C| + 1)

= 1 μ(1 α). (8)

Now choose a distinct node a0 A and change the weight on its out-edge to v to be 1 + 1 (1 α)n; we refer to this net-

work as G . The score of v has dropped in 2 1/(1 α)n

|A| + |B| =

(1 α)n > 1 2(1 α)n, for n large enough. Hence

s(v, G ) < 0. Since the rest of the scores are the same in G and G , we get that Iα(G ) = N\{v}. By IC, M(a0, G ) = M(a0, G) = μ, and by symmetry M(b, G ) = μ for any b B. We now get ,

C(M(G ), Iα(G )) 1

n (|A| + (2μ 1)|B| + C + 1)

= 1 (1 μ)(1 α) = α + μ(1 α). (9)

From (8) and (9), Qα,Δ min{1 μ(1 α), α + μ(1 α)}. Comparing the two terms to find the optimal value for μ we find that

1 μ(1 α) = α + μ(1 α) μ = 1

= Qα,Δ 1 1 α

Proposition 11. Let m = min 2(1 α), Δ

. Then Qα,Δ

Proof. Consider two cases:

Case I: m 2α. Let A, B N be two disjoint subsets of size nm/2. Let G be the graph in which A B is a clique and there are no other edges. We set the weights on all the out-edges of nodes in A to be 0, and the weights on all the out-edges of nodes in B to be 1. Hence every a A has a score of s(a) = |B| |A B|, every

b B has a score of s(b) = |B| 1

|A B| and the score of every

c / A B is 0. Since |A| = mn

2 αn, Iα(G) = A. Let M be an IC, probabilistic, symmetric mechanism. By the symmetry of M, all the vertices of B get the same probability. Denote it μ. Let b be a distinct vertex in B. Let G be the graph we get when we nullify all the weights on the outgoing edges of b. Since b is now isomorphic to the vertices in A, we get by IC and the symmetry of M that a A, M(a, G ) = M(b, G ) = M(b, G) = μ. We see that there is a trade-off in the value of μ; on the one hand, we need it to be high if we want a good quality on G , but on the other hand, it needs to be low for a good quality on G. The idea of the proof is that for n large enough, we can repeat this process and show that in essence all the vertices in A B in the graph G (or at least in one of the graphs we get from G after a negligible number of steps) should have approximately the same probability. This

implies that

n (|A|(2μ 1) + |B|(1 2μ) + |N\(A B)|)

n (|A| |B|) + 1 |A B|

To make this claim precise, suppose for contradiction that Qα,Δ(M) 1 m + ϵ for some ϵ > 0. For k X, X to be found, we let Ak, Bk N be two disjoint subsets with sizes |Ak| = mn/2 + k, |Bk| = mn/2 k. Define the graph Gk in which Ak Bk is a clique, and the weights on the outgoing edges of vertices in Ak are all 0, and the weights on the outgoing edges of vertices in Bk are all 1. Notice the following:

a) The vertices in Ak are symmetric, and so are the vertices in Bk. b) Iα(Gk) = Ak. c) If we nullify the outgoing edges of one of the nodes b Bk then we get the graph Gk+1in which b Ak+1.

By the symmetry of M, we may denote for any k, μka = M(a, Gk) for all a Ak, and μk b = M(b, Gk) for all b Bk. By (c) and IC of M, μk b = μk+1 a . By the assumption on the quality of M:

1 n (|Ak|(2μka 1) + |Bk|(1 2μk b ) + |N\(Ak Bk)|)

1 n ((mn/2 + k)(2μka 1) + (mn/2 k)(1 2μk b ) + (1 m)n)

(mn + 2k)μka (mn 2k)μk b 2k ϵn.

Summing up this inequality for 0 k X and substituting μk b for μk+1 a we get,

mnμ0a (mn 2X)μX b + 2 X

k=1 (2k 1)μka X(X + 1) Xϵn.

Let μmax = max 1 k X μka. If X = o(n), then for n large enough

mn 2X. We strengthen the inequality by removing the negative terms on the left-hand side, and replacing all the μka with μmax:

μmax(mn + 2X2) Xϵn

= μmax ϵX m + 2X2/n .

Now taking X = 2m/ϵ we get that for n large enough μmax > 1, which is a contradiction.

Case II: m < 2α The proof is very similar. We define three subsets, A, B, C of size nm/2, nm/2 and (α m/2)n, respectively.8 Let G be the graph in which A B is a clique and C is a cycle. Again we set

8Since we assume m < 2α, |C| > 0.

all the weights on the out-edges of the nodes in A to be 0, and weights on all the out-edges of nodes in B to be 1. The edges in the cycle in C also get a weight of 1. Thus now s(c) = 1 > s(a) > s(b) for any c C, a A, b B. Since |A C| = αn, we have Iα(G) = A C. Let M be an IC, probabilistic, symmetric mechanism. Using the same technique as before, we get that all the vertices in A B should get the same probability, which we call μ. Since Iα(G) = A C we can bound as before:

1 n (|A|(2μ 1) + |B|(1 2μ) + |N\(A B)|) = 1 m.

The formal argument is precisely the same.

4 Non-trivial mechanism In this section we show the existence of a mechanism with quality α, provided Δ = o(n). Specifically, we will show the following: Proposition 12. For any α and any Δ min{ 1

there is an IC classification mechanism with quality α 3Δ

For better exposition, we start by presenting a probabilistic mechanism which is slightly better. Proposition 13. For any α and any Δ αn, there is an IC probabilistic classification mechanism with quality α Δ

For a graph G and x G, denote by Gx the graph we get when we set all the weights on the out-edges of x to be -1. Let β = α Δ

n . The idea is to partition N into three subsets:

W(G) = {x N|x Iβ(Gx)},

U(G) = {x N|x Iα(Gx)},

B(G) = N\(W U) = {x N|x Iα(Gx)\Iβ(Gx)}.

Notice that the definitions of W, U, B are IC, in the sense that the sorting of x to one of these sets does not depend on his own reviews (since we fixed all his reviews to -1 before choosing his set). If x W, then his ranking in Gx is less than βn: r(x, Gx) < βn. The real reviews of x may increase the score of at most Δ agents, which means that r(x, G) r(x, Gx) + Δ < βn + Δ = αn; hence x Iα(G). We have proved that W Iα(G). We think of W as the absolutely worthy agents. Similarly, the set U is the set of absolutely unworthy agents: for x U, r(x, G) r(x, Gx) αn (increasing his reviews can only hurt his relative ranking), and U Iα(G). The set B contains all the borderline agents: these are the agents which we are not sure how to classify. We define the following probabilistic mechanism:

1/2, x B(G).

Since W, U, B are IC, this mechanism is IC. The mechanism is always correct in the classification of the agents in W U. We set the probability of agents in B to be 1/2 so that the expected contribution of the agents in B to the coincidence

measure is zero. We get that for any G G(n, Δ) with Δ αn,

C(Mp(G), Iα(G)) = 1

n (|W(G)| + |U(G)|) |W(G)|

This completes the proof of Proposition 13. The idea for the deterministic mechanism is similar. This mechanism selects as worthy all the agents in W and as unworthy all the agents in U. For the agents in B we need to find an IC, deterministic way to classify them such that in every network about half of them are rightly classified. Notice first that if |U| |B| 2Δ then

C(M(G), Iα(G)) 1

n (|W| + |U| |B|) 1

Let L(B) be a linear ordering of B according to r( , G) and breaking ties lexicographically.9 Let B+ be the top half nodes in B according to L. For x B we denote by Bx the set B in Gx.10 Similarly, let B+ x = B+(Gx). We now complete our definition of mechanism M by setting for every x B, x M(G) x B+ x . That is, x B is accepted if and only if it is ranked in the top half of Bx when breaking ties lexicographically. The mechanism does not use the weights on the outgoing edges of x to determine its classification, hence it is IC. We complete the proof of Proposition 12 with the following lemma.

Lemma 14. Suppose that Δ 1

3 (1 α)n. For any graph

G G(n, Δ) with |U| < |B| 2Δ at least 1

2 (|B U| Δ) of the agents in B U are classified correctly. Using this lemma we get that for any such graph,

C(M(G), Iα(G))

2 (|B U| Δ) 1

2 (|B U| + Δ)

n (|W| Δ) 1

n (βn Δ) = α 2Δ

as required.

Proof of Lemma 14. Consider two cases. Case I: |Iα(G)| αn + 2Δ. In this case B Iα\Iβ, since if x / Iα(G), then in Gx there are at least |Iα| Δ αn + Δ agents with a higher score than s(x); hence x / Iα(Gx). Moreover, for any x B, Bx Iα(G), since for any y / Iα, there are in Gx,y at least |Iα| 2Δ αn agents with a higher score than s(y). Let B be the top 1

2 (|B| Δ) ranked agents in B according to L(B). We claim that the agents in B are all classified by our mechanism to be worthy, which is the correct classification (since B Iα(G), as explained). The reason is that when we set the

9That is, for x, y B, x L y (r(x) > r(y)) ((r(x) = r(y)) (x < y)). 10To be clear, for x, y N, let Gx,y be the graph in which we set all the weights on the outgoing edges of x and y to -1. Then Bx(G) = B(Gx) = {y N|y Iα(Gx,y)\Iβ(Gx,y)}.

weight on an edge (x, y) with x B to -1, we add at most one agent to B which is ranked above x (this might happen when y W), or we remove at most one agent from B which is ranked below x (this might happen when y B and is ranked below him). Thus x must be in the top-half ranked agents in Bx. Since all the agents in U are correctly classified, we get that at least |B | + |U| = 1

2 (|B| + 2|U| Δ) are classified correctly. Case II: |Iα(G)| < αn + 2Δ. Let B be the bottom 1

2 (|B| |U|) Δ ranked agents in B according to L(B).11 Since |B U| = 1

2 (|B| + |U|) Δ 1 2 (1 β)n Δ = 1

2 Δ, and |Iα(G)| = n Iα(G) > (1 α)n 2Δ 1

2 Δ, we get that B Iα(G). It is therefore enough to show that for any x B , x / B+ x . Indeed, lowering the weights on the out-edges of x can advance x in the ranking of B by at most Δ places (if the edges are to nodes in B that are ranked higher than x), and it might also add all the nodes of U to |B|; in any case x will still be in the bottom half of Bx.

5 Conclusions We have introduced a generic model for the classification of agents to worthy and unworthy according to their own reviews of each other. We draw two general conclusions regarding the existence of an IC classification mechanism: 1. If Δ is large, there is no good mechanism in the sense that the best mechanisms do not take into consideration the reviews. 2. If Δ is negligible with respect to the number of agents, there is a mechanism with a positive quality, but not with quality 1. Our measure for the coincidence between the selected set and the true worthy agents (2) assumes that every classification/misclassification has the same value/price. In other applications it makes more sense to consider only the classification/misclassification of the worthy agents, which leads to the following measure:

C(M(G), Iα(G)) = 1 |Iα(G)|

1, x Iα(G),

1, x / Iα(G).

Yet another measure might consider all the agents but normalise the classification/misclassification of an agent according to his true set:12

C(M(G), Iα(G)) =

|M(G) Iα(G)|

2|Iα(G)| + |M(G) Iα(G)|

We mention here that using these measures does not change our two conclusions above; in other words, our conclusions are intrinsic in the problem and not the result of a specific measure. The exact claims and proofs can be found in the appendix of the full version; see (Babichenko, Dean, and Tennenholtz 2019).

11Notice that |B | > 0 due to our assumption on |U|. 12Though here we need to assume that Iα(G) is not empty, or define the measure for this case separately.

References Alon, N.; Fischer, F.; Procaccia, A.; and Tennenholtz, M. 2011. Sum of us: Strategyproof selection from the selectors. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK XIII, 101 110. Altman, A., and Tennenholtz, M. 2008. Axiomatic foundations for ranking systems. Journal of Artificial Intelligence Research 31(1):473 495. Aziz, H.; Lev, O.; Mattei, N.; Rosenschein, J. S.; and Walsh, T. 2016. Strategyproof peer selection: Mechanisms, analyses, and experiments. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI 16, 390 396. Babichenko, Y.; Dean, O.; and Tennenholtz, M. 2018. Incentive-compatible diffusion. In Proceedings of the 2018 World Wide Web Conference, WWW 18, 1379 1388. Babichenko, Y.; Dean, O.; and Tennenholtz, M. 2019. Incentive-compatible classification. https://arxiv.org/abs/1911.08849. Bjelde, A.; Fischer, F.; and Klimm, M. 2017. Impartial selection and the power of up to two choices. ACM Trans. Econ. Comput. 5(4). Bousquet, N.; Norin, S.; and Vetta, A. 2014. A near-optimal mechanism for impartial selection. In Liu, T.-Y.; Qi, Q.; and Ye, Y., eds., Web and Internet Economics, 133 146. Cham: Springer International Publishing. Fischer, F., and Klimm, M. 2014. Optimal impartial selection. In Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 14, 803 820. Holzman, R., and Moulin, H. 2013. Impartial nominations for a prize. Econometrica 81(1):173 196. Kurokawa, D.; Lev, O.; Morgenstern, J.; and Procaccia, A. D. 2015. Impartial peer review. In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI 15, 582 588. Mackenzie, A. 2015. Symmetry and impartial lotteries. Games and Economic Behavior 94:15 28.