This paper explores the problem of fair assignment on Multi-Stage graphs. A multi-stage graph consists of nodes partitioned into K disjoint sets (stages) structured as a sequence of weighted bipartite graphs formed across adjacent stages. The goal is to assign node-disjoint paths to n agents starting from the first stage and ending in the last stage. We show that an efficient assignment that minimizes the overall sum of costs of all the agents’ paths may be highly unfair and lead to significant cost disparities (envy) among the agents. We further show that finding an envy-minimizing assignment on a multi-stage graph is NP-hard. We propose the C-Balance algorithm, which guarantees envy that is bounded by 2M in the case of two agents, where M is the maximum edge weight. We demonstrate the algorithm’s tightness by presenting an instance where the envy is 2M. We further show that the cost of fairness (CoF), defined as the ratio of the cost of the assignment given by the fair algorithm to that of the minimum cost assignment, is bounded by 2 for C-Balance. We then extend this approach to n agents by proposing the DC-Balance algorithm that makes iterative calls to C-Balance. We show the convergence of DC-Balance, resulting in envy that is arbitrarily close to 2M. We derive CoF bounds for DC-Balance and provide insights about its dependency on the instance-specific parameters and the desired degree of envy. We experimentally show that our algorithm runs several orders of magnitude faster than a suitably formulated ILP.

One of the most common methods to train machine learning algorithms today is the stochastic gradient descent (SGD). In a distributed setting, SGD-based algorithms have been shown to converge theoretically under specific circumstances. A substantial number of works in the distributed SGD setting assume a fixed topology for the edge devices. These papers also assume that the contribution of nodes to the global model is uniform. However, experiments have shown that such assumptions are suboptimal and a non uniform aggregation strategy coupled with a dynamically shifting topology and client selection can significantly improve the performance of such models. This paper details a unified framework that covers several Local-Update SGD-based distributed algorithms with dynamic topologies and provides improved or matching theoretical guarantees on convergence compared to existing work.

Clustering is a widely used unsupervised learning tool with applications in numerous real-world problems. Traditional clustering methods can result in highly skewed clusters where one cluster is notably larger than others, rendering them unsuitable for scenarios such as logistics and routing. In response, capacitated clustering approaches have emerged over the past decade. These approaches limit the number of data points each cluster can accommodate, thus resulting in more uniform cluster formations. In an online version of capacitated clustering, the algorithm must make an irrevocable decision for each incoming data point, determining whether to establish it as a new center or allocate it to existing centers. The goal is to minimize the count of opened centers while adhering to capacity constraints and achieving a satisfactory approximation of the clustering cost compared to the optimal solution. Although exploring online capacitated clustering remains uncharted, we are the first to propose a probabilistic Capacitated Online Clustering Algorithm (called COCA) for h-dimensional euclidean spaces. We theoretically bound the number of centers opened and provide constant cost approximation guarantees. Additionally, we conduct rigorous experiments to validate the computational efficacy of the proposed approaches.

Human-AI teams have a pervasive impact in various fields including healthcare diagnosis, robotics in manufacturing, cyber-security, autonomous vehicles, and many more. The effectiveness of Human-AI teams highly depends on the set of humans that interact with the AI model for determining the final output. In this paper, we tackle the practical setting where taking the human input is of considerable cost and even expert humans can make mistakes. This paper proposes Probabilistic Labeler Assisted Cost Optimization (PLACO), a two-step framework to find cost-effective subsets of humans for multi-way classification tasks. The inputs from the subset of humans are then combined with the AI model’s output resulting in the most accurate output. For cost-effective human selection given an input task, we estimate human labels by maximizing the posterior probability of a true human label given the AI model’s output on the task. We further derive a value function that determines the value of a given human subset to maximize the lower bound on the overall accuracy of the Human-AI team. We present the theoretical foundations of our human label estimation method and human subset value function. We also empirically demonstrate the effectiveness of PLACO in terms of the Human-AI team’s performance and cost-effectiveness against state-of-art methods on the CIFAR-10H and Imagenet-16H datasets having human annotations.

Training the machine learning (ML) models require a large amount of data, still the capacity of these models is limited. To enhance model performance, recent literature focuses on combining ML models’ predictions with that of human experts, a setting popularly known as the human-in-the-loop or human-AI teams. Human experts can complement the ML models as they are well-equipped with vast real-world experience and sometimes have access to private information that may not be accessible while training the ML model. Existing approaches for combining an expert and ML model either require end-to-end training of the combined model or require expert annotations for every task. End-to-end training further needs a custom loss function and human annotations, which is cumbersome, results in slower convergence, and may adversely impact the ML model’s accuracy. On the other hand, using expert annotations for every task is also cost-ineffective. We propose a novel technique that optimizes the cost of seeking the expert’s advice while utilizing the ML model’s predictions to improve accuracy. Our model considers two intrinsic parameters: the expert’s cost for each prediction and the misclassification cost of the combined human-AI model. Further, we present the impact of group-wise calibration on the combined model that improves the overall model’s performance. Experimental results on our combined model with group-wise calibration show a significant increase in accuracy with limited expert advice against different established ML models for the image classification task. In addition, the combined model’s accuracy is always greater than that of the ML model, irrespective of the expert’s accuracy, the expert’s cost, and the misclassification cost.

One of the widely used peak reduction methods in smart grids is demand response, where one analyzes the shift in customers' (agents') usage patterns in response to the signal from the distribution company. Often, these signals are in the form of incentives offered to agents. This work studies the effect of incentives on the probabilities of accepting such offers in a real-world smart grid simulator, PowerTAC. We first show that there exists a function that depicts the probability of an agent reducing its load as a function of the discounts offered to them. We call it reduction probability (RP). RP function is further parametrized by the rate of reduction (RR), which can differ for each agent. We provide an optimal algorithm, MJS--ExpResponse, that outputs the discounts to each agent by maximizing the expected reduction under a budget constraint. When RRs are unknown, we propose a Multi-Armed Bandit (MAB) based online algorithm, namely MJSUCB--ExpResponse, to learn RRs. Experimentally we show that it exhibits sublinear regret. Finally, we showcase the efficacy of the proposed algorithm in mitigating demand peaks in a real-world smart grid system using the PowerTAC simulator as a test bed.

We study fairness in the context of feature-based price discrimination in monopoly markets. We propose a new notion of individual fairness, namely, \alpha-fairness, which guarantees that individuals with similar features face similar prices. First, we study discrete valuation space and give an analytical solution for optimal fair feature-based pricing. We show that the cost of fair pricing is defined as the ratio of expected revenue in an optimal feature-based pricing to the expected revenue in an optimal fair feature-based pricing (CoF) can be arbitrarily large in general. When the revenue function is continuous and concave with respect to the prices, we show that one can achieve CoF strictly less than 2, irrespective of the model parameters. Finally, we provide an algorithm to compute fair feature-based pricing strategy that achieves this CoF.

Demand response is a crucial tool to maintain the stability of the smart grids. With the upcoming research trends in the area of electricity markets, it has become a possibility to design a dynamic pricing system, and consumers are made aware of what they are going to pay. Though the dynamic pricing system (pricing based on the total demand a distributor company is facing) seems to be one possible solution, the current dynamic pricing approaches are either too complex for a consumer to understand or are too naive leading to inefficiencies in the system (either consumer side or distributor side). Due to these limitations, the recent literature is focusing on the approach to provide incentives to the consumers to reduce the electricity, especially in peak hours. For each round, the goal is to select a subset of consumers to whom the distributor should offer incentives so as to minimize the loss which comprises of cost of buying the electricity from the market, uncertainties at consumer end, and cost incurred to the consumers to reduce the electricity which is a private information to the consumers. Due to the uncertainties in the loss function (arising from renewable energy resources as well as consumption needs), traditional auction theory-based incentives face manipulation challenges. Towards this, we propose a novel combinatorial multi-armed bandit (MAB) algorithm, which we refer to as \namemab\ to learn the uncertainties along with an auction to elicit true costs incurred by the consumers. We prove that our mechanism is regret optimal and is incentive compatible. We further demonstrate efficacy of our algorithms via simulations.

Demand response is a critical part of renewable integration and energy cost reduction goals across the world. Motivated by the need to reduce costs arising from electricity shortage and renewable energy fluctuations, we propose a novel multiarmed bandit mechanism for demand response (MAB-MDR) which makes monetary offers to strategic consumers who have unknown response characteristics, to incetivize reduction in demand. Our work is inspired by a novel connection we make to crowdsourcing mechanisms. The proposed mechanism incorporates realistic features of the demand response problem including time varying and quadratic cost function. The mechanism marries auctions, that allow users to report their preferences, with online algorithms, that allow distribution companies to learn user-specific parameters. We show that MAB-MDR is dominant strategy incentive compatible, individually rational, and achieves sublinear regret. Such mechanisms can be effectively deployed in smart grids using new information and control architecture innovations and lead to welcome savings in energy costs.