Task assignment with controlled and autonomous agents

We analyse assignment problems in which not every agent is controlled by the central planner. The free agents search for vacant tasks autonomously, guided by their own preferences. The central planner, aiming to maximise the total value of the assignment, must take into account the behaviour of the uncontrolled agents. We model this situation as an n + 1-player game played between n free agents and the central planner. We show that it is a weakly dominant strategy for the free agents to choose tasks according to their true preferences. Contrarily, the strategy of the central planner in the resulting Nash Equilibrium is highly complex – we prove that it corresponds to the solution of a mixed integer bilevel optimisation problem. Finally, we demonstrate how this program can be reduced to a computationally much more manageable disjoint bilinear program.