## Past Seminars(For fall 2009 and earlier seminars, follow this link.) ## Spring 2011Data Streams, Dyck Languages, and Detecting Dubious Data Structures
Viewing Market Price Discovery as an Algorithmic Process Self-organizing behavior can often be viewed as arising from a distributed process. It is natural to ask when and why it occurs. Our thesis is that an algorithmic perspective may be helpful. One instance of such a distributed process is pricing in markets. A basic tenet of well-functioning markets is that they discover (converge toward) prices that simultaneously balance supplies and demands of all goods; these are called equilibrium prices. Further, the markets are self-stabilizing, meaning that they converge toward new equilibria as conditions change. This talk will seek to explain why this could happen. More specifically, we describe the setting of Ongoing Markets (by contrast with the classic Fisher and Exchange markets). An Ongoing Market allows trade at non-equilibrium prices, and, as its name suggests, continues over time. The main task remaining is to specify and analyze a suitable price update rule. We consider a (tatonnement-style) rule with the following characteristics: 1. There is a separate instance of the price update procedure for each good. 2. The procedure is distributed: (i) the instances are independent, and ii) each instance uses limited ‘local’ information. 3. It is simple. 4. It is asynchronous: price updates do not have to be simultaneous. And for appropriate markets the rule enables: 5. Fast convergence. 6. Robustness in the face of (somewhat) inaccurate data. This talk is based on papers with Lisa Fleischer and Ashish Rastogi. February 24 Learning the Demand Curve in Posted-Price Digital Goods Auctions Expert Mediated Search
Speaker: Meenal Chhabra
Learning the Demand Curve in Posted-Price Digital Goods Auctions Online digital goods auctions are settings where a seller with an unlimited supply of goods (e.g. music or movie downloads) interacts with a stream of potential buyers. In the posted price setting, the seller makes a take-it-or-leave-it offer to each arriving buyer. We study the seller's revenue maximization problem in posted-price auctions of digital goods. We find that algorithms from the multi-armed bandit literature like UCB, which come with good regret bounds, can be slow to converge. We propose and study two alternatives: scheme based on using Gittins indices with priors that make appropriate use of domain knowledge; a new learning algorithm, LLVD, that assumes a linear demand curve, and maintains a Beta prior over the free parameter using a moment-matching approximation. LLVD is not only (approximately) optimal for linear demand, but also learns fast and performs well when the linearity assumption is violated, for example in the cases of two natural valuation distributions, exponential and log-normal.
Expert Mediated Search Increasingly in both traditional, and especially Internet-based marketplaces, knowledge is becoming a traded commodity. This paper considers the impact of the presence of knowledge-brokers, or experts, on search-based markets with noisy signals. For example, consider a consumer looking for a used car on a large Internet marketplace. She sees noisy signals of the true value of any car she looks at the advertisement for, and can disambiguate this signal by paying for the services of an expert (for example, getting a Carfax report, or taking the car to a mechanic for an inspection). Both the consumer and the expert are rational, self-interested agents. We present a model for such search environments, and analyze several aspects of the model, making three main contributions: We derive the consumer's optimal search strategy in environments with noisy signals, with and without the option of consulting an expert; We find the optimal strategy for maximizing the expert's profit; We study the option of market designers to subsidize search in a way that improves overall social welfare. We illustrate our results in the context of a plausible distribution of signals and values.
Bundling in Expert-Mediated Search In search-based markets with noisy signals, like the market for used cars, experts can play an important role. These experts act as information brokers, revealing the true value of a good in exchange for the payment of a fee. Sometimes these experts may choose to sell only bundles of their services (three car inspections for a fixed price, e.g.). We analyze bundling of services in a model of expert-mediated (one-sided) search, and derive optimal strategies for experts and buyers. Our analysis reveals some surprising results. In particular, there are situations where offering only non-unit-size bundles of services can be pareto-improving for the expert and the buyer. Further, in markets with low search costs, the optimal strategy for the expert may well be to offer unlimited services for a single flat fee. Firefighting on Geometric Graphs
A Little Linear Algebraic Lemma with Lots of Uses
It is possible to take **any**(dense) weighted graph and construct a sparse weighted graph such that**every**cut is approximately preserved in the relative sense. (deterministic low order polynomial time).It is possible to take **any**matrix and choose a small subset of its columns such that one can approximate the matrix well.Linear Regression (supervised learning). It is possible to take any constrained linear regression problem and convert it into a smaller one; it is possible to reduce the dimensionality of the regression problem (sparse regression) and obtain provable performance guarantees. K-means Clustering. It is possible to reduce the dimensionality of any K-means clustering problem to O(K) dimensions and obtain provable performance guarantees. Similar methods give an elementary proof of a result due to Bourgain on restricted invertibility. This will not be covered.
Optimization Problems in Internet Advertising
## Fall 2010Permutation Methods for Model Validation We give a permutation approach to validation and model selection in data mining, machine learning and statistical inference. We define permutation complexity measures in learning, and give uniform bounds on the out-sample error, similar to a VC-style bounds. We also show concentration of measure for permutation complexity, which directly means that the methods are algorithmically efficient. The theoretical novelty is that we develop methods for analyzing Partition Equilibrium Always Exists in Resource Selection Games We consider the existence of Partition Equilibrium in Resource Selection Games. Super-strong equilibrium, where no subset of players has an incentive to change their strategies collectively, does not always exist in such games. We show, however, that partition equilibrium always exists in general resource selection games, as well as how to compute it efficiently. In a partition equilibrium, the set of players has a fixed partition into coalitions, and the only deviations considered are by coalitions that are sets in this partition. Our algorithm to compute a partition equilibrium in any resource selection game (i.e., load balancing game) settles the open question about existence of partition equilibrium in general resource selection games. Moreover, we show how to always find a partition equilibrium which is also a Nash equilibrium. This implies that in resource selection games, we do not need to sacrifice the stability of individual players when forming solutions stable against coalitional deviations. In addition, while super-strong equilibrium may not exist in resource selection games, we show that its existence can be decided efficiently, and how to find one if it exists. Impersonation Strategies in Auctions A common approach to analyzing repeated auctions, such as sponsored search auctions, is to treat them as complete information games, because it is assumed that, over time, players learn each other's types. This overlooks the possibility that players may impersonate another type. In this talk, I'll show that many standard auctions, including the Kelly mechanism, generalized second price auctions, and core-selecting auctions, have profitable impersonations. I'll define a notion of impersonation-proofness for the process by which players learn about each other's type together with the auction mechanism and associated complete information game and give several examples. Contribution Games in Social Networks We consider network contribution games, where each agent in a social network has a budget of effort that it can contribute to different collaborative projects or relationships. Depending on the contribution of the involved agents a relationship will flourish or drown, and to measure the success we use a reward function for each relationship. Every agent is trying to maximize the reward from all relationships that it is involved in. We consider pairwise equilibria of this game, and characterize the existence, computational complexity, and quality of equilibrium based on the types of reward functions involved. For example, when all reward functions are concave, we prove that the price of anarchy is at most 2. For convex functions the same only holds under some special but very natural conditions. A special focus of the talk are minimum effort games, where the reward of a relationship depends only on the minimum effort of any of the participants. Finally, we show tight bounds for approximate equilibria and convergence of dynamics in these games. ## Spring 2010Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization
Dynamic Projection Surfaces for Architectural Daylighting
Collective Intelligence: Information Aggregation in Wikis, Blogs, and Markets
Approximation Algorithms for the Firefighter Problem We provide approximation algorithms for several variants of the Firefighter problem on general graphs. The Firefighter problem models the case where a diffusive process such as an infection (or an idea, a computer virus, a fire) is spreading through a network, and our goal is to contain this infection by using targeted vaccinations. Specifically, we are allowed to vaccinate at most a fixed number (called the budget) of nodes per time-step, with the goal of minimizing the effect of the infection. The difficulty of this problem comes from its temporal component, since we must choose nodes to vaccinate at every time-step while the infection is spreading through the network, leading to notions of cuts over time. We consider two versions of the Firefighter problem: a non-spreading model, where vaccinating a node means only that this node cannot be infected; and a spreading model where the vaccination itself is an infectious process, such as in the case where the infection is a harmful idea, and the vaccine to it is another infectious beneficial idea. We look at two measures: the MaxSave measure in which we want to maximize the number of nodes which are not infected given a fixed budget, and the MinBudget measure, in which we are given a set of nodes which we have to save and the goal is to minimize the budget. We study the approximability of these problems in both models. Anarchy, Stability, and Utopia: Creating Better Matchings
Low-rank Matrix-valued Chernoff Bounds and Applications In this talk we will discuss some recent results on a non-trivial generalization of the
usual Chernoff bound for matrix-valued random variables by Ahlswede and Winter. I
am going to present this generalization and compare it with Vershynin and Rudelson deviation inequality for rank-one symmetric operators. Then I will show how Vershynin and Rudelson's approach can be adapted to prove a sharper matrix-valued Chernoff bound when the (matrix) samples have low-rank. Finally, I will show the usefulness of the latter result on the problem of approximating (w.r.t. the spectral norm) matrix multiplication. |