human
I am working on the file "Mining_of_Massive_Datasets/Advertising_on_the_Web/note.ipynb".
The first task is:
Lower-numbered advertisers cannot bid at first, and the budgets of hte higher-numbered advertisers will be exhausted eventually. All advertisers will end at $j$ round where 
$$B(\frac{1}{N} + \frac{1}{N-1} + \dotsb + \frac{1}{N-j+1}) \geq B$$
Solving this equation for $j$, we get $$j = N(1 - \frac{1}{e})$$
Thus, the approxiamte revenue obtained by the Balance Algorithm is $BN(1 - \frac{1}{e})$. Therefore, the competitive ration is $1 - \frac{1}{e}$.
8.4.7 The Generalized Balance Algorithm
With arbitrary bids and budgets Balance fails to weight the sizes of the bids properly. In order to make Balance work in more general situations, we need to make two modifications:

bias the choice of ad in favor of higher bids.

use the fraction of the budgets remaining.

We calculate $\Phi_i = x_i (1 - e^{-f_i})$, where $x_i$ is the bid of $A_i$ for the query, and $f_i$ is the fraction fo the unspent budget of $A_i$. The algorithm assignes the query to $\text{argmax} \Phi_i$. 
The competitive ration is $1 - \frac{1}{e}$.
8.4.8 Final Observations About the Adwords Problem

click-through rate.     
   multiply the bid by the click-through rate when computing the $\Phi_i$'s.

historical frequency of queries.    
   If $A_i$ has a budget sufficiently small, then we maintain $\Phi_i$ as long as we can expect that there will be enough queries remaining in the month to give $A_i$ its full budget of ads. 

Exercises  for Section 8.4
#maybe
8.5 Adwords Implementation
8.5.1 Matching Bids and Search Queries
If a search query occurs having exactly that set of words in some order, then the bid is said to match the query, and it becomes a candidate for selection.
Storing all sets of words representing a bid in lexicographic(alphabetic) order, and use it as the hash-key for the bid.
Can you write Python program for it?

=====
Give me a Python program to calculate $\Phi_i = x_i (1 - e^{-f_i})$, where $x_i$ is the bid of $A_i$ for the query, and $f_i$ is the fraction fo the unspent budget of $A_i$?
assistant
#Here is Python program to calculate $\Phi_i = x_i (1 - e^{-f_i})$, where $x_i$ is the bid of $A_i$ for the query, and $f_i$ is the fraction fo the unspent budget of $A_i$.

class advertiser:
    def __init__(self, name, bids):
        self.name = name
        self.bids = bids
    def get_info(self):
        return self.name, self.bids

advertisers = [
    advertiser('David', ['Google', 'email', 'product']),
    advertiser('Jim', ['SNS', 'Facebook', 'product']),
    advertiser('Sun', ['product', 'Google', 'email']),
]

bids_hash_table = dict()
for ad in advertisers:
    v, k = ad.get_info()
    k = [x.lower() for x in k]
    k = ' '.join(sorted(k))
    if k not in bids_hash_table: 
        bids_hash_table[k] = [v]
    else:
        bids_hash_table[k].append(v)
        
bids_hash_table

queries = [
    ('EMAIL', 'google', 'Product'),
    ('google', 'facebook', 'Product')
]

def handle_query(query):
    q = [x.lower() for x in query]
    q = ' '.join(sorted(q))
    print(q)
    try:
        print('Found: {}'.format(bids_hash_table[q]))
    except KeyError:
        print('No bids')   
        
for query in queries: 
    handle_query(query)
    print()