From the algorithmic point of view — which is to say, paying attention to some mathematical abstraction, and ignoring how close it is to the real problem — I think you're okay. Edmonds's "blossom" algorithm (Canad. J. Math 1965) is a polynomial-time algoritm for solving the minimal-weight perfect-matching problem: given a score for how much "cognitive dissonance" each person would have playing each character (which could just be a distance between the high-dimensional points corresponding to their questionnaire responses, but more involved is ok too), the algorithm will produce the matching with the minimal total dissonance.
One glaring shortcoming for your real problem is that it can't take inter-assignment relationships into account: "Player A will be much happier playing role X if B plays Y than if C plays Y" is right out. (Mathematically, that would mean your objective function isn't linear in the matching.) I don't know how much you do that sort of thing.
There's some of that, although I don't think of it in quite that form. I think of it, rather, as a faction-matching problem.
I have clumps of players who want to play together, and in some cases players who really *don't* want to play together. (The latter often being the more important cases.) And I have "factions" in the game, groups that are relatively strongly associated with each other -- heavily overlapping in a good game, but each faction represents a natural grouping from the story POV. Just to make it worse, the factions are fuzzy on both sides, especially on the player side, since they are generally expressed unidirectionally. (That is, Player A says that he wants to be associated with B and C, and not with D; the others may say something quite different.)
Ideally, I want the player factions to align as best as I can with the character factions, so that players who want to be together overlap along some sort of factional lines (and will therefore naturally wind up interacting in the game), and those who don't much like each other will be off in different parts of the story.
This really is the hardest part of the problem, and the main thing that makes it tricky -- balancing the factional desires with the personal fits is pretty tricky, especially since the factions are fairly small: typically 3-7 on both sides of the equation, so my options are limited. So I'm trying to produce a best-fit not just on the individual player level, but for the groupings as well, introducing a sort of graph-solving problem on top of the individual fits...
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
One glaring shortcoming for your real problem is that it can't take inter-assignment relationships into account: "Player A will be much happier playing role X if B plays Y than if C plays Y" is right out. (Mathematically, that would mean your objective function isn't linear in the matching.) I don't know how much you do that sort of thing.
no subject
I have clumps of players who want to play together, and in some cases players who really *don't* want to play together. (The latter often being the more important cases.) And I have "factions" in the game, groups that are relatively strongly associated with each other -- heavily overlapping in a good game, but each faction represents a natural grouping from the story POV. Just to make it worse, the factions are fuzzy on both sides, especially on the player side, since they are generally expressed unidirectionally. (That is, Player A says that he wants to be associated with B and C, and not with D; the others may say something quite different.)
Ideally, I want the player factions to align as best as I can with the character factions, so that players who want to be together overlap along some sort of factional lines (and will therefore naturally wind up interacting in the game), and those who don't much like each other will be off in different parts of the story.
This really is the hardest part of the problem, and the main thing that makes it tricky -- balancing the factional desires with the personal fits is pretty tricky, especially since the factions are fairly small: typically 3-7 on both sides of the equation, so my options are limited. So I'm trying to produce a best-fit not just on the individual player level, but for the groupings as well, introducing a sort of graph-solving problem on top of the individual fits...