The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective^†^†thanks: The author names are ordered alphabetically.

Alexander Lam Department of Computer Science, City University of Hong Kong. [email protected] Bo Li Department of Computing, The Hong Kong Polytechnic University. [email protected] Ankang Sun Department of Computing, The Hong Kong Polytechnic University. [email protected]

Abstract

We adopt a parametric approach to analyze the worst-case degradation in social welfare when the allocation of indivisible goods is constrained to be fair. Specifically, we are concerned with cardinality-constrained allocations, which require that each agent has at most $k$ items in their allocated bundle. We propose the notion of the price of cardinality, which captures the worst-case multiplicative loss of utilitarian or egalitarian social welfare resulting from imposing the cardinality constraint. We then characterize tight or almost-tight bounds on the price of cardinality as exact functions of the instance parameters, demonstrating how the social welfare improves as $k$ is increased. In particular, one of our main results refines and generalizes the existing asymptotic bound on the price of balancedness, as studied by Bei et al. [BLMS21]. We also further extend our analysis to the problem where the items are partitioned into disjoint categories, and each category has its own cardinality constraint. Through a parametric study of the price of cardinality, we provide a framework which aids decision makers in choosing an ideal level of cardinality-based fairness, using their knowledge of the potential loss of utilitarian and egalitarian social welfare.

1 Introduction

The allocation of indivisible goods to a set of agents is a ubiquitous problem in our society, capturing a number of real-world scenarios. For example, an inheritance may involve indivisible goods such as jewelry, cars, and estates, and food banks are constantly faced with the task of allocating donations to people in need. In a corporate setting, equipment and human resources such as developers and designers need to be assigned to various projects and departments. These real-world scenarios often involve constraints which are imposed on the allocation, which may make the allocation difficult to compute, or prevent it from being socially optimal.

The most commonly studied constraint in resource allocation is the requirement that the allocation should be fair to the agents [AAB⁺23]. Fairness constraints can be expressed in several different ways: a proportional allocation guarantees that each of the $n$ agents receives at least $\frac{1}{n}$ th of their utility for the entire set of items, and in a balanced allocation, the goods are spread out among the agents as evenly as possible, so that the number of items received by each agent differs by at most one. The latter notion of balancedness is a natural constraint which may be imposed by the central decision maker due to its simplicity and ease of implementation, without requiring knowledge of the agents’ utilities. However, this constraint may severely degrade the social welfare of the allocation. This is particularly true in instances where agents have low utility for a large number of items, rather than highly valuing a small subset of items, motivating the need for a weaker, more variable notion of ‘cardinal fairness’.

The main focus of our paper is on the constraint of cardinality, a generalization of balancedness which imposes an upper limit of $k$ on the number of items an agent may receive from the allocation.¹¹1Note that the cardinality constraint is equivalent to balancedness when $m\in\{kn-k+1,kn-k+2,\dots,kn\}$ , where $m$ is the total number of items. The cardinality constraint is commonly applied in practice. For example, when a university provides funding to support PhD students, it is typical to impose a limit on the number of students each professor can supervise, due to fairness concerns. Intuitively, the potential loss of welfare decreases as $k$ increases. The central decision maker may vary the parameter of $k$ to achieve their desired tradeoff between the level of balancedness and the social welfare of the cardinality-constrained allocation. More generally, the items may also be partitioned into disjoint categories, where each category $j$ has its own cardinality constraint of $k_{j}$ . However, the exact effect of the value of $k$ on the social welfare objectives remains unclear, leading to the following research question which we address in this paper:

What is the worst-case (multiplicative) loss of social welfare when there is a limit on the number of items each agent can receive in an allocation, and how does the loss change as the limit is varied?

In particular, we aim to quantify this loss in an exact sense, as opposed to the asymptotic bounds which are common in the literature. This helps with making a more informed decision on the cardinality constraint values, particularly in scenarios where the number of agents and/or items is small.

1.1 Our Contribution

In this work, we initiate the study of price of cardinality from the parametric perspective. We define the price of cardinality as the worst-case ratio between the welfare of the optimal allocation, and the optimal welfare among all cardinality-constrained allocations. Our work concerns both utilitarian and egalitarian social welfare, defined as the sum of agents’ utilities and worst-off agent’s utility respectively. For both objectives, we establish tight or almost-tight bounds for the price of cardinality in both the single-category and multi-category cases, expressing the prices as exact functions of the cardinality parameters, as opposed to the common asymptotic bounds in the literature. A benefit of our parametrized approach is that it enables decision makers to choose their desired level of fairness based on the potential loss of social welfare. We summarize our main results as follows.

Single category.

We start with the single category case, where each agent can receive at most $k$ items. We show that for any instance with $n$ agents and $m$ items such that $k\geq\frac{m}{n}$ , the utilitarian price of cardinality is $\frac{1}{2}\left(1+\sqrt{1+\frac{m-1}{k}}\right)$ . This can be visualized in Figure 1 as a function of the ratio $\frac{k}{m-1}$ . We note that this bound is precisely tight for instances where $m$ and $k$ satisfy a divisibility constraint, and tight up to an additive constant that is smaller than 1 for every instance. Furthermore, when $m=kn$ , this result coincides with (and refines) the asymptotic bound of $\Theta(\sqrt{n})$ for the price of balancedness [BLMS21].

For the objective of egalitarian social welfare, we present an exact bound of $\max\{\frac{m-n+1}{k},1\}$ which is tight for all instances. This result shows that when $k$ is small compared to $m$ , the cardinality constraint may adversely affect the egalitarian fairness of the allocation, particularly when the allocation is constrained to be balanced (i.e., $m=kn$ ).

Refer to caption — Figure 1: Plot of the utilitarian price of cardinality in the single-category setting as a function of $\frac{k}{m-1}$ .

Multiple categories.

For utilitarian social welfare, we first focus on the case of two agents, giving an exact and tight bound of $\frac{2m_{1}m_{2}}{m_{2}k_{1}+m_{1}k_{2}}$ for the utilitarian price of cardinality.²²2We order the categories such that $\frac{k_{1}}{m_{1}}\leq\frac{k_{2}}{m_{2}}\leq\dots\leq\frac{k_{h}}{m_{h}}$ , where $k_{j}$ and $m_{j}$ denote the cardinality constraint and number of items in category $j$ , respectively. For the case of general $n$ agents, we establish a utilitarian price of cardinality of $\frac{m_{1}}{k_{1}}$ , which is tight for instances where there are $n$ categories and $\frac{k_{1}}{m_{1}}=\dots=\frac{k_{n}}{m_{n}}$ .

Finally, in the multi-category case, we establish an exact bound for egalitarian price of cardinality as a function of $n$ , the cardinality constraints $k_{j}$ , and the number of items in each category $m_{j}$ , and this bound is tight for all instances.

For all of our main results, we also describe how a cardinal allocation with guaranteed welfare corresponding to the respective price of cardinality can be found.

1.2 Related Work

The problem of allocating a set of indivisible goods to self-interested agents has been extensively studied in computer science and economics in recent years, with a primary focus on finding allocations which are constrained to be ‘fair’ in some axiomatic sense (see, e.g., the seminal papers by Gamow and Stern [GS58], Steinhaus [Ste48], Varian [Var74] and the surveys by Amanatidis et al. [AAB⁺23], Walsh [Wal20]). Common fairness notions have been shown to be compatible with cardinality constraints: for example, Biswas and Barman [BB18] and Hummel and Hetland [HH22] considered how to compute EF1 and approximate MMS allocations under cardinality constraints.

While most related work is concerned with computing fair allocations, there is a growing body of research on quantifying the degradation of welfare when fairness constraints are imposed. This was first proposed by Caragiannis et al. [CKKK12], and results on the price of fairness have since been extended by Barman et al. [BBS20], Li et al. [LLW22], and Li et al. [LLL⁺24]. These papers generally examine the effect of fairness constraints from an asymptotic perspective, e.g., the prices of EF1 and $\frac{1}{2}$ -MMS are $\Theta(\sqrt{n})$ , and since computing the exact bound can be challenging for every value of $n$ , the literature often restricts to the case where $n=2$ . In particular, the paper by Bei et al. [BLMS21] gives an asymptotic bound of $\Theta(\sqrt{n})$ (and a precise bound of $4/3$ for $n=2$ ) for the price of balancedness for utilitarian social welfare. The price of fairness has also been studied in the allocations of indivisible chores [SCD23b, SCD23a, SL24]. As asymptotic bounds may obscure the precise effects of constraints (particularly in scenarios with a small number of agents), this paper aims to generalize the existing asymptotic bound on the price of balancedness to the exact bound on the price of cardinality, and extend the results to multiple categories.

Beyond cardinality constraints, other types of constraints such as connectivity [BCE⁺17, BLLS24, SL23], geometric [SHNHA17], and separation [ESHS22] have also been studied in the context of fair division. In particular, the cardinality constraint in the single-category case is equivalent to budget-feasibility (as studied by Wu et al. [WLG21]) when agents have identical budgets and items have identical costs. For a recent overview on constraints in fair division, we refer the readers to the survey by Suksompong [Suk21].

2 Preliminaries

For any $k\in\mathbb{N}^{+}$ , denote $[k]\coloneqq\{1,\ldots,k\}$ . We have a set $N$ of $n$ agents who are to receive a set $M=\{g_{1},\ldots,g_{m}\}$ of $m$ indivisible goods. Each agent $i\in N$ has a utility function $u_{i}:2^{M}\rightarrow\mathbb{R}_{\geq 0}$ over each possible subset of goods. Let $\mathcal{U}=(u_{1},u_{2},\dots,u_{n})$ denote the agents’ utility profiles. Throughout the paper, we assume the utilities are additive (i.e., $u_{i}(S)=\sum_{g\in S}u_{i}(\{g\})$ ) and normalized (i.e., $u_{i}(\emptyset)=0$ and $u_{i}(M)=1$ for each $i\in N$ ). We slightly abuse notation and write $u_{i}(g)$ instead of $u_{i}(\{g\})$ .

An allocation $\mathcal{A}$ is a partition of the items into $n$ disjoint bundles $\mathcal{A}=(A_{1},\dots,A_{n})$ , with agent $i$ receiving $A_{i}$ . The set of goods is partitioned into $h$ different non-overlapping categories $C=\{C_{1},\dots,C_{h}\}$ , with respective cardinality constraints $k_{1},\dots,k_{h}$ . The cardinality constraint $k_{j}$ specifies the maximum number of items from category $C_{j}$ that each agent can have under a cardinal allocation. In other words, an allocation $\mathcal{A}$ is cardinal if for each bundle $A_{i}$ and category $C_{j}$ , $|A_{i}\cap C_{j}|\leq k_{j}$ holds. Our prices of cardinality will be expressed in terms of the number of agents $n$ , the cardinality constraints $k_{j}$ , and the number of items in each category, so for simplicity, we denote, for each $j\in[h]$ , $m_{j}\coloneqq|C_{j}|$ and $m=\sum_{j}m_{j}$ . We also assume that for each $j\in[h]$ , $k_{j}\geq\frac{m_{j}}{n}$ so that every item can be allocated. In the single-category scenario (i.e., $h=1$ ), we slightly abuse notation and use $m$ and $k$ instead of $m_{1}$ and $k_{1}$ to refer to the number of items and the cardinality constraint, respectively.

We refer to a problem setting with agents $N$ , goods $M$ , utility profile $\mathcal{U}$ and partition of goods into categories $C$ as an instance, denoted as $I=\langle N,M,\mathcal{U},C\rangle$ .

Our results are concerned with the following objectives of utilitarian social welfare and egalitarian social welfare.

Definition 1.

Given an instance $I$ and an allocation $\mathcal{A}=(A_{1},\dots,A_{n})$ of the instance,

•

the utilitarian social welfare, or the sum of the agents’ utilities, is denoted by $\text{USW}(\mathcal{A})\coloneqq\sum_{i\in N}u_{i}(A_{i})$ .
•

the egalitarian social welfare, or the utility of the worst-off agent, is denoted by $\text{ESW}(\mathcal{A})\coloneqq\min_{i\in N}u_{i}(A_{i})$ .

We denote the optimal utilitarian (resp. egalitarian) social welfare over all possible allocations of an instance $I$ as $\text{OPT-USW}(I)$ (resp. $\text{OPT-ESW}(I)$ ).

Given an instance $I$ and cardinality constraints $\kappa=(k_{1},\dots,k_{h})$ , let the set of all cardinal allocations be denoted as $\mathcal{C}_{\kappa}(I)$ . We now define the main concept of our paper: the price of cardinality, for our objective functions of utilitarian and egalitarian social welfare.

Definition 2.

The utilitarian price of cardinality is defined as

\sup_{I=\langle N,M,\mathcal{U},C\rangle,\kappa=(k_{1},\dots,k_{h})}\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}.

Definition 3.

The egalitarian price of cardinality is defined as

\sup_{I=\langle N,M,\mathcal{U},C\rangle,\kappa=(k_{1},\dots,k_{h})}\frac{\text{OPT-ESW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{ESW}(\mathcal{A})}.

For an instance $I$ , if $\text{OPT-ESW}(I)=0$ , we define that $\frac{0}{0}=1$ and the egalitarian price of cardinality to be $1$ .

3 Single Category

We first give results for the case where there is only one category, and therefore only one cardinality constraint $k$ . Note that if $m\leq k$ , then the cardinality constraint will have no effect, and the price of cardinality will be equal to $1$ . We therefore assume that $m>k$ throughout this section.

3.1 Utilitarian Social Welfare

We begin with the utilitarian price of connectivity in the single category setting. Interestingly, the price of cardinality for utilitarian welfare is only directly dependent on the number of items and the cardinality constraint, and not directly dependent on the number of agents (it is not entirely independent of $n$ as we require $n\geq\frac{m}{k}$ ).

Theorem 1.

In the single-category case, the utilitarian price of cardinality is

\frac{1}{2}\left(1+\sqrt{1+\frac{m-1}{k}}\right).

Proof.

The lower bound will be proven in Lemma 1, and the upper bound will be proven in Lemmas 3 and 5. ∎

It is worth noting that the stated price of cardinality expression is tight in a very strong sense:

•

For any instance with cardinality constraint $k$ and $m$ items, the utilitarian price of cardinality is at most $\frac{1}{2}\left(1+\sqrt{1+\frac{m-1}{k}}\right)$ .
•

As we will shortly show in Lemma 1, for any instance with cardinality constraint $k$ and $m=k(c^{2}-1)+1$ items, where $c\in\mathbb{N}^{+}\setminus\{1\}$ , the utilitarian price of cardinality is exactly $\frac{1}{2}\left(1+\sqrt{1+\frac{m-1}{k}}\right)$ .
•

In Lemma 2, we further show that for any other instance with cardinality constraint $k$ , the utilitarian price of cardinality is at least $\frac{1}{2}\left(-1+\sqrt{1+\frac{m-1}{k}}\right)$ .

This is due to the lower bound construction requiring $m$ and $k$ to meet a divisibility constraint. Specifically, there is a set of agents who each value the same item $g_{m}$ at one utility, and the remaining agents’ utilities are such that they each receive the same number of items under the utilitarian-optimal allocation.

Lemma 1.

In the single-category case, if $m=k(c^{2}-1)+1$ for some $c\in\mathbb{N}^{+}\setminus\{1\}$ , then the utilitarian price of cardinality is at least $\frac{1}{2}\left(1+\sqrt{1+\frac{m-1}{k}}\right).$

Proof.

Let $I$ be an instance with cardinality constraint $k$ and $m=k(c^{2}-1)+1$ items for some $c\in\mathbb{N}^{+}\setminus\{1\}$ , and let $s\coloneqq-1+\sqrt{1+\frac{m-1}{k}}$ . Note that

•

$s=c-1\in\mathbb{N}^{+}$ ,
•

and $\frac{m-1}{s}=\frac{k(c^{2}-1)}{c-1}\in\mathbb{N}^{+}$ .

The agents’ utilities are as follows:

•

for $i=1,\ldots,s$ , if $j=(i-1)\frac{m-1}{s}+1,\ldots,i\frac{m-1}{s}$ , then $u_{i}(g_{j})=\frac{s}{m-1}$ ; otherwise, $u_{i}(g)=0$ ;
•

for $i\geq s+1$ , $u_{i}(g_{m})=1$ and $u_{i}(g)=0$ for each $g\in M\setminus\{g_{m}\}$ .

We have $\text{OPT-USW}(I)=1+s$ as in the utilitarian-optimal allocation, each agent $i\in[s]$ receives utility $1$ , and agents $s+1,\ldots,n$ have a total utility of $1$ . We also have $\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})=1+\frac{ks^{2}}{m-1}$ by letting every agent $i\in[s]$ keep their $k$ most valued items; note $\frac{m-1}{s}>k$ . Dividing these terms and substituting $s=-1+\sqrt{1+\frac{m-1}{k}}$ , we get our price of cardinality lower bound of $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}=\frac{1}{2}\left(1+\sqrt{1+\frac{m-1}{k}}\right)$ . ∎

Note that if the divisibility constraint is not met by $m$ and $k$ (i.e., $m\neq k(c^{2}-1)+1$ for all $c\in\mathbb{N}^{+}\setminus\{1\}$ ), we can still construct a similar lower bound which will be slightly lower than our general upper bound (as exemplified in Figure 2). We take $s=\lfloor-1+\sqrt{1+\frac{m-1}{k}}\rfloor$ , and let agents $1,\dots,s$ each equally value a disjoint subset of the items $g_{1},\dots,g_{m-1}$ , such that the number of goods they positively value differs by at most $1$ . The gap between the upper and lower bound here is due to the rounding of $s$ and the partitioning of $m-1$ items among $s$ agents as evenly as possible. Furthermore, the following lemma implies that the price of cardinality lower bound corresponding to this instance construction differs from our stated upper bound by an additive constant of at most $1$ .

Lemma 2.

In the single-category case, if $m\neq k(c^{2}-1)+1$ for all $c\in\mathbb{N}^{+}\setminus\{1\}$ , then the utilitarian price of cardinality is at least $\frac{1}{2}\left(-1+\sqrt{1+\frac{m-1}{k}}\right).$

The missing proofs are deferred to the appendix. We now prove the upper bound of Theorem 1, which holds for any $m$ and $k$ . First, we fix an arbitrary instance $I$ with $m$ items and cardinality constraint $k$ , and denote the utilitarian-optimal allocation³³3In the case of ties, the tiebreak procedure will be described in the upcoming proofs when necessary. of $I$ by $\mathcal{A}^{*}=(A^{*}_{1},\ldots,A^{*}_{n})$ . We then define the following subsets of agents. Under $\mathcal{A}^{*}$ ,

•

The set of agents receiving less than $k$ items is $R=\{i\in[n]:|A^{*}_{i}|<k\}$ .
•

The set of agents receiving exactly $k$ items is $T=\{i\in[n]:|A^{*}_{i}|=k\}$ .
•

The set of agents receiving more than $k$ items is $S=\{i\in[n]:|A^{*}_{i}|>k\}$ .

We can also assume that $\mathcal{A}^{*}$ does not satisfy the cardinality constraint, and hence $S\neq\emptyset$ , implying $R\neq\emptyset$ . We next divide the proof of the upper bound into two cases depending on whether $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})\geq 1$ or $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})<1$ . We begin with the former case.

Lemma 3.

Let $I$ be a (possibly non-normalized) instance satisfying $0<u_{i}(M)\leq 1$ for each $i\in S$ and $\sum_{i\in N}\setminus Su_{i}(A^{*}_{i})\geq 1$ , where $S$ is the set of agents who receive more than $k$ items under utilitarian-optimal allocation $\mathcal{A}^{*}=(A^{*}_{1},\ldots,A^{*}_{n})$ . Then,

\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{1+\sum_{i\in S}u_{i}(A^{*}_{i})}{1+k\sum_{i\in S}\frac{u_{i}(A^{*}_{i})}{|A^{*}_{i}|}}\leq\frac{1+s}{1+\frac{ks^{2}}{m-1}},

where $s=-1+\sqrt{1+\frac{m-1}{k}}$ .

Proof Sketch.

We present a proof sketch for the inequality $\frac{1+\sum_{i\in S}u_{i}(A^{*}_{i})}{1+k\sum_{i\in S}\frac{u_{i}(A^{*}_{i})}{|A^{*}_{i}|}}\leq\frac{1+s}{1+\frac{ks^{2}}{m-1}}.$ By taking derivatives, we find that the LHS is maximized when every $u_{i}(A^{*}_{i})$ is either $1$ or $0$ . This gives us

	$\displaystyle\frac{1+\sum_{i\in S}u_{i}(A^{}_{i})}{1+k\sum_{i\in S}\frac{u_{i}(A^{}_{i})}{\|A^{*}_{i}\|}}$	$\displaystyle\leq\frac{1+\sum_{i\in S^{\prime}}1}{1+k\sum_{i\in S^{\prime}}\frac{1}{A^{*}_{i}}}$
		$\displaystyle\leq\frac{1+\|S^{\prime}\|}{1+\frac{k\|S^{\prime}\|^{2}}{m-1}}\leq\frac{1+s}{1+\frac{ks^{2}}{m-1}},$

where $s=-1+\sqrt{1+\frac{m-1}{k}}$ . Here, the second inequality follows from the arithmetic mean-harmonic mean (AM-HM) inequality, and the final inequality follows from taking derivatives with respect to $|S^{\prime}|$ . ∎

We now address the remaining case where $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})<1$ . In this case, we assume that instance $I$ is preprocessed such that for each $j\in R$ , $\sum_{i\in S}u_{j}(A^{*}_{i}):=1-\sum_{i\in R\cup T}u_{i}(A^{*}_{i}).$ As $\mathcal{A}^{*}$ is the utilitarian-optimal allocation, we have $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})\geq\sum_{i\in R\cup T}u_{j}(A^{*}_{i})$ for all $j\in R$ , and therefore before processing, we have $\sum_{i\in S}u_{j}(A^{*}_{i})\geq 1-\sum_{i\in R\cup T}u_{i}(A^{*}_{i})$ . Accordingly, this preprocessing can be achieved by reducing the utility that each agent $j\in R$ has for items $\{A^{*}_{i}\}_{i\in S}$ until we reach $\sum_{i\in S}u_{j}(A^{*}_{i})=1-\sum_{i\in R\cup T}u_{i}(A^{*}_{i})$ . The new/preprocessed instance is not necessarily normalized, meaning there may exist $i\in R$ such that $0\leq u_{i}(M)\leq 1$ . Note that the optimal utilitarian welfare does not change before and after the preprocessing, but the optimal utilitarian welfare among cardinal allocations weakly decreases after preprocessing, meaning that $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$ weakly increases. We also remark that the preprocessing does not affect $S,R,$ or $T$ .

Before proving the price of cardinality upper bound for the case where $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})<1$ , we find a lower bound on the utilitarian social welfare of a cardinal allocation, for any arbitrary instance $I$ .⁴⁴4We remark that the lemma holds regardless of whether $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})<1$ or $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})\geq 1$ , and whether or not $I$ is preprocessed.

Lemma 4.

For an arbitrary instance $I$ , there exists a cardinal allocation $\mathcal{A}$ such that $\text{USW}(\mathcal{A})\geq 1+\sum_{i\in S}\frac{k}{|A^{*}_{i}|}(u_{i}(A^{*}_{i})-u_{i^{\dagger}}(A^{*}_{i}))$ for some agent $i^{\dagger}\in R$ .

Proof Sketch.

In the full proof, we show that there exists a cardinal allocation $\mathcal{A}$ such that $\text{USW}(\mathcal{A})\geq\sum_{i\in R\cup T}u_{i}(A^{*}_{i})+\sum_{i\in S}\frac{k}{|A^{*}_{i}|}u_{i}(A^{*}_{i})+\sum_{i\in S}\frac{|A^{*}_{i}|-k}{|A^{*}_{i}|}u_{i^{\dagger}}(A^{*}_{i})$ , which suffices because we have $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})=1-\sum_{i\in S}u_{i^{\dagger}}(A^{*}_{i}).$ (Recall that $I$ is preprocessed). Specifically, this cardinal allocation can be achieved by the following greedy procedure.

The procedure starts from $\mathcal{A}^{*}$ , and at each step, reassigns the item with the least utility loss from some unsatisfied agent’s bundle to some active agent; an agent is unsatisfied if she receives more than $k$ items, and is active if she receives less than $k$ items.

•

Step 1: Set $\mathcal{B}\leftarrow\mathcal{A}^{*}$ as the initial allocation, $P\leftarrow S$ as the initial set of unsatisfied agents, and $Q\leftarrow R$ as the initial set of active agents;
•

Step 2: If there are no unsatisfied agents, then terminate and output the underlying allocation $\mathcal{B}$ (this will be $\mathcal{A}^{k}$ ). Otherwise, find the item $e^{*}\in\bigcup_{i\in P}B_{i}$ and an active agent $i^{*}\in Q$ such that reassigning $e^{*}$ to agent $i^{*}$ causes the minimum utilitarian social welfare loss among all single-item reassignments from items of unsatisfied agents to active agents. Reassign $e^{*}$ to agent $i^{*}$ , and update $\mathcal{B}$ accordingly.
•

Step 3: Update $P$ and $Q$ , and return to Step 2.

As $m\leq kn$ , the procedure can terminate and the returned allocation $\mathcal{A}^{k}$ is cardinal. Moreover, during the reassignment process, an active agent can never become unsatisfied and any unsatisfied agent can never become active. ∎

We now prove the upper bound for Theorem 1 for the case where $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})<1$ .

Lemma 5.

If $\sum_{i\in R\cup T}u_{i}(A^{*}_{i})<1$ , then

\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{1+s}{1+\frac{ks^{2}}{m-1}},

where $s=-1+\sqrt{1+\frac{m-1}{k}}$ .

Partial Proof.

We first describe the tiebreak procedure for the utilitarian-optimal allocation $\mathcal{A}^{*}$ . If multiple agents are tied for having the highest utility for an item, we pick the allocation $\mathcal{A}^{*}$ based on the following criteria;

•

if it is possible to allocate each item to the agent that values it most, such that all $m$ items are owned by agents with strictly more than $k$ items, then $\mathcal{A}^{*}$ is defined as this allocation,
•

otherwise, the tie is broken in favour of the agent with less than $k$ items.

We divide the remainder of the proof into two cases, depending on whether or not all of the goods are allocated to agents in $S$ under $\mathcal{A}^{*}$ .

Case 1: $\sum_{i\in S}|A^{*}_{i}|<m$ . We present the full proof for the case where not all items are allocated to agents in $S$ under $\mathcal{A}^{*}$ . Recall that by Lemma 4, there exists an agent $i^{\dagger}\in R$ and a cardinal allocation $\mathcal{A}^{k}$ such that $\text{USW}(\mathcal{A}^{k})\geq 1+\sum_{i\in S}\frac{k}{|A^{*}_{i}|}(u_{i}(A^{*}_{i})-u_{i^{\dagger}}(A^{*}_{i})).$

Consider the agent $i^{\dagger}\in R$ and a specific item $g^{\dagger}\in\bigcup_{i\in R\cup T}A^{*}_{i}$ ; the existence of $g^{\dagger}$ is guaranteed due to $\sum_{i\in S}|A^{*}_{i}|<m$ . We construct another (possibly non-normalized) instance $I^{\prime}$ which differs from $I$ only by the agents’ utilities. Below, we describe the utility function $u^{\prime}$ that each agent has in $I^{\prime}$ ,

•

for $i\in R\cup T$ , $u^{\prime}_{i}(g^{\dagger})=1$ and $u^{\prime}_{i}(g)=0$ for all $g\neq g^{\dagger}$ ;
•

for $i\in S$ , $u^{\prime}_{i}(g)=u_{i}(g)-u_{i^{\dagger}}(g)$ if $g\in A^{*}_{i}$ and $u^{\prime}(g)=0$ otherwise.

Denote by $\mathcal{A}^{\prime}$ the utilitarian-optimal allocation of $I^{\prime}$ and by $S^{\prime}$ the set of agents receiving more than $k$ items in $\mathcal{A}^{\prime}$ ; note that $S^{\prime}=S$ . Due to $\sum_{i\in S}|A^{*}_{i}|<m$ , when picking $\mathcal{A}^{*}$ , if multiple agents are tied for having the highest utility for an item, then the tie is broken in favour of the agent with less than $k$ items. As a consequence, for any $i\in S$ and $g\in A^{*}_{i}$ , $u^{\prime}_{i}(g)>0$ due to $i^{\dagger}\in R$ .

Now we show that in $I^{\prime}$ , $0<u^{\prime}_{i}(A^{\prime}_{i})\leq 1$ for each $i\in S^{\prime}$ . From the construction of $u^{\prime}_{i}()$ , we immediately have $u^{\prime}_{i}(A^{\prime}_{i})\leq 1$ . To prove $0<u^{\prime}_{i}(A^{\prime}_{i})$ , since agent $i$ is the only one with positive utility on the items in bundle $A^{*}_{i}$ , we have $A^{*}_{i}\subsetneq A^{\prime}_{i}$ and hence $0<u^{\prime}_{i}(A^{\prime}_{i})$ ; note that $u^{\prime}_{i}(g)>0$ for every $g\in A^{*}_{i}$ .

We now present the upper bound of the ratio regarding $I$ for Case 1 as follows,

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{\sum_{i\in R\cup T}u_{i}(A^{}_{i})+\sum_{i\in S}u_{i}(A^{}_{i})}{\text{USW}(\mathcal{A}^{k})}$
		$\displaystyle=\frac{1-\sum_{i\in S}u_{i^{\dagger}}(A^{}_{i})+\sum_{i\in S}u_{i}(A^{}_{i})}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{*}_{i}))}$
		$\displaystyle=\frac{1+\sum_{i\in S}u^{\prime}_{i}(A^{\prime}_{i})}{1+\sum_{i\in S}\frac{k}{\|A_{i}\|}u^{\prime}_{i}(A^{\prime}_{i})}$
		$\displaystyle=\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$
		$\displaystyle\leq\frac{1}{2}\left(\sqrt{1+\frac{m-1}{k}}+1\right),$

where the first equality results from the property of the preprocessed instance and the fact that $i^{\dagger}\in R$ ; the last inequality transition follows from Lemma 3. ∎

Finally, we conclude the section with the following result on computing utilitarian-optimal cardinal allocations.

Proposition 1.

Given a single-category instance $I$ and cardinality constraint $k$ , the utilitarian-optimal cardinal allocation can be found in polynomial time, and has a utilitarian social welfare of at least $\frac{2}{1+\sqrt{1+\frac{m-1}{k}}}\cdot\text{OPT-USW}(I)$ .

Proof.

Consider a complete bipartite graph $G=(U,V,E)$ , where $U$ represents $k$ copies of each agent, and $V$ represents the $m$ goods, with zero-valued dummy items added such that $|U|=|V|$ . Also, an edge between agent $i\in U$ and item $g\in V$ has weight equal to $u_{i}(g)$ . Our desired allocation can be found by computing a maximum weight bipartite matching, such as by using the Hungarian algorithm [Kuh55]. The utilitarian social welfare guarantee follows immediately from Theorem 1. ∎

3.2 Egalitarian Social Welfare

We now move to the objective of egalitarian social welfare, where the worst-case degradation of worst-case fairness objective is quantified by our exact and tight bounds on the egalitarian price of cardinality. Note that in addition to the assumption that $m>k$ , we also assume in this subsection that $m\geq n$ , because if $m<n$ , then $\text{OPT-ESW}(I)=0$ and consequently, the egalitarian price of cardinality will be $1$ .

Theorem 2.

In the single-category case, the egalitarian price of cardinality is $\max\left\{\frac{m-n+1}{k},1\right\}$ .

Proof.

We begin by proving the upper bound and consider instance $I$ . If $\text{OPT-ESW}(I)=0$ , the statement holds trivially, so we assume $\text{OPT-ESW}(I)>0$ for the remainder of the proof. Denote by $\mathcal{A}^{*}=(A^{*}_{1},\ldots,A^{*}_{k})$ the unconstrained egalitarian-optimal allocation. If $|A^{*}_{i}|\leq k$ holds for each $i\in N$ , then the egalitarian-optimal cardinal allocation is the same as $\mathcal{A}^{*}$ , and thus the theorem statement holds for this case. We now focus on the remaining case where $\max_{i\in N}|A_{i}|>k$ .

Let $S$ be the set of agents who each receive more than $k$ items in $\mathcal{A}^{*}$ . We now consider a cardinal allocation $\mathcal{A}^{\prime}$ where each $i\in S$ receives their $k$ most valued items from $A^{*}_{i}$ and for each agent $j\notin S$ , $A^{*}_{j}\subseteq A^{\prime}_{j}$ ; note that $\mathcal{A}^{\prime}$ can be cardinal due to $m\leq kn$ . Then we have the following,

	$\displaystyle\text{ESW}(\mathcal{A}^{\prime})$	$\displaystyle=\min\left\{\min_{i\in S}u_{i}(A^{\prime}_{i}),\min_{i\notin S}u_{i}(A^{\prime}_{i})\right\}$
		$\displaystyle\geq\min\left\{\min_{i\in S}k\cdot\frac{u_{i}(A^{}_{i})}{\|A^{}_{i}\|},\text{OPT-ESW}(I)\right\}$
		$\displaystyle\geq k\cdot\frac{\text{OPT-ESW}(I)}{m-n+1},$

where the last inequality transition is due to $|A^{*}_{j}|\geq 1$ for all $j\in N$ (and hence $|A^{*}_{i}|\leq m-n+1$ for all $i$ ). As a consequence, we have

\frac{\text{OPT-ESW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{ESW}(\mathcal{A})}\leq\frac{\text{OPT-ESW}(I)}{\text{ESW}(\mathcal{A}^{\prime})}\leq\frac{m-n+1}{k},

completing the proof of the upper bound.

For the lower bound, consider instance $I$ where the agents’ utility functions are as follows;

•

for $i\in[n-1]$ , $u_{i}(g_{i})=1$ and $u_{i}(g_{j})=0$ for all $j\neq i$ ;
•

for $i=n$ , $u_{n}(g_{j})=0$ for each $j\in[n-1]$ and $u_{n}(g_{j})=\frac{1}{m-n+1}$ for each $j\geq n$ .

By allocating each $g_{i}$ to $i$ for each $i\in[n-1]$ and allocating all of the remaining items to agent $n$ , we see that $\text{OPT-ESW}(I)=1$ . On the other hand, $\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{ESW}(\mathcal{A})=\frac{k}{m-n+1}$ as agent $k$ can receive at most $k$ items, deriving the desired lower bound. ∎

Note that this bound is tight for all feasible values of $m$ , $n$ , and $k$ . This result shows that when $m$ is large compared to $n$ and $k$ , there may be a significant reduction in egalitarian fairness when cardinality constraints are naively imposed in pursuit of a fair allocation. We also remark that although computing an egalitarian-optimal (possibly non-cardinal) allocation is well-known to be NP-hard [Kar72], if we are provided with such an allocation, we can find, in linear time, a cardinal allocation with an egalitarian social welfare guarantee corresponding to the egalitarian price of cardinality. This is simply achieved by letting each agent keep their $k$ most valued items from the starting egalitarian-optimal allocation.

4 Multiple Categories

We now extend our analysis to the setting where the items are partitioned into multiple categories. Recall that there are $h$ categories, where category $j\in[h]$ has $m_{j}$ items to be allocated and a cardinality constraint of $k_{j}$ . We also ensure that all items can be assigned, $\frac{m_{j}}{k_{j}}\leq n$ holds for each $j\in[h]$ . Without loss of generality, we order categories such that $\frac{k_{1}}{m_{1}}\leq\frac{k_{2}}{m_{2}}\leq\dots\leq\frac{k_{h}}{m_{h}}$ and break ties in favour of the category with a smaller number of items (i.e., if $\frac{k_{i}}{m_{1}}=\frac{k_{j}}{m_{j}}$ and $m_{i}<m_{j}$ , then set $i<j$ ).

4.1 Utilitarian Social Welfare

For utilitarian social welfare, we first consider the case of two agents. Before stating the main result, we establish a key reduction which restricts the space of instances to those with weakly higher $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$ ratio.

Lemma 6.

Given an instance $I$ with two agents and cardinality constraints $\kappa$ , there exists another instance $I^{\prime}$ which only differs from $I$ in the utility functions, where:

•
under the utilitarian-optimal allocation $\mathcal{A}^{\prime*}$ ,
- –
  
  both agents exceed the cardinality constraint in exactly one category each,
- –
  
  neither agent receives any utility from any category where they do not exceed the cardinality constraint,
•

and $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ holds.

Following this reduction, we are now ready to present the utilitarian price of cardinality for two agents, which is exact and tight for all $\kappa=(k_{1},\dots,k_{h})$ and $m_{1},\dots,m_{h}$ .

Theorem 3.

For two agents and $h\geq 2$ , the utilitarian price of cardinality is $\frac{2}{\frac{k_{1}}{m_{1}}+\frac{k_{2}}{m_{2}}}$ .

Proof.

By Lemma 6, it suffices to focus on the case where in $\mathcal{A}^{*}$ , agent $1$ (resp. agent $2$ ) exceeds the cardinality constraint of category $j_{1}$ (resp. $j_{2}$ ). Note that due to the ordering of our categories, it is ‘weakly better’ to consider categories $1$ and $2$ . Moreover in $\mathcal{A}^{*}$ , each agent $i$ only receives non-zero utility from $C_{j_{i}}$ . Note that we must have $j_{1}\neq j_{2}$ due to $\frac{m_{j}}{k_{j}}\leq 2$ for all $j$ .

We first prove the upper bound. Consider another (possibly non-normalized) instance $I^{\prime}$ that only differs from $I$ in utility functions. In $I^{\prime}$ , agent $i$ has utility function $u^{\prime}_{i}(g)=u_{i}(g)$ if $g\in A^{*}_{ij_{i}}$ and $u^{\prime}_{i}(g)=0$ otherwise. One can verify that the welfare of utilitarian-optimal allocation of $I$ is equal to that of $I^{\prime}$ , while the maximum welfare of cardinal allocations is weakly decreased in $I^{\prime}$ . Accordingly, we have $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ . We then convert $I^{\prime}$ into a normalized instance $I^{\prime\prime}$ by increasing agent $i$ ’s utility for $A^{*}_{ij_{i}}$ to $1$ in a way such that the ‘price of cardinality’ ratio weakly increases; this can be done by increasing the utility of items valued the most by both agents. Note that $I^{\prime\prime}$ is a normalized instance where in $\mathcal{A}^{*}$ , each agent $i$ receives utility $1$ from obtaining all of the items which they positively value.

Finally, we have

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{\text{OPT-USW}(I^{\prime\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime\prime})}\text{USW}(\mathcal{A})}$
		$\displaystyle\leq\frac{2}{\frac{k_{j_{1}}}{\|A^{}_{1j_{1}}\|}+\frac{k_{j_{2}}}{\|A^{}_{2j_{2}}\|}}$
		$\displaystyle\leq\frac{2}{\frac{k_{j_{1}}}{m_{j_{1}}}+\frac{k_{j_{2}}}{m_{j_{2}}}}\leq\frac{2}{\frac{k_{1}}{m_{1}}+\frac{k_{2}}{m_{2}}},$

concluding the proof of the upper bound.

For the lower bound, consider the instance $I$ where agent $1$ values each item in category $1$ at $\frac{1}{m_{1}}$ utility and agent $2$ values each item in category $2$ each at $\frac{1}{m_{2}}$ utility. Clearly, $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}=\frac{2}{\frac{k_{1}}{m_{1}}+\frac{k_{2}}{m_{2}}}$ for this instance. ∎

We give the utilitarian price of cardinality for general $n$ .

Theorem 4.

For general $n$ , the utilitarian price of cardinality is $\frac{m_{1}}{k_{1}}$ .

Proof.

We first prove the upper bound. Given an instance $I$ , let $\mathcal{A}^{*}$ be its utilitarian-optimal allocation. Then we have

		$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$
		$\displaystyle\leq\frac{\sum_{j\in[h]}\sum_{i\in S_{j}}u_{i}(A^{}_{ij})+\sum_{j\in[h]}\sum_{i\in N\setminus S_{j}}u_{i}(A^{}_{ij})}{\sum_{j\in[h]}\sum_{i\in S_{j}}\frac{k_{j}}{\|A^{}_{ij}\|}u_{i}(A^{}_{ij})+\sum_{j\in[h]}\sum_{i\in N\setminus S_{j}}u_{i}(A^{*}_{ij})}$
		$\displaystyle\leq\frac{\sum_{j\in[h]}\sum_{i\in S_{j}}u_{i}(A^{}_{ij})}{\sum_{j\in[h]}\sum_{i\in S_{j}}\frac{k_{j}}{\|A^{}_{ij}\|}u_{i}(A^{*}_{ij})}\leq\frac{m_{1}}{k_{1}},$

where the last inequality transition is because for every $j\in[h]$ , $\frac{k_{j}}{|A^{*}_{ij}|}\leq\frac{k_{j}}{m_{j}}\leq\frac{k_{1}}{m_{1}}$ .

For the lower bound, consider an instance $I$ with $h=n$ categories, and where each category $j\in[h]$ has the same cardinality constraint of $k_{j}=k$ and same number of items $m_{j}=q$ items, where $q$ is divisible by $k$ . Suppose that in this instance, for each agent $i$ , $u_{i}(g)=\frac{1}{q}$ if $g\in C_{i}$ , and $u_{i}(g)=0$ otherwise. Clearly, we have $\text{OPT-USW}(I)=n$ . In the utilitarian-optimal cardinal allocation $\mathcal{A}^{k}$ , each agent $i$ receives a utility of $\frac{k}{q}$ . Thus, we have $\text{USW}(\mathcal{A}^{k})=\frac{nk}{q}$ , and therefore, the utilitarian price of cardinality is at least $\frac{\text{OPT-USW}(I)}{\text{USW}(\mathcal{A}^{k})}=\frac{q}{k}=\frac{m_{1}}{k_{1}},$ completing the proof. ∎

This result is roughly tight in the sense that the utilitarian price of cardinality is at most $\frac{m_{1}}{k_{1}}$ for any instance with cardinality constraints $\kappa=(k_{1},\dots,k_{j})$ , and is precisely $\frac{m_{1}}{k_{1}}$ for any instance where there are at least $n$ categories, and $\frac{k_{1}}{m_{1}}=\frac{k_{2}}{m_{2}}=\dots=\frac{k_{n}}{m_{n}}$ .

Finally, we mention a result on computing utilitarian-optimal cardinal allocations, similar to Proposition 1.

Proposition 2.

Given a multiple-category instance $I$ and cardinality constraints $\kappa$ , the utilitarian-optimal cardinal allocation can be found in polynomial time, and has a utilitarian social welfare of at least $\frac{k_{1}}{m_{1}}\cdot\text{OPT-USW}(I)$ .

Proof.

The proof is almost identical to the proof of Proposition 1, but we instead construct a separate complete bipartite graph for each category $j\in[h]$ , and compute a maximum weight bipartite matching for each of these graphs. The runtime remains in polynomial time, and the utilitarian social welfare guarantee follows immediately from Theorem 1. ∎

4.2 Egalitarian Social Welfare

Finally, for egalitarian social welfare, we present bounds for the price of cardinality which are exact and tight for any $n$ , $\kappa=(k_{1},\dots,k_{h})$ , and $m_{1},\dots,m_{h}$ .

Theorem 5.

If $n\leq\sum_{j=2}^{h}m_{j}+1$ , then the egalitarian price of cardinality is $\frac{m_{1}}{k_{1}}$ . If $n>\sum_{j=2}^{h}m_{j}+1$ , then the egalitarian price of cardinality is

\max_{j\in[h]}\left\{\frac{m_{j}-\max\{n-1-\sum_{t\neq j}m_{t},0\}}{k_{j}}\right\}.

Proof.

We begin with the upper bound and fix instance $I$ . Let $\mathcal{A}^{*}=(A^{*}_{1},\ldots,A^{*}_{n})$ be the egalitarian-optimal allocation for $I$ and let $A^{*}_{ij}$ be the bundle agent $i$ receives from category $j$ . If $\text{ESW}(\mathcal{A}^{*})=0$ , then the statement trivially holds. We further assume $\text{ESW}(\mathcal{A}^{*})>0$ .

We first show a general upper bound of $\frac{m_{1}}{k_{1}}$ . Note that in the egalitarian-optimal cardinal allocation, every agent $i$ can keep their $k_{j}$ most valued items and receives a utility of at least $\sum_{j\in[h]}\frac{k_{j}}{m_{j}}u_{i}(A^{*}_{ij})\geq\frac{k_{1}}{m_{1}}u_{i}(A^{*}_{i})\geq\frac{k_{1}}{m_{1}}\text{ESW}(\mathcal{A}^{*})$ . This bound holds for any $n$ and $m_{j}$ , proving the first part of the theorem statement.

We then strengthen the bound for the case where $n>\sum_{j=2}^{h}m_{j}+1$ . Define, for each $j\in[h]$ , $c_{j}:=\max\{n-1-\sum_{t\neq j}m_{t},0\}$ . By the definition of $c_{j}$ , we claim that for any $i\in[n]$ and $j\in[h]$ , $|A^{*}_{ij}|\leq m_{j}-c_{j}$ holds; otherwise, there must be one agent receiving no item in $\mathcal{A}^{*}$ , contradicting $\text{ESW}(\mathcal{A}^{*})>0$ . Then in the egalitarian-optimal cardinal allocation, each agent $i$ can obtain a utility of at least

	$\displaystyle\sum_{j\in[h]}\frac{k_{j}}{\|A^{}_{ij}\|}u_{i}(A^{}_{ij})$	$\displaystyle\geq\sum_{j\in[h]}\frac{k_{j}}{m_{j}-c_{j}}u_{i}(A^{*}_{ij})$
		$\displaystyle\geq\min\limits_{j\in[h]}\frac{k_{j}}{m_{j}-c_{j}}\sum_{j\in[h]}u_{i}(A^{*}_{ij})$
		$\displaystyle=\min\limits_{j\in[h]}\frac{k_{j}}{m_{j}-c_{j}}u_{i}(A^{*}_{i}).$

Therefore, the price of cardinality in this case is at most $\max_{j\in[h]}\frac{m_{j}-c_{j}}{k_{j}}$ , equal to the expression in the theorem statement.

For the lower bound, we first consider the case where $n\leq\sum_{j=2}^{h}m_{j}+1$ and show that the bound of $\frac{m_{1}}{k_{1}}$ is tight. Let agent 1 value each item of $C_{1}$ at $\frac{1}{m_{1}}$ utility each and let agents $2,\ldots,n$ only value one unique item each at 1 utility from $C_{2},\ldots,C_{h}$ . In the egalitarian-optimal allocation, each agent receives a utility of 1, leading to an optimal egalitarian welfare of 1. However, for cardinal allocations, the utility of agent 1 is at most $\frac{k_{1}}{m_{1}}$ and the lower bound of $\frac{m_{1}}{k_{1}}$ follows.

For the case where $n>\sum_{j=2}^{h}m_{j}+1$ , we first denote the category that maximizes $\max_{j\in[h]}\frac{m_{j}-c_{j}}{k_{j}}$ as $j^{*}$ ; recall that $c_{j}=\max\{n-1-\sum_{t\neq j}m_{t},0\}$ . In the subcase where $c_{j^{*}}=0$ , we let agents $1,\ldots,n-1$ value one unique item each at $1$ utility in any category $j\neq j^{*}$ and agent $n$ values each item in $C_{j^{*}}$ evenly, achieving at most $\frac{k_{j^{*}}}{m_{j^{*}}}$ utility in a cardinal allocation. Since the optimal egalitarian welfare is $1$ , the respective lower bound follows. As for the subcase where $c_{j^{*}}>0$ (this indeed implies $j^{*}=1$ ), consider the instance $I$ where $\sum_{j\neq j^{*}}m_{j}$ of the agents value one unique item each at $1$ utility in some $C_{j}$ with $j\neq j^{*}$ . Here, $n-1-\sum_{j\neq j^{*}}m_{j}$ of the remaining agents value one unique item each at $1$ utility in $C_{j^{*}}$ , and the last agent values all $m_{j^{*}}-c_{j^{*}}$ remaining items in $C_{j^{*}}$ evenly. We have $\text{OPT-ESW}(I)=1$ , and note that the last agent can receive a utility of at most $\frac{k_{j^{*}}}{m_{j^{*}}-c_{j^{*}}}$ in any cardinal allocation, achieving the lower bound in the statement. ∎

Similar to the single category scenario, if we are given an egalitarian-optimal allocation, we can construct a cardinal allocation with an egalitarian welfare guarantee corresponding to the price of cardinality by letting each agent keep their $k_{j}$ most valued items in each category $j\in[h]$ .

5 Discussion

In this work, we introduced the utilitarian and egalitarian prices of cardinality, which quantify the worst-case multiplicative loss of social welfare when cardinality constraints are imposed on the allocation. For both the single- and multi-category cases, we present tight bounds on the prices of cardinality, expressed as an exact (rather than asymptotic) function of the instance and cardinality parameters. Our results enable decision makers to make a clear, well-informed choice of cardinality constraint with respect to the level of balancedness and the potential loss of social welfare.

Our parametrized approach to the price of cardinality can be applied to other parametrized notions of fairness such as envy-freeness up to $k$ items (EF- $k$ ) or $\alpha$ -maximin share ( $\alpha$ -MMS), providing similar insights to decision makers regarding the tradeoff between the level of fairness and the potential loss of social welfare.

An immediate open question is to find a more precise utilitarian price of cardinality in the case of multiple categories and $n\geq 3$ agents. Ideally, we would like the price to be tight for all possible values of $n$ , $\{m_{j}\}_{j\in[h]}$ , and $(k_{j})_{j\in[h]}$ , like our egalitarian prices of cardinality. To pursue such a precise price, one approach is to characterize the worst case scenario. Unfortunately, our reduction (in Lemma 6) for the case of two agents can not be immediately extended to the case where $n\geq 3$ . Furthermore, part of the complete proof of Lemma 5 relies on knowing the exact form of a parameter $s$ , which we cannot find in the multi-category case due to the multivariate property of the problem. However, we believe that the greedy procedure in the proof of Lemma 4 could be helpful for identifying the worst case structure.

Another possible direction is finding the price of cardinality for the “dual” problem where each agent must receive at least $k$ items. However, this type of constraint violates the hereditary property of matroids, and is generally not studied in other related work.

Acknowledgements

The authors would like to thank Siddarth Barman, Xiaohui Bei, and the anonymous AAAI reviewers for their helpful comments. This work is funded by HKSAR RGC under Grant No. PolyU 15224823 and the Guangdong Basic and Applied Basic Research Foundation under Grant No. 2024A1515011524.

References

[AAB⁺23] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell., 322:103965, 2023.
[BB18] Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In IJCAI, pages 91–97. ijcai.org, 2018.
[BBS20] Siddharth Barman, Umang Bhaskar, and Nisarg Shah. Optimal bounds on the price of fairness for indivisible goods. In WINE, volume 12495 of Lecture Notes in Computer Science, pages 356–369. Springer, 2020.
[BCE⁺17] Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In IJCAI, pages 135–141. ijcai.org, 2017.
[BLLS24] Xiaohui Bei, Alexander Lam, Xinhang Lu, and Warut Suksompong. Welfare loss in connected resource allocation. In IJCAI, pages 2660–2668. ijcai.org, 2024.
[BLMS21] Xiaohui Bei, Xinhang Lu, Pasin Manurangsi, and Warut Suksompong. The price of fairness for indivisible goods. Theory Comput. Syst., 65(7):1069–1093, 2021.
[CKKK12] Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos, and Maria Kyropoulou. The efficiency of fair division. Theory Comput. Syst., 50(4):589–610, 2012.
[ESHS22] Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. Mind the gap: Cake cutting with separation. Artif. Intell., 313:103783, 2022.
[GS58] George Gamow and Marvin Stern. Puzzle-Math. Viking press, 1958.
[HH22] Halvard Hummel and Magnus Lie Hetland. Guaranteeing half-maximin shares under cardinality constraints. In AAMAS, pages 1633–1635. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022.
[Kar72] Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.
[Kuh55] H. W. Kuhn. The hungarian method for the assignment problem. Nav. Res. Logist. Q., 2(1-2):83–97, 1955.
[LLL⁺24] Zihao Li, Shengxin Liu, Xinhang Lu, Biaoshuai Tao, and Yichen Tao. A complete landscape for the price of envy-freeness. In AAMAS, pages 1183–1191. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2024.
[LLW22] Bo Li, Yingkai Li, and Xiaowei Wu. Almost (weighted) proportional allocations for indivisible chores. In WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 122–131. ACM, 2022.
[SCD23a] Ankang Sun, Bo Chen, and Xuan Vinh Doan. Equitability and welfare maximization for allocating indivisible items. Auton. Agents Multi Agent Syst., 37(1):8, 2023.
[SCD23b] Ankang Sun, Bo Chen, and Xuan Vinh Doan. Fairness criteria for allocating indivisible chores: connections and efficiencies. Auton. Agents Multi Agent Syst., 37(2):39, 2023.
[SHNHA17] Erel Segal-Halevi, Shmuel Nitzan, Avinatan Hassidim, and Yonatan Aumann. Fair and square: Cake-cutting in two dimensions. J. Math. Econ., 70:1–28, 2017.
[SL23] Ankang Sun and Bo Li. On the price of fairness in the connected discrete cake cutting problem. In ECAI, volume 372, pages 2242–2249. IOS Press, 2023.
[SL24] Ankang Sun and Bo Li. Allocating contiguous blocks of indivisible chores fairly: Revisited. In AAMAS, pages 1800–1808. International Foundation for Autonomous Agents and Multiagent Systems / ACM, 2024.
[Ste48] Hugo Steinhaus. The problem of fair division. Econometrica, 16:101–104, 1948.
[Suk21] Warut Suksompong. Constraints in fair division. SIGecom Exch., 19(2):46–61, 2021.
[Var74] Hal R. Varian. Equity, envy and efficiency. J. Econ. Theory, 9:63–91, 1974.
[Wal20] Toby Walsh. Fair division: The computer scientist’s perspective. In IJCAI, pages 4966–4972. ijcai.org, 2020.
[WLG21] Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare is almost envy-free. In IJCAI, pages 465–471. ijcai.org, 2021.

Appendix A Omitted Proofs for Section 3

A.1 Proof of Lemma 2

By applying basic calculus (which will also be shown in the proof of Lemma 3), we find that $s=-1+\sqrt{1+\frac{m-1}{k}}$ is the unique global maximum of the price of cardinality lower bound of $\frac{1+s}{1+\frac{ks^{2}}{m-1}}$ (under the domain of $s>0$ ). As a result, if $m$ and $k$ are such that $s$ is not integral, we have another instance which shows that the utilitarian price of cardinality is at least $\frac{1}{2}(1+\sqrt{1+\frac{m-1}{k}})-1$ .

We now fix $m,n,k\in\mathbb{N}^{+}$ satisfying $n\geq\frac{m}{k}$ and $m-2\geq k$ ; note that if $m-1=k$ , the utilitarian-optimal allocation is cardinal as the utilities are normalized. Let $s=-1+\sqrt{1+\frac{m-1}{k}}$ and denote $t\coloneqq\max\{\lfloor s\rfloor,1\}$ . Note that for any $n\geq 2$ , we have $t\leq n-1$ . Now consider an instance $I$ with $n$ agents and $m$ items, where the agents’ utilities are described as follows;

•

for $i=1,\ldots,t$ , if $j=(i-1)\lfloor\frac{m-1}{t}\rfloor+1,\ldots,i\lfloor\frac{m-1}{t}\rfloor$ , $u_{i}(g_{j})=\frac{1}{\lfloor\frac{m-1}{t}\rfloor}$ ; otherwise, $u_{i}(g)=0$ ;
•

for $i\geq t+1$ , $u_{i}(g_{m})=1$ and $u_{i}(g)=0$ for every $g\neq g_{m}$ .

Note that for agent $t$ , each item she values with non-zero utility has an index of $t\lfloor\frac{m-1}{t}\rfloor<m$ and thus the above instance is well-defined. One can verify that $\text{OPT-USW}(I)=1+t$ . Moreover, in the utilitarian-optimal allocation, we know that every agent $i\leq t$ exceeds the cardinality constraint as:

•

if $t=\lfloor s\rfloor$ , we have $\frac{m-1}{t}>\frac{m-1}{s}>k$ , and since $k\in\mathbb{N}^{+}$ , we have $\lfloor\frac{m-1}{t}\rfloor>k$ ,
•

if $t=1$ , agent 1 receives $m-1>k$ items.

Accordingly, we have $\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})=1+\frac{kt}{\lfloor\frac{m-1}{t}\rfloor}$ , showing that the utilitarian price of cardinality is at least $\frac{1+t}{1+\frac{kt}{\lfloor\frac{m-1}{t}\rfloor}}$ . Recall that $\frac{1}{2}(1+\sqrt{1+\frac{m-1}{k}})$ is equal to $\frac{1+s}{1+\frac{ks^{2}}{m-1}}$ , and therefore to prove the theorem statement, it suffices to show that

\frac{1+s}{1+\frac{ks^{2}}{m-1}}-\frac{1+t}{1+\frac{kt}{\lfloor\frac{m-1}{t}\rfloor}}\leq 1,

or equivalently,

s-t+\frac{kts}{\lfloor\frac{m-1}{t}\rfloor}-\frac{kts^{2}}{m-1}\leq 1+\frac{2ks^{2}}{m-1}+\frac{k^{2}s^{2}t}{(m-1)\lfloor\frac{m-1}{t}\rfloor}.

Since $s-t\leq 1$ , it further suffices to show that

\frac{kts}{\lfloor\frac{m-1}{t}\rfloor}-\frac{kts^{2}}{m-1}\leq\frac{2ks^{2}}{m-1}+\frac{k^{2}s^{2}t}{(m-1)\lfloor\frac{m-1}{t}\rfloor},

or equivalently,

\left(\frac{2s}{t}+s\right)\lfloor\frac{m-1}{t}\rfloor+ks\geq m-1.

We have

	$\displaystyle\left(\frac{2s}{t}+s\right)\lfloor\frac{m-1}{t}\rfloor+ks$	$\displaystyle\geq(2+s)\lfloor\frac{m-1}{t}\rfloor+ks$
		$\displaystyle>s\left(\frac{m-1}{t}-1\right)+ks$
		$\displaystyle\geq\frac{s}{t}m-1+(k-1)s$
		$\displaystyle\geq m-1,$

proving that the utilitarian price of cardinality is at least $\frac{1}{2}(1+\sqrt{1+\frac{m-1}{k}})-1$ .

A.2 Proof of Lemma 3

Firstly, we know that

\text{OPT-USW}(I)=\sum_{i\in N\setminus S}u_{i}(A^{*}_{i})+\sum_{i\in S}u_{i}(A^{*}_{i})

and

\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})\geq\sum_{i\in N\setminus S}u_{i}(A^{*}_{i})+k\sum_{i\in S}\frac{u_{i}(A^{*}_{i})}{|A^{*}_{i}|}.

Note that letting each agent $i\in S$ discard their $|A^{*}_{i}|-k$ least valued items yields in a (cardinal) partial allocation with the desired utilitarian welfare guarantee. We therefore have

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{\sum_{i\in N\setminus S}u_{i}(A^{}_{i})+\sum_{i\in S}u_{i}(A^{}_{i})}{\sum_{i\in N\setminus S}u_{i}(A^{}_{i})+k\sum_{i\in S}\frac{u_{i}(A^{}_{i})}{\|A^{*}_{i}\|}}$
		$\displaystyle\leq\frac{1+\sum_{i\in S}u_{i}(A^{}_{i})}{1+k\sum_{i\in S}\frac{u_{i}(A^{}_{i})}{\|A^{*}_{i}\|}},$

where the last inequality is due to $\frac{a+b}{a+c}\leq\frac{b}{c}$ for $a,b,c>0$ . This proves the first inequality of the lemma statement.

We next show the second inequality through derivatives. Consider the multivariable function $F(u_{1}(A^{*}_{1}),\ldots,u_{|S|}A^{*}_{|S|})=\frac{1+\sum_{i\in S}u_{i}(A^{*}_{i})}{1+k\sum_{i\in S}\frac{u_{i}(A^{*}_{i})}{|A^{*}_{i}|}}$ with domain $0\leq u_{i}(A^{*}_{i})\leq 1$ for all $i\in S$ . For each $i^{\prime}\in S$ , the derivative $\frac{\partial F}{\partial u_{i^{\prime}}(A^{*}_{i^{\prime}})}$ of the function $F$ with respect to $u_{i^{\prime}}(A^{*}_{i^{\prime}})$ is

\frac{\frac{|A^{*}_{i^{\prime}}|-k}{|A^{*}_{i^{\prime}}|}+k\left(\sum_{i\in S\setminus\{i^{\prime}\}}u_{i}(A^{*}_{i})\left(\frac{1}{|A^{*}_{i}|}-\frac{1}{|A^{*}_{i^{\prime}}|}\right)\right)}{\left(1+k\sum_{i\in S}\frac{u_{i}(A^{*}_{i})}{|A^{*}_{i}|}\right)^{2}}.

The numerator of the derivative is independent of $u_{i^{\prime}}(A^{*}_{i^{\prime}})$ , so the expression has no stationary points and is either monotonic increasing, decreasing or constant. Therefore, $F$ is maximized when every $u_{i}(A^{*}_{i})$ is either 1 or 0; note that for any $i\in S$ , $u_{i}(A^{*}_{i})\in[0,1]$ . Also note that for a specific $i^{\prime}\in S$ , setting $u_{i^{\prime}}(A^{*}_{i^{\prime}})=0$ may violate the property of $i^{\prime}\in S$ . However, as we are only concerned with establishing an upper bound for $F$ , letting $u_{i^{\prime}}(A^{*}_{i^{\prime}})=0$ for some $i^{\prime}$ does not result in any violation.

Denote by $S^{\prime}\subseteq S$ the set of agents who have utility $1$ in the solution maximizing $F$ . Observe that for there exists $i\in S$ such that the derivative of $F$ with respect to some $u_{i}(A^{*}_{i})$ is positive (e.g. the agent whose bundle under $\mathcal{A}^{*}$ has the most items). Therefore $S^{\prime}\neq\emptyset$ , so the following holds:

F=\frac{1+\sum_{i\in S}u_{i}(A^{*}_{i})}{1+k\sum_{i\in S}\frac{u_{i}(A^{*}_{i})}{|A^{*}_{i}|}}\leq\frac{1+\sum_{i\in S^{\prime}}1}{1+k\sum_{i\in S^{\prime}}\frac{1}{A^{*}_{i}}}\leq\frac{1+|S^{\prime}|}{1+\frac{k|S^{\prime}|^{2}}{m-1}},

where the first inequality is due to the construction of $S^{\prime}$ . The second inequality is due to the arithmetic mean-harmonic mean (AM-HM) inequality and the fact that $\sum_{i\in S}|A^{*}_{i}|\leq m-1$ (the agents of $N\setminus S$ must receive at least one item in $\mathcal{A}^{*}$ so that the sum of their utilities can be 1). Now consider the function $G(|S^{\prime}|)=\frac{1+|S^{\prime}|}{1+\frac{k|S^{\prime}|^{2}}{m-1}}$ with domain $0\leq|S^{\prime}|\leq n$ . Its derivative with respect to $|S|$ is

\frac{\partial G}{\partial|S^{\prime}|}=\frac{1}{\left(1+\frac{k|S^{\prime}|^{2}}{m-1}\right)^{2}}\cdot\left(1-\frac{k|S^{\prime}|(2+|S^{\prime}|)}{m-1}\right).

This derivative is non-negative for $-1-\sqrt{1+\frac{m-1}{k}}\leq|S^{\prime}|\leq-1+\sqrt{1+\frac{m-1}{k}}$ . Since $m\leq kn$ always holds, we have $-1+\sqrt{1+\frac{m-1}{k}}\leq\sqrt{n}<n$ for all $n\geq 2$ . Hence, $G$ achieves its maximum value when $|S^{\prime}|=-1+\sqrt{1+\frac{m-1}{k}}$ . Therefore, by setting $s=-1+\sqrt{1+\frac{m-1}{k}}$ , we have

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\max_{0\leq u_{i}(A^{*}_{i})\leq 1}F$
		$\displaystyle\leq\max_{0\leq\|S^{\prime}\|\leq n}G$
		$\displaystyle\leq\frac{1+s}{1+\frac{ks^{2}}{m-1}},$

completing the proof.

A.3 Proof of Lemma 4

Specifically, we will show that there exists a cardinal allocation $\mathcal{A}$ such that

	$\displaystyle\text{USW}(\mathcal{A})$	$\displaystyle\geq\sum_{i\in R\cup T}u_{i}(A^{}_{i})+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}u_{i}(A^{*}_{i})$
		$\displaystyle\quad+\sum_{i\in S}\frac{\|A^{}_{i}\|-k}{\|A^{}_{i}\|}u_{i^{\dagger}}(A^{*}_{i}),$

which suffices because

\sum_{i\in R\cup T}u_{i}(A^{*}_{i})=1-\sum_{i\in S}u_{i^{\dagger}}(A^{*}_{i}).

(Recall that $I$ is preprocessed.)

Fix an agent $t\in R$ . For each $i\in S$ , denote $L_{i}\subseteq A^{*}_{i}$ as the set of $|A^{*}_{i}|-k$ items which minimizes the loss of utilitarian social welfare when they are reallocated from $i$ to agent $t$ . Accordingly, for each $i\in S$ , we have

\frac{\sum_{g\in L_{i}}(u_{i}(g)-u_{t}(g))}{|A^{*}_{i}|-k}\leq\frac{u_{i}(A^{*}_{i})-u_{t}(A^{*}_{i})}{|A^{*}_{i}|},

which is equivalent to

\sum_{g\in L_{i}}(u_{i}(g)-u_{t}(g))\leq\frac{|A^{*}_{i}|-k}{|A^{*}_{i}|}(u_{i}(A^{*}_{i})-u_{t}(A^{*}_{i})).

Hence, the total loss of utilitarian social welfare from reallocating $L_{i}$ from every $i\in S$ to agent $t$ is at most $\sum_{i\in S}\frac{|A^{*}_{i}|-k}{|A^{*}_{i}|}(u_{i}(A^{*}_{i})-u_{t}(A^{*}_{i}))$ , and therefore, the utilitarian social welfare of the resulting allocation (which may not be cardinal) is at least

\sum_{i\in R\cup T}u_{i}(A^{*}_{i})+\sum_{i\in S}\frac{k}{|A^{*}_{i}|}u_{i}(A^{*}_{i})+\sum_{i\in S}\frac{|A^{*}_{i}|-k}{|A^{*}_{i}|}u_{t}(A^{*}_{i}).

As letting one agent $t\in R$ receive all excess items from $\{A^{*}_{i}\}_{i\in S}$ may not yield a cardinal allocation, we then consider the cardinal allocation achieved by reassigning items from $\{A^{*}_{i}\}_{i\in S}$ to agents $R$ via a greedy procedure described as follows.

•

Step 1: Set $\mathcal{B}\leftarrow\mathcal{A}^{*}$ as the initial allocation, $P\leftarrow S$ as the initial set of unsatisfied agents, and $Q\leftarrow R$ as the initial set of active agents;
•

Step 2: If there are no unsatisfied agents, then terminate and output the underlying allocation $\mathcal{B}$ (this will be $\mathcal{A}^{k}$ ). Otherwise, find the item $e^{*}\in\bigcup_{i\in P}B_{i}$ and an active agent $i^{*}\in Q$ such that reassigning $e^{*}$ to agent $i^{*}$ causes the minimum utilitarian social welfare loss among all single-item reassignments from items of unsatisfied agents to active agents. Reassign $e^{*}$ to agent $i^{*}$ , and update $\mathcal{B}$ accordingly.
•

Step 3: Update $P$ and $Q$ , and return to Step 2.

Without loss of generality, let agent $n$ be the chosen active agent at the last reassignment step. Note that $n\in R$ must hold. For any $j\in S$ , we define the loss of utility from reassigning item $e\in A^{*}_{j}$ to agent $n$ as $l^{n}_{j}(e)\coloneqq u_{j}(e)-u_{n}(e)$ , and moreover, let $L^{n}_{j}$ be the set of the $|A^{*}_{j}|-k$ items of $A^{*}_{j}$ with the lowest $l^{n}_{j}(e)$ . By this construction, $\sum_{j\in S}\sum_{g\in L^{n}_{j}}l_{j}^{n}(g)$ is the welfare loss of reassigning $\bigcup_{j\in S}\bigcup_{g\in L^{n}_{j}}g$ to agent $n$ . Based on the above arguments and the fact that $n\in R$ , we have $\sum_{j\in S}\sum_{g\in L^{n}_{j}}l_{j}^{n}(g)\leq\sum_{i\in S}\frac{|A^{*}_{i}|-k}{|A^{*}_{i}|}(u_{i}(A^{*}_{i})-u_{n}(A^{*}_{i}))$ . Our last step is to show that $\text{USW}(\mathcal{A}^{*})-\text{USW}(\mathcal{A}^{k})\leq\sum_{j\in S}\sum_{g\in L^{n}_{j}}l_{j}^{n}(g)$ .

Consider an arbitrary agent $j\in S$ . According to the reassignment process, $|A^{*}_{j}|-k$ items of $A^{*}_{j}$ are not allocated to $j$ in $\mathcal{A}^{k}$ . Suppose $0<\delta_{1}\leq\delta_{2}\leq\cdots\leq\delta_{|A^{*}_{j}|-k}$ , where $\delta_{i}$ refers to the $i$ -th lowest utility loss in the aforementioned reassignment of $|A^{*}_{j}|-k$ items. Recall that $L^{n}_{j}$ is the set of the $|A^{*}_{j}|-k$ items of $A^{*}_{j}$ with the least $l_{j}^{n}(e)$ . Let $L^{n}_{j}=\{g_{1},g_{2},\ldots,g_{|A^{*}_{j}|-k}\}$ and $l^{n}(g_{t})\leq l^{n}(g_{t+1})$ for all $t\leq|A^{*}_{j}|-k$ .

Claim 1.

For any $1\leq t\leq|A^{*}_{j}|-k$ , it holds that $\delta_{t}\leq l_{j}^{n}(g_{t})$ .

Proof of Claim 1.

For a contradiction, let $t^{\prime}$ be the smallest index such that $\delta_{t^{\prime}}>l^{n}(g_{t^{\prime}})$ . Since agent $n$ is the chosen active agent at the last reassignment step, they were active when the reassignment corresponding to $\delta_{t^{\prime}}$ happened. For ease of presentation, we let round $s$ be the moment when the reassignment corresponding to welfare loss $\delta_{t^{\prime}}$ happened, and accordingly, agent $j$ is unsatisfied at the start of round $s$ . By $\delta_{1}\leq\delta_{2}\leq\cdots\leq\delta_{t^{\prime}}$ and the reassignment rule, for any $t<t^{\prime}$ , the reassignment corresponding to welfare loss $\delta_{t}$ happened before round $s$ . There are two possible cases depending on whether item $g_{t^{\prime}}\in L_{j}^{n}$ is still in agent $j$ ’s bundle at the start of round $s$ . If so, then reassigning $g_{t^{\prime}}$ to agent $n$ results in a welfare loss $l^{n}(g_{t^{\prime}})<\delta_{t^{\prime}}$ , contradicting Step 2.

We now consider the remaining case where item $g_{t^{\prime}}$ is not in the bundle of agent $j$ at the start of round $s$ . Since $g_{t^{\prime}}\in A^{*}_{j}$ , then the reassignment of $g_{t^{\prime}}$ in the process results in a welfare loss of $\delta_{t^{\prime\prime}}$ where $t^{\prime\prime}<t^{\prime}$ , and accordingly, the reassignment of $g_{t^{\prime}}$ happened before round $s$ . Note that at the end of round $s-1$ , at most $t^{\prime}-1$ items were reassigned from bundle $A^{*}_{j}$ . Since $g_{t^{\prime}}$ was reassigned before round $s$ , then at least one item from $\{g_{1},g_{2},\ldots,g_{t^{\prime}-1}\}$ is in the bundle of agent $j$ at the start of round $s$ . Reassigning any item from $\{g_{1},g_{2},\ldots,g_{t^{\prime}-1}\}$ to agent $n$ induces a utility loss at most $l^{n}(g_{t^{\prime}})$ ; note that $l^{n}(g_{r})\leq l^{n}(g_{r+1})$ for all $r\leq|A^{*}_{j}|-k$ . Thus, at the start of round $s$ , agent $j$ is unsatisfied and their bundle contains some item from $\{g_{1},g_{2},\ldots,g_{t^{\prime}-1}\}$ . Therefore, at the start of round $s$ , there exists some item $g$ in the bundle of some agent $j$ (an unsatisfied agent), and some agent $n$ (an active agent), such that reassigning $g$ to agent $n$ causes welfare loss at most $l^{n}(g_{t^{\prime}})<\delta_{t^{\prime}}$ , a contradiction. ∎

The above claim implies that in the greedy reassignment procedure, for any $j\in S$ , the welfare loss of reassigning items in $A^{*}_{j}$ is at most $\sum_{g\in L^{n}_{j}}l_{j}^{n}(g)$ . Then, by summing up over all $j\in S$ , we have

	$\displaystyle\text{USW}(\mathcal{A}^{*})-\text{USW}(\mathcal{A}^{k})$	$\displaystyle\leq\sum_{j\in S}\sum_{g\in L^{n}_{j}}l_{j}^{n}(g)$
		$\displaystyle\leq\sum_{i\in S}\frac{\|A^{}_{i}\|-k}{\|A^{}_{i}\|}(u_{i}(A^{}_{i})-u_{n}(A^{}_{i})).$

Therefore, our procedure outputs a cardinal allocation $\mathcal{A}^{k}$ with utilitarian welfare

	$\displaystyle\text{USW}(\mathcal{A}^{k})$	$\displaystyle\geq\sum_{i\in R\cup T}u_{i}(A^{}_{i})+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}u_{i}(A^{*}_{i})$
		$\displaystyle\quad+\sum_{i\in S}\frac{\|A^{}_{i}\|-k}{\|A^{}_{i}\|}u_{n}(A^{*}_{i}),$

where $n\in R$ .

A.4 Proof of Lemma 5 (Cont.)

Case 2: $\sum_{i\in S}|A^{*}_{i}|=m$ . In the remaining case where only agents in $S$ are allocated items under $\mathcal{A}^{*}$ , we have

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{\sum_{i\in S}u_{i}(A^{}_{i})}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{}_{i}))}$
		$\displaystyle=\frac{1+\sum_{i\in S}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{}_{i}))}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{*}_{i}))}$
		$\displaystyle=\frac{1+\sum_{i\in S}v_{i}(A^{}_{i})}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}v_{i}(A^{*}_{i})},$

where $v_{i}(A^{*}_{i})=u_{i}(A^{*}_{i})-u_{i^{\dagger}}(A^{*}_{i})$ for all $i\in S$ . Similar to the proof of Lemma 3, we present the upper bound of the last expression through derivatives. Define $F(v_{1}(A^{*}_{1}),\ldots,v_{|S|}(A^{*}_{|S|}))=\frac{1+\sum_{i\in S}v_{i}(A^{*}_{i})}{1+\sum_{i\in S}\frac{k}{|A^{*}_{i}|}v_{i}(A^{*}_{i})}$ with domain $v_{i}(A^{*}_{i})\in[0,1]$ for all $i$ and $\sum_{i\in S}v_{i}(A^{*}_{i})\leq|S|-1$ .

Now for any $i^{\prime}\in S$ , the derivative of $F$ with respect to $v_{i^{\prime}}(A^{*}_{i^{\prime}})$ is

\frac{\partial F}{\partial v_{i^{\prime}}(A^{*}_{i^{\prime}})}=\frac{{1-\frac{k}{|A^{*}_{i^{\prime}}|}+k\sum_{i\in S}v_{i}(A^{*}_{i})\left(\frac{1}{|A^{*}_{i}|}-\frac{1}{|A^{*}_{i^{\prime}}|}\right)}}{{(1+\sum_{i\in S}\frac{k}{|A^{*}_{i}|}v_{i}(A^{*}_{i}))^{2}}}.

Again, as in the proof of Lemma 3, the numerator is independent of $v_{i^{\prime}}(A^{*}_{i^{\prime}})$ and therefore the derivative is either negative, positive, or zero. Hence, $F$ is maximized when each $v_{i}(A^{*}_{i})$ is either $0$ or is as large as possible, under the constraints of $\sum_{i\in S}v_{i}(A^{*}_{i})\leq|S|-1$ and $u_{i}(A^{*}_{i})\leq 1$ . Let $E\subseteq S$ denote the set of indices such that $v_{i}(A^{*}_{i})=0$ in the solution maximizing $F$ . We split the proof into three further subcases based on whether or not $E=\emptyset$ , and if $E=\emptyset$ , whether or not each bundle of items belonging to the agents of $S$ under $\mathcal{A}^{*}$ has the same number of items.

If $E$ is empty and for every $i,j\in S$ , $|A^{*}_{i}|=|A^{*}_{j}|=\frac{m}{|S|}$ , then we have

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\max\limits_{\begin{subarray}{c}0\leq v_{i}(A^{}_{i})\leq 1\\ \sum_{i=1}^{\|S\|}v_{i}(A^{}_{i})\leq\|S\|-1\end{subarray}}F(\cdot)$
		$\displaystyle\leq\frac{\|S\|}{1+k\frac{\|S\|}{m}(\|S\|-1)}$
		$\displaystyle\leq\frac{\sqrt{\frac{m}{k}}}{2-\sqrt{\frac{k}{m}}},$

where the second inequality is a result of $|A^{*}_{i}|=|A^{*}_{j}|$ for all $i,j\in S$ , as well as the requirement that $\sum_{i\in S}v_{i}(A^{*}_{i})=|S|-1$ in order to maximize $F$ . For the third inequality, some basic calculus shows that the expression is maximized when $|S|=\sqrt{\frac{m}{k}}$ . It remains to show that for any $m>k\geq 1$ , the following holds:

\frac{\sqrt{\frac{m}{k}}}{2-\sqrt{\frac{k}{m}}}<\frac{1}{2}\left(\sqrt{1+\frac{m-1}{k}}+1\right).

Setting $r=\frac{m}{k}$ , we have

	$\displaystyle\frac{1}{2}\Biggl{(}\sqrt{1+\frac{m-1}{k}}$	$\displaystyle+1\Biggr{)}-\frac{\sqrt{\frac{m}{k}}}{2-\sqrt{\frac{k}{m}}}$
		$\displaystyle=\frac{1}{2}\left(\sqrt{1+r-\frac{1}{k}}+1\right)-\frac{\sqrt{r}}{2-\frac{1}{\sqrt{r}}}$
		$\displaystyle\geq\frac{\sqrt{r}+1}{2}-\frac{r}{2\sqrt{r}-1}$
		$\displaystyle=\frac{\sqrt{r}+1}{2}-\frac{r-\frac{\sqrt{r}}{2}}{2\sqrt{r}-1}-\frac{\sqrt{r}}{4\sqrt{r}-2}$
		$\displaystyle=\frac{1}{2}-\frac{\sqrt{r}}{4\sqrt{r}-2}>0$

for all $r>1$ . This gives us

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{\sqrt{\frac{m}{k}}}{2-\sqrt{\frac{k}{m}}}$
		$\displaystyle<\frac{1}{2}\left(\sqrt{1+\frac{m-1}{k}}+1\right),$

concluding the proof of this subcase.

If $E$ is empty and $|A_{p}|\neq|A_{q}|$ for some $p,q\in S$ , then suppose without loss of generality that $S=[|S|]$ and $|A_{1}|\geq|A_{2}|\geq\dots\geq|A_{|S|}|$ . Recall that $\sum_{i=1}^{|S|}v_{i}(A^{*}_{i})=|S|-1$ is a necessary condition for maximizing $F$ . Then by the rearrangement inequality, $k\sum_{i\in S}\frac{v_{i}(A^{*}_{i})}{|A^{*}_{i}|}$ is minimized when $v_{i}(A^{*}_{i})=1$ for every $i\in[|S|-1]$ , and $v_{|S|}(A^{*}_{|S|})=0$ . Since $|A_{|S|}|\geq k+1$ , we have $\sum_{i=1}^{|S|-1}|A_{i}|\leq m-k-1$ , so therefore

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\max\limits_{\begin{subarray}{c}0\leq v_{i}(A^{}_{i})\leq 1\\ \sum_{i=1}^{\|S\|}v_{i}(A^{}_{i})\leq\|S\|-1\end{subarray}}F(\cdot)$
		$\displaystyle\leq\frac{\|S\|}{1+\sum_{i\in[\|S\|-1]}\frac{k}{\|A_{i}\|}}$
		$\displaystyle\leq\frac{\|S\|}{1+k\frac{(\|S\|-1)^{2}}{m-k-1}},$

where the last inequality transition is due to the AM-HM inequality. By computing the derivative of the last expression above with respect to $|S|$ , one can verify that the expression is maximized when $|S|=\sqrt{\frac{m-1}{k}}$ , and thus, the expression is at most

		$\displaystyle\frac{(m-k-1)\sqrt{\frac{m-1}{k}}}{m-k-1+k(\sqrt{\frac{m-1}{k}}-1)^{2}}$
		$\displaystyle=\frac{(m-1)\left(\sqrt{\frac{m-1}{k}}+1\right)-\sqrt{k(m-1)}\left(\sqrt{\frac{m-1}{k}}+1\right)}{2(m-1)-2\sqrt{k(m-1)}}$
		$\displaystyle=\frac{1}{2}\left(\sqrt{\frac{m-1}{k}}+1\right)<\frac{1}{2}\left(\sqrt{1+\frac{m-1}{k}}+1\right).$

We have now completed the proof for the subcase where $E$ is empty.

If $E$ is non-empty, we define $S^{\prime}\coloneqq S\setminus E$ and accordingly, we have

	$\displaystyle\frac{1+\sum_{i\in S}v_{i}(A^{}_{i})}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}v_{i}(A^{*}_{i})}$	$\displaystyle\leq\frac{1+\|S\|-\|E\|}{1+\sum_{i\in S\setminus E}\frac{k}{\|A^{*}_{i}\|}}$
		$\displaystyle=\frac{1+\|S^{\prime}\|}{1+\sum_{i\in S^{\prime}}\frac{k}{\|A^{*}_{i}\|}}.$

Since each agent $i\in E$ also belongs to $S$ , we have $\sum_{i\in S^{\prime}}|A_{i}^{*}|\leq m-(k+1)<m-1$ . Then by the AM-HM inequality, we have

\sum_{i\in S^{\prime}}\frac{1}{|A_{i}^{*}|}\geq\frac{|S^{\prime}|^{2}}{\sum_{i\in S^{\prime}}|A^{*}_{i}|}>\frac{|S^{\prime}|^{2}}{m-1},

implying

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{1+\|S^{\prime}\|}{1+k\frac{\|S^{\prime}\|^{2}}{m-1}}$
		$\displaystyle<\frac{1}{2}\left(\sqrt{1+\frac{m-1}{k}}+1\right),$

where the last inequality has been shown in the proof of Lemma 3.

Appendix B Omitted proofs for Section 4

B.1 Proof of Lemma 6

We prove this lemma statement via the following Lemmas 7, 8, and 9.

Lemma 7.

Given an instance $I$ where some agent $i$ exceeds the cardinality constraint in more than one category under the utilitarian-optimal allocation $\mathcal{A}^{*}$ , there exists another instance $I^{\prime}$ where under $\mathcal{A}^{\prime*}$ , agent $i$ exceeds the cardinality constraint in only one category, and $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ holds.

Proof.

For simplicity, we assume that only agent $1$ exceeds the cardinality constraint in the category subset $H$ , where $|H|\geq 2$ . Later on, we will explain how to extend the following proof to the case where both agents exceed the cardinality constraint in at least two categories each. Denote by $\mathcal{A}^{k}$ the utilitarian-optimal cardinal allocation and by $A^{k}_{ij}$ the bundle agent $i$ receives from $C_{j}$ .

Consider category $p\in\arg\min_{j}{\frac{k_{j}}{|A^{*}_{1j}|}}$ , breaking ties arbitrarily. We consider another instance $I^{\prime}$ that only differs from $I$ by the utility functions. In instance $I^{\prime}$ , each agent $i$ ’s utility function $u^{\prime}_{i}$ is described as follows,

•

for any $g\notin\bigcup_{j\in H}A^{*}_{1j}$ , $u^{\prime}_{i}(g)=u_{i}(g)$ ;
•

for any $g\in\bigcup_{j\in H\setminus\{p\}}A^{*}_{1j}$ , $u^{\prime}_{i}(g)=0$ ;
•

for any $g\in A^{*}_{1p}$ , $u^{\prime}_{i}(g)=u_{i}(g)+\frac{\sum_{j\in H\setminus\{p\}}u_{i}(A^{*}_{1j})}{|A^{*}_{1p}|}$ .

In other words, we merge each agent’s utilities for all of the items which agent $1$ receives in the category $H$ into the items which agent $1$ receives in category $p$ such that the marginal increase of item utilities is identical.

Let $\mathcal{B}^{*}$ (resp. $\mathcal{B}^{k}$ ) be the utilitarian-optimal (resp. utilitarian-optimal cardinal) allocation of $I^{\prime}$ . We have $\text{USW}(\mathcal{B}^{*})=\text{USW}(\mathcal{A}^{*})$ and therefore, in order to prove that $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ , it suffices to show that $\text{USW}(\mathcal{B}^{k})\leq\text{USW}(\mathcal{A}^{k})$ . For $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ , if $j\notin H$ , the total utility from the assignments of $C_{j}$ in these two allocations is equal. Then it suffices to prove that the total utility from the assignment of $\{C_{j}\}_{j\in H}$ in $\mathcal{B}^{k}$ is at most that in $\mathcal{A}^{k}$ . For categories $\{C_{j}\}_{j\in H}$ , the total utility from the goods $\bigcup_{j\in H}A^{*}_{2j}$ is identical between $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ as the agents’ utilities are unchanged for these items in $I^{\prime}$ , compared to $I$ . Accordingly, we next prove that the utility from $\bigcup_{j\in H}A^{*}_{1j}$ in $\mathcal{A}^{k}$ is at least that in $\mathcal{B}^{k}$ . By the construction of $u^{\prime}$ , only items in $A^{*}_{1p}$ (among $\bigcup_{j\in H}A^{*}_{1j}$ ) can result in non-zero utilities in $I^{\prime}$ . Next we claim that the assignment of items in $A^{*}_{1p}$ is identical in $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ .

Claim 2.

For any $i\in[2]$ , $A^{k}_{ip}\cap A^{*}_{1p}=B^{k}_{ip}\cap A^{*}_{1p}$ .

Proof of Claim 2.

It suffices to prove $A^{k}_{1p}\cap A^{*}_{1p}=B^{k}_{1p}\cap A^{*}_{1p}$ as we have already shown that the allocations of $A^{*}_{2p}$ are identical in $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ . Furthermore, we know that $A^{k}_{1p},B^{k}_{1p}\subseteq A^{*}_{1p}$ , and hence, it suffices to prove $A^{k}_{1p}=B^{k}_{1p}$ .

First, as $u_{1}(A^{*}_{1j})>u_{2}(A^{*}_{1j})$ for each $j\in H\setminus\{p\}$ and $u_{1}(g)\geq u_{2}(g)$ for every $g\in A^{*}_{1p}$ , we have $u^{\prime}_{1}(g)>u^{\prime}_{2}(g)$ for all $g\in A^{*}_{1p}$ . We then have $B^{*}_{1p}=A^{*}_{1p}$ . Now let $S$ denote the set of items moved from agent $1$ to agent $2$ , i.e., $S\coloneqq A^{*}_{1p}\setminus A^{k}_{1p}$ . Then $S$ contains the $|A^{*}_{1p}|-k$ items whose reassignments cause the minimum utility loss under $u_{i}$ ’s. Note that by the construction of $u^{\prime}$ , we see that starting from $\mathcal{B}^{*}$ and moving the items of $S$ from agent $1$ to agent $2$ also causes the minimum utility loss. Therefore, $B^{k}_{1p}=B^{*}_{1p}\setminus S=A^{*}_{1p}\setminus S=A^{k}_{1p}$ , completing the proof. ∎

We now upper bound the total utility of the items in $A^{*}_{1p}$ for allocation $\mathcal{B}^{k}$ as follows,

		$\displaystyle\sum_{i=1}^{2}u^{\prime}_{i}(B^{k}_{ip}\cap A^{*}_{1p})$
		$\displaystyle=\sum_{i=1}^{2}u_{i}(A^{k}_{ip}\cap A^{*}_{1p})$
		$\displaystyle\quad+\sum_{j\in H\setminus\{p\}}\left(\frac{k_{p}}{\|A^{}_{1p}\|}\cdot u_{1}(A^{}_{1j})+\frac{\|A^{}_{1p}\|-k_{p}}{\|A^{}_{1p}\|}\cdot u_{2}(A^{*}_{1j})\right)$
		$\displaystyle=\sum_{i=1}^{2}u_{i}(A^{k}_{ip}\cap A^{}_{1p})+\sum_{j\in H\setminus\{p\}}u_{2}(A^{}_{1j})$
		$\displaystyle\qquad+\frac{k_{p}}{\|A^{}_{1p}\|}\sum_{j\in H\setminus\{p\}}(u_{1}(A^{}_{1j})-u_{2}(A^{*}_{1j}))$
		$\displaystyle\leq\sum_{i=1}^{2}u_{i}(A^{k}_{ip}\cap A^{}_{1p})+\sum_{j\in H\setminus\{p\}}u_{2}(A^{}_{1j})$
		$\displaystyle\qquad+\sum_{j\in H\setminus\{p\}}\frac{k_{j}}{\|A^{}_{1j}\|}(u_{1}(A^{}_{1j})-u_{2}(A^{*}_{1j})),$

where the first equality is because $|A^{k}_{1p}\cap A^{*}_{1p}|=k_{p}$ and $|A^{k}_{2p}\cap A^{*}_{1p}|=|A^{*}_{1p}|-k$ , and the inequality is due to $\frac{k_{p}}{|A^{*}_{1p}|}\leq\frac{k_{j}}{|A^{*}_{1j}|}$ for every $j\in H$ . By using similar arguments to that in the proof of Lemma 4, one can verify that the last expression above is no greater than the utility from the assignment of $\bigcup_{j\in H}A^{*}_{1j}$ in allocation $\mathcal{A}^{k}$ . Note that the first summation term is equal to the total utility from $A^{*}_{1p}$ , and that the fact that the second summation term is at most $\sum_{j\in H\setminus\{p\}}\sum_{i=1}^{2}u_{i}(A^{k}_{ij}\cap A^{*}_{1j})$ can be checked by running the reassignment procedure in the proof of Lemma 4 for every $A^{*}_{1p}$ with $j\in H\setminus\{p\}$ . According to the construction of $I^{\prime}$ , with the exception of $\bigcup_{j\in H}A^{*}_{1j}$ , the allocations of the other items in $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ are identical. As a consequence, we have $\text{USW}(\mathcal{B}^{k})\leq\text{USW}(\mathcal{A}^{k})$ , and thus, the price of cardinality ratio of $I$ is no greater than that of $I^{\prime}$ .

For the case where both agents exceed the constraint in at least two categories, we can then repeat this process for agent $2$ ; note that the allocations of items in the category where agent $2$ exceeds the cardinality constraint are identical in $\mathcal{A}^{*}$ (resp. $\mathcal{A}^{k}$ ) and $\mathcal{B}^{*}$ (resp. $\mathcal{B}^{k}$ ) so that one can start from $I^{\prime}$ and construct another $I^{\prime\prime}$ to merge the utility of items of agent $2$ . ∎

Lemma 8.

Given an instance $I$ where under $\mathcal{A}^{*}$ , both agents exceed the cardinality constraint in at most one category each, there exists another instance $I^{\prime}$ where under $\mathcal{A}^{\prime*}$ , if an agent exceeds the cardinality constraint in some category $j$ , then she receives zero utility from every other category $[h]\setminus\{j\}$ , and $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ holds.

Proof.

Suppose without loss of generality that in $\mathcal{A}^{*}$ , agent $1$ exceeds the cardinality constraint of $C_{1}$ and also receives non-zero utility from $\{C_{2},C_{3},\ldots\}$ . By merging each agent’s utility for items $A^{*}_{12}$ , we construct an instance $I^{\prime}$ that only differs from $I$ in the utility functions. Specifically, the utility function $u^{\prime}_{i}$ of agent $i$ in $I^{\prime}$ is described as follows;

•

for any $g\in A^{*}_{12}$ , $u^{\prime}_{i}(g)=0$ ;
•

for any $g\in A^{*}_{11}$ , $u^{\prime}_{i}(g)=u_{i}(g)+\frac{1}{|A^{*}_{11}|}\cdot u_{i}(A^{*}_{12})$ ;
•

for any remaining $g$ , $u^{\prime}_{i}(g)=u_{i}(g)$ .

Let $\mathcal{B}^{*}$ and $\mathcal{B}^{k}$ denote the utilitarian-optimal allocation and the utilitarian-optimal cardinal allocation, respectively. By comparing the utility profiles between $I$ and $I^{\prime}$ , we see that $\text{USW}(\mathcal{A}^{*})=\text{USW}(\mathcal{B}^{*})$ , and thus it suffices to prove $\text{USW}(\mathcal{A}^{k})\geq\text{USW}(\mathcal{B}^{k})$ . By arguments similar to that in the proof of Claim 2, one can verify that in allocations $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ , the assignments of items $A^{*}_{11}$ are identical. We now consider the total utility from items in $A^{*}_{11}$ in allocation $\mathcal{B}^{k}$ ,

	$\displaystyle\sum_{i=1}^{2}u^{\prime}_{i}(B^{k}_{i1}\cap A^{*}_{11})$	$\displaystyle=\sum_{i=1}^{2}u_{i}(B^{k}_{i1}\cap A^{}_{11})+\frac{k_{1}}{\|A^{}_{11}\|}u_{1}(A^{*}_{12})$
		$\displaystyle\quad+\frac{\|A^{}_{11}\|-k_{1}}{\|A^{}_{11}\|}u_{2}(A^{*}_{12})$
		$\displaystyle=\sum_{i=1}^{2}u_{i}(B^{k}_{i1}\cap A^{}_{11})+u_{2}(A^{}_{12})$
		$\displaystyle\quad+\frac{k_{1}}{\|A^{}_{11}\|}\left(u_{1}(A^{}_{12})-u_{2}(A^{*}_{12})\right).$

We now show that the last expression above is no greater than the utility from items $A^{*}_{11}\cup A^{*}_{12}$ in $\mathcal{A}^{k}$ . The first summation term is equal to $u_{1}(A^{*}_{11})$ , which is the utility from items $A^{*}_{11}$ in $\mathcal{A}^{k}$ . The sum of the last two terms is no greater than $u_{1}(A^{*}_{12})$ as $k_{1}<|A^{*}_{11}|$ and $u_{1}(A^{*}_{12})\geq u_{2}(A^{*}_{12})$ . By the construction of $I^{\prime}$ , the assignments of items in $\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ are identical, with the exception of $A^{*}_{11}\cup A^{*}_{12}$ . Thus, we have $\text{USW}(\mathcal{B}^{k})\leq\text{USW}(\mathcal{A}^{k})$ and therefore $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ . We can repeat this process for both agents, and for each of the categories where an agent does not exceed the cardinality constraint but receives non-zero utility in $\mathcal{A}^{*}$ , concluding the proof. ∎

Lemma 9.

Given an instance $I$ where under $\mathcal{A}^{*}$ , at most one agent exceeds the cardinality constraint in some category, there exists another instance $I^{\prime}$ where under $\mathcal{A}^{\prime*}$ , both agents exceed the cardinality constraint in one category each, and these categories are different. Also, $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ holds.

Proof.

We ignore the case where neither agent violates the cardinality constraints, as it holds that $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}=1$ . If only one agent exceeds the cardinality constraints, by Lemma 7, it suffices to assume (w.l.o.g.) that agent $1$ exceeds (only) the constraint of category $1$ . Then by Lemma 8, we further assume that agent $1$ receives zero utility from $\{C_{2},C_{3},\ldots\}$ . As agent $2$ does not exceed the cardinality constraint of category $2$ , agent $1$ receives at least $|A^{*}_{12}|\geq|C_{2}|-k_{2}$ items from $C_{2}$ and by our assumption, has a value of $0$ for each of them. Since agents’ utilities are normalized, agent $2$ must receive at least one non-zero utility item $g^{*}\in\mathcal{A}^{*}$ . We can construct another instance $I^{\prime}$ where agent $2$ ’s utility for $g^{*}\in\mathcal{A}^{*}$ is decreased by an arbitrarily small number $\epsilon>0$ , and her utility for each item in $A^{*}_{12}$ is increased by $\frac{\epsilon}{|A^{*}_{12}|}$ . As a result, agent $2$ now exceeds the cardinality constraint in category $2$ . The optimal utilitarian welfare of $I^{\prime}$ is equal to $\text{USW}(\mathcal{A}^{*})$ , while that of utilitarian-optimal cardinal allocation slightly decreased as agent $2$ can only receive $k_{2}$ items in cardinal allocations. Therefore, $\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}\leq\frac{\text{OPT-USW}(I^{\prime})}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I^{\prime})}\text{USW}(\mathcal{A})}$ . ∎

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\frac{\sum_{i\in S}u_{i}(A^{}_{i})}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{}_{i}))}$
		$\displaystyle=\frac{1+\sum_{i\in S}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{}_{i}))}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}(u_{i}(A^{}_{i})-u_{i^{\dagger}}(A^{*}_{i}))}$
		$\displaystyle=\frac{1+\sum_{i\in S}v_{i}(A^{}_{i})}{1+\sum_{i\in S}\frac{k}{\|A^{}_{i}\|}v_{i}(A^{*}_{i})},$

	$\displaystyle\frac{\text{OPT-USW}(I)}{\max_{\mathcal{A}\in\mathcal{C}_{\kappa}(I)}\text{USW}(\mathcal{A})}$	$\displaystyle\leq\max\limits_{\begin{subarray}{c}0\leq v_{i}(A^{}_{i})\leq 1\\ \sum_{i=1}^{\|S\|}v_{i}(A^{}_{i})\leq\|S\|-1\end{subarray}}F(\cdot)$
		$\displaystyle\leq\frac{\|S\|}{1+\sum_{i\in[\|S\|-1]}\frac{k}{\|A_{i}\|}}$
		$\displaystyle\leq\frac{\|S\|}{1+k\frac{(\|S\|-1)^{2}}{m-k-1}},$

		$\displaystyle\sum_{i=1}^{2}u^{\prime}_{i}(B^{k}_{ip}\cap A^{*}_{1p})$
		$\displaystyle=\sum_{i=1}^{2}u_{i}(A^{k}_{ip}\cap A^{*}_{1p})$
		$\displaystyle\quad+\sum_{j\in H\setminus\{p\}}\left(\frac{k_{p}}{\|A^{}_{1p}\|}\cdot u_{1}(A^{}_{1j})+\frac{\|A^{}_{1p}\|-k_{p}}{\|A^{}_{1p}\|}\cdot u_{2}(A^{*}_{1j})\right)$
		$\displaystyle=\sum_{i=1}^{2}u_{i}(A^{k}_{ip}\cap A^{}_{1p})+\sum_{j\in H\setminus\{p\}}u_{2}(A^{}_{1j})$
		$\displaystyle\qquad+\frac{k_{p}}{\|A^{}_{1p}\|}\sum_{j\in H\setminus\{p\}}(u_{1}(A^{}_{1j})-u_{2}(A^{*}_{1j}))$
		$\displaystyle\leq\sum_{i=1}^{2}u_{i}(A^{k}_{ip}\cap A^{}_{1p})+\sum_{j\in H\setminus\{p\}}u_{2}(A^{}_{1j})$
		$\displaystyle\qquad+\sum_{j\in H\setminus\{p\}}\frac{k_{j}}{\|A^{}_{1j}\|}(u_{1}(A^{}_{1j})-u_{2}(A^{*}_{1j})),$

	$\displaystyle\sum_{i=1}^{2}u^{\prime}_{i}(B^{k}_{i1}\cap A^{*}_{11})$	$\displaystyle=\sum_{i=1}^{2}u_{i}(B^{k}_{i1}\cap A^{}_{11})+\frac{k_{1}}{\|A^{}_{11}\|}u_{1}(A^{*}_{12})$
		$\displaystyle\quad+\frac{\|A^{}_{11}\|-k_{1}}{\|A^{}_{11}\|}u_{2}(A^{*}_{12})$
		$\displaystyle=\sum_{i=1}^{2}u_{i}(B^{k}_{i1}\cap A^{}_{11})+u_{2}(A^{}_{12})$
		$\displaystyle\quad+\frac{k_{1}}{\|A^{}_{11}\|}\left(u_{1}(A^{}_{12})-u_{2}(A^{*}_{12})\right).$

The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective††thanks: The author names are ordered alphabetically.

Abstract

1 Introduction

1.1 Our Contribution

Single category.

Multiple categories.

1.2 Related Work

2 Preliminaries

Definition 1.

Definition 2.

Definition 3.

3 Single Category

3.1 Utilitarian Social Welfare

Theorem 1.

Proof.

Lemma 1.

Proof.

Lemma 2.

Lemma 3.

Proof Sketch.

Lemma 4.

Proof Sketch.

Lemma 5.

Partial Proof.

Proposition 1.

Proof.

3.2 Egalitarian Social Welfare

Theorem 2.

Proof.

4 Multiple Categories

4.1 Utilitarian Social Welfare

Lemma 6.

Theorem 3.

Proof.

Theorem 4.

Proof.

Proposition 2.

Proof.

4.2 Egalitarian Social Welfare

Theorem 5.

Proof.

5 Discussion

Acknowledgements

References

Appendix A Omitted Proofs for Section 3

A.1 Proof of Lemma 2

A.2 Proof of Lemma 3

A.3 Proof of Lemma 4

Claim 1.

Proof of Claim 1.

A.4 Proof of Lemma 5 (Cont.)

Appendix B Omitted proofs for Section 4

B.1 Proof of Lemma 6

Lemma 7.

Proof.

Claim 2.

Proof of Claim 2.

Lemma 8.

Proof.

Lemma 9.

Proof.

The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective^†^†thanks: The author names are ordered alphabetically.