Differentially Private Fair Division

Pasin Manurangsi,¹ Warut Suksompong²

Abstract

Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of differential privacy. We present algorithms for approximate envy-freeness and proportionality when two instances are considered to be adjacent if they differ only on the utility of a single agent for a single item. On the other hand, we provide strong negative results for both fairness criteria when the adjacency notion allows the entire utility function of a single agent to change.

1 Introduction

Fairness is a principal concern in numerous social decision-making processes, not least when it comes to allocating scarce resources among interested parties. Whether we divide equipment between healthcare personnel, assign facility time slots to potential users, or distribute office space among working groups in an organization, it is desirable that all parties involved feel fairly treated. While fair division has been studied in economics for several decades (Brams and Taylor 1996; Moulin 2003, 2019), the subject has received substantial interest from computer scientists in recent years, much of which has concentrated on the fair allocation of indivisible resources (Bouveret, Chevaleyre, and Maudet 2016; Markakis 2017; Walsh 2020; Suksompong 2021; Amanatidis et al. 2022; Aziz et al. 2022).

The fair division literature typically focuses on satisfying concrete fairness criteria. Two of the most prominent criteria are envy-freeness and proportionality. In an envy-free allocation, no agent prefers to have another agent’s bundle instead of her own. In a proportional allocation, every agent receives value at least $1/n$ of her value for the entire resource, where $n$ denotes the number of agents. As neither of these criteria is always satisfiable,¹¹1For example, imagine two siblings fighting for one toy. researchers have proposed the relaxations envy-freeness up to $c$ items (EF $c$ ) and proportionality up to $c$ items (PROP $c$ ); here, $c$ is a non-negative integer parameter. Under additive utilities, EF $c$ implies PROP $c$ for every $c$ ,²²2See the proof of Proposition 2.2(b) in our prior work (Manurangsi and Suksompong 2022). and an EF1 allocation (which must also be PROP1) is guaranteed to exist (Lipton et al. 2004).

In addition to fairness, another consideration that has become increasingly important nowadays—as large amounts of data are constantly collected, processed, and analyzed—is privacy. Indeed, an agent participating in a resource allocation procedure may not want other participants to know her preferences if she considers these as sensitive information, for example, if these preferences correspond to the times when she is available to use a facility, or if they represent her valuations for potential team members when distributing employees in an organization. Consequently, a desirable procedure should ensure that an individual participant’s preferences cannot be inferred based on the output of the procedure. Achieving privacy alone is trivial, as the procedure can simply ignore the agents’ preferences and always output a fixed allocation that it announces publicly in advance. However, it is clear that such a procedure can be highly unfair for certain preferences of the agents. Despite its significance, the issue of privacy has been largely unaddressed in the fair division literature as far as we are aware.³³3Sun and Yang (2009) studied a setting in which agents have “reservation values” over items, and considered a mechanism to be private if it does not require agents to reveal these values.

In this paper, we investigate the fundamental question of whether fairness and privacy can be attained simultaneously in the allocation of indivisible resources. We use the well-established framework of differential privacy (DP), which has been widely adopted not only in academia but also in industry (Erlingsson, Pihur, and Korolova 2014; Shankland 2014; Greenberg 2016; Apple Differential Privacy Team 2017; Ding, Kulkarni, and Yekhanin 2017) as well as government sectors (Abowd 2018). Intuitively, the output distribution of a (randomized) DP⁴⁴4We use the abbreviation DP for both “differential privacy” and “differentially private”. algorithm should not change by much when a single “entry” of the input is modified. DP provides a privacy protection for individual entries by ensuring that an adversary with access to the output can only gain limited information about each individual entry. At the same time, DP algorithms often still provide useful outputs based on the aggregated information. We outline the tools and concepts from DP used in this work in Section 2.2.⁵⁵5For in-depth treatments of the subject, we refer to the surveys by Dwork (2008) and Dwork and Roth (2014).

		Agent-Level DP	(Agent $\times$ Item)-Level DP
EF	Upper	$O(m/n)$ (Trivial)	$O(n\log m)$ (Theorem 4.1)
EF	Lower	$\Omega\left(\sqrt{\frac{m}{n}\log n}\right)$ (Theorem 3.1)	$\Omega(\log m)$ (Theorem 4.9)
PROP	Upper	$O(m/n)$ (Trivial)	$O(\log m)$ (Theorem 4.7)
PROP	Lower	$\Omega\left(\sqrt{\frac{m}{n}}\right)$ (Theorem 3.2)	$\Omega((\log m)/n)$ (Theorem 4.11)

Table 1: Overview of our results. We display the smallest

c

such that there is an

\varepsilon

-DP algorithm that outputs an EF

c

or PROP

c

allocation with probability at least

1-\beta

. For simplicity of the bounds, we assume that

m>n^{2}

\varepsilon

is a small constant, and

\beta

is sufficiently small (depending only on

\varepsilon,n

and not on

m

). All upper bounds hold even for connected allocations. Lower bounds for (agent

\times

item)-level DP hold only for connected allocations, but those for agent-level DP hold for arbitrary allocations. The bounds

O(m/n)

follow trivially from outputting a fixed allocation in which each agent receives

O(m/n)

items.

As alluded to above, DP is defined with respect to what one considers to be an entry of the input, or equivalently, in terms of adjacent inputs. We consider two notions of adjacency between fair division instances. For agent-level adjacency, two instances are considered to be adjacent if they differ on the utility function of at most one agent. For (agent $\times$ item)-level adjacency, two instances are adjacent if they differ at most on the utility of a single agent for a single item. We work with the standard definition of $\varepsilon$ -differential privacy ( $\varepsilon$ -DP): for a parameter $\varepsilon\geq 0$ , an algorithm is said to satisfy $\varepsilon$ -DP if the probability that it outputs a certain allocation for an input and the corresponding probability for an adjacent input differ by a factor of at most $e^{\varepsilon}$ . Note that, for the same $\varepsilon$ , agent-level DP offers a stronger privacy protection for an entire utility function of an individual agent, whereas (agent $\times$ item)-level DP only offers a protection for a utility of a single agent for a single item. Our goal is to devise $\varepsilon$ -DP algorithms that output an EF $c$ or PROP $c$ allocation for a small value of $c$ with sufficiently high probability, or to prove that this task is impossible. Denote by $n$ and $m$ the number of agents and items, respectively.

We begin in Section 3 by considering agent-level DP. For this demanding benchmark, we establish strong lower bounds with respect to both approximate envy-freeness and proportionality (Theorems 3.1 and 3.2). In both cases, our lower bounds imply that, for fixed $n$ and $\varepsilon$ , no $\varepsilon$ -DP algorithm can output an EF $c$ or PROP $c$ allocation for $c=o(\sqrt{m})$ with some large constant probability. Our results hold even when the agents have binary additive utilities, and indicate that agent-level DP is too stringent to permit algorithms with significant fairness guarantees.

In Section 4, we turn our attention to (agent $\times$ item)-level DP, and deliver encouraging news for this more relaxed notion. In contrast to the previous lower bounds, we present $\varepsilon$ -DP algorithms for EF $c$ and PROP $c$ where $c$ only grows logarithmically in $m$ for fixed $n$ and $\varepsilon$ (Theorems 4.1 and 4.7). Our EF $c$ algorithm works for arbitrary monotone utility functions, whereas our PROP $c$ algorithm allows (not necessarily binary) additive utilities. Moreover, our algorithms always output allocations that are connected.⁶⁶6See Section 2 for the definition. Connectivity can be desirable when there is a spatial or temporal order of the items, for instance, when allocating time slots to facility users or offices along a corridor to research groups (Bouveret et al. 2017; Suksompong 2019; Bei et al. 2022; Bilò et al. 2022). We complement these results by showing a tight lower bound of $\Omega(\log m)$ for connected allocations (Theorems 4.9 and 4.11), even with binary additive utilities.

A summary of our results can be found in Table 1.

2 Preliminaries

2.1 Fair Division

In fair division of indivisible items, there is a set $N=[n]$ of agents and a set $M=[m]$ of items, where $[k]$ denotes the set $\{1,2,\dots,k\}$ for each positive integer $k$ . The utility function of agent $i$ is given by $u_{i}:2^{M}\to\mathbb{R}_{\geq 0}$ . Throughout this work, we assume that utility functions are monotone, that is, $u_{i}(S)\leq u_{i}(T)$ for any $S\subseteq T\subseteq M$ . For a single item $j\in M$ , we write $u_{i}(j)$ instead of $u_{i}(\{j\})$ . We seek to output an allocation $A=(A_{1},\dots,A_{n})$ , which is an ordered partition of $M$ into $n$ bundles.

We consider two important fairness notions. Let $c$ be a non-negative integer.

•

An allocation $A$ is said to be envy-free up to $c$ items (EF $c$ ) if, for any $i,i^{\prime}\in N$ , there exists $S\subseteq{A_{i^{\prime}}}$ with $|S|\leq c$ such that $u_{i}(A_{i})\geq u_{i}(A_{i^{\prime}}\setminus S)$ .
•

An allocation $A$ is said to be proportional up to $c$ items (PROP $c$ ) if, for any $i\in N$ , there exists $S\subseteq M\setminus A_{i}$ with $|S|\leq c$ such that $u_{i}(A_{i})\geq u_{i}(M)/n-u_{i}(S)$ .

We say that an allocation $A$ is connected if each $A_{i}$ corresponds to an interval, i.e., $A_{i}=\{\ell,\ell+1,\dots,r\}$ for some $\ell,r\in M$ ; it is possible that $A_{i}$ is a singleton or empty. Let $\mathcal{P}^{\mathrm{conn}}(m,n)$ denote the set of all connected allocations. We will use the following result on the existence of connected EF2 allocations.⁷⁷7Recently, Igarashi (2023) improved this guarantee to EF1.

Theorem 2.1 ((Bilò et al. 2022)).

For any $m,n\in\mathbb{N}$ and any monotone utility functions, there exists a connected EF2 allocation.

A utility function $u_{i}$ is additive if $u_{i}(S)=\sum_{j\in S}u_{i}(j)$ for all $S\subseteq M$ . Furthermore, an additive utility function is said to be binary if $u_{i}(j)\in\{0,1\}$ for all $j\in M$ .

2.2 Differential Privacy

Let us start by recalling the general definition of DP. Denote by $\mathcal{X}$ the set of all possible inputs to the algorithm.

Definition 2.2 (Differential Privacy (Dwork et al. 2006b)).

Let $\varepsilon\geq 0$ be a non-negative real number. A randomized algorithm $\mathcal{M}$ is said to be $\varepsilon$ -differentially private ( $\varepsilon$ -DP) if, for every pair of adjacent inputs $X,X^{\prime}$ , it holds that

\displaystyle\Pr[\mathcal{M}(X)=o]\leq e^{\varepsilon}\cdot\Pr[\mathcal{M}(X^{\prime})=o]

for all $o\in\operatorname{range}(\mathcal{M})$ .

An input in our fair division context consists of the agents’ utility functions. Different notions of adjacency lead to different levels of privacy protection. We consider two natural notions: agent-level DP and (agent $\times$ item)-level DP.

Definition 2.3 (Agent-Level DP).

Two inputs $(u_{i})_{i\in N}$ and $(u^{\prime}_{i})_{i\in N}$ are said to be agent-level adjacent if they coincide on all but a single agent, i.e., there exists $i^{*}\in N$ such that $u_{i}=u^{\prime}_{i}$ for all $i\in N\setminus\{i^{*}\}$ .

An algorithm that is $\varepsilon$ -DP against this adjacency notion is said to be agent-level $\varepsilon$ -DP.

Definition 2.4 ((Agent $\times$ Item)-Level DP).

Two inputs $(u_{i})_{i\in N}$ and $(u^{\prime}_{i})_{i\in N}$ are said to be (agent $\times$ item)-level adjacent if they coincide on all but the utility of a single agent for a single item, i.e., there exist $i^{*}\in N,j^{*}\in M$ such that

•

$u_{i}=u^{\prime}_{i}$ for all $i\in N\setminus\{i^{*}\}$ , and
•

$u_{i^{*}}(S)=u^{\prime}_{i^{*}}(S)$ for all $S\subseteq M\setminus\{j^{*}\}$ .

An algorithm that is $\varepsilon$ -DP against this adjacency notion is said to be (agent $\times$ item)-level $\varepsilon$ -DP.

It is clear that agent-level DP is a more demanding notion than (agent $\times$ item)-level DP. Specifically, the former provides a stronger privacy protection than the latter, and designing an algorithm for the former is more difficult. Indeed, we will prove strong lower bounds for agent-level DP and present algorithms for (agent $\times$ item)-level DP.

Next, we outline several tools from the DP literature that will be useful for our proofs.

Basic Composition.

The first tool that we will use is the composition of DP: the result of running multiple DP algorithms remains DP, but with a worse privacy parameter.

Theorem 2.5 (Basic Composition of DP, e.g., (Dwork and Roth 2014)).

An algorithm that is a result of running two algorithms (possibly in an adaptive manner) that are $\varepsilon_{1}$ -DP and $\varepsilon_{2}$ -DP, respectively, is $(\varepsilon_{1}+\varepsilon_{2})$ -DP.

A special case of basic composition (Theorem 2.5) that is often used is the case $\varepsilon_{2}=0$ , which is referred to as post-processing of DP.

Observation 2.6 (Post-processing of DP).

An algorithm that runs an $\varepsilon$ -DP subroutine and then returns a function of the output of this subroutine is also $\varepsilon$ -DP.

Parallel Composition.

While basic composition provides a simple way to account for the privacy budget $\varepsilon$ when we run multiple algorithms, it can be improved in certain cases. One such case is when the algorithms are run on “disjoint pieces” of the input. In this case, we do not need to add up the $\varepsilon$ ’s, a fact known as parallel composition of DP (McSherry 2010). Since the statement we use below is slightly different from that in McSherry’s work, we provide a full proof for completeness in Section A.1.

Theorem 2.7 ((McSherry 2010)).

Let $\sim$ be an adjacency notion, and let $\Gamma:\mathcal{X}\to\mathcal{X}^{k}$ be a function such that, if $X\sim X^{\prime}$ , then there exists $i^{*}\in[k]$ such that $\Gamma(X)_{i}=\Gamma(X^{\prime})_{i}$ for all $i\in[k]\setminus\{i^{*}\}$ , and $\Gamma(X)_{i^{*}}\sim\Gamma(X^{\prime})_{i^{*}}$ . If $\mathcal{M}$ is an $\varepsilon$ -DP algorithm with respect to the adjacency notion $\sim$ , then the algorithm $\mathcal{M}^{\prime}$ that outputs $(\mathcal{M}(\Gamma(X)_{1}),\dots,\mathcal{M}(\Gamma(X)_{k}))$ is also $\varepsilon$ -DP with respect to $\sim$ .

Group Privacy.

While differential privacy offers protection primarily against the adjacency notion for which it is defined, it also offers protection against more general adjacency notions. Below we state one such protection, which is often referred to as group differential privacy.

Let $\sim$ be any adjacency relation. For $k\in\mathbb{N}$ , let us define $\sim_{k}$ as the adjacency relation where $X\sim_{k}X^{\prime}$ if and only if there exists a sequence $X_{0},\dots,X_{k}$ such that $X_{0}=X,X_{k}=X^{\prime}$ , and $X_{i-1}\sim X_{i}$ for all $i\in[k]$ .

Lemma 2.8 (Group Differential Privacy, e.g., (Vadhan 2017)).

Let $k\in\mathbb{N}$ . If an algorithm is $\varepsilon$ -DP with respect to an adjacency notion $\sim$ , it is also $(k\varepsilon)$ -DP with respect to the adjacency notion $\sim_{k}$ .

As an immediate consequence of Lemma 2.8, any (agent $\times$ item)-level $\varepsilon$ -DP algorithm is also agent-level $(m\varepsilon)$ -DP. However, the factor $m\varepsilon$ makes the latter guarantee rather weak, especially as $m$ grows.

Sensitivity.

We next define the sensitivity of a function, which will be used multiple times in this work. Note that the definition depends on the adjacency notion, but we do not explicitly include it in the notation for convenience.

Definition 2.9.

The sensitivity of a function $f:\mathcal{X}\to\mathbb{R}$ (with respect to adjacency notion $\sim$ ) is defined as $\Delta(f):=\max_{X\sim X^{\prime}}|f(X)-f(X^{\prime})|$ .

Sensitivity is a key notion in DP. As shown by Dwork et al. (2006b), the Laplace mechanism—which outputs $f(X)+Z$ where $Z$ is drawn from the Laplace distribution⁸⁸8The Laplace distribution with scale $b$ is the distribution whose probability density function is proportional to $\exp(-|x|/b)$ . with scale $(\Delta(f)/\varepsilon)$ —satisfies $\varepsilon$ -DP. This means that if a function has low sensitivity, then we can estimate it to within a small error (with high probability).

Sparse Vector Technique.

We will use the so-called sparse vector technique (SVT). The setting is that there are low-sensitivity functions $f_{1},\dots,f_{H}:\mathcal{X}\to\mathbb{R}$ . We want to find the first function $f_{i}$ whose value is above a target threshold. A straightforward approach would be to add Laplace noise to each $f_{i}(X)$ and then select the function accordingly; due to the basic composition theorem, this would require us to add noise of scale $O(H/\varepsilon)$ to each function. SVT allows us to reduce the dependency on $H$ to merely $O(\log H)$ . The technique was first introduced by Dwork et al. (2009), and the convenient version below is due to Dwork and Roth (2014, Theorem 3.24).

Theorem 2.10.

There exists a constant $\upsilon>0$ such that the following holds. Let $f_{1},\dots,f_{H}:\mathcal{X}\to\mathbb{R}$ be functions with $\Delta(f_{1}),\dots,\Delta(f_{H})\leq 1$ . For any $\varepsilon>0$ , $\beta\in(0,1)$ , and $\tau\in\mathbb{R}$ , there exists an $\varepsilon$ -DP algorithm such that, if $\max_{h}f_{h}(X)\geq\tau$ , then, with probability at least $1-\beta$ , the algorithm outputs $h^{*}\in[H]$ with the following properties:

•

$f_{h^{*}}(X)\geq\tau-\upsilon\cdot\log(H/\beta)/\varepsilon$ ;
•

For all $h^{\prime}<h^{*}$ , $f_{h^{\prime}}(X)\leq\tau+\upsilon\cdot\log(H/\beta)/\varepsilon$ .

Exponential Mechanism.

We will also use the exponential mechanism (EM) of McSherry and Talwar (2007). In its generic form, EM allows us to select a solution from a candidate set $\mathcal{H}$ . Specifically, we may define (low-sensitivity) scoring functions $\operatorname{scr}_{h}:\mathcal{X}\to\mathbb{R}$ for each $h\in\mathcal{H}$ . Then, EM outputs a solution that approximately maximizes the score. The precise statement is given below.⁹⁹9The formulation here can be derived, e.g., by plugging $t=\log(1/\beta)$ into Corollary 3.12 of Dwork and Roth (2014).

Theorem 2.11 ((McSherry and Talwar 2007)).

For any $\varepsilon>0$ and $\beta\in(0,1)$ , a finite set $\mathcal{H}$ , and a set of scoring functions $\{\operatorname{scr}_{h}\}_{h\in\mathcal{H}}$ such that $\Delta(\operatorname{scr}_{h})\leq 1$ for each $h\in\mathcal{H}$ , there is an $\varepsilon$ -DP algorithm that, on every input $X$ , outputs $h^{*}$ such that

\displaystyle\operatorname{scr}_{h^{*}}(X)\geq\max_{h\in\mathcal{H}}\operatorname{scr}_{h}(X)-\frac{2\log(|\mathcal{H}|/\beta)}{\varepsilon}

with probability at least $1-\beta$ .

2.3 Anti-Concentration Inequalities

Denote by $\operatorname{Ber}(1/2)$ the distribution that is $0$ with probability $1/2$ , and $1$ otherwise. The following type of anti-concentration inequalities is well-known; for completeness, we provide a proof of this version in Section A.2.

Lemma 2.12.

If $k\geq 100$ and $X_{1},\dots,X_{k}$ are independent random variables drawn from $\operatorname{Ber}(1/2)$ , then

\Pr\left[\sum_{i=1}^{k}X_{i}<\frac{k}{2}-0.1\sqrt{k}\right]\geq\frac{1}{4}.

We will also use the following anti-concentration inequality, whose proof can be found in Section A.3.

Lemma 2.13.

Let $k\geq 100$ and let $X_{1},\dots,X_{k}$ be independent $\operatorname{Ber}(1/2)$ random variables. Also, let $S:=X_{1}+\dots+X_{k}$ and $\gamma\in[2,2^{k/4}]$ . Then,

\displaystyle\Pr\left[S>\frac{k}{2}+0.1\sqrt{k\log\gamma}\right]\geq\frac{0.1}{\gamma}.

3 Agent-Level DP

We begin by considering the demanding notion of agent-level DP, and provide strong negative results for this notion.

For EF $c$ , we show a lower bound that,¹⁰¹⁰10Unless specified otherwise, $\log$ refers to the natural logarithm. when $m>n\log n$ , holds even against $c=\Theta\left(\sqrt{\frac{m}{n}\log n}\right)$ .

Theorem 3.1.

There exists a constant $\zeta>0$ such that, for any $\varepsilon>0$ , there is no agent-level $\varepsilon$ -DP algorithm that, for any input binary additive utility functions, outputs an EF $c$ allocation with probability higher than $1-\frac{e^{-\varepsilon}}{200}$ , where $c=\left\lfloor\zeta\sqrt{\frac{m}{n}\cdot\min\left\{\log n,\frac{m}{n}\right\}}\right\rfloor$ .

For proportionality, we prove a slightly weaker bound where $c=\Theta(\sqrt{m/n})$ and the “failure probability” required for the lower bound to apply is also smaller at $O_{\varepsilon}(1/n)$ (compared to $O_{\varepsilon}(1)$ for envy-freeness).

Theorem 3.2.

There exists a constant $\zeta>0$ such that, for any $\varepsilon>0$ , there is no agent-level $\varepsilon$ -DP algorithm that, for any input binary additive utility functions, outputs a PROP $c$ allocation with probability higher than $1-\frac{e^{-\varepsilon}}{8n}$ , where $c=\lfloor\zeta\sqrt{m/n}\rfloor$ .

We first prove Theorem 3.2, before proceeding to present the proof of Theorem 3.1, which uses similar arguments but requires a more delicate anti-concentration inequality.

3.1 Proof of Theorem 3.2

We let $\zeta=0.01$ . If $m<100n$ , then $c=0$ and the theorem holds trivially even without the privacy requirement. Hence, we may assume that $m\geq 100n$ . Throughout the proof, we consider random utility functions ${\bm{u}}=(u_{i})_{i\in N}$ where each $u_{i}(j)$ is an independent $\operatorname{Ber}(1/2)$ random variable. For brevity, we will not repeatedly state this in the calculations below.

We start by proving the following auxiliary lemma that if $A_{i}$ is small, then, for a random utility ${\bm{u}}$ as above, the allocation fails to be PROP $c$ for agent $i$ with a constant probability.

Lemma 3.3.

For $\zeta=0.01$ , let $c$ be as in Theorem 3.2 and $A$ be an allocation such that $|A_{i}|\leq m/n$ . Then, we have

\displaystyle\Pr_{{\bm{u}}}[A\text{ is not PROP}c\text{ for agent }i]\geq 1/8.

Proof.

Let $c^{\prime}=2c$ . We have

$\displaystyle\Pr_{{\bm{u}}}$	$\displaystyle[A\text{ is not PROP}c\text{ for agent }i]$
	$\displaystyle\geq\Pr_{u_{i}}\left[u_{i}(A_{i})<\frac{u_{i}(M)}{n}-c\right]$
	$\displaystyle=\Pr_{u_{i}}\left[u_{i}(A_{i})<\frac{u_{i}(M\setminus A_{i})}{n-1}-\frac{n}{n-1}\cdot c\right]$
	$\displaystyle\geq\Pr_{u_{i}}\left[u_{i}(A_{i})<\frac{m}{2n}-c^{\prime}\,\wedge\,u_{i}(M\setminus A_{i})\geq\frac{m(n-1)}{2n}\right]$
	$\displaystyle=\Pr_{u_{i}}\left[u_{i}(A_{i})<\frac{m}{2n}-c^{\prime}\right]$
	$\displaystyle\quad\cdot\Pr_{u_{i}}\left[u_{i}(M\setminus A_{i})\geq\frac{m(n-1)}{2n}\right]$
	$\displaystyle\geq\frac{1}{2}\cdot\Pr_{u_{i}}\left[u_{i}(A_{i})<\frac{m}{2n}-c^{\prime}\right],$	(1)

where the last inequality follows from the fact that $|M\setminus A_{i}|\geq m(n-1)/n$ and symmetry.

Since $|A_{i}|$ is an integer, $|A_{i}|\leq\lfloor m/n\rfloor$ . Moreover, since $\lfloor m/n\rfloor\geq 100$ and the function $f(k)=k/2-0.1\sqrt{k}$ is increasing in $[1,\infty)$ , applying Lemma 2.12 with $k=\lfloor m/n\rfloor$ gives $\Pr_{u_{i}}\left[u_{i}(A_{i})<\frac{m}{2n}-c^{\prime}\right]\geq 1/4$ . Plugging this back into (1) yields the desired bound. ∎

We are now ready to prove Theorem 3.2.

Proof of Theorem 3.2.

Let $\zeta=0.01$ and let $\mathcal{M}$ be any agent-level $\varepsilon$ -DP algorithm. Consider the input utility functions ${\bm{u}}^{\prime}=(u^{\prime}_{i})_{i\in N}$ where the utility functions are all-zero, and consider the distribution $\mathcal{M}({\bm{u}}^{\prime})$ . For any allocation $A$ , we have $\Pr_{i\in N}\left[|A_{i}|\leq m/n\right]\geq 1/n$ since at least one bundle $A_{i}$ must have size at most $m/n$ . This implies that $\Pr_{i\in N,A\sim\mathcal{M}({\bm{u}}^{\prime})}[|A_{i}|\leq m/n]\geq 1/n$ . Thus, there exists $i^{*}\in N$ such that $\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}[|A_{i^{*}}|\leq m/n]\geq 1/n$ .

Recalling the definition of ${\bm{u}}$ from earlier and applying Lemma 3.3, we have¹¹¹¹11Here, PROP $c$ is with respect to ${\bm{u}}$ .

	$\displaystyle\Pr_{{\bm{u}},A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not PROP}c\text{ for agent }i^{*}]$
	$\displaystyle\geq\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}\left[\|A_{i^{*}}\|\leq m/n\right]$
	$\displaystyle\quad\cdot\Pr_{{\bm{u}},A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not PROP}c\text{ for agent }i^{}\mid\|A_{i^{}}\|\leq m/n]$
	$\displaystyle\geq(1/n)\cdot(1/8)=1/(8n).$

Hence, there exists $u^{*}_{i^{*}}$ such that¹²¹²12The abbreviation “w.r.t.” stands for “with respect to”.

\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not PROP}c\text{ for agent }i^{*}\text{ w.r.t. }u^{*}_{i^{*}}]\geq 1/(8n).

Now, let ${\bm{u}}^{*}$ be the input utility such that $u^{*}_{i}$ is all-zero for each $i\neq i^{*}$ while $u^{*}_{i^{*}}$ is as above. Notice that ${\bm{u}}^{*}$ is adjacent to ${\bm{u}}^{\prime}$ under agent-level adjacency. Thus, applying the $\varepsilon$ -DP guarantee of $\mathcal{M}$ , we get

	$\displaystyle\Pr_{A\sim\mathcal{M}({\bm{u}}^{})}[A\text{ is not PROP}c\text{ for agent }i^{}\text{ w.r.t. }u^{}_{i^{}}]$
	$\displaystyle\geq e^{-\varepsilon}\cdot\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not PROP}c\text{ for agent }i^{}\text{ w.r.t. }u^{}_{i^{*}}]$
	$\displaystyle\geq(e^{-\varepsilon})/(8n).$

This completes the proof. ∎

3.2 Proof of Theorem 3.1

As in the proof of Theorem 3.2, we let $\zeta=0.01$ . If $m<100n$ , then $c=0$ and the theorem holds trivially even without the privacy requirement. Hence, we may assume that $m\geq 100n$ . We consider random utility functions ${\bm{u}}=(u_{i})_{i\in N}$ where each $u_{i}(j)$ is an indepedent $\operatorname{Ber}(1/2)$ random variable. For brevity, we will not repeatedly state this in the calculations below.

For an allocation $A$ and an agent $i\in N$ , we let $\operatorname{rank}(i;A)$ be the size of the set $\{j\in N\setminus\{i\}\mid|A_{j}|\geq|A_{i}|\}$ .

Lemma 3.4.

For $\zeta=0.01$ , let $c$ be as in Theorem 3.1 and $A$ be any allocation, and let $\ell\in N$ be such that $\operatorname{rank}(\ell;A)\geq(n-1)/2$ . Then, we have

\displaystyle\Pr_{{\bm{u}}}[A\text{ is not EF}c\text{ for agent }\ell]\geq 0.01.

Proof.

Without loss of generality, we may rename the agents so that agent $\ell$ in the lemma statement becomes agent $i$ and $|A_{1}|\geq\cdots\geq|A_{i}|>|A_{i+1}|\geq\cdots\geq|A_{n}|$ . We now have $\operatorname{rank}(i;A)=i-1\geq\lceil(n-1)/2\rceil$ .

We have

	$\displaystyle\Pr_{{\bm{u}}}[A\text{ is not EF}c\text{ for agent }i]$
	$\displaystyle\geq\Pr_{u_{i}}[u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle\qquad\cdot\Pr_{u_{i}}[A_{i}\text{ is not EF}c\text{ for agent }i\mid u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle\geq\frac{1}{2}\cdot\Pr_{u_{i}}[A_{i}\text{ is not EF}c\text{ for agent }i\mid u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle\geq\frac{1}{2}\cdot\Pr_{u_{i}}[\exists j<i,u_{i}(A_{j})>\|A_{i}\|/2+c\mid u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle=\frac{1}{2}\cdot\left(1-\prod_{j\in[i-1]}\Pr_{u_{i}}[u_{i}(A_{j})\leq\|A_{i}\|/2+c]\right)$

where the second inequality follows from the fact that $u_{i}(A_{i})$ is a sum of $|A_{i}|$ independent $\operatorname{Ber}(1/2)$ random variables and the last equality follows from independence.

We now consider two cases.

•

Case I: $|A_{i}|<m/(2n)$ . Since there are $m$ items and $n$ bundles, we have $|A_{1}|\geq m/n$ . Our assumption that $m\geq 100n$ and our choice of $c$ imply that $|A_{i}|/2+c\leq(|A_{1}|-1)/2$ . Hence, we have $\Pr[u_{i}(A_{1})\leq|A_{i}|/2+c]\leq 1/2$ . It follows that

	$\displaystyle\frac{1}{2}\cdot$	$\displaystyle\left(1-\prod_{j\in[i-1]}\Pr_{{\bm{u}}}[u_{i}(A_{j})\leq\|A_{i}\|/2+c]\right)$
		$\displaystyle\geq\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}.$

•

Case II: $|A_{i}|\geq m/(2n)$ . For any $j\in[i-1]$ , let $S_{j}\subseteq A_{j}$ be any subset of $A_{j}$ of size $|A_{i}|$ . Applying Lemma 2.13 with $\gamma=\min\{n,2^{m/(8n)}\}$ and $k=|A_{i}|$ yields

	$\displaystyle\Pr_{{\bm{u}}}$	$\displaystyle[u_{i}(A_{j})>\|A_{i}\|/2+c]$
		$\displaystyle\geq\Pr_{{\bm{u}}}[u_{i}(S_{j})>\|A_{i}\|/2+c]$
		$\displaystyle\geq\Pr_{{\bm{u}}}\left[u_{i}(S_{j})>\|A_{i}\|/2+0.1\sqrt{\|A_{i}\|\log\gamma}\right]$
		$\displaystyle\overset{\text{(\lx@cref{creftypecap~refnum}{lem:anti-concen})}}{\geq}0.1/\gamma\geq 0.1/n,$

where the second inequality follows from our choice of parameters $c,\gamma$ and the fact that $|A_{i}|\geq m/(2n)$ . Thus, we have

	$\displaystyle\Pr_{{\bm{u}}}$	$\displaystyle[A_{i}\text{ is not EF}c\text{ for agent }i]$
		$\displaystyle\geq\frac{1}{2}\cdot\left(1-\left(1-\frac{0.1}{n}\right)^{i-1}\right)$
		$\displaystyle\geq\frac{1}{2}\cdot\left(1-\left(1-\frac{0.1}{n}\right)^{\left\lceil\frac{n-1}{2}\right\rceil}\right)$
		$\displaystyle\geq\frac{1}{2}\cdot\left(1-e^{-\frac{0.1}{n}\cdot\left\lceil\frac{n-1}{2}\right\rceil}\right)$
		$\displaystyle\geq\frac{1}{2}\cdot\left(1-e^{-\frac{0.1}{3}}\right)\geq 0.01.$

Hence, in both cases, we have

\displaystyle\Pr_{{\bm{u}}}[A_{i}\text{ is not EF}c\text{ for agent }i]\geq 0.01,

which concludes our proof of the lemma. ∎

With Lemma 3.4 in hand, we can now prove Theorem 3.1 in a similar manner as Theorem 3.2.

Proof of Theorem 3.1.

Let $\zeta=0.01$ and let $\mathcal{M}$ be any agent-level $\varepsilon$ -DP algorithm. Consider the input utility functions ${\bm{u}}^{\prime}=(u^{\prime}_{1},\dots,u^{\prime}_{n})$ where the utility functions are all-zero, and consider the distribution $\mathcal{M}({\bm{u}}^{\prime})$ . Notice that, for any allocation $A$ , it holds that $\Pr_{i\in N}\left[\operatorname{rank}(i;A)\geq\frac{n-1}{2}\right]\geq 1/2$ . As a result, we have that $\Pr_{i\in N,A\sim\mathcal{M}({\bm{u}}^{\prime})}[\operatorname{rank}(i;A)\geq\frac{n-1}{2}]\geq 1/2$ . Thus, there exists $i^{*}\in N$ with the property that $\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}[\operatorname{rank}(i^{*};A)\geq\frac{n-1}{2}]\geq 1/2$ .

Applying Lemma 3.4, we get

	$\displaystyle\Pr_{{\bm{u}},A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not EF}c\text{ for agent }i^{*}]$
	$\displaystyle\geq\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}\left[\operatorname{rank}(i^{*};A)\geq\frac{n-1}{2}\right]$
	$\displaystyle\cdot\Pr_{{\bm{u}},A\sim\mathcal{M}({\bm{u}}^{\prime})}\bigg{[}A\text{ is not EF}c\text{ for }i^{}\,\bigg{\|}\operatorname{rank}(i^{};A)\geq\frac{n-1}{2}\bigg{]}$
	$\displaystyle\geq\frac{1}{2}\cdot\frac{1}{100}=\frac{1}{200}.$

Hence, there exists $u^{*}_{i^{*}}$ such that

\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not EF}c\text{ for agent }i^{*}\text{ w.r.t. }u^{*}_{i^{*}}]\geq\frac{1}{200}.

	$\displaystyle\Pr_{A\sim\mathcal{M}({\bm{u}}^{})}[A\text{ is not EF}c\text{ for agent }i^{}\text{ w.r.t. }u^{}_{i^{}}]$
	$\displaystyle\geq e^{-\varepsilon}\cdot\Pr_{A\sim\mathcal{M}({\bm{u}}^{\prime})}[A\text{ is not EF}c\text{ for agent }i^{}\text{ w.r.t. }u^{}_{i^{*}}]$
	$\displaystyle\geq\frac{e^{-\varepsilon}}{200}.$

This completes the proof. ∎

4 (Agent $\times$ Item)-Level DP

In this section, we turn our attention to (agent $\times$ item)-level DP, which is a more relaxed notion than agent-level DP. We explore both the possibilities (Section 4.1) and limits (Section 4.2) of private algorithms with respect to this notion.

4.1 Algorithms

In contrast to agent-level DP, we will show that $O_{\varepsilon,n}(\log m)$ upper bounds can be attained in the (agent $\times$ item)-level DP setting. Before we do so, let us first explain why straightforward approaches do not work. To this end, assume that utilities are additive and $u_{i}(j)\in[0,1]$ for all $i\in N,j\in M$ . One may want to estimate $u_{i}(S)$ for each $S$ using the Laplace mechanism. While the Laplace mechanism guarantees that the estimate has an expected additive error of $O(1/\varepsilon)$ , this is not useful for obtaining approximate envy-freeness or proportionality guarantees: it is possible that (almost) every good yields utility much less than $1$ . In this case, additive errors do not translate to any non-trivial EF $c$ or PROP $c$ guarantees. We will therefore develop different—and more robust—comparison methods, which ultimately allow us to overcome the aforementioned issue.

Approximate Envy-Freeness

Our main algorithmic result for approximate envy-freeness is stated below. Note that this result holds even for non-additive utility functions.

Theorem 4.1.

For any $\varepsilon>0$ and $\beta\in(0,1]$ , there exists an (agent $\times$ item)-level $\varepsilon$ -DP algorithm that, for any input monotone utility functions, outputs a connected EF $c$ allocation with probability at least $1-\beta$ , where $c=O\left(1+\frac{n\log(mn)+\log(1/\beta)}{\varepsilon}\right)$ .

The high-level idea of our algorithm is to apply the exponential mechanism (Theorem 2.11) to select an allocation among the $\leq(mn)^{n}$ connected allocations. This gives us an “error” in the score of $O_{\varepsilon}(\log((mn)^{n}))=O_{\varepsilon}(n\cdot\log(mn))$ . The question is how to set up the score so that (i) it has low sensitivity and (ii) such an error translates to an approximate envy-freeness guarantee. Our insight is to define the score based on the following modified utility function that “removes” a certain number of most valuable items.

Definition 4.2.

For ${\bm{u}}=(u_{1},\dots,u_{n})$ and $k\in\mathbb{N}\cup\{0\}$ , we define ${\bm{u}}^{-k}=(u^{-k}_{1},\dots,u^{-k}_{n})$ by

\displaystyle u^{-k}_{i}(S):=\min_{T\subseteq M,|T|\leq k}u_{i}(S\setminus T)

\displaystyle\forall i\in N,S\subseteq M.

It is clear that ${\bm{u}}^{-k}$ inherits the monotonicity of ${\bm{u}}$ . We next list some simple but useful properties of such utility functions. The first property, whose proof is trivial, relates Definition 4.2 to approximate envy-freeness.

Observation 4.3.

Let $k,d\in\mathbb{N}\cup\{0\}$ . Any allocation that is EF $d$ with respect to ${\bm{u}}^{-k}$ is EF $(d+k)$ with respect to ${\bm{u}}$ .

The second property is that the $d,k$ values are robust with respect to (agent $\times$ item)-level adjacency.

Lemma 4.4.

Let $k\in\mathbb{N},d\in\mathbb{N}\cup\{0\}$ , and ${\bm{u}},\tilde{{\bm{u}}}$ be any two (agent $\times$ item)-level adjacent inputs. If an allocation $A$ is EF $d$ with respect to ${\bm{u}}^{-k}$ , then it is EF $(d+2)$ with respect to $\tilde{{\bm{u}}}^{-(k-1)}$ .

Proof.

By definition of (agent $\times$ item)-level adjacency, there exist $i^{*}\in N,j^{*}\in M$ such that

•

$u_{i}=\tilde{u}_{i}$ for all $i\in N\setminus\{i^{*}\}$ , and
•

$u_{i}(S)=\tilde{u}_{i}(S)$ for all $S\subseteq M\setminus\{j^{*}\}$ .

Consider any $i,i^{\prime}\in N$ . Since $A$ is EF $d$ with respect to ${\bm{u}}^{-k}$ , we have

	$\displaystyle u^{-k}_{i}(A_{i})$	$\displaystyle\geq\min_{S\subseteq M,\|S\|\leq d}u^{-k}_{i}(A_{i^{\prime}}\setminus S)$
		$\displaystyle=\min_{T\subseteq M,\|T\|\leq d+k}u_{i}(A_{i^{\prime}}\setminus T).$		(2)

Furthermore, we have

$\displaystyle u^{-k}_{i}(A_{i})$	$\displaystyle=\min_{T\subseteq M,\|T\|\leq k}u_{i}(A_{i}\setminus T)$
	$\displaystyle\leq\min_{T\subseteq M,\|T\|\leq k-1}u_{i}(A_{i}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle=\min_{T\subseteq M,\|T\|\leq k-1}\tilde{u}_{i}(A_{i}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle\leq\min_{T\subseteq M,\|T\|\leq k-1}\tilde{u}_{i}(A_{i}\setminus T)=\tilde{u}^{-(k-1)}_{i}(A_{i}).$	(3)

Moreover,

$\displaystyle\min_{T\subseteq M,\|T\|\leq d+k}$	$\displaystyle u_{i}(A_{i^{\prime}}\setminus T)$
	$\displaystyle\geq\min_{T\subseteq M,\|T\|\leq d+k}u_{i}(A_{i^{\prime}}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle=\min_{T\subseteq M,\|T\|\leq d+k}\tilde{u}_{i}(A_{i^{\prime}}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle\geq\min_{T\subseteq M,\|T\|\leq d+k+1}\tilde{u}_{i}(A_{i^{\prime}}\setminus T)$
	$\displaystyle=\min_{S\subseteq M,\|S\|\leq d+2}\tilde{u}^{-(k-1)}_{i}(A_{i^{\prime}}\setminus S).$	(4)

Thus, we can conclude that

	$\displaystyle\tilde{u}^{-(k-1)}_{i}(A_{i})$	$\displaystyle\overset{\eqref{eq:remove-one-stable-selected}}{\geq}u^{-k}_{i}(A_{i})$
		$\displaystyle\overset{\eqref{eq:ef-condition}}{\geq}\min_{T\subseteq M,\|T\|\leq d+k}u_{i}(A_{i^{\prime}}\setminus T)$
		$\displaystyle\overset{\eqref{eq:remove-one-stable-not-selected}}{\geq}\min_{S\subseteq M,\|S\|\leq d+2}\tilde{u}^{-(k-1)}_{i}(A_{i^{\prime}}\setminus S).$

It follows that $A$ is EF $(d+2)$ with respect to $\tilde{{\bm{u}}}^{-(k-1)}$ . ∎

We can now define our scoring function.

Definition 4.5.

For an allocation $A$ , ${\bm{u}}=(u_{1},\dots,u_{n})$ , and $g\in\mathbb{N}$ , define

\operatorname{scr}^{g}_{A}({\bm{u}}):=-\min\{t\in[g]\mid A\text{ is EF}(2t)\text{ w.r.t. }{\bm{u}}^{-(g-t)}\}.

We let $\operatorname{scr}^{g}_{A}({\bm{u}})=-g$ if the set above is empty.

The following lemma shows that this scoring function has low sensitivity.

Lemma 4.6.

For any allocation $A$ and $g\in\mathbb{N}$ , $\Delta(\operatorname{scr}^{g}_{A})\leq 1$ .

Proof.

Let ${\bm{u}},\tilde{{\bm{u}}}$ be any pair of (agent $\times$ item)-level adjacent inputs. Assume without loss of generality that $\operatorname{scr}^{g}_{A}({\bm{u}})\geq\operatorname{scr}^{g}_{A}(\tilde{{\bm{u}}})$ . Let $t^{*}:=-\operatorname{scr}^{g}_{A}({\bm{u}})$ .

If $t^{*}=g$ , then $\operatorname{scr}^{g}_{A}(\tilde{{\bm{u}}})\leq\operatorname{scr}^{g}_{A}({\bm{u}})=-g$ , so $\operatorname{scr}^{g}_{A}(\tilde{{\bm{u}}})=-g$ . Otherwise, $t^{*}\leq g-1$ , and $A$ is EF $(2t^{*})$ with respect to ${\bm{u}}^{-(g-t^{*})}$ . Lemma 4.4 ensures that $A$ is EF $(2(t^{*}+1))$ with respect to $\tilde{{\bm{u}}}^{-(g-t^{*}-1)}$ . Thus, $\operatorname{scr}^{g}_{A}(\tilde{{\bm{u}}})\geq-(t^{*}+1)$ . Since $-t^{*}=\operatorname{scr}^{g}_{A}({\bm{u}})\geq\operatorname{scr}^{g}_{A}(\tilde{{\bm{u}}})$ , we have $|\operatorname{scr}^{g}_{A}({\bm{u}})-\operatorname{scr}^{g}_{A}(\tilde{{\bm{u}}})|\leq 1$ in both cases, completing the proof. ∎

With all the ingredients ready, we can prove Theorem 4.1 by applying the exponential mechanism with appropriate parameters (see Algorithm 1).

Algorithm 1 (Agent

\times

item)-level

\varepsilon

-DP algorithm for EF

c

Parameter: $\varepsilon>0,\beta\in(0,1]$

g\leftarrow 4\left\lceil 1+\frac{\log((mn)^{n}/\beta)}{\varepsilon}\right\rceil

2: return the allocation output by the

\varepsilon

-DP exponential mechanism using the scoring function

\operatorname{scr}^{g}_{A}

(Definition 4.5) with the candidate set

\mathcal{P}^{\mathrm{conn}}(m,n)

(Section 2.1).

Proof of Theorem 4.1.

Let $g=4\left\lceil 1+\frac{\log((mn)^{n}/\beta)}{\varepsilon}\right\rceil$ . We run the exponential mechanism using the scoring function $\operatorname{scr}^{g}_{A}$ with the candidate set $\mathcal{P}^{\mathrm{conn}}(m,n)$ . By Theorem 2.11, this is an $\varepsilon$ -DP algorithm that, for each ${\bm{u}}$ , with probability at least $1-\beta$ , outputs an allocation $A^{*}$ such that

\displaystyle\operatorname{scr}^{g}_{A^{*}}({\bm{u}})\geq\max_{A\in\mathcal{P}^{\mathrm{conn}}(m,n)}\operatorname{scr}^{g}_{A}({\bm{u}})-\frac{2\log\left(\frac{|\mathcal{P}^{\mathrm{conn}}(m,n)|}{\beta}\right)}{\varepsilon}.

Fix any ${\bm{u}}$ , and define $A^{*}$ as above. By Theorem 2.1, there exists a connected allocation $A^{\text{EF2}}$ that is EF2 with respect to ${\bm{u}}^{-(g-1)}$ . This means that $\operatorname{scr}^{g}_{A^{\text{EF2}}}=-1$ . Furthermore, we have¹³¹³13Indeed, from the set $M=\{1,2,\dots,m\}$ , we can allocate one “block” of items at a time starting from items with lower indices. There are at most $m$ possibilities for the size of the next block, this block can be allocated to one of the (at most $n$ ) remaining agents, and we allocate $n$ blocks in total, hence the bound $(mn)^{n}$ . $|\mathcal{P}^{\mathrm{conn}}(m,n)|\leq(mn)^{n}$ . Plugging these into the inequality above, we get

\displaystyle\operatorname{scr}^{g}_{A^{*}}({\bm{u}})\geq-1-\frac{2\log((mn)^{n}/\beta)}{\varepsilon}\geq-\frac{g}{2},

where the latter inequality follows from our choice of $g$ . Hence, $A^{*}$ is EF $(2c)$ with respect to ${\bm{u}}^{-(g-c)}$ for some $c\leq g/2$ . Invoking 4.3, we find that $A^{*}$ is EF $(g+c)$ , and therefore EF $(3g/2)$ , with respect to ${\bm{u}}$ . This concludes our proof. ∎

Approximate Proportionality

Next, we present an improved result for approximate proportionality, where the dependence on $n$ is reduced to $O(\log n)$ .

Theorem 4.7.

For any $\varepsilon>0$ and $\beta\in(0,1]$ , there exists an (agent $\times$ item)-level $\varepsilon$ -DP algorithm that, for any input additive utility functions, outputs a connected PROP $c$ allocation with probability at least $1-\beta$ , where $c=O\left(\log n+\frac{\log(mn/\beta)}{\varepsilon}\right)$ .

Our algorithm is based on the well-known “moving-knife” procedure from cake cutting (Dubins and Spanier 1961). A natural way to implement this idea in our setting is to place the items on a line, put a knife at the left end, and move it rightwards until some agent values the subset of items to the left of the knife at least $1/n$ of her value for the whole set of items. We give this subset to this agent, and proceed similarly with the remaining agents and items. To make this procedure DP, we can replace the check of whether each agent receives sufficiently high value with the SVT algorithm (Theorem 2.10), where the usual utility is modified similarly to Definition 4.5 to achieve low sensitivity. While this approach is feasible, it does not establish the bound we want: since the last agent has to participate in $n$ “rounds” of this protocol, the basic composition theorem (Theorem 2.5) implies that we can only allot a privacy budget of $\varepsilon/n$ in each round. This results in a guarantee of the form $c=O(\log m/(\varepsilon/n))=O((n\log m)/\varepsilon)$ , which does not distinctly improve upon the guarantee in Theorem 4.1.

To overcome this issue, notice that instead of targeting a single agent, we can continue moving our knife until at least $n/2$ agents value the subset of items to the left of the knife at least half of the entire set.¹⁴¹⁴14Even and Paz (1984) used a similar idea in cake cutting. This allows us to recurse on both sides, thereby reducing the number of rounds to $\log n$ . Hence, we may allot a privacy budget of $\varepsilon/\log n$ in each round. Unfortunately, this only results in a bound of the form $c=O(\log m/(\varepsilon/\log n))=O((\log n\log m)/\varepsilon)$ , which is still worse than what we claim in Theorem 4.7.

Our last observation is that we can afford to make more mistakes in earlier rounds: for example, in the first round, we would be fine with making an “error” of roughly $O(n)$ in the knife position because the subsets on both sides will be subdivided to $\Omega(n)$ parts later. As a result, our strategy is to allot less privacy budget in earlier rounds and more in later rounds. By letting the privacy budgets form a geometric sequence, we can achieve our claimed $O(\log(mn)/\varepsilon)$ bound.

Proof of Theorem 4.7.

The proof follows the overview outlined above. The statement holds trivially if $\beta=1$ , so assume that $\beta<1$ . For convenience, given any positive integers $\ell\leq r$ , we write $[\ell,r]$ as a shorthand for $\{\ell,\ell+1,\dots,r\}$ .

Let $\varepsilon_{1},\dots,\varepsilon_{\lceil\log_{2}n\rceil},g_{1},\dots,g_{\lceil\log_{2}n\rceil}$ be defined as $\varepsilon_{b}=\frac{\varepsilon}{2\cdot(1.5^{b})}$ and $g_{b}=8\lceil\upsilon\cdot\log(mn/\beta)/\varepsilon_{b}\rceil$ , where $\upsilon$ is defined as in Theorem 2.10. Our algorithm, DPMovingKnife, is presented as Algorithm 2. The final algorithm is an instantiation of Algorithm 2 with $\mathcal{I}=N$ and $(\ell,r)=(1,m)$ .

Algorithm 2 DPMovingKnife

Input: A set $\mathcal{I}\subseteq N$ of agents, a set $[\ell,r]\subseteq M$ of items
Parameter: $\varepsilon_{1},\dots,\varepsilon_{\lceil\log n\rceil}>0,g_{1},\dots,g_{\lceil\log n\rceil}\in\mathbb{N}$
Output: A partial allocation $(A_{i})_{i\in\mathcal{I}}$ of $[\ell,r]$

1: if

|\mathcal{I}|=1

then

2: return

(A_{i}=[\ell,r])

for

i\in\mathcal{I}

3: end if

b\leftarrow\lceil\log_{2}|\mathcal{I}|\rceil

n^{R}\leftarrow\lfloor|\mathcal{I}|/2\rfloor

n^{L}\leftarrow|\mathcal{I}|-n^{R}

7: for each agent

i\in\mathcal{I}

8: for each

h\in[\ell,r]

	$\displaystyle T^{i,\ell,r}_{h}({\bm{u}})\leftarrow\bigg{\{}$	$\displaystyle t\in[g_{b}]\,\bigg{\|}\,\frac{1}{n^{L}}\cdot u^{-(g_{b}+t)}_{i}([\ell,h])$
		$\displaystyle\geq\frac{1}{n^{R}}\cdot u^{-(g_{b}-t)}_{i}([h+1,r])\bigg{\}}$

10:

\displaystyle f^{i,\ell,r}_{h}({\bm{u}})\leftarrow\begin{cases}\max(T^{i,\ell,r}_{h}({\bm{u}}))&\text{ if }T^{i,\ell,r}_{h}({\bm{u}})\neq\emptyset;\\ 0&\text{ otherwise}\end{cases}

11: end for

12:

h_{i}\leftarrow

output from the

\varepsilon_{b}

-DP SVT algorithm (Theorem 2.10) with

\tau=g_{b}/2

f^{i,\ell,r}_{\ell},\dots,f^{i,\ell,r}_{r}

13: end for

14:

h_{z_{1}}\leq h_{z_{2}}\leq\cdots\leq h_{z_{|\mathcal{I}|}}\leftarrow

sorted list of

h_{i}

’s

15:

A^{L}\leftarrow\textsc{DPMovingKnife}(\{z_{1},\dots,z_{n^{L}}\},\{\ell,\dots,h_{z_{n^{L}}}\})

16:

A^{R}\leftarrow\textsc{DPMovingKnife}(\{z_{n^{L}+1},\dots,z_{|\mathcal{I}|}\},\{h_{z_{n^{L}}}+1,\dots,r\})

17: return the allocation resulting from combining

A^{L}

and

A^{R}

Before we prove the utility and privacy guarantees of our algorithm, let us prove the following auxiliary lemma which states that the sensitivity of $f^{i,\ell,r}_{h}$ is small. The proof is similar to that of Lemma 4.6.

Lemma 4.8.

For all $\ell,r,h\in M$ and $i\in N$ , it holds that $\Delta(f^{i,\ell,r}_{h})\leq 1$ .

Proof.

Let ${\bm{u}},\tilde{{\bm{u}}}$ be any pair of (agent $\times$ item)-level adjacent inputs. Assume without loss of generality that $f^{i,\ell,r}_{h}({\bm{u}})\geq f^{i,\ell,r}_{h}(\tilde{{\bm{u}}})$ . Let $t^{*}:=f^{i,\ell,r}_{h}({\bm{u}})$ .

If $t^{*}=0$ , then $f^{i,\ell,r}_{h}(\tilde{{\bm{u}}})$ must also be equal to 0.

Otherwise, $t^{*}>0$ , and we have

\displaystyle\frac{1}{n^{L}}\cdot u^{-(g_{b}+t^{*})}_{i}([\ell,h])\geq\frac{1}{n^{R}}\cdot u^{-(g_{b}-t^{*})}_{i}([h+1,r]).

(5)

From this, we can derive

	$\displaystyle\frac{1}{n^{L}}\cdot\tilde{u}^{-(g_{b}+t^{*}-1)}_{i}([\ell,h])$	$\displaystyle\geq\frac{1}{n^{L}}\cdot u^{-(g_{b}+t^{*})}_{i}([\ell,h])$
		$\displaystyle\overset{\eqref{eq:f-inequality}}{\geq}\frac{1}{n^{R}}\cdot u^{-(g_{b}-t^{*})}_{i}([h+1,r])$
		$\displaystyle\geq\frac{1}{n^{R}}\cdot\tilde{u}^{-(g_{b}-t^{*}+1)}_{i}([h+1,r]),$

where the first and last inequalities follow from the fact that ${\bm{u}},\tilde{{\bm{u}}}$ are (agent $\times$ item)-level adjacent inputs. Thus, it must be that $f^{i,\ell,r}_{h}(\tilde{{\bm{u}}})\geq t^{*}-1$ .

It follows that $|f^{i,\ell,r}_{h}(u)-f^{i,\ell,r}_{h}(\tilde{{\bm{u}}})|\leq 1$ in both cases, completing the proof. ∎

We are now ready to establish the privacy and utility guarantees of the algorithm, starting with the former.

Privacy Analysis.

We will prove by induction that $\textsc{DPMovingKnife}(N,M)$ is $\varepsilon$ -DP. Specifically, we claim that $\textsc{DPMovingKnife}(\mathcal{I},[\ell,r])$ is $\left(\sum_{b=1}^{\lceil\log_{2}|\mathcal{I}|\rceil}\varepsilon_{b}\right)$ -DP for any $\mathcal{I}\in N$ and $[\ell,r]\subseteq M$ . We prove this claim by (strong) induction on the size of $\mathcal{I}$ . The base case $|\mathcal{I}|=1$ is trivial.

For $|\mathcal{I}|>1$ , let us divide the algorithm into two stages: (i) computation of $h_{z_{1}},\dots,h_{z_{|\mathcal{I}|}}$ and (ii) computation of $A^{L}$ and $A^{R}$ given $h_{z_{1}},\dots,h_{z_{|\mathcal{I}|}}$ . The privacy for each stage can be analyzed as follows:

•

Stage (i). From Lemma 4.8 and Theorem 2.10, each application of SVT is $(\varepsilon_{\lceil\log_{2}|\mathcal{I}|\rceil})$ -DP. Moreover, since SVT is applied on each $u_{i}$ separately, parallel composition (Theorem 2.7) implies¹⁵¹⁵15More specifically, we may apply Theorem 2.7 with $\Gamma:\mathcal{X}\to(\mathcal{X})^{\mathcal{I}}$ where $\Gamma({\bm{u}})_{i}=u_{i}$ , and $\mathcal{M}$ being the SVT algorithm. that the entire computation of $(h_{i})_{i\in\mathcal{I}}$ is also $(\varepsilon_{\lceil\log_{2}|\mathcal{I}|\rceil})$ -DP. Finally, $h_{z_{1}},\dots,h_{z_{|\mathcal{I}|}}$ is simply a post-processing of $(h_{i})_{i\in\mathcal{I}}$ , so 2.6 ensures that the entire Stage (i) is $(\varepsilon_{\lceil\log_{2}|\mathcal{I}|\rceil})$ -DP.
•

Stage (ii). The inductive hypothesis asserts that each recursive call to DPMovingKnife is $\left(\sum_{b=1}^{\lceil\log_{2}|\mathcal{I}|\rceil-1}\varepsilon_{b}\right)$ -DP. Furthermore, since each $u_{i}$ is used in only one recursive call, we can apply¹⁶¹⁶16More specifically, we let $\Gamma:\mathcal{X}\to(\mathcal{X})^{2}$ where $\Gamma({\bm{u}})_{1}=(u_{z_{1}},\dots,u_{z_{n^{L}}})$ and $\Gamma({\bm{u}})_{2}=(u_{z_{n^{L}+1}},\dots,u_{z_{|\mathcal{I}|}})$ , and $\mathcal{M}$ being the DPMovingKnife algorithm. parallel composition (Theorem 2.7), which ensures that the entire Stage (ii) is also $\left(\sum_{b=1}^{\lceil\log_{2}|\mathcal{I}|\rceil-1}\varepsilon_{b}\right)$ -DP.

Therefore, applying basic composition (Theorem 2.5) across the two stages yields that the entire algorithm is $\left(\sum_{b=1}^{\lceil\log_{2}|\mathcal{I}|\rceil}\varepsilon_{b}\right)$ -DP. Since $\sum_{b=1}^{\lceil\log_{2}n\rceil}\varepsilon_{b}\leq\sum_{b=1}^{\infty}\varepsilon_{b}=\varepsilon$ , it follows that the entire algorithm when called with $\mathcal{I}=N$ is $\varepsilon$ -DP, as desired.

Utility Analysis.

We next analyze the utility of the algorithm. To this end, for each agent $i$ , let $\ell^{i}_{1},r^{i}_{1},\dots,\ell^{i}_{w_{i}},r^{i}_{w_{i}}$ be the values of $\ell,r$ with which the algorithm is invoked for a set $\mathcal{I}$ containing $i$ . Note that $\ell^{i}_{1}=1$ , $r^{i}_{1}=m$ , and $w_{i}\leq\lceil\log_{2}n\rceil+1$ . Similarly, let $h^{i}_{1},\dots,h^{i}_{w_{i}-1}$ denote the values of $h_{i}$ output by SVT for agent $i$ in each of the calls except the last one, and $n^{i}_{1},\dots,n^{i}_{w_{i}}$ denote the sizes of $\mathcal{I}$ in each invocation. (Note that we must have $n^{i}_{w_{i}}=1$ .) Furthermore, for each $q\in[w_{i}-1]$ , we let $R^{i}_{q}:=[\ell^{i}_{q},r^{i}_{q}]\setminus[\ell^{i}_{q+1},r^{i}_{q+1}]$ denote the set of items removed in the $q$ -th iteration, and let $u^{\operatorname{top-k}}_{i}(R^{i}_{q}):=\max_{S\subseteq R^{i}_{q},|S|\leq k}u_{i}(S)$ for any non-negative integer $k$ .

Consider any $i\in N$ and $q\in[w_{i}-1]$ . Let $b_{q}=\lceil\log_{2}n_{q}^{i}\rceil$ Notice that $f^{i,\ell,r}_{r}({\bm{u}})=g_{b_{q}}\geq g_{b_{q}}/2$ . Thus, by the guarantee of SVT (Theorem 2.10), we have that with probability at least $1-\beta/n^{2}$ , the following holds for each $i\in N$ and $q\in[w_{i}-1]$ :

	$\displaystyle f^{i,\ell,r}_{h^{i}_{q}}({\bm{u}})$	$\displaystyle\geq\frac{g_{b_{q}}}{2}-\upsilon\cdot\frac{\log(mn^{2}/\beta)}{\varepsilon_{b_{q}}}$
		$\displaystyle>\frac{g_{b_{q}}}{2}-2\upsilon\cdot\frac{\log(mn/\beta)}{\varepsilon_{b_{q}}}\geq\frac{g_{b_{q}}}{4}$		(6)

and

	$\displaystyle f^{i,\ell,r}_{h^{\prime}}({\bm{u}})$	$\displaystyle\leq\frac{g_{b_{q}}}{2}+\upsilon\cdot\frac{\log(mn^{2}/\beta)}{\varepsilon_{b_{q}}}$
		$\displaystyle<\frac{g_{b_{q}}}{2}+2\upsilon\cdot\frac{\log(mn/\beta)}{\varepsilon_{b_{q}}}\leq\frac{3g_{b_{q}}}{4}$		(7)

for all $h^{\prime}<h^{i}_{q}$ . Therefore, the union bound implies that, with probability at least $1-\beta$ , both (4.1) and (4.1) hold for all $i\in N$ and $q\in[w_{i}-1]$ simultaneously. We will show that, when this occurs, the output allocation is PROP $c$ for the value of $c$ in the theorem statement.

First, let us fix a pair $i\in N$ and $q\in[w_{i}-1]$ , and consider the $q$ -th time DPMovingKnife is called with $i\in\mathcal{I}$ . We will show that

		$\displaystyle u_{i}([\ell^{i}_{q+1},r^{i}_{q+1}])$
		$\displaystyle\geq\frac{n^{i}_{q+1}}{n^{i}_{q}}\left(u_{i}([\ell^{i}_{q},r^{i}_{q}])-u_{i}^{\operatorname{top-}(2g_{b_{q}})}(R^{i}_{q})\right).$		(8)

To do so, consider two cases, based on whether $i$ is recursed on the left subinstance¹⁷¹⁷17Note that all unspecified variables are for the run of the algorithm as specified above. (i.e., $i\in\{z_{1},\dots,z_{n^{L}}\}$ ) or on the right subinstance (i.e., $i\in\{z_{n^{L}+1},\dots,z_{n^{i}_{q}}\}$ ).

•

Case I: $i\in\{z_{1},\dots,z_{n^{L}}\}$ . In this case, we have

	$\displaystyle u_{i}([\ell^{i}_{q+1},r^{i}_{q+1}])$	$\displaystyle=u_{i}([\ell,h_{z_{n^{L}}}])$
		$\displaystyle\geq u_{i}([\ell,h^{i}_{q}])$
		$\displaystyle\overset{\eqref{eq:svt-above}}{\geq}\frac{n^{L}}{n^{R}}\cdot u_{i}^{-3g_{b_{q}}/4}([h^{i}_{q}+1,r])$
		$\displaystyle\geq\frac{n^{L}}{n^{R}}\cdot u_{i}^{-3g_{b_{q}}/4}([h_{z_{n^{L}}}+1,r]),$

where for the second inequality we apply (4.1) on the definition of $f^{i,\ell,r}_{h^{i}_{q}}$ with $t\geq g_{b_{q}}/4$ . Therefore, we have

	$\displaystyle u_{i}([\ell^{i}_{q+1},r^{i}_{q+1}])$
	$\displaystyle\geq\frac{n^{L}}{\|\mathcal{I}\|}u_{i}([\ell,h_{z_{n^{L}}}])$
	$\displaystyle\qquad+\frac{n^{R}}{\|\mathcal{I}\|}\cdot\frac{n^{L}}{n^{R}}\cdot u_{i}^{-3g_{b_{q}}/4}([h_{z_{n^{L}}}+1,r])$
	$\displaystyle=\frac{n^{L}}{\|\mathcal{I}\|}\bigg{(}u_{i}([\ell,h_{z_{n^{L}}}])+u_{i}^{-3g_{b_{q}}/4}([h_{z_{n^{L}}}+1,r])\bigg{)}$
	$\displaystyle=\frac{n^{L}}{\|\mathcal{I}\|}\bigg{(}u_{i}([\ell,r])-u_{i}^{\operatorname{top-}(3g_{b_{q}}/4)}([h_{z_{n^{L}}}+1,r])\bigg{)}$
	$\displaystyle=\frac{n^{i}_{q+1}}{n^{i}_{q}}\left(u_{i}([\ell^{i}_{q},r^{i}_{q}])-u_{i}^{\operatorname{top-}(3g_{b_{q}}/4)}(R^{i}_{q})\right)$
	$\displaystyle\geq\frac{n^{i}_{q+1}}{n^{i}_{q}}\left(u_{i}([\ell^{i}_{q},r^{i}_{q}])-u_{i}^{\operatorname{top-}(2g_{b_{q}})}(R^{i}_{q})\right).$

•

Case II: $i\in\{z_{n^{L}+1},\dots,z_{n^{i}_{q}}\}$ . In this case, we have

	$\displaystyle u_{i}([\ell^{i}_{q+1},r^{i}_{q+1}])$	$\displaystyle=u_{i}([h_{z_{n^{L}}}+1,r])$
		$\displaystyle\geq u_{i}([h^{i}_{q}+1,r])$
		$\displaystyle\geq u^{-1}_{i}([h^{i}_{q},r])$
		$\displaystyle\overset{\eqref{eq:svt-below}}{>}\frac{n^{R}}{n^{L}}\cdot u_{i}^{-7g_{b_{q}}/4}([\ell,h^{i}_{q}-1])$
		$\displaystyle\geq\frac{n^{R}}{n^{L}}\cdot u_{i}^{-(7g_{b_{q}}/4+1)}([\ell,h^{i}_{q}])$
		$\displaystyle\geq\frac{n^{R}}{n^{L}}\cdot u_{i}^{-(7g_{b_{q}}/4+1)}([\ell,h_{z_{n^{L}}}])$
		$\displaystyle\geq\frac{n^{R}}{n^{L}}\cdot u_{i}^{-2g_{b_{q}}}([\ell,h_{z_{n^{L}}}]),$

where the third inequality follows from applying (4.1) with $h^{\prime}=h^{i}_{q}-1$ and $t=3g_{b_{q}}/4$ in the definition of $f^{i,\ell,r}_{h^{i}_{q}}$ .

Therefore, we have

	$\displaystyle u_{i}([\ell^{i}_{q+1},r^{i}_{q+1}])$
	$\displaystyle\geq\frac{n^{L}}{\|\mathcal{I}\|}\cdot\frac{n^{R}}{n^{L}}\cdot u_{i}^{-2g_{b_{q}}}([\ell,h_{z_{n^{L}}}])$
	$\displaystyle\qquad+\frac{n^{R}}{\|\mathcal{I}\|}\cdot u_{i}([h_{z_{n^{L}}}+1,r])$
	$\displaystyle=\frac{n^{R}}{\|\mathcal{I}\|}\bigg{(}u_{i}^{-2g_{b_{q}}}([\ell,h_{z_{n^{L}}}])+u_{i}([h_{z_{n^{L}}}+1,r])\bigg{)}$
	$\displaystyle=\frac{n^{R}}{\|\mathcal{I}\|}\left(u_{i}([\ell,r])-u_{i}^{\operatorname{top-}(2g_{b_{q}})}([\ell,h_{z_{n^{L}}}])\right)$
	$\displaystyle=\frac{n^{i}_{q+1}}{n^{i}_{q}}\left(u_{i}([\ell^{i}_{q},r^{i}_{q}])-u_{i}^{\operatorname{top-}(2g_{b_{q}})}(R^{i}_{q})\right).$

Thus, (4.1) holds in both cases.

Let $A=(A_{1},\dots,A_{n})$ be the allocation returned by the algorithm. For each $i\in N$ , by repeatedly applying (4.1), we get

	$\displaystyle u_{i}(A_{i})$
	$\displaystyle=u_{i}([\ell^{i}_{w_{i}},r^{i}_{w_{i}}])$
	$\displaystyle\overset{\eqref{eq:one-step-moving-knife}}{\geq}\frac{1}{n^{i}_{w_{i}-1}}\bigg{(}u_{i}([\ell^{i}_{w_{i}-1},r^{i}_{w_{i}-1}])-u_{i}^{\operatorname{top-}(2g_{b_{w_{i}-1}})}(R^{i}_{w_{i}-1})\bigg{)}$
	$\displaystyle\overset{\eqref{eq:one-step-moving-knife}}{\geq}\frac{1}{n^{i}_{w_{i}-2}}\bigg{(}u_{i}([\ell^{i}_{w_{i}-2},r^{i}_{w_{i}-2}])-u_{i}^{\operatorname{top-}(2g_{b_{w_{i}-2}})}(R^{i}_{w_{i}-2})\bigg{)}$
	$\displaystyle\qquad-\frac{1}{n^{i}_{w_{i}-1}}\cdot u_{i}^{\operatorname{top-}(2g_{b_{w_{i}-1}})}(R^{i}_{w_{i}-1})$
	$\displaystyle\overset{\eqref{eq:one-step-moving-knife}}{\geq}\cdots$
	$\displaystyle\overset{\eqref{eq:one-step-moving-knife}}{\geq}\frac{1}{n^{i}_{1}}\cdot u_{i}([\ell^{i}_{1},r^{i}_{1}])-\sum_{q\in[w_{i}-1]}\frac{1}{n^{i}_{q}}\cdot u_{i}^{\operatorname{top-}(2g_{b_{q}})}(R^{i}_{q})$
	$\displaystyle=\frac{1}{n}\cdot u_{i}(M)-\sum_{q\in[w_{i}-1]}\frac{1}{n^{i}_{q}}\cdot u_{i}^{\operatorname{top-}(2g_{b_{q}})}(R^{i}_{q})$
	$\displaystyle\geq\frac{1}{n}\cdot u_{i}(M)-\sum_{q\in[w_{i}-1]}u_{i}^{\operatorname{top-}(\lceil 2g_{b_{q}}/n^{i}_{q}\rceil)}(R^{i}_{q})$
	$\displaystyle\geq\frac{1}{n}\cdot u_{i}(M)-u_{i}^{\operatorname{top-}\left(\sum_{q\in[w_{i}-1]}\lceil 2g_{b_{q}}/n^{i}_{q}\rceil\right)}\left(\bigcup_{q\in[w_{i}-1]}R^{i}_{q}\right)$
	$\displaystyle=\frac{1}{n}\cdot u_{i}(M)-u_{i}^{\operatorname{top-}\left(\sum_{q\in[w_{i}-1]}\lceil 2g_{b_{q}}/n^{i}_{q}\rceil\right)}\left(M\setminus A_{i}\right),$

where the last inequality follows from the fact that $R^{i}_{1},\dots,R^{i}_{w_{i}-1}$ are disjoint.

Now, we can bound the term $\sum_{q\in[w_{i}-1]}\lceil 2g_{b_{q}}/n^{i}_{q}\rceil$ as follows:

	$\displaystyle\sum_{q\in[w_{i}-1]}\left\lceil\frac{2g_{b_{q}}}{n^{i}_{q}}\right\rceil$
	$\displaystyle\leq\sum_{q\in[w_{i}-1]}\left(\frac{2g_{b_{q}}}{n^{i}_{q}}+1\right)$
	$\displaystyle\leq(w_{i}-1)+\sum_{q\in[w_{i}-1]}O\left(\frac{\log(mn/\beta)/\varepsilon_{b_{q}}+1}{n^{i}_{q}}\right)$
	$\displaystyle\leq O(\log n)+\sum_{q\in[w_{i}-1]}O\left(\frac{\log(mn/\beta)\cdot 1.5^{b_{q}}/\varepsilon+1}{2^{b_{q}}}\right)$
	$\displaystyle=O(\log n)+\sum_{q\in[w_{i}-1]}O\left(\log(mn/\beta)/\varepsilon\right)\cdot(0.75)^{b_{q}}$
	$\displaystyle\leq O(\log n)+O\left(\log(mn/\beta)/\varepsilon)\right),$

where the last inequality follows from the fact that the $b_{q}$ ’s are different for different values of $q\in[w_{i}-1]$ .

Putting the previous two bounds together, we can conclude that the allocation $A$ is PROP $c$ for $c=O(\log n+\log(mn/\beta)/\varepsilon)$ , as desired. ∎

4.2 Lower Bounds

Next, we prove lower bounds for (agent $\times$ item)-level DP via the packing method (Hardt and Talwar 2010). This involves constructing inputs that are close to one another (with respect to the corresponding adjacency notion) such that the acceptable solutions (i.e., EF $c$ or PROP $c$ allocations) are different for different inputs. The DP requirement can then be used to rule out the existence of algorithms with strong utility guarantees. We reiterate that our lower bounds hold only against connected allocations. In our constructions, we design the utility functions so that each input forces us to pick particular positions to cut in order to get an EF $c$ or PROP $c$ allocation. We start with the proof for envy-freeness.

Theorem 4.9.

There exists $\zeta>0$ such that, for any $\varepsilon\in(0,1]$ , there is no $\varepsilon$ -DP algorithm that, for any input binary additive utility functions, outputs a connected EF $c$ allocation with probability at least $0.5$ , where $c=\left\lfloor\zeta\cdot\min\left\{\frac{\log m}{\varepsilon},\frac{m}{n},\sqrt{m}\right\}\right\rfloor$ .

Proof.

Let $\zeta=0.01$ , $c$ be as in the theorem statement, and $T=\lfloor m/(4c+4)\rfloor$ . We may assume that $c\geq 1$ , as otherwise the theorem holds trivially even without the privacy requirement. Consider the following utility functions.

•
Let ${\bm{u}}^{\prime}=(u^{\prime}_{1},\dots,u^{\prime}_{n})$ denote the binary additive utility functions defined as follows:
- –
  
  $u^{\prime}_{1}$ and $u^{\prime}_{2}$ are all-zero utility functions.
- –
  
  For all $i\in\{3,\dots,n\}$ and $j\in M$ , let
  
  $\displaystyle u^{\prime}_{i}(j)=\begin{cases}1&\text{ if }j\geq m-(c+1)(n-2);\\ 0&\text{ otherwise.}\end{cases}$

•

For every $t\in[T]$ , let ${\bm{u}}^{t}=(u_{1}^{t},\dots,u_{n}^{t})$ denote the binary additive utility functions defined as follows:

–

$u^{t}_{1}$ and $u^{t}_{2}$ are defined as follows:

\displaystyle u^{t}_{1}(j)=u^{t}_{2}(j)=\begin{cases}1&\text{ if }\left\lfloor\frac{j-1}{2c+1}\right\rfloor=t-1;\\ 0&\text{ otherwise,}\end{cases}

for all $j\in M$ .

–

For all $i\in\{3,\dots,n\}$ , $u^{t}_{i}$ is exactly the same as $u^{\prime}_{i}$ defined earlier.

Suppose for contradiction that there is an $\varepsilon$ -DP algorithm $\mathcal{M}$ that, with probability at least $0.5$ , outputs a connected allocation that is EF $c$ for its input utility functions. For each $t\in[T]$ , let $\mathcal{A}^{t}$ denote the set of allocations that are EF $c$ for ${\bm{u}}^{t}$ . The assumption on $\mathcal{M}$ can be written as

\displaystyle\Pr[\mathcal{M}({\bm{u}}^{t})\in\mathcal{A}^{t}]\geq 0.5.

(9)

Let $\sim$ denote the (agent $\times$ item)-level adjacency relation. One can check that ${\bm{u}}^{\prime}\sim_{4c+2}{\bm{u}}^{t}$ for all $t\in[T]$ . Using this fact together with group DP (Lemma 2.8), we have

	$\displaystyle\Pr[\mathcal{M}({\bm{u}}^{\prime})\in\mathcal{A}^{t}]$	$\displaystyle\geq e^{-\varepsilon(4c+2)}\cdot\Pr[\mathcal{M}({\bm{u}}^{t})\in\mathcal{A}^{t}]$
		$\displaystyle\overset{\eqref{eq:utility-ef-lb}}{\geq}0.5\cdot e^{-\varepsilon(4c+2)}.$		(10)

Lemma 4.10.

$\mathcal{A}^{1},\dots,\mathcal{A}^{T}$ are disjoint.

Proof.

Suppose for contradiction that $\mathcal{A}^{t}$ and $\mathcal{A}^{t^{\prime}}$ overlap for some $t<t^{\prime}$ . Let $A$ be an allocation that is contained in both $\mathcal{A}^{t}$ and $\mathcal{A}^{t^{\prime}}$ . Observe that $A$ must satisfy the following:

•

There must be at least $n-3$ cuts between item $m-(c+1)(n-2)$ and item $m$ . (Otherwise, the allocation cannot be EF $c$ for at least one of agents $3,\dots,n$ .)
•

There must be a cut between item $(2c+1)(t-1)+1$ and item $(2c+1)t$ . (Otherwise, the allocation cannot be EF $c$ for either agent $1$ or $2$ in ${\bm{u}}^{t}$ .)
•

There must be a cut between item $(2c+1)(t^{\prime}-1)+1$ and item $(2c+1)t^{\prime}$ . (Otherwise, the allocation cannot be EF $c$ for either agent $1$ or $2$ in ${\bm{u}}^{t^{\prime}}$ .)

By our parameter selection, we have

	$\displaystyle\max\{(2c+1)t,(2c+1)t^{\prime}\}$
	$\displaystyle\leq(2c+1)T\leq m/2<m-2cn\leq m-(c+1)(n-2).$

This implies that the intervals of items discussed above are pairwise disjoint, and therefore the cuts must be distinct, i.e., those $n-1$ cuts are all the cuts in $A$ . Now, consider the leftmost interval of $A$ . The cut for this interval must be to the left of item $(2c+1)t$ . Suppose that the interval is assigned to agent $i$ . We consider the following two cases.

•

Case I: $i\in\{3,\dots,n\}$ . In this case, agent $i$ has value $0$ for her own bundle. Furthermore, since there are only $n-3$ cuts between item $m-(c+1)(n-2)$ and item $m$ , at least one other bundle has at least $c+1$ items valued $1$ by agent $i$ . As such, $A$ cannot be EF $c$ for agent $i$ .
•

Case II: $i\in\{1,2\}$ . In ${\bm{u}}^{t^{\prime}}$ , agent $i$ values her own bundle zero. Furthermore, since there is just one cut between item $(2c+1)(t^{\prime}-1)+1$ and item $(2c+1)t^{\prime}$ , at least one other bundle has at least $c+1$ items valued $1$ by agent $i$ . As such, the allocation cannot be EF $c$ for agent $i$ .

In both cases, $A$ cannot be EF $c$ for both ${\bm{u}}^{t}$ and ${\bm{u}}^{t^{\prime}}$ simultaneously, a contradiction. This establishes Lemma 4.10. ∎

Lemma 4.10 implies that

	$\displaystyle 1$	$\displaystyle\geq\sum_{t\in[T]}\Pr[\mathcal{M}({\bm{u}}^{\prime})\in\mathcal{A}^{t}]$
		$\displaystyle\overset{\eqref{eq:group-dp-application}}{\geq}0.5\cdot e^{-\varepsilon(4c+2)}\cdot T$
		$\displaystyle\geq 0.5\cdot e^{-6c\varepsilon}\cdot\left\lfloor\frac{m}{8c}\right\rfloor$
		$\displaystyle\geq 0.5\cdot e^{-0.06\log m}\cdot\lfloor 10\sqrt{m}\rfloor$
		$\displaystyle\geq(0.5/\sqrt{m})\cdot(5\sqrt{m})>1,$

where the third and fourth inequalities follow from our choice of parameters $c,T$ and the assumption that $c\geq 1$ . This is a contradiction which establishes Theorem 4.9. ∎

For proportionality, we obtain a slightly weaker bound where the $\log m$ term is replaced by $\log(m/n)/n$ . The proof is similar to that of Theorem 4.9.

Theorem 4.11.

There exists a constant $\zeta>0$ such that, for any $\varepsilon\in(0,1]$ , there is no $\varepsilon$ -DP algorithm that, for any input binary additive utility functions, outputs a connected PROP $c$ allocation with probability at least $0.5$ , where $c=\left\lfloor\zeta\cdot\min\left\{\frac{\log(m/n)}{\varepsilon n},\frac{m}{n},\sqrt{\frac{m}{n}}\right\}\right\rfloor$ .

Proof.

Let $\zeta=0.01$ , $c$ be as in the theorem statement, and $T=\lfloor m/(2nc+2)\rfloor$ . We may assume that $c\geq 1$ , as otherwise the theorem holds trivially even without the privacy requirement. Consider the following utility functions.

•
Let ${\bm{u}}^{\prime}=(u^{\prime}_{1},\dots,u^{\prime}_{n})$ denote the binary additive utility functions defined as follows:
- –
  
  $u^{\prime}_{1}$ and $u^{\prime}_{2}$ are all-zero utility functions.
- –
  
  For all $i\in\{3,\dots,n\}$ and $j\in M$ , let
  
  $\displaystyle u^{\prime}_{i}(j)=\begin{cases}1&\text{ if }j\geq m-cn;\\ 0&\text{ otherwise.}\end{cases}$

•

For every $t\in[T]$ , let ${\bm{u}}^{t}=(u_{1}^{t},\dots,u_{n}^{t})$ denote the binary additive utility functions defined as follows:

–

$u^{t}_{1}$ and $u^{t}_{2}$ are defined as follows:

\displaystyle u^{t}_{1}(j)=u^{t}_{2}(j)=\begin{cases}1&\text{ if }\left\lfloor\frac{j-1}{nc+1}\right\rfloor=t-1;\\ 0&\text{ otherwise,}\end{cases}

for all $j\in M$ .

–

For all $i\in\{3,\dots,n\}$ , $u^{t}_{i}$ is exactly the same as $u^{\prime}_{i}$ defined earlier.

Note that every agent values exactly $cn+1$ items, so each agent needs at least one item that she values in order for PROP $c$ to be satisfied.

Suppose for contradiction that there is an $\varepsilon$ -DP algorithm $\mathcal{M}$ that, with probability at least $0.5$ , outputs a connected allocation that is PROP $c$ for its input utility functions. For each $t\in[T]$ , let $\mathcal{A}^{t}$ denote the set of allocations that are PROP $c$ for ${\bm{u}}^{t}$ . The assumption on $\mathcal{M}$ can be written as

\displaystyle\Pr[\mathcal{M}({\bm{u}}^{t})\in\mathcal{A}^{t}]\geq 0.5.

(11)

Let $\sim$ denote the (agent $\times$ item)-level adjacency relation. One can check that ${\bm{u}}^{\prime}\sim_{2nc+2}{\bm{u}}^{t}$ for all $t\in[T]$ . Using this fact together with group DP (Lemma 2.8), we have

	$\displaystyle\Pr[\mathcal{M}({\bm{u}}^{\prime})\in\mathcal{A}^{t}]$	$\displaystyle\geq e^{-\varepsilon(2nc+2)}\cdot\Pr[\mathcal{M}({\bm{u}}^{t})\in\mathcal{A}^{t}]$
		$\displaystyle\overset{\eqref{eq:utility-prop-lb}}{\geq}0.5\cdot e^{-\varepsilon(2nc+2)}.$		(12)

Lemma 4.12.

$\mathcal{A}^{1},\dots,\mathcal{A}^{T}$ are disjoint.

Proof.

•

There must be at least $n-3$ cuts between item $m-cn$ and item $m$ . (Otherwise, the allocation cannot be PROP $c$ for at least one of agents $3,\dots,n$ .)
•

There must be a cut between item $(nc+1)(t-1)+1$ and item $(nc+1)t$ . (Otherwise, the allocation cannot be PROP $c$ for either agent $1$ or $2$ in ${\bm{u}}^{t}$ .)
•

There must be a cut between item $(nc+1)(t^{\prime}-1)+1$ and item $(nc+1)t^{\prime}$ . (Otherwise, the allocation cannot be PROP $c$ for either agent $1$ or $2$ in ${\bm{u}}^{t^{\prime}}$ .)

By our parameter selection, we have

	$\displaystyle\max\{(nc+1)t$	$\displaystyle,(nc+1)t^{\prime}\}$
		$\displaystyle\leq(nc+1)T\leq m/2<m-cn.$

This implies that the intervals of items discussed above are pairwise disjoint, and therefore the cuts must be distinct, i.e., those $n-1$ cuts are all the cuts in $A$ . Now, consider the leftmost interval of $A$ . The cut for this interval must be to the left of item $(nc+1)t$ . Suppose that the interval is assigned to agent $i$ . We consider the following two cases.

•

Case I: $i\in\{3,\dots,n\}$ . In this case, agent $i$ has value $0$ for her own bundle, and PROP $c$ is not satisfied.
•

Case II: $i\in\{1,2\}$ . In ${\bm{u}}^{t^{\prime}}$ , agent $i$ has value $0$ for her own bundle, and PROP $c$ is again not satisfied.

In both cases, $A$ cannot be PROP $c$ for both ${\bm{u}}^{t}$ and ${\bm{u}}^{t^{\prime}}$ simultaneously, a contradiction. This establishes Lemma 4.12. ∎

Lemma 4.12 implies that

	$\displaystyle 1$	$\displaystyle\geq\sum_{t\in[T]}\Pr[\mathcal{M}({\bm{u}}^{\prime})\in\mathcal{A}^{t}]$
		$\displaystyle\overset{\eqref{eq:group-dp-application-prop}}{\geq}0.5\cdot e^{-\varepsilon(2nc+2)}\cdot T$
		$\displaystyle\geq 0.5\cdot e^{-4nc\varepsilon}\cdot\left\lfloor\frac{m}{4nc}\right\rfloor$
		$\displaystyle\geq 0.5\cdot e^{-0.04\log(m/n)}\cdot\left\lfloor 5\sqrt{m/n}\right\rfloor$
		$\displaystyle\geq(0.5(m/n)^{-0.04})\cdot(2.5\sqrt{m/n})>1,$

where the third and fourth inequalities follow from our choice of parameters $c,T$ and the assumption that $c\geq 1$ . This is a contradiction which establishes Theorem 4.11. ∎

5 Conclusion and Future Work

In this paper, we have studied the fundamental task of fair division under differential privacy constraints, and provided algorithms and impossibility results for approximate envy-freeness and proportionality. There are several open questions left by our work. First, it would be useful to close the gaps in terms of $n$ ; for example, our envy-freeness upper bound for (agent $\times$ item)-level DP grows linearly in $n$ (Theorem 4.1) but our lower bound (Theorem 4.9) does not exhibit this behavior. Another perhaps more interesting technical direction is to extend our lower bounds for (agent $\times$ item)-level DP to arbitrary (i.e., not necessarily connected) allocations. Specifically, we leave the following intriguing open question: Is there an (agent $\times$ item)-level $\varepsilon$ -DP algorithm that, with probability at least $0.99$ , outputs an EF $c$ allocation for $c=O_{\varepsilon}(1)$ regardless of the values of $n$ and $m$ ?

While we have considered the original notion of DP proposed by Dwork et al. (2006b), there are a number of modifications that could be investigated in future work. A commonly studied notion is approximate DP (also called $(\varepsilon,\delta)$ -DP), which has an additional parameter $\delta\geq 0$ that specifies the probability with which the condition $\Pr[\mathcal{M}(X)=o]\leq e^{\varepsilon}\cdot\Pr[\mathcal{M}(X^{\prime})=o]$ is allowed to fail (Dwork et al. 2006a). The notion of DP that we use in this paper corresponds to the case $\delta=0$ and is often referred to as pure DP. Several problems in the literature are known to admit approximate-DP algorithms with better guarantees compared to pure-DP algorithms (see, e.g., the work of Steinke and Ullman (2016)). In light of this, it would be interesting to explore whether a similar phenomenon occurs in fair division as well.

Acknowledgments

This work was partially supported by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001 and by an NUS Start-up Grant.

References

Abowd (2018) Abowd, J. M. 2018. The US Census Bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2867.
Amanatidis et al. (2022) Amanatidis, G.; Birmpas, G.; Filos-Ratsikas, A.; and Voudouris, A. A. 2022. Fair division of indivisible goods: a survey. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 5385–5393.
Apple Differential Privacy Team (2017) Apple Differential Privacy Team. 2017. Learning with privacy at scale. http://machinelearning.apple.com/research/
learning-with-privacy-at-scale. Accessed 2022-11-21.
Aziz et al. (2022) Aziz, H.; Li, B.; Moulin, H.; and Wu, X. 2022. Algorithmic fair allocation of indivisible items: a survey and new questions. ACM SIGecom Exchanges, 20(1): 24–40.
Bei et al. (2022) Bei, X.; Igarashi, A.; Lu, X.; and Suksompong, W. 2022. The price of connectivity in fair division. SIAM Journal on Discrete Mathematics, 36(2): 1156–1186.
Bilò et al. (2022) Bilò, V.; Caragiannis, I.; Flammini, M.; Igarashi, A.; Monaco, G.; Peters, D.; Vinci, C.; and Zwicker, W. S. 2022. Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131: 197–221.
Bouveret et al. (2017) Bouveret, S.; Cechlárová, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), 135–141.
Bouveret, Chevaleyre, and Maudet (2016) Bouveret, S.; Chevaleyre, Y.; and Maudet, N. 2016. Fair allocation of indivisible goods. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice, chapter 12, 284–310. Cambridge University Press.
Brams and Taylor (1996) Brams, S. J.; and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press.
Ding, Kulkarni, and Yekhanin (2017) Ding, B.; Kulkarni, J.; and Yekhanin, S. 2017. Collecting telemetry data privately. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS), 3571–3580.
Dubins and Spanier (1961) Dubins, L. E.; and Spanier, E. H. 1961. How to cut a cake fairly. American Mathematical Monthly, 68(1): 1–17.
Dwork (2008) Dwork, C. 2008. Differential privacy: a survey of results. In Proceedings of the 5th International Conference on Theory and Applications of Models of Computation (TAMC), 1–19.
Dwork et al. (2006a) Dwork, C.; Kenthapadi, K.; McSherry, F.; Mironov, I.; and Naor, M. 2006a. Our data, ourselves: Privacy via distributed noise generation. In Proceedings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 486–503.
Dwork et al. (2006b) Dwork, C.; McSherry, F.; Nissim, K.; and Smith, A. D. 2006b. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Theory of Cryptography Conference (TCC), 265–284.
Dwork et al. (2009) Dwork, C.; Naor, M.; Reingold, O.; Rothblum, G. N.; and Vadhan, S. P. 2009. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 381–390.
Dwork and Roth (2014) Dwork, C.; and Roth, A. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4): 211–407.
Erlingsson, Pihur, and Korolova (2014) Erlingsson, Ú.; Pihur, V.; and Korolova, A. 2014. Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), 1054–1067.
Even and Paz (1984) Even, S.; and Paz, A. 1984. A note on cake cutting. Discrete Applied Mathematics, 7(3): 285–296.
Greenberg (2016) Greenberg, A. 2016. Apple’s ‘differential privacy’ is about collecting your data—but not your data. http://www.wired.com/2016/06/apples-differential-privacy-collecting-data. Accessed 2022-08-08.
Hardt and Talwar (2010) Hardt, M.; and Talwar, K. 2010. On the geometry of differential privacy. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 705–714.
Igarashi (2023) Igarashi, A. 2023. How to cut a discrete cake fairly. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI). Forthcoming.
Lipton et al. (2004) Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Economics and Computation (EC), 125–131.
Manurangsi and Suksompong (2022) Manurangsi, P.; and Suksompong, W. 2022. Almost envy-freeness for groups: Improved bounds via discrepancy theory. Theoretical Computer Science, 930: 179–195.
Markakis (2017) Markakis, E. 2017. Approximation algorithms and hardness results for fair division with indivisible goods. In Endriss, U., ed., Trends in Computational Social Choice, chapter 12, 231–247. AI Access.
McSherry (2010) McSherry, F. 2010. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. Communications of the ACM, 53(9): 89–97.
McSherry and Talwar (2007) McSherry, F.; and Talwar, K. 2007. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 94–103.
Moulin (2003) Moulin, H. 2003. Fair Division and Collective Welfare. MIT Press.
Moulin (2019) Moulin, H. 2019. Fair division in the Internet age. Annual Review of Economics, 11: 407–441.
Robbins (1955) Robbins, H. 1955. A remark on Stirling’s formula. American Mathematical Monthly, 62(1): 26–29.
Shankland (2014) Shankland, S. 2014. How Google tricks itself to protect Chrome user privacy. http://www.cnet.com/tech/services-and-software/how-google-tricks-itself-to-protect-chrome-user-privacy. Accessed 2022-11-21.
Steinke and Ullman (2016) Steinke, T.; and Ullman, J. R. 2016. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2): 3–22.
Suksompong (2019) Suksompong, W. 2019. Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics, 260: 227–236.
Suksompong (2021) Suksompong, W. 2021. Constraints in fair division. ACM SIGecom Exchanges, 19(2): 46–61.
Sun and Yang (2009) Sun, N.; and Yang, Z. 2009. Strategy proof and privacy preserving fair allocation mechanism. Japanese Economic Review, 60(2): 143–151.
Vadhan (2017) Vadhan, S. 2017. The complexity of differential privacy. In Lindell, Y., ed., Tutorials on the Foundations of Cryptography, chapter 7, 347–450. Springer International Publishing.
Walsh (2020) Walsh, T. 2020. Fair division: the computer scientist’s perspective. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), 4966–4972.

Appendix A Omitted Proofs

A.1 Proof of Theorem 2.7

Consider any pair of adjacent inputs $X\sim X^{\prime}$ , and any $o_{1},\dots,o_{k}\in\operatorname{range}(\mathcal{M})$ . From the condition on $\Gamma$ , there exists $i^{*}\in[k]$ such that $\Gamma(X)_{i}=\Gamma(X^{\prime})_{i}$ for all $i\neq i^{*}$ and $\Gamma(X)_{i^{*}}\sim\Gamma(X^{\prime})_{i^{*}}$ . From this, we have

	$\displaystyle\Pr[\mathcal{M}^{\prime}$	$\displaystyle(X)=(o_{1},\dots,o_{k})]$
		$\displaystyle=\Pr[\forall i\in[k],\mathcal{M}(\Gamma(X)_{i})=o_{i}]$
		$\displaystyle=\prod_{i\in[k]}\Pr[\mathcal{M}(\Gamma(X)_{i})=o_{i}]$
		$\displaystyle=\left(\prod_{i\in[k]\setminus\{i^{*}\}}\Pr[\mathcal{M}(\Gamma(X)_{i})=o_{i}]\right)$
		$\displaystyle\qquad\cdot\Pr[\mathcal{M}(\Gamma(X)_{i^{}})=o_{i^{}}]$
		$\displaystyle=\left(\prod_{i\in[k]\setminus\{i^{*}\}}\Pr[\mathcal{M}(\Gamma(X^{\prime})_{i})=o_{i}]\right)$
		$\displaystyle\qquad\cdot\Pr[\mathcal{M}(\Gamma(X)_{i^{}})=o_{i^{}}]$
		$\displaystyle\leq\left(\prod_{i\in[k]\setminus\{i^{*}\}}\Pr[\mathcal{M}(\Gamma(X^{\prime})_{i})=o_{i}]\right)$
		$\displaystyle\qquad\cdot e^{\varepsilon}\cdot\Pr[\mathcal{M}(\Gamma(X^{\prime})_{i^{}})=o_{i^{}}]$
		$\displaystyle=e^{\varepsilon}\cdot\prod_{i\in[k]}\Pr[\mathcal{M}(\Gamma(X^{\prime})_{i})=o_{i}]$
		$\displaystyle=e^{\varepsilon}\cdot\Pr[\forall i\in[k],\mathcal{M}(\Gamma(X^{\prime})_{i})=o_{i}]$
		$\displaystyle=e^{\varepsilon}\cdot\Pr[\mathcal{M}^{\prime}(X^{\prime})=(o_{1},\dots,o_{k})],$

where the inequality follows from the $\varepsilon$ -DP guarantee of $\mathcal{M}$ and the fact that $\Gamma(X)_{i^{*}}\sim\Gamma(X^{\prime})_{i^{*}}$ . Therefore, $\mathcal{M}^{\prime}$ is $\varepsilon$ -DP, as desired.

A.2 Proof of Lemma 2.12

Let $S:=X_{1}+\cdots+X_{k}$ . Due to symmetry, we have

	$\displaystyle\Pr$	$\displaystyle\left[S<\frac{k}{2}-0.1\sqrt{k}\right]$
		$\displaystyle=\frac{1}{2}\left(1-\Pr\left[\left\|S-\frac{k}{2}\right\|\leq 0.1\sqrt{k}\right]\right).$

Let $b=\lfloor k/2\rfloor$ . We have

	$\displaystyle\Pr\left[\left\|S-\frac{k}{2}\right\|\leq 0.1\sqrt{k}\right]$	$\displaystyle=\sum_{i=\left\lceil k/2-0.1\sqrt{k}\right\rceil}^{\left\lfloor k/2+0.1\sqrt{k}\right\rfloor}\binom{k}{i}\cdot\frac{1}{2^{k}}$
		$\displaystyle\leq\sum_{i=\left\lceil k/2-0.1\sqrt{k}\right\rceil}^{\left\lfloor k/2+0.1\sqrt{k}\right\rfloor}\binom{k}{b}\cdot\frac{1}{2^{k}}$
		$\displaystyle\leq\left(0.2\sqrt{k}+1\right)\binom{k}{b}\cdot\frac{1}{2^{k}}$
		$\displaystyle\leq 0.3\sqrt{k}\cdot\binom{k}{b}\cdot\frac{1}{2^{k}}.$

Now, we may bound $\binom{k}{b}\cdot\frac{1}{2^{k}}$ as follows:

	$\displaystyle\binom{k}{b}\cdot\frac{1}{2^{k}}$	$\displaystyle=\frac{k!}{b!(k-b)!}\cdot\frac{1}{2^{k}}$
		$\displaystyle\overset{\eqref{eq:stirling}}{\leq}\left(\frac{e^{1/12}}{\sqrt{2\pi}}\cdot\frac{k^{k+0.5}}{b^{b+0.5}(k-b)^{(k-b)+0.5}}\right)\cdot\frac{1}{2^{k}}$
		$\displaystyle=\frac{e^{1/12}}{\sqrt{\pi b}}\cdot\left(\frac{k}{2b}\right)^{b}\cdot\left(\frac{k}{2(k-b)}\right)^{(k-b)+0.5}$
		$\displaystyle\leq\frac{e^{1/12}}{\sqrt{\pi b}}\cdot\left(\frac{k}{2b}\right)^{b}$
		$\displaystyle=\frac{e^{1/12}}{\sqrt{\pi b}}\left(1+\frac{k-2b}{2b}\right)^{b}$
		$\displaystyle\leq\frac{e^{1/12}}{\sqrt{\pi b}}\left(1+\frac{1}{2b}\right)^{b}$
		$\displaystyle\leq\frac{e^{1/12}}{\sqrt{\pi b}}\cdot e^{(1/2b)\cdot b}$
		$\displaystyle=\frac{e^{7/12}}{\sqrt{\pi b}}$
		$\displaystyle\leq\frac{1.6}{\sqrt{k}},$

where the third-to-last inequality follows from the well-known fact that $1+x\leq e^{x}$ for every real number $x$ , and the last inequality from $b\geq(k-1)/2$ and $k\geq 100$ .

Combining the three (in)equalities above, we arrive at

\displaystyle\Pr\left[S<\frac{k}{2}-0.1\sqrt{k}\right]

\displaystyle\geq\frac{1}{2}\left(1-0.48\right)>\frac{1}{4},

completing the proof.

A.3 Proof of Lemma 2.13

Recall that a more precise version of Stirling’s Formula (e.g., (Robbins 1955)) gives

\displaystyle\sqrt{2\pi}n^{n+0.5}e^{-n}\leq n!\leq e^{1/12}\cdot\sqrt{2\pi}n^{n+0.5}e^{-n}

(13)

for every positive integer $n$ .

Let $a=\lfloor k/2+0.1\sqrt{k\log\gamma}\rfloor+1$ , $b=a+\lfloor 0.2\sqrt{k}\rfloor$ , and $r=b-k/2$ . Note that by our choice of parameters, we have

	$\displaystyle(0.4\sqrt{\log\gamma}$	$\displaystyle-0.2)\sqrt{k}$
		$\displaystyle\geq(0.4\sqrt{\log 2}-0.2)\sqrt{k}\geq 0.1\cdot 10=1.$

Hence, $0.2\sqrt{k}+1\leq 0.4\sqrt{k\log\gamma}$ , and therefore

$\displaystyle r$	$\displaystyle\leq 0.1\sqrt{k\log\gamma}+0.2\sqrt{k}+1$
	$\displaystyle\leq 0.5\sqrt{k\log\gamma}$	(14)
	$\displaystyle\leq 0.5\sqrt{0.7k\log_{2}\gamma}$
	$\displaystyle\leq 0.5\sqrt{0.7k(k/4)}<0.21k,$

which means that $b<0.71k$ .

We have

	$\displaystyle\Pr\left[S>\frac{k}{2}+0.1\sqrt{k\log\gamma}\right]$
	$\displaystyle\geq\sum_{i=a}^{b}\Pr[S=i]$
	$\displaystyle=\sum_{i=a}^{b}\binom{k}{i}\cdot\frac{1}{2^{k}}$
	$\displaystyle\geq(b-a+1)\cdot\binom{k}{b}\cdot\frac{1}{2^{k}}$
	$\displaystyle\geq 0.2\sqrt{k}\left(\binom{k}{b}\cdot\frac{1}{2^{k}}\right)$
	$\displaystyle=0.2\sqrt{k}\left(\frac{k!}{b!(k-b)!}\cdot\frac{1}{2^{k}}\right)$
	$\displaystyle\overset{\eqref{eq:stirling}}{\geq}0.2\sqrt{k}\left(0.3\cdot\frac{k^{k+0.5}}{b^{b+0.5}(k-b)^{(k-b)+0.5}}\cdot\frac{1}{2^{k}}\right)$
	$\displaystyle=0.2\sqrt{k}\left(0.3\sqrt{2}\cdot\frac{1}{b^{0.5}}\cdot\left(\frac{k}{2b}\right)^{b}\cdot\left(\frac{k}{2(k-b)}\right)^{(k-b)+0.5}\right)$
	$\displaystyle=0.2\cdot 0.3\sqrt{2}\cdot\sqrt{\frac{k}{b}}\cdot\left(\frac{k}{2b}\right)^{b}\cdot\left(\frac{k}{2(k-b)}\right)^{(k-b)+0.5}$
	$\displaystyle\geq 0.2\cdot 0.3\sqrt{2}\cdot\sqrt{\frac{1}{0.71}}\cdot\left(\frac{k}{2b}\right)^{b}\cdot\left(\frac{k}{2(k-b)}\right)^{(k-b)+0.5}$
	$\displaystyle\geq 0.1\cdot\left(\frac{k}{2b}\right)^{b}\cdot\left(\frac{k}{2(k-b)}\right)^{k-b}$
	$\displaystyle=0.1\cdot\left(\frac{k}{2b}\right)^{2b-k}\cdot\left(\frac{k^{2}}{4b(k-b)}\right)^{k-b}$
	$\displaystyle\geq 0.1\cdot\left(\frac{k}{2b}\right)^{2b-k}$
	$\displaystyle=\frac{0.1}{\left(1+\frac{2r}{k}\right)^{2r}}$
	$\displaystyle\geq\frac{0.1}{\exp(4r^{2}/k)}$
	$\displaystyle\overset{\eqref{eq:bound-r}}{\geq}\frac{0.1}{\gamma},$

where for the penultimate inequality we use the well-known fact that $1+x\leq\exp(x)$ for every real number $x$ . This completes the proof.

	$\displaystyle\Pr_{{\bm{u}}}[A\text{ is not EF}c\text{ for agent }i]$
	$\displaystyle\geq\Pr_{u_{i}}[u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle\qquad\cdot\Pr_{u_{i}}[A_{i}\text{ is not EF}c\text{ for agent }i\mid u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle\geq\frac{1}{2}\cdot\Pr_{u_{i}}[A_{i}\text{ is not EF}c\text{ for agent }i\mid u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle\geq\frac{1}{2}\cdot\Pr_{u_{i}}[\exists j<i,u_{i}(A_{j})>\|A_{i}\|/2+c\mid u_{i}(A_{i})\leq\|A_{i}\|/2]$
	$\displaystyle=\frac{1}{2}\cdot\left(1-\prod_{j\in[i-1]}\Pr_{u_{i}}[u_{i}(A_{j})\leq\|A_{i}\|/2+c]\right)$

	$\displaystyle\Pr_{{\bm{u}}}$	$\displaystyle[u_{i}(A_{j})>\|A_{i}\|/2+c]$
		$\displaystyle\geq\Pr_{{\bm{u}}}[u_{i}(S_{j})>\|A_{i}\|/2+c]$
		$\displaystyle\geq\Pr_{{\bm{u}}}\left[u_{i}(S_{j})>\|A_{i}\|/2+0.1\sqrt{\|A_{i}\|\log\gamma}\right]$
		$\displaystyle\overset{\text{(\lx@cref{creftypecap~refnum}{lem:anti-concen})}}{\geq}0.1/\gamma\geq 0.1/n,$

$\displaystyle u^{-k}_{i}(A_{i})$	$\displaystyle=\min_{T\subseteq M,\|T\|\leq k}u_{i}(A_{i}\setminus T)$
	$\displaystyle\leq\min_{T\subseteq M,\|T\|\leq k-1}u_{i}(A_{i}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle=\min_{T\subseteq M,\|T\|\leq k-1}\tilde{u}_{i}(A_{i}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle\leq\min_{T\subseteq M,\|T\|\leq k-1}\tilde{u}_{i}(A_{i}\setminus T)=\tilde{u}^{-(k-1)}_{i}(A_{i}).$	(3)

$\displaystyle\min_{T\subseteq M,\|T\|\leq d+k}$	$\displaystyle u_{i}(A_{i^{\prime}}\setminus T)$
	$\displaystyle\geq\min_{T\subseteq M,\|T\|\leq d+k}u_{i}(A_{i^{\prime}}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle=\min_{T\subseteq M,\|T\|\leq d+k}\tilde{u}_{i}(A_{i^{\prime}}\setminus(T\cup\{j^{*}\}))$
	$\displaystyle\geq\min_{T\subseteq M,\|T\|\leq d+k+1}\tilde{u}_{i}(A_{i^{\prime}}\setminus T)$
	$\displaystyle=\min_{S\subseteq M,\|S\|\leq d+2}\tilde{u}^{-(k-1)}_{i}(A_{i^{\prime}}\setminus S).$	(4)

	$\displaystyle u_{i}([\ell^{i}_{q+1},r^{i}_{q+1}])$
	$\displaystyle\geq\frac{n^{L}}{\|\mathcal{I}\|}u_{i}([\ell,h_{z_{n^{L}}}])$
	$\displaystyle\qquad+\frac{n^{R}}{\|\mathcal{I}\|}\cdot\frac{n^{L}}{n^{R}}\cdot u_{i}^{-3g_{b_{q}}/4}([h_{z_{n^{L}}}+1,r])$
	$\displaystyle=\frac{n^{L}}{\|\mathcal{I}\|}\bigg{(}u_{i}([\ell,h_{z_{n^{L}}}])+u_{i}^{-3g_{b_{q}}/4}([h_{z_{n^{L}}}+1,r])\bigg{)}$
	$\displaystyle=\frac{n^{L}}{\|\mathcal{I}\|}\bigg{(}u_{i}([\ell,r])-u_{i}^{\operatorname{top-}(3g_{b_{q}}/4)}([h_{z_{n^{L}}}+1,r])\bigg{)}$
	$\displaystyle=\frac{n^{i}_{q+1}}{n^{i}_{q}}\left(u_{i}([\ell^{i}_{q},r^{i}_{q}])-u_{i}^{\operatorname{top-}(3g_{b_{q}}/4)}(R^{i}_{q})\right)$
	$\displaystyle\geq\frac{n^{i}_{q+1}}{n^{i}_{q}}\left(u_{i}([\ell^{i}_{q},r^{i}_{q}])-u_{i}^{\operatorname{top-}(2g_{b_{q}})}(R^{i}_{q})\right).$

Differentially Private Fair Division

Abstract

1 Introduction

2 Preliminaries

2.1 Fair Division

Theorem 2.1 ((Bilò et al. 2022)).

2.2 Differential Privacy

Definition 2.2 (Differential Privacy (Dwork et al. 2006b)).

Definition 2.3 (Agent-Level DP).

Definition 2.4 ((Agent ×\times Item)-Level DP).

Basic Composition.

Theorem 2.5 (Basic Composition of DP, e.g., (Dwork and Roth 2014)).

Observation 2.6 (Post-processing of DP).

Parallel Composition.

Theorem 2.7 ((McSherry 2010)).

Group Privacy.

Lemma 2.8 (Group Differential Privacy, e.g., (Vadhan 2017)).

Sensitivity.

Definition 2.9.

Sparse Vector Technique.

Theorem 2.10.

Exponential Mechanism.

Theorem 2.11 ((McSherry and Talwar 2007)).

2.3 Anti-Concentration Inequalities

Lemma 2.12.

Lemma 2.13.

3 Agent-Level DP

Theorem 3.1.

Theorem 3.2.

3.1 Proof of Theorem 3.2

Lemma 3.3.

Proof.

Proof of Theorem 3.2.

3.2 Proof of Theorem 3.1

Lemma 3.4.

Proof.

Proof of Theorem 3.1.

4 (Agent ×\times Item)-Level DP

4.1 Algorithms

Approximate Envy-Freeness

Theorem 4.1.

Definition 4.2.

Observation 4.3.

Lemma 4.4.

Proof.

Definition 4.5.

Lemma 4.6.

Proof.

Proof of Theorem 4.1.

Approximate Proportionality

Theorem 4.7.

Proof of Theorem 4.7.

Lemma 4.8.

Proof.

Privacy Analysis.

Utility Analysis.

4.2 Lower Bounds

Theorem 4.9.

Proof.

Lemma 4.10.

Proof.

Theorem 4.11.

Proof.

Lemma 4.12.

Proof.

5 Conclusion and Future Work

Acknowledgments

References

Appendix A Omitted Proofs

A.1 Proof of Theorem 2.7

A.2 Proof of Lemma 2.12

A.3 Proof of Lemma 2.13

Definition 2.4 ((Agent $\times$ Item)-Level DP).

4 (Agent $\times$ Item)-Level DP