计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (22): 55-60.DOI: 10.3778/j.issn.1002-8331.1703-0233
彭晓芸1,陶永芊2
PENG Xiaoyun1, TAO Yongqian2
摘要: 对于给定的任意一个蛋糕分配算法,研究了玩家能从谎报中获取多大的利益。考虑两种类型的玩家:风险寻求玩家和风险厌恶玩家,并且把玩家的价值密度函数限制为分段常数。证明了风险寻求玩家和风险厌恶玩家均不能从谎报中获取更多利益。但如果只允许算法在蛋糕上切[n-1]刀,证明了玩家通过谎报能够拿到多出[Θ(n)]倍的利益。