Spliddit 算法：用算法公平分摊房租与分配房间

Spliddit 是一种室友可以用来公平分摊房租的算法。 python spliddit.py [fast] fast 选项会跳过打字动画。 在大多数情况下，Spliddit 可以说是决定房租和房间分配的最佳方式。其他策略，比如协商和按面积分配，都存在严重缺陷。协商的问题在于，有些人比其他人更愿意也更有能力去协商。对那些擅长协商的人来说，这或许看起来是件好事，但房间分配上的不平等结果很容易引发嫉妒或怨恨。 按面积分配提供了客观性，但也可能导致不公平的结果。显然，住户可能在意房间的许多方面，而不只是面积，面积本身也并不与效用完全相关（它没有考虑公共空间，也没有考虑次线性效用）。而且，按平方英尺分配并不能解决房间分配的问题。 Spliddit 采取了第三种方法：使用算法。虽然算法方法可能显得不透明、没有人情味或随意，但 Spliddit 算法恰恰被设计成绝非如此！ Spliddit 通过保证以下性质来促进和谐： Spliddit 找到的结果是，没有人会想要别人的房间、并按对方支付的价格来付钱。 Spliddit 找到的结果是，你的满意度与别人满意度之间的差距被最小化。 即使某人有正的斤斤计较倾向，该程序在事前也是公平的。换句话说，室友们可以放心使用 Spliddit，不必担心它在房间或参与者方面存在偏袒。 顺带一提，“低斤斤计较”是最佳目标这一点可能并不显而易见。考虑到无论怎样大家总共花的钱都一样，所以没有免费的午餐——降低一个人的房租必然提高另一个人的房租，这样想可能更容易接受。 每位参与者都能为每个房间给出满足以下条件的价值： 这些价值加起来等于总房租 在这些价格下，参与者对任何房间都会同样满意 在这些价格下，参与者能负担得起任何房间。 可以信任参与者会诚实地报告自己的偏好，并且仅基于个人偏好。 参与者同意不经协商就接受算法的结果。 对于 N 位参与者，居住空间中的非共享部分可以划分为 N 个分区，这些分区不会因谁被分配到何处而改变。 进一步阅读 原始讲义：http://s3.amazonaws.com/arena-attachments/1980072/5c6f0b23e0f307a7096dbfb446d1f93b.pdf?1522603643