--- title: "Incentive-Compatible Selection for One or Two Influentials" authors: - "Yuxin Zhao" - "Yao Zhang" - "Dengji Zhao" doi: "10.24963/ijcai.2023/327" url: "https://ijcai.org/proceedings/2023/327" pdf: "https://ijcai.org/proceedings/2023/0327.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "2931-2938" track: "Main Track" keywords: - "Game Theory and Economic Paradigms: GTEP: Mechanism design" --- # Incentive-Compatible Selection for One or Two Influentials Yuxin Zhao, Yao Zhang, Dengji Zhao *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 2931-2938. DOI: [10.24963/ijcai.2023/327](https://doi.org/10.24963/ijcai.2023/327) ## Abstract Selecting influentials in networks against strategic manipulations has attracted many researchers' attention and it also has many practical applications. Here, we aim to select one or two influentials in terms of progeny (the influential power) and prevent agents from manipulating their edges (incentive compatibility). The existing studies mostly focused on selecting a single influential for this setting. Zhang et al. [2021] studied the problem of selecting one agent and proved an upper bound of 1/(1+ln2) to approximate the optimal selection. In this paper, we first design a mechanism to actually reach the bound. Then, we move this forward to choosing two agents and propose a mechanism to achieve an approximation ratio of (3+ln2)/(4(1+ln2)) (approx. 0.54). ## Full text ## 1 Introduction Consider the scenario where we want to select influential agents in a network constructed by referral relationships (e.g., the following relationships in Twitter, the citations between academic papers, etc.). The selected agents may be rewarded with prizes or benefits (e.g., job opportunities [Kotturi et al., 2020]). Hence, agents have the incentive to manipulate their relationships to make themselves selected. Therefore, selection mechanisms that can prevent agents from strategic manipulations (which is referred to as the property of incentive compatibility) are highly demanded [Alon et al., 2011]. Many studies have investigated incentive-compatible selection mechanisms on different influence measurements for different purposes (see [Olckers and Walsh, 2022] for a complete survey). In this paper, we focus on the setting where an agent's influential power is measured by her progeny (the number of all agents who directly or indirectly follow her). For this setting, two studies have been conducted before. Babichenko et al. [2020b] proposed the first single agent selection mechanism for progeny maximization that can prevent agents from adding or hiding their out-edges. Their mechanism reaches an approximation ratio of about 1/3 (i.e., the expected progeny of the chosen agent is about 1/3 of the largest). However, their mechanism only works in forests. Therefore, Zhang et al. [2021] further studied the same problem in directed acyclic graphs (DAGs) with restricting manipulations in the scope of hiding edges (agents cannot add new edges). Their proposed mechanism achieves an approximation ratio of 1/2. Moreover, they proved an upper bound 1/(1 + ln2) of the approximation ratio for any incentivecompatible and fair selection mechanism in the DAG setting. In this paper, we follow the DAG setting of [Zhang et al., 2021] and make the following contributions: - For selecting one agent, we close the gap between the known approximation ratio of 1/2 and the upper bound of 1/(1 + ln 2). We propose a mechanism to achieve the exact upper bound. - For selecting two agents, we show that, for the class of mechanisms that only select agents from the 1influential set 1 (most of the existing mechanisms belong to this class), the approximation ratio cannot exceed 1/2 if the target is to select at most two agents. Moreover, we provide a deterministic mechanism in this class that exactly reaches the approximation ratio of 1/2. - We then propose a new incentive-compatible mechanism based on a 2-influential set for selecting two agents. The new mechanism achieves a higher approximation ratio of (3 + ln2)/(4(1 + ln2)) (≈ 0.54). We also provide a general upper bound (23/27) of any incentivecompatible mechanism for selecting two agents. ## 1.1 Other RelatedWork Many studies on incentive-compatible selection mechanisms use in-degrees to measure agents' influential power, which is also referred to as peer selection. For the in-degree measurement, Alon et al. [2011] firstly proposed an incentivecompatible peer selection mechanism by a randomized partition method, which divides agents into two groups and chooses the agents according to their in-degrees from the other group. Following this work, there are two major directions. One is to characterize incentive-compatible peer selection mechanisms with axioms, which is initiated by Holzman and Moulin [2013]. Mackenzie [2015] continued this study by adding symmetric axiomizations. The other direction is to improve the approximation ratios of the existing incentive-compatible peer selection mechanisms. Fischer and Klimm [2014] extended the idea of the partition mechanism to a permutation mechanism, which achieves the optimal approximation ratio (1/2) for selecting one agent with indegree. Then, Bousquet et al. [2014] characterized a class of networks where the permutation mechanism selects an agent close to the optimal. Bjelde et al. [2017] generalized the permutation mechanism for selecting multiple agents, and gave both lower and upper bounds of the approximation ratio. Recent studies also started to consider an alternative evaluation called additive approximation, which focuses on the expected difference from the optimal rather than the worstcase ratio [Caragiannis et al., 2021; Caragiannis et al., 2022; Cembrano et al., 2022]. There are also extensions on the networks, including a weighted network, where the influential power is a weighted in-degree [Kurokawa et al., 2015; Wang et al., 2018; Babichenko et al., 2020a], and rank aggregation, where each agent assigns a rank to others [Kahng et al., 2018; Mattei et al., 2020]. 1 1-influential set contains all agents each of whom has the largest progeny by hiding her out-edges. There is also a rich body of work focusing on different measurements of influential power. Ghalme et al. [2018] designed a naturally strategy-proof score function to measure the popularity of agents, thereby simplifying the selection. In contrast, Babichenko et al. [2018] targeted a PageRank-like centrality [Page et al., 1999] and offered a two-path mechanism which achieves a good approximation ratio of 2/3. Moreover, Babichenko et al. [2020b] focused on the progeny of the selected agent and proposed a mechanism with an approximation ratio of 1/(4 ln 2) in forests. Zhang et al. [2021] then proposed a geometric mechanism with an approximation ratio of 1/2 in DAGs, which is what we follow here. ## 2 Preliminaries Let Gn be the set of all directed acyclic graphs (DAGs) with n nodes and G = ⋃n∈N+ Gn be the set of all DAGs. Consider a network represented by a graph G = (N,E) ∈ G, where N = {1, 2, . . . , n} is the node set and E is the edge set. Each node i ∈ N represents an agent, and each edge (i, j) ∈ E represents that agent i follows (votes for, or quotes) agent j. Let Ei = {(i, j) | (i, j) ∈ E, j ∈ N} be the set of all edges from i. We say an agent j is influenced by the agent i if there exists a path from j to i in G. Let P (i, G)2 be the set of agents who are influenced by agent i (including i herself), which is referred to as the progeny of agent i. Our goal is to select a group of agents in the network as delegates with larger progeny. Let Sk = {S | S ⊆ N, |S| = k} be the set of all subsets with k agents, and S≤k = ⋃kt=0 St. A k-selection mechanism decides how to choose up to k agents as delegates. Definition 1. A k-selection mechanism for G is a family of functions f : Gn → [0, 1]S≤k for all n ∈ N+, that maps each graph to a probability distribution on all subsets with no more than k agents. 2 or simply P(i) if no ambiguity. Additionally, for the sake of tidiness, the notation of the set also indicates its size if no ambiguity. For a given graph G ∈ G and a k-selection mechanism f , denote xS(G) = (f(G))S as the probability of the subset S ∈ S≤k being selected, and xi(G) = ∑S∈S≤k and i∈S xS(G) as the probability of the agent i being selected. For an agent i ∈ N, she wants her probability to be selected (xi) as large as possible, while for the owner of the mechanism, we want the influential power of the selected group (the sum of the progeny) as large as possible. Unfortunately, if we simply choose an optimal subset with k agents, i.e., S∗ k ∈ argmaxS∈Sk ∑i∈S |P(i,G)|, then agents will have incentives to hide their edges to increase their ranks to be selected. We want to avoid such a manipulation, which requires the mechanism to be incentive-compatible. Definition 2. A k-selection mechanism for G is incentivecompatible (IC) if for every n ∈ N+, and every two graphs G = (N, E), G′ = (N, E′ ) ∈ Gn, such that E\Ei = E′ \E′ i and Ei ⊇ E′ i for i ∈ N, we have xi(G) ≥ xi(G′ ). Intuitively, incentive compatibility implies that no matter how other agents follow each other, it is an undominated strategy for any agent not to hide her out-edges. Since an incentive-compatible k-selection mechanism cannot always choose a group with the highest influential power, we seek the approximation of the optimum, which guarantees a worstcase ratio between the expected progeny of the selected group and an optimal group for all DAGs. Definition 3. An incentive-compatible k-selection mechanism is α-optimal if For convenience, we can characterize an optimal group by defining a strict order of agents as follows. Definition 4. For a graph G = (N,E) ∈ G, and agents i, j ∈ N, i ̸= j, we say i ≻ j if either P(i,G) > P(j,G) or P (i, G) = P (j, G) with i > j. Let i∗t be the agent with rank t such that |{j | j ≻ i∗t }| = t - 1, which must be unique since the order is strict. Then, we can order all the agents as the ranking sequence i∗1 ≻ i∗2 ≻ · · · ≻ i∗n . Apparently, {i∗1 , · · · , i∗k } is an optimal set for selecting k agents. Hence, for our strategic setting, we will pay attention to agents who can pretend to be the first k agents in the ranking sequence by hiding their out-edges. Definition 5. For a graph G = (N,E), an agent i belongs to the k-influential set Sinf. k (G) if |{j | j ≻ i}| < k holds in the graph G′ = (N, E \ Ei). In this paper, we mainly focus on the cases for k ∈ {1, 2}. Hence, we use some observations about Sinf. 1 (G) and Sinf . 2 (G). To make it easy to follow, we present the observations about Sinf. 1 (G) below as preparation and present the observations of Sinf. 2 (G) in Section 4.2. Observation 1 ([Zhang et al., 2021]). For any graph G, the set Sinf. 1 (G) can be written as {i1, i2, · · · , im}, wherem≥ 1, i1 = i∗1 , and it+1 ∈ P(it) \ {it} for all t < m. Intuitively, the agent i∗1 who ranks the first is naturally in the 1-influential set. Furthermore, if there are more than one agent in the set, the agent who has a lower rank must be in the progeny of those who have higher ranks; otherwise, she will still have a lower rank when deleting her out-edges. Hence, in other words, we can find a path in G that passes through all agents in the set with the order of their ranks. Observation 2 ([Zhang et al., 2021]). For any graph G, if the set Sinf. 1 (G) = {i1, i2, · · · , im} has more than one agent, i.e., m > 1, then for any 1 < t ≤ m, 2P(it) ≥ P(i1). Inferred from Observation 1, if there is another agent except for i∗1 is in the 1-influential set, she should hold at least half of i∗1 's progeny to make herself rank the first after removing her out-edges. ## 3 Select One Agent In this section, we present our result for only selecting k = 1 agent. Not only does it help us understand the proposed methods in the following section for k = 2, but also fills the gap between the existing mechanisms and the upper bound of approximation ratios for IC 1-selection mechanisms, which is 1/(1 + ln 2) confirmed by Zhang et al. [2021]. Formally, our method can be viewed as a general variant of the modified Babichenko's mechanism [2020b]. ## β-logarithmic Mechanism (β-LM) 1. Given a network G = (N, E), find the 1-influential set Sinf. 1 (G) = {i1, . . . , im}, where it ≻ it+1 for all 1 ≤ t < m. 2. Assign the probability of each agent to be selected as follows: The total probability of selecting one agent in β-LM is at most β + (1 - β) log2(P (i1)/P (im)) ≤ 1 by the fact in Observation 2. Hence, the probabilities assigned by the mechanism are valid as long as 0 ≤ β ≤ 1. Then, we show the mechanism is IC when β ≥ 1/2. Theorem 1. A β-logarithmic mechanism is IC if β ≥ 1/2. Proof. For any graph G ∈ G, let Sinf. 1 (G) = {i1, . . . , im}. Then, we consider three different types of agents. 1. For an agent i /∈ Sinf. 1 (G), by definition, she can never pretend to be the agent with rank 1 by hiding her outedges. Hence, she will always not belong to the 1influential set and will have 0 probability to be chosen. 2. For an agent it ∈ Sinf. 1 (G) such that t < m, no matter how she hides her out-edges, it+1 will always belong to the 1-influential set because it+1 ∈ P(it) (Observation 1) and her progeny cannot be decreased. Hence, the probability of it to be chosen will not change. 3. For the agent im ∈ Sinf. 1 (G), if she hides some of her out-edges, there may happen two cases. (i) If there is no agent in P(im) occurs in the new 1-influential set, the probability of im to be chosen will remain β. (ii) If there exists at least one agent in P(im) that occurs in the new 1-influential set, let i′1 be the first agent in the new set. Let im+1 be the one with the highest rank after im in the new set. Then, the probability of im to be chosen will become (1 - β) log2(P(im)/P(im+1)) ≤ (1 - β) log2(P(i′1 )/P(im+1)) ≤ (1 - β) ≤ β by the fact of β ≥ 1/2 and Observation 2. Taking all the above together, no agent can increase her probability to be chosen by hiding her out-edges. Now we can compute the approximation ratios of IC βLMs, from which we can find that the optimal β-LM is also an optimal IC selection mechanism for k = 1. Therefore, the mechanism is (min { 12 (β + 1-β ln 2 ) , β})- optimal. It is not hard to find out that when β = 1/(1 + ln2), the value min { 12 (β + 1-β ln 2 ) , β} takes it maximum as 1/(1 + ln2), i.e., the optimal β-LM is (1/(1 + ln2))-LM, which is (1/(1 + ln2))-optimal. Recall that Zhang et al. [2021] has proved that no IC and fair 3 selection mechanism can be αoptimal with α > 1/(1 + ln2). Hence, we can infer the optimality of (1/(1 + ln 2))-LM. 3 Fairness is a quite weak property for single agent selection that only requires i∗1 has the same probability to be chosen if the 1influential set and the structure formed by P(i∗1) remain the same. It is clear to see that β-LM satisfies this fairness. Corollary 1. There is no other IC and fair selection mecha- nism for k = 1 that can have a higher approximation ratio than (1/(1 + ln 2))-LM. At the end of this section, we give a running example of (1/(1 + ln 2))-LM. Example 1. Consider the network depicted in Figure 1, where Sinf. 1 (G) = {i1, i2, i3, i4}. For the last agent i4 in the set, her selection probability xi4 is 1/(1 + ln 2) ≈ 0.59. For the agents i3, i2 and i1, their selection probabilities are xi3 = ln2 1+ ln2 log2 xi2 = ln2 1+ ln2 log2 xi1 = ln2 1+ ln2 log2 ݆ ସ݅ P (i3) P(i4) = ln2 P (i2) 1+ ln2 log2 1+ ln2 log2 P(i3) = ln2 P (i1) P(i2) = ln2 ଷ݅ 1+ ln2 log2 ଶ݅ 𝑆ଵ ୧୬୤. ሺ𝐺ሻ Figure 1: An example of the network, where the marked agents have the relationship as i1 ≻ i2 ≻ i3 ≻ i4 ≻ j. The 1-influential set is represented by a dashed border. 4 Select Two Agents We start to consider selecting up to k = 2 agents as delegates. To select agents with larger progeny, one possible approach is to find the second delegate from the 1-influential set as well. However, this limits the performance of ICmechanisms. ## 4.1 Limitation of the 1-influential Set The limitation of selecting agents from the 1-influential set for k = 2 mainly comes from the fact that there may be only a single agent in the set. Theorem 3. If an IC 2-selection mechanism only selects agents in the 1-influential set, then it cannot be α-optimal with α > 1/2. Proof. Consider a two-star graph shown in Figure 2. Suppose P(i1) = P(j) = y and i1 > j. Then the 1-influential set of this graph Sinf. 1 (G) only contains i1. Therefore, even if the mechanism can always select agent i1 with probability 1, the approximation ratio in this graph is only (1·y)/(y+y) = 1/2. Hence, if only selecting agents in the 1-influential set, an IC 2-selection mechanism cannot achieve an approximation ratio of more than 1/2. We can also show that the limitation described in Theorem 3 is tight by providing the following mechanism. ଵ݅ 54 ≈ 0.13; 65 ≈ 0.11; 76 ≈ 0.09. Figure 2: A two-star network where the hubs satisfy i1 ≻ j. Thus, the 1-influential set only contains i1. ![Image](https://ijcai.org/proceedings/2023/fulltext/327/image_000000_67a1e2f15d8759db09883d546bb6938d149a46af274ccd6de224dc747729ad32.png) ## Least Deterministic Mechanism (LDM) 1. Given a network G = (N, E), find the 1-influential set Sinf. 1 (G) = {i1, . . . , im}, where it ≻ it+1 for all 1 ≤ t < m. 2. Assign the probability of each agent to be selected as follows: Intuitively, LDM deterministically selects the last two agents in the 1-influential set or it selects the only agent in the set if |Sinf. 1 (G)| = 1. Example 2. We take the networks shown in Figure 1 and Figure 2 as running examples. In Figure 1, there are four agents, i1, i2, i3, and i4, in the 1-influential set. Hence, LDM deterministically selects the last two agents i4 and i3, i.e., xi4 = xi3 = 1. In Figure 2, there is a single agent i1 in the 1-influential set. Hence, LDM deterministically selects the agent i1 only. Now we prove that LDM is incentive-compatible and 1/2optimal as follows. Theorem 4. LDM is an IC 2-selection mechanism. Proof. For any graph G ∈ G, suppose that Sinf. 1 (G) = {i1, . . . , im}. Then we consider the following cases. 1. For an agent i /∈ Sinf. 1 (G), same as the first point in the proof of Theorem 1, she always has no chance to be chosen by hiding her out-edges. 2. Ifm≤ 2, the agents in Sinf. 1 (G) will be deterministically selected. Hence, they have no incentive to hide their outedges. 3. If m > 2, first, for agents im and im-1 who will be deterministically selected, they have no incentive to hide their out-edges. Then, for any agent it ∈ Sinf. 1 (G) with i < m- 1, no matter how she hides her out-edges, im and im-1 will always belong to the 1-influential set because {im, im-1} ⊆ P(it) (Observation 1) and their progeny cannot be decreased. Hence, the probability of it to be chosen will remain to be 0. Taking all the above together, no agent can increase her probability to be chosen by hiding her out-edges. Therefore, the mechanism is IC. Theorem 5. LDM is 1/2-optimal. Proof. For any graph G ∈ G, if |Sinf. 1 (G)| = 1, then LDM deterministically selects the agent i∗1 . Therefore, in this case, we have If |Sinf. 1 (G)| ≥ 2, then LDM deterministically selects the agent im and im-1. By Observation 2, in this case, we have Therefore, LDM is 1/2-optimal. If we consider general IC 2-selection mechanisms, we may have a higher upper bound of the approximate ratio. This suggests the limitation of only selecting agents from the 1influential set when we target up to two delegates. Theorem 6. There is no IC 2-selection mechanism that can be α-optimal with α > 23/27. Proof. Consider three networks with four agents shown in Figure 3. Applying a generic IC 2-selection mechanism on these graphs, suppose the probabilities of each agent i being chosen in the three graphs are x(a) i , x(b) i and x(c) i . Notice that network (b) can be obtained by agent 2 or 4 in network (a) hiding their out-edges (corresponding to agent 2 or 1 in network (b)), while network (c) can be obtained by agent 3 hiding her out-edge (corresponding to agent 1 or 3 in network (c)). Since the selection mechanism is IC, we have the following constraints: Moreover, the mechanism selects at most 2 agents. Hence, The approximation ratio of the mechanism must be no more than the least ratio in these three graphs, i.e., With constraints (1) - (3), we can calculate the highest value of the minimum. Therefore, we have α ≤ 23/27 and the equations holds when Figure 3: Three networks with four agents where (b) and (c) can be obtained by one of the agents in (a) hiding her out-edge. The probabilities of each agent being chosen by a generic IC 2-selection mechanism are attached beside the node. ![Image](https://ijcai.org/proceedings/2023/fulltext/327/image_000001_28fa9721e33533a7b95b4eee311a3e14d49fa8831a957469590ad25cbdf81547.png) ## 4.2 Utilizing the 2-influential Set To break through the limitation of the 1-influential set, one natural idea is to consider the 2-influential set. We first characterize the set by following observations. According to Definition 5, agents who can pretend to be the first in the ranking sequence are definitely in the 2-influential set. The agents i∗1 and i∗2 who rank first and second are also naturally in the 2-influential set. Based on the relationship between i∗1 and i∗2 , the 2-influential set will have different forms. Observation 5. For any graph G, if i∗2 ∈ P(i∗1 ), the set Sinf . 2 (G) can be written as {i1, i2, · · · , im}, where i1 = i∗1 , i2 = i∗2 , and it+1 ∈ P(it) for all t < m. Proof. When there is another agent i3, except for i∗1 and i∗2 , is in the 2-influential set, she must have the ability to decrease i∗1 or i∗2 's progeny by hiding her out-edges, i.e., at least one of i3 ∈ P(i∗1 ) and i3 ∈ P(i∗2 ) is satisfied. If i∗2 ∈ P(i∗1 ), we will show i3 must belong to P(i∗2 ) by contradiction as follows. If i3 /∈ P(i∗2 ), then she cannot decrease i∗2 's progeny by hiding her out-edges. Since i∗2 /∈ P(i3), i∗2 ∈ P(i∗1 ) is always satisfied no matter how i3 hides her out-edges. Hence, in order to rank first or second after hiding out-edges, i3 ≻ i∗2 must be satisfied, which contradicts that i∗2 is with rank 2. Therefore, i3 ∈ P(i∗2 ). Similarly, when there is another agent i4 ≺ i3 in the 2influential set, she must belong to P(i3), and this pattern extends to subsequent agents in the 2-influential set. Observation 6. For any graph G, if i∗2 /∈ P(i∗1 ), the set Sinf . 2 (G) can be written as {i1, i2, · · · , im}, where i1 = i∗1 , i2 = i∗2 , and for others, at least one of the below is true: · i3 ∈ P(i1), it+1 ∈ P(it) for all 3 ≤ t <m; · i3 ∈ P(i2), it+1 ∈ P(it) for all 3 ≤ t <m. Proof. When there is another agent i3, except for i∗1 and i∗2 , is in the 2-influential set, at least one of i3 ∈ P(i∗1 ) and i3 ∈ P(i∗2 ) is satisfied. We first assume i3 ∈ P(i∗1 ). Then, when there is an- other agent i4 ≺ i3 in the 2-influential set, we show that i4 ∈ P(i3) by contradiction as follows. If i4 /∈ P(i3), she cannot decrease i3's progeny by hiding her out-edges. Since i3 /∈ P(i4), i3 ∈ P(i∗1 ) is always satisfied no matter how i4 hides her out-edges. Hence, i4 ≻ i3 must be satisfied to make i4 be in the 2-influential set, which makes a con- tradiction. Therefore, i4 ∈ P(i3). Similarly, when there is another agent i5 ≺ i4 in the 2-influential set, she must be- long to P(i4), and this pattern extends to subsequent agents in the 2-influential set. The same results can also be obtained similarly if i3 ∈ P(i∗2 ). From the above observations, we can see that the structure of the 2-influential set is much more complex than that of the 1-influential set. Furthermore, the progeny of the last agent in the 2-influential set might be much smaller than P(i∗1 ) since P(i∗2 ) might be small. These are the main difficulties to uti- lize the 2-influential set. Extending the idea of LDM and β- LM, we propose the following mechanism. Logarithm After Least Deterministic (LALD) 1. Given a network G = (N, E), find the 1-influential set Sinf. 1 (G) and the 2-influential set Sinf. 2. If Sinf. Sinf . 2 (G) \ Sinf. 2 (G). 1 (G) = ∅, then Sinf. 1 (G) = 2 (G) = {i1, i2 . . . , im}, where it ≻ it+1 for all 1 ≤ t < m. Then, assign the probability of each agent to be selected as follows:  1, j = im 1 1+ln 2 , j = im-1 ln 2 1+ln2 log2 0, P(it+1) , j = it, t <m-1 j /∈ Sinf. 2 (G) \ Sinf. xj = 3. If Sinf. 2 (G). 2 (G) = 1 (G) ̸= ∅, suppose Sinf. {i1, . . . , im} where it ≻ it+1 for all 1 ≤ t < m. First, deterministically select the agent im, i.e., xim = 1. Then, select the second agent by applying (1/(1 + ln 2))-LM on G. P (it) Intuitively, LALD first deterministically selects the last agent in the 2-influential set. Then, it uses the same probability distribution as (1/(1 + ln 2))-LM to select another agent among the remaining agents in the 1-influential set. Example 3. We take the networks shown in Figure 1 and Fig- ure 4 as running examples. In Figure 1, suppose j < i2. Then, Sinf. 2 (G) = Sinf. 1 (G) = {i1, i2, i3, i4}. Hence, LALD first deterministically selects agent i4, i.e., xi4 = 1. For the remaining agents in Sinf. 1 (G), LALD assigns the probabilities as xi3 = 1/(1+ln 2) ≈ 0.59, xi2 = ln 2/(1 + ln 2) log2(P(i2)/P(i3)) ≈ 0.11, and xi1 = ln 2/(1 + ln 2) log2(P (i1)/P (i2)) ≈ 0.09. {i1} and Sinf. In Figure 4, suppose i2 > i3 and i4 > j. Then, Sinf. 1 (G) = 2 (G) = {i1, i2, i3, i4}. Hence, LALD first deter- ministically selects agent i4, i.e., xi4 = 1. LALD then runs (1/(1 + ln2))-LM, which assigns the probabilities among Sinf . 1 (G). Here, it assigns that xi1 = 1/(1+ ln2) ≈ 0.59. Figure 4: An example of the network, where the marked agents have the relationship as i1 ≻ i2 ≻ i3 ≻ i4 ≻ j. The 1-influential set and the 2-influential set are represented by dashed borders. ![Image](https://ijcai.org/proceedings/2023/fulltext/327/image_000002_af4d249c6a507fd6926911c3f5e31d2521c62854c8a3b54c98133655fe2a8166.png) ## Theorem 7. LALD is an IC 2-selection mechanism. Proof. For any graph G ∈ G, We consider three different types of agents. 1. For an agent i /∈ Sinf. 2 (G), by definition, she can never be in the set by hiding her out-edges. Hence, she will always have 0 probability to be chosen. 2. For an agent i ∈ Sinf. 2 (G) \ Sinf. 1 (G) when Sinf. 2 (G) \ Sinf . 1 (G) ̸= ∅, there are two cases. (i) If i is the last agent in the 2-influential set, her probability to be chosen is 1. Hence, she has no incentive to manipulate. (ii) If i is not the last agent, no matter how she hides her outedges, both the last agent and herself are still in the set Sinf . 2 (G) \ Sinf. 1 (G). Hence, her probability to be chosen remains 0. 3. For an agent i ∈ Sinf. 1 (G), suppose Sinf. 1 (G) = {i1, . . . , iq} with it ≻ it+1 for all 1 ≤ t < q. There are three cases. (i) If i is the last agent iq in the 1influential set, she has no incentive to manipulate when Sinf . 2 (G) \ Sinf. 1 (G) = ∅ since xi = 1. When Sinf. 2 (G) \ Sinf . 1 (G) ̸= ∅, no matter how i hides her out-edges, agents in the set Sinf. 2 (G) \Sinf. 1 (G) will still be in the 2influential set (even may be in the 1-influential set). After i hides some out-edges, if Sinf. 2 (G′ ) \ Sinf. 1 (G′ ) ̸= ∅, then i cannot have higher probability by Theorem 1; if Sinf. 2 (G′ ) \ Sinf. 1 (G′ ) = ∅, then i can have at most 1/(1 + ln2) probability since she will no longer be the last agent in Sinf. 1 (G′ ), which equals to her original probability. (ii) If i = iq-1, she has no incentive to manipulate when Sinf. 2 (G) \ Sinf. 1 (G) = ∅. It is because iq will always be in the 1-influential set no matter how i hides her out-edges, which makes increasing her probability to be chosen impossible. When Sinf. 2 (G) \Sinf. 1 (G) ̸= ∅, it is almost the same condition as that for i = iq. Hence, she cannot increase her probability by manipulation, either. (iii) If i = it with t < q - 1, no matter how she hides her out-edges, iq and iq-1 are always in the 1-influential set. Hence, i's probability to be chosen will not change. Taking all the above together, we can conclude that the mechanism is IC. Theorem 8. LALD is 3+ln2 4(1+ln 2) -optimal. Proof. Suppose Sinf. 2 (G) = {i1, i2, · · · , im} for any graph G ∈ G,. There are two different cases that need consideration. 1. If Sinf. 2 (G) \ Sinf. 1 (G) = ∅, then according to Observation 1 and Theorem 2, we have 2. If Sinf. 2 (G) \Sinf. 1 (G) ̸= ∅, we first consider the progeny P(im). When i∗2 ∈ P(i∗1 ), the structure of the 2influential set is characterized by Observation 5. Then after deleting im's out-edges, i1 ≻ i2 holds. Hence, P(im) ≥ P(i2) - P(im) which implies 2P(im) ≥ P(i2). When i∗2 /∈ P(i∗1 ), the structure of the 2influential set is characterized by Observation 6. Hence, at least one of 2P(im) ≥ P(i1) and 2P(im) ≥ P(i2) is satisfied, which all imply that 2P(im) ≥ P(i2). Therefore, let P(i2)/P(i1) = ρ and we have Therefore, we can conclude that the mechanism is 3+ln2 4(1+ln 2) - optimal. ## 5 Discussion In this paper, we investigate the incentive-compatible selection mechanisms for one or two influentials, where an agent's influential power is defined by her progeny. The goal is to select agents with progeny as large as possible and to prevent them from hiding their out-edges at the same time. Based on the idea of assigning possibilities of being selected to those agents who can pretend to be the one with the largest or second largest progeny, we first propose the 1/(1 + ln2)-LM mechanism for selecting one agent, which is optimal among all IC and fair single-agent selections. We then propose the LALD mechanism for selecting up to two influentials, which has an approximation ratio of (3 + ln 2)/(4(1 + ln 2)) (≈ 0.54). To the best of our knowledge, this is the first work to select more than one agent for progeny maximization. There are several interesting future directions worth investigating, and we provide some brief discussions here. One direction is to narrow the gap between the current lower bound (given by our proposed mechanism) and the current upper bound (23/27 as we proved) of the approximation ratio for an optimal IC 2-selection mechanism. For the side of upper bounds, notice that our provided upper bound does not require additional properties like fairness defined in [Zhang et al., 2021]. This is because the fairness for selecting a single agent does not apply in selecting multiple agents (e.g., in LALD, the probability of choosing i∗1 may be also related to the structure of the 2-influential set). If we extend the definition of fairness to k-fairness like Definition 6 (sketch). i∗1 (or also with i∗2 to i∗k ) has the same probability to be chosen when the k-influential set and the structure formed by P(i∗1 ) (or also with P(i∗2 ) to P(i∗k )) remain the same. Then, we can observe that k-fairness will become weaker when k becomes larger. Zhang et al. [2021] conjectured that dropping (1-)fairness will not affect the upper bound they characterized. If it can be proven to be true, then we can also draw a corollary that introducing k-fairness will not affect the upper bounds of approximation ratios for IC k-selection mechanisms. For the side of improving lower bounds, one may consider to utilize more agents in the 2-influential set but not in the 1-influential set. The main difficulty here is these agents may have too small progeny when P (i∗2 ) ≪ P (i∗1 ). The other direction is to extend the mechanisms for selecting more agents (k ≥ 3). Similar to the case of selecting two agents, only selecting agents in the k′ -influential set with k′ < k may limit the performance. A natural idea is to select k agents in the k-influential set. The main difficulty here is that the structure of the k-influential set will become more and more complex when k becomes larger. Intuitively, the structure of the k-influential set depends on the relationships among agents i∗1 , . . . , i∗k . The number of different cases of the structure will grow exponentially with k, which is roughly 2O(n2 ) . A possible way to handle this challenge may be recursively considering the influential set with lower k. Finally, in terms of other applications, such as recruiting agents to promote some advertisements, designing selection mechanisms to maximize the expected cardinality of the union of progeny is also a promising future direction. ## Acknowledgements This work is supported by Science and Technology Commission of Shanghai Municipality (No. 22ZR1442200 and No. 23010503000), and Shanghai Frontiers Science Center of Human-centered Artificial Intelligence (ShangHAI). ## References 1. [Alon et al., 2011] Noga Alon, Felix Fischer, Ariel Procac- cia, and Moshe Tennenholtz. Sum of us: Strategyproof se- lection from the selectors. In Proceedings of the 13th Con- ference on Theoretical Aspects of Rationality and Knowl- edge, pages 101-110, 2011. 2. [Babichenko et al., 2018] Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. Incentive-compatible diffusion. In Proceedings of the 2018 World Wide Web Conference, pages 1379-1388, 2018. 3. [Babichenko et al., 2020a] Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. Incentive-compatible classifica- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7055-7062, 2020. 4. [Babichenko et al., 2020b] Yakov Babichenko, Oren Dean, and Moshe Tennenholtz. Incentive-compatible selection mechanisms for forests. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 111- 131, 2020. 5. [Bjelde et al., 2017] Antje Bjelde, Felix Fischer, and Max Klimm. Impartial selection and the power of up to two choices. ACM Transactions on Economics and Computa- tion (TEAC), 5(4):1-20, 2017. 6. [Bousquet et al., 2014] Nicolas Bousquet, Sergey Norin, and Adrian Vetta. A near-optimal mechanism for impartial se- lection. In International Conference on Web and Internet Economics, pages 133-146. Springer, 2014. 7. [Caragiannis et al., 2021] Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas. Impartial selection with prior information. arXiv preprint arXiv:2102.09002, 2021. 8. [Caragiannis et al., 2022] Ioannis Caragiannis, George Christodoulou, and Nicos Protopapas. Impartial selection with additive approximation guarantees. Theory of Computing Systems, pages 1-22, 2022. 9. [Cembrano et al., 2022] Javier Cembrano, Felix A. Fischer, David Hannon, and Max Klimm. Impartial selection with additive guarantees via iterated deletion. In EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 -15, 2022, pages 1104-1105. ACM, 2022. 10. [Fischer and Klimm, 2014] Felix Fischer and Max Klimm. Optimal impartial selection. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 803-820, 2014. 11. [Ghalme et al., 2018] Ganesh Ghalme, Sujit Gujar, Amlesh- war Kumar, Shweta Jain, and Y Narahari. Design of coali- tion resistant credit score functions for online discussion forums. In Proceedings of the 17th International Con- ference on Autonomous Agents and MultiAgent Systems, pages 95-103, 2018. 12. [Holzman and Moulin, 2013] Ron Holzman and Hervé Moulin. Impartial nominations for a prize. Econometrica, 81(1):173-196, 2013. 13. [Kahng et al., 2018] Anson Kahng, Yasmine Kotturi, Chin- may Kulkarni, David Kurokawa, and Ariel Procaccia. Ranking wily people who rank each other. In Proceed- ings of the AAAI Conference on Artificial Intelligence, vol- ume 32, 2018. 14. [Kotturi et al., 2020] Yasmine Kotturi, Anson Kahng, Ariel Procaccia, and Chinmay Kulkarni. Hirepeer: Impartial peer-assessed hiring at scale in expert crowdsourcing mar- kets. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2577-2584, 2020. 15. [Kurokawa et al., 2015] David Kurokawa, Omer Lev, Jamie Morgenstern, and Ariel D Procaccia. Impartial peer re- view. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015. 16. [Mackenzie, 2015] Andrew Mackenzie. Symmetry and im- partial lotteries. Games and Economic Behavior, 94:15- 28, 2015. 17. [Mattei et al., 2020] Nicholas Mattei, Paolo Turrini, and Stanislav Zhydkov. Peernomination: Relaxing exactness for increased accuracy in peer selection. In Proceedings of the Twenty-Ninth International Joint Conference on Ar- tificial Intelligence, IJCAI 2020, pages 393-399. ijcai.org, 2020. 18. [Olckers and Walsh, 2022] Matthew Olckers and Toby Walsh. Manipulation and peer mechanisms: A survey. arXiv preprint arXiv:2210.01984, 2022. 19. [Page et al., 1999] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stan- ford InfoLab, 1999. 20. [Wang et al., 2018] Yufeng Wang, Hui Fang, Chonghu Cheng, and Qun Jin. Tsp: Truthful grading-based strat- egyproof peer selection for moocs. In 2018 IEEE Interna- tional Conference on Teaching, Assessment, and Learning for Engineering (TALE), pages 679-684. IEEE, 2018. 21. [Zhang et al., 2021] Xiuzhen Zhang, Yao Zhang, and Dengji Zhao. Incentive compatible mechanism for influential agent selection. In International Symposium on Algorith- mic Game Theory, pages 79-93. Springer, 2021.