Abstract:

The advent of the Internet as a big playground for resource sharing among agents with very diverse interests, in varying degrees of competition and cooperation, and the emergence of Web as a ubiquitous socio-economic information repository has created a plethora of opportunities for commerce, as well as, a plenty of new design and complexity problems. For the first time, information scientists and engineers have the opportunity to investigate a purely organic computational artifact that seems to be as mysterious as our physical universe. In this dissertation, I investigate three fundamental research directions at the heart of this beautiful artifact.

First, I investigate market forces that would lead to the emergence of new classes of players in the Sponsored Search Advertising (SSA) market. I report a multi-fold diversification triggered by an inherent feature of this market, namely, capacity constraints , arising from the fact that there is a limit on the number of available advertisement slots, especially for the popular keywords . As a result, a significant pool of interested advertisers is left out. I present a comparative study of two scenarios motivated by capacity constraints--one where the additional capacity is provided by for-profit agents (or, mediators), who compete for slots in the original auction, draw traffic, and run their own sub-auctions , and the other, where the additional capacity is provided by the search engine itself, by essentially acting as a mediator and running a single combined auction . I observe that the single combined-auction model seems inferior to the mediator-based model and market becomes more capacity efficient in the latter.

Secondly, I initiate the study of another interesting aspect of SSA, namely the consequences of broad match --a feature where an ad of an advertiser can be mapped to a broader range of relevant queries, and not necessarily to the particular keyword(s) that ad is associated with. In spite of its unanimously believed importance, this aspect has not been formally studied yet, perhaps because of the inherent difficulty involved in formulating a tractable framework that can yield meaningful conclusions. I provide a natural and reasonable framework that allows us to make definite statements about the economic outcomes of broad match.

Finally, I consider the min-cost multicast problem (under network coding ) with multiple correlated sources where each terminal wants to losslessly reconstruct all the sources, and study the inefficiency brought forth by the selfish behavior of the terminals in this scenario by modeling it as a non-cooperative game among the terminals. The degradation in performance due to the lack of regulation is measured by the Price of Anarchy , which is defined as the ratio between the cost of the worst possible equilibrium and the socially optimum cost. The main result is that in contrast with the case of independent sources, the presence of source correlations can significantly increase the price of anarchy.

I use a blend of technical and conceptual tools that range from algorithms, complexity, convex optimization and information theory to game theory and economics.