Simons Science Series: Michael Kearns

Simons Foundation runs an invite-only talk Series on Science, including the new one on the block, i.e., Computer Science. Michael Kearns spoke on Sept 22 about his experiments with the behavior of economic agents (students) working on tasks (solving graph problems). I have heard parts of the talk before, but Michael is a superlative speaker, great in answering questions, and included new material.

He started the talk with saying his background was in theoretical computer science, and if you blurred your eyes a bit, you will see the vestiges of his background in the talk. He motivated network science: empirically, we observe many structures (small diameter, clustering) of networks in practice, why do each of these structures arise in the first place, but also, why do these coexist? He spoke about following games:

• Coloring. Each agent sees their node and neighbors, and given a palette of chromatic number of colors to use, Michael showed the video of play by play as players try to color the network. On simple graphs, they seem to converge on legal coloring in many cases.
  
• Consensus. Same setup as before. Agents have to agree on a color (detail: each agent has private random remapping of colors, so they cant just agree on a color a priori). Michael used this task to make the point that structure in networks by itself is not as discriminating as structure in conjuction with the task because coloring and consensus problems have different implications for the same structure. Q from audience: are there irrational, spoiler, outlier players who eg, pick a color and not change? A: Yes.
  
• Voting. Minority have greater incentive for R than B, can they impose their will on others and make all nodes go R? Baruch Schieber anecdote: Wireless providers incentivize a select few, who manage to implicitly convince others in their network to stay and not churn.
• Final example: Network Creation. Now agents can buy edges, but it reduces their payoffs. This video is harder to intuit, the results were hot-off-the-experimental-bench, and still needed more interpretation.
  

The overall talk was polished and held the attention of the \approx 60 people in the audience on fifth avenue, from Courant Inst, Columbia U, to IBM Research and elsewhere in NY. The talk went well over an hour, almost to the time when Michael had to run, catch a train. Some of us lingered and talked to David Eisenbud, Jim Simons and others. I think the foundation has done a great job of picking speakers (see the scan of the program), and am looking forward.

ps: Michael did not use the word "graph" anytime during the talk. :)