Wednesday, July 08, 2009

Game theory and ad-hoc networks

I am wondering if this could be a growth area... so there's been some work at this intersection, e.g. this paper posted to arxiv (CS and Game Theory) on Tuesday 7th July. Ad-hoc networks are composed of nodes, which in a game-theoretic context would constitute the agents or players.

I recently read another paper "New strategies for Revocation in Ad-Hoc Networks" (link) which doesn't have a game theory spin; I took a look at it because it was reported on in the New Scientist, and it relates to general issues I'm interested in, networks of decentralised agents trying to reach an agreement (so maybe there's an element of social choice theory?) where there are good and bad agents, and the good ones have to avoid being misled by the bad ones... "revocation" means removing the bad agents from the system, or at any rate, "blackballing" them.

For a theorist the paper is a bit unsatisfying to read since it doesn't spell out a mathematical model of what's going on (in terms of how agents can communicate, and what they are trying to achieve). And perhaps there is no nice model that wouldn't rule out the sort of approach one would want to use in practice, or else rule out the sort of attacks that the bad agents are supposed to be capable of. From time to time, agents may observe other agents misbehave, and when that happens, the observing agent, assuming it is one of the "good" agents, would want to report on the "bad" (misbehaving) agent to the other good ones. However, it is apparently possible for a bad agent, or agents, to bear false witness, so care must be taken in how to process one of these accusations. The only advantage the good agents have, is that they are in the majority (much less than one-third of agents are assumed bad). The paper mentions Byzantine generals, but doesn't really discuss the relationship. It would be interesting to come up with a model and relate it to the ones in The Byzantine Generals Problem and maybe also the FLP paper (Impossibility of distributed consensus with one faulty process).

No comments: