In several online marketplaces, the qualities of value-providing supply units (e.g., sellers, workers, service providers) are unknown when they join the platform. Ensuring efficient matchmaking in such markets may require identifying the higher-quality supply units, which requires a certain amount of exploration, i.e., matching with new supply units with uncertain qualities despite the availability of known high-quality supply. In the absence of centralized incentives that subsidize such myopically suboptimal matching choices, a natural question is whether competitive forces in the market may generate adequate incentives for such exploratory behavior amongst customers. The intuition is that established high-quality supply units may naturally demand higher equilibrium prices due to congestion compared to novices, effectively incentivizing customers to participate in exploration. This paper aims to understand the extent to which such intuition is well-founded.

In several applications of the stochastic multi-armed bandit problem, the traditional objective of maximizing the expected sum of rewards obtained can be inappropriate. Motivated by the problem of optimizing job assignments to train novice workers of unknown quality in labor platforms, we consider a new objective in the classical setup. Instead of maximizing the expected total reward from $T$ pulls, we consider the vector of cumulative rewards earned from the $K$ arms at the end of $T$ pulls, and aim to maximize the expected value of the highest cumulative reward across the $K$ arms. This corresponds to the objective of training a single, highly skilled worker using a limited supply of training jobs. For this new objective, we show that any policy must incur an instance-dependent asymptotic regret of $\Omega(\log T)$ (with a higher instance-dependent constant compared to the traditional objective) and an instance-independent regret of $\Omega(K^{1/3}T^{2/3})$. We then design an explore-then-commit policy, featuring exploration based on appropriately tuned confidence bounds on the mean reward and an adaptive stopping criterion, which adapts to the problem difficulty and achieves these bounds (up to logarithmic factors). Our numerical experiments demonstrate the efficacy of this policy compared to several natural alternatives in practical parameter regimes.

The pervasive prevalence of algorithmic decision-making in societal domains necessitates that these algorithms satisfy reasonable notions of fairness. One compelling notion is that of individual fairness (IF), which advocates that similar individuals should be treated similarly. In this paper, we extend the notion of IF to online contextual decision-making in settings where there exists a common notion of conduciveness of decisions as perceived by the affected individuals. We introduce two definitions: (i) fairness-across-time (FT) and (ii) fairness-in-hindsight (FH). FT requires the treatment of individuals to be individually fair relative to the past as well as future, while FH only requires individual fairness of a decision at the time of the decision. We show that these two definitions can have drastically different implications when the principal needs to learn the utility model. Linear regret relative to optimal individually fair decisions is generally unavoidable under FT. On the other hand, we design a new algorithm: Cautious Fair Exploration (CaFE), which satisfies FH and achieves order-optimal sublinear regret guarantees for a broad range of settings.

Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called Iterative Local Voting for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution.We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by various L-Norm balls. We make several observations that inform future implementations of such a procedure.

We consider the problem faced by a service platform that needs to match supply with demand but also to learn attributes of new arrivals in order to match them better in the future. We introduce a benchmark model with heterogeneous workers and jobs that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The payoff from a match depends on the pair of types and the goal is to maximize the steady-state rate of accumulation of payoff.

Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a meta-algorithm called Iterative Local Voting for collective decision-making in this setting, in which voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm. In general, such schemes do not converge, or, when they do, the resulting solution does not have a natural description.

Spectrum has traditionally been allocated for single uses and by now most of the “prime” spectrum has well-entrenched incumbent users. When a new service needs spectrum, there are two qualitatively distinct ways of making bandwidth available for it. A swath of incumbent users can be removed from a band, with the cleared band being reallocated for the new service. Alternatively, the new users can be allowed to utilize the interstitial spectrum holes (i.e. whitespaces) between incumbent users, with the requirement to protect the incumbents' QoS. But these can also be used in combination by partially clearing a band and opening up the rest for whitespace-style sharing. In this case, the ability of regulators to “repack” incumbents, e.g. alter their operating channels, can reduce the need to evict them. An open question has been how whitespaces and partial spectrum clearing interact with each other and the ability to repack incumbents. Do efficient repacks completely eliminate whitespaces? The USA FCC's upcoming incentive auction in the TV bands is the first large-scale attempt to repack a major band of spectrum in order to clear spectrum for LTE. This auction is meant to navigate the tradeoff between incumbent TV services and LTE networks. In preparation, the FCC has made a large and complex data set of repacking constraints available for the first time. We have repurposed this data and built our own repacking engine in order to study a more general version of the tradeoff between whitespaces and cleared spectrum. We conclude that (1) repacking enables clearing of significantly more spectrum than just removing incumbents; (2) the total amount of spectrum available for new uses is relatively insensitive to how incumbents are removed; (3) efficient repackings basically trade whitespace spectrum for cleared spectrum; (4) even the most efficient repackings leave plenty of whitespace - an amount that can be comparable with the amount of cleared spectrum.

Epidemics dynamics can describe the dissemination of information in delay tolerant networks, in peer to peer networks and in content delivery networks. The control of such dynamics has thus gained a central role in all of these areas. However, a major difficulty in this context is that the objective functions to be optimized are often not additive in time but are rather multiplicative. The classical objective function in DTNs, i.e., the successful delivery probability of a message within a given deadline, falls precisely in this category, because it takes often the form of the expectation of the exponent of some integral cost. So far, models involving such costs have been solved by interchanging the order of expectation and the exponential function. While reducing the problem to a standard optimal control problem, this interchange is only tight in the mean field limit obtained as the population tends to infinity. In this paper we identify a general framework from optimal control in finance, known as risk sensitive control, which let us handle the original (multiplicative) cost and obtain solutions to several novel control problems in DTNs. In particular, we can derive the structure of state-dependent controls that optimize transmission power at the source node. Further, we can account for the propagation loss factor of the wireless medium while obtaining these controls, and, finally, we address power control at the destination node, resulting in a novel threshold optimal activation policy. Combined optimal power control at source and destination nodes is also obtained.

Most theoretical research on routing games in telecommunication networks has so far dealt with reciprocal congestion effects between routed entities. Yet in networks that support differentiation between flows, the congestion experienced by a packet depends on its priority level. Another differentiation is made by compressing the packets in the low priority flow while leaving the high priority flow intact. In this paper we study such kind of routing scenarios for the case of non-atomic users and we establish conditions for the existence and uniqueness of equilibrium.