I missed an obvious counterexample for the first preference-based extension. 34: A>B>C 33: B>C>A 33: C>A>B Now (A,B) ~> C since 34 + 33 > 50, {B, C} ~> A since 33 + 33 > 50 and {C, A} ~> B since 33 + 34 > 50 hence a cycle. So that relation (with that threshold) is unsuitable. If the first preference extension is to be salvaged, the threshold can't be 1/(k-|S|+1). -km