Monday, July 27, 2009

bacterial computation

This article in the Guardian is attracting attention; rather over-inflated claims on behalf of the ability of bacteria to solve hard computational problems... (I did not post any of the comments attached to that article, but they are fun to read.) Could swine flu turn out to be even smarter than E. Coli?

I am now posting from Athens, visiting Koutsoupias and Papadimitriou; the instructions that blogger provides for logging in are rather hard to read...

Wednesday, July 22, 2009

Balanced set systems

I've been trying to understand Scarf's core theorem, which says that if a coalitional non-tranferable utility game is balanced, then it has a non-empty core. In the context of transferable utility games, there is another definition of "balanced game" which should not be confused with the one for NTU games. Osborne and Rubinstein's book studies balanced TU games in some detail, but only briefly mentions balanced NTU games.

The definition (NTU case) uses the notion of a balanced set system, defined as follows...

Given a set N, suppose that C is a collection of subsets of N, i.e. C is a subset of 2N. Let C={C1,...,Cz}. We say that C is balanced if there are non-negative real numbers αi, one for each Ci, such that, for every element of N, the sum over all Ci of their α values is 1.

The above definition is used in Scarf's 1967 paper.

The def can also be characterized as follows: Associate each member of N with a coordinate in Euclidean space, in fact let's associate it with a point in space representing the unit vector pointing in the direction of that coordinate. More generally, associate any subset of N with the average, or center of gravity, of the points corresponding to the members of that subset. An equivalent definition of "balanced collection of subsets of N" says that the point corresponding to the entire set N should be a convex combination of the points corresponding to these subsets of N. (the equivalence is straightforward; it is pointed out in this paper and probably quite a lot of others.)

There's an alternative definition that requires that the αi should be positive, rather than just non-negative (e.g. this paper). This is not equivalent in terms of which set systems are balanced (but the definitions are indeed the same modulo their use in the definition of a balanced NTU game). Let's use the phrase "positively balanced" to refer to set systems where the αi can all be positive. To see how they differ, suppose N={1,2,3} and consider the subsets {1},{2,3},{3}. These subsets are balanced, using the α values 1,1,0 respectively. It is easy to see that {3} must be given the value 0, so that these sets are balanced but not positively balanced.

From a geometrical perspective, "positively balanced" seems rather unsatisfying since a set system that is balanced but not positively balanced, is from the perspective of the αi, nevertheless arbitrarily close to being positively balanced. I am wondering if there is some nice alternative combinatorial characterization of positively balanced set systems. On the other hand, for set systems that are not balanced (under the original definition) the set of all non-negative weighted sums of their corresponding points in space, is presumably bounded away from the average of all the points. Maybe it's interesting to ask how close you can get? (My guess: for N={1,2,...,n}, take the n-1 subsets N-{1}, ..., N-{n-1}; these are not balanced; but give each one αi=1/(n-2), so for each i< n you get a total of 1, and for n you get a total of (n-1)/(n-2); pretty close to the all-ones vector.)

Wednesday, July 15, 2009

playing with javascript

One thing missing from Facebook's "shite gifts for academics" is "web page of colleague who has just discovered javascript". Here is a modest example - my reason for learning javascript is partly because I teach a class on formal language theory, and thought it would be useful motivational material to show the students how javascript lets you use regular expressions to verify user input to a web page. And, I wanted to improve the functionality of COMSOC's program page, although by now I guess that collection of papers is yesterday's news.

BTW, another missing gift is "invitation to review paper by unspecified authors that requires you to log on to the publisher's web site using a hard-to-remember user name" - I recently got one of those, but not via Facebook.

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).