Unselfish Coded Caching Can Yield Unbounded Gains Over Selfish Caching

The original coded caching scenario assumes a content library that is of interest to all receiving users. In a realistic scenario though, the users may have diverging interests which may intersect to various degrees. What happens for example if each file is of potential interest to, say, 40% of the users and each user has potential interest in 40% of the library? In this work, we investigate the so- called symmetrically selfish coded caching scenario, where each user only makes requests from a subset of the library that defines its own file demand set (FDS), each user caches selfishly only contents from its own FDS, and where the different FDSs symmetrically overlap to some extent. In the context of various traditional prefetching scenarios (prior to the emergence of coded caching), selfish approaches were known to be potentially very effective. On the other hand — with the exception of some notable works — little is known about selfish coded caching. We here present a new information-theoretic converse that proves, in a general setting of symmetric FDS structures, that selfish coded caching, despite enjoying a much larger local caching gain and a much smaller set of possible demands, introduces an unbounded load increase compared to the unselfish case. In particular, in the <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula>-user broadcast channel where each user stores a fraction <inline-formula> <tex-math notation="LaTeX">$\gamma $ </tex-math></inline-formula> of the library, where each file (class) is of interest to <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> users, and where any one specific file is of interest to a fraction <inline-formula> <tex-math notation="LaTeX">$\delta $ </tex-math></inline-formula> of users, the optimal coding gain of symmetrically selfish caching is at least <inline-formula> <tex-math notation="LaTeX">$(K - \alpha)\gamma + 1$ </tex-math></inline-formula> times smaller than in the unselfish scenario. This allows us to draw the powerful conclusion that the optimal selfish coding gain is upper bounded by <inline-formula> <tex-math notation="LaTeX">$1/(1 - \delta)$ </tex-math></inline-formula>, and thus does not scale with <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula>. These derived limits are shown to be exact for different types of demands. In the end, this work provides, in a unified manner, the strong conclusion that selfish caching can cause unbounded performance deterioration in coded caching systems.