Exploiting puzzle diversity in puzzle selection for ESP-like GWAP systems

The ESP game belongs to the genre called Games with a Purpose (GWAP), which leverage people's desire to be entertained and also outsource certain steps of the computational process to humans. The productivity of ESP-like GWAP systems depends to a great extent on the puzzle selection strategy used in the system. Although traditional approaches seek to determine the optimal number of agreements reached in each puzzle, they may be affected by the equality of outcomes issue because they ignore the differences among puzzles. In this paper, using realistic game traces, we define the puzzle diversity issue and propose a novel approach, called the Adaptive Puzzle Selection Algorithm (APSA), to promote equality of opportunity in ESP-like GWAP systems. We also introduce a data structure called the Weight Sum Tree (WST) to reduce the computational complexity of the proposed scheme and facilitate its implementation in real-world systems. Using a comprehensive set of simulations, we evaluate the APSA scheme against the traditional OPSA scheme, and demonstrate that APSA can better accommodate the differences among puzzles in ESP-like GWAP systems.