Suppose we have a set $N$ of $n$ players and a set $M$ of $m$ items. We are given a matrix $P_{n \times m}$ whose element $p_{ij} \geq 0$ $(i \in N, m \in M)$ denotes the valuation of good $j$ by player $i$. Let $v = [v_1, v_2, \cdots, v_n]$ be a vector of valuation functions defined as $v_i(S) = \sum_{j \in S} p_{ij}$ for all $S \subseteq M$ and $i \in N$. We additionally have $v_i(\{\}) = 0$ for all $i \in N$.
Consider a distribution protocol or the order in which the objects will be picked up by a player:
Number players from 1 through n
While there are unclaimed objects:
Let each player from 1 through n claim one unclaimed item one-by-one
Put simply, players take turns picking items in sequence from the first to the $n^{\text{th}}$ player, repeating the cycle until all items are chosen.
Game Description: Imagine a perfect-information sequential game that follows the distribution protocol described above. That is, the game starts with the first player choosing from a set of $m$ items. After that, the second player picks an item from the remaining $m - 1$ items, then the third from $m - 2$, and so on, until the $n$th player chooses one from what's left. Once all $n$ players have taken a turn, the game loops back to the first player, who now chooses one from $m - n$ items. This picking order continues in rounds until all items are allocated.
Along any path or in any sub-game, the utility of player $i$ is given by the valuation $v_i$ of the allocation he gets.
Example: Consider the following game with $2$ players and $4$ items.
The SPNE paths, obtained through backward induction, are marked in red.
Payoffs: The utility of player $i$, when employing strategy $s_i$, is given by $v_i(A_{(s_i, s_{-i})})$, where $A_{(s_i, s_{-i})}$ denotes the allocation resulting from player $i$ choosing strategy $s_i$ and the remaining players following strategies $s_{-i}$.
Look at the first path: $a \to b \to c \to d$. Here, $1$ gets $\{a,c\}$ and $2$ gets $\{b,d\}$ and so the utility vector is $[v1(\{a,c\}, v_2(\{b,d\}))] = [6,7]$, written in ${\color{green}{\text{lemon green}}}$.
Objective: Show that in every SPNE outcome, if the equilibrium results in allocations $(A_1, A_2, \cdots, A_n)$, then it must be that $v_1(A_1^{*}) \geq v_1(A_j^{*})$ for all $j > 1$. In simpler terms, show that in every equilibrium outcome, the first player will weakly prefer his allocation to everyone else's.
