Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
3 results
Search Results
Item Revenue Efficient Mechanisms for Online Advertising(2015) Khani, Mohammad Reza; Hajiaghayi, Mohammad; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Online advertising is an essential part of Internet and the main source of revenue for lots of web-centric companies such as search engines, news websites, Internet social networks, and other types of publishers. Online advertising happens in different settings and includes many challenges and constraints. A key component in each setting is the mechanism which selects and prices the set of winning ads. In this thesis, we consider the mechanism related issues arises in online advertising and propose candidate solutions with a special focus on the revenue aspect. Generalized Second Price (GSP) auction (the current mechanism of choice in online advertising) has appealing properties when ads are simple (text based and identical in size). But GSP does not generalize to richer ad settings, whereas truthful mechanisms, such as VCG do. Hence there are incentives for search platforms to migrate to truthful mechanisms, but a straight switch from GSP to VCG either requires all bidders instantly bid truthfully or incurs significant revenue loss. We propose a transitional mechanism which encourages advertisers to update their bids to their valuations, while mitigating revenue loss\footnote{It is the candidate mechanism to make the transition from GSP to VCG in Microsoft's Bing.}. The mechanism is equivalent to GSP when nobody has updated her bid, is equivalent to VCG when everybody has updated, and it has the same allocation and payments of the original GSP if bids were in the minimum symmetric Nash equilibrium. In settings where both GSP ads and truthful ads exist, it is easier to propose a payment function than an allocation function. We give a general framework for these settings to characterize payment functions which guarantee incentive compatibility of truthful ads, by requiring that the payment functions satisfy two properties. Next, we discuss about revenue monotonicity (revenue should go up as the number of bidders increases) of truthful mechanisms in online advertising. This natural property comes at the expense of social welfare - one can show that it is not possible to get truthfulness , revenue monotonicity, and optimal social welfare simultaneously. In light of this, we introduce the notion of Price of Revenue Monotonicity (\porm) to capture the loss in social welfare of a revenue monotone mechanism. We design truthful and revenue monotone mechanisms for important online advertising auctions with small \porm{} and prove a matching lower bound. Finally, we study how to measure revenue of mechanisms in the prior free settings. One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high values for the goods and a {\em competitive} outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to `block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of {\em core} in cooperative game theory where designing {\em core-selecting auctions} is well studied \cite{AM02,AM06,DM08,DC12}. While these auctions are known for having good revenue properties, they lack incentive-compatibility property desired for online advertising. Towards this, we define a notion of {\em core-competitive} auctions. We say that an incentive-compatible auction is $\alpha$-core-competitive if its revenue is at least $1/\alpha$ fraction of the minimum revenue of a core-outcome. We study designing core-competitive mechanisms for a famous online advertising scenario.Item Primal-Dual Techniques for Online Algorithms and Mechanisms(2015) Liaghat, Vahid; Hajiaghayi, MohammadTaghi; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)An offline algorithm is one that knows the entire input in advance. An online algorithm, however, processes its input in a serial fashion. In contrast to offline algorithms, an online algorithm works in a local fashion and has to make irrevocable decisions without having the entire input. Online algorithms are often not optimal since their irrevocable decisions may turn out to be inefficient after receiving the rest of the input. For a given online problem, the goal is to design algorithms which are competitive against the offline optimal solutions. In a classical offline scenario, it is often common to see a dual analysis of problems that can be formulated as a linear or convex program. Primal-dual and dual-fitting techniques have been successfully applied to many such problems. Unfortunately, the usual tricks come short in an online setting since an online algorithm should make decisions without knowing even the whole program. In this thesis, we study the competitive analysis of fundamental problems in the literature such as different variants of online matching and online Steiner connectivity, via online dual techniques. Although there are many generic tools for solving an optimization problem in the offline paradigm, in comparison, much less is known for tackling online problems. The main focus of this work is to design generic techniques for solving integral linear optimization problems where the solution space is restricted via a set of linear constraints. A general family of these problems are online packing/covering problems. Our work shows that for several seemingly unrelated problems, primal-dual techniques can be successfully applied as a unifying approach for analyzing these problems. We believe this leads to generic algorithmic frameworks for solving online problems. In the first part of the thesis, we show the effectiveness of our techniques in the stochastic settings and their applications in Bayesian mechanism design. In particular, we introduce new techniques for solving a fundamental linear optimization problem, namely, the stochastic generalized assignment problem (GAP). This packing problem generalizes various problems such as online matching, ad allocation, bin packing, etc. We furthermore show applications of such results in the mechanism design by introducing Prophet Secretary, a novel Bayesian model for online auctions. In the second part of the thesis, we focus on the covering problems. We develop the framework of "Disk Painting" for a general class of network design problems that can be characterized by proper functions. This class generalizes the node-weighted and edge-weighted variants of several well-known Steiner connectivity problems. We furthermore design a generic technique for solving the prize-collecting variants of these problems when there exists a dual analysis for the non-prize-collecting counterparts. Hence, we solve the online prize-collecting variants of several network design problems for the first time. Finally we focus on designing techniques for online problems with mixed packing/covering constraints. We initiate the study of degree-bounded graph optimization problems in the online setting by designing an online algorithm with a tight competitive ratio for the degree-bounded Steiner forest problem. We hope these techniques establishes a starting point for the analysis of the important class of online degree-bounded optimization on graphs.Item MECHANISM DESIGN WITH GENERAL UTILITIES(2012) Alaei, Saeed; Khuller, Samir; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis studies mechanism design from an optimization perspective. Our main contribution is to characterize fundamental structural properties of optimization problems arising in mechanism design and to exploit them to design general frameworks and techniques for efficiently solving the underlying problems. Not only do our characterizations allow for efficient computation, they also reveal qualitative characteristics of optimal mechanisms which are important even from a non-computational standpoint. Furthermore, most of our techniques are widely applicable to optimization problems outside of mechanism design such as online algorithms or stochastic optimization. Our frameworks can be summarized as follows. When the input to an optimization problem (e.g., a mechanism design problem) comes from independent sources (e.g., independent agents), the complexity of the problem can be exponentially reduced by (i) decomposing the problem into smaller subproblems, each one involving one input source, (ii) simultaneously optimizing the subproblems subject to certain relaxation of coupling constraints, and (iii) combining the solutions of the subproblems in a certain way to obtain an (approximately) optimal solution for the original problem. We use our proposed framework to construct optimal or approximately optimal mechanisms for several settings previously considered in the literature and to improve upon the best previously known results. We also present applications of our techniques to non-mechanism design problems such as online stochastic generalized assignment problem which itself captures online and stochastic versions of various other problems such as resource allocation and job scheduling.