Expected outcomes and manipulations in online fair division

DOI10.1007/978-3-319-67190-1_3MaRDI QIDQ5044849zbMATH OpenOpenAlexFDO

Authors Martin Aleksandrov, Toby Walsh

Publication date 2 November 2022

Published in KI 2017: Advances in Artificial Intelligence (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: Two simple and attractive mechanisms for the fair division of indivisible goods in an online setting are LIKE and BALANCED LIKE. We study some fundamental computational problems concerning the outcomes of these mechanisms. In particular, we consider what expected outcomes are possible, what outcomes are necessary, and how to compute their exact outcomes. In general, we show that such questions are more tractable to compute for LIKE than for BALANCED LIKE. As LIKE is strategy-proof but BALANCED LIKE is not, we also consider the computational problem of how, with BALANCED LIKE, an agent can compute a strategic bid to improve their outcome. We prove that this problem is intractable in general.

Recommendations

• Most competitive mechanisms in online fair division
• Monotone and Online Fair Division
• Truthful Fair Division
• Online max-min fair allocation
• A general strategy proof fair allocation mechanism

Cited in

(3)

• Most competitive mechanisms in online fair division
• Online max-min fair allocation
• Monotone and Online Fair Division

This page was built for publication: Expected outcomes and manipulations in online fair division

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