We study the design of service exchange platforms in which long-lived anonymous users exchange services with each other. The users are randomly matched into pairs of clients and servers repeatedly, and each server can choose whether to provide high-quality or low-quality services to the

client with whom it is matched. Since the users are anonymous and incur high costs (e.g. exert high effort) in providing high-quality services, it is crucial that the platform incentivizes users to provide high-quality services. Rating mechanisms have been shown to work effectively as incentive schemes in such platforms. A rating mechanism labels each user by a rating, which summarizes the user's past behaviors, recommends a desirable behavior to each server (e.g., provide higher-quality services for clients with higher ratings), and updates each server's rating based on the recommendation and its client's report on the service quality. Based on this recommendation, a low-rating user is less likely to obtain high-quality services, thereby providing users with incentives to obtain high ratings by providing high-quality services.

However, if monitoring or reporting is imperfect -- clients do not perfectly assess the quality or the reports are lost -- a user's rating may not be updated correctly. In the presence of such errors, existing rating mechanisms cannot achieve the social optimum. In this paper, we propose the first rating mechanism that does achieve the social optimum, even in the presence of monitoring or reporting errors. On one hand, the socially-optimal rating mechanism needs to be complicated enough, because the optimal recommended behavior depends not only on the current rating distribution, but

also (necessarily) on the history of past rating distributions in the platform. On the other hand, we prove that the social optimum can be achieved by "simple" rating mechanisms that use binary rating labels and a small set of (three) recommended behaviors. We provide design guidelines of socially-optimal rating mechanisms, and a low-complexity online algorithm for the rating mechanism to determine the optimal recommended behavior.

We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box that returns players' utilities at pure action profiles. In this model we establish that in order to compute a correlated equilibrium any deterministic algorithm must query the black box an exponential (in n) number of times.

We consider the problem of implementing an individually rational,

asymptotically Pareto optimal allocation in a barter-exchange

economy where agents are endowed with goods and preferences over the goods of others, but may not use money as a medium of

exchange. Because one of the most important instantiations of such

economies is kidney exchange -- where the ``input'' to the problem

consists of sensitive patient medical records -- we ask to what

extent such exchanges can be carried out while providing formal

privacy guarantees to the participants. We show that individually

rational allocations cannot achieve any non-trivial approximation to

Pareto optimality if carried out under the constraint of

differential privacy -- or even the relaxation of

\emph{joint}-differential privacy, under which it is known that

asymptotically optimal allocations can be computed in two sided

markets [Hsu et al. STOC 2014]. We therefore consider a further

relaxation that we call \emph{marginal}-differential privacy --

which promises, informally, that the privacy of every agent $i$ is

protected from every other agent $j \neq i$ so long as $j$ does not

collude or share allocation information with other agents. We show

that under marginal differential privacy, it is possible to compute

an individually rational and asymptotically Pareto optimal

allocation in such exchange economies.

Motivated by Internet advertising applications, online allocation problems have been studied extensively in various adversarial and stochastic models. While the adversarial arrival models are too pessimistic, many of the stochastic (such as i.i.d or random-order) arrival models do not realistically capture uncertainty in predictions. A significant cause for such uncertainty is the presence of unpredictable traffic spikes, often due to breaking news or similar events. To address this issue, a simultaneous approximation framework has been proposed to develop algorithms that work well both in the adversarial and stochastic models; however, this framework does not enable algorithms that make good use of partially accurate forecasts when making online decisions. In this paper, we propose a robust online stochastic model that captures the nature of traffic spikes in online advertising. In our model, in addition to the stochastic input for which we have good forecasts, an unknown number of impressions arrive that are adversarially chosen.

We design algorithms that combine a stochastic algorithm with an online algorithm to adaptively react to inaccurate predictions. We provide provable bounds for our new algorithms in this framework. We accompany our positive results with a set of hardness results showing that that our algorithms are not far from optimal in this framework. As a byproduct of our results, we also present improved online algorithms for a slight variant of the simultaneous approximation framework.

A \emph{network creation game} simulates a decentralized and non-cooperative construction of a communication network. Informally, there are $n$ players

sitting on the network nodes, which attempt to establish a reciprocal communication by activating, incurring a certain cost,

any of their incident links. The goal of each player is to have all the other nodes as close as possible in the resulting network, while buying as few links as possible. According to this intuition, any model of the game must then appropriately address a balance between these two conflicting objectives. Motivated by the fact that a player might have a strong requirement about her centrality in the network, in this paper we introduce a new setting in which if a player maintains her (either \emph{maximum} or \emph{average}) distance to the other nodes within a given \emph{bound}, then her cost is simply equal to the \emph{number} of activated edges, otherwise her cost is unbounded.

We study the problem of understanding the structure of pure Nash equilibria of the resulting games, that we call \textsc{MaxBD} and

\textsc{SumBD}, respectively. For both games, we show that when distance bounds associated with

players are \emph{non-uniform}, then equilibria can be arbitrarily bad.

On the other hand, for \textsc{MaxBD}, we show that when nodes have a \emph{uniform} bound $D \geq 3$ on the maximum distance, then the \emph{Price of Anarchy} (PoA)

is lower and upper bounded by $2$ and $O\left(n^{\frac{1}{\lfloor\log_3

D \rfloor+1}}\right)$, respectively (i.e., the PoA is constant as soon as $D$ is $\Omega(n^{\epsilon})$, for some $\epsilon>0$), while for the interesting case $D=2$, we are able to prove that the PoA is $\Omega(\sqrt{n})$ and $O(\sqrt{n \log n} )$. For the uniform \textsc{SumBD} we obtain similar (asymptotically) results, and moreover we show that the PoA becomes constant as soon as the bound on the average distance is $2^{\omega\big({\sqrt{\log n}}\big)}$.

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(1-\frac{1}{e})$-competitive (see \cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by \cite{buchbinder2007online}, graphs which we call $(k,d)-bounded$. In such graphs the maximal degree on the online side is at most $d$ and the minimal degree on the offline side is at least $k$. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio $1-\frac{d-1}{k+d-1}$, tending to \emph{one} as $d/k$ tends to zero. We prove this bound is tight for these algorithms.

Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio $1-(1-\frac{1}{d})^k>1-\frac{1}{e^{k/d}}$, or \emph{exponentially} better loss as a function of $k/d$, and strictly better than $1-\frac{1}{e}$ whenever $k\geq d$. We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.