Quote: Original post by Kylotan
The real problem is finding which permutation of actors joins each group. Since multiple actors would join a given group, why would they bid against each other when there is room for both?

This is only on the first pass. As more passes go along, and more actors are add, or leave for something else, the group size could reach a nice equalibreum between getting the task done, and say, how fast it's done, or how well it's done with ? number of actors working on it.

My thinking is comming from economics. How does a business decide how many employees it needs? You can't just pay a whole bunch of people to do it, no matter how competent they are, not to mention how much resourses would go into having all those employees. This little system would regulate the size of the group, and it's ability to get the task done based on what the player decides to reward the actors in resources. This system would, again, make for interesting game play, for example, if the player created a task that required the highest of competence, but only gave little reward, that task wouldn't get done. The player would have to manage what they wanted to get done with the scarse resources available. Even games have scarse resources, and you need a way do manage it without micro managing it (as that would be to time consuming).

Of course, you may have to make changes to how the reward is divided up as well. If you divided it up equally, then it wouldn't matter what you tried, some other variable would take control and make things way to complex. The reason why business higher the right amount of employees (or near), and why parts and what not are made in the right amount without someone managing the whole thing is what Adam Smith called the invisible hand. And it's all based on what the individual actor values.

-Chris

Quote: Original post by easyBob0101
This is only on the first pass. As more passes go along, and more actors are add, or leave for something else, the group size could reach a nice equalibreum between getting the task done, and say, how fast it's done, or how well it's done.

Ok, in that case you're describing something that was pretty much already discussed above, with slight tweaks to the order based on these bids.

But if an actor can leave for something else, there's no guarantee of any equilibrium, as I mentioned above. Expected value changes significantly as the make-up of the group changes. So as you add the incompetent actors to a task - who rank as highly as anybody else under the system you describe - the more competent ones may leave for other tasks. But then on the next pass, it's no longer beneficial for the incompetent ones to be there either, so they will follow the competent ones. Unless there's a guarantee that this process will terminate, there's not much point using it.

Quote: Ok, in that case you're describing something that was pretty much already discussed above, with slight tweaks to the order based on these bids.

But if an actor can leave for something else, there's no guarantee of any equilibrium, as I mentioned above. Expected value changes significantly as the make-up of the group changes. So as you add the incompetent actors to a task - who rank as highly as anybody else under the system you describe - the more competent ones may leave for other tasks. But then on the next pass, it's no longer beneficial for the incompetent ones to be there either, so they will follow the competent ones. Unless there's a guarantee that this process will terminate, there's not much point using it.

Which is why you will need a reward system that works well. If an incompetent actor joins up to a high competence (and thus high reward) task, he will not get much of the reward, as he will not do much of the work (think of him as the janitor working at a power plant). This will only have a little effect on the next evaluation of value by the high competence actors, again, depending on reward. This in effect doesn't need to terminate until the task is done. If an actor stays on the task for one step, he has done some work. If he stays on for 5 steps, he has done more work, etc...

Let's write this out again:

The task only requires a competence of lets say 2 (out of 10, being the highest)

The first round, a high competence(8) actor picks this task, because at this time, this actor will be the only one doing the job, and can expect to get the whole reward. (The reward may be small for a group, but it may be large enough for one high competent actor to select at first)

The next round, an incompetent(1) actor picks it. Being a low reward task, this low competence actor will have a larger effect on the valuation of the high competent actor currently doing it. Why? Not because the high competence actor cares who he's working with, but because of the change in expected reward; no jelousy or anything. This would also change the valuation of the low competence actor the next pass, as he is the only one doing this task, he can expect, at this time, to get the whole reward, and stay at this low competence task.

This system will (I should say should) keep the lowbies to peon work (with possiblity of training up their competence if they do end up with a high competence task), while the researchers do research, so to speak. Again, this will require the player to manage resourses well, and not just throw everything into research, as the player will run out of competent researchers at some point, and any research past that point will be a waste of resourses.

-Chris

Quote: Original post by easyBob0101

Quote: Ok, in that case you're describing something that was pretty much already discussed above, with slight tweaks to the order based on these bids.

But if an actor can leave for something else, there's no guarantee of any equilibrium, as I mentioned above. Expected value changes significantly as the make-up of the group changes. So as you add the incompetent actors to a task - who rank as highly as anybody else under the system you describe - the more competent ones may leave for other tasks. But then on the next pass, it's no longer beneficial for the incompetent ones to be there either, so they will follow the competent ones. Unless there's a guarantee that this process will terminate, there's not much point using it.

Which is why you will need a reward system that works well. If an incompetent actor joins up to a high competence (and thus high reward) task, he will not get much of the reward, as he will not do much of the work (think of him as the janitor working at a power plant).

Ok, so it may work under that situation, but I would prefer to divide the reward equally.

I can also imagine problems where groups say, "well, he contributes next to nothing, but he will cost us next to nothing too", so they'll become indifferent to who joins the group. This in turn could result in almost completely arbitrary groupings, no?

Quote: Ok, so it may work under that situation, but I would prefer to divide the reward equally.

You may have trouble finding any other way to get the groupings to work themselves out then without hard coding a solution or having the player select who does what. Of course, you could use this system to get your groups setup and then when the task is complete, just divide up the reward equally.

Quote: I can also imagine problems where groups say, "well, he contributes next to nothing, but he will cost us next to nothing too", so they'll become indifferent to who joins the group. This in turn could result in almost completely arbitrary groupings, no?

I guess it depends more on the pool of available actors the player has and what tasks he wished to get done. A player with a bunch of incompetent actors shouldn't waste resources trying to research space travel, but could if he wanted to (for example). But that's something that makes the game a challenge.

I guess writing out more scenarios would be best, just to think about what would happen. Maybe throw some code together to simulate this to see how well it works for random tasks of different competence and reward levels.

Let's look at this: "well, he contributes next to nothing, but he will cost us next to nothing too"

Without causing my brain to split open thinking about it, maybe. But on the otherhand, a low competence actor may get more expected value from doing a low competence task as his reward for joining a high competent task is very low (I'm trying to think it out a couple of passes).

This isn't easy to just write out, an will most likely require a small program to simulate just this process to make sure it works/tweaks. You may also want to think of this from an emergent behavior stand point. It's hard to say what can come out of it.

I think you got me thinking.... :)
-Chris

And BTW, I'm just trying to help...Maybe spark an idea or two...Hopefully I didn't waste anyones time.

[Edited by - easyBob0101 on April 10, 2008 1:50:05 PM]

How is the chance of success calculated?

(sum of competence) / difficulty?

If so, then based off of expected reward, no actor wants any less competent people to help them, ever. The expected reward goes down in any such case. So if you are allowed to block...

On the other hand, if the chance is highly non-linear (ie, returns per competence go up rapidly near the difficulty threshold), having lesser competent individuals can help.

I suppose not being able to stop more people from joining is also important.

Let's suppose we have the threshold game -- you need the competence total, or others can freeload and/or you are screwed success wise.

Then for each task:

Sort all actors by competence. Sum up how many of the most-competent are needed to break the difficulty.
Divide (reward) / (# of actors needed). (I believe reward is fixed by task, not by actor, right?)

Do this for each task. Then, for each task, for each player, figure out if they prefer a different task.

Now if you don't want to use currency, you can make conclusions about a subset of games at this point. Any task which has an ideal set of actor that ideally want to do that task can be committed to it.

As it happens, this is guaranteed to exist. The task that returns the highest return per actor is guaranteed to be the task that is best for each participant. In the case of a tie, random.

Remove those actors and that task from the pot. Repair the missing actors from the remaining tasks, and repeat.

A sorted list of actors by competency costs O(a lg a) per task, for a total of O(t a lg a).

Finding the # of actors needed for each task, and dividing by reward, takes O(t * a).

Removing the actors that are taken by eliminating a task costs at most O(t * lg a) for each actor removed. As each actor is removed at most once, the grant total cost of removing actors is O(t * a * lg a).

Repairing a list once actors are removed costs, in total, a (or a * lg a) per task: keep a "high water mark" around that can be looked up quickly, and it only ever has to move at most a units before it fails.

So you can do all of this in O(T * A * ln A) steps, which should be fast enough. It does require that order of memory.

...

If you allow blocking by members on a task, and there is no non-linear threshold, then each actor will want to grab the task that they have the best benefit*competence/difficulty ratio, and lock everyone else out. Greedy bastages. :)

Quote: Original post by Kylotan
But if an actor can leave for something else, there's no guarantee of any equilibrium, as I mentioned above.

But you're forgetting that you have a closed system. There IS a Nash equilibrium for this system... it just may be that it's difficult to find. There are many ways you could avoid transient oscillations in the assignment dynamics... you could specifically test for them (and restart the solution, or perturb it yourself)... or add damping (as I previously indicated).

Quote: Expected value changes significantly as the make-up of the group changes.

Yes, but the change in expected value of a group is correlated with the change in another group that was involved in the switch. So a change gives you information about the reward/assignment dynamics of two groups. As agents switch between significant subsets of the groups you get information flowing throughout the problem space and (my intuition tells me) groups will stabilise. Yes you may get one or two actors who will give you some transient oscillatory behaviour, but I don't think this will be hard to weed out.

The best way to find out is to run it and see! If I'm wrong, you have my apologies for wasting your time! ;)

Cheers,

Timkin

Quote: Original post by NotAYakk
Let's suppose we have the threshold game -- you need the competence total, or others can freeload and/or you are screwed success wise.

Then for each task:

Sort all actors by competence. Sum up how many of the most-competent are needed to break the difficulty.
Divide (reward) / (# of actors needed). (I believe reward is fixed by task, not by actor, right?)

Do this for each task. Then, for each task, for each player, figure out if they prefer a different task.

Yep, my original plan was just like this, except instead of summing up the most competent, I summed up all people eligible for the task (ie. with some positive degree of competence).

Quote: Now if you don't want to use currency, you can make conclusions about a subset of games at this point.

I think you've talked about 'using currency' a couple of times but I still have no idea what that really means in implementation terms. I can imagine some sort of hypothetical currency based on competence level and a reverse auction where actors bid on the tasks they want, something like easyBob0101's suggestion?

Quote: Any task which has an ideal set of actor that ideally want to do that task can be committed to it.

As it happens, this is guaranteed to exist. The task that returns the highest return per actor is guaranteed to be the task that is best for each participant. In the case of a tie, random.

Remove those actors and that task from the pot. Repair the missing actors from the remaining tasks, and repeat.

But what about the situation where someone's best task never draws enough interest for it to be viable. eg. Task 1 fills up nicely, but Task 2's estimate relied on those people who are now doing Task 1. So someone who picked Task 2 over Task 3 and Task 4 is now allocated to Task 2, but in fact they will now receive no reward because Task 2 cannot be done. Task 2 is only guaranteed to the best for them if the estimate was correct, yes?

Quote: So you can do all of this in O(T * A * ln A) steps, which should be fast enough. It does require that order of memory.

It's ok, I'm not concerned about that aspect of complexity. Just in knowing exactly how to implement the algorithm, and in guaranteeing that it produces useful results.

Quote: Original post by Timkin

Quote: Original post by Kylotan
But if an actor can leave for something else, there's no guarantee of any equilibrium, as I mentioned above.

But you're forgetting that you have a closed system. There IS a Nash equilibrium for this system... it just may be that it's difficult to find. There are many ways you could avoid transient oscillations in the assignment dynamics... you could specifically test for them (and restart the solution, or perturb it yourself)... or add damping (as I previously indicated).

Unfortunately my understanding of game theory is minimal. Can you explain in layman's terms what makes this situation different from Rock/Paper/Scissors, which has no pure strategy that is a Nash equilibrium, only a mixed strategy - right? In this situation, since it's a non-repeated game, a mixed strategy isn't of any use, as I understand it. And I would figure that adding damping to a permanently oscillating system would result in purely arbitrary results?

Quote: As agents switch between significant subsets of the groups you get information flowing throughout the problem space and (my intuition tells me) groups will stabilise.

Ok, I'll give it a go. It will be interesting to see how the groups change on each iteration.

You could try to maximize an arbitrary function, such as "sum(ExpectedReward(A,T)^2 * Competency(A,T))". The squared and competency both help take care of freeloaders (higher individual rewards count more since adding 1 increases the contribution by 2X+1, and experts count more since freeloaders' competency will nullify their contributions).