Given by definition, an actor wants to maximize his expected payoff.
For the second part -- an actor's contribution to the task -- is there an expense involved in this? If it requires some expenditure of resources, length of time involved, risk proportional to contribution, ect., then an actor would want to minimize their contribution.

And if there is such an associated expense, can it be expressed in units similar to the payoff? If so, then maximizing (payoff - contribution) seems to make sense. It would also mean that there's a threshhold where contribution equals or exceeds the payoff, making some options not worth the effort.

On the other hand, if a given actor cannot directly alter their contribution value, then maximizing expected payoff would be the minimum number of actors capable of getting it done (at some acceptable confidence level). Everyone would want the best actors, and the actors would probably group together by contribution level: The best with the best would produce the smallest group, 2nd best with 2nd best the next group, etc. Filling a group might entail adding an underling or two to round out the percentage.

For a socialist view, these groups could then score the various tasks to see which constellation would give the greatest total gain (seems like a lot of work). For a hierarchy view, the big dogs could pick theirs first, and work down the food chain. And here I wonder -- do you suppose that the two arrangements would be reasonably close to the same?

[Edited by - AngleWyrm on April 8, 2008 8:43:21 PM]

Most of that is already factored into the reward estimate, which is the expected value, all obvious costs and benefits included.

"maximizing expected payoff would be the minimum number of actors capable of getting it done"... the problem is picking which actor to add to the group. Obviously the people already in the group know full well which person they can add to their greatest benefit. But that person might prefer the look of a different task altogether. Do we add that person, or not? Surely the correct answer is "not yet", at least until the other option can be weighed up.

The more I think about this, the more I consider that using a genetic algorithm might have worked ok... throw everybody into random groups, and run the GA until the groups stop improving. :) (EDIT: of course, that requires that I define the overall fitness, which is part of the problem. Doh.)

[Edited by - Kylotan on April 9, 2008 8:08:09 AM]

So if you don't want to add a currency for "you scratch my back, I'll do it later"... (ie, those who helped others more get first pick later)

Is capability uniform or not? If uniform, then you can have the most capable put forward proposals, then give actors a choice to join one or more of the proposals.

Repeatedly iterate, with each actor having a chance to switch to a proposal that looks good enough and like it will complete with a higher chance as the iterations continue.

Hmm: Are the actors supposed to be greedy? Or should they aim for global goodness?

I don't know what you mean by "is capability uniform?" I've stated that the actors have different competence levels at different tasks.

Nor is there anything for actors to 'propose' really, beyond offering to join or not offering to join. Perhaps you could elaborate on what you mean? Are you suggesting anything different to the 3rd paragraph of my 2nd post? If so, in what way?

The actors are supposed to make reasonable choices as to which group to go in, and I'm supposed to end up with groups wherever possible, and those groups should appear at least as reasonable as other potential permutations of the same actors. None of these need to be strictly optimal.

How many tasks and actors are commonly present?

Would it be unreasonable to produce a realistic example scenario, generate all possible permutations, save them to a file (CSV or the like) with various relevant statistics, and then manually rate each permutation (in an additional column, a value from 0 to 100, perhaps)? If there are too many actors/tasks, you could group similar actors/tasks and treat them as interchangable to eliminate permutations where only similar actors/tasks exchange places.

Something like that might help you better define a global fitness function. Induction can be much easier with an actual concrete set of samples to generalize from.

PS: What method did you develop for assesing how interested a given actor would be in a given task?

To begin with I am assuming something like 10 tasks, 15 actors, different subsets of which are eligible for any given one of the tasks, and a typical requirement for 2 to 10 people on each task. I have no idea how many possible permutations that is, but I suspect it's too many.

The actors' interest is based on their expected value of participation, which in turn is based on an estimate of how the reward will be spread if an 'optimal' number of people participate. This optimal number is calculated on a per-task basis by calculating the average contribution of all the eligible people, and adding them one by one until the global maxima is found. Obviously this could be an underestimate if all the 'good' candidates get assigned elsewhere first, so there is the possibility of recalculating it if I wanted to go with a greedy approach that finalises one group before moving on to the next.

Even reward spread, regardless of contribution?

Rewards are the same regardless of actor?

Yes, a few posts up I said "The idea is that all members receive an equal share of the reward." The total reward available is arbitrary, and set on a per-task basis.

If we measure population fitness as the sum of everyone's expected value, then it is possible to score a permutation, and compare it against other permutations. It assumes the the good of the society is the goal.

If we measure the difference between a given actor's expected value for that permutation, and his most preferred expected value, then we can get an idea of how much that actor stands to gain or lose by doing it for 'god and country' or doing it 'because it's best for me'.

Seems like the "best" permutation would be the one that simultaneously minimizes the social-selfish difference, and maximizes the social score.

The ieal solution you desire is one in which no agent can improve their expected reward by switching to another group when no one else switches. This is the Nash equilibrium for the problem and it means that every participant's decision of which group to participate in is optimal given the decisions made by all other participants.

The Nash equilibrium ensures that individuals maximise their expected rewards in the currnt context, but it doesn't guarantee that the population has maximised its expected rewards, nor that an agent has achieved the maximum possible payoff they could (theoretically) achieve. Such determinations are beyond the capability of individual agents to influence unless you have an indefinite negotiation period. Even then, the dynamics of the assignment problem do not guarantee convergence to an optimal solution. You can force a convergence through appropriate damping (such as time pressure, a fixed negotiation deadline, cost to negotiate/tender, etc), but this necessarily constrains the search to a finite horizon within the space of possible solutions and again, you lose the 'global optimality' of the solution. The point of this then? That you shouldn't try to find a globally optimal solution... only one that is locally optimal for all agents given the negotiation constraints.

The best current way I see to solve your problem is in line with the complex systems approach, which is to put it back into the hands of the individual agents and run the solution as a simulation of the decision problem (as I have suggested previously). Give each agent the capability of chosing and some preferences over group size (which is a surrogate for risk stance).

Here's how I would do it...

First, if there are tasks that may start before the current batch of tasks are completed, add an additional task (let's call it DEFER) which represents the option for an agent to not participate in the current tasks in favour of another reward before this batch of tasks ends. They may not actually participate in this future task, preferring to yet again defer their decision, but it gives them a decision outcome in the current problem that has a finite expected reward and means some agents will choose not to participate in the current task as groups start filling up too much.

Start with a random seed of agents to tasks (including DEFER) and then allow each agent assigned and not assigned to make a choice about which task to go to. All agents make their decision at once given the current assignments. Agents should choose the task to move to that would maximise their expected reward given the current assignment of agents to tasks.

In this simple approach you are not guaranteed to converge on an stable assignment of agents to tasks... but you should be able to get something that looks reasonable within a few iterations. You can damp the assignment dynamics by adding a cost to change groups, or limiting the number of times an agent can change (staying doesn't count as a change).

I hope these thoughts help you to resolve your problem Kylotan. It's certainly been a problem that has dragged on for a while for you and it'd be nice to hear that you've found a viable solution.

Good luck with it!

Cheers,


Timkin