International Workshop on
Optimisation in Multi-Agent Systems

In conjunction with AAMAS 2015
Istanbul, Turkey
May 5, 2015

This OptMAS workshop invites works from different strands of the multi-agent systems community that pertain to the design of algorithms, models, and techniques to deal with multi-agent optimization problems. We will also place a particular emphasis on DCR approaches, which include the modeling, formulation and solution of DCR problems, including both Distributed Constraint Satisfaction and Optimization Problems.


Important Dates:

  • February 18, 2015 - Extended Submission Deadline
  • March 9, 2015 - Acceptance Notification
  • March 15, 2015 - Camera-Ready Deadline
  • May 5, 2015 - Workshop Date


The number of novel applications of multi-agent systems has followed an exponential trend over the last few years, ranging from online auction design, through multi-sensor networks, to scheduling of tasks in multi-actor systems. Multi-agent systems designed for all these applications generally involve some form of very hard optimization problems that are substantially different from problems traditionally dealt with in other areas (e.g. industrial processes or scheduling applications). More specifically, the technical issues that multi-agent algorithm designers have to deal with include:

  • Open systems: algorithms to compute solutions to mechanisms that deal with different stakeholders, who may be self-interested or may have different computation or communication capabilities from their peers.
  • Distributed systems: algorithms that are across different system components, such as those that deal with agents that are tied to physical devices. This involves considerations of computation and communication constraints, and the possibility of failures of the components and/or communication links.
  • Privacy concerns: solving optimization problems while minimising the exchange of private information.
  • Solution quality bounds: problems requiring anytime and/or approximate algorithms with quality bounds.
  • Robust optimisation: techniques to deal with optimizations that are repeated with only slight changes in the input data and/or with unreliable input data, which require solutions that are robust to these differences.
  • Highly parallel architectures: e.g., multi-core, GPGPU, which deal with large-scale problems with massive data and task parallelism.

In particular, workshop organizers are seeking papers on the following (but not limited to) topics:

  • Distributed constraint optimization/satisfaction
  • Winner determination algorithms in auctions
  • Coalition formation algorithms
  • Algorithms to compute Nash and other equilibria in games
  • Optimization under uncertainty
  • Optimization with incomplete or dynamic input data
  • Algorithms for real-time applications
  • GPU for general purpose computations (GPGPU)
  • Multi-core and many-core computing
  • Cloud, distributed and grid computing

OptMAS places particular emphasis on distributed constraint reasoning (DCR) approaches, which include the modeling, formulation and solution of DCR problems, including both Distributed Constraint Satisfaction and Optimization Problems. DCR problems arise when pieces of information about variables, constraints or both are relevant to independent but communicating agents. They provide a promising framework to deal with the increasingly diverse range of distributed real world problems emerging from the evolution of computation and communication technologies. Example DCR-specific technical issues include:

  • unified frameworks for distributed constraint reasoning
  • complete and incomplete algorithms for solving distributed constraint reasoning problems
  • privacy issues in distributed constraint reasoning
  • problem solving in systems with self-interested agents
  • negotiation among self-interested agents
  • distributed constraint propagation and consistency
  • generation and formulation/modeling of distributed constraint reasoning
  • applications of distributed constraint reasoning


Participants should submit a paper (maximum 15 pages), describing their work on one or more of the topics relevant to the workshop. Alternatively, participants may submit a shorter paper (maximum 5 pages) presenting a research statement or perspective on topics relevant to the workshop. Accepted papers will be presented during the workshop and will be published in the workshop proceedings.

Authors are requested to prepare their papers by following the LNCS Springer instructions found at:

All submissions are conducted via the OptMAS 2015 EasyChair website:

Submissions should include the name(s), affiliations, and email addresses of all authors. We welcome the submission of papers rejected from the AAMAS 2015 technical program. The deadline for receipt of submissions is February 11, 2015. Papers received after this date may not be reviewed.

Submissions will be refereed on the basis of technical quality, novelty, significance, and clarity. Each submission will be thoroughly reviewed by at least two program committee members.

For questions about the submission process, contact the workshop co-chairs.


Session 0: Opening + Tutorial (8:30 - 9:40)


Session 1: Distributed Constraint Optimization I (9:40 - 10:30)


Robust Distributed Constraint Optimisation
Archie Chapman, Alessandro Farinelli and Sarvapali Ramchurn


Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems
Ferdinando Fioretto, Tiep Le, William Yeoh, Enrico Pontelli and Tran Cao Son

Session 2: Invited Talk by Milind Tambe* (11:00 - 12:00)

An Overview of Security Games Research 

Abstract: Security is a critical concern around the world, whether it is the challenge of critical infrastructure, protecting endangered species, forests and fisheries, suppressing urban crime or security in cyberspace. Motivated by this concern,  the security games research area focuses on optimizing the deployment of limited security resources; this research area is based on computational and behavioral game theory, while also incorporating elements of AI planning under uncertainty and machine learning. We have deployed security-games based decision aids for infrastructure security of ports and ferry traffic with the US coast guard (in the ports of New York, Boston, Los Angeles/Long Beach, Houston and others),  for security of airports and air traffic with the US Federal Air Marshals and the Los Angeles World Airport (LAX) police, and tested this framework for security of metro trains with the Los Angeles Sheriff's Department. This research has led to our founding a new startup company, ARMORWAY.


This talk will provide an overview of our previous work on infrastructure security, as well as our recent work on "green security games" that has led to testing our decision aids for protection of fisheries and protection of wildlife at sites in multiple countries, and on "opportunistic crime security games" for suppression of urban crime. I will discuss our use-inspired research in security games, including algorithms for scaling up security games as well as for handling significant adversarial uncertainty and learning models of human adversary behaviors.


(*) This is joint work with a number of former and current PhD students, postdocs, and other collaborators, all listed at: 

Session 3: Game Theory (1:00 - 2:40)


Designing Defender Strategies Against Frequent Adversary Interaction
Fei Fang, Peter Stone and Milind Tambe


Effectiveness of Game-Theoretic Strategies in Extensive-Form General-Sum Games
Jiri Cermak, Branislav Bosansky and Nicola Gatti


Handling Risk-aware Attackers in Security Games
Yundi Qian, William Haskell and Milind Tambe


Behavioral Minimax Regret for Security Games and Its Application for UAV Planning
Thanh Nguyen, Amulya Yadav, Francesco Delle Fave, Milind Tambe, Noa Agmon, Manish Jain and Richard Van Deventer


Session 4: Distributed Constraint Optimization II (2:45 - 4:00)


Forward Bounding on a Pseudo Tree for DCOPs
Omer Litov and Amnon Meisels


Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization Problems
Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, Enrico Pontelli and William Yeoh


Enforcing Soft Arc Consistency on DCOPs with Multiple Variables per Agent
Jimmy Lee, Pedro Meseguer and Wen Su

Session 5: Applications (4:30 - 5:45)


Distributed Multi-Period Optimal Power Flow for Demand Response in Microgrids
Paul Scott and Sylvie Thiebaux


Heterogenous Resources for Patrolling: Finding the Best Team on a Budget
Sara Marie Mc Carthy, Aaron Schlenker, Milind Tambe and Christopher Kiekintveld


Integrating System Optimum and User Equilibrium in Traffic Assignment via Evolutionary Search and Multiagent Reinforcement Learning
Ana L. C. Bazzan and Camelia Chira




Workshop Co-Chairs: