Brute force computation of agent-item assignments for auction algorithms

Question

I am working with various auction algorithms to assess assignment of n items to n agents through a bidding mechanism, such that each agent is assigned to exactly one item, and each item is assigned to exactly one agent. I would like to assess performance of the algorithms I am testing by comparing them with a brute force approach. Comparison is via the sum of the value assignments, which I am trying to maximize.

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

What I would like to do is, given my agents and items vectors is create a data structure that holds every possible combination of member-item assignments. By my calculations there should be factorial(n) possible combinations. Thus in the example where n <- 3, the final structure should have 6 rows.

Here is a symbolic representation of what I want. Each row corresponds to a specific full assignment, where agents are columns and their corresponding items are cell values:

#     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

I am unclear the best way to achieve this generically for any positive value of n. I have tried expand.grid() but that doesn't seem to fit with what I want to achieve. Is there a function I can use for this or does anybody have any suggestions as to an algorithm I can implement to this end?

Answer 1

Expand grid won't work here, because it creates all possible combinations of agents and items, so it will spawn a combination where all agents get first item, for example. I suggest using permutations instead. It is enough to permute items, leaving agents on the same spots. I am using combinat package to generate permutations:

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

Each element of the list correspond to one possible permutation of items. So, 2 1 3 means that first agent gets second item, second agent gets first item, and third agent gets third item. To find out corresponding scores, we can subset our score matrix with permutations of boolean identity matrix:

#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

Finally, we compute individual scores and total score for all permutations and store the result in a neat 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