Algorithms for Manipulating Sequential Allocation

Mingyu Xiao, Jiaxing LingAAAI 2020 · DOI

Abstract

Sequential allocation is a widely used mechanism for distributing indivisible items among agents with private preferences. However, it is susceptible to strategic manipulation, where agents misreport their preferences to obtain better outcomes. This paper addresses the computational complexity of finding an optimal manipulation (best response) when the number of agents is fixed. We present a polynomial-time algorithm based on a novel dynamic programming approach that leverages structural properties of picking policies, specifically "crucial instances" and state invariance. Furthermore, we establish a lower bound on the performance of truthful reporting, proving it achieves at least 50% of the utility of an optimal manipulation.

Introduction

Sequential allocation is a common mechanism for distributing items like sports players in a draft or elective courses to students. Agents take turns picking their favorite available item based on a pre-set "policy" or picking sequence. While intuitive, the system is not strategyproof. If an agent knows the preferences of others, they can often improve their own outcome by lying about their own rankings—for instance, by delaying picking a top choice they know no one else wants in order to "snatch" a contested item first.

While researchers previously established that the best response can be calculated in polynomial time for two agents, the problem is NP-hard when the number of agents is part of the input. This paper fills the gap for a fixed, small number of agents (e.g., $n=3$), a scenario common in many practical applications.

Algorithmic Approach: Managing Complexity

The authors introduce a novel dynamic programming (DP) approach built on two primary theoretical pillars to manage the potentially explosive state space of the problem.

Crucial Instances and Policy Segmentation

The first pillar is the definition of "crucial instances." These are specific versions of a picking policy where any further delay in the manipulator's turns would result in a strictly worse outcome. The authors prove that every instance has a corresponding crucial instance yielding the same optimal utility. This allows the algorithm to focus on a simplified search space by segmenting the policy into manageable parts.

Figure 2: An illustration of policy segmentation and the 'core' sequence of turns. The policy is decomposed into segments, identifying the 'trivial' parts that do not impact the optimal strategy.

As shown in Figure 2, a complex policy $\pi$ can be reduced to a "core" sequence. By identifying trivial segments—turns that do not affect the manipulator's optimal choices—the algorithm significantly reduces the number of states it must evaluate.

Invariance Relations

The second pillar involves identifying "invariance properties." To prevent the DP state space from exploding, the authors show that if two different partial allocation sequences result in the same set of items being distributed, the same number of items per agent, and the same rank of the last item picked by each non-manipulator, then the future optimal moves are identical. By tracking only these essential state variables, they designed an algorithm with a complexity of $O((1+m)^{n+4})$, where $m$ is the number of items and $n$ is the number of agents.

Key Results

Polynomial Time for Fixed $n$

The paper successfully categorizes the "Best Response" problem as being in P for any constant number of agents. For $n=3$, the complexity is $O(m^7)$, which is computationally expensive but theoretically efficient (polynomial).

The 0.5-Approximation Theorem

One of the most significant findings is the "Price of Honesty." The authors prove that for any instance with additive utility functions, the utility gained from a truthful response is at least 50% of the utility achievable through perfect, omniscient manipulation. This result suggests that while lying can be beneficial, the gains from complex manipulation are bounded; an agent cannot more than double their utility by being a strategic mastermind. They also demonstrate that this 0.5 ratio is "tight," meaning no higher universal guarantee exists.

Conclusion and Future Work

This work provides a theoretical foundation for understanding manipulation in sequential allocation. While the algorithm is polynomial for a fixed $n$, the high exponent remains a practical challenge for larger groups. Furthermore, the model assumes the manipulator has complete information about others' preferences, which is rarely the case in reality. Future research may explore the approximation ratios of truthful responses in other non-strategyproof mechanisms and seek to optimize the DP for specific common policies, such as the "S-shaped" snaking drafts used in fantasy sports.

Summary updated

BibTeX
@inproceedings{xiao2020algorithms,
  author = {Mingyu Xiao and Jiaxing Ling},
  title = {{Algorithms for Manipulating Sequential Allocation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5608},
}
Figure