Fairness-Aware Performance Evaluation for Multi-Party Multi-Objective Optimization

Zifan Zhao; Peilan Xu; Wenjian Luo

cs.NEJan 30, 2026

Fairness-Aware Performance Evaluation for Multi-Party Multi-Objective Optimization

Authors: Zifan Zhao, Peilan Xu, Wenjian Luo

Organizations: School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Institute of Cyberspace Security, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China

Abstract

In multiparty multiobjective optimization problems, solution sets are usually evaluated using classical performance metrics, aggregated across DMs. However, such mean-based evaluations may be unfair by favoring certain parties, as they assume identical geometric approximation quality to each party's PF carries comparable evaluative significance. Moreover, prevailing notions of MPMOP optimal solutions are restricted to strictly common Pareto optimal solutions, representing a narrow form of cooperation in multiparty decision making scenarios. These limitations obscure whether a solution set reflects balanced relative gains or meaningful consensus among heterogeneous DMs. To address these issues, this paper develops a fairness-aware performance evaluation framework grounded in a generalized notion of consensus solutions. From a cooperative game-theoretic perspective, we formalize four axioms that a fairness-aware evaluation function for MPMOPs should satisfy. By introducing a concession rate vector to quantify acceptable compromises by individual DMs, we generalize the classical definition of MPMOP optimal solutions and embed classical performance metrics into a Nash-product-based evaluation framework, which is theoretically shown to satisfy all axioms. To support empirical validation, we further construct benchmark problems that extend existing MPMOP suites by incorporating consensus-deficient negotiation structures. Experimental results demonstrate that the proposed evaluation framework is able to distinguish algorithmic performance in a manner consistent with consensus-aware fairness considerations. Specifically, algorithms converging toward strictly common solutions are assigned higher evaluation scores when such solutions exist, whereas in the absence of strictly common solutions, algorithms that effectively cover the commonly acceptable region are more favorably evaluated.

Figures & tables

Panel of Figure 1 — Fig. 1: Visualization of fairness limitations of mean-based performance metrics in representative MPMOP cases. Decision and objective spaces for two representative MPDMP cases are shown, illustrating scenarios with and without a common Pareto-optimal region.

	$\mathrm{IGD_{A}}$	$\mathrm{IGD_{B}}$	$\mathrm{meanIGD}$	$\mathrm{HV_{A}}$	$\mathrm{HV_{B}}$	$\mathrm{meanHV}$
Case 1
$P_{1}$	0.73	0.73	0.73 $\approx$	3.90	3.90	3.90 $\approx$
$P_{2}$	0.14	1.36	0.75 $\approx$	5.42	2.06	3.74 $\approx$
Case 2
$P_{1}$	5.18	1.78	3.48 $\downarrow$	9.65	5.19	7.42 $\approx$
$P_{2}$	5.42	0.40	2.91 $\uparrow$	8.19	6.68	7.43 $\approx$

TABLE I : IGD and HV comparison for representative solution sets in Case 1 and Case 2.

Fig. 2 : Illustration of concession rates and the mutually acceptable region. $\gamma_{m}$ quantifies the normalized deviation from it. The intersection $\mathcal{A}$ indicates solutions meeting all DMs’ concession thresholds.

Problem	Metric	OptAll	OptMPNDS
MPMOP1	$\Psi_{\mathrm{NP}}$	$8.60\text{E-}10\pm 4.36\text{E-}08\ (--)$	$\pagecolor{lightgray}8.34\text{E-}02\pm 7.05\text{E-}02$
MPMOP1	meanIGD	$\pagecolor{lightgray}2.98\text{E-}01\pm 2.60\text{E-}02\ (++)$	$7.18\text{E-}01\pm 1.51\text{E-}01$
MPMOP2	$\Psi_{\mathrm{NP}}$	$2.81\text{E-}01\pm 2.06\text{E-}01\ (--)$	$\pagecolor{lightgray}8.65\text{E-}01\pm 1.32\text{E-}01$
MPMOP2	meanIGD	$\pagecolor{lightgray}1.00\text{E-}02\pm 5.10\text{E-}03\ (++)$	$4.62\text{E-}02\pm 9.28\text{E-}03$
MPMOP3	$\Psi_{\mathrm{NP}}$	$9.55\text{E-}05\pm 3.64\text{E-}05\ (--)$	$\pagecolor{lightgray}5.57\text{E-}01\pm 2.24\text{E-}01$
MPMOP3	meanIGD	$\pagecolor{lightgray}1.10\text{E-}02\pm 4.50\text{E-}03\ (++)$	$5.49\text{E-}02\pm 1.60\text{E-}02$

TABLE II : Comparison of OptMPNDS and OptAll under

\Psi_{\mathrm{NP}}

and meanIGD for MPMOP benchmarks (D = 2). Average ranks and Friedman test results are shown in the last rows. Significance markers vs. OptMPNDS: Wilcoxon rank-sum + Holm correction;

++

--

p<0.01

;

+

-

p<0.05

;

\approx

: n.s.

Fig. 3 : Representative solution sets of OptMPNDS and OptAll in the objective space of MPMOP1.

Fig. 4 : Evaluation scores

\Psi_{\mathrm{NP}}

of OptMPNDS and OptAll under varying concession thresholds in no common solution scenarios of MPMOPs.

Fig. 5 : Representative solution distributions of OptMPNDS and OptAll in the decision space of MPMOP12 and MPMOP13.

Problem	Algorithm	Jain $\uparrow$	Gini $\downarrow$
MPMOP12	OptMPNDS	0.8440	0.2150
MPMOP12	OptAll	0.9350	0.1318
MPMOP13	OptMPNDS	0.7231	0.3094
MPMOP13	OptAll	0.7722	0.2716

TABLE III : Fairness-oriented comparison of the final solution sets in MPMOP12 and MPMOP13. Larger Jain’s fairness index and smaller Gini coefficient indicate a more balanced distribution of party-wise IGD values.

Problem	Metric	OptAll	OptMPNDS	OptMPNDS2	OptMPNDS3
MPDMP1	$\log\Psi_{\mathrm{NP}}$	$5.3668\pm 0.0007(--)$	$5.3721\pm 0.0028(\approx)$	$5.3726\pm 0.0019(\approx)$	$\pagecolor{lightgray}5.3727\pm 0.0026$
MPDMP1	meanIGD	$\pagecolor{lightgray}9.04\text{E-}01\pm 7.20\text{E-}02(++)$	$1.39\text{E+}01\pm 1.60\text{E+}00(\approx)$	$1.36\text{E+}01\pm 1.10\text{E+}00(\approx)$	$1.36\text{E+}01\pm 1.50\text{E+}00$
MPDMP2	$\log\Psi_{\mathrm{NP}}$	$5.3744\pm 0.0008(--)$	$5.3782\pm 0.0034(\approx)$	$\pagecolor{lightgray}5.3790\pm 0.0039(\approx)$	$5.3777\pm 0.0033$
MPDMP2	meanIGD	$\pagecolor{lightgray}7.22\text{E-}01\pm 7.60\text{E-}02(++)$	$1.05\text{E+}01\pm 2.00\text{E+}00(\approx)$	$1.01\text{E+}01\pm 2.30\text{E+}00(\approx)$	$1.08\text{E+}01\pm 1.90\text{E+}00$
MPDMP3	$\log\Psi_{\mathrm{NP}}$	$5.3728\pm 0.0007(--)$	$5.3807\pm 0.0008(--)$	$5.3808\pm 0.0008(--)$	$\pagecolor{lightgray}5.3814\pm 0.0008$
MPDMP3	meanIGD	$\pagecolor{lightgray}1.18\text{E+}00\pm 6.00\text{E-}02(++)$	$7.73\text{E+}00\pm 4.70\text{E-}01(--)$	$7.64\text{E+}00\pm 4.70\text{E-}01(--)$	$7.28\text{E+}00\pm 4.90\text{E-}01$

TABLE IV : Comparison of OptMPNDS variants and OptAll under

\log\Psi_{\mathrm{NP}}

and meanIGD for MPDMP benchmarks (mean

\pm

std over 30 runs). Significance markers vs. OptMPNDS3: Wilcoxon rank-sum + Holm correction;

++

--

p<0.01

;

+

-

p<0.05

;

\approx

: n.s.

Fig. 6 : Critical difference plots of $\Psi_{\mathrm{NP}}$ and meanIGD under MPDMP1-12.

Fig. 7 : Evaluation scores $\log\Psi_{\mathrm{NP}}$ under varying concession thresholds in non common solution scenarios of MPDMPs.

Fig. 8 : Representative solution distributions of algorithms on decision space of MPDMP6, 8, 13, and 15.

Fig. 9 : Contour plots of $\Psi_{\mathrm{NP}}$ under symmetric concession thresholds and population dispersion.

Fig. 10 : Contour plots of

\Psi_{\mathrm{NP}}

under asymmetric concession thresholds.

Problem	metric	OptAll	OptMPNDS	OptMPNDS2	MPNNIA	MPAIMA
MPUAV1	Comparative	$3.50\text{E-01}\,(1.10\text{E-01})$	$5.70\text{E-01}\,(9.47\text{E-02})$	$6.20\text{E-01}\,(1.07\text{E-01})$	$6.11\text{E-01}\,(1.06\text{E-01})$	$\pagecolor{lightgray}7.41\text{E-01}\,(1.23\text{E-01})$
	Absolute	$1.22\text{E+04}\,(3.84\text{E+03})$	$1.98\text{E+04}\,(3.29\text{E+03})$	$2.16\text{E+04}\,(3.73\text{E+03})$	$2.13\text{E+04}\,(3.68\text{E+03})$	$\pagecolor{lightgray}2.58\text{E+04}\,(4.28\text{E+03})$
	sumHV	$9.51\text{E+05}\,(2.16\text{E+05})$	$1.23\text{E+06}\,(1.69\text{E+05})$	$1.25\text{E+06}\,(1.80\text{E+05})$	$1.23\text{E+06}\,(1.77\text{E+05})$	$\pagecolor{lightgray}1.42\text{E+06}\,(1.63\text{E+05})$
MPUAV2	Comparative	$3.51\text{E-01}\,(1.05\text{E-01})$	$6.19\text{E-01}\,(1.09\text{E-01})$	$6.44\text{E-01}\,(1.37\text{E-01})$	$6.51\text{E-01}\,(1.51\text{E-01})$	$\pagecolor{lightgray}7.54\text{E-01}\,(1.27\text{E-01})$
	Absolute	$2.65\text{E+04}\,(7.90\text{E+03})$	$4.66\text{E+04}\,(8.25\text{E+03})$	$4.86\text{E+04}\,(1.03\text{E+04})$	$4.91\text{E+04}\,(1.14\text{E+04})$	$\pagecolor{lightgray}5.69\text{E+04}\,(9.58\text{E+03})$
	sumHV	$1.96\text{E+06}\,(4.23\text{E+05})$	$2.94\text{E+06}\,(3.43\text{E+05})$	$2.89\text{E+06}\,(4.63\text{E+05})$	$2.86\text{E+06}\,(5.27\text{E+05})$	$\pagecolor{lightgray}3.10\text{E+06}\,(3.61\text{E+05})$

TABLE V : Comparison of multi-party multi-objective optimization algorithms under

\Psi_{\mathrm{NP}}

and sumHV for MPUAV path planning benchmarks.

Fig. 11 : Solution distributions of comparative algorithms in the objective spaces of MPUAV5.

Explore similar work

May 17, 2026cs.AI

Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination

Multi-party multi-objective optimization problems (MPMOPs) require consensus among autonomous decision makers and therefore differ from flattened many-objective formulations. Existing runtime theory for multi-objective evolutionary algorithms is largely tailored to single-party Pareto-front approximation and does not directly explain common-solution search in MPMOPs. We investigate cross-party recombination in two representative settings. On MP-JCG, a pseudo-Boolean benchmark with an explicit gap region, we prove that a payoff-guided mutation baseline faces a gap-crossing bottleneck requiring

Θ(n^2)

expected fitness evaluations. In contrast, an analytical CPR-NSGA-II variant discovers both common Pareto-optimal solutions in

O(n\log n)

expected evaluations by directly assembling complementary prefix and suffix templates distributed across party populations. Comparing this with the flattened four-objective formulation F-JCG, our full-front coverage analysis illustrates the additional coverage burden introduced by flattening. For BPBOMST, the bi-party, two-objective-per-party specialization of the multi-party multi-objective minimum spanning tree problem, we develop a layered support-cover analysis. For each common Pareto objective vector, the symmetric average projection induces an auxiliary bi-objective MST instance, and suitable support representatives yield a

2λ

-common approximation cover with

λ\in[1,2]

. We further derive an instance-parameterized expected runtime bound for a representative-pool CPR-NSGA-II variant using edge-union recombination and uniform repair. This bound separates the effects of local auxiliary-front filling, cross-party recombination shortcuts, and edge-union repair ambiguity.

Xiaolei Fang, Peilan Xu, Wenjian Luo

School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China · Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies, Institute of Cyberspace Security, School of Computer Science and Technology, Harbin Institute of Technology, Shenzhen 518055, China.

Multi-Objective Optimization Pareto Frontier Quality-Driven Selective Mutation Runtime

Ask PDF

May 7, 2026cs.LG

Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

We study multi-objective multi-agent multi-armed bandits (MO-MA-MAB) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time-varying graphs. We formulate this emerging problem setting to address \emph{efficient learning}, measured by Pareto regret, and incorporate \emph{fair learning} as an additional goal, captured via social welfare. To measure efficiency, we formulate Pareto regret and develop \textsc{Pareto UCB1 Gossip}, whose novel exploration radius explicitly separates statistical uncertainty in Pareto-based inference from consensus error. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference-scalarized rewards and propose \textsc{Simulated NSW UCB Gossip}, which integrates preference-based reward simulation, gossip-based utility estimation, and UCB-style exploration. We prove that \textsc{Pareto UCB1 Gossip} achieves

\mathcal{O}(\log T)

regret and an instance-independent rate of

\mathcal{O}(\sqrt{T})

, while \textsc{Simulated NSW UCB Gossip} achieves an instance-independent regret bound of

\mathcal{O}(T^{3/4})

. This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence. Experiments show that our methods consistently outperform baselines, improving performance by approximately

100\%

and

50\%

in the efficiency and fairness settings, respectively.

John Wang, Mengfan Xu

University of Massachusetts Amherst

Stochastic Multi-Armed Bandits Game Theory Algorithmic Fairness Gossip Efficiency

Ask PDF

May 14, 2026cs.MA

Temporal Fair Division in Multi-Agent Systems: From Precise Alternation Metrics to Scalable Coordination Proxies

A plethora real-world environments require agents to compete repeatedly for the same limited resource, calling for a temporal notion of fairness judged across entire interaction histories. This paper advances the theory of temporal fair division by introducing Rotational Periodicity (RP), a family of lightweight metrics, alongside the ALT family of sliding-window measures, within a unified framework for repeated multi-agent resource competition. We formalise the Multi-Agent Battle of the Exes (MBoE) as a repeated fair division instance and establish Perfect Alternation (PA) as its canonical temporally fair solution, drawing connections to proportionality, envy-freeness, and n-periodic round-robin allocation. RP decomposes temporal fairness into two complementary sub-measures: Rotational Score (RS) and Waiting Periods Evaluation (WPE), achieving O(nu+n) time complexity versus the O(nu*n) of ALT, where nu is the episode count and n the agent count. Empirical evaluation across n in {2,3,5,8,10} reveals three findings. First, both RP and ALT expose a coordination failure invisible to traditional metrics: Q-learning agents perform worse than random policies by 10-73% on RP and 7-35% on CALT, while Reward Fairness remains misleadingly high (above 0.92 for n>=3). Second, RP achieves 12-25x computational speedup over ALT, growing with n. Third, the two families are complementary: ALT provides richer discrimination for small populations; RP scales reliably where ALT becomes intractable. Together they form a diagnostic toolkit for temporal fair division.

Nikolaos Al. Papadopoulos

University of Macedonia, Department of Applied Informatics, Thessaloniki, Greece

Multi-Agent Coordination Algorithmic Fairness Schedulers Boltzmann Policies Periodic

Ask PDF