This project aims to develop theoretical models for the problems of
uncertainty and imprecise information in computing and communication
systems such as wireless sensor networks and grid computers, and design
algorithms and policies to ameliorate their impact on system
performance, thereby leading to more effective larger-scale deployments
of such systems. The goal will also be to develop algorithms for
computing dynamic information acquisition strategies in uncertain
environments, that jointly optimize the cost of acquiring more
information, together with the gain from exploiting the information to
enhance system performance. This class of problems falls within the
larger area of stochastic control theory.
Multi-armed Bandit Problems:
The multi-armed bandit problem
in stochastic decision theory models the key trade-off between
exploring the state space and exploiting the current best option.
Though this problem admits to an elegant efficient optimal policy known
as the Gittins index, it is well-known that such index policies become
increasingly sub-optimal in the presence of cost constraints,
time-varying uncertain information, blocking constraints, etc. We
present a generic solution technique that combines the efficiency of
index policies with provable performance guarantees.
Applications to Clustering: The
first paper presents simple to implement constant factor approximations
for the stochastic version of the k-center problem. The second paper
defines a new similarity metric for clustering anomalous data, and
devises a fast agglomerative technique to cluster faults in system
execution traces
Applications to Auction Design:
We
present a simple mechanism for making bidders reveal their uncertainty
truthfully in keyword search auctions. We also extend the results to
repeated auctions under a simple model of uncertainty.
We
consider the problem of designing multi-unit auctions when bidders have
private budget constraints. We show that a natural yet
counter-intuitive auction due to Ausubel is not only truthful but also
Pareto-optimal and revenue optimal in this setting. The hard part,
surprisingly, is to show truthfulness. We also present the first
approximation results for revenue optimal
multi-item auctions when bidders have arbitrary demand and budget
constraints. Our mechanisms are surprisingly simple posted price
schemes.