[EM] A question in classroom creation

[James Green-Armytage]

Michael,
	I think that you're problem is very interesting and fun! I remember that
when I was a kid, it was always a big deal who was in class with whom, and
there were plenty of hurt feelings over the years as a result. Here is the
first of what might be multiple proposals:

Proposal 1: Use a range ballot, e.g. integers from -3 to 3 inclusive. 
	Consider every possible arrangement of children into the 4 classes. 
	Give each possible arrangement a score as follows: Measure each child's
utility as the sum of his rating of all other children in the class. Sum
the utility scores for each child to find the total utility of the
arrangement.
	Choose the arrangement with the highest total utility. (If multiple
arrangements are tied, choose randomly between the arrangements with the
highest score.)

Commentary:
	This method, while perhaps optimal from a results point of view, seems
like it would take a lot of computing power. Given 100 children and 4
classrooms, how many possible arrangements are there? Is it somewhere
close to (4!)^25? So, 24^25? More than that? Yikes. I'm not much of a
computer expert, so someone else will have to tell me whether that's a
prohibitive computational cost.
	Is there a computationally cheaper method with a similar effect?

my best,
James	
http://fc.antioch.edu/~james_green-armytage/voting.htm



Michael Rouse wrote:	
>Here's a rather different (and more complicated) voting problem than
>usual:
>
>In the interest of classroom harmony, a school decides to let the 
>children vote for which classmates they want in their home room. 
>Assuming each class is the same size, what kind of ballot and what 
>method of grouping students should be used? Also, should top-ranked 
>(most liked) or bottom-ranked (most disliked) preference take precedence?
>
>Some possibilities and problems that come to mind:
>Ranked ballots  -- difficult to make it a "secret ballot," but it gives 
>a fine-grained preference listing.
>Approval/Anti-Approval -- rating classmates as approved, disapproved, 
>and unknown. Also difficult to use with secret ballot. Probably the 
>easiest to use.
>Classroom grouping -- let students make their own classroom groupings 
>(kind of like the districting problem), possibility of secret ballot but 
>a *lot* of work.
>
>If an example is needed -- and just to give some numbers -- let's say 
>the school has 4 teachers and 100 students in the same grade, which 
>would give 25 students per home room. For extra credit (heh), if they 
>can also vote for which teacher they want, what would be the fairest way 
>of resolving ties if more than one class prefers the same teacher?
>
>This would also have an interesting application in voting district 
>creation -- if voters can choose which precincts go into a voting 
>district, what would be the fairest way of doing so?
>
>