[plt-scheme] Re: please help with generating random permutation

Hi Will,

> These ideas sound very good in practice.

I'm very glad to hear it! Because the algorithms are one thing, and
then in the "real world" sometimes everything looks so muddled that
whatever I might do seems imperfect and false in a way  :-)

>
> http://en.wikipedia.org/wiki/Fair_division

Thanks for the interesting link! As I see this can also go in the
direction of optimization (which seems to be the thing I am after
mostly, trying to consider individual preferences - right in the line
of, as it was written in the article, giving everyone MORE than 1/n).
It would be interesting, I think, to see how optimization and fairness
(especially in the more demanding definitions, like equitability) can
be reconciliated (up till now I've read about optimization just as
techniques, but I guess the optimization functions could be judged
according to equitability).

Ciao,
Sigrid



> > I'm  not sure what the OS approach would be? Do you mean process
> > scheduling algorithms?
>
> > About the randomness vs. fairness distinction (don't know which word
> > to use here, "dichotomy" surely not, but are they perhaps
> > orthogonal? There's surely quite some philosophical discussion of
> > this topic),  perhaps I should really have thought about this before
> > doing the coding.
>
> > In fact what I did "intuitively" was mixing both things up, starting
> > by shuffling the input list (so, starting with the "randomness"
> > side), but then taking into account the selection from the previous
> > week and trying to select people who had not been chosen then (so,
> > deviating in a direction of what I thought was "fairness"). Because
> > of this, unfortunately, the angry colleague really had a chance of
> > 1/3 of being drawn on Monday - but as he did not know why, he
> > attributed it to his name being first in the alphabet, this was bad
> > luck for me :-;
>
> > So I proposed (at least) the following possible changes (there's no
> > reactions yet):
> > - take out the taking into account of the previous week ("back to
> > random")
> > - add the preferences (less random, but hopefully more fair)
> > - do the drawings for 2 weeks at once, having as a constraint that
> > as few people as possible be drawn twice (given the fact that we
> > have less than 10 possible "victims"). Perhaps this is even the best
> > combination of randomness & fairness (it would be random but ALSO
> > seem quite fair I guess)
>
> > Ciao
> > Sigrid
>

On 13 Sep., 18:49, Will M Farr <f... at MIT.EDU> wrote:
> Sigrid,
>
> These ideas sound very good in practice.  (And I'm not entirely sure  
> what the "OS approach" is either, but perhaps, as you guessed,  
> Matthias is thinking of your workers as OS threads.)  You may not be  
> aware, but your problem is one of a class of problems that are an  
> active area of research in math:
>
> http://en.wikipedia.org/wiki/Fair_division
>
> You might enjoy reading about some of the algorithms mathematicians  
> have discovered to partition resources "fairly".
>
> Will
>
> On Sep 13, 2009, at 12:40 PM, keyd... at gmx.de wrote:
>
> > I'm  not sure what the OS approach would be? Do you mean process  
> > scheduling algorithms?
>
> > About the randomness vs. fairness distinction (don't know which word  
> > to use here, "dichotomy" surely not, but are they perhaps  
> > orthogonal? There's surely quite some philosophical discussion of  
> > this topic),  perhaps I should really have thought about this before  
> > doing the coding.
>
> > In fact what I did "intuitively" was mixing both things up, starting  
> > by shuffling the input list (so, starting with the "randomness"  
> > side), but then taking into account the selection from the previous  
> > week and trying to select people who had not been chosen then (so,  
> > deviating in a direction of what I thought was "fairness"). Because  
> > of this, unfortunately, the angry colleague really had a chance of  
> > 1/3 of being drawn on Monday - but as he did not know why, he  
> > attributed it to his name being first in the alphabet, this was bad  
> > luck for me :-;
>
> > So I proposed (at least) the following possible changes (there's no  
> > reactions yet):
> > - take out the taking into account of the previous week ("back to  
> > random")
> > - add the preferences (less random, but hopefully more fair)
> > - do the drawings for 2 weeks at once, having as a constraint that  
> > as few people as possible be drawn twice (given the fact that we  
> > have less than 10 possible "victims"). Perhaps this is even the best  
> > combination of randomness & fairness (it would be random but ALSO  
> > seem quite fair I guess)
>
> > Ciao
> > Sigrid
>
> > Am 13.09.2009 um 17:27 schrieb Shriram Krishnamurthi:
>
> >> I think Sigrid is saying that it wouldn't -- I believe that's what
> >> she's calling "uniformity".
>
> >> On Sun, Sep 13, 2009 at 10:34 AM, Matthias Felleisen
> >> <matth... at ccs.neu.edu> wrote:
>
> >>> Would some OS-style approach to office fairness help here?
>
> >>> On Sep 13, 2009, at 5:35 AM, keyd... at gmx.de wrote:
>
> >>>> Hi Thomas,
>
> >>>> I'm not so sure about the fairness. I think it's not always easy  
> >>>> to define
> >>>> what really IS fair in a given situation.
> >>>> Personally,  I would see fairness less in the line of "uniformity"
> >>>> (everyone gets the same amount of every piece, whether he likes a  
> >>>> piece or
> >>>> not) than of  "to each according to his needs" (not being a Marxist
> >>>> otherwise, this sentence I really like).
>
> >>>> For example in this situation, what I originally proposed was to  
> >>>> have
> >>>> everyone who wants state his preferences regarding weekdays (with  
> >>>> the amb
> >>>> operator I use, this would be easy to add). Up till now, there  
> >>>> was not much
> >>>> resonance for this, but perhaps it's because people tend to  
> >>>> assume they have
> >>>> similar preferences or needs - which in my experience need not be  
> >>>> true at
> >>>> all. E.g. in this example, I would in fact prefer to be ALWAYS  
> >>>> chosen on
> >>>> Mondays :-;
>
> >>>> Cheers,
> >>>> Sigrid
>
> >>>> Am 12.09.2009 um 21:37 schrieb Thomas Holubar:
>
> >>>>> Hi Sigrid!
>
> >>>>>> thanks a lot, this helped me very much (both in understanding  
> >>>>>> and in
> >>>>>> giving me the confidence to defend my code)!
>
> >>>>> I'm sure you'll have plenty nice - and entertaining -  
> >>>>> discussions! ;-)
>
> >>>>> So FWIW:
> >>>>> Your colleague likely complains that the schedule your program  
> >>>>> generates
> >>>>> is not *fair*. You in turn claim it to be *random*. And since  
> >>>>> both of you
> >>>>> are probably right there's little chance you'll eventually come  
> >>>>> to a
> >>>>> satisfactory conclusion.
>
> >>>>> Taking for granted that my understanding of fairness is  
> >>>>> compatible with
> >>>>> yours (and your colleague's) then fairness and randomness are  
> >>>>> incompatible.
>
> >>>>> YC explained this in more detail already.
>
> >>>>> So, if you want happy colleagues make it fair, not random.
>
> >>>>> Cheers,
> >>>>> Thomas
>
> >>>> _________________________________________________
> >>>> For list-related administrative tasks:
> >>>>http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> >>> _________________________________________________
> >>> For list-related administrative tasks:
> >>>http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> > _________________________________________________
> > For list-related administrative tasks:
> >http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>  PGP.sig
> < 1 KBAnzeigenHerunterladen
>
> _________________________________________________
>   For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme