[MUD-Dev] Reputation systems: a possible path for investigation

[Andrew L. Tepper]

Something related to reputation systems are ranking systems. In a
reputation system, you say "I trust JC, and JC trusts Ed, therefore
I can trust Ed. A good property of a ranking system is that if JC
tends to beat Ed, and I tend to beat JC, then I should tend to beat
Ed.

Both systems are things that players will want to game
(manipulate). We use an algorithm in A Tale in the Desert which has
this property, and is game-resistant. It's described here:

  http://www.egenesis.com/erank.rtf

Andy Tepper

<EdNote: Below, minorly reformatted for clarity>

--<cut>--
The eGenesis Ranking SystemA highly cheat-resistant, zero-sum
ranking system for multi player games

Andrew L. Tepper, BS
Josh M. Yelon, PhD

February 15, 2002

Problem:

  Ranking systems such as ELO are often used to rate chess
  players. These systems attempt to encourage players to compete
  against others of a similar skill level by making matches between
  an advanced player A, and a beginner player B be risky for A, and
  rewarding for B.

    In the case that A wins:

      A gains a small number of points
      B loses a small number of points

    In the case that B wins:

      A loses a large number of points
      B gains a large number of points

  These systems are subject to cheating. If a player A wishes to
  boost his rank, he conspires with friends B, C, and D as follows:

    - B Plays C several times, intentionally losing to boost C's
    rank.

    - C Plays A several times, intentionally losing to greatly boost
    A's rank.

    - Another friend D is brought in. The three play each other in
    the same pattern to boost D.

    - D Plays A several times, intentionally losing to further boost
    A's rank.

  The pattern is recursive: Players P1 thru PN-1 play each other to
  boost PN-1, who then loses to PN.

Solution:

  Each player in the system starts with a vector of 256 bits. Half
  of these bits, randomly selected, are set. A players rank is the
  number of bits set.

  We number each bit 0-255. When a match occurs between two players,
  A and B, a series of 32 hash values in the range 0 to 255 are
  computed based on the players names such that the same two players
  always yield the same 32 values. For each value, we inspect that
  bit in both players vectors. When a bit is set in the losers
  vector, and clear in the winners vector, we transfer that bit:
  clear it in the losers vector, and set it in the winners. In all
  other cases we do nothing. This system forces players to play a
  wide variety of others to boost their rank.

  Still, its possible to boost your rank by only playing
  beginners. To combat this, we modify the algorithm as follows:
  Each player starts with their bit vector clear. They also have 128
  reserve bits which are stored simply as a count. A players rank is
  equal to the number of bits set in his vector, plus the number of
  bits in reserve. When a match occurs, bits are transferred as
  above, with the following additional rule: When one of the 32
  values bits are clear in both the winners and losers vectors, a
  bit is attempted to be transferred from the winners reserve to a
  specially selected clear bit in his own vector. This specially
  selected bit is based on a different hash function that again
  incorporates both players names. The losers vector and reserve are
  untouched. In this way, someone who only plays beginners doesnt
  affect his own rank, but may boost the beginners rank.

Practical Applications:

  We designed this ranking system to be used in massively
  multiplayer online games such as A Tale in the Desert
  (http://www.ataleinthedesert.com). There are some additional
  considerations to take into account.

  First, beginners should have the sense that they are making
  progress when they first start playing. To resolve this, we report
  everyones rank as simply the number of bits set in their vector,
  ignoring their reserve bit count.

  Second, friends like to play each other repeatedly, and should see
  progress on more than just the first game. To resolve this,
  instead of attempting transfers for all 32 bits, we randomly
  select 8 of the bits to transfer. In subsequent matches won by the
  same person, there are fewer bits to transfer, and eventually this
  number dwindles to none, but it allows for friends to play each
  other repeatedly and still see some progress.
--<cut>--
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev