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)

• Bruhat orders and the sequential selection of indivisible items
• scientific article; zbMATH DE number 6875266 (Why is no real title available?)
• Efficiency in sequential partnerships
• Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
• Possible and necessary allocations under serial dictatorship with incomplete preference lists
• Pexider's equation and aggregation of allocations
• How proper is sequential equilibrium?
• Parameterized complexity of manipulating sequential allocation
• A Refinement of Sequential Equilibrium
• Capacity allocation games without an initial sequence
• Fair choice sequences
• Manipulating picking sequences
• Approximate and strategyproof maximin share allocation of chores with ordinal preferences
• scientific article; zbMATH DE number 6902543 (Why is no real title available?)

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)