Superrationality and network flow control

by alexflint 6y22nd Jul 201311 comments

18


Computers exchanging messages on a network must decide how fast or slow to transmit messages. If everyone transmits too slowly then the network is underutilized, which is bad for all. If everyone transmits too quickly then most messages on the network are actually flow control messages of the form "your message could not be delivered, please try again later", which is also bad for everyone.

Unfortunately, this leads to a classic prisoner's dilemma. It is in each node's own self-interest to transmit as quickly as possible, since each node has no information about when exactly an intermediate node will accept/drop a message, so transmitting a message earlier never decreases the probability that it will be successful. Of course, this means that the Nash equilibrium is a near-complete network breakdown in which most messages are flow control messages, which is bad for everyone.

Interestingly, some folks at MIT noticed this, and also noticed that the idea of superrationality (of Douglas Hofstadter origins, and the grandfather of TDT and friends) is one way to get past prisoner's dilemmas --- at least if everyone is running the same algorithm, which, on many networks, people mostly are.

The idea put forward in the paper is to design flow control algorithms with this in mind. There is an automated design process in which flow control algorithms with many different parameter settings are sampled and evaluated. The output is a program that gets installed on each node in the network.

Now, to be fair, this isn't exactly TDT: the end-product algorithms do not explicitly consider the behavior of other nodes in the network (although they were designed taking this into account), and the automated design process itself is really just maximizing an ordinary utility function since it does not expect there to be any other automated designers out there. But nevertheless, the link to superrationality, and the fact that the authors themselves picked up on it, was, I thought, quite interesting.

18