r - 用于拍卖算法的代理项分配的蛮力计算

Question

我正在使用各种 auction algorithms评估作业n items 到 n agents 通过投标机制，这样每个代理都被分配到一个项目，并且每个项目都分配给了一个代理。我想通过将它们与蛮力方法进行比较来评估我正在测试的算法的性能。比较是通过值(value)分配的总和，我试图最大化。

set.seed(1)

#Assume:
n <- 3
agents <- 1:3 # agent IDs
items <-1:3 # item IDs

# each agent has a preference score for each item
# create agent x item matrix w/ cells containing pref score
(m <- matrix(data = round(runif(9, 0, 1),3), nrow = n, ncol = n))

##       [,1]  [,2]  [,3]
## [1,] 0.266 0.908 0.945
## [2,] 0.372 0.202 0.661
## [3,] 0.573 0.898 0.629

# Given these sample data, here is one possible assignment
s <- data.frame(agent = agents, item = NA, score = NA)

# assign item & corresponding score to agent
s[1,"item"] <- 1; s[1,"score"] <- m[1,1]
s[2,"item"] <- 2; s[2,"score"] <- m[2,2]
s[3,"item"] <- 1; s[3,"score"] <- m[3,3]
s
##   agent item score
## 1     1    1 0.266
## 2     2    2 0.202
## 3     3    1 0.629


# The value/score of this particular assignment s
(total_score <- sum(s$score))
## [1] 1.097

我想做的是，根据我的代理和项目向量，创建一个数据结构来保存成员项目分配的所有可能组合。根据我的计算，应该有 factorial(n) 可能的组合。因此，在 n <- 3 的示例中，最终结构应该有 6 行。

这是我想要的符号表示。每行对应一个特定的完整分配，其中代理是列，它们对应的项目是单元格值:

#     a1    a2    a3 <- cols are agents
#     ______________
# s1 | 1     2     3 <- corresponds to assignment s above
# s2 | 1     3     2
# s3 | 2     1     3
# s4 | 2     3     1
# s5 | 3     2     1
# s6 | 3     1     2

对于 n 的任何正值，我不清楚一般实现此目的的最佳方法。我试过 expand.grid() 但这似乎不合适与我想要实现的目标。有没有我可以为此使用的函数，或者有人对我可以为此实现的算法有任何建议吗？

Answer 1

Expand grid 在这里不起作用，因为它会创建代理和项目的所有可能组合，因此它会生成一个组合，例如，所有代理都获得第一个项目。我建议改用排列。排列项目就足够了，将代理留在相同的位置。我正在使用 combinat 包来生成排列:

库(组合)
永久(1:3)


[[1]]
[1] 1 2 3

[[2]]
[1] 1 3 2

[[3]]
[1] 3 1 2

[[4]]
[1] 3 2 1

[[5]]
[1] 2 3 1

[[6]]
[1] 2 1 3

列表中的每个元素对应于一个可能的项目排列。因此，2 1 3 表示第一个代理人获得第二个项目，第二个代理人获得第一个项目，第三个代理人获得第三个项目。为了找出相应的分数，我们可以用 bool 单位矩阵的排列对我们的分数矩阵进行子集化:

#creating scores matrix    
n=3
m <- matrix(data = round(runif(9, 0, 1),3), nrow = n, ncol = n)     
#creating boolean identity matrix
E=matrix(as.logical(diag(1,n,n)),nrow=n,ncol=n)
m[E[,c(1,3,2)]] #this shows the scores of 1 3 2 item combination

#[1] 0.472 0.039 0.223

最后，我们计算所有排列的个人分数和总分，并将结果存储在一个整洁的 data.table 中:

library(data.table)
dt=data.table(items=permn(1:n))
dt[,scores:=lapply(items,function(x) m[E[,x]])]
dt[,totalScore:=lapply(scores,sum)]
dt
#       items            scores totalScore
#1: 1,2,3 0.472,0.239,0.517      1.228
#2: 1,3,2 0.472,0.039,0.223      0.734
#3: 3,1,2 0.658,0.064,0.223      0.945
#4: 3,2,1 0.658,0.239,0.994      1.891
#5: 2,3,1 0.326,0.039,0.994      1.359
#6: 2,1,3 0.326,0.064,0.517      0.907