Abstract

The Facility Location Problem (FLP) is a well-studied optimization problem with applications in many real-world scenarios. Past literature has explored the solutions from different perspectives to tackle FLPs. These include investigating FLPs under objective functions such as utilitarian, egalitarian, Nash welfare, etc. Also, there is no treatment for asymmetric welfare functions around the facility. We propose a unified framework, FLIGHT, to accommodate a broad class of welfare notions. The framework undergoes rigorous theoretical analysis, and we prove some structural properties of the solution to FLP. Additionally, we provide approximation bounds, which provide insight into an interesting fact: as the number of agents arbitrarily increases, the choice of welfare notion is irrelevant. Furthermore, the paper also includes results around concentration bounds under certain distributional assumptions over the preferred locations of agents.

Abstract

This paper considers the problem of fair probabilistic binary classification with binary protected groups. The classifier assigns scores, and a practitioner predicts labels using a certain cut-off threshold based on the desired trade-off between false positives vs. false negatives. It derives these thresholds from the ROC of the classifier. The resultant classifier may be unfair to one of the two protected groups in the dataset. It is desirable that no matter what threshold the practitioner uses, the classifier should be fair to both the protected groups; that is, the ℒₚ norm between FPRs and TPRs of both the protected groups should be at most ε. We call such fairness on ROCs of both the protected attributes εₚ-Equalized ROC. Given a classifier not satisfying ε₁-Equalized ROC, we aim to design a post-processing method to transform the given (potentially unfair) classifier's output (score) to a suitable randomized yet fair classifier. That is, the resultant classifier must satisfy ε₁-Equalized ROC. First, we introduce a threshold query model on the ROC curves for each protected group. The resulting classifier is bound to face a reduction in AUC. With the proposed query model, we provide a rigorous theoretical analysis of the minimal AUC loss to achieve ε₁-Equalized ROC. To achieve this, we design a linear time algorithm, namely FROC, to transform a given classifier's output to a probabilistic classifier that satisfies ε₁-Equalized ROC. We prove that under certain theoretical conditions, FROC achieves the theoretical optimal guarantees. We also study the performance of our FROC on multiple real-world datasets with many trained classifiers.

Abstract

This paper considers the contextual multi-armed bandit (CMAB) problem with fairness and privacy guarantees in a federated environment. We consider merit-based exposure as the desired fair outcome, which provides exposure to each action in proportion to the reward associated. We model the algorithm's effectiveness using fairness regret, which captures the difference between fair optimal policy and the policy output by the algorithm. Applying fair CMAB algorithm to each agent individually leads to fairness regret linear in the number of agents. We propose that collaborative -- federated learning can be more effective and provide the algorithm Fed-FairX-LinUCB that also ensures differential privacy. The primary challenge in extending the existing privacy framework is designing the communication protocol for communicating required information across agents. A naive protocol can either lead to weaker privacy guarantees or higher regret. We design a novel communication protocol that allows for (i) Sub-linear theoretical bounds on fairness regret for Fed-FairX-LinUCB and comparable bounds for the private counterpart, Priv-FairX-LinUCB (relative to single-agent learning), (ii) Effective use of privacy budget in Priv-FairX-LinUCB. We demonstrate the efficacy of our proposed algorithm with extensive simulations-based experiments. We show that both Fed-FairX-LinUCB and Priv-FairX-LinUCB achieve near-optimal fairness regret.

Abstract

Existing approaches to fairness in stochastic multi-armed bandits (MAB) primarily focus on exposure guarantee to individual arms. When arms are naturally grouped by certain attribute(s), we propose Bi-Level Fairness, which considers two levels of fairness. At the first level, Bi-Level Fairness guarantees a certain minimum exposure to each group. To address the unbalanced allocation of pulls to individual arms within a group, we consider meritocratic fairness at the second level, which ensures that each arm is pulled according to its merit within the group. Our work shows that we can adapt a UCB-based algorithm to achieve a Bi-Level Fairness by providing (i) anytime Group Exposure Fairness guarantees and (ii) ensuring individual-level Meritocratic Fairness within each group. We first show that one can decompose regret bounds into two components: (a) regret due to anytime group exposure fairness and (b) regret due to meritocratic fairness within each group. Our proposed algorithm BF-UCB balances these two regrets optimally to achieve the upper bound of on regret; being the stopping time. With the help of simulated experiments, we further show that BF-UCB achieves sub-linear regret; provides better group and individual exposure guarantees compared to existing algorithms; and does not result in a significant drop in reward with respect to UCB algorithm, which does not impose any fairness constraint.

Abstract

The recently proposed Transaction Fee Mechanism (TFM) literature studies the strategic interaction between the miner of a block and the transaction creators (or users) in a blockchain. In a TFM, the miner includes transactions that maximize its utility while users submit fees for a slot in the block. The existing TFM literature focuses on satisfying standard incentive properties - which may limit widespread adoption. We argue that a TFM is "fair" to the transaction creators if it satisfies specific notions, namely Zero-fee Transaction Inclusion and Monotonicity. First, we prove that one generally cannot ensure both these properties and prevent a miner's strategic manipulation. We also show that existing TFMs either do not satisfy these notions or do so at a high cost to the miners' utility. As such, we introduce a novel TFM using on-chain randomness - rTFM. We prove that rTFM guarantees incentive compatibility for miners and users while satisfying our novel fairness notions.

Abstract

The present disclosure provides a system and a method for generating a secure digital certificate for a user using cryptographic hashing and storing the digital certificate on a smart contract by a decentralized blockchain. The method includes (i) generating a registration token for a first user using the cryptographic hashing,(ii) storing the registration token of the first user as a second hash in the smart contract,(iii) receiving digital request through the first user device,(iv) validating (a) the digital request of the first user by (m) authenticating whether the biometrics of the first user, and (n) checking whether the second hash exists in the decentralized blockchain, and (b) the second user associated with a second user device using a driver algorithm,(v) sending a message to the second user device to initiate the digital request and (vi) generating the digital certificate when the first user receives a verification.

Abstract

The present disclosure provides a system for detecting and neutralizing a plurality of security attacks on a blockchain network to improve security of the blockchain network. The system includes a sender node that is configured to send a transaction to a user device associated with at least one user. The blockchain network is configured to (i) receive the transaction from the sender node when the first block gets validated in the first blockchain,(ii) validate the transaction of the first block to neutralize the first attack,(iii) determine a second attack by initiating a split in the first blockchain to determine a second blockchain, and (iv) invalidate the second blockchain when the latest block of the first blockchain invalidates the second block of the second blockchain when a proof of invalidity (POI) is added to the second block to neutralize the second attack.

Abstract

(57) ABSTRACT A blockchain system for mining a transaction using parallel blocks to improve scalability is provided. The blockchain system includes a sender node, a blockchain network, and mining nodes. The sender node (i) creates a transaction, and (ii) broadcasts the transaction on the blockchain network. Each of the mining nodes is configured to (I) split the transaction into disjoint subsets based on a hash value of the public key;(II) assign the disjoint subsets to a plurality of sub-chains that are mined in parallel by a plurality of miners;(III) mine the parallel block followed by a mining block; and (IV) verify multiple sets of transactions associated with the parallel block using an umbrella-proof-of-work method, thereby improving scalability of the blockchain system.

Abstract

Deep Learning (DL) finds application in several prominent fields, including computer vision, natural language processing, and bioinformatics. The proliferation of DL-based methods has brought to notice critical issues about bias (or unfairness) in classification and weak privacy guarantees of the training data. It is crucial to prioritize addressing these issues to prevent the potentially significant negative impact on users. While there has been progress, majority of the works focus on independently resolving fairness and privacy. We propose a tutorial on “Fair and Private Deep Learning” – aimed to provide an exhaustive discussion on (i) reasons behind unfair classifications and lack of privacy, (ii) fairness notions in literature and methods to ensure them, (iii) differentially private DL, and (iv) algorithms that address fair and private DL simultaneously. Moreover, in this tutorial, we not just limit our attention to classical, centralized DL models but also to the fairness and privacy challenges in distributed (or federated) DL. The code, presentation and other details are available at https://github.com/magnetar-iiith/FairPrivateDL.

Abstract

Distributed consensus protocols reach agreement among n players in the presence of f adversaries; different protocols support different values of f. Existing works study this problem for different adversary types (captured by threat models). There are three primary threat models: (i) Crash fault tolerance (CFT), (ii) Byzantine fault tolerance (BFT), and (iii) Rational fault tolerance (RFT), each more general than the previous. Agreement in repeated rounds on both (1) the proposed value in each round and (2) the ordering among agreed-upon values across multiple rounds is called Atomic BroadCast (ABC). ABC is more generalized than consensus and is employed in blockchains. This work studies ABC under the RFT threat model. We consider t byzantine and k rational adversaries among n players. We also study different types of rational players based on their utility towards (1) liveness attack, (2) censorship or (3) disagreement (forking attack). We study the problem of ABC under this general threat model in partially-synchronous networks. We show (1) ABC is impossible for n/3<(t+k)