Recent Seminars (Fall 2011)

(For seminars in spring 2011 or before, follow this link.)

Abstract: One of the central problems in many data-driven sciences is the right selection of attributes to observe in order to accurately predict a variable of interest. Applications abound in areas as diverse as medical sciences (predicting medical conditions based on observable attributes), social sciences (predicting future behaviors or outcomes) and sensor networks, among others. In many of these cases, time or cost constraints prohibit sampling more than a few attributes. Also, many application domains use linear regression as a method of prediction, and evaluate the quality of attributes in terms of the $R^2$ fit with the quantity to be predicted. This motivates the following formal problem definition: “Given the covariances between observable variables $X_i$ and a target variable $Z$, select $k$ of the variables $X_i$ such that the selected set has the best possible $R^2$ fit with Z.” The main result presented in this talk is that so long as the covariance matrix between the $X_i$ variables is far from singular, greedy algorithms frequently used in practice are provably constant-factor approximations. The proof is based on extending the widely used concept of submodularity to a notion of approximate submodularity, and relating it to the spectrum of the covariance matrix. Furthermore, we will investigate various graph-theoretical properties of covariance matrices which allow for efficient exact or approximate algorithms. We conclude with several exciting open questions.
(This talk is based on joint work with Abhimanyu Das, appearing in ICML 2011 and STOC 2008.)

Abstract: Most work in algorithmic game theory assumes that players ignore the costs incurred by their fellow players. In this talk, we'll consider superimposing a social network over a game, where players are concerned with minimizing not only their own costs, but also the costs of their neighbors in the network. Our goal is to understand how properties of the underlying game are affected by this alteration to the standard model. In particular, we'll consider the ratio of the social cost of the worst Nash equilibrium when each player cares about both herself and her friends relative to the worst Nash under standard selfish play. We initiate this study in the context of a simple class of games. Counterintuitively, we show that when players become less selfish (optimizing over both themselves and their friends), the resulting outcomes can in fact be worse than they would have been in the base game. We give tight bounds on this degredation in a simple class of load-balancing games, over arbitrary social networks, and present some extensions.

Abstract: We study the problem of determining the weighted optimal length resolution refutation (WOLRR) of a system of difference constraints over an integral domain using the Fourier-Motzkin (FM) elimination procedure. Although the FM elimination procedure cannot be applied to integer programs in general, FM is a sound and complete procedure for difference constraint systems (DCS), since the constraint matrix of a DCS is totally unimodular. The literature already established that every DCS has a short refutation; however, computing the weighted optimal length resolution refutation (WOLRR) is NP-complete. In this work, we both present a pseudo-polynomial time algorithm and an efficient fully polynomial-time approximation scheme (FPTAS) for computing the WOLRR of a given weighted difference constraint system (WDCS). We also present some interesting special cases, where the WOLRR of a DCS can be computed in polynomial-time. For an unsatisfiable WDCS, the WOLRR is related to the Minimum Weight Unsatisfiable Subset (MWUS) of the WDCS. Our results directly imply the existence of a pseudo-polynomial time algorithm as well as an FPTAS for the MWUS of a given WDCS. Our work has applications in various areas of research including program verification, proof theory and operations research.

Abstract: We consider a model of next-hop routing by self-interested agents. In this model, nodes in a graph (representing ISPs, Autonomous Systems, etc.) make pricing decisions of how much to charge for forwarding traffic from each of their upstream neighbors, and routing decisions of which downstream neighbors to forward traffic to (i.e., choosing the next hop). Traffic originates at a subset of these nodes that derive a utility when the traffic is routed to its destination node; the traffic demand is elastic and the utility derived from it can be different for different source nodes. Our next-hop routing and pricing model is in sharp contrast with the more common source routing and pricing models, in which the source of traffic determines the entire route from source to destination. For our model, we begin by showing sufficient conditions for prices to result in a Nash equilibrium, and in fact give an efficient algorithm to compute a Nash equilibrium which is as good as the centralized optimum, thus proving that the price of stability is 1. When only a single source node exists, then the price of anarchy is 1 as well, as long as some minor assumptions on player behavior is made. The above results hold for arbitrary convex pricing functions, but with the assumption that the utilities derived from getting traffic to its destination are linear. When utilities can be non-linear functions, we show that Nash equilibrium may not exist, even with simple discrete pricing models.
(Joint work with Dr. Elliot Anshelevich and Dr. Koushik Kar.)