computational lens notes

**from “theory of computation as a lens on the sciences”

ehud kalai talks about structural robustness in games: an equilibrium is robust if you can alter the game in various ways (there’s a technical definition of what these ways are that I can’t recall from memory, but it’s a rich class) and the equilibrium remains. The interesting result is something like,  in the limit of infinite players, all games have robust equilibria.

also introduces the cooperative/competative (“coco”) value for semi-cooperative games (games in which the players have different interests but can, outside of the game itself, make payments to each other, sign binding contracts with each other, etc). there’s a progression of solution concepts: von neumann minimax value for two-player zero-sum games (1928), nash equilibrium (1950) generalizes minimax value but loses a lot of the nice properties (uniqueness, efficiently computable, pareto optimal, etc.). for a two-player nonzero-sum game, the coco value decomposes the game into a zero-sum part and a cooperative part (if A and B are the payoff matrices for the two players, then the the cooperative part has identical payoffs {(A+B)/2, (A+B)/2} and the zero-sum part has opposing payoffs {(A-B)/2, (B-A)/2} which sum to the original payoff matrices) and just takes the maxmax value of the cooperative part (the largest entry in the matrix) and the minimax value in the zero-sum part. The intuition is that the players will sign a contract so that they will cooperate in the actual game to get the maxmax (best cooperative) value, but that the player with the weaker position will have to pay the player with the stronger position (i.e. the player favored by the minimax value) to get him to agree to this.

all of this is presented in the context of bayesian games, in which players don’t know the payoffs of other players (or have some other kind of uncertainty, not really sure of all the technical details - but wikipedia says signalling games can be formulated in this context)

papadimitriou: four vignettes

complexity of computing equilibria (“if your laptop can’t find it, neither can the market” - and it turns out that your laptop can’t find nash equilibria)

arrow-debreu theorem shows that under certain simplifying assumptions, notably convexity, everything in economics works out beautifully and prices are set so that the market clears and everyone is at a pareto optimal solution. but convexity is wrong - it forbids economies of scale (where the 10th unit is cheaper than the 9th). that makes everything much much harder.

price of anarchy - bounded at 4/3 by tim roughgarden (the best planned solution is at most 4/3 as good as the selfish solution). but apparently this applies to highway networks but not necessarily the internet for reasons I’m not entirely clear on. apparently it’s unbounded in some cases? but if you make some assumptions about traffic being routed by selfish routers that can charge prices to route traffic, then things get better?

mechanism design: the vickrey auction is the new max function.

roughgarden reponse to papadimitriou: several points, but the one I remember is that one lesson for CS is that it’s worth considering not just malicious adversaries (as in worst-case analysis) but rational adversaries.

les valiant talks about evolvability. it’s technical and I was groggy and missed lots of it. but, one takeway is that evolvability-learnable is a subset of QS (or SQ?) learnable (Kearns) which is a subset of PAC-learnable. and he got criticism for modeling evolution with a fixed environment when it’s really game-theoretic - of course his response was that he’s trying to explain the simple case first. the cool point he made at the very beginning was that we’ve evolved about 3 billion bits of DNA (or something like that) in 3 billion years, which suggests linearity -- but we ought to think that evolution should take exponential time. he’s trying to reconcile this.

Michael kearns talked about the experiments he’s been doing into social computation. says that normally people studying networks study the structure, not the dynamics. he’s taking ~36 people and putting them in a lab in front of networked pcs, where each person controls one node of a graph and can see the state of their neighbors, but not the entire graph. they are incentivized to solve some problem. for example, graph coloring (choose a color for your node which is different from your neighbors), consensus (choose the same color as your neighbors), and some other more economics-y problems which I can’t remember. he tried this with a bunch of different network structures: cycles, cycles with a few random chords (small-world), preferential attachment, etc. I missed some of the results, but one takeaway is that some problems which are very different in their traditional computational compexity, such as graph coloring and consensus (former is np-hard even to approximate, latter is utterly trivial), turn out to be similarly difficult when solved in this local, social sense. suggests a hypothetical “crowdsourcing compiler” which takes your problem, figures out which parts are best done by machines vs. people, and then how to structure/incentivize the human tasks so that they are done efficiently.

mark newman talked about network theory. networks are the same thing as graphs, mathematically speaking, but network theory is different from graph theory in that it studies the empirical and statistical properties of real-world networks, e.g. biological, ecological, social, chemical, technological, etc. a survey of a bunch of interesting phenomena:

human/social networks all tend to have positively correlated degrees (popular people are friends with other popular people, hermits with other hermits), while most other networks have anticorrelated degrees (internet hubs tend to connect mostly to non-hubs). this makes a visible difference in the structure of the graph; the former case gives a dense center while the latter gives a more star-like structure.

people measure reciprocity in directed graphs. internet link reciprocity is about 55%. friendship reciprocity is about 40%, which is really surprising, because we would tend to assume that friendship is a symmetric relation. but when people collect the data by asking everyone individually who their friends are, it turns out that there’s only a 40% chance that someone you identify as your friend will identify you back.

transitivity in mathematics means A->B, B->C implies A->C. in networks it is not a hard property but it is very often true to some degree; this is measured by the clustering coefficient, basically how many triangles there are in the graph. turns out real-world networks universally have much higher clustering coefficients (by orders of magnitude) than you’d expect in random graphs.

sociologists often want to know who are the most important nodes in a graph. degree is one measure of this, but it doesn’t tell the whole story, because who you’re friends with matters just as much as how many friends you have. so they use eigenvector centrality, which is essentially pagerank.

graph drawing is done using masses and springs: put masses on the nodes and springs on the edges, and let the system settle. he didn’t say this but I think the physics of this again involve eigenvectors - I should know this.

he gave a nice intuitive explanation of inference using generative models (presumably because he’s used to talking with sociologists), with linear regression as the example. for linear regression, we suppose our data lies along a line, with some noise, so we fit a line and then use the slope of that line to tell us something about the data. similarly, in his more complicated case, building a model for clustering in graphs (which is just EM with some poisson distributions describing how groups are generated and how they connect), he builds the model and then fits it to the data, and looks at the fit parameters to infer interesting things about the data, even if the model isn’t perfect (just as regression coefficients are still meaningful even if the data don’t lie in a straight line).

discussion question from elchanan mossel: in the 40s (?) a Hungarian sociologist noticed that in any group of 20 children there is either a group of 4 children, none of whom are friends with each other, or a group of 4 who are all friends with each other. he asked Erdos if this was a sociological or mathematical property, and they figured out that it was a mathematical property. to what extent are the things people currently study about networks mathematical vs. sociological properties?

Michael kearns says that everything he finds is sociological; they are very far from getting hard mathematical truths.

mark newman tells the story of milgram’s experiments with small-world networks, where milgram thought he had discovered this new sociological insight, but mathematics shows that as the size of a graph goes to infinity, the chance of it having a diameter greater than log n goes to 0; i.e. almost every large graph is a small-world graph.**