Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm doing some work on a computer program that aids in ranking items which don't have a way to objectively compare to each other.

As it is now, it takes each item and pairs it up with each other item, and the user (subjectively) decides which item has more value. These individual comparisons are used to decide how the items are ranked (essentially each comparison an item "wins" earns it a "point").

Occasionally this can result in an inconsistency in one of two ways:

  • Item A is valued higher than B, B is valued higher than C, but when C and A are compared, the user places more value on item C.
  • Item A is valued higher than B when they are compared, but item B has more "points" than item A

There is a system in place to reach resolutions in these scenarios (the user manually assigns an order to any tied items).

The problem arises because there is a need to delete items at arbitrary times. This is trivial if the item has been deleted before the comparisons start, since we just remove it. However, once the comparisons start, the delete is replaced with a "soft delete", where the item still exists, but is ignored for all purposes other than ranking. This is to prevent changing the rankings/scores/consistency of any comparisons that have already been made.

My question is this:

If all of the comparisons have been performed and resulted in consistent results (no occurrences of the two cases listed above), is it possible for a deletion of an item (and by extension all comparisons involving that item) to create an inconsistency (or tie in score)?

While looking into changing the "soft delete" to a real delete (to make things easier down the road), I've verified that this will work for a small number of items, but will the consistency be preserved for an arbitrary number of items?

Another possibility I've considered is determining whether transitioning to state where two items are inconsistently ranked is possible by deleting a single item from a valid, consistent state, but I'm not entirely sure how to go about this direction of investigation.

share|cite|improve this question
How do you resolve the consistencies? I was about to answer with: "You have a directed acyclic graph and so deletes should be no problem". But I presume you might be aware of it already, and some information is probably missing. Care to give some examples? – Aryabhata Mar 30 '12 at 6:38
There are simple algorithms that can compute transitive closure. If you look for deletions, check out this paper with $O(mn)$ preprocessing and $O(1)$ query time. There is also a literature review in introduction, so if not that one, maybe some other thing will fit. – dtldarek Mar 30 '12 at 7:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.