The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k and their adjacent edges are removed until no vertices of degree less than k are left. Often the questi
on is whether the remaining hypergraph, the k-core, is empty or not. In some settings, it may be possible to remove either vertices or edges from the hypergraph before peeling, at some cost. For example, in hashing applications where keys correspond to edges and buckets to vertices, one might use an additional side data structure, commonly referred to as a stash, to separately handle some keys in order to avoid collisions. The natural question in such cases is to find the minimum number of edges (or vertices) that need to be stashed in order to realize an empty k-core. We show that both these problems are NP-complete for all $k geq 2$ on graphs and regular hypergraphs, with the sole exception being that the edge variant of stashing is solvable in polynomial time for $k = 2$ on standard (2-uniform) graphs.
We analyze the value to e-commerce website operators of offering privacy options to users, e.g., of allowing users to opt out of ad targeting. In particular, we assume that site operators have some control over the cost that a privacy option imposes
on users and ask when it is to their advantage to make such costs low. We consider both the case of a single site and the case of multiple sites that compete both for users who value privacy highly and for users who value it less. One of our main results in the case of a single site is that, under normally distributed utilities, if a privacy-sensitive user is worth at least $sqrt{2} - 1$ times as much to advertisers as a privacy-insensitive user, the site operator should strive to make the cost of a privacy option as low as possible. In the case of multiple sites, we show how a Prisoners-Dilemma situation can arise: In the equilibrium in which both sites are obliged to offer a privacy option at minimal cost, both sites obtain lower revenue than they would if they colluded and neither offered a privacy option.
