Equilibria in Sequential Allocation
Sequential allocation is a simple mechanism for sharing multiple indivisible items. We study strategic behavior in sequential allocation. In particular, we consider Nash dynamics, as well as the computation and Pareto optimality of pure equilibria, and St
- PDF / 203,856 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 103 Downloads / 200 Views
3
Data61, CSIRO, Sydney, Australia [email protected] 2 UNSW, Sydney, Australia [email protected] University of Oxford, Oxford, UK [email protected]
Abstract. Sequential allocation is a simple mechanism for sharing multiple indivisible items. We study strategic behavior in sequential allocation. In particular, we consider Nash dynamics, as well as the computation and Pareto optimality of pure equilibria, and Stackelberg strategies. We first demonstrate that, even for two agents, better responses can cycle. We then present a linear-time algorithm that returns a profile (which we call the “bluff profile”) that is in pure Nash equilibrium. Interestingly, the outcome of the bluff profile is the same as that of the truthful profile and the profile is in pure Nash equilibrium for all cardinal utilities consistent with the ordinal preferences. We show that the outcome of the bluff profile is Pareto optimal with respect to pairwise comparisons. In contrast, we show that an assignment may not be Pareto optimal with respect to pairwise comparisons even if it is a result of a preference profile that is in pure Nash equilibrium for all utilities consistent with ordinal preferences. Finally, we present a dynamic program to compute an optimal Stackelberg strategy for two agents, where the second agent has a constant number of distinct values for the items.
1
Introduction
A simple but popular mechanism to allocate indivisible items is sequential allocation [3,5,8,9,12,14,15]. Sequential allocation is used, for example, by the Harvard Business School to allocate courses to students [10] as well as multimillion dollar sports drafts [8]. In a sequential allocation mechanism, a picking sequence specifies the turns of the agents. For example, for sequence 1212, agents 1 and 2 alternate with agent 1 taking the first turn. Agents report their preferences over the items. Then the items are allocated to the agents in the following manner. In each turn, the agent in that turn is given the most preferred item that has not yet been allocated. In this paper we focus on the “direct revelation” version where agents submit their complete rankings at the same time (and are committed to them), as opposed to the “extensive form” version where agents take turns choosing and are only committed to items chosen previously. Sequential allocation is an ordinal mechanism since the outcome only depends on the ordinal preferences of agents over items. Although the agents are asked to report c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 270–283, 2017. DOI: 10.1007/978-3-319-67504-6 19
Equilibria in Sequential Allocation
271
ordinal preferences, we will assume a standard assumption in the literature that agents have underlying additive utilities for the items. It has long been known that sequential allocation is not strategy-proof when agents do not have consecutive turns. An agent may not pick their most preferred item remaining if they expect this item to remain till a later turn. Instead, the a
Data Loading...
