2014 | OriginalPaper | Buchkapitel
Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations
verfasst von : Haris Aziz, Chun Ye
Erschienen in: Web and Internet Economics
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Cake cutting is one of the most fundamental settings in fair division and mechanism design without money. In this paper, we consider different levels of three fundamental goals in cake cutting: fairness, Pareto optimality, and strategyproofness. In particular, we present robust versions of envy-freeness and proportionality that are not only stronger than their standard counter-parts but also have less information requirements. We then focus on cake cutting with piecewise constant valuations and present three desirable algorithms:
CCEA (Controlled Cake Eating Algorithm)
,
MEA (Market Equilibrium Algorithm)
and
MCSD (Mixed Constrained Serial Dictatorship)
. CCEA is polynomial-time, robust envy-free, and non-wasteful. Then, we show that there exists an algorithm
(MEA)
that is polynomial-time, envy-free, proportional, and Pareto optimal. Moreover, we show that for piecewise uniform valuations, MEA and CCEA are group-strategyproof and are equivalent to Mechanism 1 of Chen et. al.(2013). We then present an algorithm
MCSD
and a way to implement it via randomization that satisfies strategyproofness in expectation, robust proportionality, and unanimity for piecewise constant valuations. We also present impossibility results that show that the properties satisfied by CCEA and MEA are maximal subsets of properties that can be satisfied by any algorithm.