The published algorithm PageRank computes the stationary (limiting) probability distribution over a Markov-chain abstraction of the WWW, and is the first published **attack-resistant trust metric**, inspiring Levien's later work on the Advogato network-flow-based trust metric. For PageRank to be defined, the underlying Markov transition matrix needs to be ergodic; a small smoothing probability distribution $E$ is used to ensure that this is the case, although a vulnerability in $E$ (such as the uniform $\alpha$ suggested in the original paper) can make the trust metric as a whole vulnerable to spam.

One of the surprising characteristics of both PageRank and the Advogato metric is that they have **no capability for negative attestation** — you can choose to raise someone else's PageRank by linking to them, but there is no action you can take to lower it. In human social networks, an analogous phenomenon results in something known as the **broken stair effect**, where an actor who does net harm to the network by seriously harming one victim after another can nevertheless maintain a positive reputation by befriending a much larger number of people.

("Negative attestation" is a term from the literature on cryptographic authenticity verification systems. I would like a better term, but I'm not familiar with one.)

For application to human reputation systems rather than WWW search results, we might consider this a drawback, because it is much easier for someone to harm us in a permanent way than to improve our lives in a permanent way. So, when consulting a reputation system, we are much more concerned about whether a person might do us great harm, for example by raping us, assassinating our character, or looting our house, than whether they are likely to do us great good, because the harm done by a single rape, defamation, or fraud can be much greater than the plausible positive effects on our life from interacting with a person. So at an individual level, we have strong incentives to want reputation systems to support negative attestation.

Unfortunately, evidence from human society to date suggests that negative attestation can make reputation systems vulnerable to a variety of pathologies.

One common problem is that, if attestations are non-anonymous, participants have a **perverse incentive not to negatively attest**, because they may suffer baseless negative attestations in return. In individual human social dynamics, this commonly results in powerful and influential participants getting away with murder — sometimes literally — while participants with less robust reputations often suffer major repercussions for minor infractions of etiquette and are left without recourse for even major damages inflicted upon them. This perverse incentive is what allows broken stairs to continue to exist pervasively in human society.

Another problem that commonly manifests at a larger scale is **tribalism and war**: depending on which social group you happen to be born into, the reputation system may tell you that Communists and people who associate with them are evil, while capitalists are honorable captains of industry, or the reverse, through a stable membrane of negative attestations separating the two social groups and punishing anyone who attempts to bridge the membrane. The problem is that negative attestations in this case prevent the equilibrium of the calculations of the reputation system from being unique; the ergodicity present in almost all Markov chains is lost.

Human societies have developed a broad range of institutions for managing these problems of negative attestation, including money, courts, laws, prisons, police, formal and informal honor codes, diplomacy, journalism, and arguably capitalism. (Capitalism provides ambitious young psychopaths with the option of pursuing power more effectively by manufacturing inexpensive hand soap than by raising an army to conquer territory.) Each of these institutions comes in many different varieties in different cultures; the restorative justice practiced by North American Native circles of justice is radically different from the retributive justice meted out by courts of law in Roman-derived societies; both are radically different from the Romani *kris* and its ideals of *kintala* and reconciliation; and anarchist or pacifist ideals of transformative justice are different from all of these. All of these systems have their flaws. **There is no reason to think the negative-attestation problem is easy**.

These problems seem to crop up not only in real human social dynamics in meatspace, but also in mathematical or cybernetic reputation systems that attempt to provide us with tractable abstractions of those dynamics, limiting the damage that can be done by bad actors. **We must be careful to ensure that we do not write social software that worsens the problem** instead of making it better.

Within the abstraction of fixpoints of linear algebra, the corresponding statement is that the Perron–Frobenius theorem doesn't guarantee the existence of a unique largest eigenvalue for matrices with negative elements.

Scott Aaronson wrote an essay in 2014 about attempting to expand eigenvector-based reputation systems to moral philosophy in general called Eigenmorality, covering questions like this:

[S]hould we compute your “total morality” by simply summing over your interactions with everyone else in your community? If so, then can a career’s worth of lifesaving surgeries numerically overwhelm the badness of murdering a single child?

And this, by commenter "MadRocketSci", summarizing something Aaronson said:

[I]t's a little ludicrous to award “morality” to whatever group of in-group cooperators/out-group defectors happens to be largest. That seems to be a general feature of this sort of algorithm, as stated.

That is, in the presence of deep divisions in a society, Aaronson's concept of eigenmorality condemns the minority groups struggling against the majority. This is perhaps a good illustration of how it is easy for an attempt to formalize reputation systems with negative attestation can go badly wrong. I show examples of this outcome of Aaronson's framework below.

He also linked to related work by Tyler Singer-Clark on morality metrics on Iterated Prisoner's Dilemma Players (source code), by Sep Kamvar, Mario Schlosser, and Hector Garcia-Molina on trust metrics for P2P networks, and by Rebecca Newberger Goldstein on moral philosophy in a fictional context.

Kamvar et al. base all their EigenTrust computation with a "normalized local trust value" in $[0, 1]$, truncating all negative values to 0, so they do not attempt to handle negative attestation, even though the explicit goal of their research is to "identif[y] malicious peers and isolate[] them from the network."

Here are a couple of thought experiments to explore the space around PageRank.

Here we have the transition matrix of an ergodic Markov chain and we come up with its stationary distribution. First, let's generate a random square matrix.

In [1]:

```
%pylab inline
```

In [2]:

```
n = 6
pre_t = rand(n, n)
print pre_t
```

In [3]:

```
col_sums = sum(pre_t, axis=0)
print col_sums
```

[ 2.3088624 3.2768841 2.51800413 2.82512006 3.08518197 4.13190355]

In [4]:

```
t = pre_t / col_sums
print t
```

Now each column of the matrix totals to 1, and all the items are between 0 and 1:

In [5]:

```
sum(t, axis=0), t.min(), t.max()
```

Out[5]:

(array([ 1., 1., 1., 1., 1., 1.]), 0.0055043202965486624, 0.31949266802821036)

In [6]:

```
v = zeros(n)
v[0] = 1
print t.dot(v)
```

[ 0.24410566 0.06061088 0.00688473 0.2220369 0.18399118 0.28237064]

So let's generalize to arbitrary numbers of multiplications.

In [7]:

```
def ndot(m, n, v):
for i in range(n):
v = m.dot(v)
return v
print ndot(t, 1, v)
```

[ 0.24410566 0.06061088 0.00688473 0.2220369 0.18399118 0.28237064]

In [8]:

```
print ndot(t, 2, v)
```

[ 0.2042623 0.16431061 0.09107234 0.15143749 0.23288857 0.15602869]

In [9]:

```
print ndot(t, 10, v)
```

[ 0.17994214 0.18187854 0.14284492 0.12512731 0.1982469 0.17196018]

In [10]:

```
print array([ndot(t, k, v) for k in (0, 1, 10, 20, 100, 101, 102)])
```

In [11]:

```
sum(ndot(t, 100, v))
```

Out[11]:

0.99999999999999989

So we can see that this procedure converges relatively quickly (in about 20 iterations to the display precision) on a vector which is still a valid probability distribution, i.e. its values are all between 0 and 1 and its $L^1$ norm is 1, except for rounding error. It's clearly an eigenvector of the matrix with eigenvalue 1, since it's a fixpoint of the matrix.

There are a couple of obvious questions, though:

- Does this result depend on the vector we started with, or would we get other results (maybe a different eigenvector, maybe something that isn't even an eigenvector) for other starting points?
- Is it the
*first*eigenvector of the matrix? What are the other eigenvectors, if any? (They should only be missing if the matrix is singular, and since we generated it randomly, it probably isn't singular.) - Even if any vector would get us to the same place on
*this*matrix, is there anything special about this matrix that makes that true?

The first question is easy to answer; we can multiply the matrix by itself to see what it would do to any possible vector:

In [12]:

```
print ndot(t, 100, t)
```

Since every column of this resulting matrix is the same, it doesn't matter what weighted sum we make; as long as the column weights in our starting vector add up to 1, we'll always get the same result.

What about the eigenvector decomposition? Numpy has a built-in function for computing the eigenvectors and eigenvalues of a matrix:

In [13]:

```
vals, vecs = linalg.eig(t)
print vals; print vecs
```

In [14]:

```
eig0 = vecs[:,0]
print eig0; print eig0/sum(eig0)
```

Sure enough, that's our eigenvector!

Note also that all the other eigenvectors are of mixed sign — there's no way to scale them into uniformly non-negative real vectors like we did with `eig0`

. This is true in general of matrices like these, as one of the consequences of the Perron–Frobenius theorem mentioned earlier.

The third question is the most interesting. This matrix represents an ergodic Markov process, but it's easy to construct Markov-process vectors which aren't (and which thus violate the Perron–Frobenius positivity criterion). The simplest example is a deterministic periodic alternation between states:

In [15]:

```
pt = array([[0, 1],
[1, 0]])
print array([ndot(pt, k, [1, 0]) for k in range(8)])
```

[[1 0] [0 1] [1 0] [0 1] [1 0] [0 1] [1 0] [0 1]]

But you can have periodicity without determinism; for example:

In [16]:

```
bpt = array([[0, .1, 0,.9],
[.1, 0, .9, 0],
[0, .9, 0,.1],
[.9, 0, .1, 0]])
print array([ndot(bpt, k, [1, 0, 0, 0]) for k in range(8) + [100, 101]])
```

In [17]:

```
bt = array([[0, .1, 0, .9],
[.1, 0, .9, 0],
[0, .9, 0, 0.0999],
[.9, 0, .1, 0.0001]])
print array([ndot(bt, k, [1, 0, 0, 0])
for k in range(8)
+ [100, 101, 100000, 100001]])
```

In [18]:

```
vals2, vecs2 = linalg.eig(bt)
print vals2; print vecs2
```

Here we can see that the third-produced eigenvector is the one with the highest eigenvalue (and thus the "first eigenvector" in the usual ordering) and that it corresponds to a nearly even distribution of probability across the items.

It is Markov's Theorem that for the transition matrix of an arbitrary ergodic Markov chain, there is an eigenvector with the largest eigenvalue, that eigenvalue is 1, and that eigenvector is the limiting distribution of the Markov chain. The Perron-Frobenius theorem goes further and tells us that this is a general property of real all-positive square matrices (up to normalization) — you will have a unique maximum eigenvalue, the associated eigenvector will be real and all-positive, and the other eigenvectors will not be (because they have to be orthogonal to the first eigenvector). Perhaps surprisingly, you may end up with imaginary numbers in the other eigenvalues and eigenvectors. Consider the eigenvalue decomposition of this almost-periodic transition matrix:

In [19]:

```
vals2, vecs2= linalg.eig([[0.1, 0.1, 0.1, 0.7],
[0.7, 0.1, 0.1, 0.1],
[0.1, 0.7, 0.1, 0.1],
[0.1, 0.1, 0.7, 0.1]])
print vals2; print vecs2
```

In [20]:

```
print vecs2[:,0]
```

[ 0.5+0.j 0.5+0.j 0.5+0.j 0.5+0.j]

But Perron-Frobenius doesn't tell us anything about what happens once elements in the matrix can go negative. Maybe we won't have a unique maximum eigenvalue (although this will happen almost never if the matrix is random), or maybe there will be, but we'll have multiple fixpoints corresponding to different eigenvectors.

Indeed, if we start considering the previous examples as reputation systems with negative attestation, all the real eigenvectors are fixpoints of the matrix if we renormalize them after each iteration — there are almost always as many possible outcomes of the linear reputation system, in some sense, as there are nyms being assigned reputations!

But what happens if we allow negative-weight edges in our graph? One question then is how to normalize the columns of our weight matrix — if we normalize in the $L^1$ norm as before, we have the perhaps perverse outcome that you obtain more power to help your friends by bashing on your enemies. Instead, let's try normalizing in the $L^2$ norm, since the interpretation as probabilities doesn't make any sense with the negative numbers anyway.

Here's a social graph of three people. Two of them love each other, the third loves only themself and is hated by both. This third person hates the first person and is indifferent toward the second.

In [21]:

```
st_denorm = array([[ 1, 1, -1],
[ 1, 1, 0],
[-1, -1, 1.]])
def normcols(m):
return m / (m**2).sum(axis=0)**0.5
st = normcols(st_denorm)
print st
```

In [22]:

```
print array([ndot(st, k, [1, 0, 0]) for k in range(10)])
```

A couple of interesting features here already. First, our attempt to normalize the columns in $L^2$ didn't really help; we still have exponentially growing reputation magnitude values, which will prevent us from reaching a fixpoint even if we do approach an eigenvector. Second, notice that the first person is getting a big reputation boost from the fact that the third person hates them.

Before we get to changing the normalization, let's see what happens if we do the same thing, but starting from the premise that the third person is okay.

In [23]:

```
print array([ndot(st, k, [0, 0, 1]) for k in range(10)])
```

As expected, we're now exponentially zooming off in a different direction, one where the first two people appear more and more evil, while the third person is better and better — both because they love themself, but also for being hated by the other two.

Instead of trying to normalize each column, let's renormalize the reputation vector after each iteration instead. But let's do it in $L^2$, because doing it in $L^1$ could give us division by zero, or worse, division by almost zero.

In [24]:

```
def ndotn(m, n, v):
for i in range(n):
v = m.dot(v)
v /= v.T.dot(v)
return v
print array([ndotn(m, k, [0, 0, 1])
for m in st, st_denorm
for k in range(10) + [100, 101, 102, 1001, 10000]])
```

So, we still preserve this behavior that if you start believing the third person is okay, then you keep thinking the other two are baddies, but there are a couple of other anomalies there. One is that under this renormalizing procedure, our signed transition array gives us different results according to whether we've normalized its columns or not. The other is that we aren't finding an eigenvector; we're oscillating back and forth between two states, although they're only a little different.

What do the actual eigenvectors of this matrix look like?

In [25]:

```
svals, svecs = linalg.eig(st)
print svals; print svecs
```

So our first eigenvector looks pretty much like we'd expect: the third person, because they're the hated minority, is computed to have a negative reputation, exactly as negative as the positive reputation of the minority-hated person in the majority; the majority person the minority doesn't care about is computed to have a positive reputation, because the first person loves them, but less so.

The associated eigenvalue tells us how we could renormalize the entire transition matrix to get something that doesn't blow up when you iterate it.

In [26]:

```
st_n = st / svals.max()
print st_n
```

In [27]:

```
minority_report = array([ndot(st_n, k, [0, 0, 1]) for k in range(8) + [100, 101]])
print minority_report
```

In [28]:

```
first_eigenvector = svecs[:,0]
minority_report[-1] / first_eigenvector
```

Out[28]:

array([-0.50914762, -0.50914762, -0.50914762])

In [29]:

```
print array([ndot(st_n, k, [1, 0, 0]) for k in range(8) + [100, 101]])
```

In [30]:

```
ndot(st_n, 100, [1, 0, 0]) / first_eigenvector
```

Out[30]:

array([ 0.64861522, 0.64861522, 0.64861522])

In [31]:

```
print array([ndot(st_n, k, [0, 1, 1]) for k in range(8) + [100, 101]])
```

And this one, where the two groups' reputations cancel out 99.999%:

In [32]:

```
print ndot(st_n, 100, [0, .785, 1])
```

[ 1.00734560e-05 5.64346740e-06 -1.00734560e-05]

Even if we limit ourselves to $L^2$-normalized eigenvectors, there are still two candidate versions of the first eigenvector — the sign of an eigenvector is arbitrary, and remember that in the first calculation it came out all-negative instead of all-positive. In the Markov-chain interpretation, there was a principled way to resolve the ambiguity, but in this one there doesn't seem to be. The eigenvalue computation algorithm provided by Numpy happened to give us the version of the eigenvector that favors the majority, but its negation would have been equally valid.

It happens that none of the three eigenvectors in this case are all positive. It could have happened by chance, since one of the three is a rounding error, but the chance of that happening for a larger matrix is probably very small, order $\frac{N}{2^N}$ for $N$ participants. But the fact that none of the three is all positive shows that that isn't a valid way to cut the knot.

What happens if our oppressed minority turns the other cheek and makes nice with their oppressors, Dalai-Lama-style? Our attempt at normalization of the transition-Lama matrix rotates us entirely off the real line, because there are no nonzero real eigenvalues!

In [33]:

```
tl = array([[1, 1, 1],
[1, 1, 0],
[-1, -1, 1]])
tlvals, tlvecs = linalg.eig(tl)
tl_n = tl / tlvals.max()
print tl_n
```

In [34]:

```
print tlvals; print tlvecs
```

I think this shows that Singer-Clark's "eigenmoses rating" does not deterministically produce a real-valued set of morality ratings, and on some simple examples, it deterministically produces a complex-valued set of morality ratings, for which he proposes no interpretation.

Furthermore, I do not see a principled way that these problems can be overcome in the framework of an egalitarian reputation metric.