The correlations and network structure amongst individuals in datasets today---whether explicitly articulated, or deduced from biological or behavioral connections---pose new issues around privacy guarantees, because of inferences that can be made about one individual from another's data. This motivates quantifying privacy in networked contexts in terms of "inferential privacy"---which measures the change in beliefs about an individual's data from the result of a computation---as originally proposed by Dalenius in the 1970's. Inferential privacy is implied by differential privacy when data are independent, but can be much worse when data are correlated; indeed, simple examples, as well as a general impossibility theorem of Dwork and Naor, preclude the possibility of achieving non-trivial inferential privacy when the adversary can have arbitrary auxiliary information. In this paper, we ask how differential privacy guarantees translate to guarantees on inferential privacy in networked contexts: specifically, under what limitations on the adversary's information about correlations, modeled as a prior distribution over datasets, can we deduce an inferential guarantee from a differential one? We prove two main results. The first result pertains to distributions that satisfy a natural positive-affiliation condition, and gives an upper bound on the inferential privacy guarantee for any differentially private mechanism. This upper bound is matched by a simple mechanism that adds Laplace noise to the sum of the data. The second result pertains to distributions that have weak correlations, defined in terms of a suitable "influence matrix". The result provides an upper bound for inferential privacy in terms of the differential privacy parameter and the spectral norm of this matrix.

Incentive design is more likely to elicit desired outcomes when it is derived based on accurate models of agent behavior. A substantial literature in behavioral economics, however, demonstrates that individuals systematically and consistently deviate from the standard economic model---expected utility theory---for decision-making under uncertainty, %a central component of which is at the core of the equilibrium analysis necessary to facilitate mechanism design. Can these behavioral biases---as modeled by prospect theory [Kahneman and Tversky 1979]---in agents' decision-making make a difference to the optimal design of incentives in these environments? In this paper, we explore this question in the context of markets for online labor and crowdsourcing where workers make strategic choices about whether to undertake a task, but do not strategize over quality conditional on participation. We ask what kind of incentive scheme---amongst a broad class of contracts, including those observed on major crowdsourcing platforms such as fixed prices or base payments with bonuses (as on MTurk or oDesk), or open-entry contests (as on platforms like Kaggle or Topcoder)---a principal might want to employ, and how the answer to this question depends on whether workers behave according to expected utility or prospect theory preferences.

Contests are widely used as a means for effort elicitation in settings ranging from government R&D contests to online crowdsourcing contests on platforms such as Kaggle, Innocentive, or TopCoder. Such rank-order mechanisms---where agents' rewards depend only on the relative ranking of their submissions' qualities---are natural mechanisms for incentivizing effort when it is easier to obtain ordinal, rather than cardinal, information about agents' outputs, or where absolute measures of quality are unverifiable. An increasing number of online contests, however, rank entries according to some numerical evaluation of their absolute quality---for instance, the performance of an algorithm on a test dataset, or the performance of an intervention in a randomized trial. Can the contest designer incentivize higher effort by making the rewards in an ordinal rank-order mechanism contingent on such cardinal information? We model and analyze cardinal contests, where a principal running a rank-order tournament has access to an absolute measure of the qualities of agents' submissions in addition to their relative rankings, and ask how modifying the rank-order tournament to incorporate cardinal information can improve incentives for effort. Our main result is that a simple threshold mechanism---a mechanism that awards the prize for a rank if and only if the absolute quality of the agent at that rank exceeds a certain threshold---is optimal amongst all mixed cardinal-ordinal mechanisms where the fraction of the jth prize awarded to the jth-ranked agent is any arbitrary non-decreasing function of her submission's quality. Further, the optimal threshold mechanism uses exactly the same threshold for each rank. We study what contest parameters determine the extent of the benefit from incorporating such cardinal information into an ordinal rank-order contest, and investigate the extent of improvement in equilibrium effort via numerical simulations.

Discussion forums, employed by MOOC providers as the primary mode of interaction among instructors and students, have emerged as one of the important components of online courses. We empirically study contribution behavior in these online collaborative learning forums using data from 44 MOOCs hosted on Coursera, focusing primarily on the highest-volume contributors---"superposters"---in a forum. We explore who these superposters are and study their engagement patterns across the MOOC platform, with a focus on the following question---to what extent is superposting a positive phenomenon for the forum? Specifically, while superposters clearly contribute heavily to the forum in terms of quantity, how do these contributions rate in terms of quality, and does this prolific posting behavior negatively impact contribution from the large remainder of students in the class?

We study the optimal design of contests for 'simple' agents, where potential contestants strategically reason about whether or not to participate in the contest, but do not strategize about the quality of their submissions. Consider a population of n agents, where an agent with type (qi, ci chooses between participating and producing a submission of quality qi at cost ci, versus not participating at all, to maximize her utility. How should a principal distribute a total prize V amongst the n ranks to maximize some increasing function of the qualities of elicited submissions in a contest with such simple agents'

We consider the problem of designing a survey to aggregate non-verifiable information from a privacy-sensitive population: an analyst wants to compute some aggregate statistic from the private bits held by each member of a population, but cannot verify the correctness of the bits reported by participants in his survey. Individuals in the population are strategic agents with a cost for privacy, ie, they not only account for the payments they expect to receive from the mechanism, but also their privacy costs from any information revealed about them by the mechanism's outcome---the computed statistic as well as the payments---to determine their utilities. How can the analyst design payments to obtain an accurate estimate of the population statistic when individuals strategically decide both whether to participate and whether to truthfully report their sensitive information'

When a website hosting user-generated content asks users a straightforward question - "Was this content helpful?" with one "Yes" and one "No" button as the two possible answers - one might expect to get a straightforward answer. In this paper, we explore how users respond to this question and find that their responses are not quite straightforward after all. Using data from Amazon product reviews, we present evidence that users do not make absolute, independent voting decisions based on individual review quality alone. Rather, whether users vote at all, as well as the polarity of their vote for any given review, depends on the context in which they view it - reviews receive a larger overall number of votes when they are 'misranked', and the polarity of votes becomes more positive/negative when the review is ranked lower/higher than it deserves. We distill these empirical findings into a new probabilistic model of rating behavior that includes the dependence of rating decisions on context. Understanding and formally modeling voting behavior is crucial for designing learning mechanisms and algorithms for review ranking, and we conjecture that many of our findings also apply to user behavior in other online content-rating settings.

Motivated by the problem of learning the qualities of user-generated content on the Web, we study a multi-armed bandit problem where the number and success probabilities of the arms of the bandit are endogenously determined by strategic agents in response to the incentives provided by the learning algorithm. We model the contributors of user-generated content as attention-motivated agents who derive benefit when their contribution is displayed, and have a cost to quality, where a contribution's quality is the probability of its receiving a positive viewer vote. Agents strategically choose whether and what quality contribution to produce in response to the algorithm that decides how to display contributions. The algorithm, which would like to eventually only display the highest quality contributions, can only learn a contribution's quality from the viewer votes the contribution receives when displayed. The problem of inferring the relative qualities of contributions using viewer feedback, to optimize for overall viewer satisfaction over time, can then be modeled as the classic multi-armed bandit problem, except that the arms available to the bandit and therefore the achievable regret are endogenously determined by strategic agents --- a good algorithm for this setting must not only quickly identify the best contributions, but also incentivize high-quality contributions to choose amongst in the first place. We first analyze the well-known UCB algorithm Ma [Auer et al. 2002] as a mechanism in this setting, where the total number of potential contributors or arms, K, can grow with the total number of viewers or available periods, T, and the maximum possible success probability of an arm, γ, may be bounded away from 1 to model malicious or error-prone viewers in the audience. We first show that while Ma can incentivize high-quality arms and achieve strong sublinear equilibrium regret when K(T) does not grow too quickly with T, it incentivizes very low quality contributions when K(T) scales proportionally with T. We then show that modifying the UCB mechanism to explore a randomly chosen restricted subset of √{T} arms provides excellent incentive properties --- this modified mechanism achieves strong sublinear regret, which is the regret measured against the maximum achievable quality γ, in every equilibrium, for all ranges of K(T) ≤ T, for all possible values of the audience parameter $\gamma$.

Gamification is growing increasingly prevalent as a means to incentivize user engagement of social media sites that rely on user contributions. Badges, or equivalent rewards such as top-contributor lists that are used to recognize a user's contributions on a site, clearly appear to be valued by users who actively pursue and compete for them. However, different sites use different badge designs, varying how, and for what, badges are awarded--- some sites such as StackOverflow award badges for meeting fixed levels of contribution, while others like Amazon and Y! Answers reward users for being amongst some top set of contributors on the site, corresponding to a competitive standard of performance. Given that users value badges, and that contributing to a site requires effort, how badges are designed will affect the incentives--- and therefore the participation and effort--- elicited from strategic users on a site.

We present a game-theoretic model for online forums for education, where students in a class can post questions to the forum and seek responses from the instructor or other students in the class. We first show that our model predicts the anecdotally observed phenomenon that students' participation in a forum is non-monotone in the instructor's response rate to questions: if the instructor responds at too high a rate students do not respond to their peers' questions, whereas an almost-absent instructor induces very little participation from the students as well. We then investigate the optimal use of a forum for two kinds of questions--- single-answer questions and discussion-style questions--- which lead to different levels of rewards that can be meaningfully offered. We show that for discussion-style questions, the instructor can choose her response rate so that the expected rate at which the first student response is received increases linearly with the size of the class; for single-answer questions, however, the optimal expected rate of arrival of the first student response remains a constant even as class size diverges. However, this slow response rate can be remedied by mixing question\ types--- as long as there is any positive probability of a\ discussion-type question in a forum, the instructor can choose her\ response rate so that the equilibrium rate of the first response from the class diverges with the number of students in the class.

We propose a simple model where individuals in a privacy-sensitive population decide whether or not to participate in a pre-announced noisy computation by an analyst, so that the database itself is endogenously determined by individuals' participation choices. The privacy an agent receives depends both on the announced noise level, as well as how many agents choose to participate in the database. Each agent has some minimum privacy requirement, and decides whether or not to participate based on how her privacy requirement compares against her expectation of the privacy she will receive if she participates in the computation. This gives rise to a game amongst the agents, where each individual's privacy if she participates, and therefore her participation choice, depends on the choices of the rest of the population.

Crowdsourcing is now widely used to replace judgement or evaluation by an expert authority with an aggregate evaluation from a number of non-experts, in applications ranging from rating and categorizing online content all the way to evaluation of student assignments in massively open online courses (MOOCs) via peer grading. A key issue in these settings, where direct monitoring of both effort and accuracy is infeasible, is incentivizing agents in the 'crowd' to put in effort to make good evaluations, as well as to truthfully report their evaluations. We study the design of mechanisms for crowdsourced judgement elicitation when workers strategically choose both their reports and the effort they put into their evaluations. This leads to a new family of information elicitation problems with unobservable ground truth, where an agent's proficiency--- the probability with which she correctly evaluates the underlying ground truth--- is endogenously determined by her strategic choice of how much effort to put into the task.

Modern online advertising increasingly relies on the availability of user tracking technology called cookie-matching to increase efficiency in ad allocations. Web publishers today use this technology to share information about the websites a user has visited, making it possible to target advertisements to users based on their prior history. This begs the question: do publishers (who are competitors for advertising money) always have the incentive to share online information? Intuitive arguments as well as anecdotal evidence suggest that sometimes a premium publisher might suffer from information sharing through an effect called information leakage: by sharing user information with the advertiser, the advertiser will be able to target the same user elsewhere on cheaper publishers, leading to a dilution of the value of the supply on the premium publishers.

In many social computing applications such as online Q&A forums, the best contribution for each task receives some high reward, while all remaining contributions receive an identical, lower reward irrespective of their actual qualities. Suppose a mechanism designer (site owner) wishes to optimize an objective that is some function of the number and qualities of received contributions. When potential contributors are {\em strategic} agents, who decide whether to contribute or not to selfishly maximize their own utilities, is such a "best contribution" mechanism, Mb, adequate to implement an outcome that is optimal for the mechanism designer? We first show that in settings where a contribution's value is determined primarily by an agent's expertise, and agents only strategically choose whether to contribute or not, contests can implement optimal outcomes: for any reasonable objective, the rewards for the best and remaining contributions in Mb can always be chosen so that the outcome in the unique symmetric equilibrium of Mb maximizes the mechanism designer's utility. We also show how the mechanism designer can learn these optimal rewards when she does not know the parameters of the agents' utilities, as might be the case in practice. We next consider settings where a contribution's value depends on both the contributor's expertise as well as her effort, and agents endogenously choose how much effort to exert in addition to deciding whether to contribute. Here, we show that optimal outcomes can never be implemented by contests if the system can rank the qualities of contributions perfectly. However, if there is noise in the contributions' rankings, then the mechanism designer can again induce agents to follow strategies that maximize his utility. Thus imperfect rankings can actually help achieve implementability of optimal outcomes when effort is endogenous and influences quality.

We investigate the design of mechanisms to incentivize high quality outcomes in crowdsourcing environments with strategic agents, when entry is an endogenous, strategic choice. Modeling endogenous entry in crowdsourcing markets is important because there is a nonzero cost to making a contribution of any quality which can be avoided by not participating, and indeed many sites based on crowdsourced content do not have adequate participation. We use a mechanism with monotone, rank-based, rewards in a model where agents strategically make participation and quality choices to capture a wide variety of crowdsourcing environments, ranging from conventional crowdsourcing contests with monetary rewards such as TopCoder, to crowdsourced content as in online Q&A forums.

A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Publishing fully accurate information maximizes utility while minimizing privacy, while publishing random noise accomplishes the opposite. Privacy can be rigorously quantified using the framework of differential privacy, which requires that a mechanism's output distribution is nearly the same whether a given database row is included. The goal of this paper is to formulate and provide strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a symmetric and monotone loss function). Our main result is the following: for each fixed count query and differential privacy level, there is a geometric mechanism $M^*$---a discrete variant of the simple and well-studied mechanism that adds random noise from a Laplace distribution---that is simultaneously expected loss-minimizing for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: every potential user $u$, no matter what its side information and preferences, derives as much utility from $M^*$ as from interacting with a differentially private mechanism $M_u$ that is optimally tailored to $u$. More precisely, for every user $u$ there is an optimal mechanism $M_u$ for it that factors into a user-independent part (the geometric mechanism $M^*$) and a user-specific postprocessing step that depends only on the output of the geometric mechanism and not on the underlying database. The first part of our proof of this result characterizes the optimal differentially private mechanism for a user as a certain basic feasible solution to a linear program with a user-specific objective function and user-independent constraints that encode differential privacy. The second part shows that all of the relevant vertices of the feasible region (ranging over all possible users) are derivable from the geometric mechanism via suitable remappings of its range.

The social lending market, with over a billion dollars in loans, is a two-sided matching market where borrowers specify demands and lenders specify total budgets and their desired interest rates from each acceptable borrower. Because different borrowers correspond to different risk-return profiles, lenders have preferences over acceptable borrowers; a borrower prefers lenders in order of the interest rates they offer to her. We investigate the question of what is a computationally feasible, ‘good’, allocation to clear this market. We design a strongly polynomial time algorithm for computing a Pareto-efficient stable outcome in a two-sided many-to-many matching market with indifferences, and use this to compute an allocation for the social lending market that satisfies the properties of stability — a standard notion of fairness in two-sided matching markets — and Pareto efficiency; and additionally addresses envy-freeness amongst similar borrowers and risk diversification for lenders. 1

Many websites rank user-generated content (UGC) using viewer votes, displaying higher quality contributions more prominently and suppressing lower quality ones. Such an allocation of attention constitutes a mechanism, which can influence the quality of content elicited from attention-motivated contributors. In this paper, we analyze equilibrium behavior in the widely used rank-order mechanism, where contributions are allocated positions on the page in decreasing order of their ratings, and the proportional mechanism which distributes attention in proportion to the number of positive ratings, in a game-theoretic model where agents are motivated by attention and the cost of making a contribution is increasing in its quality.

A large fraction of user-generated content on the Web, such as posts or comments on popular online forums, consists of abuse or spam. Due to the volume of contributions on popular sites, a few trusted moderators cannot identify all such abusive content, so viewer ratings of contributions must be used for moderation. But not all viewers who rate content are trustworthy and accurate. What is a principled approach to assigning trust and aggregating user ratings, in order to accurately identify abusive content? In this paper, we introduce a framework to address the problem of moderating online content using crowdsourced ratings. Our framework encompasses users who are untrustworthy or inaccurate to an unknown extent --- that is, both the content and the raters are of unknown quality. With no knowledge whatsoever about the raters, it is impossible to do better than a random estimate. We present efficient algorithms to accurately detect abuse that only require knowledge about the identity of a single 'good' agent, who rates contributions accurately more than half the time. We prove that our algorithm can infer the quality of contributions with error that rapidly converges to zero as the number of observations increases; we also numerically demonstrate that the algorithm has very high accuracy for much fewer observations. Finally, we analyze the robustness of our algorithms to manipulation by adversarial or strategic raters, an important issue in moderating online content, and quantify how the performance of the algorithm degrades with the number of manipulating agents.

We initiate the study of markets for private data, through the lens of differential privacy. Although the purchase and sale of private data has already begun on a large scale, a theory of privacy as a commodity is missing. In this paper, we propose to build such a theory. Specifically, we consider a setting in which a data analyst wishes to buy information from a population from which he can estimate some statistic. The analyst wishes to obtain an accurate estimate cheaply, while the owners of the private data experience some cost for their loss of privacy, and must be compensated for this loss. Agents are selfish, and wish to maximize their profit, so our goal is to design truthful mechanisms. Our main result is that such problems can naturally be viewed and optimally solved as variants of multi-unit procurement auctions. Based on this result, we derive auctions which are optimal up to small constant factors for two natural settings: When the data analyst has a fixed accuracy goal, we show that an application of the classic Vickrey auction achieves the analyst's accuracy goal while minimizing his total payment. When the data analyst has a fixed budget, we give a mechanism which maximizes the accuracy of the resulting estimate while guaranteeing that the resulting sum payments do not exceed the analyst's budget.

We model the economics of incentivizing high-quality user generated content (UGC), motivated by settings such as online review forums, question-answer sites, and comments on news articles and blogs. We provide a game-theoretic model within which to study the problem of incentivizing high quality UGC, in which contributors are strategic and motivated by exposure. Our model has the feature that both the quality of contributions as well as the extent of participation is determined endogenously in a free-entry Nash equilibrium.

We study the unit-demand envy-free pricing problem faced by a profit-maximizing seller with unlimited supply when there is metric substitutability among the items—consumer i's value for item j is $v_i-c_{i,j}$, and the substitution costs, $\{c_{i,j}\}$, form a metric. Our model is motivated by the observation that sellers often sell the same product at different prices in different locations, and rational consumers optimize the tradeoff between prices and substitution costs. While the general envy-free pricing problem is hard to approximate, we show that the problem of maximizing revenue with metric substitutability among items can be solved exactly in polynomial time. We do this by first showing that in any optimal price vector, the set of nodes that pay exactly their value uniquely determines which nodes buy an item and what price they pay, and therefore the revenue. We transform the problem of finding an optimal set of such nodes to an instance of weighted independent set on a perfect graph which can be solved in polynomial time by the strong perfect graph theorem, proving the result. We then analyze the computational tractability of various extensions to our model. We begin with relaxing the metric substitutability requirement and show that when the substitution costs do not form a metric, even if a $(1+\epsilon)$-approximate triangle inequality holds, the problem becomes NP-hard. Thus the triangle inequality characterizes the threshold at which the problem goes from “tractable” to “hard.” We then relax assumptions on the supply and demand. We consider restricting supplies to a subset of locations, or the amount of supplies, or allowing buyers to demand more than one unit. In all cases, the problem becomes NP-hard. In addition, the multiunit demand case illustrates an interesting paradoxical nonmonotonicity: The optimal revenue the seller can extract can actually decrease when consumers' demands increase. We show the revenue maximization problem with multiunit demand is APX-hard even for the simplest valuations with equal marginal values for all items up to the demand constraint, and demands of at most 3.

We study the design of truthful mechanisms that do not use payments for the generalized assignment problem (GAP) and its variants. An instance of the GAP consists of a bipartite graph with jobs on one side and machines on the other. Machines have capacities and edges have values and sizes; the goal is to construct a welfare maximizing feasible assignment. In our model of private valuations, motivated by impossibility results, the value and sizes on all job-machine pairs are public information; however, whether an edge exists or not in the bipartite graph is a job's private information. That is, the selfish agents in our model are the jobs, and their private information is their edge set. We want to design mechanisms that are truthful without money (henceforth strategyproof), and produce assignments whose welfare is a good approximation to the optimal omniscient welfare.

When online ads are shown together, they compete for user attention and conversions, imposing negative externalities on each other. While the competition for user attention in sponsored search can be captured via models of clickthrough rates, the post-click competition for conversions cannot: since the value-per-click of an advertiser is proportional to the conversion probability conditional on a click, which depends on the other ads displayed, the private value of an advertiser is no longer one-dimensional, and the GSP mechanism is not adequately expressive. We study the design of expressive GSP-like mechanisms for the simplest form that an advertiser's private value can have in the presence of such externalities- an advertiser's value depends on exclusivity, i.e., whether her ad is shown exclusively, or along with other ads.

Prosper, the largest online social lending marketplace with nearly a million members and $178 million in funded loans, uses an auction amongst lenders to finance each loan. In each auction, the borrower specifies D, the amount he wants to borrow, and a maximum acceptable interest rate R. Lenders specify the amounts ai they want to lend, and bid on the interest rate, bi, they're willing to receive. Given that a basic premise of social lending is cheap loans for borrowers, how does the Prosper auction do in terms of the borrower's payment, when lenders are strategic agents with private true interest rates?

We study an online job scheduling problem motivated by storyboarding in web advertising, where an advertiser derives value from uninterrupted sequential access to a user surfing the web. The user ceases to browse with probability 1 – β at each step, independently. Stories (jobs) arrive online; job s has length ℓs and per-unit value vs. A value vs is obtained for every unit of the job that is scheduled consecutively without interruption, discounted for the time at which it is scheduled. Jobs can be preempted, but no further value can be derived from the residual unscheduled units of the job. We seek an online algorithm whose total reward is competitive against that of the offline scheduler that knows all jobs in advance. We consider two models based on the maximum delay that can be allowed between the arrival and scheduling of a job. In the first, a job can be scheduled anytime after its arrival; in the second a job is lost unless scheduled immediately upon arrival, preempting a currently running job if needed. The two settings correspond to two natural models of how long an advertiser retains interest in a relevant user. We show that there is, in fact, a sharp separation between what an online scheduler can achieve in these two settings. In the first setting with no deadlines, we give a natural deterministic algorithm with a constant competitive ratio against the offline scheduler. In contrast, we show that in the sharp deadline setting, no (deterministic or randomized) online algorithm can achieve better than a polylogarithmic ratio.

A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Publishing fully accurate information maximizes utility while minimizing privacy, while publishing random noise accomplishes the opposite. Privacy can be rigorously quantified using the framework of differential privacy, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. The goal of this paper is strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). Our main result is: for each fixed count query and differential privacy level, there is a geometric mechanism M* -- a discrete variant of the simple and well-studied Laplace mechanism -- that is simultaneously expected loss-minimizing for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: every potential user u, no matter what its side information and preferences, derives as much utility from M* as from interacting with a differentially private mechanism Mu that is optimally tailored to u. More precisely, for every user u there is an optimal mechanism Mu for it that factors into a user-independent part (the geometric mechanism M*) followed by user-specific post-processing that can be delegated to the user itself. The first part of our proof of this result characterizes the optimal differentially private mechanism for a fixed but arbitrary user in terms of a certain basic feasible solution to a linear program with constraints that encode differential privacy. The second part shows that all of the relevant vertices of this polytope (ranging over all possible users) are derivable from the geometric mechanism via suitable remappings of its range.

Motivated by the emergence of auction-based marketplaces for display ads such as the Right Media Exchange, we study the design of a bidding agent that implements a display advertising campaign by bidding in such a marketplace. The bidding agent must acquire a given number of impressions with a given target spend, when the highest external bid in the marketplace is drawn from an unknown distribution P. The quantity and spend constraints arise from the fact that display ads are usually sold on a CPM basis. We consider both the full information setting, where the winning price in each auction is announced publicly, and the partially observable setting where only the winner obtains information about the distribution; these differ in the penalty incurred by the agent while attempting to learn the distribution. We provide algorithms for both settings, and prove performance guarantees using bounds on uniform closeness from statistics, and techniques from online learning. We experimentally evaluate these algorithms: both algorithms perform very well with respect to both target quantity and spend; further, our algorithm for the partially observable case performs nearly as well as that for the fully observable setting despite the higher penalty incurred during learning.

We study the envy-free pricing problem faced by a profit maximizing seller when there is metric substitutability among the items --- consumer i's value for item j is vi -- ci,j, and the substitution costs, {ci,j}, form a metric. Our model is motivated from the observation that sellers often sell the same product at different prices in different locations, and rational consumers optimize the tradeoff between prices and substitution costs. While the general envy-free pricing problem is hard to approximate, the addition of metric substitutability constraints allows us to solve the problem exactly in polynomial time by reducing it to an instance of weighted independent set on a perfect graph.

Most models for online advertising assume that an advertiser's value from winning an ad auction, which depends on the clickthrough rate or conversion rate of the advertisement, is independent of other advertisements served alongside it in the same session. This ignores an important 'externality effect': as the advertising audience has a limited attention span, a high-quality ad on a page can detract attention from other ads on the same page. That is, the utility to a winner in such an auction also depends on the set of other winners.

Previous studies have highlighted the high arrival rate of new contenton the web. We study the extent to which this new content can beefficiently discovered by a crawler. Our study has two parts. First,we study the inherent difficulty of the discovery problem using amaximum cover formulation, under an assumption of perfect estimates oflikely sources of links to new content. Second, we relax thisassumption and study a more realistic setting in which algorithms mustuse historical statistics to estimate which pages are most likely toyield links to new content. We recommend a simple algorithm thatperforms comparably to all approaches we consider.We measure the emphoverhead of discovering new content, defined asthe average number of fetches required to discover one new page. Weshow first that with perfect foreknowledge of where to explore forlinks to new content, it is possible to discover 90% of all newcontent with under 3% overhead, and 100% of new content with 9%overhead. But actual algorithms, which do not have access to perfectforeknowledge, face a more difficult task: one quarter of new contentis simply not amenable to efficient discovery. Of the remaining threequarters, 80% of new content during a given week may be discoveredwith 160% overhead if content is recrawled fully on a monthly basis.

Motivated by applications to sensor, peer-to-peer, and ad hoc networks, we study distributed algorithms, also known as gossip algorithms, for exchanging information and for computing in an arbitrarily connected network of nodes. The topology of such networks changes continuously as new nodes join and old nodes leave the network. Algorithms for such networks need to be robust against changes in topology. Additionally, nodes in sensor networks operate under limited computational, communication, and energy resources. These constraints have motivated the design of "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for an arbitrary network graph, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Designing the fastest gossip algorithm corresponds to minimizing this eigenvalue, which is a semidefinite program (SDP). In general, SDPs cannot be solved in a distributed fashion; however, exploiting problem structure, we propose a distributed subgradient method that solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities derived from the gossip algorithm. We use this connection to study the performance and scaling of gossip algorithms on two popular networks: Wireless Sensor Networks, which are modeled as Geometric Random Graphs, and the Internet graph under the so-called Preferential Connectivity (PC) model.

We consider the problem of finding the optimal one-bit quantizer for symmetric source distributions, with the Euclidean norm as the measure of distortion. For fixed rate quantizers, we prove that for (symmetric) monotonically decreasing source distributions with ellipsoidal level curves, the centroids of the optimal 1-bit quantizer must be on the major axis of the ellipsoids. Under the same assumptions on the source distribution, the centroids of the optimal one-bit variable-rate quantizer lie on one of the axes of the ellipsoid. If further, the source distribution f(x) is log-concave in x, the optimal 1-bit fixed-rate quantizer is unique and symmetric about the origin. (The Gaussian is an example of a distribution that satisfies all these conditions.) Under a further set of conditions on the source distributions, we show that there is a threshold below which the optimal fixed rate and variable rate quantizer are the same.

Motivated by applications to sensor, peer-to-peer and ad hoc networks, we study distributed asynchronous algorithms, also known as gossip algorithms, for computation and information exchange in an arbitrarily connected network of nodes. Nodes in such networks operate under limited computational, communication and energy resources. These constraints naturally give rise to "gossip" algorithms: schemes which distribute the computational burden and in which a node communicates with a randomly chosen neighbor. We analyze the averaging problem under the gossip constraint for arbitrary network, and find that the averaging time of a gossip algorithm depends on the second largest eigenvalue of a doubly stochastic matrix characterizing the algorithm. Using recent results of Boyd, Diaconis and Xiao (2003), we show that minimizing this quantity to design the fastest averaging algorithm on the network is a semi-definite program (SDP). In general, SDPs cannot be solved distributedly; however, exploiting problem structure, we propose a subgradient method that distributedly solves the optimization problem over the network. The relation of averaging time to the second largest eigenvalue naturally relates it to the mixing time of a random walk with transition probabilities that are derived from the gossip algorithm. We use this connection to study the performance of gossip algorithm on two popular networks: wireless sensor networks, which are modeled as geometric random graphs, and the Internet graph under the so-called preferential connectivity model.

We consider the problem of information dissemination in wireless ad-hoc networks. Capacity constraints and the varying needs of applications lead to the need for delivering data at varying resolutions as a function of distance. We introduce a primitive, which we call visibility, to quantify the variable-resolution requirement. We design and analyze new variable resolution multicast algorithms based on simple probabilistic schemes to achieve a required visibility. We also examine how multi-path effects influence visibility and propagation algorithms. Finally, we consider the problem of designing the visibility function to maximize an overall utility function (specified by applications) over the network. We derive a condition relating optimal utility and visibility, which can be used to derive the optimal visibility for a class of utility functions. 1

This paper describes previous work on decision fusion in audio-visual speech recognition. A novel approach is proposed to combine audio and video channel information in audio-visual speech recognition scenario. We have considered frame-level phonetic classification problem using two single-stream Gaussian mixture models. Audio and video streams are adaptively weighted using a cumulative mean of the sample confidence values over past frames in addition to the present sample confidence value. The confidence values for audio and video decisions are computed using an L-statistics (linear combination of order-statistics) of log-likelihoods against phone models. It is shown through various experiments, on a database of about 15000 sentences from large vocabulary continuous speech, that the proposed approach results in better classification accuracy as compared to other approaches.