This morning, I fixed a bug in the back-end parser of my extension of a Proof-Carrying File System (D. Garg) to include support for linear file access and revocation. I had changed the front-end to write out procaps (proofs of capability) in a slightly different format, and hadn't altered the MAC signatures to match. Fortunately, was an easy bug to catch.
I worked a bit on finding a bound on the correlated equilibrium of noisy load-balancing. Up to this point, I have shown that this game is not smooth (a la Roughgarden) and Aaron Roth has shown that the coarse correlated equilibria can be arbitrarily bad. So, we've decided to look at the simplest setting we can think of to try and bound the cost of the correlated equilibria: two machines, with each player costing 1 on their optimal machine and B on the other. In this instance, the correlated equillibria and the coarse correlated equilibria will coincide. Today, I tried breaking the expected sum cost of the players into four components: the expected cost of players playing on their optimal machine and those playing on their non-optimal machine (for each machine). Each of these I subdivided further into the cost each player of each type pays, which is the sum of the expected cost incurred by the other players on that machine plus the cost of that player. I'll post a link later when I get the TeX looking good.
Pranjal and I also talked a little about how smoothness is (and is not) related to stability. It looks like the weaker notion of stability (e.g., that all e-approx. equilibria fall within a d-ball of some nash equilibrium) might have some connections to smooth games. Unclear at the moment, but seems that lambda close to 1 would be the primary case where this would be interesting.
2 comments:
Okay, so in an attempt to understand at least your first two sentences: Roth shows that a course correlated equilibria can be arbitrarily bad, and you have shown that noisy load balancing is not smooth - what are the definitions of those two things? How much "space" is there between smooth and rough?
A coarse correlated equilibrium is a probability distribution of strategy profiles (think tuples of the moves all players can make at a point) in which no player has incentive to deviate from playing according to this distribution. Regular old correlated equilibrium is similar, only you assume that there is some "correlator" who tells each player privately what strategy they should pick for each round, and no player has incentive to do anything other than listen to this advice.
Smoothness is something else: it says you can make a smooth transition from any one state in the game to another. I don't have as much intuition to give on this notion, though I'm happy to type some math at you if you'd like to see what the formal definition is.
We're currently looking at whether a game can be neither smooth nor "rough" (and by "rough", I presume you mean that the coarse equilibria can be unboundedly bad w.r.t the optimal equilibria of the game) and still have some nice properties that generally fall out from smoothness. For example, this game's ratio between its worst Nash equilibrium and its best is bounded by k/p, where p is the noise in the game and k is the number of machines. If the game were smooth, this result would extend automatically to correlated equilibria, but since the game is not smooth, we're looking for some other reason why the game might evolve nicely (that is to say, best response play will quickly lead the system to a good state).
Post a Comment