计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (22): 55-60.DOI: 10.3778/j.issn.1002-8331.1703-0233

• 理论与研发 • 上一篇    下一篇

无嫉妒蛋糕分配中的谎言

彭晓芸1,陶永芊2   

  1. 1.江西省税务干部学校,南昌 330029
    2.南昌大学 数学系,南昌 330031
  • 出版日期:2017-11-15 发布日期:2017-11-29

Misreporting in envy-free cake cutting

PENG Xiaoyun1, TAO Yongqian2   

  1. 1.Jiangxi Tax Cadre School, Nanchang 330029, China
    2.Department of Mathematics, Nanchang University, Nanchang 330031, China
  • Online:2017-11-15 Published:2017-11-29

摘要: 对于给定的任意一个蛋糕分配算法,研究了玩家能从谎报中获取多大的利益。考虑两种类型的玩家:风险寻求玩家和风险厌恶玩家,并且把玩家的价值密度函数限制为分段常数。证明了风险寻求玩家和风险厌恶玩家均不能从谎报中获取更多利益。但如果只允许算法在蛋糕上切[n-1]刀,证明了玩家通过谎报能够拿到多出[Θ(n)]倍的利益。

关键词: 蛋糕分配, 无嫉妒, 风险寻求, 风险厌恶

Abstract: It is studied that how much benefit an agent can obtain by his misreport in any envy-free cake cutting algorithm. Two types of agents, risk-seeking and risk-averse, are considered, and the value density function is restricted to piecewise constant. It can be showed that an agent cannot be benefited by misreporting if he is risk-seeking or risk-averse. If considering allocations with only [n-1] cuts on the cake, the utility gain from misreporting can be as much as [Θ(n)].

Key words: cake cutting, envy-free, risk-seeking, risk-averse