Paper deep dive
Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions
Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 7/9/2026, 6:29:38 AM
Summary
This paper introduces the Multidimensional Efficient Allocation (MDEA) model to study simultaneous efficiency when allocating indivisible items across multiple dimensions. It analyzes efficiency under Utilitarian Social Welfare (USW) and Egalitarian Social Welfare (ESW), establishing tight theoretical bounds such as a c/ℓ-approximation for maximizing Umax dimensions and a 1/ℓ threshold for approximate simultaneous efficiency. The study also defines and compares three multidimensional Pareto optimality notions (PO-agent, PO-USW, PO-ESW), characterizing their relationships and computational complexity, revealing that exact simultaneous efficiency is often impossible and degrades with the number of dimensions.
Entities (12)
Relation Signals (12)
Multidimensional Efficient Allocation (MDEA) model → studies → Egalitarian Social Welfare (ESW)
confidence 95% · ...and egalitarian social welfare (ESW), the minimum utility among agents.
Multidimensional Efficient Allocation (MDEA) model → studies → Utilitarian Social Welfare (USW)
confidence 95% · We study simultaneous efficiency under two fundamental welfare criteria: utilitarian social welfare (USW)...
1/ℓ threshold → bounds → simultaneous Emax (sEmax)
confidence 90% · Likewise, an α-sEmaxℓ allocation always exists for α=1/ℓ, but may fail for any α>1/ℓ...
1/ℓ threshold → bounds → simultaneous Umax (sUmax)
confidence 90% · An α-sUmax 1 1 allocation always exists for α=1/ℓ, but may fail to exist for any α>1/ℓ...
simultaneous Emax (sEmax) → exhibits → NP-hardness
confidence 90% · for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations.
Multidimensional Efficient Allocation (MDEA) model → introduces → simultaneous Emax (sEmax)
confidence 90% · we call such allocations simultaneous Umax (sUmax) and simultaneous Emax (sEmax)...
Multidimensional Efficient Allocation (MDEA) model → introduces → simultaneous Umax (sUmax)
confidence 90% · we call such allocations simultaneous Umax (sUmax) and simultaneous Emax (sEmax)...
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Many allocation problems are intrinsically multidimensional, since an item may contribute differently to several criteria, and optimizing a single aggregate objective can hide severe losses in other dimensions. We study how much efficiency can be guaranteed simultaneously when indivisible items have multiple attributes. To this end, we introduce the \emph{multidimensional efficient allocation} (MDEA) model, where each agent has an additive valuation in each dimension, and investigate simultaneous efficiency under utilitarian social welfare (USW) and egalitarian social welfare (ESW). Our results reveal a sharp worst-case frontier. For exact efficiency, maximizing the number of dimensions attaining the USW optimum admits a $c/\ell$-approximation for every fixed constant $c$, and this dependence on the number $\ell$ of dimensions is essentially unavoidable; for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations. For approximate simultaneous efficiency in every dimension, we identify a tight threshold of order $1/\ell$, showing that such guarantees always exist for both USW and ESW, while any asymptotically better dependence on $\ell$ is impossible, even for binary valuations. Finally, we introduce three natural multidimensional Pareto notions and characterize both their relationships and their computational complexity.
Tags
Links
- Source: https://arxiv.org/abs/2606.21346v1
- Canonical: https://arxiv.org/abs/2606.21346v1
PDF not stored locally. Use the link above to view on the source site.
Full Text
94,545 characters extracted from source content.
Expand or collapse full text
Chuo University, Tokyo, Japanhttps://orcid.org/0000-0001-5626-779XJST ERATO Grant Number JPMJER2301, JSPS KAKENHI Grant Number JP25K00137, Value Exchange Engineering, a joint research project between Mercari R4D Lab and RIISE (Research Institute for an Inclusive Society through Engineering). Indian Institute of Technology Kharagpur, Kharagpur, Indiahttps://orcid.org/0009-0005-6476-3060ANRF MATRICS Grant Number MTR/2021/000474 Indian Institute of Technology Kharagpur, Kharagpur, Indiahttps://orcid.org/0000-0001-5030-9645JST Sakura Science Exchange Program, JST LOTUS Programme Grant Number JPMJ25152681 Kawase, Bodhayan Roy, and Mohammad Azharuddin Sanpui [100]Theory of computation Design and analysis of algorithms Q. Open and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) 2016 2016 24–27, 2016 Whinging, United Kingdom 42 23 Simultaneously Efficient Allocation of Indivisible Items Across Multiple Dimensions Yasushi Kawase Bodhayan Roy Mohammad Azharuddin Sanpui Abstract Many allocation problems are intrinsically multidimensional, since an item may contribute differently to several criteria, and optimizing a single aggregate objective can hide severe losses in other dimensions. We study how much efficiency can be guaranteed simultaneously when indivisible items have multiple attributes. To this end, we introduce the multidimensional efficient allocation (MDEA) model, where each agent has an additive valuation in each dimension, and investigate simultaneous efficiency under utilitarian social welfare (USW) and egalitarian social welfare (ESW). Our results reveal a sharp worst-case frontier. For exact efficiency, maximizing the number of dimensions attaining the USW optimum admits a c/ℓc/ -approximation for every fixed constant c, and this dependence on the number ℓ of dimensions is essentially unavoidable; for ESW, even deciding whether two dimensions can be optimized simultaneously is NP-hard with binary valuations. For approximate simultaneous efficiency in every dimension, we identify a tight threshold of order 1/ℓ1/ , showing that such guarantees always exist for both USW and ESW, while any asymptotically better dependence on ℓ is impossible, even for binary valuations. Finally, we introduce three natural multidimensional Pareto notions and characterize both their relationships and their computational complexity. keywords: Fair Division of Indivisible Items, Multidimensional Evaluations, Utilitarian Social Welfare, Egalitarian Social Welfare, Pareto Optimality, Approximation Algorithms, NP-hardness 1 Introduction Resource allocation is a fundamental problem in economics and computer science [Amanatidis2022FairDO, reiter1962allocating, maskin1987fair, huesch2012one]. Classical models of indivisible-item allocation typically optimize a single welfare objective, such as utilitarian or egalitarian social welfare [aziz2022algorithmic, lipton2004approximately]. In many realistic settings, however, the quality of an allocation cannot be captured by a single scalar objective, because items must be evaluated along multiple dimensions. Such multi-criteria considerations arise in a wide range of applications. In cloud resource allocation, virtual machines or server slots may need to be assigned while accounting simultaneously for CPU capacity, memory, bandwidth, and energy efficiency. In personnel allocation, workers may be assigned to projects or service units, each of which needs a balanced mix of skills such as technical expertise, experience, communication ability, and domain knowledge. In such settings, optimizing one criterion in isolation can substantially degrade performance in others, while aggregating all criteria into a single score may obscure important trade-offs or stakeholder priorities. Since each dimension represents a distinct requirement, ignoring any one of them may lead to unacceptable outcomes. This inherent tension makes simultaneous efficiency fundamentally challenging. These challenges motivate the need to understand allocation mechanisms that perform well across multiple dimensions simultaneously. Our goal is to determine to what extent efficiency can be achieved simultaneously across several dimensions. This perspective is also reflected in recent work on fair allocation with multiple objectives. One line augments fair allocation by allowing the allocator, in addition to agents, to have preferences over outcomes [Bu2024fair, Barman2025FairDW, flammini2025fair]; another studies fair allocation with multidimensional preferences [Kawase2025SimultaneouslyFA]. These works show the importance of going beyond a single objective, but they focus primarily on fairness and are largely limited to one or two dimensions. In contrast, we study simultaneous efficiency in a model with an arbitrary number of dimensions, with the goal of characterizing the resulting dimension-dependent trade-offs, approximation guarantees, and impossibility phenomena. To capture this setting, we introduce the Multidimensional Efficient Allocation (MDEA) model. In MDEA, each item is described by ℓ attributes (or dimensions), and each agent’s valuations are additive within each dimension. By abstracting away from application-specific structure, MDEA provides a clean framework for studying the dimension-dependent trade-offs that arise when efficiency must be pursued simultaneously across many objectives. We study simultaneous efficiency under two fundamental welfare criteria: utilitarian social welfare (USW), the sum of agents’ utilities, and egalitarian social welfare (ESW), the minimum utility among agents. Ideally, we would like an allocation that maximizes USW or ESW in every dimension at once; we call such allocations simultaneous Umax (sUmax) and simultaneous Emax (sEmax), respectively. In one dimension, Umax is optimized greedily by assigning each item to an agent who values it most, whereas Emax is the classical max-min allocation problem and is already NP-hard for two agents with ternary valuations [fitzsimmons2024hardness]. This exact notion is already too demanding even in tiny instances. The following two examples show this for the two welfare notions we study. The first shows that maximizing total welfare in every dimension at once can be impossible, while the second shows that the same difficulty persists when the objective is to maximize the minimum welfare across agents in every dimension. Example 1.1 (Impossibility for sUmax). Consider two agents, two dimensions, and 2c+12c+1 items. Each item gives value 1 to agent 1 in dimension 1 and value 1 to agent 2 in dimension 2, with value 0 otherwise. The optimal USW is 2c+12c+1 in each dimension, but any allocation assigns each item to a single agent, so at least one dimension gets value at most c. Hence, no sUmax allocation exists for any c≥0c≥ 0. Example 1.2 (Impossibility for sEmax). Consider two agents, two dimensions, and 4c+24c+2 items. 2c+12c+1 items favor agent 1 in dimension 1 and agent 2 in dimension 2, and the other 2c+12c+1 swap these roles, each with value 1 for the favored agent and 0 otherwise. The optimal ESW is 2c+12c+1 in each dimension, but any allocation leaves some agent with value at most c in some dimension. Hence, no sEmax allocation exists for any c≥0c≥ 0. Together, these examples show that the obstruction is not specific to one welfare criterion: exact simultaneous efficiency can fail for both USW and ESW, although the source of failure is interpreted differently in the two cases. Rather than indicating a weakness of the model, this points to a more basic phenomenon: simultaneous efficiency across many dimensions is intrinsically limited in a general multidimensional setting. This makes exact simultaneous efficiency too strong a target in general and motivates several natural relaxations. One possibility is to maximize the number of dimensions in which the optimum is attained, asking how many objectives can still be satisfied exactly at the same time. A second possibility is to seek the best possible simultaneous guarantee in every dimension. Since a purely multiplicative relaxation is already ruled out by Examples˜1.1 and 1.2, we instead study guarantees that combine multiplicative approximation with an additive loss caused by a bounded number of high-impact goods, namely α-sUmax up to c goods (α-sUmaxc\,c) and α-sEmax up to c goods (α-sEmaxc\,c). This loss is charged only to goods whose contribution is unavailable to the relevant requirement, rather than to the optimum of a smaller instance. For Umax this means goods not assigned to a dimension-wise maximizing agent, and for Emax it means goods outside the relevant agent’s bundle. These notions are related in spirit to α-EF1 in fair division [amanatidis2023round, Barman2025FairDW], but here the goal is to characterize the optimal worst-case dependence on the number of dimensions. A third possibility is to study multidimensional Pareto optimality, which provides weaker but always meaningful baseline notions of efficiency. In particular, we consider three ways of comparing allocations: by checking whether every agent-dimension pair weakly improves (PO-agent), whether the vector of USW values across dimensions weakly improves (PO-USW), or whether the vector of ESW values across dimensions weakly improves (PO-ESW). Together, these perspectives let us quantify the frontier of what simultaneous efficiency can and cannot guarantee across multiple dimensions. Our results reveal a fundamental limitation: achieving efficiency across multiple dimensions requires significant trade-offs. In particular, guarantees degrade with the number of dimensions, and this degradation is unavoidable, highlighting a qualitative gap from the single-dimensional setting. 1.1 Our Results This paper presents the first systematic study of simultaneously efficient allocation when items are characterized by multiple attributes. We establish structural, algorithmic, and hardness results for exact, approximate, and Pareto-based notions of simultaneous efficiency across multiple dimensions. Throughout, we treat the set of dimensions as given exogenously; in practical applications, choosing or learning a useful low-dimensional representation is an important complementary modeling question, and our guarantees apply to the selected representation. Let n be the number of agents, m be the number of items, and ℓ be the number of dimensions. For exact simultaneous efficiency, we study how many dimensions can be optimized exactly under Umax and Emax. On the positive side, maximizing the number of Umax dimensions is polynomial-time solvable when either the number of items or the number of dimensions is constant (Section˜3.1), and admits a c/ℓc/ -approximation for every fixed constant c (Section˜3.1). On the negative side, even with two agents and binary valuations, the problem is NP-hard to approximate within a factor of 1/ℓ1−ϵ1/ ^1-ε (Theorem˜3.2), and maximizing the number of Emax dimensions is already NP-hard with binary valuations and two dimensions (Theorem˜3.4). This shows that the dependence on ℓ in the approximation guarantee is essentially unavoidable. We further show that, in the worst case, the fraction of dimensions in which Umax or Emax can be attained may be exponentially small in the numbers of agents and items (Theorems˜3.3 and 3.6), establishing strong impossibility bounds. For approximate simultaneous efficiency across all dimensions, we identify a sharp threshold around 1/ℓ1/ . An α-sUmax 1\,1 allocation always exists for α=1/ℓα=1/ , but may fail to exist for any α>1/ℓα>1/ (Theorems˜4.1 and 4.2). Likewise, an α-sEmaxℓ\, allocation always exists for α=1/ℓα=1/ , but may fail for any α>1/ℓα>1/ (Theorems˜4.4 and 4.5). Thus, the order 1/ℓ1/ is not an artifact of our analysis, but the best possible worst-case guarantee for simultaneous efficiency in every dimension of the chosen representation. Consequently, reducing attention to a smaller set of decision-critical dimensions directly yields stronger guarantees with the corresponding smaller value of ℓ . We also study related aggregate objectives: maximizing the sum of USWs over all dimensions is polynomial-time solvable (Theorem˜4.6), whereas maximizing the minimum of USWs or ESWs over all dimensions is NP-hard even to approximate (Theorems˜4.7 and 4.10). For multidimensional Pareto optimality, we define and compare three natural notions: PO-agent, PO-USW, and PO-ESW. We show that PO-USW implies PO-agent, while PO-USW and PO-ESW, as well as PO-agent and PO-ESW, are incomparable (Propositions˜5.1, 5.2 and 5.3). We also establish strong computational hardness: deciding whether a given allocation satisfies PO-agent is coNP-hard already in the single-dimensional case, and deciding PO-USW or PO-ESW is coNP-hard already in the two-dimensional case (Theorems˜5.4, 5.5 and 5.6). In addition, checking and computing PO-ESW remain hard even in the binary two-dimensional setting (Theorem˜5.7). A summary of the main results, including tightness information, is deferred to Table˜1 in Appendix˜A. 1.2 Related Work A line of work augments fair allocation by allowing the allocator, in addition to agents, to have preferences over outcomes [Bu2024fair, Barman2025FairDW, flammini2025fair]. These settings can be viewed as closely related two-dimensional cases of our model, with one dimension induced by the allocator (or market/social criterion) and the other by agents. Bu et al. [Bu2024fair] initiated fair allocation with allocator and agent preferences, Barman et al. [Barman2025FairDW] studied fair division with a common market valuation, and Flammini et al. [flammini2025fair] considered social-impact criteria. While these works emphasize fairness guarantees together with allocator objectives, we focus instead on simultaneous efficiency across multiple dimensions. Another related line studies allocation among groups of agents, primarily through fairness criteria [foley1966resource, manurangsi, SegalHalevi, Suksompong2017, Conitzer2019GroupFF, berliant1992fair, Aziz2019AlmostGE, segal2019, golz2025fair]. In these models, ν=ν1+⋯+νnν= _1+·s+ _n agents are partitioned into n(≥2)n 10000\ (≥ 2) groups, where group i has νi(≥1) _i 10000\ (≥ 1) members. When all groups have the same size, each group can be regarded as a single agent with one dimension for each member. A simple example is allocation to n parent-child pairs: each pair can be viewed as one agent with two dimensions, one for the parent’s valuation and one for the child’s valuation, so our framework captures the problem of balancing efficiency for parents and for children across all pairs. More generally, fixed-group allocation fits naturally into our multidimensional framework, while heterogeneous group sizes can still be embedded by padding smaller groups with dummy zero-valued members. Kawase et al. [Kawase2025SimultaneouslyFA] studied fair allocation with multidimensional preferences, focusing on fairness guarantees such as EF1, PROP1, and maximin-share-type notions. In contrast, the present paper studies efficiency: simultaneous welfare maximization, tight dimension-dependent approximation thresholds, and multidimensional Pareto optimality. Hence, while the models are closely related, the objectives and the resulting algorithmic and hardness questions are largely orthogonal. Our model is also related to multi-layered cake cutting [Hosseini2020FairDO, igarashi2021envy, Sanpui2026ProportionalAO, Cloutier2009TwoplayerEM, Nyman2017FairDW, Lebert2013EnvyfreeTM, kawase2025resource]. A key structural difference is that multi-layered cake cutting typically allocates different layers at the same position to different agents, whereas in our setting all dimensions of an item are assigned together. As a result, the underlying feasibility structure and the relevant efficiency trade-offs are different. Overall, our framework complements multidimensional allocation models that emphasize fairness or allocator objectives by focusing directly on simultaneous efficiency. 2 Preliminaries For a positive integer n, let [n]=1,2,…,n[n]=\1,2,…,n\. Let N=[n]N=[n] denote the set of agents, M=g1,g2,…,gmM=\g_1,g_2,…,g_m\ the set of indivisible items, and L=[ℓ]L=[ ] the set of dimensions. Each agent i∈Ni∈ N is equipped with a valuation function vi:M→ℝ+ℓv_i M _+ , which assigns to every item an ℓ -dimensional vector of nonnegative real numbers. We use vijk=vi(gj)kv_ijk=v_i(g_j)_k to denote the value that agent i assigns to item gj∈Mg_j∈ M in dimension k∈Lk∈ L. An instance of the MDEA problem is represented as (N,M,L,(vi)i∈N)(N,M,L,(v_i)_i∈ N). An allocation =(A1,A2,…,An)A=(A_1,A_2,…,A_n) is a partition of the items M (i.e., ⋃i∈NAi=M _i∈ NA_i=M and Ai∩Ai′=∅A_i∩ A_i = for any distinct agents i,i′∈Ni,i ∈ N), where each subset Ai⊆MA_i M is allocated to agent i∈Ni∈ N. The total valuation of agent i for her allocated set AiA_i is defined as vi(Ai)=∑gj∈Aivi(gj)∈ℝ+ℓv_i(A_i)= _g_j∈ A_iv_i(g_j) _+ . Specifically, the kkth dimensional value of agent i for the allocated set AiA_i is defined as vi(Ai)k=∑gj∈Aivijkv_i(A_i)_k= _g_j∈ A_iv_ijk. We call an instance of the MDEA problem binary if vijk∈0,1v_ijk∈\0,1\ for every agent i∈Ni∈ N, every item gj∈Mg_j∈ M, and every dimension k∈Lk∈ L. We call an instance identical if every agent has the same valuation function, i.e., v1=v2=⋯=vnv_1=v_2=…=v_n. For each dimension k∈Lk∈ L, define the maximum utilitarian social welfare as Umaxk≔max∑i∈Nvi(Ai)kUmax_k _A _i∈ Nv_i(A_i)_k. Similarly, define the maximum egalitarian social welfare as Emaxk≔maxmini∈Nvi(Ai)kEmax_k _A _i∈ Nv_i(A_i)_k. An allocation A is sUmax if its USW attains UmaxkUmax_k for all k∈Lk∈ L, and sEmax if its ESW attains EmaxkEmax_k for all k∈Lk∈ L. For an allocation A and dimension k, let Dk()=gj∈M:gj∈Ai for some i∈N with vijk<maxi′∈Nvi′jk. D_k(A)=\g_j∈ M:g_j∈ A_i for some i∈ N with v_ijk< _i ∈ Nv_i jk\. Thus, Dk()D_k(A) is the set of items whose dimension-k contribution to Umax is not fully realized by A. Equivalently, items outside Dk()D_k(A) already contribute their full possible value to dimension-k USW, so the shortfall from UmaxkUmax_k is supported only on items in Dk()D_k(A). For a nonnegative integer c, we further say that A is α-sUmaxc\,c if ∑i∈Nvi(Ai)k≥α⋅Umaxk−maxB⊆Dk():|B|≤c∑gj∈Bmaxi∈Nvijk _i∈ Nv_i(A_i)_k≥α·Umax_k- _B D_k(A):\,|B|≤ c _g_j∈ B _i∈ Nv_ijk (1) for all k∈Lk∈ L, and α-sEmaxc\,c if vi(Ai)k≥α⋅Emaxk−maxB⊆M∖Ai:|B|≤c∑gj∈Bmaxi′∈Nvi′jk v_i(A_i)_k≥α·Emax_k- _B M A_i:\,|B|≤ c _g_j∈ B _i ∈ Nv_i jk (2) for all i∈Ni∈ N and k∈Lk∈ L. These definitions do not compare the achieved welfare with the optimum of a smaller instance. Instead, they allow an additive loss charged to at most c high-impact goods that the allocation does not use for the relevant requirement. For Umax, these are goods in Dk()D_k(A); for Emax, the loss for agent i is charged only to goods outside AiA_i. These definitions are evaluated dimension-wise. For a fixed dimension k∈Lk∈ L, the additive term maxB⊆X:|B|≤c∑gj∈Bmaxi∈Nvijk _B X:\,|B|≤ c _g_j∈ B _i∈ Nv_ijk, with X=Dk()X=D_k(A) for Umax and X=M∖AiX=M A_i for Emax, selects up to c items with the largest contribution in dimension k, where each item is valued by the agent who values it most in that dimension. Thus, these notions capture robustness against a bounded number of influential indivisible goods that remain unavailable to the corresponding objective in each dimension. Moreover, we introduce related optimization problems: • Maximum Umax dimensions: max|k∈L:∑ivi(Ai)k=Umaxk| _A|\k∈ L: _iv_i(A_i)_k=Umax_k\|. • Maximum Emax dimensions: max|k∈L:minivi(Ai)k=Emaxk| _A|\k∈ L: _iv_i(A_i)_k=Emax_k\|. An allocation A is said to be PO-agent if there is no allocation B such that (i) vi(Bi)k≥vi(Ai)kv_i(B_i)_k≥ v_i(A_i)_k for all i∈Ni∈ N and for all k∈Lk∈ L and (i) vi(Bi)k>vi(Ai)kv_i(B_i)_k>v_i(A_i)_k for some i∈Ni∈ N and for some k∈Lk∈ L. An allocation A is said to be PO-USW if there is no allocation B such that (i) ∑i=1nvi(Bi)k≥∑i=1nvi(Ai)k _i=1^nv_i(B_i)_k≥ _i=1^nv_i(A_i)_k for all k∈Lk∈ L and (i) ∑i=1nvi(Bi)k>∑i=1nvi(Ai)k _i=1^nv_i(B_i)_k> _i=1^nv_i(A_i)_k for some k∈Lk∈ L. An allocation A is said to be PO-ESW if there is no such allocation B such that (i) mini∈Nvi(Bi)k≥mini∈Nvi(Ai)k _i∈ Nv_i(B_i)_k≥ _i∈ Nv_i(A_i)_k for all k∈Lk∈ L and (i) mini∈Nvi(Bi)k>mini∈Nvi(Ai)k _i∈ Nv_i(B_i)_k> _i∈ Nv_i(A_i)_k for some k∈Lk∈ L. 3 Maximizing Efficient Dimensions In this section, we focus on maximizing the number of dimensions in which Umax or Emax is achieved. 3.1 Maximizing Umax Dimensions We analyze the problem of maximizing the number of Umax dimensions. We begin with some basic observations. To achieve Umax value for a specific dimension k∈Lk∈ L, each item gj∈Mg_j∈ M must be allocated to an agent i∈Ni∈ N who values it most, that is, vijk=maxi′∈Nvi′jkv_ijk= _i ∈ Nv_i jk. Thus, it suffices to consider the corresponding binary case (N,M,L,(v^i)i∈N)(N,M,L,( v_i)_i∈ N), where v^ijk=1 v_ijk=1 if vijk=maxi′vi′jkv_ijk= _i v_i jk, and v^ijk=0 v_ijk=0 otherwise. Then, an allocation attains Umax for dimension k∈Lk∈ L in the original instance if and only if it achieves Umax for k in the binary instance, that is, if ∑i∈Nv^i(Ai)k=m _i∈ N v_i(A_i)_k=m. Thus, for any subset of dimensions L′⊆L L, there exists an allocation that simultaneously maximizes USW for all dimensions in L′L if and only if, for every gj∈Mg_j∈ M, there exists an agent i such that v^ijk=1 v_ijk=1 for every k∈L′k∈ L . Hence, it is easy to check the existence of such an allocation. Specifically, by taking L′=L =L, we can check existence of sUmax. Theorem 3.1. The existence of an sUmax allocation can be checked in polynomial time. Moreover, if such an allocation exists, it can be found in polynomial time. Moreover, if the number of dimensions ℓ is a constant, the number of subsets L′⊆L L is 2ℓ2 , which is a constant number. Consequently, we can maximize the number of Umax dimensions in polynomial time by enumerating all subsets L′⊆L L and checking whether the dimensions in L′L can be simultaneously maximized with respect to USW. Separately, if the number of items m is constant, then we can enumerate all the possible allocations, which is at most O(nm)O(n^m), a polynomial. Hence, in this case, we can maximize the number of Umax dimensions by simply enumerating all possible allocations. Thus, we obtain the following. observation If either the number of items m or the number of dimensions ℓ is bounded by a constant, then the maximum Umax dimensions problem can be solved in polynomial time. Moreover, there is an FPT algorithm with respect to ℓ for the maximum Umax dimensions problem. Further, by enumerating all subsets L′⊆L L of size at most a constant c, we can find a solution for the maximum Umax dimensions problem whose objective value is the minimum of c and the optimum value. Since the optimum value for the maximum Umax dimensions problem is at most the number of dimensions ℓ , this implies a c/ℓc/ -approximation algorithm. observation For any fixed constant c, there is a c/ℓc/ -approximation algorithm for the maximum Umax dimensions problem, where ℓ is the number of dimensions. On the other hand, the maximum Umax dimensions problem remains computationally hard even when the number of agents n is a constant. Specifically, we show a 1/ℓ1−ϵ1/ ^1-ε-factor inapproximability even for two agents with binary valuations. Our reduction is from MAX-Intersect, which is known to be as hard to approximate as Max-Clique [clifford2011maximum]. Theorem 3.2. For any ϵ>0ε>0, it is NP-hard to approximate the maximum Umax dimensions problem with ℓ dimensions within a factor 1/ℓ1−ϵ1/ ^1-ε, even when there are two agents with binary valuations. The reduction maps each pair of sets in a MAX-Intersect instance to an item and each universe element to a dimension. Assigning an item selects one of the two sets, and a dimension attains Umax exactly when the corresponding element belongs to all selected sets. Thus, the number of Umax dimensions equals the intersection size, giving a gap-preserving reduction. Together, these results (Sections˜3.1 and 3.2) show that while a simple c/ℓc/ -approximation is achievable, improving the 1/ℓ1/ dependence is unlikely, highlighting a fundamental limitation imposed by the number of dimensions. Finally, we analyze the worst-case fraction of dimensions that can achieve Umax. We show that the fraction is exponentially small with respect to n and m. Theorem 3.3. Fix the number of agents n, the number of items m, and the number of dimensions ℓ . For any MDEA instance, the maximum number of Umax dimensions max|k∈L:∑i∈Nvi(Ai)k=Umaxk| _A|\k∈ L: _i∈ Nv_i(A_i)_k=Umax_k\| is at least ⌈ℓ/nm⌉ /n^m . Moreover, there exists a binary MDEA instance for which max|k∈L:∑i∈Nvi(Ai)k=Umaxk|≤⌈ℓ/nm⌉ _A|\k∈ L: _i∈ Nv_i(A_i)_k=Umax_k\|≤ /n^m . The lower bound follows by averaging over the nmn^m allocations. Since each dimension has at least one Umax-achieving allocation, some allocation achieves Umax in at least ⌈ℓ/nm⌉ /n^m dimensions. The matching upper bound is obtained by constructing an instance where each dimension admits a unique Umax allocation and distributing the dimensions evenly across allocations. The ⌈ℓ/nm⌉ /n^m bound is tight, showing that only a very small fraction of dimensions can be optimized simultaneously, an inherent limitation of the multidimensional setting. 3.2 Maximizing Emax Dimensions We now analyze the problem of maximizing the number of Emax dimensions. Without loss of generality, we may assume in this subsection that the number of items is at least the number of agents. Otherwise, the Emax value is zero for every dimension, and any allocation achieves sEmax. Similar to the Umax case, when the number of items m is constant, we can maximize the number of Emax dimensions by enumerating all possible allocations. Thus, we obtain the following result. observation If the number of items m is bounded by a constant, then the maximum Emax dimensions problem can be solved in polynomial time. However, unlike Umax, computing an Emax allocation is already difficult in the one-dimensional setting: with two agents, the problem is polynomial-time solvable for binary valuations, but becomes NP-hard for ternary valuations [fitzsimmons2024hardness]. For the exact simultaneous problem, the one-dimensional case is trivial, since an sEmax allocation always exists and the maximum number of Emax dimensions is one. In contrast, in two dimensions both of these decision problems become NP-hard even with binary valuations. The proof proceeds by a reduction from 3-dimensional matching (3DM). Theorem 3.4. The problems of checking the existence of an sEmax allocation and of determining the maximum number of Emax dimensions are NP-hard, even when there are two dimensions and the valuations are binary. At a high level, the reduction represents each triple by an agent and creates items corresponding to the elements of the second and third parts of the 3DM instance, together with auxiliary items for triples that are not selected. The construction has Emax value one in each dimension, and an allocation attains both values exactly when the agents that receive the two element-items corresponding to their triples form a perfect 3DM matching. This highlights a sharp jump in complexity: moving from one to two dimensions fundamentally changes the problem from trivial to computationally intractable. For the non-binary case, we can prove NP-hardness of checking the existence of an sEmax allocation, and hence of determining the maximum number of Emax dimensions, when there are only two agents and only two dimensions. Theorem 3.5. The problems of checking the existence of an sEmax allocation and of determining the maximum number of Emax dimensions are NP-hard even when there are only two agents and only two dimensions. The proof is by a reduction from Partition. The two dimensions encode the two target sums, and two auxiliary items force any sEmax allocation to correspond to a balanced partition. Finally, we analyze the worst-case fraction of dimensions that can achieve Emax, as a function of the number of dimensions ℓ . As in the case of Umax, we show that the fraction is exponentially small with respect to n and m. Specifically, let T(m,n)=∑i=0n(−1)n−i(ni)imT(m,n)= _i=0^n(-1)^n-i nii^m denote the number of ways to allocate m items to n agents, where each agent receives at least one item. Then, the fraction is ⌈ℓ/T(m,n)⌉ /T(m,n) . Theorem 3.6. Fix the number of agents n, the number of items m, and the number of dimensions ℓ , with m≥nm≥ n. For any MDEA instance, the maximum number of Emax dimensions max|k∈L:mini∈Nvi(Ai)k=Emaxk| _A|\k∈ L: _i∈ Nv_i(A_i)_k=Emax_k\| is at least ⌈ℓ/T(m,n)⌉ /T(m,n) . Moreover, there exists an MDEA instance for which max|k∈L:mini∈Nvi(Ai)k=Emaxk|=⌈ℓ/T(m,n)⌉ _A|\k∈ L: _i∈ Nv_i(A_i)_k=Emax_k\|= /T(m,n) . The lower bound again follows by averaging. Among the allocations in which every agent receives at least one item, there are T(m,n)T(m,n) possibilities, and hence some allocation achieves Emax in at least ⌈ℓ/T(m,n)⌉ /T(m,n) dimensions. For the upper bound, we distribute dimensions evenly across these allocations and construct valuations so that each dimension attains Emax under only one allocation, yielding the bound. This result provides a tight bound on the number of Emax dimensions. As with Umax, only a vanishing fraction of dimensions can be optimized simultaneously, showing that this limitation is inherent even for egalitarian objectives. Unlike the Umax upper-bound construction, the matching construction for Emax uses non-binary valuations. 4 Simultaneously Maximizing Efficiency In this section, we consider the extent to which the efficiency of each dimension must be relaxed in order to achieve simultaneous efficiency across all dimensions. 4.1 Approximate sUmax We show that an α-sUmax 1\,1 allocation always exists when α=1/ℓα=1/ , whereas it may not exist when α>1/ℓα>1/ . To establish existence, we use a round-robin procedure in which each dimension is treated as a virtual agent. In the turn of dimension k, the procedure selects a remaining item maximizing uk(g)=maxi∈Nvi(g)ku_k(g)= _i∈ Nv_i(g)_k and assigns it to an agent attaining this maximum. This process cycles through the dimensions until all items are allocated; the pseudocode is given as Algorithm 1 in Appendix˜B. This is the same round-robin principle used in the EF1 existence proof of Caragiannis et al. [caragiannis2019unreasonable]. Theorem 4.1. A (1/ℓ)(1/ )-sUmax 1\,1 allocation always exists, and such an allocation can be found in polynomial time. The key point is that, for each dimension k, the items selected in the turns of k dominate the later unallocated items in value uk(g)=maxi∈Nvi(g)ku_k(g)= _i∈ Nv_i(g)_k. Hence, the only possible loss from UmaxkUmax_k comes from items selected before the first turn of k; after ignoring items already assigned to a dimension-k maximizing agent, this loss can be charged to one item in Dk()D_k(A). Conversely, for every positive integer ℓ , the approximation ratio 1/ℓ1/ cannot be improved even for the binary case. Theorem 4.2. Fix a positive integer ℓ . For any positive α>1/ℓα>1/ , there exists a binary MDEA instance with ℓ dimensions such that no allocation satisfies α-sUmax 1\,1. The lower-bound instance gives positive value in dimension k only to agent k. Since some agent receives at most m/ℓm/ items, the corresponding dimension obtains USW at most m/ℓm/ , whereas Umaxk=mUmax_k=m and the one-item additive correction is at most 11; choosing m large rules out every α>1/ℓα>1/ . These results establish a sharp threshold at 1/ℓ1/ : a constant fraction per dimension is unattainable, and the linear dependence on ℓ is inherent. 4.2 Approximate sEmax We show that an α-sEmaxℓ\, allocation always exists when α=1/ℓα=1/ , whereas for α>1/ℓα>1/ such an allocation may not exist. A direct round-robin procedure, which cycles through all agent-dimension pairs and lets each agent pick a favorite remaining item in the corresponding dimension, gives the following weaker guarantee. Since both the approximation ratio and the additive term depend on n, this result is mainly a useful baseline; the pseudocode and proof are deferred to Appendix˜B. Theorem 4.3. A 1n⋅ℓ 1n· -sEmax(nℓ−1)\,(n -1) allocation always exists, and such an allocation can be found in polynomial time. To establish existence with an approximation ratio of 1/ℓ1/ , we instead apply the iterative rounding technique of Gölz and Yaghoubizade [golz2025fair, Theorem 4.2], which guarantees the existence of a PROPℓ allocation for fair division of indivisible items among groups of agents, each of size at most ℓ . In our context, a group of ℓ agents can be regarded as a setting with ℓ dimensions. The corresponding pseudocode is given as Algorithm 3 in Appendix˜B. Theorem 4.4. A 1ℓ 1 -sEmaxℓ\, allocation always exists, and such an allocation can be found in polynomial time. The proof starts from optimal fractional Emax allocations, one for each dimension. Averaging these fractional solutions guarantees each agent a 1/ℓ1/ fraction of the fractional optimum in every dimension. Iterative rounding then converts the averaged fractional allocation into an integral one, losing value only on at most ℓ items outside each relevant bundle. Conversely, for every positive integer ℓ , the approximation ratio 1/ℓ1/ cannot be improved even for the binary case. Theorem 4.5. Fix a positive integer ℓ . For any positive α>1/ℓα>1/ and positive integer c, there exists a binary MDEA instance with ℓ agents and ℓ dimensions such that no allocation satisfies α-sEmaxc\,c. The construction is a cyclic binary instance in which, for every dimension, each item is valuable to exactly one agent, and the responsible agent shifts with the dimension. Although Emaxk=m/nEmax_k=m/n for every dimension, any allocation gives some agent at most m/nm/n items; averaging over the ℓ dimensions for this agent yields a dimension with value at most m/(nℓ)m/(n ), so no α>1/ℓα>1/ guarantee survives after removing any fixed number c of items. These results establish a tight 1/ℓ1/ threshold for Emax: even with additive relaxations, the dependence on the number of dimensions is unavoidable. 4.3 Other Notions Finally, we discuss other possible measures of efficiency across multiple dimensions. The problem of maximizing the sum of USWs over all dimensions can be solved greedily by assigning each item g to an agent i who maximizes ∑k∈Lvijk _k∈ Lv_ijk. Theorem 4.6. The problem of maximizing the sum of USWs over all dimensions is solvable in polynomial time. On the other hand, the problem of maximizing the minimum of USWs over all dimensions (i.e., mink∈L∑i∈Nvi(Ai)k _k∈ L _i∈ Nv_i(A_i)_k) is NP-hard to approximate, even in the binary case, as shown below. Theorem 4.7. Checking the existence of an allocation A such that mink∈L∑i∈Nvi(Ai)k≥1 _k∈ L _i∈ Nv_i(A_i)_k≥ 1 is NP-complete, even when the valuations are binary. Moreover, maximizing the same objective is NP-hard to approximate, even when the valuations are binary. The reduction is from Hitting Set: agents represent universe elements, dimensions represent sets, and the h items select at most h agents. An allocation achieves value at least one in every dimension exactly when the selected agents hit all sets. The same gap gives the inapproximability statement. If we do not restrict the problem to the binary case, the problem remains NP-hard even when n=ℓ=2n= =2. Theorem 4.8. Even when the numbers of agents and dimensions are two, finding an allocation A that maximizes mink∈L∑i∈Nvi(Ai)k _k∈ L _i∈ Nv_i(A_i)_k is NP-hard. The proof is again by a reduction from Partition, using the two dimensions to encode the two sides of the partition. Nevertheless, if each valuation is an integer bounded by a constant (i.e., in 0,1,…,c\0,1,…,c\ for some constant c) and the number of dimensions ℓ is fixed, the problem of maximizing the minimum of USWs over all dimensions is solvable in polynomial time by a dynamic programming approach. Specifically, one constructs a table of possible ℓ -dimensional USW vectors for each prefix set of items g1,g2,…,gj\g_1,g_2,…,g_j\ for every j∈[m]j∈[m]. Since the number of possible USW vectors is at most (cj+1)ℓ(cj+1) , this is polynomial for fixed ℓ , with the exponent depending on ℓ . Theorem 4.9. There is a polynomial-time algorithm for the problem of maximizing the minimum of USWs over all dimensions if each valuation is an integer bounded by a constant and the number of dimensions is fixed. For ESW, consider two problems: maximizing the sum of ESWs over all dimensions (i.e., ∑k∈Lmini∈Nvi(Ai)k _k∈ L _i∈ Nv_i(A_i)_k) and maximizing the minimum of ESWs over all dimensions (i.e., mink∈Lmini∈Nvi(Ai)k _k∈ L _i∈ Nv_i(A_i)_k). However, since computing an Emax allocation is NP-hard already in the one-dimensional two-agent case with ternary valuations [fitzsimmons2024hardness], both of these problems are NP-hard even when the number of dimensions is one. Moreover, Theorem˜3.4 implies that the problem of maximizing the minimum ESW across dimensions is NP-hard even to approximate. Therefore, egalitarian objectives are inherently hard, and this difficulty is further amplified in multidimensional settings. Theorem 4.10. Checking the existence of an allocation A such that vi(Ai)k≥1v_i(A_i)_k≥ 1 for every i∈Ni∈ N and k∈Lk∈ L is NP-complete, even when there are two dimensions and the valuations are binary. Moreover, maximizing mink∈Lmini∈Nvi(Ai)k _k∈ L _i∈ Nv_i(A_i)_k is NP-hard to approximate, even when there are two dimensions and the valuations are binary. This follows from the same 3DM reduction as Theorem˜3.4: in that construction, the Emax value is one in both dimensions, so achieving value at least one for every agent and dimension is exactly the existence of an sEmax allocation. The resulting gap between value one and value zero gives the inapproximability statement. 5 Pareto Optimality In this section, we examine the concepts of PO-agent, PO-USW, and PO-ESW. 5.1 Relationship between PO Notions We observe relationships between PO-agent, PO-USW, and PO-ESW. First, PO-USW and PO-ESW are fundamentally distinct concepts, and they are not necessarily compatible. Proposition 5.1. There exists a single-dimensional MDEA instance in which no allocation simultaneously satisfies both PO-USW and PO-ESW. Comparing PO-agent and PO-USW, we show that PO-USW is stronger than PO-agent. Theorem 5.2. In every MDEA instance, every PO-USW allocation is also PO-agent. However, some MDEA instances admit PO-agent allocations that are not PO-USW. It may seem that the same relationship holds between PO-agent and PO-ESW as between PO-agent and PO-USW. However, the two concepts are incomparable. Nevertheless, we can show that there always exists an allocation that simultaneously satisfies both PO-agent and PO-ESW. Theorem 5.3. PO-agent and PO-ESW are incomparable. However, for every MDEA instance, there exists an allocation that satisfies both PO-agent and PO-ESW simultaneously. The existence part follows by taking a PO-agent allocation that is maximal with respect to PO-ESW among all PO-agent allocations; any ESW improvement can be followed by agent-Pareto improvements, contradicting this maximality. 5.2 Checking Pareto Optimality The multidimensional efficiency measures considered above (e.g., maximum Umax dimensions, α-sUmax 1\,1) are compatible with PO-agent because these properties are preserved under Pareto improvements. We therefore ask whether the algorithms studied above can guarantee PO-agent, PO-USW, or PO-ESW. First, note that the algorithm for Theorem˜4.6 gives a PO-agent and PO-USW allocation, since it maximizes the sum of utilities with respect to agents and USWs. observation A PO-agent and PO-USW allocation can be computed in polynomial time. However, most algorithms do not necessarily yield PO allocations. Consider an instance of two agents, two dimensions, and two items g1g_1, g2g_2. The valuations are v1(g1)=(5,1)v_1(g_1)=(5,1), v1(g2)=(2,1)v_1(g_2)=(2,1) and v2(g1)=(4,3)v_2(g_1)=(4,3), v2(g2)=(0,2)v_2(g_2)=(0,2). The round-robin algorithm described in Theorem˜4.1 gives =(g1,g2)A=(\g_1\,\g_2\). However, ′=(g2,g1)A =(\g_2\,\g_1\) Pareto dominates A in the sense of USW because the USWs for A and ′A are (5,3)(5,3) and (6,4)(6,4), respectively. Thus, approximation guarantees should not be conflated with Pareto optimality: an allocation may satisfy the target approximation guarantee while still admitting a Pareto improvement under a stronger welfare-vector comparison. This naturally suggests attempting to apply a Pareto improvement to a given allocation. Unfortunately, determining whether any Pareto improvement exists is computationally hard. In fact, deciding whether a proposed allocation is already Pareto optimal (i.e., admits no improvement) is coNP-complete, even in one dimension. Theorem 5.4 ([de2009complexity, Theorem 11]). Checking whether a given allocation is PO-agent is coNP-complete, even for the single-dimensional case. Thus, even the basic task of certifying the absence of an improving allocation is intractable. We show similar hardness results for both PO-USW and PO-ESW below. We first establish hardness for checking PO-USW. Note that the problem is easy in the single-dimensional case, because determining whether an allocation is PO-USW can be done by comparing it with the Umax value. However, the problem is coNP-hard even for two dimensions. Theorem 5.5. Checking whether a given allocation is PO-USW is coNP-complete, even in the case of two agents and two dimensions. The hardness proof reduces from Partition. The constructed allocation fails to be PO-USW exactly when there is an improving allocation whose two-dimensional USW vector corresponds to a balanced partition. Next, we turn to PO-ESW. In the single-dimensional case, computing a PO-ESW allocation is equivalent to computing an Emax allocation, and is therefore NP-hard. We additionally show that checking whether a given allocation is PO-ESW is already coNP-hard with two agents and two dimensions. Theorem 5.6. Computing a PO-ESW allocation is NP-hard, even in the single-dimensional two-agent case. Additionally, checking whether a given allocation is PO-ESW is coNP-complete, even in the case of two agents and two dimensions. The computing hardness follows from the known NP-hardness of one-dimensional Emax allocation. The verification hardness is shown by a reduction from Partition, where a Pareto improvement in the ESW vector exists exactly when the input can be partitioned evenly. For binary valuations, the single-dimensional case remains tractable because PO-ESW coincides with Emax. This tractability disappears already with two dimensions: computing a PO-ESW allocation is NP-hard, and checking whether a given allocation is PO-ESW is coNP-hard, as established by Theorem˜3.4. Theorem 5.7. Computing a PO-ESW allocation is NP-hard, even in the case of two dimensions with binary valuations. Additionally, checking whether a given allocation is PO-ESW is coNP-complete, even in the case of two dimensions with binary valuations. The reduction uses the same binary two-dimensional 3DM construction as Theorem˜3.4. 6 Conclusion In this paper, we introduced the MDEA model for allocating indivisible items with multidimensional valuations and characterized the worst-case frontier of simultaneous efficiency. We showed that exact simultaneous efficiency is severely limited, that approximate simultaneous efficiency admits sharp dimension-dependent thresholds, and that natural multidimensional Pareto notions have distinct structural and computational properties. In particular, the order 1/ℓ1/ for guaranteeing simultaneous efficiency in every dimension is essentially best possible in the general model. These results should not be viewed as indicating a weakness of the model, but rather as showing that simultaneous efficiency across many dimensions is intrinsically constrained without additional structure. In this sense, MDEA serves as a baseline framework: once the worst-case frontier is identified, one can ask which extra assumptions permit stronger guarantees. An important modeling issue concerns the choice of the dimensions themselves. We treat the set of dimensions as given exogenously, but in practice the value of ℓ and the interpretation of each dimension depend on how one represents the relevant criteria. Since our guarantees deteriorate with ℓ , deciding which attributes should be kept separate, aggregated, or compressed is itself a central design question. In particular, if a decision maker can identify a smaller set of decision-critical dimensions, our guarantees apply with respect to that reduced value of ℓ , giving stronger worst-case bounds for the selected representation. More generally, one may reduce many raw attributes to a smaller set of latent dimensions using PCA, factor analysis, or domain-driven grouping before applying our framework. Our guarantees should then be understood relative to the chosen representation. Other directions include richer objective functions, indivisible chores, and empirical studies. Theorem˜3.1 and Section˜3.1 extend to chores and even to mixed goods and chores, but for other notions the achievable forms of multidimensional efficiency remain open. References Appendix A Our Results Table 1 summarizes our results. When a bound is best possible, this is stated directly in the result description rather than encoded by a separate checkmark. Table 1: Summary of simultaneous efficiency results Setting Main result Ref. Exact sUmax Need not exist, even with two agents and two dimensions. Ex. 1.1 Exact sEmax Need not exist, even with two agents and two dimensions. Ex. 1.2 Max Umax dims c/ℓc/ -approximation for every fixed c; no 1/ℓ1−ϵ1/ ^1-ε-approximation unless P==NP, so the dependence on ℓ is tight up to ϵε. Obs. 3.1, Thm. 3.2 Max Emax dims NP-hard already with binary valuations and two dimensions. Thm. 3.4 α-sUmax 1\,1 Always exists for α=1/ℓα=1/ , and may fail for every α>1/ℓα>1/ ; this gives a tight threshold. Thms. 4.1, 4.2 α-sEmaxc\,c Always exists for α=1/ℓα=1/ when c=ℓc= , while every fixed c may fail for α>1/ℓα>1/ ; this gives a tight threshold in ℓ . Thms. 4.4, 4.5 Aggregate USW Maximizing the sum is polynomial-time solvable, but maximizing the minimum is NP-hard to approximate. Thms. 4.6, 4.7 Aggregate ESW Maximizing the minimum ESW is NP-hard to approximate, even with binary valuations and two dimensions. Thm. 4.10 Pareto notions PO-agent and PO-USW allocations are computable, but verifying PO-USW and PO-ESW is coNP-complete. Obs. 5.2, Thms. 5.5, 5.6 Appendix B Omitted Proofs See 3.2 Proof B.1. We provide a gap-preserving reduction from the MAX-Intersect problem. In the problem, we are given a universe U=e1,e2,…,eℓU=\e_1,e_2,…,e_ \, and m sets consisting of two sets S1,S2,…,SmS_1,S_2,…,S_m where Sj=Sj,1,Sj,2S_j=\S_j,1,S_j,2\, the goal is to select π:[m]→[2]π [m]→[2] that maximizes |⋂j∈[m]Sj,π(j)|| _j∈[m]S_j,π(j)|. By a gap-preserving reduction from the Max-Clique problem, Clifford and Popa [clifford2011maximum] proved that this problem cannot be approximated within a multiplicative factor of 1/ℓ1−ϵ1/ ^1-ε, for any ϵ>0ε>0, unless P==NP. We use MAX-Intersect instances after the standard preprocessing that deletes every element eke_k for which ek∉Sj,1∪Sj,2e_k∉ S_j,1∪ S_j,2 for some j∈[m]j∈[m]. Such an element can never belong to any feasible intersection, and hence does not affect the objective value. We denote the size of the remaining universe by ℓ ; the hardness statement above is with respect to this reduced universe size. From a given Max-Intersect instance, we construct an MDEA instance with two agents N=1,2N=\1,2\, items M=g1,g2,…,gmM=\g_1,g_2,…,g_m\, and dimensions L=[ℓ]L=[ ]. For i∈Ni∈ N, gj∈Mg_j∈ M, and k∈Lk∈ L, the valuation is defined as vijk v_ijk =1if ek∈Sj,i,0otherwise. = cases1&if e_k∈ S_j,i,\\ 0&otherwise. cases (3) Note that, for each dimension k∈Lk∈ L, the Umax value is Umaxk=mUmax_k=m. We now show that the optimum value for the Max-Intersect instance is equal to the optimum value of the maximum Umax dimensions problem for the constructed MDEA instance. From a mapping π:[m]→[2]π [m]→[2], we construct the allocation =(A1,A2)A=(A_1,A_2) such that Ai=gj∈M:π(j)=iA_i=\g_j∈ M:π(j)=i\ for i=1,2i=1,2. Then, the USW value ∑i∈Nvi(Ai)k _i∈ Nv_i(A_i)_k attains Umaxk(=m)Umax_k 10000\ (=m) if and only if ek∈Sj,π(j)e_k∈ S_j,π(j) for all j∈[m]j∈[m]. This means that the number of Umax dimensions for A is equal to |⋂j∈[m]Sj,π(j)|| _j∈[m]S_j,π(j)|. Conversely, given an allocation ′=(A1′,A2′)A =(A _1,A _2), we can construct a mapping π′:[m]→[2]π [m]→[2] as π′(j)=iπ (j)=i if gj∈Ai′g_j∈ A _i for i=1,2i=1,2. The number of Umax dimensions for ′A is then |⋂j∈[m]Sj,π′(j)|| _j∈[m]S_j,π (j)|. Therefore, this is a gap-preserving reduction. See 3.3 Proof B.2. Let A denote the set of all possible allocations of the m items to the n agents. Since each item can be assigned to any of the n agents, the total number of distinct allocations is ||=nm|A|=n^m. Define k⊆A_k to be the set of allocations A such that ∑i∈Nvi(Ai)k=Umaxk _i∈ Nv_i(A_i)_k=Umax_k for each dimension k∈Lk∈ L. Note that kA_k is not empty for each k∈Lk∈ L because UmaxkUmax_k is achievable by definition. Thus, ∑k=1ℓ|k| _k=1 |A_k| is at least ℓ . On the other hand, for each allocation ∈A , let f()=|k∈[ℓ]:∈k|f(A)=|\k∈[ ]:A _k\| be the number of dimensions in which A achieves Umax. Then, we have ∑∈f()=∑k=1ℓ|k|≥ℓ. _A f(A)= _k=1 |A_k|≥ . (4) Thus, by the pigeonhole principle, we obtain max∈|k∈L:∑i∈Nvi(Ai)k=Umaxk|=max∈f()≥⌈ℓnm⌉. _A | \k∈ L:Σ _i∈ Nv_i(A_i)_k=Umax_k \ |= _A f(A)≥ n^m . This proves the lower bound. Next, we provide the upper bound. Choose a mapping ρ:[ℓ]→ρ [ ] such that |k∈[ℓ]:ρ(k)=|≤⌈ℓ/nm⌉|\k∈[ ]:ρ(k)=A\|≤ /n^m for every ∈A . Such a mapping exists by distributing the ℓ dimensions as evenly as possible among the ||=nm|A|=n^m allocations. For each agent i∈[n]i∈[n], item index j∈[m]j∈[m], and dimension k∈[ℓ]k∈[ ], we define the valuation as vijk=1if agent i receives gj in allocation ρ(k),0otherwise. v_ijk= cases1&if agent $i$ receives $g_j$ in allocation $ρ(k)$,\\ 0&otherwise. cases (5) This instance is binary by construction. For this instance, the Umax value in dimension k∈[ℓ]k∈[ ] is m, and it can only be achieved by using the allocation ρ(k)ρ(k). Hence, for each allocation ∈A , the number of dimensions in which A achieves Umax is |k∈[ℓ]:ρ(k)=|≤⌈ℓ/nm⌉|\k∈[ ]:ρ(k)=A\|≤ /n^m . Thus, max|k∈L:∑i∈Nvi(Ai)k=Umaxk|≤⌈ℓ/nm⌉ _A|\k∈ L: _i∈ Nv_i(A_i)_k=Umax_k\|≤ /n^m for this instance. See 3.4 Proof B.3. It suffices to prove hardness for the existence of an sEmax allocation, since the constructed instances have two dimensions and hence attaining Emax in both dimensions is equivalent to maximizing the number of Emax dimensions to two. We present a polynomial-time reduction from the 3-dimensional matching (3DM) problem, which is known to be NP-hard [garey1979computers]. In the 3DM problem, we are given three sets of elements, X=x1,…,xnX=\x_1,…,x_n\, Y=y1,…,ynY=\y_1,…,y_n\, and Z=z1,…,znZ=\z_1,…,z_n\. We are also given a set of hyperedges T=t1,…,tmT=\t_1,…,t_m\ where each t∈Tt∈ T is an ordered triple in X×Y×ZX× Y× Z. The goal of the problem is to determine if there exists a subset T′T of T such that each element from X, Y, and Z appears exactly once in T′T . In other words, our task is to find a perfect matching that covers all the elements in X, Y, and Z without any repetitions. Without loss of generality, we assume that there exists a subset T(Y)⊆T^(Y) T such that each element from X and Y appears exactly once in T(Y)T^(Y), since otherwise the instance is a no-instance, and this can be easily verified in polynomial time. Similarly, we assume that there exists a subset T(Z)⊆T^(Z) T such that each element from X and Z appears exactly once in T(Z)T^(Z). For each j∈[n]j∈[n], let sj=|ti∈T:xj∈ti|s_j=|\t_i∈ T:x_j∈ t_i\| be the number of hyperedges tit_i that contains xjx_j. Note that ∑j=1nsj=m _j=1^ns_j=m. From a given 3DM instance, we construct an MDEA instance with agents N=[m]N=[m], M=g1,g2,…,gn+mM=\g_1,g_2,…,g_n+m\, and L=1,2L=\1,2\. For i∈Ni∈ N, gj∈Mg_j∈ M, k∈Lk∈ L, with ti=(xa,yb,zc)t_i=(x_a,y_b,z_c), the valuation vijkv_ijk equals 11 if (j,k)=(b,1)(j,k)=(b,1), (n+c,2)(n+c,2), or 2n+∑p=1a−1(sp−1)<j≤2n+∑p=1a(sp−1)2n+ _p=1^a-1(s_p-1)<j≤ 2n+ _p=1^a(s_p-1), and 0 otherwise. An example of this reduction is illustrated in Table˜2. Table 2: The valuations vijkv_ijk for the reduced instance in Theorem˜3.4 for the instance: n=3n=3, m=5m=5, t1=(x1,y2,z2)t_1=(x_1,y_2,z_2), t2=(x1,y2,z3)t_2=(x_1,y_2,z_3), t3=(x2,y3,z3)t_3=(x_2,y_3,z_3), t4=(x3,y1,z1)t_4=(x_3,y_1,z_1), t5=(x3,y3,z3)t_5=(x_3,y_3,z_3). The red allocation corresponds to the solution t1,t3,t4\t_1,t_3,t_4\. agent dim. g1g_1 g2g_2 g3g_3 g4g_4 g5g_5 g6g_6 g7g_7 g8g_8 1 1 0 1 0 0 0 0 1 0 2 0 0 0 0 1 0 1 0 2 1 0 1 0 0 0 0 1 0 2 0 0 0 0 0 1 1 0 3 1 0 0 1 0 0 0 0 0 2 0 0 0 0 0 1 0 0 4 1 1 0 0 0 0 0 0 1 2 0 0 0 1 0 0 0 1 5 1 0 0 1 0 0 0 0 1 2 0 0 0 0 0 1 0 1 We remark that, for each dimension, the Emax value is 11, and each agent must receive exactly one valuable item. Indeed, for each i∈Ni∈ N with ti=(xa,yb,zc)∈Tt_i=(x_a,y_b,z_c)∈ T, allocating gbg_b to i if ti∈T(Y)t_i∈ T^(Y), and allocating one item from g2n+∑p=1a−1(sp−1)+1,…,g2n+∑p=1a(sp−1) \g_2n+ _p=1^a-1(s_p-1)+1,…,g_2n+ _p=1^a(s_p-1) \ if ti∉T(Y)t_i∉ T^(Y), guarantees a utility of 11 for agent i in the first dimension. Moreover, the Emax value is at most 11 for the first dimension because there are m items that are valuable to at least one agent in the first dimension (i.e., g1,…,gn,g2n+1,…,gn+m\g_1,…,g_n,g_2n+1,…,g_n+m\), and each agent can receive at most one valuable item. An analogous argument applies to the second dimension. We now prove that the MDEA instance admits a sEmax allocation if and only if the 3DM instance is a yes-instance. Suppose that an allocation A achieves sEmax, i.e., vi(Ai)k=1v_i(A_i)_k=1 for all i∈Ni∈ N and k∈Lk∈ L. Then, for each i∈Ni∈ N with ti=(xa,yb,zc)∈Tt_i=(x_a,y_b,z_c)∈ T, we have Ai=gb,gn+cA_i=\g_b,g_n+c\ or Ai=gjA_i=\g_j\ with 2n+∑p=1a−1(sp−1)<j≤2n+∑p=1a(sp−1)2n+ _p=1^a-1(s_p-1)<j≤ 2n+ _p=1^a(s_p-1). Thus, T′≔i∈N:|Ai|=2T \i∈ N:|A_i|=2\ forms a 3-dimensional matching, and the 3DM instance is a yes-instance. Conversely, suppose that the 3DM instance is a yes-instance, and let T′T be a 3-dimensional matching. Then, for each i∈Ni∈ N with ti=(xa,yb,zc)∈Tt_i=(x_a,y_b,z_c)∈ T, allocating gb,gn+c\g_b,g_n+c\ to i if ti∈T′t_i∈ T , and allocating one item from g2n+∑p=1a−1(sp−1)+1,…,g2n+∑p=1a(sp−1)\g_2n+ _p=1^a-1(s_p-1)+1,…,g_2n+ _p=1^a(s_p-1)\ if ti∉T′t_i∉ T , guarantees a utility of 11 for agent i in both dimensions. Thus, this allocation achieves the ESW value of 1 for both dimensions. Therefore, the problems of checking the existence of an sEmax allocation and of determining the maximum number of Emax dimensions are NP-hard, even when there are two dimensions and the valuations are binary. See 3.5 Proof B.4. We present a polynomial-time reduction from the PARTITION problem, which is known to be NP-complete [garey1979computers]. In the PARTITION problem, we are given m positive integers a1,a2,⋯,ama_1,a_2,·s,a_m such that ∑j=1maj=2T _j=1^ma_j=2T. The goal is to determine whether there exists a partition (S1,S2)(S_1,S_2) of the set [m][m] such that ∑j∈S1aj=∑j∈S2aj=T _j∈ S_1a_j= _j∈ S_2a_j=T. From a given instance of the PARTITION problem, we construct an MDEA instance with agents N=1,2N=\1,2\, items M=g1,g2,…,gm,gm+1,gm+2M=\g_1,g_2,…,g_m,g_m+1,g_m+2\, and dimensions L=1,2L=\1,2\. For i∈Ni∈ N, gj∈Mg_j∈ M, k∈Lk∈ L, the valuation is defined as vijk=ajif i=k and j≤m,Tif (i,j,k)=(1,m+1,2) or (2,m+2,1),0otherwise. v_ijk= casesa_j&if $i=k$ and $j≤ m$,\\ T&if $(i,j,k)=(1,m+1,2)$ or $(2,m+2,1)$,\\ 0&otherwise. cases (6) The valuations are illustrated in Table˜3. Table 3: The valuations vijkv_ijk for the reduced instance in Theorem˜3.5. Each column block corresponds to an item, the blue numbers denote the agent index, and the two rows represent the valuations in dimensions 11 and 22, respectively. g1g_1 g2g_2 ⋯·s gjg_j ⋯·s gmg_m gm+1g_m+1 gm+2g_m+2 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 ⋯·s 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 ⋯·s 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 11 a1a_1 0 a2a_2 0 ⋯·s aja_j 0 ⋯·s ama_m 0 0 0 0 T 22 0 a1a_1 0 a2a_2 ⋯·s 0 aja_j ⋯·s 0 ama_m T 0 0 0 Without loss of generality, we may assume that gm+1g_m+1 is allocated to agent 11 and gm+2g_m+2 is allocated to agent 22. The Emax values are Emax1=Emax2=TEmax_1=Emax_2=T. If the PARTITION instance is a yes-instance, then there exists a partition (S1,S2)(S_1,S_2) of [m][m] such that ∑j∈S1aj=∑j∈S2aj=T _j∈ S_1a_j= _j∈ S_2a_j=T. Allocating gj:j∈S1∪gm+1\g_j:j∈ S_1\∪\g_m+1\ to agent 11 and gj:j∈S2∪gm+2\g_j:j∈ S_2\∪\g_m+2\ to agent 22 achieves Emax in both dimensions. Conversely, suppose that the MDEA instance admits a sEmax allocation A. To achieve Emax1=TEmax_1=T, we must have v1(A1)1=∑gj∈A1∩g1,…,gmaj≥Tv_1(A_1)_1= _g_j∈ A_1∩\g_1,…,g_m\a_j≥ T, since gm+1g_m+1 contributes nothing in dimension 11 and gm+2g_m+2 is allocated to agent 22. Similarly, achieving Emax2=TEmax_2=T requires v2(A2)2=∑gj∈A2∩g1,…,gmaj≥Tv_2(A_2)_2= _g_j∈ A_2∩\g_1,…,g_m\a_j≥ T. Because ∑j=1maj=2T _j=1^ma_j=2T and the items g1,…,gm\g_1,…,g_m\ are partitioned between the two agents, both sums must in fact be exactly T. Hence, the sets S1=A1∩g1,…,gmS_1=A_1∩\g_1,…,g_m\ and S2=A2∩g1,…,gmS_2=A_2∩\g_1,…,g_m\ form a solution to the PARTITION instance. Since there are only two dimensions, determining whether the maximum number of Emax dimensions is two is equivalent to checking the existence of an sEmax allocation. Therefore, the problems of checking the existence of an sEmax allocation and of determining the maximum number of Emax dimensions are NP-hard. See 3.6 Proof B.5. Let ′A denote the set of all possible allocations of the m items to the n agents, where each agent receives at least one item. Note that |′|=T(m,n)|A |=T(m,n). Define k′⊆′A _k to be the set of allocations ∈′A such that mini∈Nvi(Ai)k=Emaxk _i∈ Nv_i(A_i)_k=Emax_k for each dimension k∈Lk∈ L. Note that k′A _k is not empty for each k∈Lk∈ L because EmaxkEmax_k is achievable while ensuring that no agent receives zero items. Thus, ∑k=1ℓ|k′| _k=1 |A _k| is at least ℓ . On the other hand, for each allocation ∈′A , let f′()=|k∈[ℓ]:∈k′|f (A)=|\k∈[ ]:A _k\| be the number of dimensions in which A achieves Emax. Then, we have ∑∈′f′()=∑k=1ℓ|k′|≥ℓ. _A f (A)= _k=1 |A _k|≥ . (7) Thus, by the pigeonhole principle, we obtain max∈′|k∈L:mini∈Nvi(Ai)k=Emaxk|=max∈′f′()≥⌈ℓ/T(m,n)⌉. _A | \k∈ L: _i∈ Nv_i(A_i)_k=Emax_k \ |= _A f (A)≥ /T(m,n) . (8) This proves the lower bound. Next, we provide the upper bound. Choose a mapping ρ′:[ℓ]→′ρ [ ] such that |k∈[ℓ]:ρ′(k)=|≤⌈ℓ/T(m,n)⌉|\k∈[ ]:ρ (k)=A\|≤ /T(m,n) for every ∈′A . Such a mapping exists by distributing the ℓ dimensions as evenly as possible among the |′|=T(m,n)|A |=T(m,n) allocations. For each agent i∈[n]i∈[n], item index j∈[m]j∈[m], and dimension k∈[ℓ]k∈[ ], let ρ′(k)=ρ (k)=A and define the valuation as vijk=1/|Ai|if gj∈Ai,0otherwise. v_ijk= cases1/|A_i|&if g_j∈ A_i,\\ 0&otherwise. cases (9) This upper-bound construction is not binary in general because the values 1/|Ai|1/|A_i| may be fractional; this is the point where the construction differs from the Umax counterpart. For this instance, the Emax value in dimension k∈[ℓ]k∈[ ] is 11, and it can only be achieved by using the allocation ρ′(k)ρ (k). Hence, for each allocation ∈′A , the number of dimensions in which A achieves Emax is |k∈[ℓ]:ρ′(k)=|≤⌈ℓ/T(m,n)⌉|\k∈[ ]:ρ (k)=A\|≤ /T(m,n) . Thus, max|k∈L:mini∈Nvi(Ai)k=Emaxk|≤⌈ℓ/T(m,n)⌉ _A|\k∈ L: _i∈ Nv_i(A_i)_k=Emax_k\|≤ /T(m,n) for this instance. Input: Agents N, items M, dimensions L=1,…,ℓL=\1,…, \ Output: Allocation A 1 2Initialize Ai←∅A_i← for all i∈Ni∈ N; 3 M′←M ← M; 4 5while M′≠∅M ≠ do 6 for k←1k← 1 to ℓ do 7 if M′=∅M = then 8 break 9 g∗∈argmaxg∈M′maxi∈Nvi(g)kg^*∈ _g∈ M _i∈ Nv_i(g)_k; 10 i∗∈argmaxi∈Nvi(g∗)ki^*∈ _i∈ Nv_i(g^*)_k; 11 Ai∗←Ai∗∪g∗A_i^*← A_i^*∪\g^*\; 12 M′←M′∖g∗M ← M \g^*\; 13 14 return A Algorithm 1 Round-Robin (1/ℓ)(1/ )-sUmax 1\,1 See 4.1 Proof B.6. For each dimension k∈Lk∈ L, define the value of item g∈Mg∈ M as uk(g)=maxi∈Nvi(g)ku_k(g)= _i∈ Nv_i(g)_k. We then apply a round-robin procedure as follows: In the order 1,2,…,ℓ1,2,…, , each dimension k sequentially takes turns selecting its favorite available item g (i.e., an item maximizing uk(g)u_k(g)), and g is then allocated to an agent in argmaxi∈Nvi(g)k *arg\,max_i∈ Nv_i(g)_k. This process is repeated in multiple rounds until all items have been allocated. Let A be the resulting allocation. The procedure clearly runs in polynomial time. We now show that A is a (1/ℓ)(1/ )-sUmax 1\,1 allocation. Relabel the item, and let gjg_j denote the item chosen at the jjth step. The items assigned in turn k∈Lk∈ L are gk,gℓ+k,g2ℓ+k,…,g⌊(m−k)/ℓ⌋⋅ℓ+kg_k,g_ +k,g_2 +k,…,g_ (m-k)/ · +k. It follows that ∑i∈Nvi(Ai)k≥∑p=0⌊(m−k)/ℓ⌋uk(gpℓ+k) _i∈ Nv_i(A_i)_k≥ _p=0 (m-k)/ u_k(g_p +k). Note that, for each k∈Lk∈ L, p∈0,1,…,⌊(m−k)/ℓ⌋p∈\0,1,…, (m-k)/ \, and q∈[m]q∈[m] with q≥pℓ+kq≥ p +k, we have uk(gpℓ+k)≥uk(gq)u_k(g_p +k)≥ u_k(g_q). Therefore, Umaxk _k =∑g∈Mmaxi∈Nvi(g)k=∑g∈Muk(g)=∑q=1muk(gq) = _g∈ M _i∈ Nv_i(g)_k= _g∈ Mu_k(g)= _q=1^mu_k(g_q) (10) ≤∑q=1k−1uk(gq)+ℓ⋅∑p=0⌊(m−k)/ℓ⌋uk(gpℓ+k) ≤ _q=1^k-1u_k(g_q)+ · _p=0 (m-k)/ u_k(g_p +k) (11) ≤∑q=1k−1uk(gq)+ℓ⋅∑i∈Nvi(Ai)k. ≤ _q=1^k-1u_k(g_q)+ · _i∈ Nv_i(A_i)_k. (12) Let Pk=q∈1,…,k−1:gq∈Dk()P_k=\q∈\1,…,k-1\:g_q∈ D_k(A)\. Any item among g1,…,gk−1g_1,…,g_k-1 that is not in Dk()D_k(A) is assigned to a dimension-k maximizing agent, and hence its full uku_k-value is already counted in ∑ivi(Ai)k _iv_i(A_i)_k. Therefore, the preceding bound can be sharpened to Umaxk≤∑q∈Pkuk(gq)+ℓ⋅∑i∈Nvi(Ai)k.Umax_k≤ _q∈ P_ku_k(g_q)+ · _i∈ Nv_i(A_i)_k. Hence, for every k∈Lk∈ L, ∑i∈Nvi(Ai)k Σ _i∈ Nv_i(A_i)_k ≥Umaxkℓ−∑q∈Pkuk(gq)ℓ ≥ Umax_k - _q∈ P_ku_k(g_q) (13) ≥Umaxkℓ−maxB⊆Dk():|B|≤1∑gj∈Bmaxi∈Nvijk. ≥ Umax_k - _B D_k(A):\,|B|≤ 1 _g_j∈ B _i∈ Nv_ijk. (14) The last inequality holds because |Pk|≤k−1≤ℓ−1|P_k|≤ k-1≤ -1, so the average loss after division by ℓ is at most the largest item in Dk()D_k(A), or zero if Dk()=∅D_k(A)= . This shows that A is a (1/ℓ)(1/ )-sUmax 1\,1 allocation. See 4.2 Proof B.7. Consider an instance with n=ℓn= agents, m>1/(α−1/ℓ)m>1/(α-1/ ) items, and ℓ dimensions. For i∈Ni∈ N, gj∈Mg_j∈ M, and k∈Lk∈ L, set the valuation vijkv_ijk to 11 if i=ki=k and 0 otherwise. For every k∈Lk∈ L, we have Umaxk=mUmax_k=m. Fix any allocation A. Then, there is an agent i∗∈Ni^*∈ N such that |Ai∗|≤m/n=m/ℓ|A_i^*|≤ m/n=m/ . Thus, ∑i∈Nvi(Ai)i∗=|Ai∗|≤mℓ=α⋅m−(α−1ℓ)⋅m _i∈ Nv_i(A_i)_i^*=|A_i^*|≤ m =α· m- (α- 1 )· m (15) <α⋅m−1≤α⋅Umaxi∗−maxB⊆Di∗():|B|≤1∑g∈Bmaxi∈Nvi(g)i∗, <α· m-1≤α·Umax_i^*- _B D_i^*(A):\,|B|≤ 1 _g∈ B _i∈ Nv_i(g)_i^*, (16) which implies that A is not α-sUmax 1\,1 for the chosen instance. Input: Agents N, items M, dimensions L=1,…,ℓL=\1,…, \, valuations vi(g)kv_i(g)_k Output: Allocation =(A1,…,An)A=(A_1,…,A_n) 1 2Initialize Ai←∅A_i← for all i∈Ni∈ N; 3 M′←M ← M; 4 5while M′≠∅M ≠ do 6 for k=1k=1 to ℓ do 7 for i=1i=1 to n do 8 if M′=∅M = then 9 break; 10 11 Select g∗∈argmaxg∈M′vi(g)kg^*∈ _g∈ M v_i(g)_k; 12 Assign g∗g^* to agent i: Ai←Ai∪g∗A_i← A_i∪\g^*\; 13 Remove g∗g^* from M′M ; 14 15 16 17return A; Algorithm 2 Round-Robin Allocation for 1nℓ 1n -sEmax(nℓ−1)\,(n -1) See 4.3 Proof B.8. We apply a round-robin procedure as follows: Agents select items by cycling through all agents for the first dimension, then all agents for the second dimension, and so on, until the ℓ dimension is reached. Formally, the order of selection is (i,k)(i,k) where k is from 11 to ℓ , and for each fixed k, is from 11 to n, that is, (i,k)=(1,1),(2,1),…,(n,1),(1,2),(2,2),…,(n,2),…,(1,ℓ),(2,ℓ),…,(n,ℓ)(i,k)=(1,1),(2,1),…,(n,1),(1,2),(2,2),…,(n,2),…,(1, ),(2, ),…,(n, ). In each step, agent i chooses their most preferred available item g with respect to kkth dimension (i.e., an item maximizing vi(g)kv_i(g)_k). The process is repeated in multiple round until all items have been allocated. Let A be the resulting allocation. The procedure clearly runs in polynomial time. We now show that A is a 1nℓ 1n -sEmax(nℓ−1)\,(n -1) allocation. Relabel the item, and let gjg_j denote the item chosen at the jjth step. The items assigned agent i∈Ni∈ N are gi,gn+i,g2n+i,…,g⌊(m−i)/n⌋⋅n+ig_i,g_n+i,g_2n+i,…,g_ (m-i)/n · n+i. It follows that, for each i∈Ni∈ N and k∈Lk∈ L, we have vi(Ai)k≥∑p=0⌊(m−(k−1)n−i)/(nℓ)⌋vi(gpnℓ+(k−1)n+i)k.v_i(A_i)_k≥ _p=0 (m-(k-1)n-i)/(n ) v_i(g_pn +(k-1)n+i)_k. Note that, for each i∈Ni∈ N, k∈Lk∈ L, p∈0,1,…,⌊(m−(k−1)n−i)/(nℓ)⌋p∈\0,1,…, (m-(k-1)n-i)/(n ) \, and q∈[m]q∈[m] with q≥pnℓ+(k−1)n+iq≥ pn +(k-1)n+i, we have vi(gpnℓ+(k−1)n+i)k≥vi(gq)kv_i(g_pn +(k-1)n+i)_k≥ v_i(g_q)_k. Therefore, for every i∈Ni∈ N and k∈Lk∈ L, Emaxk _k ≤∑g∈Mvi(g)k=∑q=1mvi(gq)k ≤ _g∈ Mv_i(g)_k= _q=1^mv_i(g_q)_k (17) =∑q=1(k−1)n+i−1vi(gq)k+nℓ⋅∑p=0⌊(m−(k−1)n−i)/(nℓ)⌋vi(gpnℓ+(k−1)n+i)k = _q=1^(k-1)n+i-1v_i(g_q)_k+n · -11.38109pt _p=0 (m-(k-1)n-i)/(n ) -11.38109ptv_i(g_pn +(k-1)n+i)_k (18) ≤∑q=1(k−1)n+i−1vi(gq)k+nℓ⋅vi(Ai)k. ≤ _q=1^(k-1)n+i-1v_i(g_q)_k+n · v_i(A_i)_k. (19) Fix i∈Ni∈ N and k∈Lk∈ L, and let Pi,k=g1,…,g(k−1)n+i−1∖AiP_i,k=\g_1,…,g_(k-1)n+i-1\ A_i. Items in the prefix that already belong to AiA_i are counted in vi(Ai)kv_i(A_i)_k, so the preceding bound can be strengthened to Emaxk≤∑g∈Pi,kvi(g)k+nℓ⋅vi(Ai)k. _k≤ _g∈ P_i,kv_i(g)_k+n · v_i(A_i)_k. (20) Here Pi,k⊆M∖AiP_i,k M A_i and |Pi,k|≤nℓ−1|P_i,k|≤ n -1, and each term vi(g)kv_i(g)_k is at most maxi′∈Nvi′(g)k _i ∈ Nv_i (g)_k. Therefore, for every i∈Ni∈ N and k∈Lk∈ L, vi(Ai)k≥Emaxknℓ−maxB⊆M∖Ai:|B|≤nℓ−1∑gj∈Bmaxi′∈Nvi′jk, v_i(A_i)_k≥ Emax_kn - _B M A_i:\,|B|≤ n -1 _g_j∈ B _i ∈ Nv_i jk, (21) which shows that A is a 1nℓ 1n -sEmax(nℓ−1)\,(n -1) allocation. See 4.4 Proof B.9. For each k∈Lk∈ L, we first compute the Emax value for the fractional allocation, which can be formulated as the following linear program (LP): maxγs.t.γ≤∑gj∈Mvijkxij(i∈N),∑i∈Nxij=1(gj∈M),0≤xij≤1((i,j)∈N×M). array[]rll &γ&\\ s.t.&γ≤ _g_j∈ Mv_ijkx_ij&(i∈ N),\\[5.0pt] & _i∈ Nx_ij=1&(g_j∈ M),\\[5.0pt] &0≤ x_ij≤ 1&((i,j)∈ N× M). array (26) Let Emax¯k Emax_k denote the optimal value and x(k)x^(k) the corresponding optimal solution of the LP. Every integral allocation is feasible for this LP, and hence Emax¯k≥Emaxk Emax_k _k. Here Emax¯k Emax_k is the fractional optimum, whereas EmaxkEmax_k denotes the integral optimum used in the definition of sEmax. Furthermore, x∗=∑k′∈Lx(k′)/ℓx^*= _k ∈ Lx^(k )/ is a fractional allocation that guarantees each agent at least a 1/ℓ1/ fraction of Emax¯k Emax_k for every k∈Lk∈ L. We now construct an integral allocation with a matching additive-loss guarantee. We now use the iterative rounding framework of Gölz and Yaghoubizade [golz2025fair, Theorem 4.2], and briefly recall its idea. Starting from a basic feasible solution of a polytope, it repeatedly fixes decisions forced by the remaining fractional structure: either an item is almost fully assigned to one agent and is fixed, or some agent constraint has support size at most ℓ and those items are fixed together. The polytope is updated after each step; feasibility is preserved and the loss is bounded by the sum of the largest values of at most ℓ items, yielding an integral allocation. We apply the framework with our target guarantee by replacing the proportionality condition vi(M)k/nv_i(M)_k/n (written as ugi(M)/nu_gi(M)/n in their notation) with Emax¯k/ℓ Emax_k/ , which is feasible for x∗x^*. Then the algorithm outputs an allocation A such that vi(Ai)k≥Emax¯kℓ−maxB⊆M∖Ai:|B|≤ℓ∑gj∈Bmaxi′∈Nvi′jk v_i(A_i)_k≥ Emax_k - _B M A_i:\,|B|≤ _g_j∈ B _i ∈ Nv_i jk (27) holds for each i∈Ni∈ N and k∈Lk∈ L. Since Emax¯k≥Emaxk Emax_k _k, for every i∈Ni∈ N and k∈Lk∈ L we have vi(Ai)k v_i(A_i)_k ≥Emaxkℓ−maxB⊆M∖Ai:|B|≤ℓ∑gj∈Bmaxi′∈Nvi′jk. ≥ Emax_k - _B M A_i:\,|B|≤ Σ _g_j∈ B _i ∈ Nv_i jk. (28) Thus, A is a 1ℓ 1 -sEmaxℓ\, allocation. Input: Agents N, items M, dimensions L=1,…,ℓL=\1,…, \, valuations vi(g)kv_i(g)_k Output: Allocation =(A1,…,An)A=(A_1,…,A_n) 1 2Initialize Ai←∅A_i← for all i∈Ni∈ N; 3 4for each dimension k∈Lk∈ L do 5 Solve LP: maxγs.t. γ≤∑g∈Mvi(g)kxig∀i,∑ixig=1, 0≤xig≤1 γ .t. γ≤ _g∈ Mv_i(g)_kx_ig\ ∀ i,\; _ix_ig=1,\;0≤ x_ig≤ 1 Let x(k)x^(k) be the optimal solution; 6 7 8Compute averaged fractional allocation: xig∗←1ℓ∑k∈Lxig(k)x^*_ig← 1 _k∈ Lx^(k)_ig 9while there exists fractional x∗x^* do 10 if there exists item g with xig∗=1x^*_ig=1 for some i then 11 Assign g to i: Ai←Ai∪gA_i← A_i∪\g\; 12 Remove g from the instance and update x∗x^*; 13 14 else 15 Find agent i with at most ℓ fractional items, whose existence follows from the iterative-rounding lemma [golz2025fair, Theorem 4.2]; 16 Assign all such items to i; 17 Update instance and x∗x^*; 18 19 20 21return A; Algorithm 3 Iterative Rounding for (1/ℓ)(1/ )-sEmaxℓ\, See 4.5 Proof B.10. Consider an instance with n=ℓn= agents, m>cn/(α−1/ℓ)m>cn/(α-1/ ) items, and ℓ dimensions. Suppose that m is a multiple of n. For i∈Ni∈ N, gj∈Mg_j∈ M, and k∈Lk∈ L, set the valuation vijkv_ijk to 11 if j≡i+k−1(modn)j≡ i+k-1 n and 0 otherwise. For every k∈Lk∈ L, the Emax value is Emaxk=m/nEmax_k=m/n by allocating each item gjg_j to the agent i≡j−k+1(modn)i≡ j-k+1 n. Fix any allocation A. Then, there is an agent i∗∈Ni^*∈ N such that |Ai∗|≤m/n|A_i^*|≤ m/n. Moreover, there is a dimension k∗∈Lk^*∈ L such that vi∗(Ai∗)k∗≤|Ai∗|/ℓ≤m/(nℓ)v_i^*(A_i^*)_k^*≤|A_i^*|/ ≤ m/(n ). Indeed, for fixed i∗i^*, each item contributes value 11 to agent i∗i^* in exactly one dimension, so ∑k∈Lvi∗(Ai∗)k=|Ai∗| _k∈ Lv_i^*(A_i^*)_k=|A_i^*| and the claim follows by averaging. Thus, vi∗(Ai∗)k∗ v_i^*(A_i^*)_k^* ≤mnℓ=αmn−(α−1ℓ)⋅mn<α⋅mn−c ≤ mn =α mn- (α- 1 )· mn<α· mn-c (29) ≤αEmaxk∗−maxB⊆M∖Ai∗:|B|≤c∑g∈Bmaxi∈Nvi(g)k∗, ≤ _k^*- _B M A_i^*:\,|B|≤ c _g∈ B _i∈ Nv_i(g)_k^*, (30) which implies that A is not α-sEmaxc\,c for the chosen instance. See 4.7 Proof B.11. The decision problem is in NP since a proposed allocation can be checked directly. We present a polynomial-time reduction from the Hitting set problem. In the Hitting set problem, we are given a universe U=a1,a2,…,anU=\a_1,a_2,…,a_n\, subsets S1,S2,…,Sm⊆US_1,S_2,…,S_m U, and an integer h. The goal is to check existence of a subset U′⊆U U of size h such that U′∩Sp≠∅U ∩ S_p≠ for all p∈[m]p∈[m]. It is known that this problem is NP-complete [garey1979computers]. From a given instance of the Hitting set problem, we construct an MDEA instance with agents N=[n]N=[n], items M=g1,g2,…,ghM=\g_1,g_2,…,g_h\, and dimensions L=[m]L=[m]. For i∈Ni∈ N, gj∈Mg_j∈ M, and p∈Lp∈ L, the valuation vijpv_ijp is 11 if ai∈Spa_i∈ S_p and 0 otherwise. We remark that the valuation vijpv_ijp does not depend on the item gjg_j. Intuitively, any agent who receives at least one item in the MDEA instance corresponds to an element selected as U′U in the Hitting set instance. We now show that the USW ∑i∈Nvi(Ai)p _i∈ Nv_i(A_i)_p is at least 11 for every p∈Lp∈ L if and only if the Hitting set instance is a yes-instance. Suppose that the Hitting set instance is a yes-instance, i.e., there exists a subset U′⊆U U with |U′|=h|U |=h such that U′∩Sp≠∅U ∩ S_p≠ for all p∈[m]p∈[m]. Let U′=aq1,aq2,…,aqhU =\a_q_1,a_q_2,…,a_q_h\, and consider an allocation A such that Aqt=gtA_q_t=\g_t\ for each t∈[h]t∈[h] and Ai=∅A_i= for each ai∈U∖U′a_i∈ U U . Then, for each dimension p∈Lp∈ L, the USW is ∑i∈Nvi(Ai)p=|ai∈U′:ai∈Sp|≥1 _i∈ Nv_i(A_i)_p=|\a_i∈ U :a_i∈ S_p\|≥ 1. Conversely, suppose that there exists an allocation A such that ∑i∈Nvi(Ai)p≥1 _i∈ Nv_i(A_i)_p≥ 1 for all p∈Lp∈ L. Let U′=ai∈U:Ai≠∅U =\a_i∈ U:A_i≠ \ (if the cardinality of U′U is smaller than h, we arbitrarily add elements to U′U so that its size becomes h). Then, U′∩Sp≠∅U ∩ S_p≠ by ∑i∈Nvi(Ai)p≥1 _i∈ Nv_i(A_i)_p≥ 1. Therefore, the problem of deciding whether the maximum value of minp∈L∑i∈Nvi(Ai)p _p∈ L _i∈ Nv_i(A_i)_p is at least one or zero is NP-complete. This establishes the claimed hardness results. See 4.8 Proof B.12. We present a polynomial-time reduction from the PARTITION problem, which is known to be NP-complete [garey1979computers]. In the PARTITION problem, we are given m positive integers a1,a2,⋯,ama_1,a_2,·s,a_m such that ∑j=1maj=2T _j=1^ma_j=2T. The goal is to determine whether there exists a partition (S1,S2)(S_1,S_2) of the set [m][m] such that ∑j∈S1aj=∑j∈S2aj=T _j∈ S_1a_j= _j∈ S_2a_j=T. From a given instance of the PARTITION problem, we construct an MDEA instance with agents N=1,2N=\1,2\, items M=g1,g2,…,gmM=\g_1,g_2,…,g_m\, and dimensions L=1,2L=\1,2\. For each agent i∈Ni∈ N, the valuation for item gj∈Mg_j∈ M and dimension k∈Lk∈ L is defined as vijk=ajif i=k,0if i≠k. v_ijk= casesa_j&if i=k,\\ 0&if i≠ k. cases (31) For an allocation A, we have v1(A1)1≥Tv_1(A_1)_1≥ T if and only if ∑gj∈A1aj≥T _g_j∈ A_1a_j≥ T and v2(A2)2≥Tv_2(A_2)_2≥ T if and only if ∑gj∈A2aj≥T _g_j∈ A_2a_j≥ T. Thus, the MDEA instance admits an allocation A with mink∈L∑i∈Nvi(Ai)k≥T _k∈ L _i∈ Nv_i(A_i)_k≥ T if and only if the PARTITION instance is a yes-instance. Therefore, finding an allocation A that maximizes mink∈L∑i∈Nvi(Ai)k _k∈ L _i∈ Nv_i(A_i)_k is NP-hard. See 5.1 Proof B.13. Consider an MDEA instance with agents N=1,2N=\1,2\, items M=g1,g2M=\g_1,g_2\, and dimensions L=1L=\1\. Suppose that the valuations are given by v1(g1)1=v1(g2)1=2v_1(g_1)_1=v_1(g_2)_1=2, v2(g1)1=0v_2(g_1)_1=0, and v2(g2)1=1v_2(g_2)_1=1. Then, allocation (g1,g2,∅)(\g_1,g_2\, ) is the unique PO-USW allocation, with USW value 44. In contrast, (g1,g2)(\g_1\,\g_2\) is the unique PO-ESW allocation, with ESW value 11. Therefore, PO-USW and PO-ESW are not compatible in this instance. See 5.2 Proof B.14. We begin by proving the contrapositive of the first statement. Let A be an allocation that is not PO-agent in an MDEA instance (N,M,L,(vi)i∈N)(N,M,L,(v_i)_i∈ N). Then, there exists an allocation ′A that Pareto dominates A with respect to agents, i.e., vi(Ai′)k≥vi(Ai)kv_i(A _i)_k≥ v_i(A_i)_k for every i∈Ni∈ N, k∈Lk∈ L, and vi∗(Ai∗′)k∗>vi∗(Ai∗)k∗v_i^*(A _i^*)_k^*>v_i^*(A_i^*)_k^* for some i∗∈Ni^*∈ N, k∗∈Lk^*∈ L. This implies that ′A also Pareto dominates A with respect to USW because ∑i∈Nvi(Ai′)k≥∑i∈Nvi(Ai)k _i∈ Nv_i(A _i)_k≥ _i∈ Nv_i(A_i)_k for every k∈Lk∈ L, and ∑i∈Nvi(Ai′)k∗>∑i∈Nvi(Ai)k∗ _i∈ Nv_i(A _i)_k^*> _i∈ Nv_i(A_i)_k^* for k∗∈Lk^*∈ L. Next, we prove the second statement. Consider an MDEA instance with agents N=1,2N=\1,2\, items M=gM=\g\, and dimensions L=1L=\1\. Suppose that the valuations are given by v1(g)1=2v_1(g)_1=2 and v2(g)1=1v_2(g)_1=1. Then, allocation (g,∅)(\g\, ) is the unique PO-USW allocation, with USW value 22. However, (∅,g)( ,\g\) is also a PO-agent allocation. Therefore, PO-agent does not necessarily imply PO-USW. See 5.3 Proof B.15. For the first statement, consider an MDEA instance with agents N=1,2N=\1,2\, items M=g1,g2,g3M=\g_1,g_2,g_3\, and dimensions L=1L=\1\. Suppose that the valuations are given by (v1(g1)1,v1(g2)1,v1(g3)1)=(3,2,1)(v_1(g_1)_1,v_1(g_2)_1,v_1(g_3)_1)=(3,2,1) and (v2(g1)1,v2(g2)1,v2(g3)1)=(1,3,0)(v_2(g_1)_1,v_2(g_2)_1,v_2(g_3)_1)=(1,3,0). Then, allocation (1)=(g1,g2,g3,∅)A^(1)=(\g_1,g_2,g_3\, ) is PO-agent, but not PO-ESW. In contrast, allocation (2)=(g1,g2,g3)A^(2)=(\g_1\,\g_2,g_3\) is PO-ESW, but not PO-agent. The allocation (3)=(g1,g3,g2)A^(3)=(\g_1,g_3\,\g_2\) satisfies both PO-agent and PO-ESW. Note that (3)A^(3) Pareto dominates (1)A^(1) with respect to ESW and (2)A^(2) with respect to agents. For the second statement, consider the finite set of allocations that satisfy PO-agent, and choose one, say A, that is maximal with respect to PO-ESW among this set. Such an allocation exists because every finite partially ordered set has a maximal element. We claim that A is also PO-ESW among all allocations. Suppose otherwise that some allocation B Pareto dominates A with respect to ESW. Starting from B, repeatedly apply Pareto improvements with respect to agents until reaching an allocation ⋆A that is PO-agent. Then, for every k∈Lk∈ L, each agent-Pareto improvement weakly increases every vi(Ai)kv_i(A_i)_k, and hence weakly increases mini∈Nvi(Ai)k _i∈ Nv_i(A_i)_k. Therefore, ⋆A Pareto dominates B with respect to ESW, and thus also Pareto dominates A with respect to ESW. This contradicts the choice of A as a PO-ESW-maximal allocation among all PO-agent allocations. Hence, A satisfies both PO-agent and PO-ESW. See 5.5 Proof B.16. The problem is in coNP since a Pareto improvement is a polynomial-size certificate that a given allocation is not PO-USW. We provide a reduction from the PARTITION problem. Suppose that we are given m positive integers a1,a2,⋯,ama_1,a_2,·s,a_m such that ∑j=1maj=2T _j=1^ma_j=2T. From a given instance of the PARTITION problem, we construct an MDEA instance with agents N=1,2N=\1,2\, items M=g1,g2,…,gm,gm+1M=\g_1,g_2,…,g_m,g_m+1\, and dimensions L=1,2L=\1,2\. For i∈Ni∈ N, gj∈Mg_j∈ M, k∈Lk∈ L, the valuation is defined as vijk=ajif i=k and j≤m,Tif (i,j,k)=(1,m+1,1),T−1/2if (i,j,k)=(2,m+1,2),0otherwise. v_ijk= casesa_j&if $i=k$ and $j≤ m$,\\ T&if $(i,j,k)=(1,m+1,1)$,\\ T-1/2&if $(i,j,k)=(2,m+1,2)$,\\ 0&otherwise. cases (32) The valuations are illustrated in Table˜4. Note that the USWs for an allocation A are v1(A1)1v_1(A_1)_1 and v2(A2)2v_2(A_2)_2 for the first and the second dimension, respectively. Consider the problem of checking whether ∗≔(g1,…,gm,gm+1)A^* (\g_1,…,g_m\,\g_m+1\) is a PO-USW allocation. Table 4: The valuations vijkv_ijk for the reduced instance in Theorem˜5.5. g1g_1 ⋯·s gjg_j ⋯·s gmg_m gm+1g_m+1 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 ⋯·s 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 ⋯·s 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 11 a1a_1 0 ⋯·s aja_j 0 ⋯·s ama_m 0 T 0 22 0 a1a_1 ⋯·s 0 aja_j ⋯·s 0 ama_m 0 T−1/2T-1/2 Suppose that ′A Pareto improves ∗A^* with respect to USW. Then, we have v1(A1′)1≥v1(A1∗)1=2Tv_1(A _1)_1≥ v_1(A^*_1)_1=2T, v2(A2′)2≥v2(A2∗)2=T−1/2v_2(A _2)_2≥ v_2(A^*_2)_2=T-1/2, and v1(A1′)1+v2(A2′)2>v1(A1∗)1+v2(A2∗)2=3T−1/2v_1(A _1)_1+v_2(A _2)_2>v_1(A^*_1)_1+v_2(A^*_2)_2=3T-1/2. This is possible only when v1(A1′)1=2Tv_1(A _1)_1=2T and v2(A2′)2=Tv_2(A _2)_2=T. Consequently, for I=j∈[m]:gj∈A2′I=\j∈[m]:g_j∈ A _2\, we have ∑j∈Iaj=T _j∈ Ia_j=T. Therefore, such an allocation ′A exists if and only if the PARTITION instance is a YES-instance. Hence, checking whether a given allocation is PO-USW is coNP-complete, even in the case of two agents and two dimensions. See 5.6 Proof B.17. The first statement follows from the NP-hardness of computing an Emax allocation in the single-dimensional two-agent case. We prove only the second statement. The problem is in coNP since a Pareto improvement is a polynomial-size certificate that a given allocation is not PO-ESW. We provide a reduction from the PARTITION problem. Suppose that we are given m positive integers a1,a2,⋯,ama_1,a_2,·s,a_m such that ∑j=1maj=2T _j=1^ma_j=2T. From a given instance of the PARTITION problem, we construct an MDEA instance with agents N=1,2N=\1,2\, items M=g1,g2,…,gm,gm+1M=\g_1,g_2,…,g_m,g_m+1\, and dimensions L=1,2L=\1,2\. For i∈Ni∈ N, gj∈Mg_j∈ M, k∈Lk∈ L, the valuation is defined as vijk=ajif i=1 and j≤m,Tif i=1 and j=m+1,2ajif i=2 and j≤m,2T−1/2if i=2 and j=m+1,0otherwise. v_ijk= casesa_j&if $i=1$ and $j≤ m$,\\ T&if $i=1$ and $j=m+1$,\\ 2a_j&if $i=2$ and $j≤ m$,\\ 2T-1/2&if $i=2$ and $j=m+1$,\\ 0&otherwise. cases (33) The valuations are illustrated in Table˜5. Consider the problem of checking whether ∗≔(g1,…,gm,gm+1)A^* (\g_1,…,g_m\,\g_m+1\) is a PO-ESW allocation. Note that the ESW value for ∗A^* is minv1(A1∗)1,v2(A2∗)1=min2T,2T−1/2=2T−1/2 \v_1(A^*_1)_1,v_2(A^*_2)_1\= \2T,2T-1/2\=2T-1/2. Table 5: The valuations vijkv_ijk for the reduced instance in Theorem˜5.6. g1g_1 ⋯·s gjg_j ⋯·s gmg_m gm+1g_m+1 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 ⋯·s 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 ⋯·s 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 1 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,11 2 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,12 11 a1a_1 a1a_1 ⋯·s aja_j aja_j ⋯·s ama_m ama_m T T 22 2a12a_1 2a12a_1 ⋯·s 2aj2a_j 2aj2a_j ⋯·s 2am2a_m 2am2a_m 2T−1/22T-1/2 2T−1/22T-1/2 Suppose that ′A has a strict better ESW value than ∗A^*. Then, we have v1(A1′)1≥2Tv_1(A _1)_1≥ 2T and v2(A2′)1≥2Tv_2(A _2)_1≥ 2T. This is possible only when v1(A1′)1=2Tv_1(A _1)_1=2T and v2(A2′)1=2Tv_2(A _2)_1=2T. Consequently, for I=j∈[m]:gj∈A2′I=\j∈[m]:g_j∈ A _2\, we have ∑j∈Iaj=T _j∈ Ia_j=T. Therefore, such an allocation ′A exists if and only if the PARTITION instance is a YES-instance. Hence, checking whether a given allocation is PO-ESW is coNP-complete, even in the case of two agents and two dimensions.