PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Objective Multi-Agent Decision Making: A Utility-based Analysis and Survey

Roxana Rădulescu, Patrick Mannion, Diederik M. Roijers, Ann Nowé

arXiv:1909.02964v1cs.MAcs.AIcs.LG

TL;DR

Multi-objective multi-agent decision making requires analysing conflicting objectives through user utility rather than single-objective policy optimisation. The paper develops a utility-based taxonomy spanning reward structures, utility functions, and ESR/SER criteria, and surveys applicable solution concepts and methods. It concludes that the field is structured but unevenly explored, with important differences between ESR- and SER-focused literatures and several open research problems.

  • Problem

    Most multi-agent systems optimise a single objective even though many real-world problems involve multiple conflicting objectives and, in multi-agent settings, potentially different user preferences.

  • Method

    The paper classifies multi-objective multi-agent decision problems by reward structures, utility functions, and ESR or SER optimisation criteria, then analyses solution concepts and surveys methods and applications.

  • Results

    The survey structures the field around utility-based settings and identifies applicable solution sets, solution methods, and research directions, while noting that many taxonomy settings remain under-explored.

  • Takeaways & Limitations

    ESR and SER are both appropriate in different execution contexts, so selecting between them depends on whether utility is determined by a single execution or average returns across repeated executions.

  • Takeaways & Limitations

    The literature has a large discrepancy between game theory’s predominantly ESR focus and planning and reinforcement learning’s predominantly SER focus.

Abstract

from arXiv · show

The majority of multi-agent system (MAS) implementations aim to optimise agents' policies with respect to a single objective, despite the fact that many real-world problem domains are inherently multi-objective in nature. Multi-objective multi-agent systems (MOMAS) explicitly consider the possible trade-offs between conflicting objective functions. We argue that, in MOMAS, such compromises should be analysed on the basis of the utility that these compromises have for the users of a system. As is standard in multi-objective optimisation, we model the user utility using utility functions that map value or return vectors to scalar values. This approach naturally leads to two different optimisation criteria: expected scalarised returns (ESR) and scalarised expected returns (SER). We develop a new taxonomy which classifies multi-objective multi-agent decision making settings, on the basis of the reward structures, and which and how utility functions are applied. This allows us to offer a structured view of the field, to clearly delineate the current state-of-the-art in multi-objective multi-agent decision making approaches and to identify promising directions for future research. Starting from the execution phase, in which the selected policies are applied and the utility for the users is attained, we analyse which solution concepts apply to the different settings in our taxonomy. Furthermore, we define and discuss these solution concepts under both ESR and SER optimisation criteria. We conclude with a summary of our main findings and a discussion of many promising future research directions in multi-objective multi-agent systems.

1 Introduction

The paper motivates multi-objective multi-agent systems by contrasting single-objective optimisation with real-world conflicting objectives, then frames compromises through user utility, ESR/SER criteria, and a taxonomy of settings and solutions.

  • Motivation: MOMAS represent each agent’s reward as a vector whose components capture performance on different, potentially conflicting objectives.This framing supports trade-offs in domains including energy generation, transportation, aviation, natural-resource management, and robotics.
  • Utility-based analysis: User utility functions map value or return vectors to scalar utilities, providing a basis for choosing and evaluating compromises.The paper notes that utility can sometimes be applied before solving the decision problem.
  • Optimisation criteria: ESR derives utility from individual policy roll-outs, whereas SER derives utility from expected outcomes averaged across multiple roll-outs.These criteria receive less attention in multi-agent settings than in single-agent settings.
  • Taxonomy: Multi-agent settings may involve different individual reward vectors and agent-specific utility functions, complicating the definition of solution sets.Fully cooperative systems commonly share team rewards, but general settings can involve conflicting preferences and reward structures.
  • Survey scope: The paper builds a taxonomy from reward structures, utility functions, and optimisation criteria, then uses it to review solution sets, solution methods, and open problems.The analysis works backward from execution to determine which solution concepts apply in each setting.
  • Motivating example: The Commuting MONFG illustrates the shift from scalar to vector payoffs by modelling taxi and train choices with conflicting cost and travel-time objectives.Its commuters may use different utility functions and evaluate outcomes under ESR or SER, depending on whether individual trips or averages matter.

2 Background

This section introduces multi-agent decision theory and multi-objective optimisation, emphasizing distributed, stochastic settings and user-utility-based evaluation. It distinguishes cooperative, competitive, and mixed reward structures and explains how execution assumptions determine ESR or SER optimisation.

  • 2.1 Multi-Agent Decision Theory: Stochastic games model states, joint actions, probabilistic transitions, and agent-specific reward functions whose outcomes depend on the joint action.Agents may observe the full state or only local views; partial observability extends the model but is excluded from this article’s main treatment.
  • 2.1 Multi-Agent Decision Theory: Policies select actions probabilistically from states, and in discounted infinite-horizon settings are optimised through expected discounted long-term rewards.The joint policy, initial-state distribution, discount factor, and timestep rewards determine the value being optimised.
  • 2.1 Multi-Agent Decision Theory: Multi-agent systems distribute multiple agents across a common environment, supporting scalability and fault tolerance while allowing cooperative, competitive, or mixed behaviour.Learning is difficult because environments are complex and stochastic, while multi-agent settings introduce non-stationarity, resource-sharing constraints, coordination, and conflicting goals.
  • 2.1 Multi-Agent Decision Theory: Multi-agent decision problems are commonly classified as cooperative, competitive, or mixed according to how agents’ reward functions relate.Cooperative systems share rewards, competitive systems oppose agents’ interests, and mixed games impose no restriction on reward definitions.
  • 2.2 Multi-Objective Decision-Making: Utility functions map vector-valued outcomes to scalar user utility, making them central to selecting and evaluating compromises among multiple objectives.When alternatives are few and discrete, utility-based maximisation can be computed explicitly in reasonable time; continuous alternatives generally prevent guaranteed optimality.
  • 2.3 Multi-Objective Optimisation Criteria: SER applies utility after averaging returns across executions, whereas ESR applies utility to individual roll-outs before averaging.SER suits repeated execution where average return determines utility, while ESR suits settings where a single execution matters.
  • 2.4 Utility Functions: For linear utility functions, SER and ESR coincide because the weight-vector inner product distributes over expectation.The weights are non-negative and sum to 1, with each weight assigned to one objective.

3 Modelling Multi-Objective Multi-Agent Settings

This section models multi-objective multi-agent decision making with stochastic games and uses the general MOPOSG framework to organize special cases. It then builds a taxonomy around reward and utility assumptions and maps existing approaches onto restricted versions of the model.

  • 3.1 The Multi-Objective Stochastic Game Model: The MOSG is defined for n ≥2 agents and d ≥2 objectives using state spaces, joint actions, probabilistic transitions, and vectorial agent rewards.Each agent’s reward function maps state transitions and joint actions to a d-dimensional reward vector.
  • 3.1 The Multi-Objective Stochastic Game Model: Partial observability extends the MOSG to a MOPOSG, where agents receive observations and maintain beliefs over possible environment states.The article focuses on the fully observable MOSG while noting that its solution concepts generalise to partial observability.
  • 3.1 The Multi-Objective Stochastic Game Model: In the MOSG, each agent follows a state-conditioned stochastic policy and optimises an expected discounted vectorial reward under the joint policy.The framework permits agent-specific discount factors by replacing γ with γ_i.
  • 3.1 The Multi-Objective Stochastic Game Model: Each agent’s vectorial value function is projected to a scalar using that agent’s individual utility function.This connects the multi-objective game model to the utility-based analysis developed earlier.
  • 3.2 Special Case Models: The taxonomy focuses on reward and utility dimensions and maps literature approaches by restricting states, observability, individual rewards, or utilities.This provides a common framework for comparing multi-objective multi-agent decision-making settings.
  • 3.2 Special Case Models: MOPOSG is general enough to encompass many common decision models, including MOSG, MODec-POMDP, MOBG, MOMMDP, MONFG, MOCBG, and MOCoG.Restricting MOPOSG dimensions can recover models from single-agent, multi-agent, single-objective, and multi-objective literatures; setting n = 1 and d = 1 yields a traditional POMDP.
  • 3.2 Special Case Models: The taxonomy is intended as a reference for extending single-objective methods to multi-objective settings and applying multi-objective methods to corresponding single-objective models.This frames the survey as a bridge between established model classes and multi-objective approaches.

4 The Execution Phase

The execution-phase taxonomy distinguishes reward structures from utility arrangements, yielding settings in which agents may share rewards yet pursue different utilities. Individual utilities make joint-policy coordination essential, while individual rewards create harder strategic and informational challenges.

  • Taxonomy: The taxonomy distinguishes team versus individual rewards and team, social-choice, versus individual utilities, with ESR or SER applicable to every setting.Team rewards give agents the same value or return vector; individual rewards give each agent a different vector.
  • Team Reward: Team reward with team utility is the most common setting, where agents jointly optimise one utility under SER.This setting is typically treated as fully cooperative.
  • Team Reward Individual Utility: Shared reward vectors do not imply shared preferences: agents may value the same objectives differently and therefore prefer different joint policies.The MMORPG example illustrates differing preferences over experience, currency, and gear under SER.
  • Team Reward Individual Utility: Individual utilities require coordination because each agent controls only part of the joint policy and unilateral changes can produce poor outcomes for all agents.The paper identifies stable joint policies and negotiated agreements as two broad routes to coordination.
  • Individual Reward: With individual rewards, differing agendas can produce complex, non-convergent behaviour, while utility functions may not be common knowledge.The paper proposes truthful-revelation mechanisms or social-welfare functions as an open direction for optimisation.

5 Solution Concepts

Because agents’ strategies are interdependent, multi-agent optimisation typically seeks groups of outcomes that provide meaningful equilibrium or stability properties. The paper maps these solution concepts to the five settings in its taxonomy.

  • Solution Concepts: The section introduces solution concepts from multi-agent systems and multi-objective optimisation and relates them to the taxonomy’s scenarios.The mapping covers the settings identified for multi-objective multi-agent decision making.
  • Solution Concepts: Interdependent agent strategies make optimal behaviour difficult to identify, so analysis focuses on outcome groups that characterize forms of equilibrium.Figure 10 summarizes which concepts are relevant to each of the five taxonomy settings.

5.1 Policies

The paper distinguishes policy classes by stochasticity and time dependence, noting that multi-objective optimisation can make stochastic or non-stationary policies preferable. Mixture policies combine deterministic base policies between episodes.

  • Policy Types: Deterministic policies always select one action per state, whereas stochastic policies sample actions from a state-dependent probability distribution.Stationary policies depend only on state; non-stationary policies may also depend on time.
  • Policy Types: Multi-objective decision problems can benefit from stochastic or non-stationary policies under both SER and ESR.This differs from the common single-objective focus on deterministic stationary policies.
  • Mixture Policies: Mixture policies stochastically combine deterministic base policies, switching between them across episodes rather than within an episode.The approach can combine Pareto-optimal policies to satisfy user preferences, while intra-episode switching may be erratic and sub-optimal.
  • Mixture Policies: Mixture policies could feasibly transfer from single-agent multi-objective settings to team reward with team utility.That setting is sufficiently similar to single-agent multi-objective decision making for such methods to apply.

5.2 Coverage Sets

Coverage-set concepts represent policies that are optimal or potentially useful across utility functions, with the appropriate set depending on reward structure, utility shape, and ESR versus SER. Individual rewards remain a major boundary because preferences and policy outcomes diverge across agents.

  • Coverage Sets: A coverage set contains at least one optimal policy for each allowed utility function and excludes dominated policies under the relevant criterion.The goal is a compact set, but minimally sized coverage sets are difficult to construct because they are not unique.
  • Coverage Sets: Coverage sets are directly appropriate for team reward with team utility because all agents share rewards and one execution-phase utility function.The setting is fully cooperative and corresponds to the single-agent multi-objective rationale.
  • Coverage Sets: Under team reward with individual utility, a coverage set can provide negotiation alternatives if agents agree to execute a potentially optimal policy.This requires agreement, preferably contractual, among the agents.
  • Individual Rewards: Coverage-set construction does not trivially extend to individual rewards because a joint policy may be optimal for one agent but strictly dominated for another.Generalising coverage sets to individual-reward settings is identified as an open question.
  • Individual Utility: For individual utility, coverage sets may represent best responses to other agents’ behaviours, but a separate set for each behaviour combination can become infeasible.The approach may remain viable when opponents can be represented by a small behaviour set.
  • Convex Coverage Sets: A convex coverage set is optimal when all agents’ utility functions are linear, and linear utility makes SER and ESR equivalent.The convex hull may be undesirably large, especially for stochastic policies, motivating more compact convex coverage sets.
  • Pareto Coverage Sets: For monotonically increasing non-linear utilities, the Pareto front provides the undominated policies because Pareto-dominated policies cannot have higher utility.A Pareto coverage set can retain one policy for each distinct value vector while covering all admissible policies.
  • Pareto Coverage Sets: Pareto coverage sets can serve as negotiation inputs when agents cannot specify utilities numerically, alongside preference elicitation and uncertainty methods.Negotiation seeks compromises among alternatives with different objective values.

5.3 Nash Equilibria

Nash equilibrium captures joint policies where no individual agent can improve its return through unilateral deviation. In MOMAS, this concept is defined separately under ESR and SER, and nonlinear utilities can make the resulting equilibrium sets differ or disappear.

  • Nash equilibrium occurs when no agent can improve its own return by changing policy while other agents hold their policies fixed.
  • In cooperative MAS, convergence to an equilibrium does not necessarily yield a joint policy that maximises system welfare.
  • Under ESR, Nash equilibrium requires that no agent can increase the expected utility of its returns by deviating unilaterally.
  • Under SER, Nash equilibrium requires that no agent can increase the utility of its expected returns through unilateral deviation.
  • Nonlinear utility functions can alter the Nash equilibrium set, and under SER a Nash equilibrium need not exist even in multi-objective normal-form games.

5.4 ϵ-approximate Nash Equilibria

ϵ-approximate Nash equilibrium relaxes exact equilibrium by allowing deviations that improve an agent’s return by at most an additive ϵ. ESR and SER Nash definitions can be adapted using this tolerance.

  • An ϵ-approximate Nash equilibrium permits unilateral deviations only when they cannot increase an agent’s return by more than additive ϵ > 0.
  • ϵ-Nash equilibria can be viewed as regions surrounding Nash equilibria.
  • ESR and SER Nash equilibrium definitions extend to ϵ-Nash equilibria by subtracting ϵ from the right side of each inequality.

5.5 Correlated Equilibria

Correlated equilibrium incorporates communication or externally sampled private recommendations, allowing explicit dependencies among agents’ actions. In MOMAS, it is formulated for different utilities under both ESR and SER, but nonlinear SER games may lack such equilibria.

  • A correlated equilibrium models communication through private action recommendations or an external device that samples signals for agents.
  • A correlated policy is a probability distribution over joint actions, introducing explicit dependencies between agents’ behaviours.
  • A correlated equilibrium prevents an agent from gaining additional return by deviating from recommendations when other agents follow them.
  • Correlated equilibria apply when agents derive different utilities from reward vectors, including team-reward individual-utility and individual-reward individual-utility settings.
  • Under ESR, correlated equilibrium prohibits unilateral increases in expected utility following action recommendations.
  • Under SER, correlated equilibrium prohibits unilateral increases in the utility of expected returns following action recommendations.
  • With nonlinear utilities under SER, correlated equilibrium need not exist when expectations are taken over all possible correlation signals.

5.6 Coalition Formation and Stability Concepts

Coalition formation studies stable partitions of agents, using core, Nash, and individual stability concepts to constrain deviations. In multi-objective settings, differing agent utilities can eliminate stable partitions even when utility differences are arbitrarily small.

  • Coalition formation: Cooperative game theory studies coalition formation when agents can make binding agreements, with utilities derived directly from the coalition formed.
  • MC2FG model: An MC2FG assigns each coalition a vector-valued reward and each agent an individual utility function over those vectors.
  • MC2FG model: MC2FGs provide a minimal model for coalition cooperation where coalition value vectors are predictable but agents may prefer them differently.
  • Stability concepts: The goal of MC2FG coalition formation is a stable partition, with core, Nash, and individual stability representing different stability strengths.
  • Stability concepts: Core stability excludes blocking coalitions, while Nash and individual stability exclude deviations with progressively stronger acceptance requirements.
  • Multi-objective instability: For any positive n and 0 < ε < 1, an MC2FG with two criteria can admit neither a core nor individually stable partition despite arbitrarily similar linear utility weights.
  • Multi-objective instability: Stable partitions need not exist even when the number of objectives is smaller than the number of agents and utility-function differences are arbitrarily small.
  • Implications: The absence of guaranteed coalition stability may cause contract negotiations to continue indefinitely as agents repeatedly switch coalitions.

5.7 Social Welfare and Mechanism Design

The system perspective evaluates multi-agent outcomes through social welfare, while mechanism design seeks to align privately known agent utilities with socially desirable solutions. In multi-objective settings, articulated utility functions enable mechanisms for selected linear and non-linear cases.

  • Social welfare functions specify which outcomes should be maximised from the system perspective.Mechanism design uses this perspective alongside agents’ individual reward functions.
  • Multi-objective mechanisms are harder to design because agents may have complex individual utilities rather than simple scalar rewards.The difficulty arises when agents’ utilities are not directly known to other agents or the game owner.
  • Linear utility functions permit mechanisms that remain agnostic about weights by computing a convex coverage set and selecting weights afterward.The inner product with weights distributes over expectations, enabling posterior weight selection.
  • For threshold-based non-linear utilities, effective mechanisms can be designed when one objective is maximised subject to minimum values for others.Utility equals the primary objective when all thresholds are met and negative infinity otherwise; solutions can be found within reasonable time.
  • Adding positive and negative team-impact objectives can improve social behaviour in vector-valued decentralised planning, although the approach lacks strong guarantees.This is presented as an example of multi-objectivisation for better-functioning teams.

5.8 Other Solution Concepts

Beyond coverage sets, multi-objective multi-agent research uses Pareto-Nash and evolutionary-stability extensions, as well as cyclic equilibria for games without stationary equilibria.

  • These concepts form only a partial set of possible solutions for multi-objective multi-agent systems.The paper introduces them as additional solution concepts discussed in the literature.
  • The surveyed solution concepts extend single-objective equilibrium ideas to vector-valued games using vector domination.Weak and strong equilibria are proposed as Pareto-Nash Equilibria, alongside extensions of evolutionary stability.
  • Cyclic equilibria address games where no stationary equilibrium exists by repeatedly cycling through stationary policies without unilateral incentives to deviate.An ϵ-correlated cyclic equilibrium limits unilateral improvement at every stage to at most ϵ.

6 Algorithmic Approaches and Applications

Algorithmic work is organised around coverage sets, stability and equilibria, and mechanism design, with applications spanning coordination graphs, reinforcement learning, resource management, games, and traffic control.

  • The survey classifies algorithmic approaches into coverage-set methods, stability and equilibria methods, and mechanism-design methods using reward and utility structures.This taxonomy also organises the surveyed applications and related work.
  • Coverage sets: MOCoGs exploit factorised local rewards and are widely used to compute approximate Pareto coverage sets for cooperative multi-agent problems.Their local reward components may depend on small, overlapping subsets of agents; related models include MO-WCSPs and MOCOPs.
  • Coverage sets: Convex coverage sets often scale better than Pareto coverage sets as the number of agents increases, and may suffice when mixture policies are allowed.The surveyed work therefore proposes focusing on CCSs in many-agent problems and develops anytime approximations.
  • Coverage sets: Preference information can be integrated into AND/OR branch-and-bound to compute relevant coverage sets more efficiently than computing a Pareto coverage set.The approach assumes knowledge of the utility-function shape and users’ a priori expressed preferences.
  • Reinforcement learning: Reward shaping improves cooperative MOMARL performance in reported congestion and robot-coordination experiments, increasing learning speed and the quality of non-dominated solutions.Theoretical analyses also report preservation of Pareto relations under difference rewards and potential-based reward shaping.
  • Applications: Applications include energy-aware task allocation, flow systems, competitive games, traffic signals, smart cameras, watershed management, and robust weighted Nash equilibrium search.Reported methods include distributed reinforcement learning, co-evolutionary search, adaptive weighting, bargaining, and robust equilibrium approaches.

7 Conclusions and New Horizons

The paper structures MOMAS decision making around utility, solution concepts, and a sequence of practical steps, while identifying substantial gaps across optimisation criteria, preference modelling, and application settings. It highlights several largely unexplored directions, including ESR sequential decision making, SER game-theoretic models, interactive preference learning, and continuous or high-dimensional domains.

  • Open theoretical directions: The literature on non-linear utility functions and the relationship between ESR, SER, and MOMAS solution concepts remains limited.An initial SER analysis of multi-objective normal-form games showed that Nash equilibria need not exist.
  • Open theoretical directions: ESR sequential decision problems and SER game-theoretic models remain almost entirely unstudied despite both criteria being well-motivated and producing different theoretical and practical solutions.The paper notes that game theory mainly studies ESR, whereas planning and reinforcement learning mainly study SER.
  • Open methodological directions: Opponent-utility modelling faces multiple users, conflicting interests, possible strategic misreporting, and open questions about truthful elicitation or behaviour-only estimation.Preference-query methods can estimate utility functions under monotonicity information, but existing assumptions may not hold in multi-agent settings.
  • Field-wide gaps: The field remains fractured, with uneven attention across taxonomy settings and no standardised approach for completing all steps of a MOMAS application.The authors identify this fragmentation as a consequence of the field’s limited current maturity.
  • Practical workflow: The proposed workflow links model selection, taxonomy identification, environment and utility design, solution-concept selection, planning or learning, execution, and utility evaluation.The authors hope this sequence will make MOMAS theory easier to apply in practice.
  • Applications and future research: Parallel negotiation with learning or planning, and MOMAS methods for continuous or high-dimensional state and action spaces, remain important research opportunities.The survey also points to revisiting single-objective multi-agent problems using coverage sets, multi-objectivisation, and tunable multi-behaviour agents.
Loading 1909.02964v1…