[EUMAS08] Coallitions and Coordination

Coallition Structure Generation: Dynamic Programming Meets Anytime Optimization
Just how to optimize coallition formation based on its utility. Nothing new, but the method used: an anytime algorithm (IP). He’s comparing with a previos work based on dynamic programming (IDP). The proposal is to divide the search space in subspaces and to add an upper and a lower bound. The subspaces are made by the number of agents in eachs group (f.i. [1,3] means all coallitions formed by one isolated agent and a group of 3). He adjust the behaviour of the algorithm between being IP or IDP. Good results…. but for 23 agents only!! Let’s try with 100. This solution is O(n^n).

Only a question: they’ve published a paper (about IDP)  with worse results than a previous one (IP) And they’re only comparing with themselves. I can’t do that, reviwers don’t allow me to do that.

Optimal Coalition Structure Generation In Partition Function Games
A question: what happen if the value of a coallition depends on the value of the rest of the coallitions? (that is: the partition function). There’re many example of real systems working in that way; economics (petrol, R&D coallitions or coordination of monjetary policies) and other areas.

Patterns:

  • positive externalities: when one coallition is formed all the rest increase their value
  • nevative externalities: when one coalition is formed all the rest decrease its value
  • super-additive: when one coallition is formed it increases its value
  • sub-additive: when one coallition is formed it decreases its value

and he consideres its combinations. He explains the algorithms used to create the coallitions, usgin the same algorithm that in the previous speech (anytime).

A problem with all that: how the utility is calculated for coallitions? I have no faith in utility.

From Agent Games Protocols to Implementable Roles
Problems:service composition at run-time. He shows an example about merchant delivery, and shows that protocols can content errors, that can be solve by taking into account roles to deal with invisible transitions. Ups, that’s the end and I haven’t the point :-( I have no idea what he is talking about.

Adaptation in a P2P Scenario with 2-LAMA
Jordi explains that MAS organization can be adapted by using a layer of specialised agents in charge of supervise the systen. Itis applied in a P2P environment. The organisation is formed by a set of roles, protocols and norms. Agents are organised in two levels: Domain-level (DL) and Meta-level (ML).

Tos test it, they’ve used a modified (simplifies) version of BitTorrent protocol. Domain-level agents are organised in clusters and each cluster is supervised by an assistant in a Meta-level. Experiments have been organised in 3 arqchitectures: All4all, centralised and distributed. Good enogh results.

What’s the difference with P4P? I’ll look for it.

Blogged with the Flock Browser

Tags: ,