Theoretically, proxy voting comes with an interesting feature: individual judgment sets (when including the proxy’s judgment on each delegated issue) may turn out to be inconsistent. As social choice theory (and judgment aggregation) standardly assume that individual preferences (and individual judgment sets), all the main results in those fields (i.e. Arrow’s theorem) rely on this individual rationality assumption. Allowing for inconsistent individual judgment sets hence opens a new level of generality in judgment aggregation and social choice theory.
As an illustration, recall the doctrinal paradox, which famously shows that consistent individual judgment sets sometimes leads to an inconsistent collective outcome:
| p | q | \(p\rightarrow q\) | |
|---|---|---|---|
| a | 1 | 0 | 0 |
| b | 0 | 0 | 1 |
| c | 1 | 1 | 1 |
| majority | 1 | 0 | 1 |
Consider now the following modification of the above case: assume that agent \(c\) votes himself on issue \(p\) but delegates to agent \(b\) his vote on \(q\) and on \(p\rightarrow q\). We obtain the following situation, where agent’s \(c\) judgments are inconsistent:
| p | q | \(p\rightarrow q\) | |
|---|---|---|---|
| a | 1 | 0 | 0 |
| b | 0 | 0 | 1 |
| c | 1 | 0 | 1 |
| majority | 1 | 0 | 1 |
This raises new research questions: What are the conditions for the collective outcome of a vote to be rational, when individuals can be irrational? In particular, under what conditions does liquid democracy preserve majority consistency? Moreover, what are the criteria for rational delegation?11It seems intuitive to impose the following constraint: if agent \(i\) delegates issue \(r\) to an agent \(j\), he should also delegate to \(j\) all the remaining issues which depend solely on the truth of \(r\), given \(i\)’s judgment on non-delegated issues. In our example, this means that it would not be rational for agent \(c\) to delegate to agent \(b\) on issue \(q\) but not on issue \(p\rightarrow q\), given that \(c\) judges \(p\) true. And assuming some criteria of rational delegation, is it possible to go from the above cases of discursive dilemma (with consistent individuals) to a liquid case where inconsistent individuals outputs a consistent collective outcome, via only rational delegation?
By multiplying the two matrices, a new opinion matrix is generated, representing the opinion state of agents after one influence step (for instance after they exchange information with each other). DeGroot, using the associativity of matrix multiplication, shows that whether the opinions of a group of agents converge in the limit depends on the underlying influence graph. If multiplying the influence matrix by itself converge in the limit, then any distribution of opinions of the agents will converge too. More precisely, convergence depends on (each connected and closed component) of the influence graph being aperiodic (that is, the greatest common divisor of all directed cycles lenghts is \(1\).): “convergence in overall society hold if an only if each closed and strongly connected set of nodes converges, which happens if and only if each such set is aperiodic.” \cite[p.233]{jackson08social}
Consider the limit cases of DeGroot influence, where both the opinion of each agent and the influence weight belong to \(\{0,1\}\) instead of \([0,1]\). We will call such cases Boolean deGroot process (BdG). In that case the trust network is a graph which is functional (or serial and deterministic): every agent has exactly one “guru” (possibly itself). The influence matrix \(P\) will read \(1\) for entry \(P(i,j)\) of the matrix when agent \(i\) follows (copies) \(j\)’s opinion, and \(o\) for all other entries of the same row. The opinion matrix \(Q\) will read \(1\) for entry \(p(i,m)\) which the agent judges true, and \(o\) for other entries in the same row. For simplicity, we will start with considering the case where there is only one issue \(p\).
On the deterministic frames, \(\Box p\leftrightarrow\diamond p\) is a validity. The rule “copy your guru” is just the same as the rule of “influence by unanimity” (which states: switch opinion on \(p\) if and only if all of your influencers have the opposite opinion than you).
A model is stable if and only if the formula \(p\leftrightarrow\Box p\) is a validity. That is to say \(p\) is a fixpoint of \(\Box p\). - Since \(\Box p\) is a positive formula (and hence \(\Box\) denotes a monotonic function from sets of states to sets of states) the Knaster-Tarski fixpoint theorem applies: so we know that a smallest and largest fixpoints exist (and possibly more in-between). The smallest fixpoint is the empty-set (nothing is \(p\)) and the largest is the whole domain (everything is \(p\)).
First, for functional graphs, no node in a cycle can have any successor outside of the cycle. Therefore, all cycles have to be vertex-disjoint:
Let \(G\) be an influence graph. All cycles in \(G\) are vertex-disjoint.
Let \(G\) be an influence graph, such that it contains two cycles which are not vertex disjoint. Then there is a vertex \(i\) contained in both cycles, such that \(i\) has a different successor in each cycle. But since \(G\) is functional, \(i\) has at most one successor. Contradiction. ∎
There are two stability-related questions, given an initial model:
Is the model stable in the sense that it is a limit point of the dynamics (that is it is a fixpoint of \(\Box\), if my thoughts above are correct)? YES!
Is the model such that it will eventually reach a limit point, or oscillate instead?
As to 1), if the validity of the fixpoint equation \(p\leftrightarrow\Box p\) fails in the model, then we are not in a stable model. Notice that your Proposition 2, if one assumes the frame is functional, states precisely that the model is unstable whenever \(p\leftrightarrow\Box p\) is not valid in the model.
As to 2), if neither p nor p is a post-fixpoint of \(Box\) then the frame is 2-colorable (and vice versa). And that means the model cannot possibly stabilize. @DAVIDE: NO, AS MENTIONED THIS MORNING, THIS DEPENDS ON THE FRAMES BEING SYMMETRIC, SO I NEED TO THINK A BIT BETTER INTO WHAT THE FORMULA MEANS WITHOUT SYMMETRY IMPOSED. I WILL COME BACK TO THIS VERY SOON. (we have seen that for instance a simple triangle can carry non-stabilizing opinions).
The Boolean case of the theorem by Jackson should state conditions under which, no matter what the initial assignment for \(p\) is, the model will always stabilize (that is either \(p\) or \(\lnot p\) is a post-fixpoint of \(\Box\)). So Jackson’s theorem should state conditions that make a graph non-2-colorable.
Indeed, Jackson’s theorem excludes 2-colorable graphs, since they are not aperiodic (the greater divisor of all cycles lengths is 2). Jackson results implies that 2-colorable graphs do not guarantee stabilization for any distribution of opinions (and of influence weights). However, more can be said.
For instance, in the case of symmetric frames, all and only models which are not proper two-coloring of the graphs will stabilize. This gives us a full characterization of stabilization. There exists only 2 such colorings (for each connected component) of a graph. And the loop is always of size two.NOTE THAT THIS LAST PARAGRAPH DOES NOT RELY ON THE FRAME BEING FUNCTIONAL, SO THIS IS A MORE GENERAL RESULT ABOUT UNANIMITY RULE IN SYMMETRIC GRAPHS. MAYBE WE SHOULD ALSO INTRODUCE IT AS SUCH THEN.
QUESTIONS: WHAT PROPERTY DOES THE FORMULA CHARACTERIZING STABILIZATION CORRESPOND TO ON NON-SYMMETRIC FRAMES? WHAT ARE THE CONDITIONS FOR STABILIZATION IN THE RESTRICTED CASE OF BDG (COMPARED TO THE GENERAL CASE OF JACKSON’S THEOREM