We would like to dedicate this blog post to the Mutual Information Paradigm (MIP) of mechanism construction by Kong and Schoenebeck [3], as well as to its flagship mechanism Determinant Mutual Information (DMI) [1] and mechanism class Volume Mutual Information (VMI) [2]. These mechanisms stood out in the survey of social epistemic mechanisms for content moderation that we conducted in our previous blog post. We believe they already can be used in practical applications, such as a better version of Community Notes.

Recall that our goal is to obtain a mechanism with the following desiderata: truthfulness, collusion resistance, minimalism, agent heterogeneity, simplicity, small population, effort incentivization and flexible risk profiles. With the lottery trick we mentioned, VMI mechanisms such as DMI satisfy all of our desiderata, with the notable exception of collusion resistance and, depending on the point of view, of simplicity, though it is certainly not one of the hardest mechanisms to understand. While the lack of collusion resistance does hinder its employment in a decentralized setting, the ideas behind these mechanisms are so powerful and beautiful that they merit being known. It is also worth understanding how these mechanisms fail in the presence of coalitions, so as to guide future mechanism design.

Mechanism Explanation and Assumptions

Concerned with multi-task peer prediction, the MIP assumes a finite set of tasks assigned to \(n \geqslant 2\) agents. Each agent produces an answer from a finite set \(C\) of choices.

Each task \(t\) has a statistical type \(\theta\), which is a probability distribution \(U^{\theta}_{[n]} \in \Delta_{C^n}\), a fancy way of saying that, with tasks sampled uniformly at random, the probability that a given agent \(\)will come to believe that a given answer is the correct one depends only on the type of the task. In fact, if we let \(X^{\theta}_i\) be a random variable over \(C\) governing the beliefs (also known as signals) agent \(i\) acquires on tasks of type \(\theta\), then for all \(c \in C\),

As we mentioned in our previous blog post, the insight that achieves agent heterogeneity via multi-task peer prediction is moving statistical assumptions away from agents and towards tasks. Thus the first assumption made by the mechanism is that there is only one statistical type of task, which enables us to “drop the superscripts.”

Assumption (A Priori Similar Tasks). All tasks have the same statistical type.

Observation. One simple way of ensuring this assumption holds in practice is to randomize task assignment.

The mechanisms do have one assumption on agents' strategies, but, before we state that assumption, we must understand what a strategy is. Formally, it is, for each input signal, a probability distribution of output signals. It means that whenever an agent is given a task, it will receive its true signal (his genuine belief) of what the correct answer is and then, given this input signal, it will report an output signal at random based on the corresponding distribution.

A simple way to represent a strategy is via (column) stochastic matrices [4], also known as transition matrices. Each column of such a matrix is made of non-negative entries that sum to one and thus represent a probability distribution. A strategy \(S\) is thus a \(C \times C\) matrix where \(S_{\hat{c} c}\) is the probability that the agent will report \(\hat{c}\) given that his true signal is \(c\). The honest reporting strategy, for example, would correspond to the identity matrix.

Example. Let's again consider Alice and Bob, and recall that Alice has an agenda for the political situation, while Bob is honest and neutral (with the identity matrix as his strategy). Suppose that exactly 30% of the Community Notes to rate are pro-establishment and, for simplicity, that the helpfulness of notes is independent of the political leaning, with 50% of notes truly helpful and 50% truly unhelpful. Let's assume as well that both Alice and Bob understand precisely which notes are truly helpful and which ones aren't. Because Alice's commitment is not to the truth, but to the establishment, one strategy she could employ is reporting all pro-establishment notes as helpful and all other notes as unhelpful. Thus, according to this strategy, she will promote 30% of unhelpful notes and demote 70% of helpful notes, resulting in a strategy matrix However, that might give away that she is dishonest, so she might try to mask her bias with another strategy: to reject all unhelpful pro-establishment notes but to never accept any counter-establishment note. This would result in the strategy matrix

One advantage of framing strategies as matrices appears if we interpret the random variable \(X_i\) governing the true beliefs of agent \(i\) as a \(| C |\)-dimensional vector \(\boldsymbol{x}_i\), with \((x_i)_c = \Pr [X_i = c]\). Then if agent \(i\) uses a strategy \(S\), the vector \(\hat{\boldsymbol{x}}_i = S\boldsymbol{x}_i\) corresponds to the random variable \(\hat{X}_i\) governing the actual responses of the agent (with \(\hat{X}_i\) defined analogously).

Now that we understand strategies, we can state the second assumption of the mechanism, which is admittedly difficult to enforce in general.

Assumption (Consistent Strategies). Each agent employs the same strategy for all tasks.

In order to define what is mutual information, let's first denote the joint distribution matrix \(\)of two random variables \(X\) and \(Y\) over \(C\) as \(U_{X Y}\), so \((U_{X Y})_{a b} = \Pr [X = a \wedge Y = b]\). The following proposition, whose proof we leave for the Appendix, establishes the effect of the employment of a strategy on the joint distribution of reports.

Proposition 1. Let \(i\) and \(j\) be two distinct agents and let \(S\) be the strategy employed by \(i\). Then

The key insight is that since \(\hat{X}_i\) is derived from \(X_i\) via a strategy, it should be less informative of \(\hat{X}_j\) than is \(X_i\). Thus any function \(\operatorname{MI}\) of \(C \times C\) matrices that satisfies \(\operatorname{MI} (SU) \leqslant \operatorname{MI} (U)\) for all joint distribution matrices \(U\) and stochastic matrices \(S\) can be called a mutual information measure ¹ .

Denoting \(\operatorname{MI} (U_{X Y})\) as \(\operatorname{MI} (X, Y)\) for brevity, such mutual information measures induce dominantly truthful mechanisms under certain conditions [ 2 , Lemma 3.10], as long as they can be accurately estimated ² . Indeed, rewarding two distinct agents \(i\) and \(j\) with \(\operatorname{MI} (\hat{X}_i, \hat{X}_j)\) disincentivizes the usage of non-permutation strategies.

It turns out that every mutual information measure \(\operatorname{MI} (U)\) that is polynomial in the entries of the joint distribution matrix \(U\) can be estimated with only \(d\) samples, where \(d\) is the degree of the polynomial (the maximum monomial degree). This is quite important, as we can estimate \(\operatorname{MI} (\hat{X}_i, \hat{X}_j)\) from the responses of agents \(i\) and \(j\) to \(d\) tasks.

One good candidate for the mutual information measure is the determinant mutual information measure \(\operatorname{DMI} (U) = | \det U |\), which maps a joint probability distribution matrix to the absolute value of its determinant. This works out of the box because the determinant of a transition matrix is always between \(- 1\) and \(1\), and also the determinant of a matrix product is the product of the determinants. However, while the determinant is a polynomial of degree \(| C |\) on the entries of \(U\), the absolute value of the determinant is not. To work around this, we either use the square of the determinant (a polynomial of degree \(2 | C |\)) or an alternative simpler mechanism [2, Section 4.2] with the same payoffs in expectation, so the measure has an unbiased estimator. In either case, it will be a mechanism for \(n \geqslant 2\) agents and \(| T | \geqslant 2 | C |\) tasks. With these considerations, the \(\operatorname{DMI}\) measure gives birth to the determinant mutual information mechanism, which is the first dominantly truthful mechanism in the literature with a finite number of tasks.

Example. Going back to our example with Alice and Bob, because half of the notes are helpful and half are unhelpful, and because Bob reports honestly, the joint distribution of the belief of Alice and the report of Bob is Recall that Alice has two lying strategies \(S_0\) and \(S_1\) at her disposal to try to forward her political agenda. If she chooses \(S_0\), then \(\displaystyle U_{\hat{X}_0 \hat{X}_1} = S_0 U_{X_0 \hat{X}_1} = \left[ \begin{array}{cc} 0.3 & 0.3\\ 0.7 & 0.7 \end{array} \right] \left[ \begin{array}{cc} 0.5 & 0\\ 0 & 0.5 \end{array} \right] = \left[ \begin{array}{cc} 0.15 & 0.15\\ 0.35 & 0.35 \end{array} \right] .\) If she chooses \(S_1\), then \(\displaystyle U_{\hat{X}_0 \hat{X}_1} = S_1 U_{X_0 \hat{X}_1} = \left[ \begin{array}{cc} 0.3 & 0\\ 0.7 & 1 \end{array} \right] \left[ \begin{array}{cc} 0.5 & 0\\ 0 & 0.5 \end{array} \right] = \left[ \begin{array}{cc} 0.15 & 0\\ 0.35 & 0.5 \end{array} \right] .\) However, \begin{eqnarray*} \displaystyle \mathrm{det}^2 \left[ \begin{array}{cc} 0.15 & 0.15\\ 0.35 & 0.35 \end{array} \right] &=& 0, \\ \mathrm{det}^2 \left[ \begin{array}{cc} 0.15 & 0\\ 0.35 & 0.5 \end{array} \right] &=& 0.005625 \text{ and} \\ \mathrm{det}^2 \left[ \begin{array}{cc} 0.5 & 0.0\\ 0 & 0.5 \end{array} \right] &=& 0.0625, \end{eqnarray*} so Alice is heavily punished by choosing a lying strategy over the truth-telling one. Bob is also punished when Alice is his peer, but Alice is only one of Bob's peers, while Alice is punished for every other honest peer she is paired with.

The more general Volume Mutual Information (VMI) mechanism relies on the same principles of the DMI mechanism, but it uses more general mutual information measures than the magnitude of the determinant. For a joint distribution \(U\), the value of \(\operatorname{VMI}^w (U)\) is the volume of the space of less informative joint distributions, which is the set \(\downarrow U\) of all joint distributions \(U'\) for which there is a stochastic matrix \(S\) with \(SU = U'\). Because each column of the \(| C | \times | C |\) matrix \(S\) sums to one, the (Hausdorff) dimension of this space is at most \(| C | (| C | - 1)\), and the volume (Hausdorff measure) is taken at that dimension. The parameter \(w\) is the space's density, which can be freely chosen as well, and is very important to incentivize honest behavior when effort is needed to improve the agent's beliefs. The fancy formula is

Collusion Resistance

There are three main reasons why these mechanisms do not resist coordinated coalitions. The first reason regards tasks of low entropy, the second ambiguous tasks and the third tasks requiring high effort.

The entropy of a task is how unpredictable its true answer is prior to reading the task description. For instance, if each task is a comparison between two random items, then each task achieves a maximum entropy of one bit. However, other tasks can have much less entropy. For instance, moderating flagged content on social media, particularly if good economic incentives are in place to regulate flagging, can result in the majority of answers to tasks, say 90% of them, to be to moderate content. The mutual information between the reports of two honest agents is much less than the maximum mutual information, which can be manufactured between two colluding agents. The collusion strategy is for collusion participants to just agree with the answers of the collusion's coordinator, which are tailored to mimic those to maximum entropy tasks.

Collusions are also incentivized by the difficulty of tasks. Tasks may be difficult in two principal ways: they may require effort to complete properly and they may be ambiguous. In the scenarios we present, the collusion will have a coordinator, who decides which answer all the agents in the collusion will provide. The coordinator may or may not rotate, being randomly drawn from the collusion from time to time. The cost of effort is optimized for colluding participants because it is only incurred by the coordinator, with answers simply copied by members. Furthermore, if a task is ambiguous, the mutual information between two honest agents will be less than that between two agents in the collusion and, as long as the coordinator responds honestly, the collusion members will, in expectation, have the same mutual information with non-colluding agents as would other non-colluding ones.

Conclusion

The Mutual Information Paradigm of mechanism design is extremely powerful and generates strong truth-telling incentives. In applications that already assume non-colluding users, it is an extremely good fit. In particular, we believe it to be a better alternative to Birdwatch in a Community Notes setting, because it has formal game theoretic guarantees of truthfulness. However, using these mechanisms in a decentralized setting is risky due to the possible presence of coordinated coalitions, which can, under certain conditions, siphon resources away from the principal and agents while damaging the formation of truthful knowledge.

In the first six blog posts in this series, we introduced the key concepts and problems underlying decentralized moderation and epistemology, as well as surveyed different strategies to tackle them, including using prediction markets and mechanisms from the literature of Information Elicitation Without Verification (IEWV). The conclusion so far is that none of these methods is a perfect fit, but that they are powerful tools with plenty of application potential.

In the future, we will consider other approaches to tackling the decentralized moderation problem. As a matter of fact, we are working on an entirely different direction right now. However, for the short term, we will be taking a break in this series. If the content exposed here so far is of interest to you, feel free to reach out at hello@mbd.xyz.

Appendix

Proof of Proposition 1. We have

Thus \(U_{\hat{X}_i \hat{X}_j} = SU_{X_i \hat{X}_j}\) as claimed.\(\Box\)

References