I retract the <2x claim. I think it’s still basically correct, but I can’t prove it so there may well be edge cases I’m missing.
My new claim is <=16x.
We currently have a total of U upvotes. The maximal karma threshold is 16 karma per strong upvote at 500k karma (and there are no fractional karma). So the “worst case” scenario is if all current users are at the lowest threshold (<10 karma) and you top out at making all users >500k karma, with 16 loops across all upvotes. This involves ~16U updates, which is bounded at 16x.
If you do all the changes at once you might crash a server, but presumably it’s not very hard to queue and amortize.
I think you’re mixing up updates and operations. If I understand you right, you’re saying each user on the forum can get promoted at most 16 times, so at most each strong update gets incremented 16 times.
But you have to count the operations of the algorithm that does that. My naive effort is something like this: Each time a user’s rank updates (1 operation), you have to find and update all the posts and users that received their strong upvotes (~N operations where N is either their number of strong upvotes, or their number of votes depending on how the data is stored). For each of those posts’ users, you now need to potentially do the same again (N^2 operations in the worst case) and so on.
(Using big O approach of worst case after ignoring constants)
The exponent probably couldn’t get that high—eg maybe you could prove no cascade would cause a user to be promoted more than once in practice (eg each karma threshold is >2x the previous, so if a user was one karma short of it, and all their karma was in strong upvotes, then at most their karma could double unless someone else was somehow multiply promoted), so I was probably wrong that it’s computationally intractable. I do think it could plausibly impose a substantial computational burden on a tiny operation like CEA though, so it’d be someone would need to do the calculations carefully before trying to implement it.
There’s also the philosophical question of whether it’s a good idea—if we think increasing karma is a proxy for revealing good judgement, then we might want to retroactively reward users for upvotes from higher ranked people. If we think it’s more like a proxy for developing good judgement, then maybe the promotee’s earlier upvotes shouldn’t carry any increased weight, or at least not as much.
I retract the <2x claim. I think it’s still basically correct, but I can’t prove it so there may well be edge cases I’m missing.
My new claim is <=16x.
We currently have a total of U upvotes. The maximal karma threshold is 16 karma per strong upvote at 500k karma (and there are no fractional karma). So the “worst case” scenario is if all current users are at the lowest threshold (<10 karma) and you top out at making all users >500k karma, with 16 loops across all upvotes. This involves ~16U updates, which is bounded at 16x.
If you do all the changes at once you might crash a server, but presumably it’s not very hard to queue and amortize.
I think you’re mixing up updates and operations. If I understand you right, you’re saying each user on the forum can get promoted at most 16 times, so at most each strong update gets incremented 16 times.
But you have to count the operations of the algorithm that does that. My naive effort is something like this: Each time a user’s rank updates (1 operation), you have to find and update all the posts and users that received their strong upvotes (~N operations where N is either their number of strong upvotes, or their number of votes depending on how the data is stored). For each of those posts’ users, you now need to potentially do the same again (N^2 operations in the worst case) and so on.
(Using big O approach of worst case after ignoring constants)
The exponent probably couldn’t get that high—eg maybe you could prove no cascade would cause a user to be promoted more than once in practice (eg each karma threshold is >2x the previous, so if a user was one karma short of it, and all their karma was in strong upvotes, then at most their karma could double unless someone else was somehow multiply promoted), so I was probably wrong that it’s computationally intractable. I do think it could plausibly impose a substantial computational burden on a tiny operation like CEA though, so it’d be someone would need to do the calculations carefully before trying to implement it.
There’s also the philosophical question of whether it’s a good idea—if we think increasing karma is a proxy for revealing good judgement, then we might want to retroactively reward users for upvotes from higher ranked people. If we think it’s more like a proxy for developing good judgement, then maybe the promotee’s earlier upvotes shouldn’t carry any increased weight, or at least not as much.