Multi-Agent Coordination

Purpose

Allocate tasks to specialized agents with limited capacity at minimum total cost, and measure how far a greedy first-come rule is from the exact optimum.

Variables

• c_ijcost of doing task i with agent j
• x_ij1 if task i is assigned to agent j
• n, mnumber of tasks and of agents
• kcapacity of each agent, k = ⌈n/m⌉

Assumptions

• Costs are random integers from 1 to 9 generated from the seed.
• Every agent can take at most k tasks.
• All tasks are known up front and costs add up.

Model

Data this would need in practice

• Real cost per task-agent pair (time, error rate, price) estimated from history.
• Real capacities and working hours.
• Task arrival rates, if tasks do not all arrive at once.

Interpretation

The gap is the price of the simple rule. A small gap says the rule is good enough; a large one justifies coordination. Change the seed to see that the gap varies from case to case.

Limitations

• Static assignment ignores tasks that arrive later.
• The result is optimal only for these synthetic costs.
• Dependencies between tasks are not modeled.