  We study a new framework for designing differentially private (DP) mechanisms
via randomized graph colorings, called rainbow differential privacy. In this
framework, datasets are nodes in a graph, and two neighboring datasets are
connected by an edge. Each dataset in the graph has a preferential ordering for
the possible outputs of the mechanism, and these orderings are called rainbows.
Different rainbows partition the graph of connected datasets into different
regions. We show that if a DP mechanism at the boundary of such regions is
fixed and it behaves identically for all same-rainbow boundary datasets, then a
unique optimal $(\epsilon,\delta)$-DP mechanism exists (as long as the boundary
condition is valid) and can be expressed in closed-form. Our proof technique is
based on an interesting relationship between dominance ordering and DP, which
applies to any finite number of colors and for $(\epsilon,\delta)$-DP,
improving upon previous results that only apply to at most three colors and for
$\epsilon$-DP. We justify the homogeneous boundary condition assumption by
giving an example with non-homogeneous boundary condition, for which there
exists no optimal DP mechanism.
