随机序列独裁算法与线性规划求解分配问题的疑问

问题背景 #

我偶然看到一个帖子，感到十分困惑。若要将N个对象分配给N个用户，已知每个用户对对象有排名偏好，目标是实现尽可能低的平均排名，我第一选择会是线性规划。但帖子中推荐了Random Serial Dictatorship（随机序列独裁算法），并称其能达到某种最优性。

测试案例与算法理解 #

我不确定这类贪心随机算法如何能保证最优解，因此进行了测试：
假设3位用户A、B、C对3套房屋H1、H2、H3的排名偏好如下：

user
house A B C
   H1 3 2 1
   H2 1 1 2
   H3 2 3 3

我们需要为每位用户分配一套房屋，使排名的平均值（或总和）最小。

我理解的随机序列独裁算法是：随机确定用户的选择顺序，让他们依次选择偏好的房屋。显然这种策略可能：

• 每次得到的排名总和不同
• 无法保证最优解

例如：

• 若A先选、B其次、C最后：A选H2（排名1），B只能选H1（排名2），C只能选H3（排名3），排名总和为6，平均值2；
• 若B先选、A其次、C最后：B选H2（排名1），A选H3（排名2），C选H1（排名1），总和4，平均值4/3。

R模拟随机序列独裁算法 #

# 3 users A, B, C want to buy a house each, chosen from H1, H2, H3.
# Their preferences are expressed by 'rank' (1 = first choice, 2 = second choice, etc).
d0 <- data.frame("user" = rep(c("A","B","C"), each = 3),
                "house" = rep(c("H1", "H2", "H3"), 3),
                "rank" = c(3,1,2,2,1,3,1,2,3)
                )

# 1. Assignment by random serial dictatorship

set.seed(232425)

all_ranks <- numeric(0)

for (i in 1:1000) {
  d <- d0
  # Create a random order of priority for the users.
  o <- setNames(sample(1:3), c("A","B","C"))
  # Let users choose their preferred house in turn, according to the created order.
  d["order"] <- o[d$user]
  d <- d[order(d$order, d$rank),]
  for (i in 1:2) {
    h <- d[i, "house"]
    d <- rbind(d[1:i,], d[(d$order > i) & (d$house != h),])
  }
  ranks <- d$rank
  ranks <- ranks[order(d$user)]
  all_ranks <- rbind(all_ranks, ranks)
  #print(d)
}

all_ranks <- setNames(as.data.frame(all_ranks), c("A","B","C"))
all_ranks_summary <- cbind("ID" = 1, setNames(stack(all_ranks), c("rank", "user")))
all_ranks_summary <- aggregate(ID ~ user + rank, all_ranks_summary, length)

barplot(ID ~ rank + user, all_ranks_summary, beside = TRUE, col = 2:4, legend.text = TRUE)
boxplot(rowMeans(all_ranks), main = "average rank")

模拟结果显示平均排名并非始终最小。

线性规划分配法实现 #

# 2. Assignment by linear programming

require(lpSolve)
cm <- xtabs(rank ~ house + user, d0)
lp.out <- lp.assign(cm)
lp.out$solution * cm

得到了最优解：

user
house A B C
   H1 0 0 1
   H2 0 1 0
   H3 2 0 0

疑问 #

1. 我是否误解了随机序列独裁算法？它能否通过某种方式保证最优解？
2. 线性规划分配法的计算复杂度是否几乎与暴力枚举所有组合相当？

我困惑的是，明明目标是「为每位用户分配一个选项，使所有用户的分配选项在其排名列表中的平均排名最小」，为何要选择一种看似无法达成该目标的算法，除非我完全误解了核心点。

内容的提问来源于stack exchange，提问作者user6376297