Wednesday, February 20, 2013

HW3: Stability in Cooperative Games

We have discussed cooperative games, the core, the nucleolus, and excess. For this homework you will implement a simulation of agents participating in a cooperative game and acting selfishly to join their preferred coalition. The simulation will show how long it takes for the system to achieve a stable solution where no one agent has an excess.

Specifically, your simulation will have number-agents agents, all of which start out in their own coalition, that is, alone.

An agent can have any one of the colors: red, blue, black, green, cyan
An agent can have any one of the shapes: circle, square, triangle

These are assigned randomly on setup.

The value function v(S) is defined as: the number of different colors in the coalition + 3 - number of different shapes - (size of the coalition / 2).

Each time the 'go' button is pressed each agent will: check the value of the coalition where he joins one of the other existing coalitions, for all other coalitions. Of these, he finds the one with the highest value. If that value is bigger than the value of his current coalition then he will leave his current coalition and join the new one. In other words, each agent asks himself: "what would the value be if I joined this other coalition? what about this one? and this one? and so on to find the biggest value. If that value is bigger than his current coalition then he joins that coalition. If the biggest value is less than the value of his current coalition, the agent does not do anything.

The coalitions are represented as fully-connected graphs. That is, an agent has a link to all the other agents in his coalition, and to no one else.

You will then plot the number of agents that change coalition on each tick, the total number of coalitions over time, and a histogram of the current size of coalitions.

Anyway, all this is easier to see in a video:

Email me your finished program by Monday, March 11 @10am.

No comments: