How many queries does it take to find the best flight?

Question

I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and on a certain date) the search engine returns the cheapest flight in this subset. My goal using the search engine, however, is not so simple as restricting to a subset and finding the cheapest flight. Rather, I mentally place a certain dollar value on how much I am willing to pay extra for various options: e.g., willing to pay \$20 extra for nonstop, willing to pay \$50 extra for closer airport. I want to find the cheapest flight after these dollar values are taken into account.

This raises an algorithmic question: how many queries to the search engine does it take to find the best flight? We can formulate this as the following search problem:

• $X$ is a search space (set of flights);

• $f: X \to \mathbb{R}^+$ is an unknown price function, where $f(x)$ is the price of $x$;

• $g: X \to \mathbb{R}^+$ is a known additional cost to us, which we assume is a weighted sum of $k$ known indicator functions: $$ g(x) = \alpha_1 [x \in A_1] + \alpha_2 [x \in A_2] + \cdots + \alpha_k [x \in A_k], $$ where $\alpha_i \ge 0$ are weights and $[x \in A] = \begin{cases} 1 &\text{if } x \in A \\ 0 &\text{otherwise} \end{cases}$ is the Iverson bracket.

The problem: Determine $\min_{x \in X} (f(x) + g(x))$, using queries to an oracle which, on input any subset $X' \subseteq X$, returns $\min_{x \in X'} f(x)$ and $\arg\min_{x \in X'} f(x)$.

Question 1: As a function of $k$, how many queries to the oracle are needed in the worst case?

It can easily be done in $2^k$ queries: the sets $A_1, A_2, \ldots, A_k$ collectively partition $X$ into $2^k$ regions, so we can query on each subset. Is there a better algorithm in general?

Question 2: Assume that the actual minimum of $f(x) + g(x)$ falls into at most $k' \ll k$ of the indicator sets $A_i$ (so I'm not going to pay too much extra). As a function of $k$ and $k'$, how many queries to the oracle are now needed?

Answer 1

There are problem parameters where you need $2^k$ queries in the worst case. I'll prove this by giving an explicit example of an instance where you need $2^k$ queries.

Suppose $X = \{0,1\}^k$ and $A_i = \{x \in X : x_i = 1\}$ (this is without loss of generality in any case). Suppose $\alpha_i = 1/2^i$. Pick a single value $x^* \in X$, and define

$$f(x) = 1 - g(x) - 2^{-k-1} [x = x^*].$$

To any query set $X'$ we can associate a single element $m(X') = \arg \max_{x \in X'} g(x)$. Notice that the results of the query $X'$ depends only on $m(X')$, and there are $2^k$ possible values for $m(X')$. Thus we can identify each query with the value of $m(X')$, so effectively there are only $2^k$ different queries (where I consider two queries different if their value of $m(\cdot)$ differs; formally, consider the equivalence relation induced by $m(\cdot)$, choose one canonical representative for each equivalence class, and from here on we will assume that each query is one of these $2^k$ canonical representatives). Now I claim that out of these $2^k$ possible queries, there is only a single one that gives you any useful information about $x^*$. In particular, the only thing you learn about $x^*$, when you query on the set $X'$, is whether $x^* = m(X')$ or not. Why? If $x^* = m(X')$, then the oracle will return $x^*$, and you can recognize that this has happened by looking at the value of $f$. However, if $x^* \ne m(X')$, then the oracle will return $m(X')$ as well as the value of $f$ on that element, and that is something you could have computed on your own using your knowledge of $g$, so you have learned nothing about $x^*$ other than that it is different from $m(X')$. Moreover, there is only a single (canonical) set $X'$ where $x^* = m(X')$.

So, you have a search space of size $2^k$, and each query only lets you test a single candidate for $x^*$. It's like playing a game where I think of a secret number, and you can ask me questions like "is your number 17?" where you replace 17 with any number of your choice. It's easy to see that this game will require $2^k$ guesses in the worst case, and $2^{k-1}$ guesses on average.

So for that setting of weights, you can't do any better than $2^k$ queries.

(As a generalization, for your Question 2, this will require ${k \choose k'}$ queries in the worst case.)

---

In contrast, there also exist choices of weights where this allows an efficient solution. Consider the case where $\alpha_1=\cdots=\alpha_k=1$. Then you can query on the subsets $X'_0 = \{x \in X : g(x) = 0\}$, $X'_1 = \{x \in X : g(x)=1\}$, .., $X'_k= \{x \in X : g(x)=k\}$. Then, take the best of those results -- the one that has the smallest value of $f(x)+g(x)$. After doing $k+1$ queries, this is guaranteed to find you the optimal solution to the problem. As a generalization, if the set of sums $\{\sum_i c_i \alpha_i : c \in \{0,1\}^k\}$ has cardinality Q, then Q queries suffice to obtain the exact answer.

---

So, ultimately, the number of queries needed to the oracle depends on the weights. There are some choices where this might require many queries, and other choices where very few queries suffice.

One nice thing is that you can approximate the optimal value to within an additive error of $\delta$ using $(\sum_i \alpha_i)/\delta$ queries. In particular, query the subset $X' = \{x \in X : g(x) \le t\}$ for $t:=\delta,2\delta,3\delta,\dots,\sum_i \alpha_i$. Take the best solution found over all of those queries, and that will be at most $\delta$ worse than the optimum.