Abstract

In resource allocation, it is common to assume that agents have a utility for their allocated items and zero utility for unallocated ones. We refer to such valuation domain as 1-D. This assumption of zero utility for unallocated items is not always valid. For example, in the pandemic, allocation of ventilators, oxygen beds, and critical medical help yields dis-utility to an agent when not received in time, i.e., a setting where people consume resources at the cost of others’ utility. Various externalities affect an agent’s utility, i.e., when an agent doesn’t receive an item, it can result in their gain (positive externalities) or loss (negative externalities). The existing preference models lack capturing the setting with these externalities. We conduct a study on a 2-D domain, where each agent has a utility (푣) for an item assigned to it and utility (푣 ′ ) for an item not allocated to it. We consider a generalized model, i.e., goods and chores. There is vast literature for allocating resources both fairly and efficiently. We observe that adapting the existing notions of fairness and efficiency to the 2-D domain is non-trivial. We propose a utility transformation (푇푢) and valuation transformation (푇푣) to convert from the 2-D domain to 1-D, i.e., the existing domain. We study the retention of fairness and efficiency property given this transformation, i.e., an allocation with property P in a 1-D domain also satisfies property P in 2-D, and vice versa. If a property is retainable, we can apply the transformation, and all the existing approaches are valid for the 2-D domain. Further, we study whether we can apply current results in a 2-D domain when they do not retain. We explore fairness notions such as Envy-freeness (EF), Equitability (EQ), Maxmin Share (MMS), and Proportionality and efficiency notions such as Pareto Optimality, Utilitarian Welfare, Nash Welfare, and Egalitarian Welfare.

Abstract

Deep learning’s unprecedented success raises several ethical concerns ranging from biased predictions to data privacy. Researchers tackle these issues by introducing fairness metrics, or federated learning, or differential privacy. A first, this work presents an ethical federated learning model, incorporating all three measures simultaneously. Experiments on the Adult, Bank and Dutch datasets highlight the resulting “empirical interplay” between accuracy, fairness, and privacy.

Abstract

In this paper, we introduce ballooning multi-armed bandits (BL-MAB), a novel extension of the classical stochastic MAB model. In the BL-MAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regret in a BL-MAB setting is computed with respect to the best available arm at each time. We first observe that the existing stochastic MAB algorithms result in linear regret for the BL-MAB model. We prove that, if the best arm is equally likely to arrive at any time instant, a sub-linear regret cannot be achieved. Next, we show that if the best arm is more likely to arrive in the early rounds, one can achieve sub-linear regret. Our proposed algorithm determines (1) the fraction of the time horizon for which the newly arriving arms should be explored and (2) the sequence of arm pulls in the exploitation phase from among the explored arms. Making reasonable assumptions on the arrival distribution of the best arm in terms of the thinness of the distribution’s tail, we prove that the proposed algorithm achieves sublinear instance-independent regret. We further quantify explicit dependence of regret on the arrival distribution parameters. We reinforce our theoretical findings with extensive simulation results. We conclude by showing that our algorithm would achieve sub-linear regret even if (a) the distributional parameters are not exactly known, but are obtained using a reasonable learning mechanism or (b) the best arm is not more likely to arrive early, but a large fraction of arms is likely to arrive relatively early.

Abstract

In this paper, we study an interesting combination of sleeping and combinatorial stochastic bandits. In the mixed model studied here, at each discrete time instant, an arbitrary availability set is generated from a fixed set of base arms. An algorithm can select a subset of arms from the availability set (sleeping bandits) and receive the corresponding reward along with semi-bandit feedback (combinatorial bandits). We adapt the well-known CUCB algorithm in the sleeping combinatorial bandits setting and refer to it as CS-UCB. We prove — under mild smoothness conditions — that the CS-UCB algorithm achieves an O(log(T)) instance-dependent regret guarantee. We further prove that (i) when the range of the rewards is bounded, the regret guarantee of CS-UCB algorithm is O( p T log(T)) and (ii) the instance-independent regret is O( 3 q T 2 log(T)) in a general setting. Our results are quite general and hold under general environments — such as non-additive reward functions, volatile arm availability, a variable number of base-arms to be pulled — arising in practical applications. We validate the proven theoretical guarantees through experiments.

Abstract

Electing democratic representatives via voting has been a common mechanism since the 17th century. However, these mechanisms raise concerns about fairness, privacy, vote concealment, fair calculations of tally, and proxies voting on their behalf for the voters. Ballot voting, and in recent times, electronic voting via electronic voting machines (EVMs) improves fairness by relying on centralized trust. Homomorphic encryption-based voting protocols also assure fairness but cannot scale to large scale elections such as presidential elections. In this paper, we leverage the blockchain technology of distributing trust to propose a smart contract-based protocol, namely, FASTEN. There are many existing protocols for voting using smart contracts. We observe that these either are not scalable or leak the vote tally during the voting stage, i.e., do not provide vote concealment. In contrast, we show that FASTEN preserves voter’s privacy ensures vote concealment, immutability, and avoids double voting. We prove that the probability of privacy breaches is negligibly small. Further, our cost analysis of executing FASTEN over Ethereum is comparable to most of the existing cost of elections.

Abstract

We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents’ quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely DPSS that provides an exact solution to our ILP. We then consider the setting when the qualities of the agents are unknown. We model this as a Multi-Arm Bandit (MAB) problem and propose DPSS-UCB to learn the qualities over multiple rounds. We show that after a certain number of rounds, τ , DPSS-UCB outputs a subset of agents that satisfy the average quality constraint with a high probability. Next, we provide bounds on τ and prove that after τ rounds, the algorithm incurs a regret of O(ln T), where T is the total number of rounds. We further illustrate the efficacy of DPSS-UCB through simulations. To overcome the computational limitations of DPSS, we propose a polynomial-time greedy algorithm, namely GSS, that provides an approximate solution to our ILP. We also compare the performance of DPSS and GSS through experiments.

Abstract

Blockchain-based Distributed Ledgers (DLs) promise to transform the existing financial system by making it truly democratic. In the past decade, blockchain technology has seen many novel applications ranging from the banking industry to real estate. However, in order to be adopted universally, blockchain systems must be scalable to support a high volume of transactions. As we increase the throughput of the DL system, the underlying peer-to-peer network might face multiple levels of challenges to keep up with the requirements. Due to varying network capacities, the slower nodes would be at a relative disadvantage compared to the faster ones, which could negatively impact their revenue. In order to quantify their relative advantage or disadvantage, we introduce two measures of network fairness, 푝푓 , the probability of frontrunning and 훼푓 , the publishing fairness. We show that as we scale the blockchain, both these measures deteriorate, implying that the slower nodes face a disadvantage at higher throughputs. It results in the faster nodes getting more than their fair share of the reward while the slower nodes (slow in terms of network quality) get less. Thus, fairness and scalability in blockchain systems do not go hand in hand. In a setting with rational miners, lack of fairness causes miners to deviate from the “longest chain rule” or undercut, which would reduce the blockchain’s resilience against byzantine adversaries. Hence, fairness is not only a desirable property for a blockchain system but also essential for the security of the blockchain and any scalable blockchain protocol proposed must ensure fairness.

Abstract

—Music has the power to evoke intense emotional experiences and regulate the mood of an individual. With the advent of online streaming services, research in music recommendation services has seen tremendous progress. Modern methods leveraging the listening histories of users for session-based song recommendations have overlooked the significance of features extracted from lyrics and acoustic content. We address the task of song prediction through multiple modalities, including tags, lyrics, and acoustic content. In this paper, we propose a novel deep learning approach by refining Attentive Neural Networks using representations derived via a Transformer model for lyrics and Variational Autoencoder for acoustic features. Our model achieves significant improvement in performance over existing state-of-the-art models using lyrical and acoustic features alone. Furthermore, we conduct a study to investigate the impact of users’ psychological health on our model’s performance. Index Terms—Music Recommend

Abstract

The use of in situ hyperspectral reflectance and bio-physical measurements has been increasing in forestry. Due to limited physical accessibility in a forest environment, most of the reflectance measurements of trees are acquired at a leaf or bunch of leaves level. A few radiative transfer models are available for upscaling leaf spectra to canopy level. While these models are sophisticated, they retrieve canopy spectra based on certain assumptions. We propose ‘semi-empirical model for upscaling leaf spectra (SEMULS)’ which upscales in situ leaf spectra to canopy level based on the relationship between leaf spectra and its bio-physical parameters. The performance of the model has been quantitatively validated by comparing the upscaled canopy spectra with spectra from – CHRIS hyperspectral imagery acquired concurrently and from the PROSAIL model. Results indicate that the SEMULS retrievals are …

Abstract

Generation of spatial profiles of airborne volcanic ash that is spread at synoptic scales is a problem that directly impacts lives and properties. Robust algorithms are needed to model the distribution using sparse data sampled in the neighborhood of an erupting volcano. Existing Numerical Weather Prediction (NWP) algorithms model the dispersion at coarser spatial resolutions. In this study, we evaluate a geospatial interpolation technique called Kriging [1] to generate prediction and error surfaces. Location and temperature values of ash from 2010 Icelandic eruption were spatially autocorrelated using a stochastic kriging method, known as Empirical Bayesian Kriging (EBK) [7]. The EBK estimates were rigorously validated against NWP for regions with varying sample densities. Subsequently, a method to generate an accurate overlay map using EBK estimates to augment NWP outputs is proposed to aid in …