Teams of agents often have to coordinate their decisions in a distributed manner to achieve both individual and shared goals. Examples include service-oriented computing, sensor network problems, and smart devices coordination homes problems. The resulting Distributed Constraint Optimization Problem (DCOP) is NP-hard to solve, and the multi-agent coordination process non-trivial.

In this tutorial we will provide an overview of DCOPs, focusing on its algorithms and its applications. We will present an accessible and structure overview of the available optimal and suboptimal approaches to solve DCOPs. We will discuss recent extensions to the DCOP framework to capture agents acting in a dynamic environment and/or using asymmetric costs/rewards. Finally, we will discuss what are the suitable applications that can be modeled and solved as a DCOP, and conclude with the most recurrent challenges and open questions.


  1. Preliminaries
    • CSP and WCSP
    • Multiagent Systems
    • DCOP
    • Overview of Agents Interaction Graphs
  2. DCOP Algorithms
    • Overview and Categorization
    • Introduction to Search-based Algorithms
      • SyncBB
      • DSA and MGM
    • Introduction to Inference-based Algorithms
      • DPOP
    • Critical Overview of DCOP Algorithms
  1. DCOP Extensions
    • Asymmetric DCOP
    • Dynamic DCOP
  2. Applications for Cooperative Multiagent Systems
    • Meetings Scheduling
    • Traffic Flow Control
    • Smart Device Scheduling in Smart Homes
  3. Challenges and Open Questions

Time and Venue

Saturday, February 3    11:15 AM - 1:00 PM
Hilton New Orleans Riverside, New Orleans, Louisiana, USA
Room: TBA

Extra Material


  • Ferdinando Fioretto

    University of Michigan
    Ferdinando Fioretto is a postdoctoral researcher at the University of Michigan. His research focuses on multiagent systems, data privacy, and discrete optimization. His dissertation was awarded “the best AI dissertation” from the Italian Association of Artificial Intelligence in 2017.
  • William Yeoh

    Washington University St. Luis
    William Yeoh is an assistant professor in the Computer Science and Engineering Department at Washington University in St. Louis. His research interests include multi-agent systems, distributed constraint reasoning, and planning with uncertainty. He is an NSF CAREER awardee and was named in IEEE’s 2015 AI’s 10-to-Watch list.
  • Roie Zivan

    Ben Gurion University
    Roie Zivan is a senior lecturer (assistant professor) in the Industrial Engineering and Management Department at Ben Gurion University of the Negev. His research interests include multi-agent systems and distributed constraint reasoning. He won the best paper award at CP 2005.