.. This file is part of the OpenDSA eTextbook project. See .. http://opendsa.org for more details. .. Copyright (c) 2012-2020 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. avmetadata:: :title: Adversarial Lower Bounds Proofs :author: Cliff Shaffer :institution: Virginia Tech :requires: :satisfies: :topic: Lower Bounds :keyword: Lower Bound Proof; Adversary Argument :naturallanguage: en :programminglanguage: N/A :description: Introduces the concept of an adversary argument for finding the lower bound for a problem. Uses the problem of finding the two largest values in an unsorted list as an example. Adversarial Lower Bounds Proofs =============================== Our next problem to examine will be finding the second largest in a collection of objects. Imagine that we are running a standard single-elimination tournament. We are going to overly simplify things by assuming that teams have a true "rank order", and that if one team is ranked "better" than another, it always wins any game between them. Now, even if we assume that the "best" team wins in every game, is the second best the one that loses in the finals? Not necessarily. We might expect that the second best team must lose to the best, but they might meet at any time. Let us go through our standard "algorithm for finding algorithms" by first proposing an algorithm, then a lower bound, and seeing if they match. Asymptotically, this is pretty much open-and-shut on what the cost will be, and not that interesting. However, unlike our analysis for most problems, this time we are going to count the **exact number** of comparisons involved, and attempt to minimize this count. After all, it takes a lot of work to have two teams play a match! A simple algorithm for finding the second largest is to first find the maximum (in :math:`n-1` comparisons), discard it, and then find the maximum of the remaining elements (in :math:`n-2` comparisons) for a total cost of :math:`2n-3` comparisons. Is this optimal? That seems doubtful, but let us now proceed to the step of attempting to prove a lower bound. .. topic:: Theorem The lower bound for finding the second largest value is :math:`2n-3`. .. topic:: Proof Any element that loses to anything other than the maximum cannot be second. So, the only candidates for second place are those that lost to the maximum. Function ``largest`` might compare the maximum element to :math:`n-1` others. Thus, we might need :math:`n-2` additional comparisons to find the second largest. This proof is wrong. It exhibits the :term:`necessary fallacy`: "Our algorithm does something, therefore all algorithms solving the problem must do the same." There is no reason why the maximum element must directly compare against every other element. Even the most basic standard maximum-finding algorithm does not require that this happen. This leaves us with a default best lower bounds argument at the moment being that finding the second largest must cost at least as much as finding the largest, or :math:`n-1`. Let us take another try at finding a better algorithm by adopting a strategy of divide and conquer. What if we break the list into halves, and run `largest` on each half? This costs :math:`n-2` comparisons. We can then compare the two winners (we have now used a total of :math:`n-1` comparisons), and remove the winner from its half. Another call to ``largest`` on the winner's half (minus the winner) yields its second best at a cost of :math:`n/2 - 1`. A final comparison against the winner of the other half gives us the true second place winner. The total cost is :math:`\lceil 3n/2\rceil - 2`. Is this optimal? What if we break the list into four pieces? The best would be about :math:`\lceil 5n/4\rceil`. What if we break the list into eight pieces? Then the cost would be about :math:`\lceil 9n/8\rceil`. But notice that as we break the list into more parts, comparisons among the winners of the parts becomes a larger concern. Looking at this another way, the only candidates for second place are losers to the eventual winner, and our goal is to have as few of these as possible. So we need to keep track of the set of elements that have lost in direct comparison to the (eventual) winner. We also observe that we learn the most from a comparison when both competitors are known to be larger than the same number of other values. So we would like to arrange our comparisons to be against "equally strong" competitors. We can do all of this with a :term:`binomial tree`. A binomial tree of height :math:`m` has :math:`2^m` nodes. Either it is a single node (if :math:`m=0`), or else it is two binomial trees of height :math:`m-1`, with one tree's root becoming a child of the other. Let's see how a binomial tree with eight nodes would be constructed. .. _BinomialTree: .. inlineav:: BinomialTreeCON ss :links: AV/SeniorAlgAnal/BinomialTreeCON.css :scripts: AV/SeniorAlgAnal/BinomialTreeCON.js :output: show :keyword: Lower Bounds Proofs; Adversary Arguments The resulting algorithm is simple in principle: Build the binomial tree for all :math:`n` elements, and then compare the :math:`\lceil \log n\rceil` children of the root to find second place. We could store the binomial tree as an explicit tree structure, and easily build it in time linear on the number of comparisons as each comparison requires one link be added. Because the shape of a binomial tree is heavily constrained, we can also store the binomial tree implicitly in an array, much as we do for a heap. Assume that two trees, each with :math:`2^k` nodes, are in the array. The first tree is in positions 1 to :math:`2^k`. The second tree is in positions :math:`2^k+1` to :math:`2^{k+1}`. The root of each subtree is in the final array position for that subtree. To join two trees, we simply compare the roots of the subtrees. If necessary, swap the subtrees so that tree with the the larger root element becomes the second subtree. This trades space (we only need space for the data values, no node pointers) for time (in the worst case, all of the data swapping might cost :math:`O(n \log n)`, though this does not affect the number of comparisons required). Note that for some applications, this is an important observation that the array's data swapping requires no comparisons. If a comparison is simply a check between two integers, then of course moving half the values within the array is too expensive. But if a comparison requires that a competition be held between two sports teams, then the cost of a little bit (or even a lot) of book keeping on a computer becomes irrelevent. Because the binomial tree's root has :math:`\log n` children, and building the tree requires :math:`n-1` comparisons, the number of comparisons required by this algorithm is :math:`n + \lceil \log n \rceil - 2`. This is clearly better than our previous algorithm. Is it optimal? **A small digression:** You might be wondering what the deal is with presenting a binomial tree here. It might seem confusing because you are probably used to seeing something like the tournament layout that shows the planned playing schedule for various players or teams in a single-elimination tounament. In particular, if the number of entities competing is :math:`2^n`, this tournament layout is a balanced tree, whereas the binomial tree is not balanced. The difference is that the tournament tree and the binomial tree are presenting two views of similar information. The tournament tree is showing, *a priori*, the playing schedule. The binomial tree is showing the results of competitions, such as what would come from executing the schedule from the tournament tree. In particular, onces a competitor loses, they don't play anymore (at least not in a regular single-elimination tournament). Since some competitors play less than others, the binomial tree is not balanced. **End digression.** We now go back to trying to improve the lower bounds proof. To do this, we introduce the concept of an :term:`adversary`. The adversary's job is to make an algorithm's cost as high as possible. Imagine that the adversary keeps a list of all possible inputs. We view the algorithm as asking the adversary for information about the algorithm's input, and the adversay will give an answer when asked. The adversary may never lie, in that any answer it gives must be consistent with all of its previous answers. But it is permitted to "rearrange" the input as it sees fit in order to drive the total cost for the algorithm as high as possible (so long as that rearranged input would be consistent with prior answers). In particular, when the algorithm asks a question, the adversary must answer in a way that is consistent with at least one remaining input. The adversary then crosses out all remaining inputs inconsistent with that answer. Keep in mind that there is not really an entity within the computer program that is the adversary, and we don't actually modify the program. The adversary operates merely as an analysis device, to help us reason about the program. As an example of the adversary concept, consider the standard game of Hangman. Player A picks a word and tells player B how many letters the word has. Player B guesses various letters. If B guesses a letter in the word, then A will indicate which position(s) in the word have the letter. Player B is permitted to make only so many guesses of letters not in the word before losing. In the Hangman game example, the adversary is imagined to hold a dictionary of words of some selected length. Each time the player guesses a letter, the adversary consults the dictionary and decides if more words will be eliminated by accepting the letter (and indicating which positions it holds) or saying that its not in the word. The adversary can make any decision it chooses, so long as at least one word in the dictionary is consistent with all of the decisions. In this way, the adversary can hope to make the player guess as many letters as possible. Before explaining how the adversary plays a role in our lower bounds proof for finding the second best, first observe that at least :math:`n-1` values must lose at least once. This requires at least :math:`n-1` compares. In addition, at least :math:`k-1` values must lose to the second largest value. That is, :math:`k` direct losers to the winner must be compared. There must be at least :math:`n + k - 2` comparisons. The question is: How low can we make :math:`k`? Call the **strength** of element ``A[i]`` the number of elements that ``A[i]`` is (known to be) bigger than. If ``A[i]`` has strength :math:`a`, and ``A[j]`` has strength :math:`b`, then the winner has strength :math:`a + b + 1`. The algorithm gets to know the (current) strengths for each element, and it gets to pick which two elements are compared next. The adversary gets to decide who wins any given comparison. What strategy by the adversary would cause the algorithm to learn the least from any given comparison? It should minimize the rate at which any element improves it strength. It can do this by making the element with the greater strength win at every comparison. This is a "fair" use of an adversary in that it represents the results of providing a worst-case input for that given algorithm. To minimize the effects of worst-case behavior, the algorithm's best strategy is to maximize the minimum improvement in strength by balancing the strengths of any two competitors. From the algorithm's point of view, the best outcome is that an element doubles in strength. This happens whenever :math:`a = b`, where :math:`a` and :math:`b` are the strengths of the two elements being compared. All strengths begin at zero, so the winner must make at least :math:`k` comparisons when :math:`2^{k-1} < n \leq 2^k`. Thus, there must be at least :math:`n + \lceil \log n\rceil - 2` comparisons. So our algorithm is optimal. Acknowledgement --------------- This page borrows heavily from presentation in Section 3.3 of *Compared to What?* by Gregory J.E. Rawlins.