Adversary strategies and lower bounds

Jump to:

The comparison oracle for linear orders

We are going to consider a linearly ordered set; we will assume that this set can be accessed only through an oracle that, given any pair u,v of distinct keys, announces that

Example 1: Merging sorted sequences

We propose to show that

merging a sorted sequence of n keys with another sorted sequence of n keys
takes at least 2n-1 calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that merges sequences u1, u2, ...., un and v1, v2, ...., vn such that

u1 < u2 < ....< un and v1 < v2 < ....< vn.
and that accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm: 
repeat ui and vj = the next pair of keys to be compared;
       if   i=j
       then answer "ui precedes vj"
       else if   i<j   
            then answer "ui precedes vj"
            else answer "vj precedes ui"
            end 
       end
end
Another way of describing this algorithm is saying If A calls the oracle fewer than 2n-1 times, then at least one of the 2n-1 pairs
(u1 and v1), (v1 and u2), (u2 and v2), ... , (vn-1 and un), (un and vn)
of keys that are adjacent in the input template remains uncompared, and so the answers provided by the oracle match not only this template, but also the template where the order of these two keys is switched.

For example, let us take n=5. If u2 and v2 remain uncompared, then the answers provided by the oracle match both templates

u1 < v1 < u2 < v2 < u3 < v3 < u4 < v4 < u5 < v5
and
u1 < v1 < v2 < u2 < u3 < v3 < u4 < v4 < u5 < v5.
If v3 and u4 remain uncompared, then the answers provided by the oracle match both templates
u1 < v1 < u2 < v2 < u3 < v3 < u4 < v4 < u5 < v5
and
u1 < v1 < u2 < v2 < u3 < u4 < v3 < v4 < u5 < v5.
And so on.

Jump to:

Example 2: Finding the maximum

We propose to show that

finding the maximum of n keys takes at least n-1 calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that finds the largest of keys u1, u2, ...., un and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm: 

for i = 1 to n do  candidate(ui)=YES end
repeat ui and uj = the next pair of keys to be compared;
       if   i<j   
       then answer "ui precedes uj"
            candidate(ui)=NO;
       else answer "uj precedes ui"
            candidate(uj)=NO;
       end 
end
Another way of describing this oracle is saying If A calls the oracle fewer than n-1 times, then at least two of the n keys uk have candidate(uk)=YES; one of these is un and the other has k<n. But then the answers provided by the oracle match not only the initial template, but also the template
u1 < u2 < ... < uk-1 < uk+1 < ... < un < uk.

Non-adaptive and adaptive oracle simulations

The two oracle simulations used in Examples 1 and 2 have a common feature: they start out with an input template,
u1 < v1 < u2 < v2 < ... < un < vn in Example 1
and
u1 < u2 < ... < un in Example 2,
and answer all questions as if the unknown input matched this template. Such oracle simulations might be called non-adaptive. More sophisticated oracle simulations construct the template incrementally in a way that depends on A's questions. One example of such an adaptive oracle simulation is coming up next.

Jump to:

Example 3: Finding the median

We propose to show that

finding the median of 2k+1 keys
takes at least 3k calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that finds the median of a set S of 2k+1 keys and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm: 

/* Initialization */
for all elements u of S 
do  rank(u) = "unassigned"; 
    candidate(u) = YES; 
end

/* Adaptive stage */
num_small = 0, num_large = 0;
while num_small < k and num_large < k 
do    u,v = the next pair of keys to be compared;
      if   rank(u) = "unassigned"
      then if   rank(v) = "unassigned"
           then num_small = num_small+1, rank(u) = num_small; 
                num_large = num_large+1, rank(v) = k+1+num_large; 
           else if   rank(v) < k+1 
                then num_large = num_large+1, rank(u) = k+1+num_large; 
                else num_small = num_small+1, rank(u) = num_small; 
                end 
           end 
      else if   rank(v) = "unassigned"
           then if   rank(u) < k+1 
                then num_large = num_large+1, rank(v) = k+1+num_large; 
                else num_small = num_small+1, rank(v) = num_small; 
                end 
           end 
      end 
      if   rank(u) < rank(v) 
      then answer "u precedes v"
           if k+1 < rank(u) then candidate(v) = NO end 
           if rank(v) < k+1 then candidate(u) = NO end 
      else answer "v precedes u"
           if k+1 < rank(v) then candidate(u) = NO end 
           if rank(u) < k+1 then candidate(v) = NO end 
      end 
end

/* Completing the template */
w = an element of S such that rank(w) = "unassigned";
rank(w) = k+1;
if   num_small = k 
then for all elements u of S 
     do  if   rank(u) = "unassigned" 
         then num_large = num_large+1, rank(u) = k+1+num_large; 
         end 
     end 
else for all elements u of S 
     do  if   rank(u) = "unassigned" 
         then num_small = num_small+1, rank(u) = num_small; 
         end 
     end 
end 

/* Non-adaptive stage */
repeat u,v = the next pair of keys to be compared;
       if   rank(u) < rank(v) 
       then answer "u precedes v";
            if rank(u) is at least k+1 then candidate(v) = NO end 
            if rank(v) is at most  k+1 then candidate(u) = NO end 
       else answer "v precedes u";
            if rank(v) is at least k+1 then candidate(u) = NO end 
            if rank(u) is at most  k+1 then candidate(v) = NO end 
       end 
end
Let us say that a call of oracle is useful if it brings about setting candidate(w)=NO for some w. In the adaptive stage, at least k calls of the oracle are countered by setting the value of rank(u) or rank(v) or both in such a way that
the smaller of rank(u), rank(v) is smaller than k+1 and
the larger   of rank(u), rank(v) is larger   than k+1;
none of these calls are useful. It follows that, as long as A calls the oracle fewer than 3k times, at most 2k-1 of these calls are useful, and so in the end at least two distinct elements w of S have candidate(w)=YES. In particular, there is an element x of S such that rank(x) is not k+1 and such that candidate(x)=YES. If rank(x) < k+1, then set 
    newrank(x) = k+1,
    newrank(y) = rank(y)-1  whenever rank(x) < rank(y) < k+2,  
    newrank(y) = rank(y)    for all other choices of y;
if rank(x) > k+1, then set 
    newrank(x) = k+1,
    newrank(y) = rank(y)+1  whenever k < rank(y) < rank(x),
    newrank(y) = rank(y)    for all other choices of y;
The answers that oracle has provided are consistent with the linear order defined by rank(.) as well as with the linear order defined by newrank(.). However, the median with respect to rank(.) differs from x, which is the median with respect to newrank(.).

Jump to:

Example 4: Finding a counterfeit coin

We have a number of coins which look alike; one of them is counterfeit and all of the remaining ones are genuine; all the genuine coins have an equal weight and the counterfeit coin is lighter. To find the counterfeit coin, we may use pharmacy scales as many times as necessary. In each weighing, we put an equal number of coins in each tray of the scales: the counterfeit is in the lighter set of coins or, in case the two sets are equally heavy, in the set of coins that has been left out.

We propose to show that

finding the counterfeit among n coins takes at least lg n / lg 3 weighings in the worst case.

For this purpose, consider an arbitrary algorithm A that finds the counterfeit in a set P of n coins and accesses the input only through the use of pharmacy scales. Let us simulate the outcomes of the weighings by the following algorithm: 

repeat L,R = the two sets of coins to be placed on the two trays;
       /* we have |L|=|R| */
       if   |L| > |P|/3
       then answer "L is lighter than R";
            P = L;
       else answer "L and R are of equal weight";
            remove both L and R from P;
       end 
       /* the counterfeit is in P */
end
After t iterations, the size of P is at least n / 3t . In particular, if t < lg n / lg 3, then the size of P is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct choices of the counterfeit.

Jump to:

Example 5: Sorting

We propose to show that

sorting n keys takes at least lg(n!) calls of the comparison oracle in the worst case.

For this purpose, consider an arbitrary algorithm A that sorts a set S of n keys and accesses the input only through the comparison oracle. Let us simulate the oracle by the following algorithm: 

P = the set of all linear orders on S;
repeat u,v = the next pair of keys to be compared;
       P(u) = the set of all linear orders in P where u precedes v;
       P(v) = the set of all linear orders in P where v precedes u;
       if   |P(u|) > |P(v)|
       then answer "u precedes v";
            P = P(u);
       else answer "v precedes u";
            P = P(v);
       end 
end
After t iterations, the size of P is at least n! / 2t . In particular, if t < lg(n!), then the size of P is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct linear orders on S.

Jump to:

A unified general setting and information-theoretic bounds

  1. We start out with a set P of inputs.
    • In Example 1, elements of P are all linear orders < on the set {u1, u2, ...., un, v1, v2, ...., vn} that satisfy
      u1 < u2 < ....< un and v1 < v2 < ....< vn.
    • In Example 2, elements of P are all linear orders < on the set {u1, u2, ...., un}.
    • In Example 3, elements of P are all linear orders < on the set S of 2k+1 elements.
    • In Example 4, elements of P are all the n coins suspected of being counterfeit.
    • In Example 5, elements of P are all linear orders < on the set S of n elements.

  2. The inputs in P can be accessed only indirectly, by means of an oracle.
    • In Examples 1, 2, 3, 5, the oracle is the comparison oracle.
    • In Example 4, the oracle is represented by the scales.
    In general, the oracle is specified by a set Q of questions and each question is a function f defined on P. Each access of an input x by the oracle amounts to choosing a question f in Q and asking the oracle for the answer f(x).
    • The comparison oracle is specified by questions fuv, one for each pair u,v of distinct elements of the linearly ordered set: fuv(<) is "u precedes v" whenever u < v and it is "v precedes u" whenever v < u.
    • The oracle of Example 4 is specified by questions fLR, one for each pair L,R of disjoint and equally sized subsets of P; fLR(x) is "L is lighter than R" whenever x is in L, it is "R is lighter than L" whenever x is in R, and it is "L and R are of equal weight" whenever x is in neither L nor R.

  3. With each input in P, we associate a single output.
    • In Example 1, the output associated with < is < itself.
    • In Example 2, the output associated with < is the largest (with respect to <) element of {u1, u2, ...., un}.
    • In Example 3, the output associated with < is the median (with respect to <) element of S.
    • In Example 4, the output associated with x is x itself.
    • In Example 5, the output associated with < is < itself.
    In general, let g denote the function that associates an output g(x) with each input x.

If A is an algorithm that attempts to determine g(x) of an unknown input x by calling the oracle as few times as possible, then an adversary strategy against A simulates the oracle in a way that attempts to keep g(x) unknown as long as possible. The non-adaptive adversary strategies are particularly simple: they have the form 

choose an element y of P;
repeat f = the next function in Q for which 
           the oracle is asked to return f(x);
       answer "f(y)";
end

The adaptive adversary strategies used in Examples 4 and 5 generalize as follows: 

repeat f = the next function in Q for which 
           the oracle is asked to return f(x);
       w = an element of f(P) that
       maximizes |{g(x) : x is in P and f(x)=w}|;
       answer "w";
       P = {x : x is in P and f(x)=w};
end
To analyze this algorithm, let us write
N = |g(P)| and k = max {|f(P)| : f is in Q} ;
In each iteration, let us enumerate the elements of f(P) as w1, w2, ...., wd and, for each of these elements wi, let us write
Pi = {x : x is in P and f(x)=wi}.
In this notation, w is a wj that maximizes |g(Pj)|; since the union of g(P1), g(P2), ...., g(Pd) is g(P), it follows that |g(Pj)| is at least |g(P)| / d, which is at least |g(P)| / k. Since this iteration replaces the current P by Pj, straightforward induction on t shows that
after t iterations, the size of g(P) is at least N / kt .
In particular, if t < lg N / lg k , then the size of g(P) is greater than 1, and so the answers that the oracle has provided are consistent with at least two distinct outputs. To put it differently,
determining the output takes at least lg N / lg k calls of the oracle in the worst case.
This lower bound, lg N / lg k, on the worst-case number of calls of the oracle, is known as an information-theoretic bound or a decision-tree bound.

Jump to:

Back to the table of contents of Vašek Chvátal's course notes