[EM] A question in classroom creation

[Paul Kislanko]

James G-A wrote,
> 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?

 
Michael A. 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?

I don't think there's any way ranked ballots could be applicable, and I'm
not sure any of the others would be either. 

To fill class one of four, you need to rank the preferences for each of
C(100,25) = the different ways you can select 25 objects from a collection
of 100 = more than 2.4 x 10^23 choices.

Then to fill the next one, you have C(75,25) = more than 5.25 x 10^19
choices, and for the third of four C(50,25) = more than 1.2 x 10^14 choices.


There's one way to fill the fourth of 4. But, you there are C(100,25) x
C(75,25) x C(50,25) ways to arrive at the final 25. That's more than 1.6 x
10^57 alternatives to rank.

Now, ranked ballots might be used in another way than to select the entire
class composition, but I think there'd need to be a "primary" stage that
uses truncated ballots - list the ten people you'd most like to be in class
with. for instance. Then sets could be formed of all pairs of students who
each listed the other, all pairs of pairs (quntuples) with intersections of
at least 2, all pairs of quintuples with intersections of at least 4) and so
un.

Find the largest N for which each member approves and is approved by at
least half the s