- #1
mathlete
- 151
- 0
I have two sets of vectors:
A: a1, a2, a3... an
B: b1, b2, b3... bm
n > m and n/m is an integer, p.
Each vector bi has ranked, in order of preference, a set of vectors from A. For example, b1 may "prefer" a1, a9, and a10. The only constraint on this set is that each vector ai from A appears only p total times across all these ranked sets.
The problem is to find the set of vectors, C, such that:
Ci = ai[tex]\sum b_k[/tex]
where:
- The sum of bk is a sum of p vectors from B that listed ai as a preferred vector
- No vector Cj would increase in value by substituting in bk, where j is a value listed in b's preferences about i. Using the example of b1 above, if b1 was in C10, you could not switch it to C9 and increase its value (since 9 is ranked above 10).
The last condition is the one that's giving me a problem. This seems close to, but not exactly, a maximization problem.
Simple example (too simple because each b vector lists all c vectors as preferences which makes it somewhat trivial to solve, but gives an idea of what I'm trying to do):
a1 = { 1, 2, 1 }
a2 = { 2, 1, 2 }
b1 = { 5, 1, 2} Lists preferences as: a2, a1
b2 = { 1, 5, 2} Lists preferences as: a1, a2
b3 = { 8, 0, 6} Lists preferences as: a2, a1
b4 = { 0, 9, 0} Lists preferences as: a2, a1
Answer: c1: a1 paired with b1 and b3; c2: a2 paired with b2 and b4
A: a1, a2, a3... an
B: b1, b2, b3... bm
n > m and n/m is an integer, p.
Each vector bi has ranked, in order of preference, a set of vectors from A. For example, b1 may "prefer" a1, a9, and a10. The only constraint on this set is that each vector ai from A appears only p total times across all these ranked sets.
The problem is to find the set of vectors, C, such that:
Ci = ai[tex]\sum b_k[/tex]
where:
- The sum of bk is a sum of p vectors from B that listed ai as a preferred vector
- No vector Cj would increase in value by substituting in bk, where j is a value listed in b's preferences about i. Using the example of b1 above, if b1 was in C10, you could not switch it to C9 and increase its value (since 9 is ranked above 10).
The last condition is the one that's giving me a problem. This seems close to, but not exactly, a maximization problem.
Simple example (too simple because each b vector lists all c vectors as preferences which makes it somewhat trivial to solve, but gives an idea of what I'm trying to do):
a1 = { 1, 2, 1 }
a2 = { 2, 1, 2 }
b1 = { 5, 1, 2} Lists preferences as: a2, a1
b2 = { 1, 5, 2} Lists preferences as: a1, a2
b3 = { 8, 0, 6} Lists preferences as: a2, a1
b4 = { 0, 9, 0} Lists preferences as: a2, a1
Answer: c1: a1 paired with b1 and b3; c2: a2 paired with b2 and b4
Last edited: