Consider $n \in \mathbb{N}$ fashion-sensitive kids, each wearing a T-shirt; for simplicity, kid $i \in \{1, \ldots, n\}$ initially wears shirt $i$. Tastes over the shirts are summarized in an $n \times n$ matrix: entry $a_{ij} \in \mathbb{R}$ in row $i$ and column $j$ tells how much child $i$ values shirt $j$.
Show that some subset of kids can swap shirts among themselves so that (1) they each receive a favorite shirt among those redistributed and (2) these newly attired kids have no common fashion victim with a shirt all of them find uglier than the one they are currently wearing.
Formally: show that there is a nonempty subset $S$ of $\{1, \ldots, n\}$ and a permutation $\sigma: S \to S$ with the interpretation that kid $i \in S$ gets shirt $\sigma(i) \in S$ (valued at $a_{i, \sigma(i)}$) such that:
- each member of $S$ gets a favorite shirt among those in $S$: $a_{i, \sigma(i)} = \max \{a_{ij}: j \in S\}$ for all $i \in S$;
- no child $k \in \{1, \ldots, n\}$ has a shirt that all members of $S$, now in their new shirts, find worse: there is no $k \in \{1, \ldots, n\}$ such that $a_{i, \sigma(i)} > a_{ik}$ for all $i \in S$.
Comment on origin/approach: my book club is reading about game theory and this came up in a discussion of matching theory, a topic of the 2012 Nobel prize to Shapley and Roth. It seems straightforward to assure the first property: let each kid point toward the kids with shirts he/she prefers most. This generates a directed graph and if you find a cycle, say with kid $A$ pointing to $B$, $B$ pointing to $C$, and $C$ pointing back to $A$, just give these three kids the shirt of the person they're pointing at. Removing $A$, $B$, and $C$ and repeating until there are no kids left, each such cycle generates a set of people satisfying the first property. That was referred to as the top-trading cycle algorithm. But I couldn't figure out how to adjust this to take care of the second property.