Karma Loop Problem

[tayler6000]

Consolidating #108 and #110.

Most of us are aware of the Karma Loop Vulnerability but based on these two GitHub issues it looks like there are two trains of thought on how to fix it (so far).

What solution should we actually work towards developing?

(We can also probably fix #134 while we're messing with stamps)

[tayler6000]

Math isn't exactly my strong suit (Not a great quality for a programmer, I know) so my understanding of this is a little shaky but I understand the general concept of how it works and the problem we have.

Is it possible/easy to detect when this loop occurs? If it is, I think the ideal solution would be to calculate each user's score without the loop and see who has the larger score between the two without this loop. Then recalculate as if only the user with the higher score gave a stamp to the person with the lower score.

Also, can this occur in larger loops as well? If person A only stamps person B, who only stamps person C, who only stamps person ..., who only stamps person A? The larger the loop the lower the factor everyone increases by but a wide enough net could make up for that I would assume. Is this also possible?

[plexish]

Thanks for digging into this! Yes, larger loops also work and cause problems. Yes, it's pretty easy to detect and avoid all loopy behavior in a clean way, though computationally intensive. Even not absolute loops are not ideal, as they allow tactical voting (e.g. I gained a lot of stamps by giving you some stamps). So I think the solution is to block all karma flows from returning to the giver, by calculating each person's stamps as if they'd never given anything out (zeroing the relevant part of the outgoing matrix) and using this score directly. In a large graph there will almost always be backflowing karma, so I don't think the step of comparing loopless and looped karma is necessary, and skipping it avoids complexity.

[plexish]

Giving stampy stamps by default would no longer be necessary to fix karma loops with the non-backflowing karma and the decay factor, but giving Stampy some stamps helps with a distinct problem: Instability of karma flows around users who have received a significant number of stamps but only given out a small number of stamps.

In other contexts, Stampy getting stamps would instead go to a null user.

Giving Stampy stamps is also not a very good solution to karma loops, as users could overwhelm it by giving a very large number of stamps to each other. It does stop the absolute loops and crashes, but it's not the true solution to tactical voting and backflows.

@AugustusCeasar might be interested

[tayler6000]

I’m not entirely convinced this solution would work to be honest.

The karma loop problem exists as long as two people stamp each other, even if they’ve stamped others. Just 1 on 1 has the greatest impact.

So imagine a situation where we’ve given each other a stamp, and I’ve given one to Augustus, when it calculates me it assumes I’ve not given anyone a stamp which works, then it calculates you and it assumes you’ve not given anyone a stamp and it works, then it calculates Augustus and it sees my weight is now larger because you and I are in a karma loop and I’ve distributed some of that looped weight to Augustus.

So really that solution just makes it so I can’t benefit myself.

I think the only way you can do it is by calculating only inflow to the person your calculating. But the problem is that would require you to know how many stamps each person that gave you stamps has. And in the case of Stampy no one has stamps unless they come from Stampy, and I believe that Stampy has given one stamp to Rob and all other stamps are based off him. But Rob has more than one stamp because people have given him stamps. But the only reason anyone had stamps to give to Rob is because he gave someone a stamp who gave someone a stamp, etc, etc until it got to the person who gave Rob a stamp, and in giving Rob a stamp, increased everyone’s stamps because Rob is the true source of all stamps.

So you could say everyone is inherently worth 1/n stamps where n is the number of users on the platform. Which at least gives everyone inherent value to make them calculable (ish). The system would still loop but you could just say don’t factor it in if a loop is detected but those loops will always show up differently since the point of origin (the user being checked) is always changing, which could make it near impossible to detect said loops.

All this to say I’m at the point where I don’t think the karma loop is truly fixable and I think that’s ok. I’m not entirely sure it needs to be fixed.

We may need something done since members get certain perks for having a high amount of stamps but I really don’t know what can be done.

[robertskmiles]

So, as soon as you're giving stamps to anyone outside of the loop, the loop becomes way way less powerful because, in your example, you're giving half of the stamp power to Augustus every time it comes around the loop (actually with gamma at 0.9 as it is now, 55% leaves the loop through Augustus and decay, and 45% continues on), so then the multiplication you get by looping is pretty small (1.81x what you got in, compared to 9x for a fully closed loop). The problem with loops is just that closed loops give you artificially inflated stamp numbers which is a problem if you have stamp count thresholds on important things. As soon as you try to use that high stamp count to directly influence anything by giving stamps, you lose almost all the amplification, and the loop isn't really a problem.

[Aprillion]

Do we want to go 1 step back and make some examples for testing future eigenkarma implementations?

For following tables, where people in columns upvote people in rows, what is the expected (desired) eigenkarma of person C from the point of view of person A (not taking into account Stampy for now)?

0.          1.          2.          3.       
  A B C       A B C       A B C       A B C
A - 0 0     A - 0 0     A - 0 0     A - 0 1
B 0 - 0     B 1 - 0     B 1 - 0     B 1 - 1
C 1 0 -     C 1 1 -     C 0 2 -     C 0 2 -

If we add Stampy (S) and Rob (R) to the mix, what is the expected eigenkarma of person C from the point of Stampy in following examples (and is it different from Rob's point of view)?

4.              5.              6.              7.              8.              9.              10.          
  S R A B C       S R A B C       S R A B C       S R A B C       S R A B C       S R A B C       S R A B C
S - - - - -     S - - - - -     S - - - - -     S - - - - -     S - - - - -     S - - - - -     S - - - - -
R 1 - 0 0 0     R 1 - 0 0 0     R 1 - 0 0 0     R 1 - 1 1 0     R 1 - 1 1 1     R 1 - 1 1 1     R 1 - 5 0 0
A - 0 - 0 0     A - 1 - 0 0     A - 2 - 0 0     A - 1 - 1 0     A - 1 - 1 1     A - 2 - 1 1     A - 5 - 0 5
B - 0 0 - 0     B - 0 1 - 0     B - 0 1 - 0     B - 1 1 - 0     B - 1 1 - 1     B - 1 1 - 1     B - 0 5 - 5
C - 1 0 0 -     C - 0 0 1 -     C - 0 0 1 -     C - 1 1 1 -     C - 1 1 1 -     C - 1 1 1 -     C - 0 0 5 -

(edit: updated to flow karma from columns to rows, to match the implementation convention)

[tayler6000]

Ok so I ran a test where you have 4 people who've all stamped each other and compared how that's calculated currently to how it would be calculated using Plex's idea of not counting your votes on your own score and here's a screen shot of the result:

Under Current method for personal stamps the 0th index is 0 because Stampy has 0 stamps, on the new method I removed Stampy, so that's why the matrix sizes are different.

In this scenario everyone's stamps went down from 9.6 for Rob and 4.8 for everyone else to 6 for Rob and 3 for everyone else. Bringing total stamps in circulation from ~24 to 15 (down 37.5%) which I'd say is pretty good.

And Plex said this solution:

...removes tactical voting and the ability to participate in a karma loop yourself, which I think covers the core needs.

So I'm personally for this solution.

Edit/Note: in my example everyone technically gave a vote to Stampy but this is because np.linalg.solve would fail otherwise.

[tayler6000]

Hm, do we want to go 1 step back and make some examples for testing future eigenkarma implementations?

Just a quick implementation note the actual matrices that include Stampy and Rob are set up like:

  S  R  A
S 1  0  0
R 1 -1  0
A 0  0 -1

[Aprillion]

Just a quick implementation note the actual matrices that include Stampy and Rob are set up like:

I updated my previous comment to flow karma from columns to rows, ignoring the diagonal, any stamps to Stampy, not using any negative numbers, and using integer number of stamps (not score) in my examples that I am interested about to understand the expectation better.