Task assignment with controlled and autonomous agents

• We introduce an assignment problem where some agents act autonomously.
• Many real-world problems fall under this assignment model.
• Matching theory is used to model the assignment of autonomous agents to tasks.
• The problem is stated as a bi-level mathematical program.
• We transform the problem into a computationally simpler bilinear problem.

We analyse assignment problems in which not every agent is controlled by the central planner. The autonomous agents search for vacant tasks guided by their own preference orders over available tasks. The goal of the central planner is to maximise the total value of the assignment, taking into account the behaviour of the uncontrolled agents. Such optimisation problems arise in numerous real-world situations, ranging from organisational economics to “crowdsourcing” and disaster response. We show that the problem faced by the central planner can be transformed into a mixed integer bilevel optimisation problem. Then we demonstrate how this program can be reduced to a disjoint bilinear program, which is much more manageable computationally.