[proofplan]
We construct $\varphi$ by fixing one base point of $\Gamma$ and taking the supremum over all finite cyclically monotone path sums starting from that base point. Each path sum is an affine function of the terminal variable, so the supremum is convex and lower semicontinuous by a direct verification. Cyclic monotonicity applied to cycles returning to the base point shows that $\varphi$ is finite at the base point, hence proper. Finally, appending an arbitrary pair $(x,p) \in \Gamma$ to any admissible chain gives the subgradient inequality $\varphi(z) \geq \varphi(x) + p \cdot (z-x)$ for every $z \in \mathbb{R}^d$.
[/proofplan]
[step:Define the Rockafellar potential from chains based at a fixed point]
Since $\Gamma$ is nonempty, choose a base point $(x_0,p_0) \in \Gamma$. For each integer $m \geq 0$, let $\mathcal{C}_m$ be the set of finite chains
\begin{align*}
C = ((x_i,p_i))_{i=0}^m
\end{align*}
such that $(x_i,p_i) \in \Gamma$ for every $0 \leq i \leq m$ and the initial pair is the fixed base pair $(x_0,p_0)$.
For a chain $C \in \mathcal{C}_m$, define the affine function $A_C: \mathbb{R}^d \to \mathbb{R}$ by
\begin{align*}
A_C(x) := p_m \cdot (x - x_m) + \sum_{i=0}^{m-1} p_i \cdot (x_{i+1} - x_i).
\end{align*}
When $m=0$, the empty sum is interpreted as $0$, so $A_C(x)=p_0\cdot(x-x_0)$.
Define $\varphi: \mathbb{R}^d \to (-\infty,\infty]$ by
\begin{align*}
\varphi(x) := \sup \{ A_C(x) : m \geq 0,\ C \in \mathcal{C}_m \}.
\end{align*}
The indexing family is nonempty because the chain $((x_0,p_0))$ belongs to $\mathcal{C}_0$.
[/step]
[step:Use cyclic monotonicity to prove that the potential is proper]
For every chain $C=((x_i,p_i))_{i=0}^m \in \mathcal{C}_m$, set $x_{m+1}:=x_0$. Evaluating the affine path sum at the base point gives
\begin{align*}
A_C(x_0) = p_m \cdot (x_0 - x_m) + \sum_{i=0}^{m-1} p_i \cdot (x_{i+1} - x_i).
\end{align*}
By the definition of $x_{m+1}$, this is
\begin{align*}
A_C(x_0) = \sum_{i=0}^{m} p_i \cdot (x_{i+1} - x_i).
\end{align*}
Since the finite family $(x_i,p_i)_{i=0}^m$ lies in $\Gamma$ and $\Gamma$ is cyclically monotone, we have
\begin{align*}
A_C(x_0) \leq 0.
\end{align*}
Taking the supremum over all chains gives $\varphi(x_0) \leq 0$. On the other hand, the length-zero chain $C_0=((x_0,p_0))$ satisfies
\begin{align*}
A_{C_0}(x_0)=p_0\cdot(x_0-x_0)=0,
\end{align*}
so $\varphi(x_0) \geq 0$. Hence
\begin{align*}
\varphi(x_0)=0.
\end{align*}
Moreover, for every $x \in \mathbb{R}^d$,
\begin{align*}
\varphi(x) \geq A_{C_0}(x)=p_0\cdot(x-x_0)>-\infty.
\end{align*}
Thus $\varphi$ never takes the value $-\infty$ and is finite at $x_0$, so $\varphi$ is proper.
[guided]
The possible failure of properness would be that the supremum is identically $+\infty$, or that the construction somehow allows the value $-\infty$. The second failure cannot occur because our family of affine functions is nonempty: the one-point chain $C_0=((x_0,p_0))$ always contributes the finite affine function $x \mapsto p_0\cdot(x-x_0)$.
The main point is to show that $\varphi$ is not $+\infty$ everywhere. We prove this at the base point $x_0$. Let $C=((x_i,p_i))_{i=0}^m \in \mathcal{C}_m$ be any admissible chain, and define $x_{m+1}:=x_0$ so that the chain closes into a cycle. At $x_0$, the terminal affine term becomes
\begin{align*}
p_m \cdot (x_0 - x_m)=p_m\cdot(x_{m+1}-x_m).
\end{align*}
Therefore
\begin{align*}
A_C(x_0)=p_m \cdot (x_{m+1}-x_m)+\sum_{i=0}^{m-1}p_i\cdot(x_{i+1}-x_i).
\end{align*}
This is exactly the full cyclic sum
\begin{align*}
A_C(x_0)=\sum_{i=0}^{m}p_i\cdot(x_{i+1}-x_i).
\end{align*}
Because every pair $(x_i,p_i)$ belongs to $\Gamma$ and $\Gamma$ is cyclically monotone, this cyclic sum is at most $0$. Hence every admissible affine function satisfies $A_C(x_0)\leq 0$, so their supremum satisfies $\varphi(x_0)\leq 0$.
The reverse inequality comes from the one-point chain $C_0=((x_0,p_0))$. For this chain,
\begin{align*}
A_{C_0}(x_0)=p_0\cdot(x_0-x_0)=0.
\end{align*}
Since $\varphi(x_0)$ is the supremum over all admissible chains, $\varphi(x_0)\geq 0$. Combining the two inequalities gives
\begin{align*}
\varphi(x_0)=0.
\end{align*}
Finally, the same one-point chain also gives, for every $x \in \mathbb{R}^d$,
\begin{align*}
\varphi(x)\geq A_{C_0}(x)=p_0\cdot(x-x_0),
\end{align*}
which is a finite real number. Thus $\varphi$ never equals $-\infty$, and since $\varphi(x_0)=0<\infty$, the function is proper.
[/guided]
[/step]
[step:Verify convexity and lower semicontinuity from the affine supremum]
For each admissible chain $C$, the map $A_C:\mathbb{R}^d\to\mathbb{R}$ is affine, hence convex and continuous.
Let $x,y\in\mathbb{R}^d$ and let $\lambda\in[0,1]$. For every admissible chain $C$,
\begin{align*}
A_C(\lambda x+(1-\lambda)y)=\lambda A_C(x)+(1-\lambda)A_C(y).
\end{align*}
Taking the supremum over all admissible chains on the left and using $A_C(x)\leq\varphi(x)$ and $A_C(y)\leq\varphi(y)$ on the right gives
\begin{align*}
\varphi(\lambda x+(1-\lambda)y)\leq \lambda\varphi(x)+(1-\lambda)\varphi(y).
\end{align*}
Thus $\varphi$ is convex.
To prove lower semicontinuity, fix $a\in\mathbb{R}$. Since
\begin{align*}
\{x\in\mathbb{R}^d:\varphi(x)>a\}
=
\bigcup_{m\geq0}\ \bigcup_{C\in\mathcal{C}_m}\{x\in\mathbb{R}^d:A_C(x)>a\},
\end{align*}
and each set $\{x\in\mathbb{R}^d:A_C(x)>a\}$ is open by continuity of $A_C$, the strict superlevel set $\{\varphi>a\}$ is open. Therefore $\varphi$ is lower semicontinuous.
[/step]
[step:Append a given point of $\Gamma$ to obtain the subgradient inequality]
Fix an arbitrary pair $(x,p)\in\Gamma$. Let $z\in\mathbb{R}^d$ be arbitrary.
For any integer $m\geq0$ and any chain $C=((x_i,p_i))_{i=0}^m\in\mathcal{C}_m$, define the appended chain $\widetilde C\in\mathcal{C}_{m+1}$ by
\begin{align*}
(\widetilde x_i,\widetilde p_i) &:=(x_i,p_i) \quad \text{for } 0\leq i\leq m,
\end{align*}
and
\begin{align*}
(\widetilde x_{m+1},\widetilde p_{m+1}) &:=(x,p).
\end{align*}
This is admissible because the original chain begins at $(x_0,p_0)$ and $(x,p)\in\Gamma$. By the definition of $\varphi$,
\begin{align*}
\varphi(z)\geq A_{\widetilde C}(z).
\end{align*}
Expanding $A_{\widetilde C}(z)$ gives
\begin{align*}
A_{\widetilde C}(z)
=
p\cdot(z-x)+p_m\cdot(x-x_m)+\sum_{i=0}^{m-1}p_i\cdot(x_{i+1}-x_i).
\end{align*}
The final two terms are exactly $A_C(x)$, so
\begin{align*}
A_{\widetilde C}(z)=p\cdot(z-x)+A_C(x).
\end{align*}
Hence, for every admissible chain $C$,
\begin{align*}
\varphi(z)\geq p\cdot(z-x)+A_C(x).
\end{align*}
Taking the supremum over all admissible chains $C$ yields
\begin{align*}
\varphi(z)\geq p\cdot(z-x)+\varphi(x).
\end{align*}
Since $z\in\mathbb{R}^d$ was arbitrary, this is precisely the subgradient inequality
\begin{align*}
\varphi(z)\geq\varphi(x)+p\cdot(z-x) \qquad \text{for every } z\in\mathbb{R}^d.
\end{align*}
Therefore $p\in\partial\varphi(x)$. Since $(x,p)\in\Gamma$ was arbitrary, $\Gamma\subset\partial\varphi$.
[/step]
