Equilibria in sequential allocation

DOI10.1007/978-3-319-67504-6_19MaRDI QIDQ1990309zbMATH OpenOpenAlexFDO

Authors Haris Aziz, Paul W. Goldberg, Toby Walsh

Publication date 25 October 2018

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(14)

• Possible and necessary allocations under serial dictatorship with incomplete preference lists
• scientific article; zbMATH DE number 6902543 (Why is no real title available?)
• Pexider's equation and aggregation of allocations
• Efficiency in sequential partnerships
• Fair choice sequences
• scientific article; zbMATH DE number 6875266 (Why is no real title available?)
• How proper is sequential equilibrium?
• Bruhat orders and the sequential selection of indivisible items
• A Refinement of Sequential Equilibrium
• Parameterized complexity of manipulating sequential allocation
• 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
• Manipulating picking sequences

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)