3
$\begingroup$

Problem

For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated based on the total weight of the active players, and banned players cannot vote, so the total weight of the system can change during the computation.

Can I make this computation, avoiding infinite loops?

Constraints

  • The whole system is unveiled simultaneously, players and votes.
  • I have to compute this on the fly, so I cannot fix the total weight by using the final weight of a previous computation
  • I absolutely cannot count the banned players' votes, trolls are common
  • Also because trolls are common, a big percentage of the players can be banned at any point, so I can't either just count them in the final weight even if their actual votes don't count, because the minimum downvote percentage by legit players can grow beyond 100%.

Cases

I already spotted the trivial case of a player with 66%+ weight voting himself down, resembling "this sentence is false", so I disabled that.

But there's also the case where there's N players that together account for 66%+ weight, and where every combination of N-1 players still account for 66%+, and each of those agents downvote each other. So together they downvote each other but at the same time, because all of them are downvoted, all of their votes don't count. It's almost the same as the previous case but way harder to solve and even detect.

However, I think that case is unlikely because most of the players have to conspire for that to happen, or just by chance which is even more unlikely I believe.

$\endgroup$
  • 1
    $\begingroup$ Although I'm sure there are scenarios in which loops can occur, if I understand correctly then the example in the last paragraph isn't one of them: after A and B are banned, the other people who downvoted them will have 65% * 1/0.96 ~ 67.7% of the weight. $\endgroup$ – Peter Taylor Aug 14 at 10:30
  • $\begingroup$ You're right. I removed that case. $\endgroup$ – battlegrounds66 Aug 15 at 1:28
  • 2
    $\begingroup$ What does "players with 66% of downvote weight" mean? Can you specify that more carefully? $\endgroup$ – D.W. Aug 19 at 22:47
1
$\begingroup$

I come from a database / transaction background which will influence this answer.

My take would be to serialize the downvotes and handle one at a time. The banned function will be handled this way. Unbanning (is this a Word? ) will need to be handle separately: imagine that a troll is banned, a while later the total weight has increased enough for that player to be undammed.

  1. When a player does a downvote, add the downvote to a queue (or similar). Save the id of the downvoted player, the id of the downvoter and the downvote quotient = downvoter current weight divided by current total weight.
  2. In the serial function handle one item from the queue at a time.
  3. Link the downvote to a list for the downvoted person. If one downvoter has downvoted a person several times, save only the latest. If the downvote player is already banned, nothing more needs to be done.
  4. Now calculate the total downvote quotient by traversing the list. Only sum quotient for currently not banned users.
  5. If the quotient is above 66% ban the user.
  6. Take next item from the queue, see above

Now in order to unban a user you need to have a separate function. It might be a good idea to remove all old downvotes Before unbanning, or perhaps mark them as invalid?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.