用于拍卖算法的代理项分配的蛮力计算
Brute force computation of agent-item assignments for auction algorithms
我正在与各种 auction algorithms 合作评估作业
n items 到 n agents 通过投标机制，这样每个代理都被分配给一个项目，每个项目都被分配给一个代理。我想通过将它们与蛮力方法进行比较来评估我正在测试的算法的性能。比较是
通过价值分配的总和，我试图最大化。
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() 但这似乎不合适
与我想要实现的目标。有没有我可以为此使用的函数，或者有人对我可以为此实现的算法有任何建议吗？
扩展网格在这里不起作用，因为它会创建代理和项目的所有可能组合，因此它会生成一个组合，例如，所有代理都获得第一个项目。
我建议改用排列。排列项目就足够了，将代理留在相同的位置。我正在使用 combinat 包来生成排列：
library(combinat)
permn(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 意味着第一个代理人获得第二个项目，第二个代理人获得第一个项目，第三个代理人获得第三个项目。
为了找出相应的分数，我们可以用布尔单位矩阵的排列对我们的分数矩阵进行子集化：
#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
我正在与各种 auction algorithms 合作评估作业 n items 到 n agents 通过投标机制，这样每个代理都被分配给一个项目，每个项目都被分配给一个代理。我想通过将它们与蛮力方法进行比较来评估我正在测试的算法的性能。比较是 通过价值分配的总和，我试图最大化。
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() 但这似乎不合适
与我想要实现的目标。有没有我可以为此使用的函数，或者有人对我可以为此实现的算法有任何建议吗？
扩展网格在这里不起作用，因为它会创建代理和项目的所有可能组合，因此它会生成一个组合，例如，所有代理都获得第一个项目。
我建议改用排列。排列项目就足够了，将代理留在相同的位置。我正在使用 combinat 包来生成排列：
library(combinat)
permn(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 意味着第一个代理人获得第二个项目，第二个代理人获得第一个项目，第三个代理人获得第三个项目。
为了找出相应的分数，我们可以用布尔单位矩阵的排列对我们的分数矩阵进行子集化：
#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