Consider two independent sequences $(X_i)_{i\leq n}$ and $(X'_i)_{i\leq n}$ that are independent and uniformly distributed over $\lbrack 0, 1\rbrack^d, d \geq 3$. Under mild regularity conditions, we describe the convex functions $\varphi$ such that, with large probability, there exists a one-to-one map $\pi$ from $\{1,\ldots,n\}$ to $\{1,\ldots,n\}$ for which $\sum_{i\leq n}\frac{1}{n}\varphi\big(\frac{X_i - X'_{\pi(i)}}{n^{-1/d}K_\varphi}\big) \leq 1,$ where $K_\varphi$ depends on $\varphi$ only.