We study the complexity of equilibrium computation in discrete preference games. These games were introduced by Chierichetti, Kleinberg, and Oren (EC '13, JCSS '18) to model decision-making by agents in a social network that choose a strategy from a finite, discrete set, balancing between their intrinsic preferences for the strategies and their desire to choose a strategy that is `similar' to their neighbours. There are thus two components: a social network with the agents as vertices, and a metric space of strategies. These games are potential games, and hence pure Nash equilibria exist. Since their introduction, a number of papers have studied various aspects of this model, including the social cost at equilibria, and arrival at a consensus. We show that in general, equilibrium computation in discrete preference games is PLS-complete, even in the simple case where each agent has a constant number of neighbours. If the edges in the social network are weighted, then the problem is PLS-complete even if each agent has a constant number of neighbours, the metric space has constant size, and every pair of strategies is at distance 1 or 2. Further, if the social network is directed, modelling asymmetric influence, an equilibrium may not even exist. On the positive side, we show that if the metric space is a tree metric, or is the product of path metrics, then the equilibrium can be computed in polynomial time.

Label propagation is a well-explored family of methods for training a semi-supervised classifier where input data points (both labeled and unlabeled) are connected in the form of a weighted graph. For binary classification, the performance of these methods starts degrading considerably whenever input dataset exhibits following characteristics - (i) one of the class label is rare label or equivalently, class imbalance (CI) is very high, and (ii) degree of supervision (DoS) is very low -- defined as fraction of labeled points. These characteristics are common in many real-world datasets relating to network fraud detection. Moreover, in such applications, the amount of class imbalance is not known a priori. In this paper, we have proposed and justified the use of an alternative formulation for graph label propagation under such extreme behavior of the datasets. In our formulation, objective function is the difference of two convex quadratic functions and the constraints are box constraints. We solve this program using Concave-Convex Procedure (CCCP). Whenever the problem size becomes too large, we suggest to work with a k-NN subgraph of the given graph which can be sampled by using Locality Sensitive Hashing (LSH) technique. We have also discussed various issues that one typically faces while sampling such a k-NN subgraph in practice. Further, we have proposed a novel label flipping method on top of the CCCP solution, which improves the result of CCCP further whenever class imbalance information is made available a priori. Our method can be easily adopted for a MapReduce platform, such as Hadoop. We have conducted experiments on 11 datasets comprising a graph size of up to 20K nodes, CI as high as 99:6%, and DoS as low as 0:5%. Our method has resulted up to 19:5-times improvement in F-measure and up to 17:5-times improvement in AUC-PR measure against baseline methods.

Customer satisfaction (CSAT) is the key driver for retention and growth in retail banking and several techniques have been applied by banks to achieve this. For instance, banks in emerging markets with high footfall in branches have gone beyond the traditional approach of segmenting customers and services to optimizing the wait time for customers visiting the bank's branch. While this approach has significantly improved service quality, it has also added a new dimension in the service quality metric : pro-actively identify and address customer needs for (i) efficient banking experience and (ii) enhancing profit by selling additional services to existing customer. In this paper we present a system that addresses the challenge involved in providing better service to retail banking customer while ensuring that a larger share of customer's wallet comes to the branch. We do this by combining predictive analytics, scheduling and process optimization techniques.

We consider the problem of allocating resources for completing a collection of jobs. Each resource is specified by a start-time, finish-time and the capacity of resource available and has an associated cost, and each job is specified by a start-time, finish-time and the amount of the resource required (demand) during this interval. A feasible solution is a multiset of resources (i.e., multiple units of each resource may be picked) such that at any point of time, the sum of the capacities offered by the resources is at least the total demand of the jobs active at that point of time. The cost of the solution is the sum of the costs of the resources included in the solution (taking into account the units of the resources). The goal is to find a feasible solution of minimum cost. This problem arises naturally in many scenarios. For example, given a set of jobs, we would like to allocate some resource such as machines, memory or bandwidth in order to complete all the jobs. This problem generalizes a covering version of the knapsack problem which is known to be NP-hard. We present a constant factor approximation algorithm for this problem based on a Primal-Dual approach.

One of the distinguishing features of the services industry is the high emphasis on people interacting with other people and serving customers rather than transforming physical goods like in the traditional manufacturing processes. It is evident that analysis of such interactions is an essential aspect of designing effective and efficient services delivery. In this work we focus on learning individual and team behavior of different people or agents of a service organization by studying the patterns and outcomes of historical interactions. For each past interaction, we assume that only the list of participants and an outcome indicating the overall effectiveness of the interaction are known. Note that this offers limited information on the mutual (pairwise) compatibility of different participants. We develop the notion of service interaction networks which is an abstraction of the historical data and allows one to cast practical problems in a formal setting. We identify the unique characteristics of analyzing service interaction networks when compared to traditional analyses considered in social network analysis and establish a need for new modeling and algorithmic techniques for such networks. On the algorithmic front, we develop new algorithms to infer attributes of agents individually and in team settings. Our first algorithm is based on a novel modification to the eigen-vector based centrality for ranking the agents and the second algorithm is an iterative update technique that can be applied for subsets of agents as well. One of the challenges of conducting research in this setting is the sensitive and proprietary nature of the data. Therefore, there is a need for a realistic simulator for studying service interaction networks. We present the initial version of our simulator that is geared to capture several characteristics of service interaction networks that arise in real-life.

Stochastic integer programs (SIPs) represent a very difficult class of optimization problems arising from the presence of both uncertainty and discreteness in planning and decision problems. Although applications of SIPs are abundant, nothing is available by way of computational software. On the other hand, commercial software packages for solving deterministic integer programs have been around for quite a few years, and more recently, a package for solving stochastic linear programs has been released. In this paper, we describe how these software tools can be integrated and exploited for the effective solution of general-purpose SIPs. We demonstrate these ideas on four problem classes from the literature and show significant computational advantages.