wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Best non-transitive set item
        
(Message started by: tes on Dec 4th, 2003, 1:46am)
Title: Best non-transitive set item
Post by tes on Dec 4th, 2003, 1:46am
You have a group of items, each of which can be used as a
parameter to the function better (item1, item2), which will tell you which of the two items is "better" or that none of them are clearly "better". Find the best item in the group if possible given that the better function is non-transitive (i.e. if item1 is "better" than "item2" and "item2" is better than "item3", it does not imply that "item1" is better than "item3")
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 2:06am
if it's not transitive, define what 'best' means..
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 2:11am
Is there a time complexity that your looking for ??? (i.e. finding the element in O(n2) is trivial and even finding the element with O(n log(n)) expected time is quite easy, so are you looking for something better) ?
Title: Re: Best non-transitive set item
Post by TenaliRaman on Dec 4th, 2003, 2:16am
if there is an item i which is the best of the lot,

that means when i put (item j and item i) in the function it would return me item i. and also for some (item k and item i) the function would return me item i. when i input (item j and item k) into the function it would return me either item j or item k. This would mean the function is transitive and the premise is false ???
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 2:17am

on 12/04/03 at 02:06:51, towr wrote:
if it's not transitive, define what 'best' means..

towr hi,
I think that 'best' means the element that is "better"/equal (tes: "...none of them are clearly "better"...") in respect to all the other elements (assuming that such an element exists (tes: "...if possible...")) :P.
I hope I got it right !?
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 2:32am

on 12/04/03 at 02:16:14, TenaliRaman wrote:
This would mean the function is transitive and the premise is false ???

TenaliRaman hi,
I think there is no problem. I believe that tas meant that the function is non-transitive in the sense that it isn't obligatory that (if x<y and y<z [to] x<y). e.g. for every k (> 2) elements there might be a circle of "better" relations (and, of course, there might not be)...
Title: Re: Best non-transitive set item
Post by TenaliRaman on Dec 4th, 2003, 2:51am
Dudidu,
quoting tes here,

Quote:
..given that the better function is non-transitive..


If it had been as you said, then prolly it should have been "the better function is not necessarily transitive".
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 3:09am

on 12/04/03 at 02:51:53, TenaliRaman wrote:
If it had been as you said, then prolly it should have been "the better function is not necessarily transitive".
TenaliRaman you are right (tas should have written that "the better function is not necessarily transitive") but as I said, I believe that tas meant it (and his explanation...

Quote:
i.e. if item1 is "better" than "item2" and "item2" is better than "item3", it does not imply that "item1" is better than "item3"...
supports it).
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 3:14am
suppose we have three items,a,b,c
a > b, b > c, c > a
tell me, which is better?

rock,paper,scissors
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 3:23am

on 12/04/03 at 03:14:36, towr wrote:
suppose we have three items,a,b,c
a > b, b > c, c > a
tell me, which is better?
In such a case you should return (in my opinion) that there is no element that has the desired property (i.e. the 'best'). (I think that) the following quote of tas supports it:

Quote:
Find the best item in the group if possible...
Now its your turn... ;)
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 3:29am
or how about a,b,c,d,e

a > b,c,d
e > a
b=c=d=e

If you give each item 1 point for being better than another then clearly a wins with 3 points
If you give each item half a point for being better than item X + half a point for each item X is better than. Then
a get's 1.5 point, and e get's 2.. So e is now better

So how do we uniquely determine which of a set is better? When there transitivy you simply have a very best, when there's cycles you need to define what 'best' means.. Majority? Weighing?
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 3:36am

on 12/04/03 at 03:23:55, Dudidu wrote:
Now its your turn... ;)
It's allways possible.. It just depends on your criteria.
supose a>b>c>a
a scores 2 points over b
b scores 1 over c
c scores 1 over a
value of a = 2-1=1
value of c = 1-1=0
value of b = 1-2=-1

Something may be a bit better, or a lot better, or a hell of a lot better..
It really depends on how you define better/best
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 3:43am
Help !
I didn't imagine that there will be so many questions and I'll be the only one that tries to defend this problem...
However, I'm not going to break (yet ;))

Quote:
how about a,b,c,d,e...
For my opinion and as I posted earlier (quoting myself :D):

Quote:
I think that 'best' means the element that is "better"/equal in respect to all the other elements...
Thus, in your problem I would say e since e [ge] a,b,c,d and a > b,c,d and a < e...
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 3:52am

on 12/04/03 at 03:36:44, towr wrote:
...a scores 2 points over...b scores 1 over...c scores 1 over...
towr, I don't think this question deals with scores (or how big/small an element in relation to other element). It just deals with relations (i.e. you are given a set of relations and you need to find the 'best')...
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 3:54am
hmm.. yes.. I forgot about that..
But really, I'm sure you can imagine a case where that won't work..
Just try the whole set of webpages, and as 'better' relation use
webpage a better than b if b links to a
Now find the best webpage.. I very much doubt you'll find any page that every other page links to. But page ranking f.i. would be a way of finding the best page..
Title: Re: Best non-transitive set item
Post by Dudidu on Dec 4th, 2003, 4:02am

on 12/04/03 at 03:54:23, towr wrote:
I very much doubt you'll find any page that every other page links to...
towr, I agree with you but lets leave aside the practical things and deal with this hypothetical problem ;)...
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 4:25am
I don't really think you hypothetically need to have one hypothetical item being hypothetically better or equal to all the others hypothetically to be considered hypothetically best..

That just really really limiting, and uninteresting..
Sure if one item is better than all the others it's best..
But if an item is better than the majority of items, wouldn't that also be a sufficient condition?
Or if it's better than more items than any other? (top rank with 1 point for each item it is better as)
etc
So many possible ranking schemes..
Title: Re: Best non-transitive set item
Post by flan on Dec 4th, 2003, 8:18am
Don't forget what category this is. An interview q might not have a right or wrong answer, just rate how creatively and analytically you answer it.
So let's say that Better(a,b) is used to judge job applicants. First it categorizes them according to the job they're seeking and sorts them by the criteria of that job. When comparing applicants in different job categories, the primary criteria may be inapplicable, so it falls back on a tie-breaker criterion such as years of experience or IQ.
SO a and b are programmers. a knows C++ better than b.
But c is a salesman; his programming skill is irrelevant, so he's compared to the others by IQ. That's how you can end up with a>b>c>a. In that specific case there's no way to tell from the output who's the best.
But if you had 1,000 applicants it might be possible; first I'd try comparing each to every other one. If that failed because a lot of them are tied for first, Perhaps you could sort the output. I'm not sure any method would work in all situations, but I'd look for the largest subset which is completely transitive, and repeat using the remaining applicants to divide the thousand into categories as much as possible (of completely transitive subsets). Assume that the tie-breaker cross-category comparisons are less significant, and rescore. That might break the tie.
That method would presumably fail if there are many categories with few members in each being judged on the top priority criteria. In that case I think this method would end up sorting them first by that secondary criterion (IQ), and in this case I think that's the only criterion that could actually identify a "best."
Title: Re: Best non-transitive set item
Post by towr on Dec 4th, 2003, 9:07am
I'd think that if there were many different jobs that needed to be filled you'd select one applicant for each job (unless one can do multiple jobs cheaper/better)..
If you were limited to selecting one applicant the best would probably be the one that earns your company the most money. (So every other trait/skill is translated into a common currency, so that it's comparable)

And if all else fails, just pick whoever you like best.. Natural selection at work ;)
Title: Re: Best non-transitive set item
Post by TenaliRaman on Dec 4th, 2003, 9:22am
for the job thing,
i could solve it as a knapsack problem or an LPP even(and ppl ask me how higher mathematics applies to real life).
Title: Re: Best non-transitive set item
Post by flan on Dec 4th, 2003, 2:31pm
My point was not that I'd hire employees that way. That's just an example of one way a>b>c>a where the comparisons are not arbitrary or subjective and where further analysis could determine which comparisons used a first level, important comparison and which ones used a second level tie-breaker (for all we know, the tie-breaker could be shoe size, and we may not be told anything at all about what's being compared or how except that item1>item2). If the question can be answered then there must be some way to further analyze the output than simply a>b>c>a.
Title: Re: Best non-transitive set item
Post by James Fingas on Dec 10th, 2003, 5:57am
This is closely tied into the idea of the run-off election method. One way to do this is to first perform all comparisons, taking O(n^2), then throw away all "bad" candidates. Rerun the test, winnowing out some more "bad" candidates. Keep doing this until there are only two left, and pick the better of the two.

There are a number of ways you could determine which are "bad", but one way would be to throw away all below-average candidates. Another would be to throw away all candidates that did not get the highest score received.

Not efficient, but I think it addresses the problem.
Title: Re: Best non-transitive set item
Post by shmuha on Dec 10th, 2003, 8:38am
I am afraid that the answer to this riddle is "it is not possible to find the best item"

In order for a set to have best item it must posses the property "total(linear) ordering".

http://mathworld.wolfram.com/TotallyOrderedSet.html

One of the requierements for "total order" is the transitivity set property. Since the given set is non-transitive it is not possible for the set to be lineary orderer -> no best item can be found.
Title: Re: Best non-transitive set item
Post by towr on Dec 10th, 2003, 9:57am

on 12/10/03 at 08:38:15, shmuha wrote:
I am afraid that the answer to this riddle is "it is not possible to find the best item"
That's not true..
supopose a game between players a,b,c and d, scoring like in chess
round 1: a beats b,  c and d tie
round 2: a beats c,  b beats d
round 3: a loses to d,  c beats b

a has 2 points, b 1 point, c and d 1 1/2 points

a is better than b and c, but not better than d, yet still the overall best.
Title: Re: Best non-transitive set item
Post by TenaliRaman on Dec 10th, 2003, 12:38pm
Shmuha,
i said the same thing some post earlier (though in different words). As much as you are right (because i was  :) )but consider this as the employee selection problem which flan suggests wherein the transitivity is "not necessary".
Title: Re: Best non-transitive set item
Post by shmuha on Dec 12th, 2003, 7:39am
Can you find best item among the set of: rock,paper,scissors ?

No.

Why?

Because they are in non-transitive relation.
The same is true for the riddle.
Title: Re: Best non-transitive set item
Post by towr on Dec 12th, 2003, 2:25pm

on 12/12/03 at 07:39:37, shmuha wrote:
Can you find best item among the set of: rock,paper,scissors ?

No.

Why?

Because they are in non-transitive relation.
The same is true for the riddle.
Wow, one case were it doesn't work, and you immediately generalize to every case..
My one year old niece can't solve 1+1, so nobody can.. yep, seems to make sense :P

Non-transitivity does not exclude 'best-ness' of any item. Whereas transitivity on the other hand does guarantee it. But it's an implication, not an equality, so you can't just turn it around.
I allready gave a non-transitive example that does have a best 'item', so that proves there can be.

Note also that, although you're given one kind of 'better than'- relation, which happens not to be transitive, you can still (try and) use it to build another one that is.
Title: Re: Best non-transitive set item
Post by Eigenray on Dec 12th, 2003, 10:20pm

on 12/12/03 at 14:25:19, towr wrote:
Wow, one case were it doesn't work, and you immediately generalize to every case..

Everybody does that, towr.  I know I do.
Title: Re: Best non-transitive set item
Post by grimbal on Apr 30th, 2004, 2:13pm
First you need to define "the best".
a. x is best if x is better than y for each y.
b. x is best if x is better or equivalent to y for each y.
c. x is best by some evaluation of the number of items it is better than.

a. it is easy, take them each in turn, compare them 2 by 2 and keep the one (or none) that is better than the other.
b. it is also easy, except that you have to keep the set of items that are equivalent.  A possible optimisation would be a binary elimination where both players can be promoted and only items worse than some other are eliminated.
c. Is badly defined and needs more clarification.  For instance, if A is better than B and C is better than D, then should A be considered better than C if B is better than more items than D is, something like in the ranking for chess players?  And you have to decide how "impossible" the decision is.
Title: Re: Best non-transitive set item
Post by unknown on Jul 7th, 2005, 8:11pm

on 12/12/03 at 14:25:19, towr wrote:
Whereas transitivity on the other hand does guarantee it.


Sorry to nitpick, but transitivity does not guarantee a best item, especially if the best should be better than all items.  Here's a case.
a = b
a > c and d
b > b and d
c > d

On the other hand, you could consider a and b to be the best because both of them are >= then all items.

To solve this problem, I would use the celebrity algorithm.  Hey, this is the first time I see an application for this one.

First, let's go trying to find the easy case : looking for 1 item > than all other items.  This runs in O(n).

1) Set best = item 1.
2) for all items i from 2 to n do
3) compare item i to best item.
4) If Item i > currently best item, best = item i.
5) Go back to 2 until finished.


We should now verify if our best item is really the best.  To do this, we compare it to every other items.  If it is >, we have a best item, else it doesn't exist.

If we allow for >= instead of >, it gets a bit more complicated.  We need to keep a list of the best items.  Then when we compare a new item to the list, we might need to remove some of the items are < than the current one.

The worst case would probably O(n^2) if all items are equal.

I hope this makes a bit of sense.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board