To give you an idea how serious we took our responsibility to try to do things differently here, and attempt to figure out the fairest way to parcel out the prizes this month, I thought that it might be useful to tell you a little bit about how prizes were assigned.
Rather than just give out prizes completely at random, we asked everyone who entered the drawing to submit a form rating the programs based on how badly they wanted to win each.
A custom program was then written to parse these submissions and search for the best way to assign prizes. What follows is a brief description of that program.
-mouser
Overview
This program is used to try to find a reasonable way to divide up a number of prizes among a number of users.
It used a simple optimization procedure which iterates through millions of simulated possible assignments of gifts in search of the best pairings.
Users submit a form indicating their preference for each prize; these forms are submitted by a php script over email.
The program parses these email messages and extracts user ratings for each program, as well as user comments and email addresses.
A prize file is parsed which described how many of each prize is available.
It also reads an option file of user weights, which allows us to decrease the weight for users who have won previous prizes, and increase the weights of users who have contributed greatly to the community but have not yet won anything.
Optimization proceeds interactively; at any time it can be paused and the current configuration as well as user preferences, weights, and comments can be evaluated manually.
The program outputs both a list of who has won each prize, and a set of emails, one to each person who has one, informing them of the prize they have won (or that they have not won anything). These can be imported into a mail program (like thebat!) and sent out en masse.
More on the Optimization Procedure
The optimization procedure is governed by a scoring function which can assign a score to each possible assignment of prizes. The cost is based on the sum (weighted) "happiness" of each user. Happiness is a function of the relative rating of the prize the user currently has compared to other prizes they have rated.
The program begins by assigns prizes randomly and then proceeds in iteration loops where two users are picked and their prizes are probabilistically exchanged based on the score differential and some noise.
The noise is decreases over time throughout a cycle and then resets; in this way the optimization process is able to explore some regions of the search space that involve making some non-beneficial swaps before a better assignment is found (i.e. this helps is escape situations where there is no single swap that improves the score, but there is a 3-way swap that does).
At the end of each annealing cycle the best scoring assignment is recalled and the process starts again.
