Incentive-Compatible Selection for One or Two Influentials

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.

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

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.

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

1. 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).