Optimal Temporal Decoupling in Multiagent Systems

When agents need to interact in order to solve some (possibly common) problem, resolving potential conflicts beforehand is often preferred to coordination during execution. Agents may lose some flexibility, but their course of actionwill be more predictable and often also more efficient, obtaining a socially optimal outcome instead of a local optimum. One way to resolve conflicts beforehand is to give extra constraints to each of the agents such that when they allmeet these constraints, the resulting execution is conflict-free. A set of constraints that meets this requirement iscalled a decoupling of the original problem; if it also maximizes the social welfare (i. e. the sum of the valuations ofall the agents), it is called optimal. Representing interestingmultiagent problems as a constraint problem, we show thatfinding an optimal decoupling is at least as hard as finding a solution for the constraint problem. We therefore focus on a constraint problem that is efficiently solvable, butstill very relevant and interesting in the context of multiple agents executing their actions, i. e. the Simple TemporalProblem (STP). Two more technical results, then, are thatwe resolve the open question whether finding an optimal decoupling of the STP is NP-hard (it is), and if all agents havelinear valuation functions, this decoupling problem can besolved efficiently.

Authors

• L
• eacute; on Planken
• Mathijs de Weerdt
• Cees Witteveen

Keywords

• Optimal Decoupling
• Temporal Decoupling Problem