Equilibria in sequential allocation

DOI10.1007/978-3-319-67504-6_19zbMATH Open1398.91361arXiv1705.09444OpenAlexW2619218712MaRDI QIDQ1990309FDOQ1990309

Authors: Haris Aziz, Paul W. Goldberg, Toby Walsh 

Publication date: 25 October 2018

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 emph{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.

Full work available at URL: https://arxiv.org/abs/1705.09444

Recommendations

• scientific article; zbMATH DE number 6902543
• Strategy-proof allocation of indivisible goods
• Strategy-proof, efficient, and nonbossy quota allocations
• Manipulating picking sequences
• The curse of simultaneity

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cited In (11)

• Possible and necessary allocations under serial dictatorship with incomplete preference lists
• Title not available (Why is that?)
• Pexider's equation and aggregation of allocations
• Efficiency in sequential partnerships
• Title not available (Why is that?)
• How proper is sequential equilibrium?
• Bruhat orders and the sequential selection of indivisible items
• A Refinement of Sequential Equilibrium
• Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
• Capacity allocation games without an initial sequence
• Approximate and strategyproof maximin share allocation of chores with ordinal preferences

This page was built for publication: Equilibria in sequential allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990309)