Keywords: Peer selection, Network, Mechanism design without money, Dominant strategy incentive compatibility,

Declarations of interest: none

JEL: D82, D86

1 Introduction↩︎

We consider a selection problem where the planner has to select one individual out of a group of \(n\) individuals on the basis of a binary characteristic. For instance, an agent could be either ‘’needy" or’‘not needy",’‘high" or’‘low" ability,’‘deserving" or’’not deserving". Depending on the context, the chosen agent will then be given a cash grant, or promotion or job offer. To fix ideas, we will henceforth denote the binary characteristic to be one of being needy or not needy. Moreover, the agent selected by the planner will be given a cash grant.

A mechanism design problem arises because the planner does not observe the neediness status of any agent. However, all agents know each others’ neediness status. This is of course also true in the classical peer selection problem discussed originally by Alon et al [1] and Holzman and Moulin [2]. However, our framework, while related, differs in important ways from the Alon-Holzman-Moulin classical framework.

The planner’s problem in our setting is considerably more complicated because all pairs of agents are also related to each other by bilateral relations of friendship and enmity. That is, each pair \(i, j\) are either friends, enemies or impartial. These relationships give rise to networks of friends, enemies or impartials. These bilateral relationships influence preferences. Each agent strictly prefers being selected. If not selected herself, then she would like a friend to be selected regardless of the friend’s binary characteristic. Moreover, she strictly prefers that no enemy be selected, again irrespective of the enemy’s neediness status. Obviously, any incentive compatible (probabilistic) peer selection mechanism must ensure that no agent is able to influence his or her own probability of being selected. In our setting, incentive compatibility imposes an additional requirement – agents cannot influence the probability of their friends and enemies from being selected.

We focus on the possibility of constructing probabilistic mechanisms under which (i) revealing truthful information will be a weakly dominant strategy for each agent, and (ii) the support of the probability distribution corresponding to truthful reports will be contained in the set of needy agents when the latter set is nonempty.⁵ In contrast, the classical Holzman-Moulin-Alon framework focussed on deterministic mechanisms. We consider two informational scenarios. In the first, the planner knows either the friendship, enemy or impartial relationships of every agent. We derive different sufficient conditions which allow the planner to construct three probabilistic mechanisms satisfying the two requirements.⁶ We have not been able to show whether these sufficient conditions characterise the class of all mechanisms satisfying the two requirements.

We then go onto consider the case when the planner does not know the bilateral relationships of friends and enemies. We first show that in this setting, there is no incentive compatible mechanism that is efficient in the sense of ensuring that some needy agent is picked whenever there is at least one needy agent. Although there are differences between our framework and the probabilistic framework of Gibbard [3], we show that adaptations of both random dictatorships and duples are DSIC mechanisms. We compare these two mechanisms in terms of their relative efficiency. We show that if every individual has at least two friends, then the random dictatorship is at least as efficient as the duple mechanism. Otherwise, under plausible conditions on the bilateral relationships, the duple mechanism is better than the random dictatorship on a worst-case basis. Both mechanisms are better than the constant mechanism that picks an agent at random.

Finally, we consider networks which satisfy structural balance – for which the enemy of an enemy is a friend, and the friend of an enemy an enemy.⁷ When structural balance is satisfied we are able to provide a necessary and sufficient condition for existence of an efficient, dominant strategy incentive compatible mechanism. We also compute a lower bound on efficiency of the duples mechanism when the planner does not know the network.

2 Related Literature↩︎

Our paper relates to several strands of the literature. It is most closely related to the large literature in economics and computer science on peer selection mechanisms. Holzman and Moulin [2] provide an axiomatic analysis of deterministic “impartial” or dominant strategy incentive compatible voting rules when individuals nominate a single individual for office. Alon et al. [1] consider the problem of designing a dominant strategy mechanism to select \(k\) individuals from a group of peers. They show that no deterministic efficient dominant strategy mechanism exists, and then go on to construct approximately efficient, stochastic, dominant strategy mechanisms.⁸

The peer selection problem has also been studied in the context of social networks, where the social network is a network of observation, describing who can observe whom in the network. Bloch and Olckers [16] characterize network structures for which efficient, ex post incentive compatible mechanisms exist. ⁹

Faced with the impossibility of constructing an efficient, dominant strategy mechanism, Ben Porath, Dekel and Lipman [18] propose to add another instrument for the planner, and allow her to check the report of the agents at a cost. Mylonanov and Zapechelnuyk [19] analyze the problem when verification can only happen ex post, after the object has been allocated. Kattwinkel [20], Pereyra and Silva [21] and Bloch, Dutta and Dziubiński [22] analyze situations where, in addition to the agent’s reports, the planner can use a correlated signal on the agents’ types, and show how the planner can leverage this correlation to construct efficient Bayesian incentive compatible mechanisms.

The entire literature on peer selection assumes that players only care about being selected, and that there are no externalities in players’ utilities. Our paper thus departs from the existing literature since players also care about who is selected if they themselves are not. This is related to the biased juror problem where jurors may deviate from the true ranking of candidates since they may be biased for or against specific candidates. The biased jury problem was initiated by Amorós et al. [23] and Amorós [24] in a series of very interesting papers.¹⁰ A significant difference between the biased jury and peer selection literature is that in the former, the selectors (the jury) are not themselves candidates. Another difference between our paper and the papers mentioned here is that they focus on deterministic mechanisms and\(\backslash\)or different solution concepts such as Nash equilibrium or subgame perfection.

3 The Model↩︎

There is a set \(V = \{1,\ldots,n\}\) of agents. Nature selects an agent to be needy with probability \(q >0\). Let \(N\) denote the realized set of needy agents.

Any pair \(i, j \in V\times V\) are either friends, enemies or impartials. Of course, these are symmetric relationships. For any \(i \in V\), \(F_i\), \(E_i\), \(I_i\) are the set of friends, enemies and impartials of \(i\). So, \(\{F_i, E_i, I_i\}\) form a partition of \(V\setminus \{i\}\).

We assume that every agent in \(V\) knows the set \(N\) of needy agents as well as her own set of friends, enemies and impartials. We are agnostic about whether \(i\) knows anything else about the networks of friends, enemies and impartials. We can then represent the type of any agent as a triple \(\theta_i= (N, F_i, E_i)\). Notice that we can ignore \(I_i\) since \(I_i\equiv V \setminus (\{i\} \cup F_i\cup E_i)\). Let \(\Theta_i\) represent the set of all possible types of agent \(i\).

The planner does not know the set \(N\). We consider two alternative informational scenarios. In one scenario, the planner knows either the sets \(I_i\) or \(F_i\) or \(E_i\) of each agent. In the other informational scenario, the planner knows nothing about these sets. In either case, the planner wants to use a mechanism that will induce agents to report the set \(N\) truthfully.

Mechanism

We are interested in direct mechanisms where each agent reports her type. So, a typical message profile, to be denoted by \(\boldsymbol{m}\) will be an element of \(\boldsymbol{\Theta} = \prod_{i \in V} \Theta_i\). A (direct) mechanism is defined by an outcome function \(g : \boldsymbol{\Theta} \rightarrow [0,1]^V\), with \(g_i(\boldsymbol{m} )\) representing the probability of agent \(i\) being chosen. The mechanism is valid if for all message profiles \(\boldsymbol{m}\), \[\sum_{i \in V} g_i(\boldsymbol{m}) \le 1.\] Notice that this keeps open the possibility that the planner may not choose any agent at some message profiles.

Throughout, the rest of the paper we restrict attention to valid mechanisms.

Preferences

Let \(p=(p_1, \ldots, p_n)\) and \(p'=(p'_1, \ldots, p'_n)\) be two vectors where \(p_i, p_j\), \(p'_i,p'_j\) etc. are probabilities with which \(i\) and \(j\) are chosen corresponding to different message profiles.

Agents have lexicographic preferences over such probability vectors. First, \(i\) checks her own probability of being chosen. She strictly prefers \(p\) to \(p'\) if \(p_i >p'_i\).

Second, she prefers her friends being chosen and dislikes her enemies being chosen. She assigns weights \(w_f >0, w_e>0\) and ranks vectors \(p\) and \(p'\) so that \[p\succ_i p'if\begin{cases} p_i >p'_i \\ p_i=p'_iand\sum_{j \in F_i} w_f ( p_j -p'_j) - \sum_{j \in E_i} w_e ( p_j -p'_j) >0\end{cases}\]

It is clear that in our setting, preferences do not depend upon the set \(N\). So, for instance, each individual \(i\) is indifferent between whether friend \(j\) or friend \(k\) is selected, regardless of the neediness status of \(j\) and \(k\).

A mechanism \(g\) is dominant strategy incentive compatible (DSIC) if and only if, for all \(i \in V\), all \(\boldsymbol{m} \in \boldsymbol{\Theta}\) and all \(m'_i \in \Theta_i\), \[p \succsim_i p',wherep= g(\boldsymbol{m}), p'= g(m'_i,\boldsymbol{m}_{-i}).\] That is, revealing the true state must be a dominant strategy for \(i\) at all states.

The planner also wants to be able to pick a needy agent whenever the set of needy agents is non-empty. This gives rise to the next definition.

A mechanism \(g\) is efficient if and only if, for any state of the world, \(\theta\) with truthful message profile \(\boldsymbol{m} \in \boldsymbol{\Theta}\) , if \(N \ne \varnothing\), then \(\sum_{i \in N } g_i(\boldsymbol{m})=1\).

4 Known Relationships Networks↩︎

In this section, we assume that the planner knows either the network of impartials or the network of enemies or the network of friends. In each case, we derive sufficient conditions under which the planner can construct DSIC mechanisms that are also efficient.

Since the planner is assumed to know the relevant networks, all the mechanisms considered in this section ignore reports about the sets \(I_i, E_i, F_i\), and only use the reports on the neediness status of others. So, in order to simplify the notation, we will identify message \(m_i\) sent by an agent \(i\) with the set of needy agents reported by \(i\). In particular, \(j\in m_i\) means that \(i\) reports that \(j\) is needy and \(j \notin m_i\) means that \(j\) is not needy according to \(i\).

4.1 Planner knows the sets \(I_i\) of each \(i\)↩︎

The mechanism we construct exploits the fact that impartials do not have an incentive to lie about the neediness status of their impartial neighbours provided their reports do not affect their own probability of being chosen.

Given a message profile \(\boldsymbol{m}\) and any pair of agents \(i, j \in V\), the message \(m_j\) is called a positive vote of \(j\) on \(i\) if \(i \in m_j\), while it is called a negative vote if \(i\notin m_j\). In addition, given a message profile \(\boldsymbol{m}\) and a set of agents \(X \subseteq V\), \(\boldsymbol{m}_{X} = \{m_j\}_{j \in X}\) is the message profile \(\boldsymbol{m}\) restricted to agents in \(X\). In the case of \(X = V\), we simply write \(\boldsymbol{m}\) instead of \(\boldsymbol{m}_V\) and in the case of \(X = V\setminus \{i\}\) we write \(\boldsymbol{m}_{-i}\) instead of \(\boldsymbol{m}_{V\setminus \{i\}}\).

Given a message profile \(\boldsymbol{m}\), let \(pos(\boldsymbol{m}_X)\) be the set of agents \(j\in V\) receiving positive votes from all their impartial agents in \(X\), i.e. from all agents in \(X\cap I_j\).

We construct the following mechanism \(g^1\). The probability of agent \(i\in V\) being selected under message profile \(\boldsymbol{m}\) is \[g^1_i(\boldsymbol{m}) = \begin{cases} \frac{1}{|pos(\boldsymbol{m}_{I_i})|}, & \textrm{if i \in pos(\boldsymbol{m}_{I_i}),}\\ 0, & \textrm{otherwise.} \end{cases}\]

So, for each agent \(i \in V\), the mechanism first checks whether the agent receives positive votes from all her impartial agents. If \(i\) passes this test, then the mechanism assigns \(i\) the probability that is the reciprocal of the number of all the agents, \(j \in V\) who received positive votes from the agents that are impartial to both \(i\) and \(j\), i.e. all the agents in \(I_i \cap I_j\). If \(i\) receives even one negative vote from some \(j \in I_i\), then \(g^1\) assigns zero probability to \(i\).

The following condition will play an important role.

The Intersection Condition I: For all \(i,j \in V\), \(I_i \cap I_j \neq \varnothing\).

The next result describes the properties of \(g^1\).

4.2 The planner knows the sets \(E_i\) for all agents \(i \in V\)↩︎

Suppose now that the planner knows the enemy network, that is the sets \(E_i\) for all agents \(i\). We will construct another DSIC mechanism that will use reports of enemies, and that will, under an Intersection Condition which is similar to the earlier condition, be also efficient. At this stage, it is worth emphasizing the similarities and differences between a DSIC mechanism based on messages from impartials and one based on reports from enemies. A common implication of DSIC mechanisms is that no agent \(i\) can unilaterally change her own probability of being selected. As exhibited by \(g^1\), this is essentially the only condition that is imposed by DSIC if the mechanism uses only messages from agents on the neediness status of their impartials. However, a DSIC mechanism that uses messages from enemies must satisfy an additional requirement – no agent \(i\) should be able to gain by declaring an enemy to be not needy if she is actually needy. Since agent \(i\) would like to declare that enemy \(j\) is not needy, the mechanism must ensure that the total probability of agent \(i\)’s enemies being selected does not depend upon agent \(i\)’s report.

The mechanism we construct possesses this feature because it uses a distinguished agent as a “sink”. In particular, there must be a special agent \(k\) such that the enemies of \(k\), the set \(E_k\), can act as a set of selectors. The set of selectors must have the property that for any pair of agents \(i, j \in V\setminus \{k\}\), there is an agent \(l \in E_k\) who is a common enemy of \(i, j\). Since both \(i\) and \(j\) are enemies of \(l\), agent \(l\) has no incentive to discriminate between the pair. Moreover, \(l\) also does not gain by declaring that \(i\) or \(j\) is not a needy agent if they actually are needy precisely because \(k\) acts as a sink and \(l\) is also an enemy of \(k\). Notice that since this new intersection condition (that \(l \in E_i\cap E_j\)) must also apply to pairs of agents in \(E_k\), \(E_k\) must contain at least three agents.

We describe formal details below.

Given a message profile \(\boldsymbol{m}\), let \(\mathit{posE}(\boldsymbol{m}_X)\) be the set of agents, \(j\in V\), receiving positive votes from all their enemies in \(X\), i.e. from all agents in \(X\cap E_j\).

For any distinguished agent \(k \in V\), the mechanism \(g^{2,k}\) is defined as follows.

The probability of agent \(i\in V\setminus\{k\}\) being selected under message profile \(\boldsymbol{m}\) is \[g^{2,k}_i(\boldsymbol{m}) = \begin{cases} \frac{1}{|\mathit{posE}(\boldsymbol{m}_{E_i \cap E_k})\setminus \{k\}|}, & \textrm{if i \in \mathit{posE}(\boldsymbol{m}_{E_k}),}\\ 0, & \textrm{otherwise.} \end{cases}\] The probability of agent \(k\) being selected is \[g^{2,k}_k(\boldsymbol{m}) = 1 - \sum_{i \in V\setminus \{k\}} g^{2,k}_i(\boldsymbol{m}).\] So, for each agent \(i \in V\setminus\{k\}\) the mechanism checks whether the agent receives positive votes from all her enemies who are also enemies of \(k\), i.e. from all agents in \(E_i\cap E_k\), and if so, it assigns \(i\) the probability equal to \(1\) over the number of all the agents, \(j \in V\setminus \{k\}\) who received positive votes from all their enemies who are also enemies of \(i\) and \(k\), i.e. all the agents in \(E_j \cap E_i \cap E_k\). If \(i\) receives a negative vote from at least one of her enemies who is also an enemy of \(k\), then the probability assigned to \(i\) is \(0\). Agent \(k\) is selected whenever no other agent is selected, i.e. \(k\) is selected with probability equal to \(1\) minus the probability of selecting one of the agents in \(V\setminus \{k\}\).

Intersection Condition E(k): For all \(i, j \in V\setminus\{k\}\), \(E_i \cap E_j \cap E_k \neq \varnothing\).

The following result states validity, efficiency and DSIC of \(g^{2,k}\) when the Intersection Condition E(k) is satisfied.

4.3 The planner knows the sets \(F_i\) for all agents \(i \in V\)↩︎

Suppose instead that the planner knows the sets \(F_i\) of each agent. It is not difficult to see that a DSIC mechanism using messages only of friends analogous to \(g^{2,k}\) can be defined with a pre-specified agent \(k\) acting as a sink.

Given a message profile \(\boldsymbol{m}\), let \(\mathit{posF}(\boldsymbol{m}_X)\) be the set of agents, \(j\in V\), receiving positive votes from all their friends in \(X\), i.e. from all agents in \(X\cap F_j\). Let mechanism \(g^{3,k}\) be defined as follows. The probability of agent \(i\in V\setminus\{k\}\) being selected under message profile \(\boldsymbol{m}\) is \[g^{3,k}_i(\boldsymbol{m}) = \begin{cases} \frac{1}{|\mathit{posF}(\boldsymbol{m}_{F_i \cap F_j})\setminus \{k\}|}, & \textrm{if i \in \mathit{posF}(\boldsymbol{m}_{F_k}),}\\ 0, & \textrm{otherwise.} \end{cases}\] The probability of agent \(k\) being selected is \[g^{3,k}_k(\boldsymbol{m}) = 1 - \sum_{i \in V\setminus \{k\}} g^{3,k}_i(\boldsymbol{m}).\]

Intersection Condition F(k): For all \(i, j \in V\setminus\{k\}\), \(F_i \cap F_j \cap F_k \neq \varnothing\).

The proof is omitted since it is virtually identical to that of Theorem 2.

5 Unknown Relationships Networks↩︎

In the last section, we showed that the planner can construct efficient and DSIC mechanisms for classes of networks satisfying appropriate sufficient conditions provided the planner knows the networks. Notice that the construction of these mechanisms exploits the finer details of the networks. For instance, when the network satisfies the Intersection Condition I, the mechanism used in the proof of Theorem 1 depends only on the network of impartials. This raises the question of whether the planner can construct efficient DSIC mechanisms when she does not know the networks of impartials, enemies and friends. Notice that in this case, the planner has to construct one mechanism that is DSIC and efficient for  all  networks. In the theorem below, we show that this cannot be done. Since we want to focus on the role played by incomplete information about the network, the proof below will only use networks that satisfy the Intersection Condition I. This will highlight the fact that the impossibility result is precipitated by the lack of information about the bilateral relationships.

In view of Theorem 4, the search must be for ’’second-best" mechanisms. Of course, the constant mechanism where each agent is picked with equal probability is DSIC. The constant mechanism picks a needy agent with probability \(q\).

Can one improve on the constant mechanism? We take a step in this direction by constructing two DSIC mechanisms and comparing their relative efficiency. The mechanisms we construct are adaptations of the two canonical DSIC mechanisms – the random dictatorship and duples mechanisms – in the literature on probabilistic social choice starting from Gibbard [3].

We point out the differences between our framework and that of Gibbard [3] before we formally describe the two mechanisms.

In our framework, voters and alternatives coincide, and it is commonly known that every agent \(i\)’s most preferred outcome is \(i\) herself. Hence, the unmodified random dictatorship where each agent is picked at random and that agent’s most preferred outcome is chosen is nothing but the constant mechanism itself. Moreover, there is some correlation in individual preference since the bilateral relationships of friendship, impartiality and enmity are symmetric.¹² Perhaps the most important difference between the two frameworks is that preference orderings are not strict in our framework unlike the Gibbardian framework. Finally, our entirely different notion of efficiency is based on the external characteristic of neediness and is quite independent of individual preferences.

We now define the two DSIC mechanisms. Both are direct mechanisms and so each agent reports a type \(m_i= ( F_i, I_i, E_i, N)\) or simply one of the two sets of relationships since the latter follows as a residue. Given a message profile \(\boldsymbol{m}\) and an agent \(j\), let \(E_j(\boldsymbol{m})\), \(F_j(\boldsymbol{m})\), and \(I_j(\boldsymbol{m})\) be sets of enemies, friends, and impartial agents of agent \(j\), and \(N_j(\boldsymbol{m})\) be set of needy agents reported by \(j\).

Formally, let \(g^{\mathbf{R}}\) be the random dictatorship mechanism defined as follows

\[g^{\mathrm{R}}_{i}(\boldsymbol{m}) = \frac{1}{n} \sum_{j \in V\setminus \{i\}} g^{\mathrm{R}}_{i \mid j} (\boldsymbol{m}),\] where \[g^{\mathrm{R}}_{i\mid j}(\boldsymbol{m}) = \begin{cases} \frac{1}{|F_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m})|}, & \textrm{if i \in F_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m}),}\\ \frac{1}{|F_j(\boldsymbol{m})|}, & \textrm{if i \in F_j(\boldsymbol{m}) and F_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m}) = \varnothing,}\\ \frac{1}{|I_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m})|}, & \textrm{if i \in I_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m}) and F_j(\boldsymbol{m}) = \varnothing,}\\ \frac{1}{|I_j(\boldsymbol{m})|}, & \textrm{if i \in I_j(\boldsymbol{m}) and F_j(\boldsymbol{m}) \cup (I_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m})) = \varnothing,}\\ \frac{1}{|E_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m})|}, & \textrm{if i \in E_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m}) and F_j(\boldsymbol{m}) \cup I_j(\boldsymbol{m}) = \varnothing,}\\ \frac{1}{|E_j(\boldsymbol{m})|}, & \textrm{if i \in E_j(\boldsymbol{m}) and F_j(\boldsymbol{m}) \cup I_j(\boldsymbol{m}) \cup (E_j(\boldsymbol{m}) \cap {N}_j(\boldsymbol{m})) = \varnothing,}\\ 0, & \textrm{otherwise.} \end{cases}\]

As is standard, the random mechanism picks each agent with probability \(1/n\),¹³ and allowing that agent to specify her set of second best outcomes. So, if \(i\) has a needy friend, then she gets to pick such friends with equal probability. If no friend is needy, then she gets to choose her friends with equal probability even if they are not needy. If \(i\) has no friends, then she chooses needy impartial agents if such agents exist. If not, then she chooses impartial agents with equal probability. Finally, if \(i\) has only enemies, then she chooses the needy enemies, and so on. Notice that the sequence in which \(i\) is allowed to choose matters. For instance, if she is asked to choose initially from her set of enemies, then she will declare a friend to be an enemy and choose her.

Next, we define the duples mechanism. For any \(m_i\), define a hierarchy of sets \(H(m_i) =\{ S^1(m_i), S^2(m_i), S^3(m_i), S^4(m_i), S^5(m_i), S^6(m_i)\}\) such that

• \(S^1(m_i) = F_i \cap N\)

• \(S^2(m_i) = F_i \setminus N\)

• \(S^3(m_i) = I_i \cap N\)

• \(S^4(m_i) = I_i \setminus N\)

• \(S^5(m_i) = E_i \cap N\)

• \(S^6(m_i) = E_i \setminus N.\)

For any pair of agents, \(j,k \in V\setminus\{i\}\). \[ Agent i votes for j against k ifj\in S^a(m_i), k \in S^b(m_i), a<b\] Agent \(i\) abstains from voting over the pair \(\{j,k\}\) if \(j\) and \(k\) both belong to \(S^a(m_i)\) for some \(a\).

Let \(x_{jk}(\boldsymbol{m})\) be the number of votes cast for \(j\), and \(x_{kj}(\boldsymbol{m})\) be the number of votes cast for \(k\) in the vote over the pair\(\{j,k\}\) at report profile \(\boldsymbol{m}\). Then,

\[g_j^D({\{j,k\}, \boldsymbol{m}) =\begin{cases} 1, &ifx_{jk}(\boldsymbol{m}) > x_{kj}(\boldsymbol{m}),\\ 1/2, & ifx_{jk}(\boldsymbol{m}) = x_{kj}(\boldsymbol{m}),\\ 0, &ifx_{jk}(\boldsymbol{m}) < x_{kj}(\boldsymbol{m}), \end{cases}}\] And, \[g_k^D(\{j,k\},\boldsymbol{m}) =1- g_j^D(\{j,k\}, (\boldsymbol{m}).\] Then, the duples mechanism, \(g^D\) is \[g_i^D(\boldsymbol{m}) = \frac{2}{n(n-1)} \sum_{j \in V\setminus\{i\}} g_i^D(\{i,j\}, \boldsymbol{m}).\]

The following proposition is stated without proof.

We now evaluate the relative efficiency of the random dictator and duple mechanisms.

Fix the networks of friends, enemies and impartials and denote the overall network by \(G\). Consider any agent \(j\) in the network with \(f >0\) friends. Suppose \(j\) is the random dictator. Then, the probability that none of her friends is needy is \((1-q)^f\). So, when \(f>0\), agent \(j\) selects a needy individual with probability \(1- (1-q)^f\). When agent \(j\) has no friends, she selects a needy agent with probability \(1-(1-q)^i\) when \(i>0\) is the number of her impartials. Finally, if agent \(j\) has only enemies, she selects a needy agent with probability \(1-(1-q)^{n-1}\).

So, letting \(m^G_{f,i}\) be the number of nodes with \(f\) friends and \(i\) impartials in the given network \(G\), the probability of choosing a needy agent in \(G\) by the random dictator mechanism is: \[\begin{align} \label{rd} P_{RD}(G) = & \frac{1}{n} \Bigg( m^{G}_{0,0} \left(1 - (1-q)^{n-1}\right) + {} \nonumber\\ & \sum_{i = 1}^{n-1} m^{G}_{0,i} \left(1 - (1 - q)^{i}\right) + {} \nonumber\\ & \sum_{f = 1}^{n-1} \sum_{i = 0}^{n - f - 1} m^{G}_{f,i} \left(1 - (1-q)^f\right)\Bigg). \end{align}\tag{6}\] Hence the probability of choosing a needy agent by the random dictator mechanism, on any network \(G\), is greater or equal to \(q\). The following proposition describes the obvious implications of Equation 6 .

We now consider the duples mechanism. Since the duples mechanism is the average of mechanisms each of whom has a range of two alternatives, the maximum probability with which the duples mechanism chooses a needy agent is \(1-(1-q)^2\). So, on networks where all agents have two or more friends, or no friends but two or more impartials, or where the enemy network is a complete graph on \(V\), the random dictatorship will be relatively more efficient than the duples mechanism.

It is also interesting to compare the two mechanisms in terms of a worst-case scenario. From Proposition 2, we know that the lowest probability with which a needy agent is picked by the random dictatorship equals \(q\). We now show that if there are only two types of links between the agents (e.g. only friends and impartial agents, or only enemies and impartial agents), then the lowest probability with which the duples mechanism chooses a needy agent is strictly greater than \(q\).

6 Structural Balance↩︎

In this section, we restrict attention to the class of networks satisfying structural balance theory, a concept borrowed from social network analysis which asserts that social networks tend towards balanced or stable relationships. Following Heider [4], Cartwright and Harary [5] formulated the hypothesis within a graph-theoretic framework. Using the term ‘’friend" to designate a positive sentiment and the term’’enemy" to designate a negative relationship, the classic balance model defines a social network as balanced if it contains no violations of three assumptions:

• If \(j \in F_i\) and \(k \in F_j\) then \(k \in F_i\) (a friend of a friend is a friend).

• If \(j \in E_i\) and \(k \in E_j\) then \(k \in F_i\) (an enemy of an enemy is a friend).

• If \(j \in E_i\) and \(k \in F_j\) then \(k \in E_i\) (a friend of an enemy is an enemy).

Notice that the third condition, together with symmetry of enmity and friendship relations implies that if \(j \in F_i\) and \(k \in E_j\) then \(k \in E_i\) (an enemy of a friend is an enemy).

6.1 Planner knows the network↩︎

Suppose the planner knows the network. We are then able to fully characterize the networks (within the class of networks satisfying structural balance) which admit an efficient DSIC mechanism. Before we state the result, we need to introduce the following notions.

An EF-component in network \(G\) is a maximal set of nodes, \(X\subseteq V\), such that for any two nodes \(\{i,j\} \subseteq X\), \(i \neq j\), there is a sequence of nodes \(\{i_0,\ldots,i_m\}\) such that \(i_0 = i\), \(i_m = j\), and for any \(1 \leq r \leq m\), \(i_{r-1} \in F_{i_{r}} \cup E_{i_{r}}\). In other words, \(j\) is reachable from \(i\) in \(G\) by a path consisting of the friendship links or enmity links only.

An F-component is an EF-component \(X\) in which for all pairs of agents \(i,j \in X\), there is a path consisting of the friendship links only. Of course, every F-component is also an EF-component.

An F-component \(X\subseteq V\) of \(G\) is an F-clique if, for any distinct two nodes \(\{i,j\} \subseteq X\), we have \(i \in F_j\). In other words, any two nodes in an F component are friends.

An EF-component \(X\subseteq V\) of \(G\) is an EF-clique if it is either an F-clique or there exists an non-empty set \(Y\subsetneq X\), such that \(Y\) and \(X\setminus Y\) are both F-cliques and, for any node \(i \in Y\) and \(j \in X\setminus Y\), \(i \in E_j\), i.e. \(i\) and \(j\) are enemies.

We can now state our characterisation result.

6.2 The planner does not know the network↩︎

If we restrict attention to networks satisfying structural balance, the duples mechanism strictly dominates the constant mechanism since it chooses a needy agent with probability greater than \(q\). On the other hand, there will be networks satisfying structural balance where the random dictator chooses a needy agent with probability \(q\). For instance, structural balance is satisfied if \(n\) is even and each agent has exactly one friend and no enemies.

References↩︎