# Older blog entries for Bram (starting at number 84)

Trust Metrics

I think I've figured out how to fix the gameability problems I've talked about in the last few entries.

Water pours in at a fixed rate from the seed. At any given time, each node is either trying to collect water, done collecting water and now dispensing it, or done dispensing water and simply passing it through. When a node is dispensing water it will do so at a rate depending on the amount of water flowing into it.

We will construct a schedule of what water goes where when. For each node which is trying to collect water, we ask 'if all dispensing nodes were to allocate their full amount to this node, when would it be full?' The node which does so the fastest gets added first, and all the dispensation of the nodes which certify it gets allocated up until the time. When deciding on later nodes to add, it is assumed that dispensers don't start contributing until after their previously allocated contributions are done.

Note that when a node is first added its rate of dispensation is zero. When all of the nodes which a dispenser certifies have been added, then that node's rate of dispensation is distributed evenly across all the nodes it certifies. Dead ends are skipped over, to avoid water wastage. More sophisticated forms of backlogging indirect dead ends could be made, but the simplest one should work fine in practice.

I'm very enamored of this technique. It does accurate proportional representation and is very hard to game outside of the gameability inherent in having proportional representation at all. My one current gripe is that while the technique for selecting which node gets added next is linear on the number of nodes, the technique for redistributing the dispensation of full peers is quadratic. Harumph.

To see the gameability inherent in proportional representation, consider this case: There are three voters, who will elect three candidates. Two voters prefer A, B, and C, while the third one prefers A, B, and D. Clearly the winners should be A, B, and C, but the third voter can list simply D and get exactly the candidates he wants elected.

Election Methods

On a related subject, I've for a long time been thinking about improvements to single transferable vote. There is a form of gameability of STV which I think can be completely overcome. Specifically, a voter can make their vote much stronger by taking a candidate who has no hope of winning and ranking them first. This causes very bad distortions, including the occasional candidate with no hope who actually wins!

My modification is surprisingly simple. The first winner is selected by the condorcet method. Later candidates are elected one at a time using essentially the condorcet method but with the pairwise results modified based on previous winners. Specifically, if we're comparing candidates A and B, then if X was already elected we take all candidates who ranked X above both A and B and evenly distribute a reduction in their vote strength by a total of the droop quota.

I did some testing of this and found (assuming I didn't botch up my implementation) that when using minimax there are circumstances in which the weight of a vote becomes negative. I suspect this stops happening if you use ranked pairs instead.

This technique completely obliterates the rank-a-weak-candidate-higher form of gaming which plagues STV. It also has the nice feature of not requiring all votes to be kept around. All you need to do is collate the vote counts of each two- and three-way race and the winners can be calculated from that.

Voting Machines

chalst: unfortunately the electronic voting systems are far less accurate than the paper-based ones they're replacing. Not only do they not have a paper trail, making any sort of double-checking impossible, but they run on un-audited proprietary software. The software has been known to crash in deployment. The solution? Reboot it.

There is one thing which could be done to increase the accuracy of vote counting and the difficulty of vote fraud. Instead of creating a single paper ballot, create two, which go into two different bins, and are sent to two different vote counting agencies, which are run by two different political organisations.

Sadly, the current trend is in the exact opposite direction, with paper trails getting eliminated entirely. They're replaced by unpublished electronic protocols which we're simply supposed to trust. There is a very real possibility that in the near future every major election in the united states will be rigged.

Trust Metrics

I've been thinking about how to apply ciphergoth's new trust metric ideas, discussed in my last few entries, with negative certs for spam resistance. The two match up very well. When a bucket is full, in addition to dribbling out more positive water, it also dribbles out some anti-water to all of its negative certs. Anti-water can filter backwards until it's negated an entire bucket then flow backwards from there. This approach needs more polish, but I like its game-resistance properties.

I figured out an in some ways better way to do simple peer ordering. For each new inclusion, figure which peer has the greatest total sum weight pointing at it, then include that peer and move weight of all the peers which certify it onto that one, setting the weight to 1/numcerts * peerweight for each certifier. Unfortunately this removes the disincentive for certifying peers by replacing it with a strong incentive for certifying peers, since the more peers you certify the less your strength gets diluted.

More thought is required. I've figured out one nice straightforward criterion though. If the seed certifies two peers, and the first one certs x peers and the second one x+y peers, then they should get to alternately appoint includes until they've both selected x, then the y extras should get added at the end.

Math Puzzles

It's impossible to position three solid tori in 3-space in such a way that they're borromean linked without deforming them. Is it possible to position a larger number of solid torii such that the entire set of them is linked but no pair is?

How can you find the midpoint of two points using a compass only, no straightedge?

6 Aug 2003 (updated 8 Aug 2003 at 23:00 UTC) »
Ciphergoth's trust metric

Ciphergoth made a nifty web toy based on his new trust metric. It's gotten so popular in just two days that it can't handle the load. From this and Friendster, it seems that it's extremely easy to get lots of users if you let them study their friends neigborhood, but it's hard to handle all the load.

Thinking about the first few people added to the metric, it's clear that ciphergoth's approach has some definite advantages over the one I gave in my last entry. Specifically, once you're done with the immediate friends list, the person who is a friend of a friend in the most ways should be selected next. My approach most definitely does not do that.

When selecting the first friend of a friend, what we have is essentially a voting problem. Ciphergoth's approach tries to find the best next person by assuming honesty, while my approach tries to reduce the amount of dishonesty by selecting the next person in as non-gameable a way as possible. Of these two tradeoffs, ciphergoth's seems to be the more appealing. This analysis indicates that maybe a condorcet style approach to picking the next person will achieve the best of both approachs. I'll have to think about that.

Minefield

Minefield is a game involving infinite numbers for two players.

Both players write down an infinite number (assuming the axiomatic basis ZF). They then both reveal what number they wrote down.

Both players now have a set amount of time to come up with a challenge to the other person's number. This can be done either by showing that the statement of the existence of the other person's infinite causes a contradiction, or by showing that your infinite is at least as large as the other person's.

If exactly one player shows that the other person's number causes an inconsistency, then that person wins. Otherwise, if exactly one person shows that their infinite is at least as big as the other person's, then that person wins. Otherwise the game is a do-over. In the case where someone should win by being larger, the opponent has an opportunity once they see the proof to challenge the consistency of the other player's number. This is to prevent the cheap trick of saying 'my number is inconsistent, therefore all statements are true, so it's at least as large as yours.

This game can be played, although it's a bit odd. Mostly I've thought of it as a way of getting a visceral sense of how very large infinites work.

Triumvirate

The 'degenerate' case of my game second best is actually the most interesting. Three players each write down either a 0 or 1, then all reveal what they wrote down. If they all wrote down the same number, then they all get one point. Otherwise, the player who wrote down the number which is in the minority gets three points. I'm calling this game triumvirate.

In triumvirate, two players can gang up on the third one by putting down different numbers, but then the third player can pick which one of them will win, and thus easily bully around either of them. I believe that triumvirate gets to the heart of what's difficult about multi-player, zero-sum games in much the same way that prisoner's dilemma gets to the heart of what's difficult about two-player, non-zero-sum games.

2 Aug 2003 (updated 12 Aug 2004 at 05:10 UTC) »
Backwards Compatibility

Extending protocols is very simple. You have a base level of functionality which is the core of the protocol, and a way of adding new information which is ignored in the current implementation. When later implementations are made, they can use the extra space to do protocol negotiation and use new features if both sides support it.

Well, duh. Unfortunately most people can't seem to grok this very basic concept.

For example, http 1.0 has quite nice extensible straightforward protocol negotiation built in, using headers, and a 1.0 client or server is very easy to implement. Rather than keep on adding optional features to 1.0 declared in headers, http 1.1 has now been created, and the push is to make everything run 1.1 (of course, the version number is an opaque string which there are no clear guidelines on how to parse and deal with). http 1.1 is a bloated mess, with all kinds of 'required' features, many of which aren't, and won't be, implemented properly in practice. This engineering debacle hasn't stopped certain people from claiming that they're 'creating the technology to enable the future internet' though.

Telnet has some basic protocol negotiation hacked in, which is used by competently written protocols like kerberos and srp. Unfortunately ssh, among many other problems, is its own protocol, forcing the end user to be aware of yet another TLA. ssh version 1 was hacked together amateurishly for a variety of forgiveable reasons, so ssh2 was created to fix its problems. ssh2 has succeeded in having embarassing crypto breaks less frequently than ssh1, but the engineering decision was made that since it was done wrong the first time, it would keep being done wrong the second time, and it still doesn't work as a negotiated protocol on top of telnet. (Just because you're running a telnet server doesn't mean you have to accept sessions which are unencrypted. In fact telnet is very nice in making it possible to put up a human-readable error message when that happens.) Unsurprisingly, a very large fraction, if not the majority, of all remote terminal sessions still use unencrypted telnet.

The quality of phone reception has been limited by bandwidth for a while now. Since calls pass through multiple intermediary machines, it isn't possible to magically flip a switch and have all phone reception get better. However, if I'm speaking to someone two doors down on the same exchange, there's no reason we should be stuck at the old quality. It would be fairly straightforward to create a new voice quality format which only turned on if the entire line of equipment (including the end phones) supported it. This would require innovation by the telcos though, who account for their phone switching equipment as depreciating over the course of forty years, so don't expect it to actually happen. Phone reception will only get better when people switch to using voice over IP.

Trust Metrics

Paul Crowley came up with a nice trust metric. Unfortunately this one will sometimes cause someone's certs to not work at all if they cert more people, creating a strong artificial disincentive to certification. I've figured out a way of fixing this, and fixing the performance problems which result. Rather than pontificate about it at length, I'll just post example code, which is quite terse and straightforward.

```# certs is {node: [certed nodes]}
def rank(seed, certs):
numhits = {}
for key, value in certs.items():
numhits[key] = [0] * len(value)
def rank_single(current, passed):
if passed.has_key(current):
return None
passed[current] = 1
return current
cs = certs.get(current, [])
numhit = numhits.get(current, [])
nexts = [(numhit[i], i, cs[i]) for i in xrange(len(cs))]
nexts.sort()
for garbage, i, next in nexts:
result = rank_single(next, passed)
if result is not None:
numhit[i] += 1
return result
return None
result = []
while True:
next = rank_single(seed, {})
if next is None:
return result
result.append(next)
```

MineSweeper

MineSweeper3D is cool.

I would like to have a minesweeper engine which calculated the exact probability that each not yet revealed cell had a mine in it. This could be done reasonably for large boards using a neat memoization trick where you go a row at a time. Even better would be to make it so that each cell you clicked on didn't have a bomb in it, but your cumulative probability of winning got multiplied by the chances that there was a mine in that cell. In the end, your score would be the log of your winning probability. That would be fun to play, and very interesting to implement.

Life Patterns

Computer searches for life patterns have been going on for the last two decades and the results are quite astounding. I'm particularly enamored of the wickstretchers. Unfortunately I can't seem to find a pattern file for the wick stretcher which leaves a single diagonal line of cells.

BitTorrent home

Jacob Moorman contacted me after my last post about difficulties with SourceForge. The problems I have are being worked on, as detailed on this page. It appears that the problems will be resolved within a short enough time frame that switching to another CVS would cause more pain than it would alleviate (but not by a large margin). brondsem links to several other project hosting facilities.

Spam Stopping

I was talking with clausen and we came up with some interesting ideas for spam stopping.

Rubik's UFO

I came up with a nice solution to Rubik's UFO.

Busy Beaver Numbers

There's some very interesting recent work on busy beaver numbers. Computing bb(5) may be possible.

BitTorrent home

Sourceforge's CVS has been terrible recently. I would like to move BitTorrent's hosting somewhere else. Ideally to a place which is already hosting other things, has been doing so for a while, and is free.

I need the following -

• A CVS repository, with ViewCVS, globally available anonymous CVS, the ability to set up new accounts, and access control. This should go without saying, but CVS should update immediately, which sourceforge isn't doing any more. It should also be possible to easily download a whole repository tarball.

• Mailing lists which support moderation with more than one moderator, make the archives available online, do a reasonable job of keeping people from harvesting addresses, and give me easy access to the list of subscribed addresses so I can easily move it elsewhere later if necessary.

Anyone who would like to volunteer or suggest resources please mail me.

Random Picking

An interesting problem came up in BitTorrent development. There are n things, some of which pass and some of which don't. We would like to do a scan over all things and stop at the first one which passes. We could scan from the beginning, but that would lack an another property we want which is that each acceptable thing should have about an equal probability of being picked.

Scanning could be done randomly but that involves generating lots of random numbers, which can be very slow. I came up with a neat trick. Arrange the n objects into a list, pick an s less than n at random and a d less than n and relatively prime to n at random, then scan through (s + d * i) % n for each i < n.

What is the maximum possible bias towards or away from a particular object this technique can have? I think it works fine in practice.

Algorithm obfuscation

I realized the other day why my attempts to come up with simplistic invariants for circuit satisfiability problems were going absolutely nowhere.

Consider some algorithm for solving some problem. We will now generate an equivalent algorithm which is only slightly slower but whose operation is completely obfuscated. Select a secure hash function (we assume there are infinitely many of these, and they cannot all be summed up simply). Memory will instead of containing bits in the unobfuscated algorithm instead contain a single plaintext counter and many (count, bit) pairs. Whenever writing to memory, instead of writing out the bit you would have increment the counter by 1, then store (count, hash(count)[0] xor mybit). Memory can be read out by computing hash(count) xor memvalue. This completely and thoroughly obfuscates memory, to the point that I've decided to give up looking for a simple invariant to prove an absolute lower bound on runtime. Ah well.

21 Jun 2003 (updated 21 Jun 2003 at 02:55 UTC) »
Lost Mail

Due to technical difficulties, I lost some mail from last week.

Apache and BitTorrent

There's some interesting discussion as to whether Apache will come with the BitTorrent mimetype already configured.

New Puzzle

I came up with a new puzzle.

Snail Racing

I saw a very cute board game in a store the other day. It features a racetrack which six different colored snails move along. There is a single six-sided die to roll. All snails start at the beginning line, and a snail to move forwards is repeatedly selected by die roll. The game ends when a snail crosses the finish line.

It's clearly meant for very young children, and the box says that players try to guess which snail will win in the end, and it's a family game with no winners and losers. Natuarally, I immediately noticed that it would make a great prop for a cutthroat gambling game.

Snail racing, a game for two players.

Both players start by putting a fixed ante into the pool. Before each die roll, both players write down an amount of money. The amounts they wrote down are then revealed, and they each put the amount they wrote down into the pool. The player who wrote down the larger number (determined by coin toss in the case of a tie) gets to put a single token on a snail of their choosing. A snail is then advanced by die roll, and play continues with another round of writing down numbers. When a snail wins, all the money in the pot is divided among the two players proportionately to how many tokens each of them had on that snail.

Hexagonal Game Rules

There was an error in my analysis of game winning positions given in my last entry. Before explaining what the error was and why I've made a slight rules change, I'd like to recap the rules, since they're now considerably more understandable.

Game is played on a hexagonal board with hexagonal cells. Players alternate placing pieces of their color. At the beginning, one player puts down the first piece and the other player decides which color they want to play.

A player wins whenever they make any of the following configurations:

1. A single group which touches four or more edges

2. Two separate groups, one of which touches three adjacent edges and one of which touches three edges not all adjacent, and which share exactly one edge between them.

3. Two groups each of which span three edges and a third group which spans two non-adjacent edges not connected by either of the other two. The third group may touch more edges as well.

These rules are straightforward, and force there to be no draws. They also make winning require clear board domination, resulting in a game with much long-term positional play.

The error in my last post was that one of the winning configurations was a superset of another. To see where the difficulty comes from, compare the three following positions (see my last entry for notation):

1. ((1, 3, 5)) ((1, 2, 3), (3, 4, 5), (5, 6, 1))

2. ((1, 3, 5), (1, 2, 3)) ((1, 3), (3, 4, 5), (5, 6, 1))

3. ((1, 2, 3, 5)) ((3, 4, 5), (5, 6, 1))

In each of these positions player A is strictly better than in the previous one. In each case where there are two completed positions which are individually ambiguous as to who should win and in which player A is strictly better in one, I wanted player A should win in the former, and lose in the latter. This criterion can't be satisfied due to position #2 above. I decided to make position #2 a win for player B, mostly because that makes the rules much more succinct.

Rubik and Megaminx pun

A came up with a unified solution which applies both to Rubik's cube and Megaminx. It's a nice solution to either one even without that property.

Hexagon Game

The hexagon game I mentioned earlier is easier to win than necessary. When designing a game, one wants there to be no draws, but within that restriction you want it to be as difficult as possible to win, so as not to truncate interesting game play.

The new winning condition is that a player wins if they make a move such that after that if all the empty cells are filled in for the opponent then the opponent does not have any of the following:

• A single group which touches four edges

• Three separate groups each of which touch three edges

• Two separate groups each of which touch three edges and one of which touches three edges no two of which are adjacent

I'll now go over each of the specific winning configurations in detail and explain the reasoning behind them. My notation will be that the edges of the hexagon are numbered 1-6 going clockwise and that (a, b, c) describes a single group touching edges 1, 2, and 3. Multiple groups are grouped together to describe a player's position, so ((1, 3), (3, 5)) means that a single player has two groups, one connecting sides 1 and 3 and the other connecting sides three and five. To describe a whole board position I'll give two sets of groupings in a row, the first for player A and the second for player B.

Here are the winning configurations, not including rotations and reflections. Some entries will include two whose reasons for being winning are related. You may wish to get out two different colored pens and draw the actual diagrams.

((1, 2, 3, 4))

Consider the complete board ((1, 2, 3, 4)) ((1, 4, 5, 6)). This is rotationally symmetric, so it must be a winning configuration.

((1, 2, 3), (1, 4, 6))

Consider the complete board ((1, 2, 3), (1, 4, 6)) ((4, 5, 6), (1, 3, 4)). This is rotationally symmetric, so it must be a winning configuration.

((1, 2, 3), (1, 4, 5))

Consider the complete board ((1, 2, 3), (1, 4, 5)) ((1, 5, 6), (1, 3, 4)). This is symmetric about a line through the middle of sides 1 and 4, so it must be a winning configuration.

((1, 2, 3), (1, 3, 4), (4, 6))

Consider the complete board ((1, 2, 3), (1, 3, 4), (4, 6)) ((4, 5, 6), (1, 4, 6), (1, 3)). This is rotationally symmetric, so it must be a winning configuration.

((1, 2, 3), (1, 2, 4), (1, 5))

Consider the complete board ((1, 2, 3), (1, 2, 4), (1, 5)) ((1, 5, 6), (1, 4, 5), (1, 3)). This is symmetric about a line through the middle of sides 1 and 4, so it must be a winning configuration.

((1, 3, 4, 6)) and ((1, 2, 3), (1, 4), (4, 5, 6))

Compare the completed positions ((1, 3, 4, 6)) ((1, 2, 3), (4, 5, 6)) and ((1, 3, 4), (1, 4, 6)) ((1, 2, 3), (1, 4), (4, 5, 6)). Player A is strictly better in the first case, therefore A should win in the first case and B should win in the second case.

((1, 3, 4, 5)) and ((1, 2, 3), (1, 4), (1, 5, 6))

Compare the completed positions ((1, 3, 4, 5)) ((1, 2, 3), (1, 5, 6)) and ((1, 3, 4), (1, 4, 5)) ((1, 2, 3), (1, 4), (1, 5, 6)). Player A is strictly better in the first case, therefore A should win in the first case and B should win in the second case.

((1, 2, 3), (3, 4, 5), (1, 5, 6)) and ((1, 3, 5), (1, 5, 6))

Compare the completed positions ((1, 2, 3), (3, 4, 5), (1, 5, 6)) ((1, 3, 5)) and ((1, 2, 3), (3, 4, 5), (1, 5)) ((1, 3, 5), (1, 5, 6)). Player A is strictly better in the first case, therefore A should win in the first case and B should win in the second case.

I'm very happy with this game. There is a clear canonical winner in every position, and making any of the won positions happen is very subtle. It's missing the property that even if you kept playing after the game ended it would still be clear from the board position who the winner was, but that only happens with completely symmetric final positions, and having initiative play a strategic role may be a good thing.

Core Wars Rules

The rules to Core Wars could use some improvement. Specifically, there's way too much of a paper-scissors-stone effect with strategies. No fundamentally new approaches have been invented in years.

I think the cause of this problem is that vampires are too powerful. They preclude techniques such as self-healing programs.

Here is my proposed solution.

Each location on the battlefield has an alignment. Initially the starting locations for both sides are set to their alignment and the empty space is all set to neutral.

When a MOV is executed, the target of that MOV is set to the same alignment as the MOV command. Note that this may be different from the alignment of the thread which executed the command.

When a SPL is executed by a command which has different alignment than its executing thread, it acts as a noop. This is what gets the strength of vampires under control.

When any read operation is done on a location with a different alignment from the executing command, it always reads as DAT 0 1. Whenever ADD or any other command which affects state is executed on a location with a different alignment than the one being executed, it has no effect. Note that these rules apply regardless of the alignment of the thread performing the instruction. These rules are designed to furthur reduce vampire-like techniques.

I think my rule variant does a good job of getting vampires under control. The vampire technique still applies and is extremely important, but a single capture no longer kills you.

Book Review: Moneyball

I highly recommend Moneyball, by Michael Lewis.

Moneyball is a book about financial shenanigans in baseball How does that happen? The Oakland Athletics win completely disproportionately many games for their salary budget by evaluating players better and buying undervalued ones. Moneyball is a story of the triumph of science and reason over the superstitions of an entrenched beurocracy which kept the truth out for decades by branding it as heresy.

One part of Moneyball possibly inadventantly explains why it's such a compelling story. At one point the author asks two people with ivy league educations if they feel bad using their advanced degrees on something so trivial as baseball. They burst out laughing and ask 'You mean, as opposed to having a deeply meaningful job on wall street?' Lewis's book Liar's Poker, while just as well written and about far larger sums of money, has a subject which simply cannot compete with competitive sport as the basis for a compelling narrative.

Twisty Puzzle Reviews

I just posted some twisty puzzle reviews.

Someone told me that Y suffers from the corners hardly ever getting used, making the effective board size very small. A similar game which fixes this problem is to play on a hexagonal board, and the first player to complete a group which either connects two opposite or three non-adjacent sides (meaning (1, 3, 5) or (2, 4, 6)) is the winner. This game also has no draws, and makes the whole board important while maintaining the subtleties of Y. I wonder if anyone has thought of this game before.

The sourceforge stats for PHP-Nuke for this week look extremely fishy.

75 older entries...