Experiments in Behavioral Network ScienceCrucial InformationOverviewThe Graph Coloring GameSlide 5A Not Properly Colored GraphThe Consensus GameA Solved Consensus GameAn Unsolved Consensus GamePurpose of StudiesGraphs and SubgraphsExample of a First-Neighborhood SubgraphA Player’s View: ExamplePlayer’s View: DetailsGlobal Aspects of Game DesignDetails of User InterfaceSlide 17Status BarsProgression of a Single GameProgression of Entire SessionCompensation DetailsSome Aspects of PlayImportant NotesExperiments in Behavioral Network ScienceNetworked LifeCSE 112Spring 2007Michael Kearns & Stephen Judd2Crucial Information•The experiments take place tomorrow, Feb 16, beginning at 5 PM sharp. Please arrive a few minutes early.•The location is 207 Moore. Find out how to get there well in advance.•Go to the bathroom before you arrive.•You are responsible for showing up if you’re on the list. No excuses.3Overview•Experiments in collective problem-solving in network settings•Now in their third year–early efforts: pen-and-paper in-class exercises for several problems–have gradually become more systematic and ambitious–last year: graph coloring system, hefty cash payouts, scientific paper•Directly related to almost all class themes–we’ll discuss (and you will analyze) the results in due course•Our immediate agenda:–background and information for game players–system walk-through–compensation details–logistics, ground rules, etc.•Please ask questions if you have them!4The Graph Coloring Game•Each player controls a vertex•Player action is to choose a color from a fixed set•Graph is properly colored if:– for every edge, vertices at each end are different colors•Cellphone ringtones; specialization within an organization; scheduling•Player “goal”: –choose a color that is different from those chosen by all neighbors•Minimum number of colors required:–called the chromatic number of the graph–all coloring experiments will use exactly this many colors•Brief comments on coloring:–notoriously difficult computational problem (even centralized or approximate)–k-clique forces at least k colors, but constraints can be much more subtle5A Properly Colored Graph6A Not Properly Colored Graph7The Consensus Game•Somewhat the “opposite” of coloring•Each player controls a vertex•Player action is to choose a color from a fixed set•This time, goal is for all players to choose the same color•Player “goal”: choose a color that is the same as those chosen by all neighbors•A basic problem of coordination or deciding on a convention•Minimum number of colors required: 1–but to create a challenging coordination problem, we’ll give you many•Brief comments on consensus:–trivial centralized computational problem–and the system will prevent trivial solutions (first button, conventions…)8A Solved Consensus Game9An Unsolved Consensus Game10Purpose of Studies•We are interested in how people solve problems on networks...–As a group•“collective dynamics” --- coordination is important•search & navigation (Travers&Milgram, Kleinberg, Watts,…)•other problems?–With each person seeing only a small part of the graph•confusion due to limited view is important–Without coordinated, centralized strategies–Under differing network structures•course theme: how does network structure influence outcomes?–Under varying problem types•start with coloring and consensus; later sessions will examine other problems11Graphs and Subgraphs•Graph (a.k.a. Network)–set of nodes, set of edges that join some pairs of them–the nodes adjacent to a given node are “neighbors”•First Neighborhood Subgraph–one given node + all its neighbors–all the edges between those nodes•In all experiments, players will have first-neighborhood views–will not have global views of the network!–will also show you how many “other” neighbors your neighbors have•Rationale: “Maximum” plausible info available to individuals12Example of a First-Neighborhood Subgraphoverall graphsubgraph(of n8 and all its neighbors)13A Player’s View: Exampledisplaysubgraph14Player’s View: Details•Names of nodes have been removed–your neighbors will always be anonymous•The node the player controls is labeled “you”•Edges that connect to the larger graph:–have been removed–# of them shown in the node with a “+”•Edges from “you” to neighbors are black•Edges between your neighbors are red•Location of a node on the page indicates nothing!15 Global Aspects of Game Design•Global Graphs:–always connected–edges chosen randomly according to some generative model–details purposely withheld for now•1 node ↔ 1 player–as many nodes in the overall graph as there are players–each node has one controllable property–each player controls exactly one node–players are assigned to nodes in random, unbiased fashion•Game is always solvable–there is a solution where everyone can get paid on every game16 Details of User Interface•Player View–a graph of several nodes and edges, peculiar to you alone•first-neighborhood subgraph of one big network, in which you control one node. Your node is labeled with “you”. •You DO NOT see the whole network!–each node will take on a color. •Actions–several colored buttons; just click on them to change color–each button click will cause YOUR node to change color within 200 milliseconds. If it does not change, either the game is finished, or it is suspended, or there is a system problem. –if a problem persists, please raise your hand and tell us.17•status bars•graph panel•button barPlayer Interface18Status Bars•game progress bar: measure of global progress•game status bar: what’s happening•elapsed time bar: game ends when bar completes•your current payoff: your pay if game ends NOW•payoff definition: just words to remind you19 Progression of a Single Game•Your view appears; no buttons work•Supervisor says something; you ask questions•Supervisor starts the game; buttons become live•Players click, timer runs, solution detector runs•Game stops; buttons inactive again–time ran out–global solution found–supervisor suspended it due to some problem•Game panel disappears•Ending a game: –Any time a global solution is reached, game automatically ends•global solution: no “conflicts” anywhere