1  20
Next
Number of results to display per page
 Roughgarden, Tim, author.
 First edition.  San Francisco, CA : Soundlikeyourself Publishing LLC, [2018]
 Description
 Book — xi, 209 pages : illustrations ; 23 cm
 Online
Engineering Library (Terman)
Engineering Library (Terman)  Status 

Stacks


QA76.9 .A43 R682 2017 PT.2  Unknown 
 Roughgarden, Tim, author.
 San Francisco, CA : Soundlikeyourself Publishing LLC, [2017]
 Description
 Book — xii, 204 pages : illustrations ; 23 cm
 Summary

"Algorithms are the heart and soul of computer science. Their applications range from network routing and computational genomics to publickey cryptography and database system implementation. Studying algorithms can make you a better programmer, a clearer thinker, and a master of technical interviews. Algorithms Illuminated is an accessible introduction to the subjecta transcript of what an expert algorithms tutor would say over a series of oneonone lessons. Part 1 covers asymptotic analysis and bigO notation, divideandconquer algorithms and the master method, randomized algorithms, and several famous algorithms for sorting and selection."Back cover.
 Online
Engineering Library (Terman)
Engineering Library (Terman)  Status 

Stacks  
QA76.9 .A43 R68 2017  Unknown 
 Roughgarden, Tim author.
 Cambridge : Cambridge University Press, 2016.
 Description
 Book — 1 online resource : digital, PDF file(s).
 Summary

 1. Introduction and examples
 2. Mechanism design basics
 3. Myerson's Lemma
 4. Algorithmic mechanism design 34
 5. Revenuemaximizing auctions
 6. Simple nearoptimal auctions
 7. Multiparameter mechanism design
 8. Spectrum auctions
 9. Mechanism design with payment constraints
 10. Kidney exchange and stable matching
 11. Selfish routing and the price of anarchy
 12. Network overprovisioning and atomic selfish routing
 13. Equilibria: definitions, examples, and existence
 14. Robust priceofanarchy bounds in smooth games
 15. Bestcase and strong Nash equilibria
 16. Bestresponse dynamics
 17. Noregret dynamics
 18. Swap regret and the Minimax theorem
 19. Pure Nash equilibria and PLScompleteness
 20. Mixed Nash equilibria and PPADcompleteness.
 (source: Nielsen Book Data)
(source: Nielsen Book Data) 9781107172661 20160823
4. Selfish routing and the price of anarchy [2005]
 Roughgarden, Tim.
 Cambridge, Mass. : MIT Press, c2005.
 Description
 Book — ix, 196 p. : ill. ; 24 cm.
 Summary

The author studies the loss of social welfare cause by selfish, uncoordinated behavior in netwoks. He quantifies the price of anarchy and also discusses several methods for improving the price of anarchy with centralised control.
(source: Nielsen Book Data) 9780262182430 20160528
 Online
SAL3 (offcampus storage)
SAL3 (offcampus storage)  Status 

Stacks  Request 
TK5105.5 .R697 2005  Available 
5. Tradeoffs in cost sharing [2009]
 Sundararajan, Mukund.
 2009.
 Description
 Book — xii, 136 p.
 Online

 Search ProQuest Dissertations & Theses. Not all titles available.
 Google Books (Full view)
SAL1&2 (oncampus shelving), SAL3 (offcampus storage), Special Collections
SAL1&2 (oncampus shelving)  Status 

Stacks  Request 
3781 2009 S  Unknown 
SAL3 (offcampus storage)  Status 

Stacks  Request 
3781 2009 S  Available 
Special Collections  Status 

University Archives  Request onsite access 
3781 2009 S  Inlibrary use 
 MoskAoyama, Damon.
 2008, c2009.
 Description
 Book — x, 115 p.
 Online

 Search ProQuest Dissertations & Theses. Not all titles available.
 Google Books (Full view)
SAL1&2 (oncampus shelving), SAL3 (offcampus storage), Special Collections
SAL1&2 (oncampus shelving)  Status 

Stacks  Request 
3781 2009 M  Unknown 
SAL3 (offcampus storage)  Status 

Stacks  Request 
3781 2009 M  Available 
Special Collections  Status 

University Archives  Request onsite access 
3781 2009 M  Inlibrary use 
Online 7. An Empirical Analysis of Return on Investment Maximization in Sponsored Search Auctions [2008]
 Auerbach, Jason (Author)
 200805
 Description
 Book
 Summary

In this thesis I empirically investigate whether bidders are maximizing their return on investment (ROI) across multiple keywords in sponsored search auctions. I classify bidders based on the minimum perturbations that must be applied to their bids in order for various conditions to be satisfied. I show that a large fraction of bidders in the Yahoo Webscope first price data set may be following ROIbased strategies.
In this thesis I empirically investigate whether bidders are maximizing their return on investment (ROI) across multiple keywords in sponsored search auctions. I classify bidders based on the minimum perturbations that must be applied to their bids in order for various conditions to be satisfied. I show that a large fraction of bidders in the Yahoo Webscope first price data set may be following ROIbased strategies.  Collection
 Undergraduate Theses, School of Engineering
8. Algorithmic game theory [2007]
 New York, NY : Cambridge University Press, 2007.
 Description
 Book — xxi, 754 p. : ill. ; 26 cm.
 Summary

 Introduction Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani Part I. Computing in Games:
 1. Basic solution concepts and computational issues Eva Tardos and Vijay V. Vazirani
 2. Algorithms for equilibria Christos Papadimitriou
 3. Equilibrium computation for games in strategic and extensive form Bernhard von Stengel
 4. Learning, regret minimization and correlated equilibria Avrim Blum and Yishay Mansour
 5. Graphical games Michael J. Kearns
 6. Cryptography and game theory Yevgeniy Dodis and Tal Rabin
 7. Combinatorial algorithms for market equilibria Vijay V. Vazirani
 8. Computation of market equilibria by convex programming Bruno Codenotti and Kasturi Varadarajan Part II. Algorithmic Mechanism Design:
 9. Introduction to mechanism design (for computer scientists) Noam Nisan
 10. Mechanism design without money James Schummer and Rakesh V. Vohra
 11. Combinatorial auctions Noam Nisan and Liad Blumrosen
 12. Computationally efficient approximation mechanisms Ron Lavi
 13. Profit maximization in mechanism design Jason Hartline and Anna Karlin
 14. Distributed algorithmic mechanism design Joan Feigenbaum, Michael Schapira and Scott Shenker
 15. Cost sharing Kamal Jain and Mohammad Mahdian
 16. Online mechanisms David C. Parkes Part III. Quantifying the Inefficiency of Equilibria:
 17. Introduction to the inefficiency of equilibria Tim Roughgarden and Eva Tardos
 18. Routing games Tim Roughgarden
 19. Inefficiency of equilibria in network formation games Eva Tardos and Tom Wexler
 20. Selfish loadbalancing Berthold Vocking
 21. Efficiency loss and the design of scalable resource allocation mechanisms Ramesh Johari Part IV. Additional Topics:
 22. Incentives and pricing in communication networks Asuman Ozdaglar and R. Srikant
 23. Incentives in peertopeer systems John Chuang, Michal Feldman and Moshe Babaioff
 24. Cascading behavior in networks: algorithmic and economic issues Jon Kleinberg
 25. Incentives and information security Ross Anderson, Tyler Moore, Shishir Nagaraja and Andy Ozment
 26. Computational aspects of information markets David M. Pennock and Rahul Sami
 27. Manipulationresistant reputation systems Eric Friedman, Paul Resnick and Rahul Sami
 28. Sponsored search auctions Sebastien Lahaie, David M. Pennock, Amin Saberi and Rakesh V. Vohra
 29. Algorithmic issues in evolutionary game theory Michael Kearns and Siddharth Suri.
 (source: Nielsen Book Data)
(source: Nielsen Book Data) 9780521872829 20160528
 Online
Science Library (Li and Ma)
Science Library (Li and Ma)  Status 

Stacks  
QA269 .A43 2007  Unknown 
Online 9. Resource allocation and decision making for groups [2018]
 Suksompong, Warut, author.
 [Stanford, California] : [Stanford University], 2018.
 Description
 Book — 1 online resource.
 Summary

Social choice theory concerns the design and analysis of methods for aggregating possibly conflicting individual preferences to reach a collective decision in a satisfactory manner. The discipline dates from Condorcet's voting paradox in the 18th century, and its paradigm was significantly influenced by Arrow's seminal work in the 1950s. While classical social choice theory focuses on the existence and nonexistence of aggregation methods that satisfy certain axioms, over the past two decades computer scientists have studied the discipline from a computational perspective, leading to an active research area of computational social choice. This dissertation presents results of the classical flavor as well as those applying complexity concepts and algorithmic techniques. In the first part, we consider resource allocation settings. We depart from the usual framework in which each recipient of a bundle of items is represented by a single preference, and assume instead that each interested party consists of agents who may have different preferences on the items. We study the problem of assigning a small subset of indivisible items to a group of agents so that the subset is agreeable to all agents, and derive bounds on the size of such a set under various informational and computational assumptions. We also investigate fairness guarantees in the allocation of indivisible items among groups. While the problem is more challenging than in the traditional setting with individual agents, we show that it is nevertheless possible to obtain positive results using asymptotic analysis and approximation. In the second part, we study decision making problems, where our goal is to choose the "best" alternatives from a given set of alternatives. We demonstrate that the bipartisan set, a method for selecting the best alternatives from a tournament proposed in the 1990s, is the unique method that satisfies a number of desirable properties. In addition, we consider issues related to choosing winners in sports competitions. We show that if tournament organizers have the freedom to determine the bracket of a singleelimination tournament, they can often make their favorite player win the tournament. We also tackle the problem of scheduling asynchronous roundrobin tournaments, in which all games take place at different times, and propose schedules that perform well with respect to measures concerning the quality and fairness of the tournament.
 Also online at

Online 10. Theoretical models for practical problems : dynamic data structures, hierarchical clustering, and modern parallel computing [2018]
 Wang, Joshua R., author.
 [Stanford, California] : [Stanford University], 2018.
 Description
 Book — 1 online resource.
 Summary

In theoretical computer science, we take practical problems, design abstractions to model them, and then prove what efficient algorithms can or cannot compute in these models. Naturally, our choice of abstraction can have ramifications on what we can formally prove and how applicable our theorems are to the original problems we had in mind. Ideally, our model attains both of these goals simultaneously. This is perhaps best illustrated by its quintessential success story: the Turing machine, a model of computation known for its universality and usefulness in proofs. In this dissertation, we examine three instances where choice of model features prominently. Dynamic Data Structures. Lower bounds for data structures typically proceed by reduction to communication complexity, where we first convert a hypothetical efficient data structure into an efficient protocol for a communication game, and then rule out the possibility of the latter. We present a novel online communication model and then use it to prove robust data structure lower bounds. In particular, we show that a hypothetical efficient data structure with asymptotically faster time per operation than classical data structures for these problems is so inaccurate that it might as well be ignoring updates and answering queries randomly. Hierarchical Clustering. We study several popular algorithms that people use to perform hierarchical clustering. We first consider a previously proposed objective function for hierarchical clustering, but we demonstrate that in the worstcase, these algorithms are poor approximations to this objective. We then propose a related objective function, and show that one method, average linkage agglomerative clustering, is a constantapproximation to our objective, while the other algorithms remain poor approximations. Modern Parallel Computation. We consider the question of how efficiently algorithms implemented on parallel computation platforms such as MapReduce and Hadoop can solve central problems in motivating application domains. To do so, we introduce a new abstract model for massively parallel computation, where the key limitation is the input size of each machine and the fundamental metric is the number of synchronous rounds needed to perform a particular computation. We show how efficient computations in our model can be represented as lowdegree polynomials over the reals, allowing us to translate lower bounds from Boolean function analysis into parallel computation bounds. We also show that our lower bounds are the best that one could hope for; asymptotically better lower bounds would separate P from NC1.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2018 W  Inlibrary use 
Online 11. Learning and incentives in computer science [electronic resource] [2017]
 Schrijvers, Okke.
 2017.
 Description
 Book — 1 online resource.
 Summary

In this thesis we look at topics in algorithmic game theory, with influences from learning theory. We use tools and insights from game theory to look at areas in computer science, such as machine learning and the bitcoin blockchain, that have been developed incognizant of incentives for selfish behavior. Here we 1) show that there are incentives to behave in a way that's harmful for the system, 2) give mechanisms where the incentives for the individual and group are aligned, and 3) measure how harmful (having to account for) selfish behavior is. In particular we study the problem of online prediction with expert advice, where we show that when experts are selfish and care about their reputation, the design of incentive compatible algorithms is tightly coupled to strictly proper scoring rules. We give algorithms that have good regret guarantees, and we prove that it is not possible to match regret guarantees for honest experts. For Bitcoin, we show that the way rewards are shared in mining pools can lead to miners strategically hiding work to improve their payout. This holds true even in the absence of outside options for miners, such as other pools or solo mining. We give a novel reward sharing function that does not have perverse incentives, and analyze its performance analytically and through simulations. On the other hand we look at how data can be used in a variety of game theory applications. We ask the questions 1) how can we use data to replace standard informational assumptions in auction theory, 2) how much data do we need for good results in this area, 3) how can we use data to learn about the utilities of agents when we observe behavior, and finally (as misrecorded data may lead algorithms astray) 4) how can we find anomalies in a data set in an unsupervised manner? For the first two questions we look at position auction environments where we give the first computationally efficient algorithm for i.i.d.~bidders with irregular value distributions, that achieves revenue arbitrarily close to optimal using polynomial samples. Due to the low sample complexity, our approach leads to a noregret algorithm in the online setting. To address the third question, we give a computationally efficient algorithm that computes, given a correlated equilibrium (which may be a pure or mixed Nash equilibrium), the set of utilities that are consistent with it. Finally, we give an unsupervised anomaly detection algorithm that runs in a stream, and we show its performance through experiments on real and synthetic data.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2017 S  Inlibrary use 
Online 12. Theoretical foundations for practical problems [electronic resource] : network analysis, algorithm selection, and interaction design [2016]
 Gupta, Rishi Vijay.
 2016.
 Description
 Book — 1 online resource.
 Summary

Characterizing algorithm performance is a tricky business. For most problems, any given algorithm is going to have widely varying performance over the possible inputs to the problem, and the performance of any two reasonable algorithms will be uncomparable over the input space. Over the last forty years, worstcase analysis has emerged as the dominant theoretical framework for resolving this issue: score each algorithm by the input on which it does the worst, and then rank algorithms by their score. While inspiring many of the algorithms in use today, worstcase analysis runs into a natural block when the "worstcase" inputs are not representative of the inputs typically seen in practice. In this dissertation, we look at several problem domains facing this issue, and introduce frameworks that go beyond worstcase analysis. The first domain is graph algorithms on social networks. We define a new class of graphs, "triangledense" graphs, which encompasses all known models of social networks, but is restricted enough to exclude worstcase inputs. One can then employ the following strategy for ranking social network algorithms: score each algorithm by the input from this class on which it does the worst, and then rank algorithms by their score. We present novel clustering and cliquecounting algorithms demonstrating that this framework is both mathematically tractable and a useful restriction of the worstcase framework. The second domain we consider is applicationspecific algorithm selection, including parameter tuning. In this setting an engineer has a set of candidate algorithms and a list of representative inputs from an application, and needs to pick an algorithm to run on future inputs from the application. Intuitively, the less complex the set of algorithms, the fewer representative inputs the engineer needs to do a good job. We introduce two new models that allow one to formally reason about this tradeoff. Finally, we look at a problem that arises in understanding how users are interacting with an application, given traces of their behavior. We model the problem as that of recovering a mixture of Markov chains, and show surprising conditions under which one can recover the mixture.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2016 G  Inlibrary use 
Online 13. Sharing costs to optimize network equilibria [electronic resource] [2015]
 Kollias, Konstantinos.
 2015.
 Description
 Book — 1 online resource.
 Summary

Congestion games are a fundamental class of applications in the study of strategic behavior in large systems. In congestion games, selfish individuals act as consumers of resources at local parts of the system. These individuals typically obey their own selfinterests and will not necessarily adhere to the prescriptions of a socially optimal solution. Imposing centralized control upon these individuals is infeasible, but the deployment of simple rules at a local level can limit the discrepancy between the individual goals of the system users and the global optimization objectives of the system designer. Such rules can be abstracted as cost sharing methods that distribute the joint cost on a resource among those who generate it. This thesis aims to present a comprehensive study of cost sharing as a means of decentralized control in congestion games and their generalizations.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2015 K  Inlibrary use 
 Bhawalkar, Kshipra.
 2013.
 Description
 Book — 1 online resource.
 Summary

Gametheoretic equilibria model natural outcomes of selfish behavior. The concept of the "Price of Anarchy (POA)" captures how well gametheoretic equilibria approximate the socially optimal outcome. In this dissertation, we consider the POA in three different models, as a function of different design parameters and equilibrium concepts. We first consider weighted congestion games where players compete to share resources. The cost of a resource depends on the total weight of the players using that resource and players are allowed to use only certain subsets of the resources. Routing games are a canonical example of such games. We provide a precise characterization of the POA as a function of the resource cost functions. We also explore how the POA is affected by the structure of the permitted strategies for the players. Our bounds apply to pure Nash, mixed Nash, correlated, and coarsecorrelated equilibria. We next consider opinion formation games, where players in a social network choose opinions to express to minimize the cost of disagreement with their neighbors' opinions and their own intrinsic beliefs. We obtain bounds on the POA with respect to the pure Nash, mixed Nash, and correlated equilibria. We show that the POA is always at most 2 when the cost functions are convex. We provide a more detailed characterization of the the Price of Anarchy as a function of the costs of disagreement. Finally, we consider combinatorial auctions with item bidding. In this model, several goods are sold simultaneously in independent auctions to buyers who have different values for different bundles of goods. We bound the pure Nash and the BayesNash POA when the individual singleitem auctions are second price auctions and buyers' valuations over the bundles are subadditive. We provide the first explicit gap between the worst case pure Nash and BayesNash POA. We also consider how the pure Nash POA varies as a function of the payment rule in the underlying singleitem auction.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2013 B  Inlibrary use 
 Chen, Daniel.
 2012.
 Description
 Book — 1 online resource.
 Summary

Large scale collections of trajectory data, such as GPS traces, are becoming widely available, and there are many emerging applications that involve understanding and extracting information from such data. Much of this data is noisy, contains outliers, and has missing parts — raising many difficult statistical, geometric, and algorithmic problems. In this thesis, we study methods to extract structure from such data and to organize the data in a fashion that facilitates further analysis. We start by presenting a datadriven framework for smoothing trajectory data. Our framework, which can be viewed of as a generalization of the classical moving average technique, naturally leads to practical algorithms for various smoothing objectives. The second part of this thesis is about understanding the essential structure underlying the collections of trajectories. This topic is similar in spirit to dimension reduction or manifold learning in classical data analysis. Under reasonable similarity measures, collections of trajectories have significantly different structure than that of traditional data sets. In particular, simplifying assumptions such as the belief that the data lies on a lowdimensional manifold are no longer reasonable. Instead, it is often the case that the underlying space of the trajectories has a one dimensional stratified (or branching) structure. Our goal is then to reconstruct such a branching structure from a collection of input trajectories. Using sampling assumptions modeled after previous geometric reconstruction work in the computational geometry community, we formulate a new algorithm for reconstructing branching structures with guarantees. To make such a structure useful, we study the problem of map matching, which enables the branching structure to be used efficiently as a coordinate system. In particular, we extend recent results for Fréchet distance computation to obtain an algorithm for map matching with respect to the Fréchet distance that runs in nearlinear time under reasonable models for the input trajectory and the map, which improves on previous nearquadratic running times. Finally, we also study a version of our reconstruction problem in a more general setting with weaker assumptions and develop an algorithm that is oblivious to ordering information of the individual trajectories in the data set, and even to the embedding of the data. Here, we explore a new model of reconstruction we call "metric reconstruction" that lies somewhere between geometric and topological reconstruction. In this model, we reconstruct the topology and distances of the underlying structure, while being somewhat oblivious to its extrinsic embedding. This algorithm allows the reconstruction of branching structures to be extended to settings where ordering information may not be reliable, or even to more abstract instances where an embedding is not available.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2012 C  Inlibrary use 
Online 16. Algorithms for bipartite matching problems with connections to sparsification and streaming [electronic resource] [2012]
 Kapralov, Mikhail.
 2012.
 Description
 Book — 1 online resource.
 Summary

The problem of finding maximum matchings in bipartite graphs is a classical problem in combinatorial optimization with a long algorithmic history. Graph sparsification is a more recent paradigm of replacing a graph with a smaller subgraph that preserves some useful properties of the original graph, perhaps approximately. Traditionally, sparsification has been used for obtaining faster algorithms for cutbased optimization problems. The contributions of this thesis are centered around new algorithms for bipartite matching problems, in which, surprisingly, graph sparsification plays a major role, and efficient algorithms for constructing sparsifiers in modern data models. In the first part of the thesis we develop sublinear time algorithms for finding perfect matchings in regular bipartite graphs. These graphs have been studied extensively in the context of expander constructions, and have several applications in combinatorial optimization. The problem of finding perfect matchings in regular bipartite graphs has seen almost 100 years of algorithmic history, with the first algorithm dating back to K\"onig in 1916 and an algorithm with runtime linear in the number of edges in the graph discovered in 2000. In this thesis we show that, even though traditionally the use of sparsification has been restricted to cutbased problems, in fact sparsification yields extremely efficient {\em sublinear time} algorithms for finding perfect matchings in regular bipartite graphs when the graph is given in adjacency array representation. Thus, our algorithms recover a perfect matching (with high probability) without looking the whole input. We present two approaches, one based on independent sampling and another on random walks, obtaining an algorithm that recovers a perfect matching in $O(n\log n)$ time, within $O(\log n)$ of output complexity, essentially closing the problem. In the second part of the thesis we study the streaming complexity of maximum bipartite matching. This problem is relevant to modern data models, where the algorithm is constrained in space and is only allowed few passes over the input. We are interested in determining the best tradeoff between the space usage and the quality of the solution obtained. We first study the problem in the single pass setting. A central object of our study is a new notion of sparsification relevant to matching problems: we define the notion of an $\e$matching cover of a bipartite graph as a subgraph that approximately preserves sizes of matchings between every two subsets of vertices, which can be viewed as a 'sparsifier' for matching problems. We give an efficient construction of a sparse subgraph that we call a 'matching skeleton', which we show is a linearsize matching cover for a certain range of parameters (in fact, for $\e> 1/2$). We then show that our 'sparsifier' can be applied repeatedly while maintaining a nontrivial approximation ratio in the streaming model with vertex arrivals, obtaining the first $11/e$ deterministic onepass streaming algorithm that uses linear space for this setting. Further, we show that this is in fact best possible: no algorithm can obtain a better than $11/e$ approximation in a single pass unless it uses significantly more than quasilinear space. This is a rather striking conclusion since a $11/e$ approximation can be obtained even in the more restrictive online model for this setting. Thus, we show that streaming algorithms can get no advantage over online algorithms for this problem unless they use substantially more than quasilinear space. Our impossibility results for approximating matchings in a single pass using small space exploit a surprising connection between the sparsifiers that we define and a family of graphs known as \rs graphs. In particular, we show that bounding the best possible size of $\e$covers for general $\e$ is essentially equivalent to determining the optimal size of an $\e$\rs graph. These graphs have received significant attention due to applications in PCP constructions, property testing and additive combinatorics, but determining their optimal size still remains a challenging open problem. Besides giving matching upper and lower bounds for single pass algorithms in the vertex arrival setting, we also consider the problem of approximating matchings in multiple passes. Here we give an algorithm that achieves a factor of $1e^{k}k^{k}/k!=1\frac{1}{\sqrt{2\pi k}}+o(1/k)$ in $k$ passes, improving upon the previously best known approximation. In the third part of the thesis we consider the concept of {\em spectral sparsification} introduced by Spielman and Teng. Here, we uncover a connection between spectral sparsification and spanners, i.e. subgraphs that approximately preserve shortest path distances. This connection allows us to obtain a quasilinear time algorithm for constructing spectral sparsifiers using approximate distance oracles and entirely bypassing linear system solvers, which was previously the only known way of constructing spectral sparsifiers in quasilinear time. Finally, in the last part of the thesis we design an efficient implementation of cutpreserving sparsification in a streaming setting with edge deletions using only one pass over the data.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2012 K  Inlibrary use 
Online 17. Auction design with robust guarantees [electronic resource] [2012]
 Description
 Book — 1 online resource.
 Summary

In this dissertation, we design and analyze auctions that are more practical than those in the traditional auction theory in several settings. The first setting is the search advertising market, in which the multikeyword sponsored search mechanism is the dominant platform. In this setting, a search engine sells impressions generated from various search terms to advertisers. The main challenge is the sheer diversity of the items for sale  the number of distinct items that an advertiser wants is so large that he cannot possibly communicate all of them to the search engine. To alleviate this communication problem, the search engine introduces a bidding language called broad match. It allows an advertiser to submit a single bid for multiple items at once. Popular models such as the GSP auction do not capture this aspect of sponsored search. We propose a model, named the broad match mechanism, for the sponsored search platform with broad match keywords. The analysis of the broad match mechanism produces many insights into the performance of the sponsored search platform. First, we identify two properties of the broad match mechanism, namely expressiveness and homogeneity, that characterize the performance of the mechanism. Second, we show that, unlike the GSP auction, the broad match mechanism does not necessarily have a pure equilibrium. Third, we analyze two variants of the broad match mechanism, the payperimpression variant and the payperclick variant. Under a common model of advertiser valuation, we show that the payperclick variant is more economically efficient than the payperimpression variant. This result justifies the prevalent use of the payperclick scheme in search advertising. In addition, the broad match mechanism can be viewed as an auction of which the bidding language is crucial to its performance. In the second part, we design and analyze approximately revenuemaximizing auctions in singleparameter settings. Bidders have publicly observable attributes and we assume that the valuations of bidders with the same attribute are independent draws from a common distribution. Previous works in revenuemaximizing auctions assume that the auctioneer knows the distributions from which the bidder valuations are drawn \cite{M81}. In this dissertation, we assume that the distributions are a priori unknown to the auctioneer. We show that a simple auction which does not require any knowledge of the distributions can obtain revenue comparable to what could be obtained if the auctioneer had the distributional knowledge in advance. Our most general auction has expected revenue at least a constant fraction of that of the optimal distributionaldependent auction in two settings. The first setting concerns arbitrary downwardclosed singleparameter environments and valuation distributions that satisfy a standard hazard rate condition, called monotone hazard rate. In this setting, the expected revenue of our auction is improved to a constant fraction of the expected optimal welfare. In the second setting, we allow a more general class of valuation distributions, called regular distributions, but require a more restrictive environment called the matroid environment. In our results, we assume that no bidder has a unique attribute value, which is obviously necessary with unknown and attributedependent valuation distributions. Our auction sets a reserve price for a bidder using the valuation of another bidder who has the same attribute. Conceptually, our analysis shows that even a single sample from a distribution  another bidder's valuation  is sufficient information to obtain nearoptimal expected revenue, even in quite general settings. In the third part, we design and analyze auctions that approximately maximize residual surplus in singleparameter settings. Residual surplus is defined to be the surplus less the sum of the bidders' payments. The guarantee of our auction is of the same type as the auctions in the second part, i.e., its expected residual surplus is a fraction of that of the optimal distributionaldependent auction. Instead of the nouniqueattribute assumption made in the second setting, in this setting we assume that the distributions of bidder valuations can be ordered, that is, the distribution of the first bidder stochastically dominates that of the second bidder and the distribution of the second bidder stochastically dominates that of the third and so on. In every downwardclosed stochasticdominance environment where the distributions of bidder valuations satisfy the monotone hazard rate condition, our auction produces residual surplus that is a $\Omega(\tfrac{1}{\log n})$ fraction of the optimal residual surplus, without taking any bid (although it makes use of the ordering), where $n$ is the number of bidders.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2012 D  Inlibrary use 
 Yan, Qiqi.
 2012.
 Description
 Book — 1 online resource.
 Summary

We propose to study revenuemaximizing auctions in the priorindependent analysis framework. The goal is to identify a single auction mechanism for all underlying valuation distributions, so that its expected revenue approximates that of the optimal mechanism tailored for the underlying distribution, under standard weak conditions on the distribution. We use the priorindependent analysis framework to analyze natural and practical auction mechanisms such as welfaremaximization with reserve prices, limiting supply to induce artificial scarcity, sequentially posting prices, etc. Our framework allows us to argue that these simple mechanisms give nearoptimal revenue guarantee in a very robust manner.
 Also online at

 Korolova, Aleksandra.
 2012.
 Description
 Book — 1 online resource.
 Summary

In today's digital age, online services, such as search engines and social networks, collect large amounts of data about their users and their users' online activities. Largescale mining and sharing of this data has been a key driver of innovation and improvement in the quality of these services, but has also raised major user privacy concerns. This thesis aims to help companies find ways to mine and share user data for the purpose of furthering innovation while all the while protecting their users' privacy, and to motivate and help them reason about the privacyutility tradeoffs using a rigorous quantifiable definition of privacy. To achieve this we explore examples of privacy violations, propose privacypreserving algorithms, and analyze the tradeoffs between utility and privacy for several concrete algorithmic problems in search and social network domains. We propose and execute two novel privacy attacks on an advertising system of a social network that lead to breaches of user privacy. The attacks take advantage of the advertising system's use of users' private profile data, the powerful microtargeting capabilities provided by the system, and the detailed ad campaign performance reports provided to advertisers, in order to infer private information about users. The proposed attacks build a case for a need to reason about data sharing and mining practices using a rigorous definition of privacy, elucidate the privacy and utility tradeoffs that may arise in advertising systems that allow finegrained targeting based on user profile and activity characteristics, and have contributed to changes in the social network's advertising system aimed at increasing the barriers to practical execution of such attacks in the future. We propose a practical algorithm for sharing a subset of user search data consisting of queries and clicks in a provably privacypreserving manner. The algorithm protects privacy by limiting the amount of each user's data used and, nondeterministically, throwing away infrequent elements in the data, with the specific parameters of the algorithm being determined by the privacy guarantees desired. The proposed algorithm, and the insights gained from its analysis offer a systematic and practical approach towards sharing counts of user actions while satisfying a rigorous privacy definition, and can be applied to improve privacy in applications that rely on mining and sharing user search data. We then present a quantitative analysis of privacyutility tradeoffs in the social recommendations and social data sharing domains using formal models of privacy and utility. For social recommendations, we present a lower bound on the minimum loss in privacy for linkbased recommendation algorithms achieving good utility. For social data sharing, we present a theoretical and experimental analysis of the relationship between visibility of connections in the social network and the difficulty for a competing service to obtain knowledge of a large fraction of connections in the network. The methods of analysis introduced and the harsh tradeoffs identified can be useful for guiding privacyconscious development of social products and algorithms, and give a refined understanding of the privacyutility tradeoffs. Few topics today arouse as much heated discussion as issues of user privacy. This thesis focuses on making practical and constructive strides towards understanding and providing tools for achieving a viable balance between two seemingly opposing needs  user datadriven innovation and privacy.
 Also online at

Online 20. Some applications of duality and flows [electronic resource] : algorithms for network design and deterministic Markov decision processes [2012]
 Post, Ian Thomas.
 2012.
 Description
 Book — 1 online resource.
 Summary

This thesis combines several algorithmic results from different domains unified by common themes in the techniques usedthe strong use of linear programming duality and properties of vertex solutions and the use of network flows. First, we study the singlesink buyatbulk problem with an unknown cost function. We want to route flow through a graph from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, nondecreasing function f satisfying f(0)=0. Approximation algorithms are known for any given cost function, but we assume the function is not given. We describe a polynomial time algorithm that finds a small distribution over trees such that the expected cost of a tree for any f is within an O(1)factor of the optimum cost for that f. We design a primaldual algorithmic framework using the ellipsoid method that finds an O(1)approximation if one exists, and then construct a separation oracle using a novel adaptation of the Guha, Meyerson, and Munagala [GMM 2001] algorithm for the singlesink buyatbulk problem that proves an O(1) approximation is possible for all f. We also present a simple, fast, combinatorial algorithm that constructs a single tree T such that for all f the cost f(T) is simultaneously a 47.45approximation of the optimal cost for that particular f. This approaches the best approximation ratio currently achievable when the tree can be optimized for a specific function. Prior to this work, trees achieving simultaneous O(1)approximations for all concave functions were previously not known to exist regardless of computation time. Second, we consider a problem arising in cloud computing where users can rent computing capability in the form of a network of virtual machines (VMs) with bandwidth guarantees between pairs of VMs. We study the problem of mapping such networks of VMs onto servers in the data center network so as to minimize network congestion. This problem differs from both traditional routing problems, in which the endpoints of communication demands are fixed, and most existing graph embedding work, in which the objective is to minimize some measure of stretch rather than congestion. We focus on a special case arising in practice in which the host network is a tree and the requests are paths. We prove that given a set of weighted path requests, we can embed a 1epsilon fraction of requests with a congestion approximation of O(Hlog n/epsilon^2) if node capacities can be augmented by a 1+epsilon factor. If node capacities cannot be augmented, we prove we can embed a 1epsilon fraction of requests with congestion at most poly(log n, log theta, epsilon^{1}) where theta is the ratio of the maximum to minimum weights of the path requests. Our algorithm applies a randomized rounding scheme based on Group Steiner Tree rounding to a novel LP relaxation of the set of trees with a given number of leaves. Finally, motivated by the search for a stronglypolynomial algorithm for Markov decision processes (MDPs) and linear programming, we analyze the performance of the simplex method applied to deterministic MDPs. We prove that the simplex method with the highest gain/mostnegativereduced cost pivoting rule converges in strongly polynomial time for deterministic MDPs regardless of the discount factor. For a deterministic MDP with n states and m actions, we prove the simplex method runs in O(n^3 m^2 log^2 n) iterations if the discount factor is uniform and O(n^5 m^3 log^2 n) iterations if each action has a distinct discount factor. Previously the simplex method was known to run in polynomial time only for discounted MDPs where the discount was bounded away from 1 [Ye 2011]. Unlike in the discounted case, the algorithm does not greedily converge to the optimum, and we require a more complex measure of progress. We identify a set of layers in which the values of primal variables must lie and show that the simplex method always makes progress optimizing one layer, and when the upper layer is updated the algorithm makes a substantial amount of progress. In the case of nonuniform discounts, we define a polynomial number of ``milestone'' policies and we prove that, while the objective function may not improve substantially overall, the value of at least one dual variable is always making progress towards some milestone, and the algorithm will reach the next milestone in a polynomial number of steps.
 Also online at

Special Collections
Special Collections  Status 

University Archives  Request onsite access 
3781 2012 P  Inlibrary use 
Articles+
Journal articles, ebooks, & other eresources
 Articles+ results include