*Carbon copied from C_ECHO*
Hello All,
Don't let the subject scare you :), I need a solution to a problem which 
everyone can understand fairly easily:
As the only programmer member of Science Fiction and Fantasy Society at my 
university, I get all the programming jobs and I need to complete a Game 
Convetion program in the next few months.
A game convention is basically a tournement where there are some RPG games 
(in my case that would be between 30-50, but a solution must work for at 
least 100 games), and some players (between #games*3 and #games*6) which 
every game must be played if possible and every player must be assigned to a 
game.
The players are given the chance of selecting the game that they would like 
to play, they have sorted list of selections like:
SA02, SA06, SU12, SU03
where the player in question wants to play in SA02, if that is not possible, 
play in SA06 game,if that is not possible SU12 etc..
There are no weights associated with selections, ie. the player can not say 
that he wants to play in SA02 by 10 units, SA06 by 7 units and so on...
A player can be assumed to be more satisfied with the assignment if they are 
assigned to their first choice rather than second, or to their second choice 
rather than third and so on..
The goal is to assign the players such that total satisfaction is highest 
possible, or near to that . And *NO* restrictions should be violated.
Restriction list is as follows:
1) Each game has to have a minimum number of players to be able to played. 
This number changes from game to game. Every game must have at least that 
much players unless total player number is below the total required minimum 
player number(ie. convention does not get enough interest). If this rule 
should be violated, it would be done such that some games would have 0 
players (that is, cancelled) and the rule should be obeyed by remaining games 
and least possible number of games should be cancelled.
2) Each game has a, possibly different, maximum player number which the game 
can be played. No game should have more players assigned than this number. 
(There is no exception to this rule as we know ahead of time how many players 
we can accept.)
3) Every player should be assigned to exactly one game.
It is possible to assign a player to a game which is not his choice because 
of either all his selections are already full or a game can not find enough 
players among the ones that have selected it; in this case the player should 
be considered as 'least satisfied'.
I guess this is a np hard problem and cannot be solved exactly in a 
polinomial time, so any approximate solutions are welcome.
I surfed internet some and found sources related to this problem, but they 
all are under documented and specific to a problem.In my algoriths book, it 
gives some ideas about representing this problem as a network and maximizing 
flow but algorithm presented there does not allow weighted matching with 
one-to-many matchings.
I considered a NN solution similar to solution of TS problem with a Hoppfield 
network but could not really formulate it.
I'm currently working on an algorith where during the first phase which every 
game gets its minimum number of players, during the second stage all players 
get a game and during the third phase players are switched if their switch 
yields a better total satisfaction. I have formulated a general switching 
algorithm but it really takes too much time to discover possibilties of 
switching/rotating more than 4 players simultaneously. So I need a better 
solution.
Any ideas/sources (book or web site)?
If you send any source code in C or C++ I would be more than grateful :) Send 
them to berk@cclub.metu.edu.tr if they are too long to post here.
Thanks for reading so far...
Note: I'm neither a computer engineering nor a mathematics student, so please 
try to keep your answer simple in terms of jargon.
                                                Berk
--- GoldED/386 2.50.A0715 UNREG
---------------