Mechanism Design in Fair Sequencing

Sequencing agents to ensure fairness is a common issue in various domains, such as project presentations, job interview scheduling, and sports or musical game sequence arrangement. Since agents have their own positional preferences, we investigate whether extra credits can be assigned to some agents, so that all agents can choose their preferred positions. We propose an auction system to determine the fair number of credits that an agent may sacrifice for a position they like or request for a position they dislike. The system is modeled as a problem of pricing sequence positions, which demands budget-balanced and egalitarian conditions. We prove that deterministic protocols that guarantee DSIC (dominant-strategy incentive compatibility), budget-balance and egalitarianism do not exist. Furthermore, we design a randomized protocol that ensures being truthful is always the optimal response for every player. A particularly significant technical contribution we make is the establishment of the uniqueness of a randomized protocol with respect to the incentive compatible condition, which serves as the most suitable proxy when incentives are compatible.