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

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

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

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 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

We consider the problem of achieving fair classification in Federated Learning (FL) under data heterogeneity. Most of the approaches proposed for fair classification require diverse data that represent the different demographic groups involved. In contrast, it is common for each client to own data that represents only a single demographic group. Hence the existing approaches cannot be adopted for fair classification models at the client level. To resolve this challenge, we propose several aggregation techniques. We empirically validate these techniques by comparing the resulting fairness metrics and accuracy on CelebA, UTK, and FairFace datasets.

Abstract

Civic crowdfunding (CC) is a popular medium for raising funds for civic projects from interested agents. With Blockchains gaining traction, we can implement CC in a reliable, transparent, and secure manner with smart contracts (SCs). The fundamental challenge in CC is free-riding. PPR, the proposal by Zubrickas [21] of giving refund bonus to the contributors, in the case of the project not getting provisioned, has attractive properties. However, as observed by Chandra et al. [6], PPR faces a challenge wherein the agents defer their contribution until the deadline. We define this delaying of contributions as a race condition. To address this, their proposal, PPS, considers the temporal aspects of a contribution. However, PPS is computationally complex, expensive to implement as an SC, and it being sophisticated, it is difficult to explain to a layperson. In this work, our goal is to identify all essential properties a refund bonus scheme must satisfy in order to curb free-riding while avoiding the race condition. We prove Contribution Monotonicity and Time Monotonicity are sufficient conditions for this. We propose three elegant refund bonus schemes satisfying these two conditions leading to three novel mechanisms for CC - PPRG, PPRE, and PPRP. We show that PPRG is the most cost-effective mechanism when deployed as an SC. We show that under certain modest assumptions on valuations of the agents, in PPRG, the project is funded at equilibrium.

Abstract

Crowdsourcing is an effective method to collect data by employing distributed human population. Researchers introduce appropriate reward mechanisms to incentivize agents to report accurately. In particular, this paper focuses on Peer-Based Mechanisms (PBMs). We observe that with PBMs, crowdsourcing systems may not be fair, i.e., agents may not receive the deserved rewards despite investing efforts and reporting truthfully. Unfair rewards for the agents may discourage participation. This paper aims to build a general framework that assures fairness for PBMs in temporal settings, i.e., settings that prefer early reports. Towards this, we introduce two general notions of fairness for PBMs, namely γ-fairness and qualitative fairness. To satisfy these notions, our framework provides trustworthy agents with additional chances of pairing. We introduce Temporal Reputation Model (TERM) to quantify agents’ trustworthiness across tasks. With TERM as the key constituent, we present our iterative framework, REFORM, that can adopt the reward scheme of any existing PBM. We demonstrate REFORM’s significance by deploying the framework with RPTSC’s reward scheme. Specifically, we prove that REFORM with RPTSC considerably improves fairness; while incentivizing truthful and early reports. We conduct synthetic simulations and show that our framework provides improved fairness over RPTSC.

Abstract

Fairness is well studied in the context of resource allocation. Researchers have proposed various fairness notions like envy-freeness (EF), and its relaxations, proportionality and max-min share (MMS). There is vast literature on the existential and computational aspects of such notions. While computing fair allocations, any algorithm assumes agents’ truthful reporting of their valuations towards the resources. Whereas in real-world web-based applications for fair division, the agents involved are strategic and may manipulate for individual utility gain. In this paper, we study strategy-proof mechanisms without monetary transfer, which satisfies the various fairness criteria. We know that for additive valuations, designing truthful mechanisms for EF, MMS and proportionality is impossible. Here we show that there cannot be a truthful mechanism for EFX and the existing algorithms for EF1 are manipulable. We then study the particular case of single-minded agents. For this case, we provide a Serial Dictatorship Mechanism that is strategy-proof and satisfies all the fairness criteria except EF.

Abstract

Several optimization scenarios involve multiple agents that desire to protect the privacy of their preferences. There are distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty computation. However, it comes at the expense of high computational complexity and does not constitute a rigorous privacy guarantee for optimization outcomes, as the result of the computation itself may compromise agents’ preferences. In this work, we show how to achieve privacy, specifically differential privacy, through the randomization of the solving process. In particular, we present P-Gibbs, which adapts the SD-Gibbs algorithm to obtain differential privacy guarantees with much higher computational efficiency. Experiments on graph coloring and meeting scheduling show the algorithm’s privacy-performance trade-off for varying privacy budgets, and the SD-Gibbs algorithm.