Eliciting the deserving winner in the presence of enemies

This work analyzes the problem in which a jury has to choose a winner from a group of candidates when (i) the identity of the deserving winner is known to all jurors but not verifiable, (ii) each juror identifies with a different candidate they want to favor, and (iii) some jurors may have an enemy among the candidates they intend to harm. For example, this identification between jurors and candidates occurs in some international competitions, such as those in certain sports, where each country is represented by one candidate and one juror. In such instances, it is reasonable to think that each juror will strive to favor the candidate from their own nationality. At the same time, geopolitical tensions may compel a juror to seek harm to a candidate from a particular foreign country.¹ In order to address this problem, the task is to design a mechanism (or voting system) that incentivizes jurors to choose the deserving winner, whoever they may be. The socially optimal rule is implementable when such a mechanism exists.

Some works, such as Amorós (2011) or Adachi (2014), have proposed mechanisms that implement the socially optimal rule via backward induction when jurors want to favor their friends, but they do not account for situations where some jurors may also have enemies. The existence of enemies alters the strategic behavior of jurors because, in addition to the existing incentives to deceive to ensure that their favorite candidate is chosen, new incentives to deceive emerge to prevent their enemy from being selected when they are the deserving winner. The combination of these incentives could potentially render the implementation of the socially optimal rule impossible. To prevent this, and under the assumption that the planner knows the identity of the candidate each juror identifies with and that of their enemy (if they have one), a specific condition relating to the jurors’ enemies must be satisfied. This condition, termed “minimal impartiality,” requires that for every pair of candidates, a juror for whom neither of them is an enemy exists. We demonstrate that minimal impartiality is necessary for implementing the socially optimal rule via backward induction.

Unfortunately, the mechanisms of Amorós (2011) and Adachi (2014) mentioned above prove ineffective when jurors may have enemies, despite the fulfillment of minimal impartiality. In this paper, we propose a novel, simple, and natural mechanism that successfully implements the socially optimal rule via backward induction, whether all jurors are impartial regarding all candidates other than their own or some have enemies among the other candidates, as long as minimal impartiality is fulfilled.

In our mechanism, jurors are assigned numbers from 1 to n (where n is the total number of jurors) to announce a winner sequentially. The announcement by juror 1 is implemented if either (1) he has no enemy and does not propose his friend as the winner, or (2) he has an enemy whom he proposes as the winner. If juror 1 has an enemy, \(e_{1}\), and proposes a candidate x who is neither his friend nor his enemy as the winner, then we move to another stage in which a juror who is impartial between x and \( e_{1}\) chooses the winner between those two candidates (minimal impartiality guarantees the existence of such an impartial juror). If juror 1 proposes his friend as the winner, the process moves on to juror 2, and this sequence continues. When it is the turn of juror n because jurors 1, 2 , ..., and \(n-1\) have announced their friends, the candidate announced by juror n is chosen as the winner, even if that candidate is his friend.

For the proposed mechanism to work, the jurors’ order of intervention must satisfy certain conditions. Specifically, agents numbered \(n-3\), \(n-2\), and \( n-1\) must satisfy the following: \(n-1\) is not the enemy of \(n-2\) or \(n-3\), \( n-2\) is not the enemy of \(n-1\), and the enemies of \(n-1\) and \(n-2\) (if they exist) are distinct. Fortunately, minimal impartiality guarantees the existence of three jurors who meet these conditions.

The first paper analyzing a model similar to that of this work is Amorós et al. (2002). They study the problem of selecting a deserving ranking of candidates (instead of a single winner) that is known to all jurors. Under the assumption that each juror identifies with one candidate to whom they want to favor and has no enemies, they demonstrate that while implementation of the deserving ranking in dominant strategies is not possible, its implementation in Nash equilibrium is possible. Amorós (2023) analyzes the same model as the previous work and proposes two natural sequential mechanisms that implement the deserving ranking via backward induction. Amorós (2009) explores a more general model in which jurors may have enemies and provides a necessary and sufficient condition for the Nash implementability of the deserving ranking. However, the mechanism proposed to demonstrate the sufficient part of this condition is a variation of Maskin’s (1999) canonical mechanism, which has been criticized in the literature for being unnatural (see, e.g., Jackson 1992). Yadav (2016) analyzes the problem of implementing the deserving winners in Nash equilibrium when some jurors are “partially honest” in the sense that they have a strict preference for revealing the true state when truth-telling does not lead to a worse outcome for them.

Holzman and Moulin (2013) also analyze the problem of determining a winner when the voters are the candidates. They study a model where each agent has a private opinion about which of his peers is best and yet is indifferent about which of his peers wins, and the objective is to design direct mechanisms that use these opinions as input. The authors prove that no such mechanism (i) has the property that honesty is always a dominant strategy and (ii) respects consensus about who should win and who should lose. It is interesting to compare the current paper’s positive result to the negative result of Holzman and Moulin (2013). On the one hand, this paper makes things easier in a few ways: (i) agents do not have arbitrary private opinions, but rather the deserving winner is observed by all agents (although not verifiable), (ii) it involves fewer possible type profiles because, despite some known conflicts of interest, agents otherwise have a preference for the deserving winner, and (iii) it weakens the solution concept from dominant strategy equilibrium to backward induction equilibrium. On the other hand, this paper makes things harder in a few ways: (i) it requires full implementation, and (ii) it relaxes what is common knowledge about preferences. In this paper, the common knowledge is described by a jury configuration specifying all conflicts of interest, which still leaves room for a lot of unknown comparisons (and thus incentives to manipulate), whereas in the simplest interpretation of Holzman and Moulin, the full preference profile is common knowledge.

Niemeyer and Preusser (2023) study a model similar to that of Holzman and Moulin in which an object is allocated among a set of agents, the optimal allocation depends on the agents’ information about their peers, and each agent wants the object for himself. However, this model does not consider the possible existence of “enemies”. Mackenzie (2015) analyzes a stochastic version of the Holzman and Moulin’s model. Tamura (2016) establishes a characterization result in the context of impartial nomination rules that satisfy anonymity, symmetry, and monotonicity. Mackenzie (2020) studies how the pope is elected in the Roman Catholic Church. This problem falls within the cases analyzed by our model since the cardinals are both the jurors and the candidates. Finally, Olckers and Walsh (2024) conduct a survey on peer mechanisms in which the competitors for a prize also determine who wins.

The rest of the paper is organized as follows. Section 2 describes the model and notation. Section 3 states the necessary condition for implementation. Section 4 introduces our mechanism and shows that it implements the deserving winner. Section 5 provides concluding remarks. The Appendix shows that the mechanisms suggested by Amorós (2011) and Adachi (2014) fail when agents have enemies and analyzes two possible extensions.

Let N be a set of \(n\ge 4\) candidates participating in a competition. Each candidate has a distinct representative on a jury tasked with selecting one winner from among them. We use agent i to denote candidate i and their corresponding jury representative. There exists a deserving winner, denoted as \(\omega ^{d}\in N\), who is known to all agents but cannot be verified. The socially optimal outcome is the victory of this deserving winner. However, agents exhibit biases in the following ways: Let us formalize these concepts. Each agent \(i\in N\) is characterized by an element \(e_{i}\in (N\backslash \{i\}\cup \{\emptyset \})\), known by the planner. If \(e_{i}\ne \emptyset \), we refer to \(e_{i}\) as the enemy of i. If \(e_{i}=\emptyset \), we say that i has no enemy. Let \(\Re \) be the class of preference relations defined over N. Each agent i has a preference function \(R_{i}:N\longrightarrow \Re \) that maps each deserving winner \(\omega ^{d}\) to a preference relation \(R_{i}(\omega ^{d})\in \Re \). We denote the strict component of \(R_{i}(\omega ^{d})\) as \(P_{i}(\omega ^{d}) \).

Let \(\mathcal {R}_{i}(e_{i})\) denote the class of all preference functions that are admissible for agent i at \(e_{i}\). A jury configuration is a profile \(e=(e_{i})_{i\in N}\) and it is known to the planner. A profile \( R\equiv \left( R_{i}\right) _{i\in N}\) of preference functions is admissible at e if \(R_{i}\in \mathcal {R}(e_{i})\) for every \(i\in N\). Let \(\mathcal {R} (e)\) denote the set of admissible profiles of preference functions at e. The planner knows that the agents’ preference functions are in \(\mathcal {R} (e)\), although he does not know the actual functions.

Given a jury configuration e, a state is a profile \((\omega ^{d},R)\in N\times \mathcal {R}(e)\equiv S(e)\). The socially optimal rule is the function \(\varphi :S(e)\rightarrow N\) such that, for each \( (\omega ^{d},R)\in S(e)\), \(\varphi (\omega ^{d},R)=\omega ^{d}\) (i.e. , for each admissible state, \(\varphi \) selects the deserving winner).

A normal form mechanism is a pair (M, g), where \(M=\times _{i\in N}M_{i}\), \( M_{i}\) is a message space for agent i, \(g:M\rightarrow N\) is an outcome function mapping the agents’ messages to a final winner, and agents send messages simultaneously. A sequential mechanism is a dynamic mechanism in which agents make choices sequentially. Given a jury configuration e, a finite sequential mechanism with perfect information implements the socially optimal rule via backward induction if, for each admissible state \((\omega ^{d},R)\in S(e)\), the only outcome reached via backward induction is \(\omega ^{d}\).² The socially optimal rule is implementable if a mechanism exists that implements it.

Our first result states a necessary condition on the jury configuration for implementing the socially optimal rule via backward induction. This condition requires that, for every pair of agents, there is always a third agent who does not have either of them as an enemy.

The following proposition demonstrates that the socially optimal rule cannot be implemented via backward induction if the jury configuration is not minimally impartial. The reason is that, in that case, there exist two states such that, when moving from one to the other, the individual preferences of each agent remain unchanged even though the deserving winner has changed. Consequently, any backward induction equilibrium in the first state will also be one in the second. Since the deserving winners in the two states are different, implementing the socially optimal rule becomes unattainable.

Note that, given the characteristics of our model, the condition of minimal impartiality is equivalent to requiring that for each pair of candidates, at least one juror who does not wish to favor or harm either of the candidates exists. In this case, that juror will be “impartial” with respect to both candidates, in the sense that if one of them is the deserving winner, the juror prefers that candidate over the other. Conditions similar to this have frequently appeared in the literature. The first paper to establish a related condition was Amorós (2009, Proposition 1), who demonstrated that, to implement the deserving ranking of candidates in Nash equilibria, it must hold that for each pair of candidates, there exists at least one juror who prefers the two candidates to be ordered according to the deserving ranking.

Minimal impartiality is not only a necessary condition for implementing the socially optimal rule via backward induction but also sufficient. In the following section, we propose a simple and natural mechanism that implements the socially optimal rule via backward induction as long as the jury configuration is minimally impartial.

In this section, we introduce a mechanism that successfully implements the socially optimal rule via backward induction, whether the agents have enemies or not, as long as minimal impartiality is met.

Before defining the mechanism, we demonstrate that minimal impartiality implies the existence of three agents, i, j, and k, whose enemies (if they exist) are not connected in a particular manner: i is not the enemy of either j or k, j is not the enemy of i, and i and j do not have the same enemy.

(1) Let us number the agents, \(N=\{1,...,n\}\), in such a way that:

      (1.1) \(n-1\notin \{e_{n-2},e_{n-3}\}\),

      (1.2) \(n-2\ne e_{n-1}\), and

      (1.3) \(e_{n-1}\ne e_{n-2}\).

Because e is minimally impartial, point 1 of Lemma 1 ensures that such numbering of agents is possible. In particular, given agents i, j, and k in point 1 of Lemma 1, we can take \(n-1=i\), \(n-2=j\), and \(n-3=k\).

(2) For each pair of agents \(i,j\in N\), let \(k_{i,j}\in N\backslash \{i,j\}\) be an agent such that, for every \(R_{k_{i,j}}\in \mathcal {R} _{k_{i,j}}(e_{k_{i,j}})\), i \(P_{k_{i,j}}(i)\) j and j \(P_{k_{i,j}}(j)\) i. Agent \(k_{ij}\) is “impartial” between agents i and j in that if one of them is the deserving winner, \(k_{ij}\) prefers that agent to the other. Since e is minimally impartial, the existence of these agents is guaranteed by point 2 of Lemma 1.

Given a numbering and a notation of the agents as defined in points 1 and 2 above, Mechanism 1 is defined as follows. Agents take turns announcing who they think should win. The announcement of agent 1 is implemented if either (1) he has no enemy and does not propose himself as the winner, or (2) he has an enemy he proposes as the winner. If agent 1 has an enemy and proposes an agent x who is neither himself nor his enemy as the winner, then we move to another stage in which \(k_{x,e_{1}}\) (the “impartial” agent between x and \(e_{1}\)) chooses the winner between those two candidates. If agent 1 proposes himself as the winner, then it is the turn of agent 2, and the process repeats. If it is the turn of agent n because jurors 1, 2, ..., and \(n-1\) have announced themselves, then the agent announced by agent n is chosen as the winner, even if that agent is himself. Formally:

Stage 1: Agent 1 announces \(m_{1}\in N.\)Stage 1.\(m_{1}\): Agent \(k_{m_{1},e_{1}}\) announces \(m_{k_{m_{1},e_{1}}}\in \{m_{1},e_{1}\}.\)Stage 2: Agent 2 announces \(m_{2}\in N.\)Stage 2.\(m_{2}\): Agent \(k_{m_{2},e_{2}}\) announces \(m_{k_{m_{2},e_{2}}}\in \{m_{2},e_{2}\}.\)\(\vdots \)

Stage \(n-1\): Agent \(n-1\) announces \( m_{n-1}\in N.\)Stage \((n-1).\) \(m_{1}\): Agent \( k_{m_{n-1},e_{n-1}}\) announces \(m_{k_{m_{n-1},e_{n-1}}}\in \{m_{n-1},e_{n-1}\}.\)Stage n: Juror n announces \( m_{n}\in N.\)

Then, in this example, Mechanism 1 is as represented in Figure 1. Given the jury configuration e, Table 3 shows the conditions that must satisfy the admissible preference functions of each agent i, \(\mathcal {R}_{i}(e)\) .

Next, we explain why the mechanism represented in Figure 1 works. Given any state, \((\omega ^{d},R)\in S(e)\), consider a profile of strategies that is a backward induction equilibrium of the previous mechanism at \( (\omega ^{d},R)\). Thus, any backward induction equilibrium of the mechanism always results in \( \omega ^{d}\).

The following theorem demonstrates that the observation in Example 5 holds true in general. Whenever the necessary condition of minimal impartiality is satisfied, Mechanism 1 implements the socially optimal rule via backward induction.

The following example illustrates the importance of the numbering of the agents in Mechanism 1 satisfying the requirements listed in points 1 and 2 of its definition.

Let \((\omega ^{d},R)\in S(e)\) be a state such that \(\omega ^{d}=a\), b \( P_{d}(a)\) c, and d \(P_{c}(a)\) b (there are admissible preference functions for agents d and c that satisfy these conditions). Then, any profile of strategies that is a backward induction equilibrium of the mechanism depicted in Figure 1 at \((\omega ^{d},R)\) is such that: Therefore, the outcome reached via backward induction is \(d\ne \omega ^{d}\) , and so the mechanism in Figure 1 does not implement the socially optimal rule via backward induction.

One can find similar examples to demonstrate that if the numbering of the agents does not satisfy any of the other requirements listed in the definition of Mechanism 1 (\(n-1\ne e_{n-2}\), \(n-2\ne e_{n-1}\), and \( e_{n-1}\ne e_{n-2}\)), then Mechanism 1 fails to implement the socially optimal rule.

We have studied the problem of selecting the deserving winner from a group of candidates when each juror identifies with a different friend they wish to favor, and some jurors may have enemies they intend to harm. We have identified a necessary and sufficient condition on the jurors’ enemies to implement the deserving winner by backward induction. The mechanisms suggested in the literature to implement the deserving winner via backward induction when jurors lack enemies fail when jurors may indeed have enemies, even when the previous condition is satisfied. To address this problem, we have proposed a simple mechanism that successfully implements the deserving winner via backward induction in such cases.

Here are some suggestions for potential lines of extensions.

a. The feasibility of implementing the deserving winner is contingent upon both the feasibility of the implementation mechanism and the feasibility of the solution concept utilized. Regarding the latter, we concur with Herrero and Srivastava (1992) that, besides dominant strategies, backward induction is among the most attractive solution concepts. Using an argument similar to that of Amorós et al. (2002, Theorem 1), it can be demonstrated that if there are only three agents, the deserving winner is not implementable in dominant strategies even if minimal impartiality is satisfied. However, the question of whether this impossibility extends to cases where there are more than three agents is still open.

b. Exploring a more general model than the one examined in this work could involve eliminating the identification between candidates and jurors. This modification would allow each juror to have multiple friends they wish to favor and enemies they aim to harm. In Appendix B, we provide a preliminary approach to this problem. However, extending our Mechanism 1 to this setting remains an open question.

c. Continuing with the previous extension, it would be interesting to study the case where the mechanism designer does not know each juror’s friends and enemies. In this case, we should investigate whether it is possible to design a mechanism in which the jurors have incentives to reveal such information.

d. There are situations in which being selected is a bad thing, so (i) the worst alternative for each agent is for himself to be chosen, and (ii) having someone as an enemy means that I want him to always be selected, even when he does not “deserve” it. For example, this could occur when identifying actual criminals from suspects. In Appendix C, we analyze this extension where the roles of the agents and their enemies are reversed.