Abstract
We present a model of competition between web search algorithms and study the impact of such competition on user welfare. In our model, search providers compete for customers by strategically selecting which search results to display in response to user queries. Customers, in turn, have private preferences over search results and will tend to use search engines that are more likely to display pages satisfying their demands. Our main question is whether competition between search engines increases the overall welfare of the users (i.e., the likelihood that a user finds a page of interest). When search engines derive utility only from customers to whom they show relevant results, we show that they differentiate their results, and every equilibrium of the resulting game achieves at least half of the welfare that could be obtained by a social planner. This bound also applies whenever the likelihood of selecting a given engine is a convex function of the probability that a user's demand will be satisfied, which includes natural Markovian models of user behavior. On the other hand, when search engines derive utility from all customers (independent of search result relevance) and the customer demand functions are not convex, there are instances in which the (unique) equilibrium involves no differentiation between engines and a high degree of randomness in search results. This can degrade social welfare by a factor of the square root of $N$ relative to the social optimum, where $N$ is the number of webpages. These bad equilibria persist even when search engines can extract only small (but non-zero) expected revenue from dissatisfied users, and much higher revenue from satisfied ones.
Introduction
In classical economic theory, competition is generally viewed as a mechanism that drives quality up and prices down. However, the sponsored search market presents a unique challenge to this intuition. In this ecosystem, users do not pay for search services; rather, they are the product being sold to advertisers. This creates a potential misalignment between the search engine's objective (maximizing revenue) and the user's objective (finding relevant information). This paper investigates the conditions under which competition between search engines maximizes "user welfare," defined as the probability that a user finds a satisfying result.
The Search Engine Game Model
The authors model the interaction between $K$ search engines and $N$ possible webpages as a game-theoretic problem. Each user has a specific set of satisfying pages and a "patience threshold"—the maximum number of results they are willing to explore before abandoning the search.
The strategies for each search engine involve choosing a probability distribution over the orderings of webpages. The engine's utility is governed by a revenue parameter, $\beta$:
- Per-Click Revenue ($\beta = 0$): The engine only earns revenue if the user finds a relevant result and clicks on it.
- Per-Impression Revenue ($\beta = 1$): The engine earns revenue simply because the user visited the site, regardless of whether the search was successful.
Users choose which engine to use based on "selection rules"—functions that map the perceived quality of an engine to the probability of a user selecting it.
The Role of Specialization and Convexity
A critical finding of the research is the incentive for specialization. When revenue is tied strictly to user satisfaction ($\beta = 0$), search engines are incentivized to differentiate their results. By focusing on different niches, they can capture segments of the market that other engines might ignore. This specialization leads to high overall user welfare.
Furthermore, the authors identify "convexity" as a vital safety net. If a user's selection rule is convex—meaning they are disproportionately more likely to choose an engine as its quality increases—user welfare remains high even if engines are paid per-impression. The paper proves that natural Markovian models of user behavior, where users remain loyal to an engine until it fails them, are inherently convex and thus robust against welfare collapse.
The "Race to the Bottom"
The research highlights a darker scenario when selection rules are non-convex (such as proportional choice) and revenue is derived from impressions ($\beta = 1$). In these cases, engines often fall into a symmetric equilibrium where they all attempt to satisfy the "average" user by displaying the same popular results. This lack of differentiation is catastrophic for users with rare or specific needs.
Surprisingly, these "bad" equilibria are highly persistent. Even if an engine derives the vast majority of its revenue from clicks and only a tiny fraction from impressions, the non-specialized equilibrium can still dominate if the number of webpages ($N$) is large.
Key Results and Price of Anarchy
The study quantifies these effects using the Price of Anarchy (PoA), the ratio between the maximum possible social welfare and the welfare achieved in the worst-case competitive equilibrium:
- High Welfare Scenarios: When $\beta = 0$ or the selection rule is convex, the PoA is at most 2. Competition never degrades welfare by more than 50% compared to an omniscient social planner.
- Low Welfare Scenarios: When $\beta = 1$ and the selection rule is non-convex, the PoA can reach $\Omega(\sqrt{N})$ or $\Omega(K)$. In a web environment with millions of pages, this represents a massive loss of utility.
- Uniqueness of Inefficiency: For proportional selection rules with $\beta = 1$, the authors prove the existence of a unique symmetric equilibrium where every engine provides the exact same strategy, effectively nullifying the benefits of having multiple providers.
Conclusion and Future Directions
This research demonstrates that the benefits of competition in search are not guaranteed; they depend heavily on the underlying revenue models and user behaviors. While per-click models and loyal user bases naturally protect welfare, per-impression models can lead to a significant degradation of search quality.
Future work may expand this model to account for user inertia and brand loyalty beyond simple selection rules, the costs associated with crawling and indexing $N$ pages, and the impact of multi-query loyalty, where satisfaction today influences engine choice for different queries in the future.
Summary updated