Technical Perspective: Can Data Structures Treat Us Fairly?

When asked to pick a random buddy from our Facebook friends list, we may struggle since our nomination is likely to be biased toward individuals with whom we interact more frequently. Computer assistance in such a case would make things easier: we can just store our friends' names in an array. Whenever a query comes, the computer generates a random array index and returns the name stored in the corresponding location. The question now is whether, for any given data structure problem, we can build a data structure that generates "fair" output while maintaining query efficiency. In the context of data structure query-answering, fairness can be defined as follows: we either return all valid answers or just return a uniformly random one.