Faculty/ Sujit Prakash Gujar
Sujit Prakash Gujar
Associate Professor
mail_outline
sujit.gujar[at]iiit.ac.in
language
Selected Publications
Let Leaders Play Games: Improving Timing in Leader-based Consensus
Mohammad Rasheed Ahmed,Parth Nimish Desai,Sujit Prakash Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2026
Abs | | bib Tex
@inproceedings{bib_Let__2026, AUTHOR = {Ahmed, Mohammad Rasheed and Desai, Parth Nimish and Gujar, Sujit Prakash }, TITLE = {Let Leaders Play Games: Improving Timing in Leader-based Consensus}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2026}}
Propagation latency is inherent to any distributed network, including blockchains. Typically, blockchain protocols allow some timing buffer for block propagation in the network. In leader-based blockchains, the leader -- block proposer -- is known a priori for each slot. A fast (or low-latency) proposer may delay the block proposal in anticipation of more rewards from the transactions that otherwise would have been in the subsequent block. Deploying such a strategy by manipulating the timing is known as timing games. It increases the risk of missed blocks due to reduced time for other nodes to vote on the block, affecting the overall efficiency of the blockchain.
Additionally, as the proposers who play timing games essentially steal MEV that otherwise would have gone to the next block, it is unfair to the subsequent block-proposers. We propose a dual block-proposal mechanism, 2-Prop to curtail the timing games. 2-Prop selects two proposers per slot to propose blocks, out of which one is finalized. We design a reward-sharing policy for the proposers based on how fast these blocks are propagated to avoid strategic deviations. In the induced game, which we call the Latency Game, we show that it is a Nash Equilibrium for the proposers to propose the block as quickly as possible if both are under the same network conditions. Even under disparate network conditions, we study many configurations. Our analysis shows that a faster proposer would prefer not to delay unless the other proposer is extremely slow. Thus, the efficacy of 2-Prop in mitigating the effect of timing games is established.
FLIGHT: Facility Location Integrating Generalized, Holistic Theory of Welfare
Avyukta Manjunatha Vummintala,Shivam Gupta,Shweta Jain,Sujit Prakash Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2025
@inproceedings{bib_FLIG_2025, AUTHOR = {Vummintala, Avyukta Manjunatha and Gupta, Shivam and Jain, Shweta and Gujar, Sujit Prakash }, TITLE = {FLIGHT: Facility Location Integrating Generalized, Holistic Theory of Welfare}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2025}}
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.
FROC: Building Fair ROC from a Trained Classifier
Avyukta Manjunatha Vummintala,Shantanu Das,Sujit Prakash Gujar
AAAI Conference on Artificial Intelligence, AAAI, 2025
@inproceedings{bib_FROC_2025, AUTHOR = {Vummintala, Avyukta Manjunatha and Das, Shantanu and Gujar, Sujit Prakash }, TITLE = {FROC: Building Fair ROC from a Trained Classifier}, BOOKTITLE = {AAAI Conference on Artificial Intelligence}. YEAR = {2025}}
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.
Shapley Value-based Approach for Redistributing Revenue of Matchmaking of Private Transactions in Blockchains
Mohammad Rasheed Ahmed,Parth Nimish Desai,Yash Chaurasia,Sujit Prakash Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2025
Abs | | bib Tex
@inproceedings{bib_Shap_2025, AUTHOR = {Ahmed, Mohammad Rasheed and Desai, Parth Nimish and Chaurasia, Yash and Gujar, Sujit Prakash }, TITLE = {Shapley Value-based Approach for Redistributing Revenue of Matchmaking of Private Transactions in Blockchains}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2025}}
In the context of blockchain, MEV refers to the maximum value that can be extracted from block
production through the inclusion, exclusion, or reordering of transactions. Searchers often partici-
pate in order flow auctions (OFAs) to obtain exclusive rights to private transactions, available through
entities called matchmakers, also known as order flow providers (OFPs). Most often, redistributing
the revenue generated through such auctions among transaction creators is desirable. In this work, we
formally introduce the matchmaking problem in MEV, its desirable properties, and associated chal-
lenges. Using cooperative game theory, we formalize the notion of fair revenue redistribution in
matchmaking and present its potential possibilities and impossibilities. Precisely, we define a char-
acteristic form game, referred to as RST-Game, for the transaction creators. We propose to re-
distribute the revenue using the Shapley value of RST-Game. We show that the corresponding prob-
lem is SUBEXP (i.e. 2o(n), where n is the number of transactions); therefore, approximating the
Shapley value is necessary. Further, we propose a randomized algorithm for computing the Shapley
value in RST-Game and empirically verify its efficacy.
"Fairness and Privacy Guarantees in Federated Contextual Bandits
Sambhav Solanki,Shweta Jain,Sujit Prakash Gujar
Asian Conference on Machine Learning, ACML, 2024
@inproceedings{bib_"Fai_2024, AUTHOR = {Solanki, Sambhav and Jain, Shweta and Gujar, Sujit Prakash }, TITLE = {"Fairness and Privacy Guarantees in Federated Contextual Bandits}, BOOKTITLE = {Asian Conference on Machine Learning}. YEAR = {2024}}
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.
Differentially Private Multi-Agent Constraint Optimization." In Journal of Automated Agents and Multi-Agent Systems
Sankarshan Damle,Aleksei Triastcyn Boi Faltings,Boi Faltings,Sujit Prakash Gujar
Journal on Autonomous Agents and Multiagent Systems, J-AAMAS, 2024
@inproceedings{bib_Diff_2024, AUTHOR = {Damle, Sankarshan and Faltings, Aleksei Triastcyn Boi and Faltings, Boi and Gujar, Sujit Prakash }, TITLE = {Differentially Private Multi-Agent Constraint Optimization." In Journal of Automated Agents and Multi-Agent Systems}, BOOKTITLE = {Journal on Autonomous Agents and Multiagent Systems}. YEAR = {2024}}
Distributed constraint optimization (DCOP) is a framework in which multiple agents with private constraints (or preferences) cooperate to achieve a common goal optimally. DCOPs are applicable in several multi-agent coordination/allocation problems, such as vehicle routing, radio frequency assignments, and distributed scheduling of meetings. However, optimization scenarios may involve multiple agents wanting to protect their preferences’ privacy. Researchers propose privacy-preserving algorithms for DCOPs that provide improved privacy protection through cryptographic primitives such as partial homomorphic encryption, secret-sharing, and secure multiparty computation. These privacy benefits come at the expense of high computational complexity. Moreover, such an approach does not constitute a rigorous privacy guarantee for optimization outcomes, as the result of the computation may compromise agents’ preferences. In this work, we show how to achieve privacy, specifically Differential Privacy, by randomizing the solving process. In particular, we present P-Gibbs, which adapts the current state-of-the-art algorithm for DCOPs, namely SD-Gibbs, to obtain differential privacy guarantees with much higher computational efficiency. Experiments on benchmark problems such as Ising, graph-coloring, and meeting-scheduling show P-Gibbs’ privacy and performance trade-off for varying privacy budgets and the SD-Gibbs algorithm. More concretely, we empirically show that P-Gibbs provides fair solutions for competitive privacy budgets.
Designing Redistribution Mechanisms for Reducing Transaction Fees in Blockchains
Sankarshan Damle,P Manisha,Sujit Prakash Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2024
@inproceedings{bib_Desi_2024, AUTHOR = {Damle, Sankarshan and Manisha, P and Gujar, Sujit Prakash }, TITLE = {Designing Redistribution Mechanisms for Reducing Transaction Fees in Blockchains}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2024}}
Blockchains deploy Transaction Fee Mechanisms (TFMs) to determine which user transactions to include in blocks and determine their payments (i.e., transaction fees). Increasing demand and scarce block resources have led to high user transaction fees. As these blockchains are a public resource, it may be preferable to reduce these transaction fees. To this end, we introduce Transaction Fee Redistribution Mechanisms (TFRMs) -- redistributing VCG payments collected from such TFM as rebates to minimize transaction fees. Classic redistribution mechanisms (RMs) achieve this while ensuring Allocative Efficiency (AE) and User Incentive Compatibility (UIC). Our first result shows the non-triviality of applying RM in TFMs. More concretely, we prove that it is impossible to reduce transaction fees when (i) transactions that are not confirmed do not receive rebates and (ii) the miner can strategically manipulate the mechanism. Driven by this, we propose emph{Robust} TFRM (textsf{R-TFRM}): a mechanism that compromises on an honest miner's individual rationality to guarantee strictly positive rebates to the users. We then introduce emph{robust} and emph{rational} TFRM (textsf{R}textsf{-TFRM}) that uses trusted on-chain randomness that additionally guarantees miner's individual rationality (in expectation) and strictly positive rebates. Our results show that TFRMs provide a promising new direction for reducing transaction fees in public blockchains.
Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits
Shubham Pokhriayal,Shweta Jain,Ganesh Ghalme,Swapnil Dhamal,Sujit Prakash Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2024
@inproceedings{bib_Simu_2024, AUTHOR = {Pokhriayal, Shubham and Jain, Shweta and Ghalme, Ganesh and Dhamal, Swapnil and Gujar, Sujit Prakash }, TITLE = {Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2024}}
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.
No Transaction Fees? No Problem! Achieving Fairness in Transaction Fees Mechanism Design
Varul Srivastava,Sankarshan Damle,Sujit Prakash Gujar
European Conference on Artificial Intelligence, ECAI, 2024
@inproceedings{bib_No_T_2024, AUTHOR = {Srivastava, Varul and Damle, Sankarshan and Gujar, Sujit Prakash }, TITLE = {No Transaction Fees? No Problem! Achieving Fairness in Transaction Fees Mechanism Design }, BOOKTITLE = {European Conference on Artificial Intelligence}. YEAR = {2024}}
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.
System and method for generating a digital certificate for a user using a decentralized blockchain
Sujit Prakash Gujar,Kishore Kothapalli
United States Patent, Us patent, 2024
@inproceedings{bib_Syst_2024, AUTHOR = {Gujar, Sujit Prakash and Kothapalli, Kishore }, TITLE = {System and method for generating a digital certificate for a user using a decentralized blockchain}, BOOKTITLE = {United States Patent}. YEAR = {2024}}
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.
System and method for detecting and neutralizing security attacks in blockchains
Sujit Prakash Gujar,Varul Srivastava
United States Patent, Us patent, 2024
@inproceedings{bib_Syst_2024, AUTHOR = {Gujar, Sujit Prakash and Srivastava, Varul }, TITLE = {System and method for detecting and neutralizing security attacks in blockchains}, BOOKTITLE = {United States Patent}. YEAR = {2024}}
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.
Blockchain system for mining transaction using parallel blocks to improve scalability and a method thereof
Sujit Prakash Gujar,Kannan Srinathan,Anurag Jain
United States Patent, Us patent, 2024
@inproceedings{bib_Bloc_2024, AUTHOR = {Gujar, Sujit Prakash and Srinathan, Kannan and Jain, Anurag }, TITLE = {Blockchain system for mining transaction using parallel blocks to improve scalability and a method thereof}, BOOKTITLE = {United States Patent}. YEAR = {2024}}
(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.
Tutorial on Fair and Private Deep Learning
Manisha Padala,,Sankarshan Damle,Sujit Prakash Gujar
India Joint International Conference on Data Science & Management of Data, COMAD/CODS, 2024
@inproceedings{bib_Tuto_2024, AUTHOR = {Padala, Manisha and , and Damle, Sankarshan and Gujar, Sujit Prakash }, TITLE = {Tutorial on Fair and Private Deep Learning}, BOOKTITLE = {India Joint International Conference on Data Science & Management of Data}. YEAR = {2024}}
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.
Towards Rational Consensus in Honest Majority
Varul Srivastava,Sujit Prakash Gujar
International Conference on Distributed Computing Systems, ICDCS, 2024
@inproceedings{bib_Towa_2024, AUTHOR = {Srivastava, Varul and Gujar, Sujit Prakash }, TITLE = {Towards Rational Consensus in Honest Majority}, BOOKTITLE = {International Conference on Distributed Computing Systems}. YEAR = {2024}}
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)
Centralization in Proof-of-Stake Blockchains: A Game-Theoretic Analysis of Bootstrapping Protocols
Varul Srivastava,Sankarshan Damle,Sujit Prakash Gujar
6th Games, Agents, and Incentives Workshop, GAIW, 2024
@inproceedings{bib_Cent_2024, AUTHOR = {Srivastava, Varul and Damle, Sankarshan and Gujar, Sujit Prakash }, TITLE = {Centralization in Proof-of-Stake Blockchains: A Game-Theoretic Analysis of Bootstrapping Protocols}, BOOKTITLE = {6th Games, Agents, and Incentives Workshop}. YEAR = {2024}}
Proof-of-stake (PoS) has emerged as a natural alternative to the resource-intensive Proof-of-Work (PoW) blockchain, as was recently seen with the Ethereum Merge. PoS-based blockchains require an initial stake distribution among the participants. Typically, this initial stake distribution is called bootstrapping. This paper argues that existing bootstrapping protocols are prone to centralization. To address centralization due to bootstrapping, we propose a novel game Γbootstrap. Next, we define three conditions: (i) Individual Rationality (IR), (ii) Incentive Compatibility (IC), and (iii) (τ,δ,ϵ)− Decentralization that an emph{ideal} bootstrapping protocol must satisfy. (τ,δ,ϵ) are certain parameters to quantify decentralization. Towards this, we propose a novel centralization metric, C-NORM, to measure centralization in a PoS System. We define a centralization game -- Γcent, to analyze the efficacy of centralization metrics. We show that C-NORM effectively captures centralization in the presence of strategic players capable of launching Sybil attacks. With C-NORM, we analyze popular bootstrapping protocols such as Airdrop and Proof-of-Burn (PoB) and prove that they do not satisfy IC and IR, respectively. Motivated by the Ethereum Merge, we study W2SB (a PoW-based bootstrapping protocol) and prove it is ideal. In addition, we conduct synthetic simulations to empirically validate that W2SB bootstrapped PoS is decentralized.
DECENT-BRM: Decentralization through Block Reward Mechanisms
Varul Srivastava,Sujit Prakash Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2024
@inproceedings{bib_DECE_2024, AUTHOR = {Srivastava, Varul and Gujar, Sujit Prakash }, TITLE = {DECENT-BRM: Decentralization through Block Reward Mechanisms}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2024}}
Proof-of-Work is a consensus algorithm where miners solve cryptographic puzzles to mine blocks and obtain a reward through some Block Reward Mechanism (BRM). PoW blockchain faces the problem of centralization due to the formation of mining pools, where miners mine blocks as a group and distribute rewards. The rationale is to reduce the risk (variance) in reward while obtaining the same expected block reward. In this work, we address the problem of centralization due to mining pools in PoW blockchain. We propose a two-player game between the new miner joining the system and the PoW blockchain system.
We model the utility for the incoming miner as a combination of (i) expected block reward, (ii) risk, and (iii) cost of switching between different mining pools. With this utility structure, we analyze the equilibrium strategy of the incoming miner for different BRMs: (a) memoryless -- block reward is history independent (e.g., Bitcoin) (b) retentive: block reward is history-dependent (e.g., Fruitchains). For memoryless BRMs, we show that depending on the coefficient of switching cost c, the protocol is decentralized when c=0 and centralized when c>c–. In addition, we show the impossibility of constructing a memoryless BRM where solo mining gives a higher payoff than forming/joining mining pools. While retentive BRM in Fruitchains reduces risk in solo mining, the equilibrium strategy for incoming miners is still to join mining pools, leading to centralization. We then propose our novel retentive BRM -- Decent-BRM. We show that under Decent-BRM, incoming miners obtain higher utility in solo mining than joining mining pools. Therefore, no mining pools are formed, and the Pow blockchain using Decent-BRM is decentralized.
Fairness and Privacy Guarantees in Federated Contextual Bandits
Sambhav Solanki,Sujit Prakash Gujar,Shweta Jain
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2024
@inproceedings{bib_Fair_2024, AUTHOR = {Solanki, Sambhav and Gujar, Sujit Prakash and Jain, Shweta }, TITLE = {Fairness and Privacy Guarantees in Federated Contextual Bandits}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2024}}
This paper studies the contextual multi-armed bandit problem with fairness and privacy guarantees in a federated setting. It proposes a collaborative algorithm, Fed-FairX-LinUCB that achieves sublinear fairness regret and can be adapted to ensure differential privacy. The key challenge is designing a communication protocol that balances privacy and regret. The proposed protocol achieves both sub-linear fairness regret and effective use of privacy budget. Experiments validates the efficacy of both Fed-FairX-LinUCB and its private counterpart, Priv-FairX-LinUCB.
QuickSync A Quickly Synchronizing PoS-Based Blockchain Protocol
Siddiqui Shoeb Khaled,Varul Srivastava,Raj Maheshwari,Sujit Prakash Gujar
International Conference on Blockchain and Cryptocurrency, ICBC, 2023
@inproceedings{bib_Quic_2023, AUTHOR = {Khaled, Siddiqui Shoeb and Srivastava, Varul and Maheshwari, Raj and Gujar, Sujit Prakash }, TITLE = {QuickSync A Quickly Synchronizing PoS-Based Blockchain Protocol}, BOOKTITLE = {International Conference on Blockchain and Cryptocurrency}. YEAR = {2023}}
Proof-of-Stake(PoS) based blockchain protocols have gained popularity due to their higher throughput and low carbon footprint when compared with Proof-of-Work blockchain protocols. The two major parts of blockchain protocols are the selection of the next block proposer and the selection of the longest chain. In PoS the block publishers are selected based on their relative stake. However, PoS-based blockchain protocols may face vulnerability against Fully Adaptive Corruptions. This paper proposes a novel PoS-based blockchain protocol, QuickSync, to achieve security against Fully Adaptive Corruptions while improving performance. Towards this, we propose a metric for each block: block power. We compute the chain power of a chain as the sum of block powers of all the blocks comprising the chain. The chain selection rule selects the chain with the highest chain power as the valid chain. Since the block proposer is not selected upfront, this scheme is resilient to fully adaptive corruptions, which we also show formally. We also ensure that our block power mechanism is resistant to Sybil attacks. We prove the security of QuickSync by showing that it satisfies the common prefix, chain growth, and chain quality properties. Our analysis demonstrates that QuickSync performs better than Bitcoin by order of magnitude on both transactions per second and time to finality.
Multi-armed Bandit Based Tariff Generation Strategy for Multi-agent Smart Grid Systems
Chandlekar Sanjay Rajendrabhai,Easwar Subramanian,Sujit Prakash Gujar
Engineering Multi-Agent Systems., EMAS, 2023
@inproceedings{bib_Mult_2023, AUTHOR = {Rajendrabhai, Chandlekar Sanjay and Subramanian, Easwar and Gujar, Sujit Prakash }, TITLE = {Multi-armed Bandit Based Tariff Generation Strategy for Multi-agent Smart Grid Systems}, BOOKTITLE = {Engineering Multi-Agent Systems.}. YEAR = {2023}}
The emergence of smart grid technology has opened the door for wide-scale automation in decision-making. A distribution company, an integral part of a smart grid system, has to procure electricity from the wholesale market and then sell it to customers in the retail market by publishing attractive tariff contracts. It can deploy autonomous agents to make decisions on its behalf. In this work, we describe the tariff contracts generation strategy of one such autonomous agent, which is based on a Contextual Multi-armed Bandit (ConMAB) based learning technique to generate tariff contracts for various types of customers in the retail market of smart grids. We particularly utilize the Exponential-weight algorithm for Exploration and Exploitation (EXP-3) for ConMAB-based learning. We call our proposed strategy GenerateTariffs-EXP3. Our previous work shows that maintaining an appropriate market share in the retail market yields high net revenue. Thus, we first present a game-theoretic analysis that determines an optimal level of market share. Then we train our proposed strategy to achieve and maintain the suggested level of market share by adapting to the market situation and revising the tariff contracts periodically. We validate our proposed strategy in PowerTAC, a close-to real-world smart grid simulator, and showcase that it is able to maintain the suggested market share.
ChatGPT in education: A blessing or a curse? A qualitative study exploring early adopters’ utilization and perceptions
Reza Hadi Mogavi,Pan Hui,Sujit P Gujar,Chao Deng,Justin Juho Kim,Young D Kwon,Ahmed Hosny Saleh Metwally,Ahmed Tlili,Simone Bassanelli,Antonio Bucchiarone,Lennart E Nacke
Computers in Human Behavior: Artificial Humans, CHBAH, 2023
Abs | | bib Tex
@inproceedings{bib_Chat_2023, AUTHOR = {Mogavi, Reza Hadi and Hui, Pan and Gujar, Sujit P and Deng, Chao and Kim, Justin Juho and Kwon, Young D and Metwally, Ahmed Hosny Saleh and Tlili, Ahmed and Bassanelli, Simone and Bucchiarone, Antonio and Nacke, Lennart E }, TITLE = {ChatGPT in education: A blessing or a curse? A qualitative study exploring early adopters’ utilization and perceptions}, BOOKTITLE = {Computers in Human Behavior: Artificial Humans}. YEAR = {2023}}
To foster the development of pedagogically potent and ethically sound AI-integrated learning landscapes, it is pivotal to critically explore the perceptions and experiences of the users immersed in these contexts. In this study, we perform a thorough qualitative content analysis across four key social media platforms. Our goal is to understand the user experience (UX) and views of early adopters of ChatGPT across different educational sectors. The results of our research show that ChatGPT is most commonly used in the domains of higher education, K-12 education, and practical skills training. In social media dialogues, the topics most frequently associated with ChatGPT are productivity, efficiency, and ethics. Early adopters' attitudes towards ChatGPT are multifaceted. On one hand, some users view it as a transformative tool capable of amplifying student self-efficacy and learning motivation. On the other hand, there is a degree of apprehension among concerned users. They worry about a potential overdependence on the AI system, which they fear might encourage superficial learning habits and erode students’ social and critical thinking skills. This dichotomy of opinions underscores the complexity of Human-AI Interaction in educational contexts. Our investigation adds depth to this ongoing discourse, providing crowd-sourced insights for educators and learners who are considering incorporating ChatGPT or similar generative AI tools into their pedagogical strategies
VidyutVanika: AI-Based Autonomous Broker for Smart Grids: From Theory to Practice
Chandlekar Sanjay Rajendrabhai,Bala Suraj Pedasingu,SUSOBHAN GHOSH,Eashwar Subramanian,Atharv Sanjaykumar Bhatt,Sujit P Gujar,Praveen Paruchuri
Energy Sustainability through Retail Electricity Markets, ESTREM, 2023
Abs | | bib Tex
@inproceedings{bib_Vidy_2023, AUTHOR = {Rajendrabhai, Chandlekar Sanjay and Pedasingu, Bala Suraj and GHOSH, SUSOBHAN and Subramanian, Eashwar and Bhatt, Atharv Sanjaykumar and Gujar, Sujit P and Paruchuri, Praveen }, TITLE = {VidyutVanika: AI-Based Autonomous Broker for Smart Grids: From Theory to Practice}, BOOKTITLE = {Energy Sustainability through Retail Electricity Markets}. YEAR = {2023}}
We present the design, implementation, and analysis of autonomous brokers for a smart grid ecosystem, in the context of PowerTAC. PowerTAC simulates the real-world smart grid ecosystem through wholesale, retail, and balancing markets. The complexity of grid operations makes designing broker components using artificial intelligence (AI) inevitable. We begin with the challenges prevalent in devising such autonomous brokers. Then, we describe the design, implementation, and performance of our AI-based autonomous agent VidyutVanika (VV). We discuss two variants of VV: VV18 and VV21, which were successful in the annual PowerTAC tournaments, 2018 and 2021, respectively.
Combinatorial Civic Crowdfunding with Budgeted Agents: Welfare Optimality at Equilibrium and Optimal Deviation
Sankarshan Damle,P Manisha,Sujit P Gujar
Association for the Advancement of Artificial Intelligence, AAAI, 2023
@inproceedings{bib_Comb_2023, AUTHOR = {Damle, Sankarshan and Manisha, P and Gujar, Sujit P }, TITLE = {Combinatorial Civic Crowdfunding with Budgeted Agents: Welfare Optimality at Equilibrium and Optimal Deviation}, BOOKTITLE = {Association for the Advancement of Artificial Intelligence}. YEAR = {2023}}
Civic Crowdfunding (CC) uses the ``power of the crowd" to garner contributions towards public projects. As these projects are non-excludable, agents may prefer to ``free-ride," resulting in the project not being funded. Researchers introduce refunds for single project CC to incentivize agents to contribute, guaranteeing the project's funding. These funding guarantees are applicable only when agents have an unlimited budget. This paper focuses on a combinatorial setting, where multiple projects are available for CC and agents have a limited budget. We study specific conditions where funding can be guaranteed. Naturally, funding the optimal social welfare subset of projects is desirable when every available project cannot be funded due to budget restrictions. We prove the impossibility of achieving optimal welfare at equilibrium for any monotone refund scheme. Further, given the contributions of other agents, we prove that it is NP-Hard for an agent to determine its optimal strategy. That is, while profitable deviations may exist for agents instead of funding the optimal welfare subset, it is computationally hard for an agent to find its optimal deviation. Consequently, we study different heuristics agents can use to contribute to the projects in practice. We demonstrate the heuristics' performance as the average-case trade-off between the welfare obtained and an agent's utility through simulations.
A Novel Demand Response Model and Method for Peak Reduction in Smart Grids -- PowerTAC
Chandlekar Sanjay Rajendrabhai,Shweta Jain,Sujit P Gujar
International Joint Conference on Artificial Intelligence, IJCAI, 2023
@inproceedings{bib_A_No_2023, AUTHOR = {Rajendrabhai, Chandlekar Sanjay and Jain, Shweta and Gujar, Sujit P }, TITLE = {A Novel Demand Response Model and Method for Peak Reduction in Smart Grids -- PowerTAC}, BOOKTITLE = {International Joint Conference on Artificial Intelligence}. YEAR = {2023}}
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 dis- tribution company. Often, these signals are in the form of incentives offered to agents. This work studies the effect of incentives on the prob- abilities of accepting such offers in a real-world smart grid simulator, PowerTAC. We first show that there exists a function that depicts the prob- ability of an agent reducing its load as a func- tion of the discounts offered to them. We call it reduction probability (RP). RP function is fur- ther 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 maximiz- ing the expected reduction under a budget con- straint. When RRs are unknown, we propose a Multi-Armed Bandit (MAB) based online algo- rithm, namely MJSUCB–EXPRESPONSE, to learn RRs. Experimentally we show that it exhibits sub- linear regret. Finally, we showcase the efficacy of the proposed algorithm in mitigating demand peaks in a real-world smart grid system using the Power- TAC simulator as a test bed.
FAIR ALLOCATION OF GOODS AND CHORES – TUTORIAL AND SURVEY OF RECENT RESULTS
Shaily Ashokkumar Mishra,P Manisha,Sujit P Gujar
Technical Report, arXiv, 2023
@inproceedings{bib_FAIR_2023, AUTHOR = {Mishra, Shaily Ashokkumar and Manisha, P and Gujar, Sujit P }, TITLE = {FAIR ALLOCATION OF GOODS AND CHORES – TUTORIAL AND SURVEY OF RECENT RESULTS}, BOOKTITLE = {Technical Report}. YEAR = {2023}}
Fair resource allocation is an important problem in many real-world scenarios, where resources such as goods and chores must be allocated among agents. In this survey, we delve into the intricacies of fair allocation, focusing specifically on the challenges associated with indivisible resources. We de- fine fairness and efficiency within this context and thoroughly survey existential results, algorithms, and approximations that satisfy various fairness criteria, including envyfreeness, proportionality, MMS, and their relaxations. Additionally, we discuss algorithms that achieve fairness and efficiency, such as Pareto Optimality and Utilitarian Welfare. We also study the computational complexity of these algorithms, the likelihood of finding fair allocations, and the price of fairness for each fairness notion. We also cover mixed instances of indivisible and divisible items and investigate different valuation and allocation settings. By summarizing the state-of-the-art research, this survey provides valuable insights into fair resource allocation of indivisible goods and chores, highlighting compu- tational complexities, fairness guarantees, and trade-offs between fairness and efficiency. It serves as a foundation for future advancements in this vital field.
Exploring user perspectives on chatgpt: Applications, perceptions, and implications for ai-integrated education
Reza Hadi Mogavi,Sujit P Gujar,Lennart E. Nacke,Pan Hui,Chao Deng,Justin Juho Kim,Pengyuan Zhou,Young D. Kwon,Ahmed Hosny Saleh Metwally,Ahmed Tlili,Simone Bassanelli,Antonio Bucchiarone
Technical Report, arXiv, 2023
@inproceedings{bib_Expl_2023, AUTHOR = {Mogavi, Reza Hadi and Gujar, Sujit P and Nacke, Lennart E. and Hui, Pan and Deng, Chao and Kim, Justin Juho and Zhou, Pengyuan and Kwon, Young D. and Metwally, Ahmed Hosny Saleh and Tlili, Ahmed and Bassanelli, Simone and Bucchiarone, Antonio }, TITLE = {Exploring user perspectives on chatgpt: Applications, perceptions, and implications for ai-integrated education}, BOOKTITLE = {Technical Report}. YEAR = {2023}}
Understanding user perspectives on Artificial Intelligence (AI) in education is essential for creating pedagogically effective and ethically responsible AI-integrated learning environments. In this paper, we conduct an extensive qualitative content analysis of four major social media platforms (Twitter, Reddit, YouTube, and LinkedIn) to explore the user experience (UX) and perspectives of early adopters toward ChatGPT-an AI Chatbot technology-in various education sectors. We investigate the primary applications of ChatGPT in education (RQ1) and the various perceptions of the technology (RQ2). Our findings indicate that ChatGPT is most popularly used in the contexts of higher education (24.18%), K-12 education (22.09%), and practical-skills learning (15.28%). On social media platforms, the most frequently discussed topics about ChatGPT are productivity, efficiency, and ethics. While early adopters generally lean toward seeing ChatGPT as a revolutionary technology with the potential to boost students' self-efficacy and motivation to learn, others express concern that overreliance on the AI system may promote superficial learning habits and erode students' social and critical thinking skills. Our study contributes to the broader discourse on Human-AI Interaction and offers recommendations based on crowd-sourced knowledge for educators and learners interested in incorporating ChatGPT into their educational settings. Furthermore, we propose a research agenda for future studies that sets the foundation for continued investigation into the application of ChatGPT in education.
F3: fair and federated face attribute classification with heterogeneous data
Kanaparthy S V Samhita,P Manisha,Sankarshan Damle,Santosh Ravi Kiran,Sujit P Gujar
Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD, 2023
@inproceedings{bib_F3:__2023, AUTHOR = {Samhita, Kanaparthy S V and Manisha, P and Damle, Sankarshan and Kiran, Santosh Ravi and Gujar, Sujit P }, TITLE = {F3: fair and federated face attribute classification with heterogeneous data}, BOOKTITLE = {Pacific-Asia Conference on Knowledge Discovery and Data Mining}. YEAR = {2023}}
Fairness across different demographic groups is an essential criterion for face-related tasks, Face Attribute Classification (FAC) being a prominent example. Apart from this trend, Federated Learning (FL) is increasingly gaining traction as a scalable paradigm for distributed training. Existing FL approaches require data homogeneity to ensure fairness. However, this assumption is too restrictive in real-world settings. We propose F3, a novel FL framework for fair FAC under data heterogeneity. F3 adopts multiple heuristics to improve fairness across different demographic groups without requiring data homogeneity assumption. We demonstrate the efficacy of F3 by reporting empirically observed fairness measures and accuracy guarantees on popular face datasets. Our results suggest that F3 strikes a practical balance between accuracy and fairness for FAC.
A NOVEL DEMAND RESPONSE MODEL AND METHOD FOR PEAK REDUCTION IN SMART GRIDS – POWERTAC
Chandlekar Sanjay Rajendrabhai,Arthik Boroju,Shweta Jain,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2023
@inproceedings{bib_A_NO_2023, AUTHOR = {Rajendrabhai, Chandlekar Sanjay and Boroju, Arthik and Jain, Shweta and Gujar, Sujit P }, TITLE = {A NOVEL DEMAND RESPONSE MODEL AND METHOD FOR PEAK REDUCTION IN SMART GRIDS – POWERTAC}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2023}}
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.
AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities
Sankarshan Damle,Vlasis Koutsos,Dimitrios Papadopoulos,Dimitris Chatzopoulos,Sujit P Gujar
Technical Report, arXiv, 2023
@inproceedings{bib_AVeC_2023, AUTHOR = {Damle, Sankarshan and Koutsos, Vlasis and Papadopoulos, Dimitrios and Chatzopoulos, Dimitris and Gujar, Sujit P }, TITLE = {AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities}, BOOKTITLE = {Technical Report}. YEAR = {2023}}
In crowdsourcing systems, requesters publish tasks, and interested workers provide answers to get rewards. Worker anonymity motivates participation since it protects their privacy. Anonymity with unlinkability is an enhanced version of anonymity because it makes it impossible to “link” workers across the tasks they participate in. Another core feature of crowdsourcing systems is worker quality which expresses a worker’s trustworthiness and quantifies their historical performance. Notably, worker quality depends on the participation history, revealing information about it, while unlinkability aims to disassociate the workers’ identities from their past activity. In this work, we present AVeCQ, the first crowdsourcing system that reconciles these properties, achieving enhanced anonymity and verifiable worker quality updates. AVeCQ relies on a suite of cryptographic tools, such as zeroknowledge proofs, to (i) guarantee workers’ privacy, (ii) prove the correctness of worker quality scores and task answers, and (iii) commensurate payments. AVeCQ is developed modularly, where the requesters and workers communicate over a platform that supports pseudonymity, information logging, and payments. In order to compare AVeCQ with the state-of-theart, we prototype it over Ethereum. AVeCQ outperforms the state-of-the-art in three popular crowdsourcing tasks (image annotation, average review, and Gallup polls). For instance, for an Average Review task with 5 choices and 128 participating workers AVeCQ is 40% faster (including overhead to compute and verify the necessary proofs and blockchain transaction processing time) with the task’s requester consuming 87% fewer gas units.
Your Favorite Gameplay Speaks Volumes about You: Predicting User Behavior and Hexad Type
Reza Hadi Mogavi,Chao Deng,Jennifer Hoffman,Ehsan-Ul Haq,Sujit P Gujar,Antonio Bucchiarone,Pan Hui
Technical Report, arXiv, 2023
@inproceedings{bib_Your_2023, AUTHOR = {Mogavi, Reza Hadi and Deng, Chao and Hoffman, Jennifer and Haq, Ehsan-Ul and Gujar, Sujit P and Bucchiarone, Antonio and , Pan Hui }, TITLE = {Your Favorite Gameplay Speaks Volumes about You: Predicting User Behavior and Hexad Type}, BOOKTITLE = {Technical Report}. YEAR = {2023}}
In recent years, the gamification research community has widely and frequently questioned the effectiveness of one-size-fits-all gamification schemes. In consequence, personalization seems to be an important part of any successful gamification design. Personalization can be improved by understanding user behavior and Hexad player/user type. This paper comes with an original research idea: It investigates whether users’ game-related data (collected via various gamer-archetype surveys) can be used to predict their behavioral characteristics and Hexad user types in non-game (but gamified) contexts. The affinity that exists between the concepts of gamification and gaming provided us with the impetus for running this exploratory research. We conducted an initial survey study with 67 Stack Exchange users (as a case study). We discovered that users’ gameplay information could reveal valuable and helpful information about their behavioral characteristics and Hexad user types in a non-gaming (but gamified) environment. The results of testing three gamer archetypes (i.e., Bartle , Big Five, and BrainHex ) show that they can all help predict users’ most dominant Stack Exchange behavioral characteristics and Hexad user type better than a random labeler’s baseline. That said, of all the gamer archetypes analyzed in this paper, BrainHex performs the best. In the end, we introduce a research agenda for future work. Keywords: Game · Gamification · archetypes · Bartle · Big Five · BrainHex · Prediction · User behavior · CQA · Hexad.
QuickSync: A Quickly Synchronizing PoS-Based Blockchain Protocol
Siddiqui Shoeb Khaled,Sujit P Gujar
International Conference on Blockchain and Cryptocurrency, ICBC, 2023
@inproceedings{bib_Quic_2023, AUTHOR = {Khaled, Siddiqui Shoeb and Gujar, Sujit P }, TITLE = {QuickSync: A Quickly Synchronizing PoS-Based Blockchain Protocol}, BOOKTITLE = {International Conference on Blockchain and Cryptocurrency}. YEAR = {2023}}
To implement a blockchain, we need a blockchain protocol for all the nodes to follow. To design a blockchain protocol, we need a block publisher selection mechanism and a chain selection rule. In Proof-of-Stake (PoS) based blockchain protocols, block publisher selection mechanism selects the node to publish the next block based on the relative stake held by the node. However, PoS protocols may face vulnerability to fully adaptive corruptions. In literature, researchers address this issue at the cost of performance. In this paper, we propose a novel PoS-based blockchain protocol, QuickSync, to achieve security against fully adaptive corruptions without compromising on performance. We propose a metric called block power, a value defined for each block, derived from the output of the verifiable random function based on the digital signature of the block publisher. With this metric, we compute chain power, the sum of block powers of all the blocks comprising the chain, for all the valid chains. These metrics are a function of the block publisher's stake to enable the PoS aspect of the protocol. The chain selection rule selects the chain with the highest chain power as the one to extend. This chain selection rule hence determines the selected block publisher of the previous block. When we use metrics to define the chain selection rule, it may lead to vulnerabilities against Sybil attacks. QuickSync uses a Sybil attack resistant function implemented using histogram matching. We prove that QuickSync satisfies common prefix, chain growth, and chain quality properties and hence it is secure. We also show that it is resilient to different types of adversarial …
Rise of Algorithmic Trading in Today’s Changing Electricity Market
Anindya Pradhan,Easwar Subramanian,Sanjay Bhat,Praveen Paruchuri,Sujit P Gujar
International Conference and Exhibition on Smart Grids and Smart Cities, ISUW, 2022
Abs | | bib Tex
@inproceedings{bib_Rise_2022, AUTHOR = {Pradhan, Anindya and Subramanian, Easwar and Bhat, Sanjay and Paruchuri, Praveen and Gujar, Sujit P }, TITLE = {Rise of Algorithmic Trading in Today’s Changing Electricity Market}, BOOKTITLE = {International Conference and Exhibition on Smart Grids and Smart Cities}. YEAR = {2022}}
Electricity markets are getting more dynamic and complex today. On the one hand, there are outside-in factors like new entrants and increasing competition, regulatory mandates, and volatility of the electricity prices. In contrast, on the other hand, there are inside-out factors like the adoption of renewable energies, storages, and EV, emphasis on the generation and retail portfolio optimization together with creating affinity services around the empowered consumers. The paper will start with the introduction of this dynamic environment across the globe with a specific focus on Australia, the UK, and US electricity markets. Introduction of 5 min settlement in Australian Electricity Market, the rise of ancillary service products in the UK, or new roles like Community Choice Aggregators (CCA) in the US are some of the
Toward Mobile Distributed Ledgers
Dimitris Chatzopoulos,Anurag Jain,Sujit P Gujar,Boi Faltings,Pan Hui
IEEE Internet of Things Journal, IOT, 2022
Abs | | bib Tex
@inproceedings{bib_Towa_2022, AUTHOR = {Chatzopoulos, Dimitris and Jain, Anurag and Gujar, Sujit P and Faltings, Boi and Hui, Pan }, TITLE = {Toward Mobile Distributed Ledgers}, BOOKTITLE = {IEEE Internet of Things Journal}. YEAR = {2022}}
Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on Device-to-Device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distributed ledgers (DLs) to function. DLs, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However, such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing DLs are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce and analyze Mneme, a DAG-based DL that can be maintained solely by mobile devices. Mneme utilizes two novel consensus protocols: 1) Proof of Context (PoC) and 2) Proof of Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze Mneme’s security and justify the ability of PoC and PoE to guarantee the characteristics of DLs: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely
Differentially Private Federated Combinatorial Bandits with Constraints
Sambhav Solanki,Kanaparthy S V Samhita,Sankarshan Damle,Sujit P Gujar
The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Da, ECML PKDD, 2022
@inproceedings{bib_Diff_2022, AUTHOR = {Solanki, Sambhav and Samhita, Kanaparthy S V and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {Differentially Private Federated Combinatorial Bandits with Constraints}, BOOKTITLE = {The European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Da}. YEAR = {2022}}
There is a rapid increase in the cooperative learning paradigm in online learning settings, i.e., federated learning (FL). Unlike most FL settings, there are many situations where the agents are competitive. Each agent would like to learn from others, but the part of the information it shares for others to learn from could be sensitive; thus, it desires its privacy. This work investigates a group of agents working concurrently to solve similar combinatorial bandit problems while maintaining quality constraints. Can these agents collectively learn while keeping their sensitive information confidential by employing differential privacy? We observe that communicating can reduce the regret. However, differential privacy techniques for protecting sensitive information makes the data noisy and may deteriorate than help to improve regret. Hence, we note that it is essential to decide when to communicate and what shared data to learn to strike a functional balance between regret and privacy. For such a federated combinatorial MAB setting, we propose a Privacy-preserving Federated Combinatorial Bandit algorithm, P-FCB. We illustrate the efficacy of P-FCB through simulations. We further show that our algorithm provides an improvement in terms of regret while upholding quality threshold and meaningful privacy guarantees.
Coordinating Monetary Contributions in Participatory Budgeting
HARIS AZIZ,Sujit P Gujar,P Manisha,MASHBAT SUZUKI,JEREMY VOLLEN
International Symposium on Algorithmic Game Theory, SAGT, 2022
@inproceedings{bib_Coor_2022, AUTHOR = {AZIZ, HARIS and Gujar, Sujit P and Manisha, P and SUZUKI, MASHBAT and VOLLEN, JEREMY }, TITLE = {Coordinating Monetary Contributions in Participatory Budgeting}, BOOKTITLE = {International Symposium on Algorithmic Game Theory}. YEAR = {2022}}
We formalize a framework for coordinating the funding of projects and sharing the costs among agents with quasi-linear utility functions and individual budgets. Our model contains the classical discrete participatory budgeting model as a special case, while capturing other well-motivated problems. We propose several important axioms and objectives and study how well they can be simultaneously satisfied. One of our main results is that whereas welfare maximization admits an FPTAS, welfare maximization subject to a well-motivated and very weak participation requirement leads to a strong inapproximability result. We show that this result is bypassed if we consider some natural restricted valuations or when we take an average-case heuristic approach.
Individual fairness in feature-based pricing for monopoly markets
Shantanu Das,Swapnil Dhamal,Ganesh Ghalme,Shweta Jain,Sujit P Gujar
Uncertainty in Artificial Intelligence, UAI, 2022
@inproceedings{bib_Indi_2022, AUTHOR = {Das, Shantanu and Dhamal, Swapnil and Ghalme, Ganesh and Jain, Shweta and Gujar, Sujit P }, TITLE = {Individual fairness in feature-based pricing for monopoly markets}, BOOKTITLE = {Uncertainty in Artificial Intelligence}. YEAR = {2022}}
We study fairness in the context of feature-based price discrimination in monopoly markets. We propose a new notion of individual fairness, namely, α-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 optimal featurebased 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
BlockVac: A Universally Acceptable and Ideal Vaccination System on Blockchain
Manika Sharma,Kishore Kothapalli,Sujit P Gujar
International Conference on Blockchain, Blockchain, 2022
@inproceedings{bib_Bloc_2022, AUTHOR = {Sharma, Manika and Kothapalli, Kishore and Gujar, Sujit P }, TITLE = {BlockVac: A Universally Acceptable and Ideal Vaccination System on Blockchain}, BOOKTITLE = {International Conference on Blockchain}. YEAR = {2022}}
2022 IEEE International Conference on Blockchain (Blockchain) BLOC KVAC: A Un iversally Acceptable and Ideal Vaccination System on Blockchain Manik a Sharma Center for Securit y, Theory, and Algorithmic Research Intern ationa l Institute of Inform ation Technology, Hyderabad Gach ibowli, Hyderabad, India 500 032 manik a.sharm a @research.iiit.ac.in Kishore Kothap alli Cent er for Securit y, Theo ry, and Algorithmic Research Interna tional Institute of Information Technology, Hyderabad Gachibowli, Hyderabad , Indi a 500 032 kisho re @iiit.ac .in Sujit Gujar Machin e Learning Lab International Institute of Information Technology, Hyderabad Gachib owli, Hyderabad , India 500 032 suj it.gujar @iiit.ac.in Abstract-Vaccines are essential in pro tecting indivi dua ls and commun ities from the risk of ha rmful an d fatal diseases. The wor ld is migra ting towards the digitization of vacci nation docu- mentation. Still, the current digita l vacci nation is a centra lized mode l, lacking a nnive rsal acceptance. A Universally Acceptable an d Id eal Vacci nat ion System (UAIVS ) sho nld possess (a) a sta ndard vaccination cert ificate ver ificat ion algorithm, (h) p r i- vacy to per sonal in form a tion, (c) sca lab ilit y, (d) s npport lor all vacci nat ions, (e) acco u ntab ility for vaccination information access, and (f) a sco pe for scientific researc h a nd d evelopm en t. Blockc ha in tec hno logy int ro dnces d ecentr alizat ion, immn tability, acco unta bility, per sistence, and liveliness. T hese pro per ties ma ke block cha in an ideal can di da te to solve the existing pro blems in digital vacci nat ion. In this pa per, we prop ose a novel blockchain- base d syste m, n am ely BLO CKVAC, to implem ent a UA IVS . F urt her more , o ur wor k provi des a way to track an individ nal's an d fa mily's vacc ination histo ry, which is esse ntial for sc ient ific research a nd developm ent . BLOCKVAC is highly modular, sca l- a ble, an d cost -efficien t, pr oviding eno ugh roo m for fnt n re feature addi tio ns. The c urre nt works lack cost and sca lab ility ana lysis. WI' show thc scalability of o ur system t hro ugh a th oron gh a nalys is. O ur impl em entation shows t hat add ing one vacc inati on re cor d costs 7 . l(j ~2 ~ x 10- 6 ETH ( ~ U.U26US D) for reg istratio n, 2.5089 x 10- 5 ETH ( ~ 0.07 8USD) for vaccina tion, a nd th e syste m ca n easi ly han dl e np to 20K vaccinations per hon r. Ind ex Terms- B1ockc ha in, Eth ere um, Sm art Contrac ts, Public Acco unta bility, Sca lab ilit y I. I N TR O D UC TI O N The vaccination process, also known as imm unization , was introduced in the late 18th century by the British physician Edward Jenn er against the deadly smallpox virus [ I]. Since then. it has become an inevitab le medical proc edur e, protecting individuals and communities from harmful and fatal diseases. The World Hea lth Organi zation (WHO) estimates that vac- cination saves around 2.5 millio n child lives every year [2]. A record of vacci nation details massively aid s in providing qualit y health care to individuals [3]. Whi le secure storage and verificat ion of vaccination details are challenges even within a country, it is tediou s to merge them from across all the countries [4 ]. Moreover. a definitive process is the need of the hour to verify the required vaccinati on certification for travelers when they enter a country. We wou ld like to than k MeitY and Ripp le for fundin g this research . O ver view of existing vac cina tion mod els: Traditional paper- based vaccination records [5] are prone to challenges such as the possibil ity of losing, damaging, or forging the records without any accountability. Digital solutions replace the need for paper, provide an immutable card, and reduc e manual labor [6]. However, the current vacci nation systems follow a centralized model, where the users need to trust the cent ral autho rity. Further. these sys tems are prone to single-point failures and jeopardize data security P 1. Moreover, current vaccination portal s mainly deal with just slot bookings and issuin g non -verifiab le vaccination certificates. Mo tiva tion: Th e Covid-19 pandemic has caused a digital revolution in vaccination data managem ent. Countri es are shifting towards a digital solution to secure vaccination data ami issue certificates. However, such a system should be universally acceptabl e. We identi fy the properties requ ired for such a sys tem and call it a Universally Acceptable and Ideal Vaccination System (UA IVS). We furt her categorize the proper- ties of UAIVS into two subcategories: Universally Acceptable Vaccination System and Ideal Va ccination System. A Universally Acce ptable Vaccination System co
Dynamic matching in campus placements: The benefits and affordability of the dream option
ASHUTOSH RANJAN,Sujit P Gujar,Vinay Ramani
IIMB Management Review, IMR, 2022
@inproceedings{bib_Dyna_2022, AUTHOR = {RANJAN, ASHUTOSH and Gujar, Sujit P and Ramani, Vinay }, TITLE = {Dynamic matching in campus placements: The benefits and affordability of the dream option}, BOOKTITLE = {IIMB Management Review}. YEAR = {2022}}
We propose a new approach to improving student outcomes - the provision of the dream option that allows a student with a job offer to participate in the placement process again. Comparing three different student preference structures, we show that the dream option improves stability; however, it does not always improve student happiness and rank efficiency. Nevertheless, imposing a particular structure on student preferences, namely the sequential preference condition, improves both student happiness and rank efficiency. We recommend when to use the dream option and when not to use it. © 2022 Published by Elsevier Ltd on behalf of Indian Institute of Management Bangalore. This is an open access article under the CC BY-NC-ND license
Interlude: Balancing Chaos And Harmony For Fair and Fast Blockchains
Anurag Jain,Srinathan Kannan,Sujit P Gujar
Technical Report, arXiv, 2022
@inproceedings{bib_Inte_2022, AUTHOR = {Jain, Anurag and Kannan, Srinathan and Gujar, Sujit P }, TITLE = {Interlude: Balancing Chaos And Harmony For Fair and Fast Blockchains}, BOOKTITLE = {Technical Report}. YEAR = {2022}}
Blockchains lie at the heart of Bitcoin and other cryptocurrencies that have shown great promise to revolutionize finance and commerce. Although they are gaining increasing popularity, they face technical challenges when it comes to scaling to support greater demand while maintaining their desirable security properties. In an exciting line of recent work, many researchers have proposed various scalable blockchain protocols that demonstrate the potential to solve these challenges. However, many of these protocols come with the assumptions of honest majority and symmetric network access which may not accurately reflect the real world where the participants may be self-interested or rational. Secondly, these works show that their protocol works in an ideal environment where each party has equal access to the network whereas different parties have varying latencies and network speeds. These assumptions may render the protocols susceptible to security threats in the real world, as highlighted by the literature focused on exploring gametheoretic attacks on these protocols. We propose a scalable blockchain protocol, Interlude, which comes with the typical security guarantees while focusing on game-theoretic soundness and network fairness. The novelty of Interlude is that it has a relatively simple design consisting of a sequence of parallel blocks containing disjoint transaction sets that can be mined quickly followed by a series block that is slow to mine and gives the honest parties in the network time to synchronize. Thus, between the chaos of parallel blocks, our blockchain protocol masquerades an interlude moment of harmony in series blocks that synchronize the network.
EEF1-NN: Efficient and EF1 allocations through Neural Networks
Shaily Ashokkumar Mishra,P Manisha,Sujit P Gujar
Pacific Rim International Conference on Artificial Intelligence, PRICAI, 2022
@inproceedings{bib_EEF1_2022, AUTHOR = {Mishra, Shaily Ashokkumar and Manisha, P and Gujar, Sujit P }, TITLE = {EEF1-NN: Efficient and EF1 allocations through Neural Networks}, BOOKTITLE = {Pacific Rim International Conference on Artificial Intelligence}. YEAR = {2022}}
Neural networks have shown state-of-the-art performance in designing auctions, where the network learns the optimal allocations and payment rule to ensure desirable properties. Motivated by the same, we focus on learning fair division of resources, with no payments involved. Our goal is to allocate the items, goods and/or chores efficiently among the fair allocations. By fair, we mean an allocation that is Envy-free (EF). However, such an allocation may not always exist for indivisible resources. Therefore, we consider the relaxed notion, Envy-freeness up to one item (EF1) that is guaranteed to exist. However, it is not enough to guarantee EF1 since the allocation of empty bundles is also EF1. Hence, we add the further constraint of efficiency, maximum utilitarian social welfare (USW). In general finding, USW allocations among EF1 is an NP-Hard problem even when valuations are additive. In this work, we design a network for this task which we refer to as EEF1-NN. We propose an UNet inspired architecture, Lagrangian loss function, and training procedure to obtain desired results. We show that EEF1-NN finds allocation close to optimal USW allocation and ensures EF1 with a high probability for different distributions over input valuations. Compared to existing approaches EEF1-NN empirically guarantees higher USW. Moreover, EEF1-NN is scalable and determines the allocations much faster than solving it as a constrained optimization problem.
Fair Allocation with Special Externalities
Shaily Ashokkumar Mishra,P Manisha,Sujit P Gujar
Pacific Rim International Conference on Artificial Intelligence, PRICAI, 2022
@inproceedings{bib_Fair_2022, AUTHOR = {Mishra, Shaily Ashokkumar and Manisha, P and Gujar, Sujit P }, TITLE = {Fair Allocation with Special Externalities}, BOOKTITLE = {Pacific Rim International Conference on Artificial Intelligence}. YEAR = {2022}}
Most of the existing algorithms for fair division do not consider externalities. Under externalities, the utility an agent obtains depends not only on its allocation but also on the allocation of other agents. An agent has a positive (negative) value for the assigned goods (chores). This work focuses on a special case of externality, i.e., an agent receives positive or negative value for unassigned items independent of which other agent gets it. We show that it is possible to adapt existing algorithms using a transformation to ensure certain fairness and efficiency notions in this setting. Despite the positive results, fairness notions like proportionality need to be re-defined. Further, we prove that maximin share (MMS) may not have any multiplicative approximation in this setting. Studying this domain is a stepping stone towards full externalities where ensuring fairness is much more challenging
More Gamification Is Not Always Better: A Case Study of Promotional Gamification in a Question Answering Website
REZA HADI MOGAVI,EHSAN-UL HAQ,Sujit P Gujar,PAN HUI,XIAOJUAN MA
Conference on Computer-Supported Cooperative Work , CSCW, 2022
@inproceedings{bib_More_2022, AUTHOR = {MOGAVI, REZA HADI and HAQ, EHSAN-UL and Gujar, Sujit P and HUI, PAN and MA, XIAOJUAN }, TITLE = {More Gamification Is Not Always Better: A Case Study of Promotional Gamification in a Question Answering Website}, BOOKTITLE = {Conference on Computer-Supported Cooperative Work }. YEAR = {2022}}
Community Question Answering Websites (CQAs) like Stack Overflow rely on continuous user contributions to keep their services active. Nevertheless, they often undergo a sharp decline in their user participation during the holiday season, undermining their performance. To address this issue, some CQAs have developed their own special promotional gamification schemes to incentivize users to maintain their contributions throughout the holiday season. These promotional gamification schemes are often time-limited, optional, and run alongside the default gamification schemes of their websites. However, the impact of such promotional gamification schemes on user behavior remains largely unexplored in the existing literature. This paper takes the first steps toward filling this knowledge gap by conducting a large-scale empirical study of a particular promotional gamification scheme called Winter Bash (WB) on the CQA of Stack Overflow. According to our findings, promotional gamification schemes may not be the panacea they are portrayed to be. For example, in the case of WB, we find that the scheme is not effective for improving the collective engagement of all users. Only some particular user types (i.e., experienced and reputable users) are often provoked under WB. Most novice users, who comprise the majority of Stack Overflow website’s user base, seem to be indifferent to such a gamification scheme. Our research also shows the importance of studying the quantity and quality of user engagement in unison to better understand the effectiveness of a gamification scheme. Previous gamification studies in the literature have focused predominantly on studying the quantity of user engagement alone. Last but not least, we conclude our paper by presenting some practical considerations for improving the design of future promotional gamification schemes in CQAs and similar platforms.
COMBINATORIAL CIVIC CROWDFUNDING WITH BUDGETED AGENTS: WELFARE OPTIMALITY AT EQUILIBRIUM AND OPTIMAL DEVIATION
Sankarshan Damle,P Manisha,Sujit P Gujar
Technical Report, arXiv, 2022
@inproceedings{bib_COMB_2022, AUTHOR = {Damle, Sankarshan and Manisha, P and Gujar, Sujit P }, TITLE = {COMBINATORIAL CIVIC CROWDFUNDING WITH BUDGETED AGENTS: WELFARE OPTIMALITY AT EQUILIBRIUM AND OPTIMAL DEVIATION}, BOOKTITLE = {Technical Report}. YEAR = {2022}}
Civic Crowdfunding (CC) uses the “power of the crowd” to garner contributions towards public projects. As these projects are non-excludable, agents may prefer to “free-ride,” resulting in the project not being funded. For single project CC, researchers propose to provide refunds to incentivize agents to contribute, thereby guaranteeing the project’s funding. These funding guarantees are applicable only when agents have an unlimited budget. This work focuses on a combinatorial setting, where multiple projects are available for CC and agents have a limited budget. We study certain specific conditions where funding can be guaranteed. Further, funding the optimal social welfare subset of projects is desirable when every available project cannot be funded due to budget restrictions. We prove the impossibility of achieving optimal welfare at equilibrium for any monotone refund scheme. We then study different heuristics that the agents can use to contribute to the projects in practice. Through simulations, we demonstrate the heuristics’ performance as the average-case trade-off between welfare obtained and agent utility.
Multi-unit Double Auctions: Equilibrium Analysis and Bidding Strategy using DDPG in Smart-grids
Chandlekar Sanjay Rajendrabhai,Easwar Subramanian,Sanjay Bhat,Praveen Paruchuri,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2022
@inproceedings{bib_Mult_2022, AUTHOR = {Rajendrabhai, Chandlekar Sanjay and Subramanian, Easwar and Bhat, Sanjay and Paruchuri, Praveen and Gujar, Sujit P }, TITLE = {Multi-unit Double Auctions: Equilibrium Analysis and Bidding Strategy using DDPG in Smart-grids}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2022}}
We present a Nash equilibrium analysis for single-buyer singleseller multi-unit 𝑘-double auctions for scaling-based bidding strategies. We then design a Deep Deterministic Policy Gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent to suggest bids that approximately achieve the above Nash equilibrium. We expand DDPGBBS to be helpful in more complex settings with multiple buyers/sellers trading multiple units in a Periodic Double Auction (PDA), such as the wholesale market in smart-grids. We demonstrate the efficacy of DDPGBBS with Power Trading Agent Competition’s (PowerTAC) wholesale market PDA as a testbed.
VidyutVanika21: An Autonomous Intelligent Broker for Smart-grids
Chandlekar Sanjay Rajendrabhai,Bala Suraj Pedasingu,Easwar Subramanian,Sanjay Bhat,Praveen Paruchuri,Sujit P Gujar
International Joint Conference on Artificial Intelligence, IJCAI, 2022
@inproceedings{bib_Vidy_2022, AUTHOR = {Rajendrabhai, Chandlekar Sanjay and Pedasingu, Bala Suraj and Subramanian, Easwar and Bhat, Sanjay and Paruchuri, Praveen and Gujar, Sujit P }, TITLE = {VidyutVanika21: An Autonomous Intelligent Broker for Smart-grids}, BOOKTITLE = {International Joint Conference on Artificial Intelligence}. YEAR = {2022}}
An autonomous broker that liaises between retail customers and power-generating companies (GenCos) is essential for the smart grid ecosystem. The effciency brought in by such brokers to the smart grid setup can be studied through a well-developed simulation environment. In this paper, we describe the design of one such intelligent energy broker called VidyutVanika21 (VV21) and analyze its performance using a simulation platform called PowerTAC (Power Trading Agent Competition). Specifcally, we discuss the retail (VV21–RM) and wholesale market (VV21–WM) modules of VV21 that help the broker achieve high net profts in a competitive setup. Supported by game-theoretic analysis, the VV21–RM designs tariff contracts that a) maintain a balanced portfolio of different types of customers; b) sustain an appropriate level of market share, and c) introduce surcharges on customers to reduce energy usage during peak demand times. The VV21–WM aims to reduce the cost of procurement by following the supply curve of the GenCo to identify its lowest ask for each auction which is then used to generate suitable bids. We further demonstrate the effcacy of the retail and wholesale strategies of VV21 in PowerTAC 2021 fnals and through several controlled experiments.
How Private Is Your RL Policy? An Inverse RL Based Analysis Framework
Kritika Prakash,Fiza Husain,Praveen Paruchuri,Sujit P Gujar
American Association for Artificial Intelligence, AAAI, 2022
@inproceedings{bib_How__2022, AUTHOR = {Prakash, Kritika and Husain, Fiza and Paruchuri, Praveen and Gujar, Sujit P }, TITLE = {How Private Is Your RL Policy? An Inverse RL Based Analysis Framework}, BOOKTITLE = {American Association for Artificial Intelligence}. YEAR = {2022}}
Reinforcement Learning (RL) enables agents to learn how to perform various tasks from scratch. In domains like autonomous driving, recommendation systems, and more, optimal RL policies learned could cause a privacy breach if the policies memorize any part of the private reward. We study the set of existing differentially-private RL policies derived from various RL algorithms such as Value Iteration, Deep-Q Networks, and Vanilla Proximal Policy Optimization. We propose a new Privacy-Aware Inverse RL analysis framework (PRIL) that involves performing reward reconstruction as an adversarial attack on private policies that the agents may deploy. For this, we introduce the reward reconstruction attack, wherein we seek to reconstruct the original reward from a privacy-preserving policy using the Inverse RL algorithm. An adversary must do poorly at reconstructing the original reward function if the agent uses a tightly private policy. Using this framework, we empirically test the effectiveness of the privacy guarantee offered by the private algorithms on instances of the FrozenLake domain of varying complexities. Based on the analysis performed, we infer a gap between the current standard of privacy offered and the standard of privacy needed to protect reward functions in RL. We do so by quantifying the extent to which each private policy protects the reward function by measuring distances between the original and reconstructed rewards.
Learning Equilibrium Contributions in Multi-project Civic Crowdfunding
P Manisha,Sankarshan Damle,Sujit P Gujar
International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, WI, 2022
@inproceedings{bib_Lear_2022, AUTHOR = {Manisha, P and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {Learning Equilibrium Contributions in Multi-project Civic Crowdfunding}, BOOKTITLE = {International Joint Conferences on Web Intelligence and Intelligent Agent Technologies}. YEAR = {2022}}
Crowdfunding is an efficient method for raising funds for projects. When used for non-excludable public projects, the process is termed Civic Crowdfunding (CC) and is an active research area. Researchers have analyzed CC in game-theoretic settings assuming that agents are interested in (and contribute to) a single public project. Gen- eralizing the existing single project theory to determine agents’ equilibrium contributions for multiple projects is non-trivial – espe- cially with budget-constrained agents. This work hypothesizes that the agents can learn their equilibrium contributions with repeated participation in multi-project CC. We model CC as a game to vali- date the hypothesis and build an RL-based simulator: EqC-Learner. We first show that EqC-Learner learns a policy that mimics equi- librium contributions in a single project case for the existing CC mechanisms. To validate EqC-Learner for the multi-project case, we present certain theoretical results for the general multi-project case. Via extensive simulation-based experiments, we show that the learned contributions in EqC-Learner follow all the available theo- retical analysis. Thus, we believe that such an RL-based simulator can learn equilibrium contributions for the general multi-project CC mechanism
Tiramisu: Layering Consensus Protocols for Scalable and Secure Blockchains
Anurag Jain,Sanidhay Arora,Sankarshan Damle,Sujit P Gujar
Technical Report, arXiv, 2022
@inproceedings{bib_Tira_2022, AUTHOR = {Jain, Anurag and Arora, Sanidhay and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {Tiramisu: Layering Consensus Protocols for Scalable and Secure Blockchains}, BOOKTITLE = {Technical Report}. YEAR = {2022}}
Cryptocurrencies are poised to revolutionize the modern economy by democratizing commerce. These currencies operate on top of blockchain-based distributed ledgers. Existing permissionless blockchain-based protocols offer unparalleled benefits like decentralization, anonymity, and transparency. However, these protocols suffer in performance which hinders their widespread adoption. In particular, high time-to-finality and low transaction rates keep them from replacing centralized payment systems such as the Visa network. Permissioned blockchain protocols offer attractive performance guarantees, but they are not considered suitable for deploying decentralized cryptocurrencies due to their centralized nature. Researchers have developed several multi-layered blockchain protocols that combine both permissioned and permissionless blockchain protocols to achieve high performance along with decentralization. The key idea with existing layered blockchain protocols in literature is to divide blockchain operations into two layers and use different types of blockchain protocols to manage each layer. However, many such works come with the assumptions of honest majority which may not accurately reflect the real world where the participants may be self-interested or rational. These assumptions may render the protocols susceptible to security threats in the real world, as highlighted by the literature focused on exploring game-theoretic attacks on these protocols. We generalize the “layered” approach taken by existing protocols in the literature and present a framework to analyze the system in the BAR Model and provide a generalized game-theoretic analysis of such protocols. Using our analysis, we identify the critical system parameters required for a distributed ledger’s secure operation in a more realistic setting.
REFORM: Reputation Based Fair and Temporal RewardFramework for Crowdsourcing
Kanaparthy S V Samhita,Sankarshan Damle,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2022
@inproceedings{bib_REFO_2022, AUTHOR = {Samhita, Kanaparthy S V and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {REFORM: Reputation Based Fair and Temporal RewardFramework for Crowdsourcing}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2022}}
Crowdsourcing is an effective method to collect data by employingdistributed human population. Researchers introduce Peer-BasedMechanisms (PBMs) in crowdsourcing settings to incentivize agentsto report accurately. We observe that with PBMs, crowdsourcingsystems may not be fair. Unfair rewards for the agents may discour-age participation. This work aims to build a general frameworkthat assures fairness for PBMs in a temporal setting, i.e., wherereports are time-sensitive. Towards this, we introduce two notionsof fairness for PBMs, namely𝛾-fairnessandqualitative fairness. Tosatisfy these notions, our framework provides trustworthy agentswith additional chances of pairing. We introduce Temporal Reputa-tion Model (TERM) to quantify agents’ trustworthiness across tasks.Having TERM, we present our iterative framework, REFORM, thatcan adopt the reward scheme of any existing PBM. We demonstrateREFORM’s significance by deploying the framework with RPTSC’sreward scheme and prove that REFORM with RPTSC considerablyimproves fairness; while incentivizing truthful and early reports.
Fair Federated Learning for Heterogeneous Data
Samhita Kanaparthy,Manisha Padala, Sankarshan Damle,Sujit P Gujar
Joint International Conference on Data Science & Management of Data, CODS-COMAD, 2022
@inproceedings{bib_Fair_2022, AUTHOR = {Kanaparthy, Samhita and Padala, Manisha and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {Fair Federated Learning for Heterogeneous Data}, BOOKTITLE = {Joint International Conference on Data Science & Management of Data}. YEAR = {2022}}
We consider the problem of achieving fair classification in Federated Learning (FL) under data heterogeneity. Most of the approaches pro- posed 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 and accuracy on CelebA and UTK datasets
Budgeted Combinatorial Multi-Armed Bandits
Debojit Das,Shweta Jain,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2022
@inproceedings{bib_Budg_2022, AUTHOR = {Das, Debojit and Jain, Shweta and Gujar, Sujit P }, TITLE = {Budgeted Combinatorial Multi-Armed Bandits}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2022}}
We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a super-arm consisting of one or more arms. The goal is to minimize the total expected regret after all rounds within a limited budget. Existing techniques in this literature either fix the budget per round or fix the number of arms pulled in each round. Our setting is more general where based on the remaining budget and remaining number of rounds, the algorithm can decide how many arms to be pulled in each round. First, we propose CBwK-Greedy-UCB algorithm, which uses a greedy technique, CBwK-Greedy, to allocate the arms to the rounds. Next, we propose a reduction of this problem to Bandits with Knapsacks (BwK) with a single pull. With this reduction, we propose CBwK-LP-UCB that uses PrimalDualBwK ingeniously. We rigorously prove regret bounds for CBwK-LP-UCB. We experimentally compare the two algorithms and observe that CBwK-Greedy- UCB performs incrementally better than CBwK-LP-UCB. We also show that for very high budgets, the regret goes to zero.
Effect of Input Noise Dimension in GANs
P Manisha,Debojit Das,Sujit P Gujar
International Conference on Neural Information Processing, ICONIP, 2021
Abs | | bib Tex
@inproceedings{bib_Effe_2021, AUTHOR = {Manisha, P and Das, Debojit and Gujar, Sujit P }, TITLE = {Effect of Input Noise Dimension in GANs}, BOOKTITLE = {International Conference on Neural Information Processing}. YEAR = {2021}}
Generative Adversarial Networks (GANs) are by far the most successful generative models. Learning the transformation which maps a low dimensional input noise to the data distribution forms the foundation for GANs. Despite their application in various domains, they are prone to certain challenges like mode collapse and unstable training. To overcome the challenges, researchers have proposed novel loss functions, architectures, and optimization methods. Unlike the previous approaches, we focus on the input noise and its role in the generation in our work here. We aim to quantitatively and qualitatively study the effect of the dimension of the input noise on the performance of GANs. For quantitative measures, typically Fréchet Inception Distance (FID) and Inception Score (IS) are used as performance measure on image data-sets. We compare the FID and IS values for DCGAN and WGAN-GP. We use three different image data-sets – each consisting of different levels of complexity. Our experiments show that the right dimension of input noise for optimal results depends on the data-set and architecture used. We also observe that the state of the art performance measures does not provide enough
Blockchain-based Practical Multi-agent Secure Comparison and its Application in Auctions
Sankarshan Damle,Boi Faltings,Sujit P Gujar
International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, WI, 2021
Abs | | bib Tex
@inproceedings{bib_Bloc_2021, AUTHOR = {Damle, Sankarshan and Faltings, Boi and Gujar, Sujit P }, TITLE = {Blockchain-based Practical Multi-agent Secure Comparison and its Application in Auctions}, BOOKTITLE = {International Joint Conferences on Web Intelligence and Intelligent Agent Technologies}. YEAR = {2021}}
AI applications find widespread use in a variety of domains. For further acceptance, mostly when multiple agents interact with the system, we must aim to preserve the privacy of participants information in such applications. Towards this, the Yao’s Millionaires’ problem (YMP), i.e., to determine the richer among two millionaires’ privately, finds relevance. This work presents a novel, practical, and verifiable solution to YMP, namely, Secure Comparison Protocol (SCP). We show that SCP achieves this comparison in a constant number of rounds, without using encryption and not requiring the participants’ continuous involvement. SCP uses semi-trusted third parties - which we refer to as privacy accountants - for the comparison, who do not learn any information about the values. That is, the probability of information leak is negligible in the problem size. In SCP, we also leverage the Ethereum network for
FNNC: Achieving fairness through neural networks
P Manisha,Sujit P Gujar
International Joint Conference on Artificial Intelligence, IJCAI, 2021
@inproceedings{bib_FNNC_2021, AUTHOR = {Manisha, P and Gujar, Sujit P }, TITLE = {FNNC: Achieving fairness through neural networks}, BOOKTITLE = {International Joint Conference on Artificial Intelligence}. YEAR = {2021}}
In classification models fairness can be ensured by solving a constrained optimization problem. We focus on fairness constraints like Disparate Impact, Demographic Parity, and Equalized Odds, which are non-decomposable and non-convex. Researchers define convex surrogates of the constraints and then apply convex optimization frameworks to obtain fair classifiers. Surrogates serve only as an upper bound to the actual constraints, and convexifying fairness constraints might be challenging. We propose a neural network-based framework, FNNC, to achieve fairness while maintaining high accuracy in classification. The above fairness constraints are included in the loss using Lagrangian multipliers. We prove bounds on generalization errors for the constrained losses which asymptotically go to zero. The network is optimized using two-step mini-batch stochastic gradient descent. Our experiments show that FNNC performs as good as the state of the art, if not better. The experimental evidence supplements our theoretical guarantees. In summary, we have an automated solution to achieve fairness in classification, which is easily extendable to many fairness constraints.
Designing Bounded min-knapsack Bandits algorithm for Sustainable demand response
Akansha Singh,P Meghana Reddy,Shweta Jain,Sujit P Gujar,Zoltan Nagy
International Conference on Machine Learning, ICML-W, 2021
@inproceedings{bib_Desi_2021, AUTHOR = {Singh, Akansha and Reddy, P Meghana and Jain, Shweta and Gujar, Sujit P and Nagy, Zoltan }, TITLE = {Designing Bounded min-knapsack Bandits algorithm for Sustainable demand response}, BOOKTITLE = {International Conference on Machine Learning}. YEAR = {2021}}
Around 40% of global energy produced is consumed by buildings. By using renewable energy resources we can alleviate the dependence on electrical grids. Recent trends focus on incentivizing consumers to reduce their demand consumption during peak hours for sustainable demand response. To minimize the loss, the distributor companies should target the right set of consumers and demand the right amount of electricity reductions.This paper proposes a novel bounded integer min-knapsack algorithm and shows that the algorithm, while allowing for multiple unit reduction, also optimizes the loss to the distributor company within a factor of two (multiplicative) and a problem dependent additive constant. Existing CMAB algorithms fail to work in this setting due to nonmonotonicity of reward function and time varying optimal sets. We propose a novel algorithm (TwinMinKPDR-CB) to learn these compliance probabilities efficiently. Twin-MinKPDR-CB works for non-monotone reward functions, bounded minknapsack constraints, and time-varying optimal sets. We find that Twin-MinKPDR-CB achieves sub-linear regret of O(log T) with T being the number of rounds demand response is run.
Effect of Input Noise Dimension in GANs
P Manisha,Debojit Das,Sujit P Gujar
International Conference on Neural Information Processing, ICONIP, 2021
@inproceedings{bib_Effe_2021, AUTHOR = {Manisha, P and Das, Debojit and Gujar, Sujit P }, TITLE = {Effect of Input Noise Dimension in GANs}, BOOKTITLE = {International Conference on Neural Information Processing}. YEAR = {2021}}
Generative Adversarial Networks (GANs) are by far the most successful generative models. Learning the transformation which maps a low dimensional input noise to the data distribution forms the foundation for GANs. Although they have been applied in various domains, they are prone to certain challenges like mode collapse and unstable training. To overcome the challenges, researchers have proposed novel loss functions, architectures, and optimization methods. In our work here, unlike the previous approaches, we focus on the input noise and its role in the generation. We aim to quantitatively and qualitatively study the effect of the dimension of the input noise on the performance of GANs. For quantitative measures, typically Fr´echet Inception Distance (FID) and Inception Score (IS) are used as performance measure on image data-sets. We compare the FID and IS values for DCGAN and WGAN-GP. We use three different image data-sets – each consisting of different levels of complexity. Through our experiments, we show that the right dimension of input noise for optimal results depends on the data-set and architecture used. We also observe that the state of the art performance measures does not provide enough useful insights. Hence we conclude that we need further theoretical analysis for understanding the relationship between the low dimensional distribution and the generated images. We also require better performance measures.
PUPoW: A Framework for Designing Blockchains with Practically-Useful-Proof-of-Work & VanityCoin
Yash Chaurasia,Visvesh S Subramanian,Sujit P Gujar
International Conference on Blockchain, Blockchain, 2021
@inproceedings{bib_PUPo_2021, AUTHOR = {Chaurasia, Yash and Subramanian, Visvesh S and Gujar, Sujit P }, TITLE = {PUPoW: A Framework for Designing Blockchains with Practically-Useful-Proof-of-Work & VanityCoin}, BOOKTITLE = {International Conference on Blockchain}. YEAR = {2021}}
Bitcoin is the first of its kind, a truly decentralized and anonymous cryptocurrency. To realize it, it has developed a blockchain technology using the concept of ‘Proof of Work’ (PoW). The miners, nodes responsible for writing transaction database, solve a cryptographic puzzle to claim the right to write to the database. Though bitcoin and many other relevant cryptocurrencies such as ether use revolutionary ideas, the main criticism involves the computing resource and energy consump- tion to solve the puzzles that have otherwise no use. There are attempts to use the PoW to do something useful, commonly referred to as Proof-of-Useful-Work (PoUW). In this paper, we attempt to (i) make PoUW more usable – describe how a central problem setter can crowdsource their work as PoUW and (ii) in the true spirit of blockchains, decentralize the role of problem setter, whom we call puzzlers. We propose a formal framework to do so, namely PUPoW. PUPoW has an inbuilt provision of payments from puzzler to the miner who solves its puzzle. Additionally, miners have the option to not rely on continuous feed of the puzzles and instead use original PoW puzzles. We also propose a way to use PUPoW for solving TOR vanity URL generation and bitcoin vanity address generation problems. We call this PUPoW blockchain solving vanity address generation problems as VanityCoin. Both the problems need to generate public keys from private keys such that resultant addresses are of interest. Such key pairs are found only by a brute force search. However, there are privacy concerns that miners would know the private keys of the puzzlers. We resolve this by splitting the private keys, and the miners would know only one part of it. In summary, we are proposing how PoW can be made practically useful, and we believe such an approach is needed for PoW blockchains to survive.
Differentially Private Multi-Agent Constraint Optimization
Sankarshan Damle,Aleksei Triastcyn Boi Faltings,Sujit P Gujar
International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, WI, 2021
@inproceedings{bib_Diff_2021, AUTHOR = {Damle, Sankarshan and Faltings, Aleksei Triastcyn Boi and Gujar, Sujit P }, TITLE = {Differentially Private Multi-Agent Constraint Optimization}, BOOKTITLE = {International Joint Conferences on Web Intelligence and Intelligent Agent Technologies}. YEAR = {2021}}
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.
Mechanism Design without Money for Fair Allocations
P Manisha,Sujit P Gujar
Technical Report, arXiv, 2021
@inproceedings{bib_Mech_2021, AUTHOR = {Manisha, P and Gujar, Sujit P }, TITLE = {Mechanism Design without Money for Fair Allocations}, BOOKTITLE = {Technical Report}. YEAR = {2021}}
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.
REFORM: Reputation Based Fair and Temporal Reward Framework for Crowdsourcing
Kanaparthy S V Samhita,Sankarshan Damle,Sujit P Gujar
Technical Report, arXiv, 2021
@inproceedings{bib_REFO_2021, AUTHOR = {Samhita, Kanaparthy S V and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {REFORM: Reputation Based Fair and Temporal Reward Framework for Crowdsourcing}, BOOKTITLE = {Technical Report}. YEAR = {2021}}
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.
DESIGNING REFUND BONUS SCHEMES FOR PROVISION POINT MECHANISM IN CIVIC CROWDFUNDING
Sankarshan Damle,Moin Hussain Moti,Sujit P Gujar,Praphul Chandra
Pacific Rim International Conference on Artificial Intelligence, PRICAI, 2021
@inproceedings{bib_DESI_2021, AUTHOR = {Damle, Sankarshan and Moti, Moin Hussain and Gujar, Sujit P and Chandra, Praphul }, TITLE = {DESIGNING REFUND BONUS SCHEMES FOR PROVISION POINT MECHANISM IN CIVIC CROWDFUNDING}, BOOKTITLE = {Pacific Rim International Conference on Artificial Intelligence}. YEAR = {2021}}
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.
Fair Federated Learning for Heterogeneous Data
Kanaparthy S V Samhita,P Manisha,Sujit P Gujar
Joint International Conference on Data Science & Management of Data, CODS-COMAD, 2021
@inproceedings{bib_Fair_2021, AUTHOR = {Samhita, Kanaparthy S V and Manisha, P and Gujar, Sujit P }, TITLE = {Fair Federated Learning for Heterogeneous Data}, BOOKTITLE = {Joint International Conference on Data Science & Management of Data}. YEAR = {2021}}
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.
Fair and Efficient Resource Allocation with Externalities
Shaily Ashokkumar Mishra,P Manisha,Sujit P Gujar
Technical Report, arXiv, 2021
@inproceedings{bib_Fair_2021, AUTHOR = {Mishra, Shaily Ashokkumar and Manisha, P and Gujar, Sujit P }, TITLE = {Fair and Efficient Resource Allocation with Externalities}, BOOKTITLE = {Technical Report}. YEAR = {2021}}
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.
Federated Learning Meets Fairness and Differential Privacy
P Manisha,Sankarshan Damle,Sujit P Gujar
International Conference on Neural Information Processing, ICONIP, 2021
@inproceedings{bib_Fede_2021, AUTHOR = {Manisha, P and Damle, Sankarshan and Gujar, Sujit P }, TITLE = {Federated Learning Meets Fairness and Differential Privacy}, BOOKTITLE = {International Conference on Neural Information Processing}. YEAR = {2021}}
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.
Ballooning multi-armed bandits
Ganesh Ghalme,Swapnil Dhama,Shweta Jain,Sujit P Gujar,Y. Narahari
Artificial Intelligence, AI, 2021
@inproceedings{bib_Ball_2021, AUTHOR = {Ghalme, Ganesh and Dhama, Swapnil and Jain, Shweta and Gujar, Sujit P and Narahari, Y. }, TITLE = {Ballooning multi-armed bandits}, BOOKTITLE = {Artificial Intelligence}. YEAR = {2021}}
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.
Sleeping Combinatorial Bandits
Kumar Abhishek,Ganesh Ghalme,Sujit P Gujar,Yadati Narahari,
Technical Report, arXiv, 2021
@inproceedings{bib_Slee_2021, AUTHOR = {Abhishek, Kumar and Ghalme, Ganesh and Gujar, Sujit P and Narahari, Yadati and , }, TITLE = {Sleeping Combinatorial Bandits}, BOOKTITLE = {Technical Report}. YEAR = {2021}}
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.
FASTEN: Fair and Secure Distributed Voting Using Smart Contracts
Sankarshan Damle,Sujit P Gujar,Moin Hussain Moti
International Conference on Blockchain and Cryptocurrency, ICBC, 2021
@inproceedings{bib_FAST_2021, AUTHOR = {Damle, Sankarshan and Gujar, Sujit P and Moti, Moin Hussain }, TITLE = {FASTEN: Fair and Secure Distributed Voting Using Smart Contracts}, BOOKTITLE = {International Conference on Blockchain and Cryptocurrency}. YEAR = {2021}}
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.
A Multi-Arm Bandit Approach To Subset Selection Under Constraints
Ayush Deva,Kumar Abhishek,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2021
@inproceedings{bib_A_Mu_2021, AUTHOR = {Deva, Ayush and Abhishek, Kumar and Gujar, Sujit P }, TITLE = {A Multi-Arm Bandit Approach To Subset Selection Under Constraints}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2021}}
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.
We might walk together, but I run faster: Network Fairness and Scalability in Blockchains
Anurag Jain,Siddiqui Shoeb Khaled,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2021
@inproceedings{bib_We_m_2021, AUTHOR = {Jain, Anurag and Khaled, Siddiqui Shoeb and Gujar, Sujit P }, TITLE = {We might walk together, but I run faster: Network Fairness and Scalability in Blockchains}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2021}}
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.
Towards Mobile Distributed Ledgers
Dimitris Chatzopoulos,Anurag Jain,Sujit P Gujar,Boi Faltings, Pan Hui
Internet of Things Journal, IOT, 2021
@inproceedings{bib_Towa_2021, AUTHOR = {Chatzopoulos, Dimitris and Jain, Anurag and Gujar, Sujit P and Faltings, Boi and Hui, Pan }, TITLE = {Towards Mobile Distributed Ledgers}, BOOKTITLE = {Internet of Things Journal}. YEAR = {2021}}
Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (eg, crowdsensing). Sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However, such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce and analyse Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices. Mneme utilizes two novel consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users' context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze Mneme's security and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.
Orthos: A Trustworthy AI Framework For Data Acquisition
Moin Hussain Moti,Dimitris Chatzopoulos,Pan Hui,Boi Faltings,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2020
@inproceedings{bib_Orth_2020, AUTHOR = {Moti, Moin Hussain and Chatzopoulos, Dimitris and Hui, Pan and Faltings, Boi and Gujar, Sujit P }, TITLE = {Orthos: A Trustworthy AI Framework For Data Acquisition}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2020}}
Information acquisition through crowdsourcing with mobile agents is a popular way to collect data, especially in the context of smart cities where the deployment of dedicated data collectors is expensive and ineffective. It requires trustworthy and effective mechanisms to guarantee that the collected data are accurately acquired and reported. Trustworthy and transparent frameworks can be implemented via smart contracts on blockchain to enable robust information elicitation mechanisms. In this work we develop Orthos, a blockchain-based trustworthy framework for spontaneous location-based information aggregation queries without assuming any prior knowledge about them. We employ game-theoretic mechanisms to incentivize agents to report truthfully and ensure that the information is collected at the desired location while ensuring the privacy of the agents. We identify six necessary characteristics for information aggregation mechanisms to be applicable in spontaneous location-based settings. Orthos implements the function of robust peer truth serum for crowdsourcing (RPTSC), the state-of-the-art information aggregation mechanism using smart contracts. Additionally, as location information is exogenous to RPTSC, we design the Proof-of-Location protocol to ensure that agents gather the data at the desired locations. We examine the performance of Orthos on Rinkeby Ethereum testnet and conduct experiments with live audience.
A Multiarmed Bandit Based Incentive Mechanism for a Subset Selection of Customers for Demand Response in Smart Grids
Shweta Jain,Sujit P Gujar
American Association for Artificial Intelligence, AAAI, 2020
@inproceedings{bib_A_Mu_2020, AUTHOR = {Jain, Shweta and Gujar, Sujit P }, TITLE = {A Multiarmed Bandit Based Incentive Mechanism for a Subset Selection of Customers for Demand Response in Smart Grids}, BOOKTITLE = {American Association for Artificial Intelligence}. YEAR = {2020}}
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 GLS-MAB 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.
FNNC: Achieving Fairness through Neural Networks
P Manisha,Sujit P Gujar
International Joint Conference on Artificial Intelligence, IJCAI, 2020
@inproceedings{bib_FNNC_2020, AUTHOR = {Manisha, P and Gujar, Sujit P }, TITLE = {FNNC: Achieving Fairness through Neural Networks}, BOOKTITLE = {International Joint Conference on Artificial Intelligence}. YEAR = {2020}}
In classification models fairness can be ensured by solving a constrained optimization problem. We focus on fairness constraints like Disparate Impact, Demographic Parity, and Equalized Odds, which are non-decomposable and non-convex. Researchers define convex surrogates of the constraints and then apply convex optimization frameworks to obtain fair classifiers. Surrogates serve only as an upper bound to the actual constraints, and convexifying fairness constraints might be challenging. We propose a neural network-based framework, FNNC, to achieve fairness while maintaining high accuracy in classification. The above fairness constraints are included in the loss using Lagrangian multipliers. We prove bounds on generalization errors for the constrained losses which asymptotically go to zero. The network is optimized using two-step mini-batch stochastic gradient descent. Our experiments show that FNNC performs as good as the state of the art, if not better. The experimental evidence supplements our theoretical guarantees. In summary, we have an automated solution to achieve fairness in classification, which is easily extendable to many fairness constraints.
Bidding in Smart Grid PDAs: Theory, Analysis and Strategy.
SUSOBHAN GHOSH,Sujit P Gujar,Praveen Paruchuri,Easwar Subramanian,Sanjay P. Bhat
American Association for Artificial Intelligence, AAAI, 2020
@inproceedings{bib_Bidd_2020, AUTHOR = {GHOSH, SUSOBHAN and Gujar, Sujit P and Paruchuri, Praveen and Subramanian, Easwar and Bhat, Sanjay P. }, TITLE = {Bidding in Smart Grid PDAs: Theory, Analysis and Strategy.}, BOOKTITLE = {American Association for Artificial Intelligence}. YEAR = {2020}}
Periodic Double Auctions (PDAs) are commonly used in the real world for trading, eg in stock markets to determine stock opening prices, and energy markets to trade energy in order to balance net demand in smart grids, involving trillions of dollars in the process. A bidder, participating in such PDAs, has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. In this paper, we perform an equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a single-shot double auction with ACPR. Leveraging the theory developed for single-shot double auction and taking the PowerTAC wholesale market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an MDP. We propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the-art bidding strategies for the PowerTAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently.
Mneme: A Mobile Distributed Ledger
Dimitris Chatzopoulos,Sujit P Gujar,Boi Faltings,Pan Hui
IEEE International Conference on Computer Communications, INFOCOM, 2020
@inproceedings{bib_Mnem_2020, AUTHOR = {Chatzopoulos, Dimitris and Gujar, Sujit P and Faltings, Boi and Hui, Pan }, TITLE = {Mneme: A Mobile Distributed Ledger}, BOOKTITLE = {IEEE International Conference on Computer Communications}. YEAR = {2020}}
Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (eg, crowdsensing). More sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices and operates via two consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users’ context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze the security of Mneme and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.
Human-Machine Collaboration for Face Recognition
Saurabh Ravindranath,Rahul Baburaj,Vineeth N. Balasubramanian,Nageswararao Namburu,Sujit P Gujar,Jawahar C V
India Joint International Conference on. Data Science & Management of Data, COMAD/CODS, 2020
@inproceedings{bib_Huma_2020, AUTHOR = {Ravindranath, Saurabh and Baburaj, Rahul and Balasubramanian, Vineeth N. and Namburu, Nageswararao and Gujar, Sujit P and V, Jawahar C }, TITLE = {Human-Machine Collaboration for Face Recognition}, BOOKTITLE = {India Joint International Conference on. Data Science & Management of Data}. YEAR = {2020}}
Despite advances in deep learning and facial recognition techniques, the problem of fault-intolerant facial recognition remains challenging. With the current state of progress in the field of automatic face recognition and the in-feasibility of fully manual recognition, the situation calls for human-machine collaborative methods. We design a system that uses machine predictions for a given face to generate queries that are answered by human experts to provide the system with the information required to predict the identity of the face correctly. We use a Markov Decision Process for which we devise an appropriate query structure and a reward structure to generate these queries in a budget or accuracy-constrained setting. Finally, as we do not know the capabilities of the human experts involved, we model each human as a bandit and adopt a multi-armed bandit approach with consensus queries to efficiently estimate …
Ballooning Multi-Armed Bandits
Ganesh Ghalme,Swapnil Dhamal,Shweta Jain,Sujit P Gujar,Y. Narahari
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2020
@inproceedings{bib_Ball_2020, AUTHOR = {Ghalme, Ganesh and Dhamal, Swapnil and Jain, Shweta and Gujar, Sujit P and Narahari, Y. }, TITLE = {Ballooning Multi-Armed Bandits}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2020}}
In this paper, we introduce Ballooning Multi-Armed Bandits (BL-MAB), a novel extension to the classical stochastic MAB model. In 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 MAB algorithms are not regret-optimal for the BL-MAB model. We show that if the best arm is equally likely to arrive at any time, a sub-linear regret cannot be achieved, irrespective of the arrival of other arms. We further 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 sub-linear instance-independent regret. We further quantify the explicit dependence of regret on the arrival distribution parameters. We reinforce our theoretical findings with extensive simulation results.
Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions
Kumar Abhishek,Shweta Jain,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2020
@inproceedings{bib_Desi_2020, AUTHOR = {Abhishek, Kumar and Jain, Shweta and Gujar, Sujit P }, TITLE = {Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2020}}
For sponsored search auctions, we consider contextual multi-armed bandit problem in the presence of strategic agents. In this setting, at each round, an advertising platform (center) runs an auction to select the best-suited ads relevant to the query posted by the user. It is in the best interest of the center to select an ad that has a high expected value (ie, probability of getting a click value it derives from a click of the ad). The probability of getting a click (CTR) is unknown to the center and depends on the user's profile (context) posting the query. Further, the value derived for a click is the private information to the advertiser and thus needs to be elicited truthfully. The existing solution in this setting is not practical as it suffers from very high regret ().
BitcoinF: Achieving Fairness for Bitcoin in Transaction-Fee-Only Model
Siddiqui Shoeb Khaled,GANESH DEVENDRAPPA VANAHALLI,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2020
@inproceedings{bib_Bitc_2020, AUTHOR = {Khaled, Siddiqui Shoeb and VANAHALLI, GANESH DEVENDRAPPA and Gujar, Sujit P }, TITLE = {BitcoinF: Achieving Fairness for Bitcoin in Transaction-Fee-Only Model}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2020}}
A blockchain, such as Bitcoin, is an append-only, secure, transparent, distributed ledger. A fair blockchain is expected to have healthy metrics; high honest mining power, low processing latency, ie, low wait times for transactions and stable price of consumption, ie, the minimum transaction fee required to have a transaction processed. As Bitcoin matures, the influx of transactions increases and the block rewards become insignificant. We show that under these conditions, it becomes hard to maintain the health of the blockchain. In Bitcoin, under these mature operating conditions (MOC), the miners would find it challenging to cover their mining costs as there would be no more revenue from merely mining a block. It may cause miners not to continue mining, threatening the blockchain's security. Further, as we show in this paper using simulations, the cost of acting in favor of the health of the blockchain, under MOC, is very high in Bitcoin, causing all miners to process transactions greedily. It leads to stranded transactions, ie, transactions offering low transaction fees, experiencing unreasonably high processing latency. To make matters worse, a compounding effect of these stranded transactions is the rising price of consumption. Such phenomena not only induce unfairness as experienced by the miners and the users but also deteriorate the health of the blockchain.
Civic Crowdfunding for Agents with Negative Valuations and Agents with Asymmetric Beliefs
Sankarshan Damle,Moin Hussain Moti,Praphul Chandra,Sujit P Gujar
International Joint Conference on Artificial Intelligence, IJCAI, 2019
@inproceedings{bib_Civi_2019, AUTHOR = {Damle, Sankarshan and Moti, Moin Hussain and Chandra, Praphul and Gujar, Sujit P }, TITLE = {Civic Crowdfunding for Agents with Negative Valuations and Agents with Asymmetric Beliefs}, BOOKTITLE = {International Joint Conference on Artificial Intelligence}. YEAR = {2019}}
In the last decade, civic crowdfunding has proved to be effective in generating funds for the provision of public projects. However, the existing literature deals only with citizen's with positive valuation and symmetric belief towards the project's provision. In this work, we present novel mechanisms which break these two barriers, i.e., mechanisms which incorporate negative valuation and asymmetric belief, independently. For negative valuation, we present a methodology for converting existing mechanisms to mechanisms that incorporate agents with negative valuations. Particularly, we adapt existing PPR and PPS mechanisms, to present novel PPRN and PPSN mechanisms which incentivize strategic agents to contribute to the project based on their true preference. With respect to asymmetric belief, we propose a reward scheme Belief Based Reward (BBR) based on Robust Bayesian Truth Serum mechanism. With BBR, we propose a general mechanism for civic crowdfunding which incorporates asymmetric agents. We leverage PPR and PPS, to present PPRx and PPSx. We prove that in PPRx and PPSx, agents with greater belief towards the project's provision contribute more than agents with lesser belief. Further, we also show that contributions are such that the project is provisioned at equilibrium.
Generative Adversarial Networks (GANs): What it can generate and What it cannot?
P Manisha,Sujit P Gujar
Technical Report, arXiv, 2019
@inproceedings{bib_Gene_2019, AUTHOR = {Manisha, P and Gujar, Sujit P }, TITLE = {Generative Adversarial Networks (GANs): What it can generate and What it cannot?}, BOOKTITLE = {Technical Report}. YEAR = {2019}}
In recent years, Generative Adversarial Networks (GANs) have received significant attention from the research community. With a straightforward implementation and outstanding results, GANs have been used for numerous applications. Despite the success, GANs lack a proper theoretical explanation. These models suffer from issues like mode collapse, non-convergence, and instability during training. To address these issues, researchers have proposed theoretically rigorous frameworks inspired by varied fields of Game theory, Statistical theory, Dynamical systems, etc. In this paper, we propose to give an appropriate structure to study these contributions systematically. We essentially categorize the papers based on the issues they raise and the kind of novelty they introduce to address them. Besides, we provide insight into how each of the discussed articles solves the concerned problems. We compare and contrast different results and put forth a summary of theoretical contributions about GANs with focus on image/visual applications. We expect this summary paper to give a bird’s eye view to a person wishing to understand the theoretical progress in GANs so far.
Learning optimal redistribution mechanisms through neural networks
P Manisha,Jawahar C V,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2019
@inproceedings{bib_Lear_2019, AUTHOR = {Manisha, P and V, Jawahar C and Gujar, Sujit P }, TITLE = {Learning optimal redistribution mechanisms through neural networks}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2019}}
We consider a setting where public resources are to be allocated among competing and strategic agents so as to maximize social welfare (the objects should be allocated to those who value them the most). This is called allocative efficiency (AE). We need the agents to report their valuations for obtaining these resources, truthfully referred to as dominant strategy incentive compatibility (DSIC). We use auction-based mechanisms to achieve AE and DSIC yet budget balance cannot be ensured, due to Green-Laffont Impossibility Theorem. That is, the net transfer of money cannot be zero. This problem has been addressed by designing a redistribution mechanism so as to ensure a minimum surplus of money as well as AE and DSIC. The objective could be to minimize surplus in expectation or in the worst case and these objects could be homogeneous or heterogeneous. Designing redistribution mechanisms which perform well in expectation becomes analytically challenging for heterogeneous settings. In this paper, we take a completely different, data-driven approach. We train a neural network to determine an optimal redistribution mechanism based on given settings with both the objectives, optimal in expectation and optimal in the worst case. We also propose a loss function to train a neural network to optimize worst case. We design neural networks with the underlying rebate functions being linear as well as nonlinear in terms of bids of the agents. Our networks' performances are same as the theoretical guarantees for the cases where it has been solved. We observe that a neural network based redistribution mechanism for homogeneous …
Vidyutvanika: An autonomous broker agent for smart grid environment
SUSOBHAN GHOSH,Kritika Prakash,Sanjay Chandlekar,Easwar Subramanian,Sanjay P. Bhat,Sujit P Gujar,Praveen Paruchuri
Proceedings of the International Conference on Artificial Intelligence, IC-AI, 2019
@inproceedings{bib_Vidy_2019, AUTHOR = {GHOSH, SUSOBHAN and Prakash, Kritika and Chandlekar, Sanjay and Subramanian, Easwar and Bhat, Sanjay P. and Gujar, Sujit P and Paruchuri, Praveen }, TITLE = {Vidyutvanika: An autonomous broker agent for smart grid environment}, BOOKTITLE = {Proceedings of the International Conference on Artificial Intelligence}. YEAR = {2019}}
We describe the design of an autonomous electricity broker agent, VidyutVanika, the runner-up of the 2018 PowerTAC competition. The agent uses techniques from reinforcement learning, dynamic programming and other areas of machine learning to seek appropriate actions in tariff and wholesale market of the PowerTAC simulation environment. The novelty of our agent lies in defining the reward functions of suitably defined Markov decision processes (MDPs), solving these MDPs, and applying these solutions to real actions in the market. In addition, VidyutVanika uses a neural network to predict the energy consumption of various customers using weather data. The usage forecasts, so obtained, are used to place orders in day-ahead wholesale market. These forecasts also helps in reducing the balancing costs incurred by the broker.
Methods and systems for regulating service layer agreements for multiple cloud service requests
Sujit P Gujar,Mukherjee,Dasgupta ,Jung
United States Patent, Us patent, 2019
@inproceedings{bib_Meth_2019, AUTHOR = {Gujar, Sujit P and Mukherjee, and , Dasgupta and Jung, }, TITLE = {Methods and systems for regulating service layer agreements for multiple cloud service requests}, BOOKTITLE = {United States Patent}. YEAR = {2019}}
Methods and systems are disclosed for providing cloud services to multiple customers in a cloud. One embodiment includes receiving a number of requests for the cloud services from the multiple customers simultaneously or substantially simultaneously; prioritizing the requests based on a probability distribution of actually deploying a service, a budget of the customers, and an expected demand of the requested service based on the probability distribution; generating a number of cloud configurations along with a number of Service Level Agreements (SLAs) for the customers based on prioritization of the requests, a class & past behavior of the customers, and a current demand of the cloud services, the SLAs of the customers include differentiated price offering; recommending the cloud configurations and the SLAs to the customers; allowing the customers to negotiate terms of the SLAs; and providing the cloud …
Thompson Sampling Based Multi-Armed-Bandit Mechanism Using Neural Networks.
P Manisha,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2019
@inproceedings{bib_Thom_2019, AUTHOR = {Manisha, P and Gujar, Sujit P }, TITLE = {Thompson Sampling Based Multi-Armed-Bandit Mechanism Using Neural Networks.}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2019}}
In many practical applications such as crowd-sourcing and online advertisement, use of mechanism design (auction-based mechanisms) depends upon inherent stochastic parameters which are unknown. These parameters are learnt using multi-armed bandit (MAB) algorithms. The mechanisms which incorporate MAB are referred to as Multi-Armed-Bandit Mechanisms. While most of the MAB mechanisms focus on frequentist approaches like upper confidence bound algorithms, recent work has shown that using Bayesian approaches like Thompson sampling results in mechanisms with better regret bounds; although lower regret is obtained at the cost of the mechanism ending up with a weaker game theoretic property ie Within-Period Dominant Strategy Incentive Compatibility (WP-DSIC). The existing payment rules used in the Thompson sampling based mechanisms may cause negative utility to the auctioneer. In addition, if we wish to minimize the cost to the auctioneer, it is very challenging to design payment rules that satisfy WP-DSIC while learning through Thompson sampling. In our work, we propose a data-driven approach for designing MAB-mechanisms. Specifically, we use neural networks for designing the payment rule which is WP-DSIC, while the allocation rule is modeled using Thompson sampling. Our results, in the setting of crowd-sourcing for recruiting quality workers, indicate that the learned payment rule guarantees better cost while maximizing the social welfare and also ensuring reduced variance in the utilities to the agents.
Aggregating Citizen Preferences for Public Projects Through Civic Crowdfunding.
Sankarshan Damle,Moin Hussain Moti,Praphul Chandra,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2019
@inproceedings{bib_Aggr_2019, AUTHOR = {Damle, Sankarshan and Moti, Moin Hussain and Chandra, Praphul and Gujar, Sujit P }, TITLE = {Aggregating Citizen Preferences for Public Projects Through Civic Crowdfunding.}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2019}}
We focus on the aggregation of citizen preferences for public projects through civic crowdfunding. Existing civic crowdfunding mechanisms consider only agents with positive valuation towards the public project. Moreover, these mechanisms assume that each agent has a symmetric belief about the project getting provisioned. As public projects aim to cater to the majority, they should be provisioned only if the majority prefers it. To incorporate negative valuations, we propose a methodology to convert existing civic crowdfunding mechanisms for positive preferences to cater to markets having both types of agents. Specifically, we adapt existing PPR and PPS mechanisms to design PPRN and PPSN, that incentivize agents to contribute towards or against the project’s provision: based on their preference. Besides, to address asymmetric beliefs, we propose a novel reward scheme, Belief Based Reward (BBR) based on Robust Bayesian Truth Serum (RBTS) mechanism. BBR rewards agents based on their belief towards the project’s provision. Using this reward scheme, we introduce a general mechanism for civic crowdfunding which allows for agents having asymmetric beliefs towards the project getting provisioned and incentivizes them to contribute towards the project’s provision. We illustrate the general mechanism by designing two novel mechanisms, namely PPRx and PPSx, adapting PPR and PPS respectively, and prove that in both the mechanisms the project is provisioned at equilibrium
A Truthful, Privacy-Preserving, Approximately Efficient Combinatorial Auction For Single-minded Bidders.
Sankarshan Damle,Boi Faltings,Sujit P Gujar
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2019
@inproceedings{bib_A_Tr_2019, AUTHOR = {Damle, Sankarshan and Faltings, Boi and Gujar, Sujit P }, TITLE = {A Truthful, Privacy-Preserving, Approximately Efficient Combinatorial Auction For Single-minded Bidders.}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2019}}
Auctions are mechanisms which facilitate the buying and selling of goods/items amongst a group of agents. In general, a combinatorial auction, where the agents can bid for combination (s) of items, yields a higher revenue than selling the goods/items individually.
Civic crowdfunding for agents with negative valuations and agents with asymmetric beliefs
Sankarshan Damle,Moin Hussain Moti,Praphul Chandra,Sujit P Gujar
AAAI Conference on Artificial Intelligence, AAAI, 2019
@inproceedings{bib_Civi_2019, AUTHOR = {Damle, Sankarshan and Moti, Moin Hussain and Chandra, Praphul and Gujar, Sujit P }, TITLE = {Civic crowdfunding for agents with negative valuations and agents with asymmetric beliefs}, BOOKTITLE = {AAAI Conference on Artificial Intelligence}. YEAR = {2019}}
In the last decade, civic crowdfunding has proved to be effective in generating funds for the provision of public projects. However, the existing literature deals only with citizen's with positive valuation and symmetric belief towards the project's provision. In this work, we present novel mechanisms which break these two barriers, ie, mechanisms which incorporate negative valuation and asymmetric belief, independently. For negative valuation, we present a methodology for converting existing mechanisms to mechanisms that incorporate agents with negative valuations. Particularly, we adapt existing PPR and PPS mechanisms, to present novel PPRN and PPSN mechanisms which incentivize strategic agents to contribute to the project based on their true preference. With respect to asymmetric belief, we propose a reward scheme Belief Based Reward (BBR) based on Robust Bayesian Truth Serum mechanism. With BBR, we propose a general mechanism for civic crowdfunding which incorporates asymmetric agents. We leverage PPR and PPS, to present PPRx and PPSx. We prove that in PPRx and PPSx, agents with greater belief towards the project's provision contribute more than agents with lesser belief. Further, we also show that contributions are such that the project is provisioned at equilibrium.
FaRM: fair reward mechanism for information aggregation in spontaneous localized settings
Moin Hussain Moti,Dimitris Chatzopoulos,Pan Hui,Sujit P Gujar
Technical Report, arXiv, 2019
@inproceedings{bib_FaRM_2019, AUTHOR = {Moti, Moin Hussain and Chatzopoulos, Dimitris and Hui, Pan and Gujar, Sujit P }, TITLE = {FaRM: fair reward mechanism for information aggregation in spontaneous localized settings}, BOOKTITLE = {Technical Report}. YEAR = {2019}}
Although peer prediction markets are widely used in crowdsourcing to aggregate information from agents, they often fail to reward the participating agents equitably. Honest agents can be wrongly penalized if randomly paired with dishonest ones. In this work, we introduce selective and cumulative fairness. We characterize a mechanism as fair if it satisfies both notions and present FaRM, a representative mechanism we designed. FaRM is a Nash incentive mechanism that focuses on information aggregation for spontaneous local activities which are accessible to a limited number of agents without assuming any prior knowledge of the event. All the agents in the vicinity observe the same information. FaRM uses (i) a report strength score to remove the risk of random pairing with dishonest reporters,(ii) a consistency score to measure an agent’s history of accurate reports and distinguish valuable reports,(iii) a reliability score to estimate the probability of an agent to collude with nearby agents and prevents agents from getting swayed, and (iv) a location robustness score to filter agents who try to participate without being present in the considered setting. Together, report strength, consistency, and reliability represent a fair reward given to agents based on their reports.
FaRM: Fair Reward Mechanism for Information Aggregation in Spontaneous Localized Settings (Extended Version)
Moin Hussain Moti,Dimitris Chatzopoulos,Pan Hui,Sujit P Gujar
AAAI Conference on Artificial Intelligence, AAAI, 2019
@inproceedings{bib_FaRM_2019, AUTHOR = {Moti, Moin Hussain and Chatzopoulos, Dimitris and Hui, Pan and Gujar, Sujit P }, TITLE = {FaRM: Fair Reward Mechanism for Information Aggregation in Spontaneous Localized Settings (Extended Version)}, BOOKTITLE = {AAAI Conference on Artificial Intelligence}. YEAR = {2019}}
Although peer prediction markets are widely used in crowdsourcing to aggregate information from agents, they often fail to reward the participating agents equitably. Honest agents can be wrongly penalized if randomly paired with dishonest ones. In this work, we introduceemph {selective} andemph {cumulative} fairness. We characterize a mechanism as fair if it satisfies both notions and present FaRM, a representative mechanism we designed. FaRM is a Nash incentive mechanism that focuses on information aggregation for spontaneous local activities which are accessible to a limited number of agents without assuming any prior knowledge of the event. All the agents in the vicinity observe the same information. FaRM usestextit {(i)} aemph {report strength score} to remove the risk of random pairing with dishonest reporters,textit {(ii)} aemph {consistency score} to measure an agent's history of accurate reports and distinguish valuable reports,textit {(iii)} aemph {reliability score} to estimate the probability of an agent to collude with nearby agents and prevents agents from getting swayed, andtextit {(iv)} aemph {location robustness score} to filter agents who try to participate without being present in the considered setting. Together, report strength, consistency, and reliability represent a fair reward given to agents based on their reports.
A Practical Solution to Yao's Millionaires' Problem and Its Application in Designing Secure Combinatorial Auction
Sankarshan Damle,Boi Faltings,Sujit P Gujar
Technical Report, arXiv, 2019
@inproceedings{bib_A_Pr_2019, AUTHOR = {Damle, Sankarshan and Faltings, Boi and Gujar, Sujit P }, TITLE = {A Practical Solution to Yao's Millionaires' Problem and Its Application in Designing Secure Combinatorial Auction}, BOOKTITLE = {Technical Report}. YEAR = {2019}}
The emergence of e-commerce and e-voting platforms has resulted in the rise in the volume of sensitive information over the Internet. This has resulted in an increased demand for secure and private means of information computation. Towards this, the Yao's Millionaires' problem, ie, to determine the richer among two millionaires' securely, finds an application. In this work, we present a new solution to the Yao's Millionaires' problem namely, Privacy Preserving Comparison (PPC). We show that PPC achieves this comparison in constant time as well as in one execution. PPC uses semi-honest third parties for the comparison who do not learn any information about the values. Further, we show that PPC is collusion-resistance. To demonstrate the significance of PPC, we present a secure, approximate single-minded combinatorial auction, which we call TPACAS, ie, Truthful, Privacy-preserving Approximate Combinatorial Auction for Single-minded bidders. We show that TPACAS, unlike previous works, preserves the following privacies relevant to an auction: agent privacy, the identities of the losing bidders must not be revealed to any other agent except the auctioneer (AU), bid privacy, the bid values must be hidden from the other agents as well as the AU and bid-topology privacy, the items for which the agents are bidding must be hidden from the other agents as well as the AU. We demonstrate the practicality of TPACAS through simulations. Lastly, we also look at TPACAS'implementation over a publicly distributed ledger, such as the Ethereum blockchain.
VidyutVanika: A reinforcement learning based broker agent for a power trading competition
SUSOBHAN GHOSH,Easwar Subramanian,Sanjay P. Bhat,Sujit P Gujar,Praveen Paruchuri
American Association for Artificial Intelligence, AAAI, 2019
@inproceedings{bib_Vidy_2019, AUTHOR = {GHOSH, SUSOBHAN and Subramanian, Easwar and Bhat, Sanjay P. and Gujar, Sujit P and Paruchuri, Praveen }, TITLE = {VidyutVanika: A reinforcement learning based broker agent for a power trading competition}, BOOKTITLE = {American Association for Artificial Intelligence}. YEAR = {2019}}
A smart grid is an efficient and sustainable energy system that integrates diverse generation entities, distributed storage capacity, and smart appliances and buildings. A smart grid brings new kinds of participants in the energy market served by it, whose effect on the grid can only be determined through high fidelity simulations. Power TAC offers one such simulation platform using real-world weather data and complex state-of-the-art customer models. In Power TAC, autonomous energy brokers compete to make profits across tariff, wholesale and balancing markets while maintaining the stability of the grid. In this paper, we design an autonomous broker VidyutVanika, the runner-up in the 2018 Power TAC competition. VidyutVanika relies on reinforcement learning (RL) in the tariff market and dynamic programming in the wholesale market to solve modified versions of known Markov Decision Process (MDP) formulations in the respective markets. The novelty lies in defining the reward functions for MDPs, solving these MDPs, and the application of these solutions to real actions in the market. Unlike previous participating agents, VidyutVanika uses a neural network to predict the energy consumption of various customers using weather data. We use several heuristic ideas to bridge the gap between the restricted action spaces of the MDPs and the much more extensive action space available to VidyutVanika. These heuristics allow VidyutVanika to convert near-optimal fixed tariffs to time-of-use tariffs aimed at mitigating transmission capacity fees, spread out its orders across several auctions in the wholesale market to procure energy at a lower price …
HRCR: Hidden Markov-based Reinforcement to Reduce Churn in Question Answering Forums
Reza Hadi Mogavi,Sujit P Gujar,Xiaojuan Ma,Pan Hui
Pacific Rim International Conference on Artificial Intelligence, PRICAI, 2019
@inproceedings{bib_HRCR_2019, AUTHOR = {Mogavi, Reza Hadi and Gujar, Sujit P and Ma, Xiaojuan and Hui, Pan }, TITLE = {HRCR: Hidden Markov-based Reinforcement to Reduce Churn in Question Answering Forums}, BOOKTITLE = {Pacific Rim International Conference on Artificial Intelligence}. YEAR = {2019}}
The high rate of churning users who abandon the Community Question Answering forums (CQAs) may be one of the crucial issues that hinder their development. More personalized question recommendation to users might help to manage this problem better. In this paper, we propose a new algorithm (we name HRCR) that recommends questions to users such to reduce their churning probability. We present our algorithm in a two-fold structure: First, we use Hidden Markov Models (HMMs) to uncover the users’ engagement states inside a CQA. Second, we apply a Reinforcement Learning Model (RL) to recommend users the questions that match better with their engagement mood and thus help them get into a better engagement state (the one with the least churning probability). Experiments on a large-scale offline dataset from Stack Overflow show a meaningful reduction in the churning probability of the
Introduction to Concentration Inequalities
Kumar Abhishek,Sneha Maheshwari,Sujit P Gujar
Technical Report, arXiv, 2019
@inproceedings{bib_Intr_2019, AUTHOR = {Abhishek, Kumar and Maheshwari, Sneha and Gujar, Sujit P }, TITLE = {Introduction to Concentration Inequalities}, BOOKTITLE = {Technical Report}. YEAR = {2019}}
In this report, we aim to exemplify concentration inequalities and provide easy to understand proofs for it. Our focus is on the inequalities which are helpful in the design and analysis of machine learning algorithms.
Bidding in smart grid pdas: Theory, analysis and strategy (extended version)
SUSOBHAN GHOSH,Sujit P Gujar,Praveen Paruchuri,Easwar Subramanian,Sanjay P. Bhat
AAAI Conference on Artificial Intelligence, AAAI, 2019
@inproceedings{bib_Bidd_2019, AUTHOR = {GHOSH, SUSOBHAN and Gujar, Sujit P and Paruchuri, Praveen and Subramanian, Easwar and Bhat, Sanjay P. }, TITLE = {Bidding in smart grid pdas: Theory, analysis and strategy (extended version)}, BOOKTITLE = {AAAI Conference on Artificial Intelligence}. YEAR = {2019}}
Periodic Double Auctions (PDAs) are commonly used in the real world for trading, eg in stock markets to determine stock opening prices, and energy markets to trade energy in order to balance net demand in smart grids, involving trillions of dollars in the process. A bidder, participating in such PDAs, has to plan for bids in the current auction as well as for the future auctions, which highlights the necessity of good bidding strategies. In this paper, we perform an equilibrium analysis of single unit single-shot double auctions with a certain clearing price and payment rule, which we refer to as ACPR, and find it intractable to analyze as number of participating agents increase. We further derive the best response for a bidder with complete information in a single-shot double auction with ACPR. Leveraging the theory developed for single-shot double auction and taking the PowerTAC wholesale market PDA as our testbed, we proceed by modeling the PDA of PowerTAC as an MDP. We propose a novel bidding strategy, namely MDPLCPBS. We empirically show that MDPLCPBS follows the equilibrium strategy for double auctions that we previously analyze. In addition, we benchmark our strategy against the baseline and the state-of-the-art bidding strategies for the PowerTAC wholesale market PDAs, and show that MDPLCPBS outperforms most of them consistently.
An optimal bidimensional multi-armed bandit auction for multi-unit procurement
Satyanath Bhat,Shweta Jain,Sujit P Gujar,Y Narahari
Annals of Mathematics and Artificial Intelligence, AMAI, 2019
@inproceedings{bib_An_o_2019, AUTHOR = {Bhat, Satyanath and Jain, Shweta and Gujar, Sujit P and Narahari, Y }, TITLE = {An optimal bidimensional multi-armed bandit auction for multi-unit procurement}, BOOKTITLE = {Annals of Mathematics and Artificial Intelligence}. YEAR = {2019}}
We study the problem of a buyer who gains stochastic rewards by procuring through an auction, multiple units of a service or item from a pool of heterogeneous agents who are strategic on two dimensions, namely cost and capacity. The reward obtained for a single unit from an allocated agent depends on the inherent quality of the agent; the agent’s quality is fixed but unknown. Each agent can only supply a limited number of units (capacity of the agent). The cost incurred per unit and capacity (maximum number of units that can be supplied) are private information of each agent. The auctioneer is required to elicit from the agents their costs as well as capacities (making the mechanism design bidimensional) and further, learn the qualities of the agents as well, with a view to maximize her utility. Motivated by this, we design a bidimensional multi-armed bandit procurement auction that seeks to maximize the
Privacy Preserving and Cost Optimal Mobile Crowdsensing using Smart Contracts on Blockchain
Dimitris Chatzopoulos,Sujit P Gujar,Boi Faltings,Pan Hui
International Conference on Mobile Ad-hoc and Sensor Systems, MASS, 2018
@inproceedings{bib_Priv_2018, AUTHOR = {Chatzopoulos, Dimitris and Gujar, Sujit P and Faltings, Boi and Hui, Pan }, TITLE = {Privacy Preserving and Cost Optimal Mobile Crowdsensing using Smart Contracts on Blockchain}, BOOKTITLE = {International Conference on Mobile Ad-hoc and Sensor Systems}. YEAR = {2018}}
The popularity and applicability of mobile crowdsensing applications are continuously increasing due to the widespread of mobile devices and their sensing and processing capabilities. However, we need to offer appropriate incentives to the mobile users who contribute their resources and preserve their privacy. Blockchain technologies enable semi-anonymous multi-party interactions and can be utilized in crowdsensing applications to maintain the privacy of the mobile users while ensuring first-rate crowdsensed data. In this work, we propose to use blockchain technologies and smart contracts to orchestrate the interactions between mobile crowdsensing providers and mobile users for the case of spatial crowdsensing, where mobile users need to be at specific locations to perform the tasks. Smart contracts, by operating as processes that are executed on the blockchain, are used to preserve users’ privacy and make payments. Furthermore, for the assignment of the crowdsensing tasks to the mobile users, we design a truthful, cost-optimal auction that minimizes the payments from the crowdsensing providers to the mobile users. Extensive experimental results show that the proposed privacy preserving auction outperforms state-of-the-art proposals regarding cost by ten times for high numbers of mobile users and tasks.
Design of Coalition Resistant Credit Score Functions for Online Discussion Forums
Ganesh Ghalme,Sujit P Gujar,Amleshwar Kumar,Shweta Jain,Y. Narahari
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2018
@inproceedings{bib_Desi_2018, AUTHOR = {Ghalme, Ganesh and Gujar, Sujit P and Kumar, Amleshwar and Jain, Shweta and Narahari, Y. }, TITLE = {Design of Coalition Resistant Credit Score Functions for Online Discussion Forums}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2018}}
The internet has transformed the way we communicate ideas and share knowledge. Online discussion forums (ODFs) play an important role by providing a platform for the internet users to interact. There exist numerous ODFs where participants (ie the agents) can post the reviews of events, restaurants, movies, books, services, and so on. Such online forums are also commonly used as a web-based discussion platform to discuss academic topics, personal experiences, views, etc. We are motivated by forums such as Quora, Stack Exchange, Reddit, WikiAnswers, and Yahoo! Answers, which provide a platform for open-ended discussions, and by platforms such as Piazza and iClicker which supplement traditional classroom teaching. These forums are also used by massive online
Designing refund bonus schemes for provision point mechanism in civic crowdfunding
Sankarshan Damle,Moin Hussain Moti,Sujit P Gujar,Praphul Chandra
Pacific Rim International Conference on Artificial Intelligence, PRICAI, 2018
@inproceedings{bib_Desi_2018, AUTHOR = {Damle, Sankarshan and Moti, Moin Hussain and Gujar, Sujit P and Chandra, Praphul }, TITLE = {Designing refund bonus schemes for provision point mechanism in civic crowdfunding}, BOOKTITLE = {Pacific Rim International Conference on Artificial Intelligence}. YEAR = {2018}}
Civic crowdfunding (CC) is a practice with which interested players can raise funds for a civic project. With Blockchains gaining traction, CC can be implemented in a reliable, transparent and secure manner with smart contracts. The fundamental challenge in CC is free riding. PPR, the proposal by [Zubrickas, 2014] of refund bonus to the contributors in the case of the project not getting provisioned has interesting properties. As observed by [Chandra et al, 2016], PPR faces a challenge of race condition. To address this, their proposal, PPS considers the temporal aspects of a contribution. However, PPS is computationally complex and is difficult to explain to a layperson. In this work, we look for all important properties a refund bonus scheme must satisfy in order to discourage free riding while avoiding the race condition. We identify Contribution Monotonicity and Time Monotonicity as sufficient conditions for this. We propose three 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 a smart contract. We then prove that under certain assumptions on valuations of the players, in PPRG, the project is funded at equilibrium
FNNC: Achieving Fairness through Neural Networks
,P Manisha,Sujit P Gujar
International Joint Conference on Artificial Intelligence, IJCAI, 2018
@inproceedings{bib_FNNC_2018, AUTHOR = {, and Manisha, P and Gujar, Sujit P }, TITLE = {FNNC: Achieving Fairness through Neural Networks}, BOOKTITLE = {International Joint Conference on Artificial Intelligence}. YEAR = {2018}}
Machine learning models are extensively being used in decision making, especially for prediction tasks. These models could be biased or unfair towards a specific sensitive group either of a specific race, gender or age. Researchers have put efforts into characterizing a particular definition of fairness and enforcing them into the models. In this work, mainly we are concerned with the following three definitions, Disparate Impact, Demographic Parity and Equalized Odds. Researchers have shown that Equalized Odds cannot be satisfied in calibrated classifiers unless the classifier is perfect. Hence the primary challenge is to ensure a degree of fairness while guaranteeing as much accuracy as possible. Fairness constraints are complex and need not be convex. Incorporating them into a machine learning algorithm is a significant challenge. Hence, many researchers have tried to come up with a surrogate loss which is convex in order to build fair classifiers. Besides, certain papers try to build fair representations by preprocessing the data, irrespective of the classifier used. Such methods, not only require a lot of unrealistic assumptions but also require human engineered analytical solutions to build a machine learning model. We instead propose an automated solution which is generalizable over any fairness constraint. We use a neural network which is trained on batches and directly enforces the fairness constraint as the loss function without modifying it further. We have also experimented with other complex performance measures such as H-mean loss, Q-mean-loss, F-measure; without the need for any surrogate loss functions. Our experiments …
A quality assuring, cost optimal multi-armed bandit mechanism for expert sourcing
ShwetaJain,Sujit P Gujar,Satyanath Bhat,Onno Zoeter,Y.Narahari
Artificial Intelligence, AI, 2017
@inproceedings{bib_A_qu_2017, AUTHOR = {ShwetaJain, and Gujar, Sujit P and Bhat, Satyanath and Zoeter, Onno and Y.Narahari, }, TITLE = {A quality assuring, cost optimal multi-armed bandit mechanism for expert sourcing}, BOOKTITLE = {Artificial Intelligence}. YEAR = {2017}}
There are numerous situations when a service requester wishes to expertsourcea series of identical but non-trivial tasks from a pool of experts so as to achieve an assured accuracy level for each task, in a cost optimal way. The experts available are typically heterogeneous with unknown but fixed qualities and different service costs. The service costs are usually private to the experts and the experts could be strategic about their costs. The problem is to select for each task an optimal subset of experts so that the outcome obtained after aggregating the opinions from the selected experts guarantees a target level of accuracy. The problem is a challenging one even in a non-strategic setting since the accuracy of an aggregated outcome depends on unknown qualities. We develop a novel multi-armed bandit (MAB) mechanism for solving this problem. First, we propose a framework, Assured Accuracy Bandit (AAB)framework, which leads to a MAB algorithm, Constrained Confidence Bound for Non-Strategic Setting (CCB-NS). We derive an upper bound on the number of time steps this algorithm chooses a sub-optimal set, which depends on the target accuracy and true qualities. A more challenging situation arises when the requester not only has to learn the qualities of the experts but has to elicit their true service costs as well. We modify the CCB-NS algorithm to obtain an adaptive exploration separated algorithm Constrained Confidence Bound for Strategic Setting (CCB-S). The CCB-S algorithm produces an ex-post monotone allocation rule that can then be transformed into an ex-post incentive compatible and ex-post individually rational mechanism. This mechanism learns the qualities of the experts and guarantees a given target accuracy level in a cost optimal way. We also provide a lower bound on the number of times any algorithm must select a sub-optimal set and we see that the lower bound matches our upper bound up to a constant factor. We provide insights on a practical implementation of this framework through an illustrative example and demonstrate the efficacy of our algorithms through simulations
LocalCoin: An Ad-hoc Payment Scheme for Areas with High Connectivity
Dimitris Chatzopoulos,Sujit P Gujar,Boi Faltings, Pan Hui
International Symposium on Mobile Ad Hoc Networking and Computing, MOBIHOC, 2017
@inproceedings{bib_Loca_2017, AUTHOR = {Chatzopoulos, Dimitris and Gujar, Sujit P and Faltings, Boi and Hui, Pan }, TITLE = {LocalCoin: An Ad-hoc Payment Scheme for Areas with High Connectivity}, BOOKTITLE = {International Symposium on Mobile Ad Hoc Networking and Computing}. YEAR = {2017}}
The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin’s security lies in a proof-of-work scheme, which requires high computational resources at the miners. Despite advances in mobile technology, existing cryptocurrencies cannot be maintained by mobile devices due to their low processing capabilities. Mobile devices can only accommodate mobile applications (wallets) that allow users to exchange credits of cryptocurrencies. In this work, we propose LocalCoin, an alternative cryptocurrency that requires minimal computational resources, produces low data traffic and works with off-the-shelf mobile devices. LocalCoin replaces the computational hardness that is at the root of Bitcoin’s security with the social hardness of ensuring that all witnesses to a transaction are colluders. Localcoin features (i) a lightweight proof-of-work scheme and (ii) a distributed blockchain. We analyze LocalCoin for double spending for passive and active attacks and prove that under the assumption of sufficient number of users and properly selected tuning parameters the probability of double spending is close to zero. Extensive simulations on real mobility traces, realistic urban settings, and random geometric graphs show that the probability of success of one transaction converges to 1 and the probability of the success of a double spending attempt converges to 0.
LocalCoin: An Ad-hoc Payment Scheme for Areas with High Connectivity
Dimitris Chatzopoulos,Sujit P Gujar,Boi Faltings,Pan Hui
ACM Symposium of Mobile and Ad Hoc Computing, MOBIHOC, 2017
@inproceedings{bib_Loca_2017, AUTHOR = {Chatzopoulos, Dimitris and Gujar, Sujit P and Faltings, Boi and Hui, Pan }, TITLE = {LocalCoin: An Ad-hoc Payment Scheme for Areas with High Connectivity}, BOOKTITLE = {ACM Symposium of Mobile and Ad Hoc Computing}. YEAR = {2017}}
The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin’s security lies in a proof-of-work scheme, which requires high computational resources at the miners. Despite advances in mobile technology, existing cryptocurrencies cannot be maintained by mobile devices due to their low processing capabilities. Mobile devices can only accommodate mobile applications (wallets) that allow users to exchange credits of cryptocurrencies. In this work, we propose LocalCoin, an alternative cryptocurrency that requires minimal computational resources, produces low data traffic and works with off-the-shelf mobile devices. LocalCoin replaces the computational hardness that is at the root of Bitcoin’s security with the social hardness of ensuring that all witnesses to a transaction are colluders. Localcoin features (i) a lightweight proof-of-work scheme and (ii) a distributed blockchain. We analyze LocalCoin for double spending for passive and active attacks and prove that under the assumption of sufficient number of users and properly selected tuning parameters the probability of double spending is close to zero. Extensive simulations on real mobility traces, realistic urban settings, and random geometric graphs show that the probability of success of one transaction converges to 1 and the probability of the success of a double spending attempt converges to 0.
Thompson Sampling Based Mechanisms for Stochastic Multi-Armed Bandit Problems
Ganesh Ghalme,Shweta Jain,Sujit P Gujar,Y. Narahari
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2017
@inproceedings{bib_Thom_2017, AUTHOR = {Ghalme, Ganesh and Jain, Shweta and Gujar, Sujit P and Narahari, Y. }, TITLE = {Thompson Sampling Based Mechanisms for Stochastic Multi-Armed Bandit Problems}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2017}}
This paper explores Thompson sampling in the context of mechanism design for stochastic multi-armed bandit (MAB) problems. The setting is that of an MAB problem where the reward distribution of each arm consists of a stochastic component as well as a strategic component. Many existing MAB mechanisms use upper confidence bound (UCB) based algorithms for learning the parameters of the reward distribution. The randomized nature of Thompson sampling introduces certain unique, non-trivial challenges for mechanism design, which we address in this paper through a rigorous regret analysis. We first propose a MAB mechanism with deterministic payment rule, namely, TSM-D. We show that in TSMD, the variance of agent utilities asymptotically approaches zero. However, the game theoretic properties satisfied by TSM-D (incentive compatibility and individual rationality with high probability) are rather weak. As our main contribution, we then propose the mechanism TSM-R, with randomized payment rule, and prove that TSM-R satisfies appropriate, adequate notions of incentive compatibility and individual rationality. For TSM-R, we also establish a theoretical upper bound on the variance in utilities of the agents. We further show, using simulations, that the variance in social welfare incurred by TSM-D or TSM-R is much lower when compared to that of existing UCB based mechanisms. We believe this paper establishes Thompson sampling as an attractive approach to be used in MAB mechanism design.
Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation
Sujit P Gujar,Boi Faltings
European Conference on Artificial Intelligence, ECAI, 2016
@inproceedings{bib_Onli_2016, AUTHOR = {Gujar, Sujit P and Faltings, Boi }, TITLE = {Online Auctions for Dynamic Assignment: Theory and Empirical Evaluation}, BOOKTITLE = {European Conference on Artificial Intelligence}. YEAR = {2016}}
Dynamic resource assignment is a common problem in multi-agent systems. We consider scenarios in which dynamic agents have preferences about assignments and the resources that can be assigned using online auctions. We study the trade-off between the following online auction properties: (i) truthfulness, (ii) expressiveness, (iii) efficiency, and (iv) average case performance. We theoretically and empirically compare four different online auctions: (i) Arrival Priority Serial Dictatorship, (ii) Split Dynamic VCG, (iii) e-Action, and (iv) Online Ranked Competition Auction. The latter is a novel design based on the competitive secretary problem. We show that, in addition to truthfulness and algorithmic efficiency, the degree of competition also plays an important role in selecting the best algorithm for a given context
A Deterministic MAB Mechanism for Crowdsourcing with Logarithmic Regret and Immediate Payments
Shweta Jain,Ganesh Ghalme,Satyanath Bhat,Sujit P Gujar,Y. Narahari
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2016
@inproceedings{bib_A_De_2016, AUTHOR = {Jain, Shweta and Ghalme, Ganesh and Bhat, Satyanath and Gujar, Sujit P and Narahari, Y. }, TITLE = {A Deterministic MAB Mechanism for Crowdsourcing with Logarithmic Regret and Immediate Payments}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2016}}
We consider a general crowdsourcing setting with strategic workers whose qualities are unknown and design a multiarmed bandit (MAB) mechanism, CrowdUCB, which is deterministic, regret minimizing, and offers immediate payments to the workers. The problem involves sequentially selecting workers to process tasks in order to maximize the social welfare while learning the qualities of the strategic workers (strategic about their costs). Existing MAB mechanisms are either: (a) deterministic which potentially cause significant loss in social welfare, or (b) randomized which typically lead to high variance in payments. CrowdUCB completely addresses the above problems with the following features: (i) offers deterministic payments, (ii) achieves logarithmic regret in social welfare, (iii) renders allocations more effective by allocating blocks of tasks to a worker instead of a single task, and (iv) offers payment to a worker immediately upon completion of an assigned block of tasks. CrowdUCB is a mechanism with learning that learns the qualities of the workers while eliciting their true costs, irrespective of whether or not the workers know their own qualities. We show that CrowdUCB is ex-post individually rational (EPIR) and ex-post incentive compatible (EPIC) when the workers do not know their own qualities and when they update their beliefs in sync with the requester. When the workers know their own qualities, CrowdUCB is EPIR and ε−EPIC where ε is sub-linear in terms of the number of tasks.
Crowdfunding Public Projects with Provision Point: A Prediction Market Approach
Praphul Chandra,Sujit P Gujar,Y Narahari
European Conference on Artificial Intelligence, ECAI, 2016
@inproceedings{bib_Crow_2016, AUTHOR = {Chandra, Praphul and Gujar, Sujit P and Narahari, Y }, TITLE = {Crowdfunding Public Projects with Provision Point: A Prediction Market Approach}, BOOKTITLE = {European Conference on Artificial Intelligence}. YEAR = {2016}}
Crowdfunding is emerging as a popular means to generate funding from citizens for public projects. This is popularly known as civic crowdfunding. In this paper, we focus on crowdfunding public projects with provision point: these are projects in which contributions must reach a predetermined threshold in order for the project to be provisioned. On web based civic crowdfunding platforms, the success of crowdfunding public projects has been somewhat mixed. In this paper, our objective is to design a mechanism that improves the success of crowdfunding public projects. In particular, we propose a class of mechanisms for crowdfunding platforms with sequentially arriving agents. This class of mechanisms induces an extensive form game for agents arriving on the platform and we show that the game has a non-empty set of sub-game perfect equilibria at which the project is fully funded. We call this new class of mechanisms Provision Point Mechanism with Securities (PPS). The novelty of PPS lies in the use of a prediction market to incentivize agents to contribute in proportion to their true value for the project and to contribute as soon as they arrive at the crowdfunding platform. Different variations of PPS are possible depending on the underlying prediction market. In this paper, we use a cost function (or equivalently, scoring rule) based prediction market; in fact, we specify the requirements that a cost function should satisfy to be used in PPS. We study and compare two specific instances of PPS: (1) Logarithmic Market Scoring Rule based and (2) Quadratic Scoring Rule based. We also discuss the considerations that should guide the choice of the cost function when deploying our mechanism on crowdfunding platforms
Crowdsourced Referral Auctions
Praphul Chandra ,Sujit P Gujar,Y Narahari
European Conference on Artificial Intelligence, ECAI, 2016
@inproceedings{bib_Crow_2016, AUTHOR = {, Praphul Chandra and Gujar, Sujit P and Narahari, Y }, TITLE = {Crowdsourced Referral Auctions}, BOOKTITLE = {European Conference on Artificial Intelligence}. YEAR = {2016}}
Motivated by web based marketplaces where the number of bidders in an auction is a small subset of potential bidders, we consider auctions where the auctioneer (seller) wishes to increase her revenue and/or social welfare by expanding the pool of participants. To this end, the seller crowdsources this task by offering a referral bonus to the participants. With the introduction of referrals, a participant can now bid and/or refer other agents to bid. We call our auctions crowdsourced referral auctions since the seller exploits the knowledge that agents have about other potential participants in the crowd. We introduce the notion of price of locality to quantify the loss in social welfare due to restricted (local) access of the seller to potential bidders. We introduce the notion of Crowdsourced Referral Auction Mechanisms (CRAMs), propose two novel versions of CRAMs and study the induced referral game in the canonical context of an auction for selling a single indivisible item. We compare their revenue performance and game theoretic properties and show that both of them outperform the baseline auction without referrals
Referral-Embedded Provision Point Mechanisms for Crowdfunding of Public Projects
Praphul Chandra,Sujit P Gujar,Y. Narahari
International Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2016
@inproceedings{bib_Refe_2016, AUTHOR = {Chandra, Praphul and Gujar, Sujit P and Narahari, Y. }, TITLE = {Referral-Embedded Provision Point Mechanisms for Crowdfunding of Public Projects}, BOOKTITLE = {International Conference on Autonomous Agents and Multiagent Systems}. YEAR = {2016}}
Civic Crowdfunding is emerging as a popular means to mobilize funding from citizens for public projects. A popular mechanism deployed on civic crowdfunding platforms is a provision point mechanism, wherein, the total contributions must reach a predetermined threshold in order for the project to be provisioned (undertaken). Such a mechanism may have multiple equilibria; unfortunately, in many of these equilibria, the project is not funded even if it is highly valued among the agents.Recent work has proposed mechanisms with refund bonuses where the project gets funded in equilibrium if its net value is higher than a threshold among the agents who are aware of the crowdfunding effort. In this paper, we formalize the notion of social desirability of a public project and propose mechanisms which use the idea of referrals to expand the pool of participants and achieve an equilibrium in which the project gets funded if its net value exceeds a threshold among the entire agent population. We call this new class of mechanisms Referral-Embedded Provision Point Mechanisms (REPPM). We specifically propose two variants of REPPM and both these mechanisms have the remarkable property that, at equilibrium, referral bonuses are offered but there is no need for actual payment of these bonuses. We establish that any given agent’s equilibrium strategy is to refer other agents and to contribute in proportion to the agent’s true value for the project. By referring others to contribute, an agent can, in fact, reduce his equilibrium contribution. In our view, the proposed mechanisms will lead to an increase in the number of projects that are funded on civic crowdfunding platforms.
Dynamic Task Assignments: An Online Two Sided Matching Approach
Sujit P Gujar,Boi Faltings
International Workshop on Matching Under Preferences, MATCHUP, 2015
@inproceedings{bib_Dyna_2015, AUTHOR = {Gujar, Sujit P and Faltings, Boi }, TITLE = {Dynamic Task Assignments: An Online Two Sided Matching Approach}, BOOKTITLE = {International Workshop on Matching Under Preferences}. YEAR = {2015}}
For the task assignment problem in an expert crowdsourcing platform, we propose that the dynamically arriving workers report their preferences for the tasks as ordinal preferences to the platform. We model then the task assignment problem as a dynamic two sided matching problem. In this paper we study the dynamic two sided matching when the men (the workers) side of the market is arriving dynamically and the women (the requesters) side is available since beginning. We assume strict preferences of the agents. Using a deferred acceptance algorithm as a building block, we first develop f AP ODA, a class of strategy-proof online mechanisms. We design f AP ODA and f T hODA in this class. As no mechanism can achieve stability in our settings, we propose a weaker notion of stability, namely, progressive stability. We introduce an online mechanism f RODA that achieve the progressive stability. For achieving good rank-efficiency, we design an online matching mechanism f BOMA. We study all the four mechanisms empirically for stability and rank-efficiency.
Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing
Sujit P Gujar,Boi Faltings
Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing, AMEC/TADA, 2015
@inproceedings{bib_Auct_2015, AUTHOR = {Gujar, Sujit P and Faltings, Boi }, TITLE = {Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing}, BOOKTITLE = {Auction Based Mechanisms for Dynamic Task Assignments in Expert Crowdsourcing}. YEAR = {2015}}
Crowdsourcing marketplaces link large populations of workers to an even larger number of tasks. Thus, it is necessary to have mechanisms for matching workers with interesting and suitable tasks. Earlier work has addressed the problem of finding optimal workers for a given set of tasks. However, workers also have preferences and will stay with a platform only if it gives them interesting tasks. We therefore analyze several matching mechanisms that take into account workers’ preferences as well. We propose that the workers pay premiums to get preferred matches and auction-based models where preferences are expressed through variations of the payment for a task. We analyze the properties of two matching different mechanisms: Split Dynamic VCG (SDV) and e-Auction. We compare both the mechanisms with Arrival Priority Serial Dictatorship (APSD) empirically for efficiency.
RISC: Robust Infrastructure over Shared Computing Resources Through Dynamic Pricing and Incentivization
Tridib Mukherjee,Partha Dutta,Vinay G. Hegde,Sujit P Gujar
International Parallel and Distributed Processing Symposium, IPDPS, 2015
@inproceedings{bib_RISC_2015, AUTHOR = {Mukherjee, Tridib and Dutta, Partha and Hegde, Vinay G. and Gujar, Sujit P }, TITLE = {RISC: Robust Infrastructure over Shared Computing Resources Through Dynamic Pricing and Incentivization}, BOOKTITLE = {International Parallel and Distributed Processing Symposium}. YEAR = {2015}}
This paper presents a framework for Robust Infrastructure over Shared Computing resource (RISC), which can offer Organizations with Small-scale Computing infrastructures (OSCs) a way to share their unused resources in an ad-hoc manner for suitable monetary incentives. Such a framework provides dual benefits to an OSC: it enables sharing of unused resource during periods of low computing load while allowing execution of any long-term computation on public or anonymized data at a very low cost during periods of high load. The ad-hoc and heterogeneous nature of the shared infrastructure make the resource management problem in RISC non-trivial—a resource manager needs to: (i) maximize profit while determining incentives for resource owners and prices for resource users in an integrated manner; and (ii) emulate large-scale cloud-like robustness and capabilities out of unreliable, small-scale and intermittently available resources at a low cost. This leads to a constrained market situation where offered prices and incentives should lead to a desired level of SLA and reliability for the consumers. Existing approaches of incentive based scheduling for market-like grids assume an open market, based only on demand response; and thus are inapplicable for the constrained market situation in shared resources infrastructure. Specifically, RISC framework has two main components: (i) a firstof-a-kind Dynamic Pricing and Incentivization (DPI) strategy that computes the incentives and the prices while maximizing profit for RISC, using an epoch-by-epoch pricing feedback loop; and (ii) a DPI dependent Reliability, Cost and SLAaware (RCS) scheduler that takes the resource reservation requests as input and assigns replicas of these requests to one or more shared resources for guaranteeing performance SLAs and reliability, while minimizing the cost of resource reservations. Moreover, to handle the communication overhead of computing over geographically distributed resources, the scheduler strives to reduce the network cost of resource allocation. Results from extensive trace-driven experimentation show that our approach can indeed provide appropriate incentives for resource providers, and robust cost-efficient infrastructure solution for resource users.
Copyright © 2023 All rights reserved