Showing 1–50 of 64 results for author: Gujar, S

MEV Ecosystem Evolution From Ethereum 1.0

Authors: Rasheed, Yash Chaurasia, Parth Desai, Sujit Gujar

Abstract: Smart contracts led to the emergence of the decentralized finance (DeFi) marketplace within blockchain ecosystems, where diverse participants engage in financial activities. In traditional finance, there are possibilities to create values, e.g., arbitrage offers to create value from market inefficiencies or front-running offers to extract value for the participants having privileged roles. Such op… ▽ More Smart contracts led to the emergence of the decentralized finance (DeFi) marketplace within blockchain ecosystems, where diverse participants engage in financial activities. In traditional finance, there are possibilities to create values, e.g., arbitrage offers to create value from market inefficiencies or front-running offers to extract value for the participants having privileged roles. Such opportunities are readily available -- searching programmatically in DeFi. It is commonly known as Maximal Extractable Value (MEV) in the literature. In this survey, first, we show how lucrative such opportunities can be. Next, we discuss how protocol-following participants trying to capture such opportunities threaten to sabotage blockchain's performance and the core tenets of decentralization, transparency, and trustlessness that blockchains are based on. Then, we explain different attempts by the community in the past to address these issues and the problems introduced by these solutions. Finally, we review the current state of research trying to restore trustlessness and decentralization to provide all DeFi participants with a fair marketplace. △ Less

Submitted 19 June, 2024; originally announced June 2024.

Towards Fairness in Provably Communication-Efficient Federated Recommender Systems

Authors: Kirandeep Kaur, Sujit Gujar, Shweta Jain

Abstract: To reduce the communication overhead caused by parallel training of multiple clients, various federated learning (FL) techniques use random client sampling. Nonetheless, ensuring the efficacy of random sampling and determining the optimal number of clients to sample in federated recommender systems (FRSs) remains challenging due to the isolated nature of each user as a separate client. This challe… ▽ More To reduce the communication overhead caused by parallel training of multiple clients, various federated learning (FL) techniques use random client sampling. Nonetheless, ensuring the efficacy of random sampling and determining the optimal number of clients to sample in federated recommender systems (FRSs) remains challenging due to the isolated nature of each user as a separate client. This challenge is exacerbated in models where public and private features can be separated, and FL allows communication of only public features (item gradients). In this study, we establish sample complexity bounds that dictate the ideal number of clients required for improved communication efficiency and retained accuracy in such models. In line with our theoretical findings, we empirically demonstrate that RS-FairFRS reduces communication cost (~47%). Second, we demonstrate the presence of class imbalance among clients that raises a substantial equity concern for FRSs. Unlike centralized machine learning, clients in FRS can not share raw data, including sensitive attributes. For this, we introduce RS-FairFRS, first fairness under unawareness FRS built upon random sampling based FRS. While random sampling improves communication efficiency, we propose a novel two-phase dual-fair update technique to achieve fairness without revealing protected attributes of active clients participating in training. Our results on real-world datasets and different sensitive features illustrate a significant reduction in demographic bias (~approx40\%), offering a promising path to achieving fairness and communication efficiency in FRSs without compromising the overall accuracy of FRS. △ Less

Submitted 2 May, 2024; originally announced May 2024.

Towards Rational Consensus in Honest Majority

Authors: Varul Srivastava, Sujit Gujar

Abstract: Distributed consensus protocols reach agreement among $n$ players in the presence of $f$ adversaries; different protocols support different values of $f$. Existing works study this problem for different adversary types (captured by threat models). There are three primary threat models: (i) Crash fault tolerance (CFT), (ii) Byzantine fault tolerance (BFT), and (iii) Rational fault tolerance (RFT),… ▽ More 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) <n/2$ if rational players prefer liveness or censorship attacks and (2) the consensus protocol proposed by Ranchal-Pedrosa and Gramoli cannot be generalized to solve ABC due to insecure Nash equilibrium (resulting in disagreement). For ABC in partially synchronous network settings, we propose a novel protocol \textsf{pRFT}(practical Rational Fault Tolerance). We show \textsf{pRFT} achieves ABC if (a) rational players prefer only disagreement attacks and (b) $t < \frac{n}{4}$ and $(t + k) < \frac{n}{2}$. In \textsf{pRFT}, we incorporate accountability (capturing deviating players) within the protocol by leveraging honest players. We also show that the message complexity of \textsf{pRFT} is at par with the best consensus protocols that guarantee accountability. △ Less

Submitted 13 May, 2024; originally announced May 2024.

Centralization in Proof-of-Stake Blockchains: A Game-Theoretic Analysis of Bootstrapping Protocols

Authors: Varul Srivastava, Sankarshan Damle, Sujit Gujar

Abstract: 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. T… ▽ More 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 $Γ_\textsf{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 -- $Γ_\textsf{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. △ Less

Submitted 15 April, 2024; originally announced April 2024.

Comments: Appears at the 6th Games, Agents, and Incentives Workshop (GAIW-24). Held as part of the Workshops at the 22st International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

Fairness of Exposure in Online Restless Multi-armed Bandits

Authors: Archit Sood, Shweta Jain, Sujit Gujar

Abstract: Restless multi-armed bandits (RMABs) generalize the multi-armed bandits where each arm exhibits Markovian behavior and transitions according to their transition dynamics. Solutions to RMAB exist for both offline and online cases. However, they do not consider the distribution of pulls among the arms. Studies have shown that optimal policies lead to unfairness, where some arms are not exposed enoug… ▽ More Restless multi-armed bandits (RMABs) generalize the multi-armed bandits where each arm exhibits Markovian behavior and transitions according to their transition dynamics. Solutions to RMAB exist for both offline and online cases. However, they do not consider the distribution of pulls among the arms. Studies have shown that optimal policies lead to unfairness, where some arms are not exposed enough. Existing works in fairness in RMABs focus heavily on the offline case, which diminishes their application in real-world scenarios where the environment is largely unknown. In the online scenario, we propose the first fair RMAB framework, where each arm receives pulls in proportion to its merit. We define the merit of an arm as a function of its stationary reward distribution. We prove that our algorithm achieves sublinear fairness regret in the single pull case $O(\sqrt{T\ln T})$, with $T$ being the total number of episodes. Empirically, we show that our algorithm performs well in the multi-pull scenario as well. △ Less

Submitted 9 February, 2024; originally announced February 2024.

Comments: Accepted as extended abstract in AAMAS 2024

Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits

Authors: Subham Pokhriyal, Shweta Jain, Ganesh Ghalme, Swapnil Dhamal, Sujit Gujar

Abstract: Existing approaches to fairness in stochastic multi-armed bandits (MAB) primarily focus on exposure guarantee to individual arms. When arms are naturally grouped by certain attribute(s), we propose Bi-Level Fairness, which considers two levels of fairness. At the first level, Bi-Level Fairness guarantees a certain minimum exposure to each group. To address the unbalanced allocation of pulls to ind… ▽ More 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 $O(\sqrt{T})$ on regret; $T$ 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. △ Less

Submitted 8 February, 2024; originally announced February 2024.

Comments: Accepted in AAMAS 2024

No Transaction Fees? No Problem! Achieving Fairness in Transaction Fee Mechanism Design

Authors: Sankarshan Damle, Varul Srivastava, Sujit Gujar

Abstract: The recently proposed Transaction Fee Mechanism (TFM) literature studies the strategic interaction between the miner of a block and the transaction creators (or users) in a blockchain. In a TFM, the miner includes transactions that maximize its utility while users submit fees for a slot in the block. The existing TFM literature focuses on satisfying standard incentive properties -- which may limit… ▽ More 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 constraints. △ Less

Submitted 7 February, 2024; originally announced February 2024.

Comments: Extended Abstract (AAMAS '24)

Fairness and Privacy Guarantees in Federated Contextual Bandits

Authors: Sambhav Solanki, Shweta Jain, Sujit Gujar

Abstract: This paper considers the contextual multi-armed bandit (CMAB) problem with fairness and privacy guarantees in a federated environment. We consider merit-based exposure as the desired fair outcome, which provides exposure to each action in proportion to the reward associated. We model the algorithm's effectiveness using fairness regret, which captures the difference between fair optimal policy and… ▽ More 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. △ Less

Submitted 5 February, 2024; originally announced February 2024.

Comments: 16 pages, 2 figures

Analyzing Crowdfunding of Public Projects Under Dynamic Beliefs

Authors: Sankarshan Damle, Sujit Gujar

Abstract: In the last decade, social planners have used crowdfunding to raise funds for public projects. As these public projects are non-excludable, the beneficiaries may free-ride. Thus, there is a need to design incentive mechanisms for such strategic agents to contribute to the project. The existing mechanisms, like PPR or PPRx, assume that the agent's beliefs about the project getting funded do not cha… ▽ More In the last decade, social planners have used crowdfunding to raise funds for public projects. As these public projects are non-excludable, the beneficiaries may free-ride. Thus, there is a need to design incentive mechanisms for such strategic agents to contribute to the project. The existing mechanisms, like PPR or PPRx, assume that the agent's beliefs about the project getting funded do not change over time, i.e., their beliefs are static. Researchers highlight that unless appropriately incentivized, the agents defer their contributions in static settings, leading to a ``race'' to contribute at the deadline. In this work, we model the evolution of agents' beliefs as a random walk. We study PPRx -- an existing mechanism for the static belief setting -- in this dynamic belief setting and refer to it as PPRx-DB for readability. We prove that in PPRx-DB, the project is funded at equilibrium. More significantly, we prove that under certain conditions on agent's belief evolution, agents will contribute as soon as they arrive at the mechanism. Thus, we believe that by incorporating dynamic belief evolution in analysis, the social planner can mitigate the concern of race conditions in many mechanisms. △ Less

Submitted 1 February, 2024; originally announced February 2024.

Comments: AAMAS '24 (Extended Abstract)

Designing Redistribution Mechanisms for Reducing Transaction Fees in Blockchains

Authors: Sankarshan Damle, Manisha Padala, Sujit Gujar

Abstract: 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 Redistri… ▽ More 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}$^2$\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. △ Less

Submitted 24 January, 2024; originally announced January 2024.

Comments: Full Paper (AAMAS '24)

DECENT-BRM: Decentralization through Block Reward Mechanisms

Authors: Varul Srivastava, Sujit Gujar

Abstract: 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 bl… ▽ More 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 > \underline{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 -- \textsf{Decent-BRM}. We show that under \textsf{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 \textsf{Decent-BRM} is decentralized. △ Less

Submitted 17 January, 2024; originally announced January 2024.

Automated DevOps Pipeline Generation for Code Repositories using Large Language Models

Authors: Deep Mehta, Kartik Rawool, Subodh Gujar, Bowen Xu

Abstract: Automating software development processes through the orchestration of GitHub Action workflows has revolutionized the efficiency and agility of software delivery pipelines. This paper presents a detailed investigation into the use of Large Language Models (LLMs) specifically, GPT 3.5 and GPT 4 to generate and evaluate GitHub Action workflows for DevOps tasks. Our methodology involves data collecti… ▽ More Automating software development processes through the orchestration of GitHub Action workflows has revolutionized the efficiency and agility of software delivery pipelines. This paper presents a detailed investigation into the use of Large Language Models (LLMs) specifically, GPT 3.5 and GPT 4 to generate and evaluate GitHub Action workflows for DevOps tasks. Our methodology involves data collection from public GitHub repositories, prompt engineering for LLM utilization, and evaluation metrics encompassing exact match scores, BLEU scores, and a novel DevOps Aware score. The research scrutinizes the proficiency of GPT 3.5 and GPT 4 in generating GitHub workflows, while assessing the influence of various prompt elements in constructing the most efficient pipeline. Results indicate substantial advancements in GPT 4, particularly in DevOps awareness and syntax correctness. The research introduces a GitHub App built on Probot, empowering users to automate workflow generation within GitHub ecosystem. This study contributes insights into the evolving landscape of AI-driven automation in DevOps practices. △ Less

Submitted 20 December, 2023; originally announced December 2023.

Fair Allocation of goods and chores -- Tutorial and Survey of Recent Results

Authors: Shaily Mishra, Manisha Padala, Sujit Gujar

Abstract: 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 define fairness and efficiency within this context and thoroughly survey existential results, algori… ▽ More 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 define 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 computational complexities, fairness guarantees, and trade-offs between fairness and efficiency. It serves as a foundation for future advancements in this vital field. △ Less

Submitted 21 July, 2023; v1 submitted 20 July, 2023; originally announced July 2023.

Exploring User Perspectives on ChatGPT: Applications, Perceptions, and Implications for AI-Integrated Education

Authors: Reza Hadi Mogavi, Chao Deng, Justin Juho Kim, Pengyuan Zhou, Young D. Kwon, Ahmed Hosny Saleh Metwally, Ahmed Tlili, Simone Bassanelli, Antonio Bucchiarone, Sujit Gujar, Lennart E. Nacke, Pan Hui

Abstract: 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 o… ▽ More 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. △ Less

Submitted 25 November, 2023; v1 submitted 22 May, 2023; originally announced May 2023.

Comments: This is the authors' preprint version of the paper accepted by the Journal of Computers in Human Behavior: Artificial Humans (doi: https://doi.org/10.1016/j.chbah.2023.100027)

A Novel Demand Response Model and Method for Peak Reduction in Smart Grids -- PowerTAC

Authors: Sanjay Chandlekar, Arthik Boroju, Shweta Jain, Sujit Gujar

Abstract: 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 simulato… ▽ More 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. △ Less

Submitted 24 February, 2023; originally announced February 2023.

Comments: 11 pages, 5 figures, 2 tables, Accepted as an Extended Abstract in AAMAS'23

PRAGTHOS:Practical Game Theoretically Secure Proof-of-Work Blockchain

Authors: Varul Srivastava, Dr. Sujit Gujar

Abstract: Security analysis of blockchain technology is an active domain of research. There has been both cryptographic and game-theoretic security analysis of Proof-of-Work (PoW) blockchains. Prominent work includes the cryptographic security analysis under the Universal Composable framework and Game-theoretic security analysis using Rational Protocol Design. These security analysis models rely on stricter… ▽ More Security analysis of blockchain technology is an active domain of research. There has been both cryptographic and game-theoretic security analysis of Proof-of-Work (PoW) blockchains. Prominent work includes the cryptographic security analysis under the Universal Composable framework and Game-theoretic security analysis using Rational Protocol Design. These security analysis models rely on stricter assumptions that might not hold. In this paper, we analyze the security of PoW blockchain protocols. We first show how assumptions made by previous models need not be valid in reality, which attackers can exploit to launch attacks that these models fail to capture. These include Difficulty Alternating Attack, under which forking is possible for an adversary with less than 0.5 mining power, Quick-Fork Attack, a general bound on selfish mining attack and transaction withholding attack. Following this, we argue why previous models for security analysis fail to capture these attacks and propose a more practical framework for security analysis pRPD. We then propose a framework to build PoW blockchains PRAGTHOS, which is secure from the attacks mentioned above. Finally, we argue that PoW blockchains complying with the PRAGTHOS framework are secure against a computationally bounded adversary under certain conditions on the reward scheme. △ Less

Submitted 13 February, 2023; originally announced February 2023.

Your Favorite Gameplay Speaks Volumes about You: Predicting User Behavior and Hexad Type

Authors: Reza Hadi Mogavi, Chao Deng, Jennifer Hoffman, Ehsan-Ul Haq, Sujit Gujar, Antonio Bucchiarone, Pan Hui

Abstract: 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 inves… ▽ More 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. △ Less

Submitted 11 February, 2023; originally announced February 2023.

Comments: This manuscript is the pre-print version of our paper accepted at the conference of HCI International 2023

AVeCQ: Anonymous Verifiable Crowdsourcing with Worker Qualities

Authors: Sankarshan Damle, Vlasis Koutsos, Dimitrios Papadopoulos, Dimitris Chatzopoulos, Sujit Gujar

Abstract: 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 w… ▽ More 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 zero-knowledge 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-the-art, 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. △ Less

Submitted 8 February, 2023; originally announced February 2023.

Combinatorial Civic Crowdfunding with Budgeted Agents: Welfare Optimality at Equilibrium and Optimal Deviation

Authors: Sankarshan Damle, Manisha Padala, Sujit Gujar

Abstract: 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 applic… ▽ More 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. △ Less

Submitted 25 November, 2022; originally announced November 2022.

Comments: To appear in the Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI '23). A preliminary version of this paper titled "Welfare Optimal Combinatorial Civic Crowdfunding with Budgeted Agents" also appeared at GAIW@AAMAS '22

PUPoW: A framework for designing blockchains with practically-useful-proof-of-work & vanitycoin

Authors: Yash Chaurasia, Visvesh Subramanian, Sujit Gujar

Abstract: Bitcoin is the first of its kind, a truly decentralized and anonymous cryptocurrency. To realize it, it has developed blockchain technology using the concept of `Proof of Work' (PoW). The miners, nodes responsible for writing transaction databases, solve a cryptographic puzzle to claim the right to write to the database. Though bitcoin and many other relevant cryptocurrencies, such as ether use re… ▽ More Bitcoin is the first of its kind, a truly decentralized and anonymous cryptocurrency. To realize it, it has developed blockchain technology using the concept of `Proof of Work' (PoW). The miners, nodes responsible for writing transaction databases, 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 computing resources and energy consumption to solve 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 the puzzler to the miner who solves its puzzle. Additionally, miners have the option to not rely on a 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 problems require generating 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 helpful, and we believe such an approach is needed for PoW blockchains to survive. △ Less

Submitted 13 October, 2022; originally announced October 2022.

Interlude: Balancing Chaos And Harmony For Fair and Fast Blockchains

Authors: Anurag Jain, Sujit Gujar, Kannan Srinathan

Abstract: 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 sca… ▽ More 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 game-theoretic 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. △ Less

Submitted 21 September, 2022; originally announced September 2022.

Differentially Private Federated Combinatorial Bandits with Constraints

Authors: Sambhav Solanki, Samhita Kanaparthy, Sankarshan Damle, Sujit Gujar

Abstract: 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… ▽ More 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. △ Less

Submitted 28 May, 2023; v1 submitted 27 June, 2022; originally announced June 2022.

Comments: 12 pages, 4 Figures, A version of this paper has appeared in the Proceedings of the ECML PKDD '22

Coordinating Monetary Contributions in Participatory Budgeting

Authors: Haris Aziz, Sujit Gujar, Manisha Padala, Mashbat Suzuki, Jeremy Vollen

Abstract: We formalize a framework for coordinating funding and selecting projects, the costs of which are shared 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 useful scenarios. We propose several important axioms and objectives and study how well they can be simultaneo… ▽ More We formalize a framework for coordinating funding and selecting projects, the costs of which are shared 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 useful scenarios. We propose several important axioms and objectives and study how well they can be simultaneously satisfied. We show that whereas welfare maximization admits an FPTAS, welfare maximization subject to a natural and very weak participation requirement leads to a strong inapproximability. This result is bypassed if we consider some natural restricted valuations, namely laminar single-minded valuations and symmetric valuations. Our analysis for the former restriction leads to the discovery of a new class of tractable instances for the Set Union Knapsack problem, a classical problem in combinatorial optimization. △ Less

Submitted 22 February, 2023; v1 submitted 13 June, 2022; originally announced June 2022.

Comments: In this version, we include results regarding single minded valuations. We have also corrected a bug in the proof of Lemma 1

Tiramisu: Layering Consensus Protocols for Scalable and Secure Blockchains

Authors: Anurag Jain, Sanidhay Arora, Sankarshan Damle, Sujit Gujar

Abstract: 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, hi… ▽ More 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. △ Less

Submitted 24 March, 2022; v1 submitted 21 March, 2022; originally announced March 2022.

Individual Fairness in Feature-Based Pricing for Monopoly Markets

Authors: Shantanu Das, Swapnil Dhamal, Ganesh Ghalme, Shweta Jain, Sujit Gujar

Abstract: 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 a… ▽ More 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 an optimal feature-based pricing to the expected revenue in an optimal fair feature-based pricing (CoF) can be arbitrarily large in general. When the revenue function is continuous and concave with respect to the prices, we show that one can achieve CoF strictly less than 2, irrespective of the model parameters. Finally, we provide an algorithm to compute fair feature-based pricing strategy that achieves this CoF. △ Less

Submitted 25 February, 2022; originally announced February 2022.

Budgeted Combinatorial Multi-Armed Bandits

Authors: Debojit Das, Shweta Jain, Sujit Gujar

Abstract: 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 ba… ▽ More 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-LPUCB 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. △ Less

Submitted 13 February, 2022; v1 submitted 8 February, 2022; originally announced February 2022.

Comments: 15 pages, 4 figures. To be published in AAMAS 2022. arXiv admin note: text overlap with arXiv:1305.2545 by other authors

Multi-unit Double Auctions: Equilibrium Analysis and Bidding Strategy using DDPG in Smart-grids

Authors: Sanjay Chandlekar, Easwar Subramanian, Sanjay Bhat, Praveen Paruchuri, Sujit Gujar

Abstract: Periodic double auctions (PDA) have applications in many areas such as in e-commerce, intra-day equity markets, and day-ahead energy markets in smart-grids. While the trades accomplished using PDAs are worth trillions of dollars, finding a reliable bidding strategy in such auctions is still a challenge as it requires the consideration of future auctions. A participating buyer in a PDA has to desig… ▽ More Periodic double auctions (PDA) have applications in many areas such as in e-commerce, intra-day equity markets, and day-ahead energy markets in smart-grids. While the trades accomplished using PDAs are worth trillions of dollars, finding a reliable bidding strategy in such auctions is still a challenge as it requires the consideration of future auctions. A participating buyer in a PDA has to design its bidding strategy by planning for current and future auctions. Many equilibrium-based bidding strategies proposed are complex to use in real-time. In the current exposition, we propose a scale-based bidding strategy for buyers participating in PDA. We first present an equilibrium analysis for single-buyer single-seller multi-unit single-shot k-Double auctions. Specifically, we analyze the situation when a seller and a buyer trade two identical units of quantity in a double auction where both the buyer and the seller deploy a simple, scale-based bidding strategy. The equilibrium analysis becomes intractable as the number of participants increases. To be useful in more complex settings such as wholesale markets in smart-grids, we model equilibrium bidding strategy as a learning problem. We develop a deep deterministic policy gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent in PDAs to suggest an action at any auction instance. DDPGBBS, which empirically follows the obtained theoretical equilibrium, is easily extendable when the number of buyers/sellers increases. We take Power Trading Agent Competition's (PowerTAC) wholesale market PDA as a testbed to evaluate our novel bidding strategy. We benchmark our DDPG based strategy against several baselines and state-of-the-art bidding strategies of the PowerTAC wholesale market PDA and demonstrate the efficacy of DDPGBBS against several benchmarked strategies. △ Less

Submitted 22 February, 2022; v1 submitted 25 January, 2022; originally announced January 2022.

Comments: Accepted for publication in the proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS-22)

REFORM: Reputation Based Fair and Temporal Reward Framework for Crowdsourcing

Authors: Samhita Kanaparthy, Sankarshan Damle, Sujit Gujar

Abstract: Crowdsourcing is an effective method to collect data by employing distributed human population. Researchers introduce appropriate reward mechanisms to incentivize agents to report accurately. In particular, this paper focuses on Peer-Based Mechanisms (PBMs). We observe that with PBMs, crowdsourcing systems may not be fair, i.e., agents may not receive the deserved rewards despite investing efforts… ▽ More 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 gamma-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. △ Less

Submitted 22 December, 2021; v1 submitted 20 December, 2021; originally announced December 2021.

Mechanism Design without Money for Fair Allocations

Authors: Manisha Padala, Sujit Gujar

Abstract: Fairness is well studied in the context of resource allocation. Researchers have proposed various fairness notions like envy-freeness (EF), and its relaxations, proportionality and max-min share (MMS). There is vast literature on the existential and computational aspects of such notions. While computing fair allocations, any algorithm assumes agents' truthful reporting of their valuations towards… ▽ More 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. △ Less

Submitted 14 December, 2021; originally announced December 2021.

How Private Is Your RL Policy? An Inverse RL Based Analysis Framework

Authors: Kritika Prakash, Fiza Husain, Praveen Paruchuri, Sujit P. Gujar

Abstract: 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 Iteratio… ▽ More 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 (PRIL) analysis framework, that performs 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 an 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 multiple 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. △ Less

Submitted 10 December, 2021; originally announced December 2021.

Comments: 15 pages, 7 figures, 5 tables, version accepted at AAAI 2022

EEF1-NN: Efficient and EF1 allocations through Neural Networks

Authors: Shaily Mishra, Manisha Padala, Sujit Gujar

Abstract: 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 allocatio… ▽ More 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. △ Less

Submitted 10 December, 2021; originally announced December 2021.

F3: Fair and Federated Face Attribute Classification with Heterogeneous Data

Authors: Samhita Kanaparthy, Manisha Padala, Sankarshan Damle, Ravi Kiran Sarvadevabhatla, Sujit Gujar

Abstract: 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 i… ▽ More 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. △ Less

Submitted 24 June, 2022; v1 submitted 6 September, 2021; originally announced September 2021.

Comments: This paper is accepted as 2-page extended abstract at CODS-COMAD 2022 with title "Fair Federated Learning for Heterogeneous Face Data"

Fair Allocation with Special Externalities

Authors: Shaily Mishra, Manisha Padala, Sujit Gujar

Abstract: 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 unassigne… ▽ More 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. △ Less

Submitted 25 February, 2022; v1 submitted 29 August, 2021; originally announced August 2021.

Federated Learning Meets Fairness and Differential Privacy

Authors: Manisha Padala, Sankarshan Damle, Sujit Gujar

Abstract: Deep learning's unprecedented success raises several ethical concerns ranging from biased predictions to data privacy. Researchers tackle these issues by introducing fairness metrics, or federated learning, or differential privacy. A first, this work presents an ethical federated learning model, incorporating all three measures simultaneously. Experiments on the Adult, Bank and Dutch datasets high… ▽ More 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. △ Less

Submitted 23 August, 2021; originally announced August 2021.

Sleeping Combinatorial Bandits

Authors: Kumar Abhishek, Ganesh Ghalme, Sujit Gujar, Yadati Narahari

Abstract: In this paper, we study an interesting combination of sleeping and combinatorial stochastic bandits. In the mixed model studied here, at each discrete time instant, an arbitrary \emph{availability set} is generated from a fixed set of \emph{base} arms. An algorithm can select a subset of arms from the \emph{availability set} (sleeping bandits) and receive the corresponding reward along with semi-b… ▽ More 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 \emph{availability set} is generated from a fixed set of \emph{base} arms. An algorithm can select a subset of arms from the \emph{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 \CSUCB. We prove -- under mild smoothness conditions -- that the \CSUCB\ 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 \CSUCB\ algorithm is $O(\sqrt{T \log (T)})$ and (ii) the instance-independent regret is $O(\sqrt[3]{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. △ Less

Submitted 3 June, 2021; originally announced June 2021.

FASTEN: Fair and Secure Distributed Voting Using Smart Contracts

Authors: Sankarshan Damle, Sujit Gujar, Moin Hussain Moti

Abstract: Electing democratic representatives via voting has been a common mechanism since the 17th century. However, these mechanisms raise concerns about fairness, privacy, vote concealment, fair calculations of tally, and proxies voting on their behalf for the voters. Ballot voting, and in recent times, electronic voting via electronic voting machines (EVMs) improves fairness by relying on centralized tr… ▽ More 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, \proto. 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. △ Less

Submitted 21 February, 2021; originally announced February 2021.

Comments: A version of this paper will appear in the IEEE International Conference on Blockchain and Cryptocurrency (IEEE ICBC 2021). This is a full version

A Multi-Arm Bandit Approach To Subset Selection Under Constraints

Authors: Ayush Deva, Kumar Abhishek, Sujit Gujar

Abstract: We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents' quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm,… ▽ More 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 \newalgo\ to learn the qualities over multiple rounds. We show that after a certain number of rounds, $τ$, \newalgo\ 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 \newalgo\ through simulations. To overcome the computational limitations of \dpss, we propose a polynomial-time greedy algorithm, namely \greedy, that provides an approximate solution to our ILP. We also compare the performance of \dpss\ and \greedy\ through experiments. △ Less

Submitted 9 February, 2021; originally announced February 2021.

Comments: Accepted in AAMAS 2021 as Extended Abstract

We might walk together, but I run faster: Network Fairness and Scalability in Blockchains

Authors: Anurag Jain, Shoeb Siddiqui, Sujit Gujar

Abstract: Blockchain-based Distributed Ledgers (DLs) promise to transform the existing financial system by making it truly democratic. In the past decade, blockchain technology has seen many novel applications ranging from the banking industry to real estate. However, in order to be adopted universally, blockchain systems must be scalable to support a high volume of transactions. As we increase the throughp… ▽ More 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, $p_f$, the probability of frontrunning and $α_f$, 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. △ Less

Submitted 19 February, 2021; v1 submitted 8 February, 2021; originally announced February 2021.

Comments: Full Version of the paper submitted to AAMAS as an Extended Abstract

Towards Mobile Distributed Ledgers

Authors: Dimitris Chatzopoulos, Anurag Jain, Sujit Gujar, Boi Faltings, Pan Hui

Abstract: 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 to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data… ▽ More 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 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. △ Less

Submitted 12 January, 2021; originally announced January 2021.

Comments: Part of it was presented in IEEE Infocom 2020

A Multi-Task Deep Learning Framework to Localize the Eloquent Cortex in Brain Tumor Patients Using Dynamic Functional Connectivity

Authors: Naresh Nandakumar, Niharika Shimona D'souza, Komal Manzoor, Jay J. Pillai, Sachin K. Gujar, Haris I. Sair, Archana Venkataraman

Abstract: We present a novel deep learning framework that uses dynamic functional connectivity to simultaneously localize the language and motor areas of the eloquent cortex in brain tumor patients. Our method leverages convolutional layers to extract graph-based features from the dynamic connectivity matrices and a long-short term memory (LSTM) attention network to weight the relevant time points during cl… ▽ More We present a novel deep learning framework that uses dynamic functional connectivity to simultaneously localize the language and motor areas of the eloquent cortex in brain tumor patients. Our method leverages convolutional layers to extract graph-based features from the dynamic connectivity matrices and a long-short term memory (LSTM) attention network to weight the relevant time points during classification. The final stage of our model employs multi-task learning to identify different eloquent subsystems. Our unique training strategy finds a shared representation between the cognitive networks of interest, which enables us to handle missing patient data. We evaluate our method on resting-state fMRI data from 56 brain tumor patients while using task fMRI activations as surrogate ground-truth labels for training and testing. Our model achieves higher localization accuracies than conventional deep learning approaches and can identify bilateral language areas even when trained on left-hemisphere lateralized cases. Hence, our method may ultimately be useful for preoperative mapping in tumor patients. △ Less

Submitted 17 November, 2020; originally announced November 2020.

Comments: Presented at MLCN 2020 workshop, as a part of MICCAI 2020

QuickSync: A Quickly Synchronizing PoS-Based Blockchain Protocol

Authors: Shoeb Siddiqui, Varul Srivastava, Raj Maheshwari, Sujit Gujar

Abstract: 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, such a… ▽ More 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, such as Ouroboros v1, may face vulnerability to fully adaptive corruptions. In this paper, we propose a novel PoS-based blockchain protocol, QuickSync, to achieve security against fully adaptive corruptions while improving 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 attack strategies. Our analysis demonstrates that QuickSync performs better than Bitcoin by an order of magnitude on both transactions per second and time to finality, and better than Ouroboros v1 by a factor of three on time to finality. △ Less

Submitted 16 March, 2023; v1 submitted 7 May, 2020; originally announced May 2020.

Effect of Input Noise Dimension in GANs

Authors: Manisha Padala, Debojit Das, Sujit Gujar

Abstract: 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 n… ▽ More 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 \emph{Fréchet Inception Distance (FID)} and \emph{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. △ Less

Submitted 15 April, 2020; originally announced April 2020.

BitcoinF: Achieving Fairness for Bitcoin in Transaction-Fee-Only Model

Authors: Shoeb Siddiqui, Ganesh Vanahalli, Sujit Gujar

Abstract: 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, i.e., low wait times for transactions and stable price of consumption, i.e., the minimum transaction fee required to have a transaction processed. As Bitcoin matures, the influx of transactions increases… ▽ More 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, i.e., low wait times for transactions and stable price of consumption, i.e., 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, i.e., 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. We propose BitcoinF transaction processing protocol, a simple, yet highly effective modification to the existing Bitcoin protocol to fix these issues of unfairness. BitcoinF resolves these issues of unfairness while preserving the ability of the users to express urgency and have their transactions prioritized. △ Less

Submitted 2 March, 2020; originally announced March 2020.

Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions

Authors: Kumar Abhishek, Shweta Jain, Sujit Gujar

Abstract: 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 (i.e., probability of getting a click… ▽ More 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 (i.e., probability of getting a click $\times$ 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 ($O(T^{\frac{2}{3}})$). △ Less

Submitted 26 February, 2020; originally announced February 2020.

Ballooning Multi-Armed Bandits

Authors: Ganesh Ghalme, Swapnil Dhamal, Shweta Jain, Sujit Gujar, Y. Narahari

Abstract: In this paper, we introduce Ballooning Multi-Armed Bandits (BL-MAB), a novel extension of the classical stochastic MAB model. In the BL-MAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regret in a BL-MAB setting is computed with respect to the best available arm at eac… ▽ More 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 sub-linear 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. △ Less

Submitted 22 February, 2021; v1 submitted 23 January, 2020; originally announced January 2020.

Comments: A full version of this paper is accepted in the Journal of Artificial Intelligence (AIJ) of Elsevier. A preliminary version is published as an extended abstract in AAMAS 2020. Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 2020

Bidding in Smart Grid PDAs: Theory, Analysis and Strategy (Extended Version)

Authors: Susobhan Ghosh, Sujit Gujar, Praveen Paruchuri, Easwar Subramanian, Sanjay P. Bhat

Abstract: Periodic Double Auctions (PDAs) are commonly used in the real world for trading, e.g. 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 highlight… ▽ More Periodic Double Auctions (PDAs) are commonly used in the real world for trading, e.g. 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. △ Less

Submitted 23 November, 2019; v1 submitted 19 November, 2019; originally announced November 2019.

Comments: Accepted for publication in the proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20)

Introduction to Concentration Inequalities

Authors: Kumar Abhishek, Sneha Maheshwari, Sujit Gujar

Abstract: 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. 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. △ Less

Submitted 4 October, 2019; originally announced October 2019.

Comments: 17 pages

A Practical Solution to Yao's Millionaires' Problem and Its Application in Designing Secure Combinatorial Auction

Authors: Sankarshan Damle, Boi Faltings, Sujit Gujar

Abstract: 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, i.e., to determine the richer among two millionaires' securely, finds an application. In this work, we present a new solu… ▽ More 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, i.e., 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, i.e., 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. △ Less

Submitted 15 June, 2019; originally announced June 2019.

FaRM: Fair Reward Mechanism for Information Aggregation in Spontaneous Localized Settings (Extended Version)

Authors: Moin Hussain Moti, Dimitris Chatzopoulos, Pan Hui, Sujit Gujar

Abstract: 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 \emph{selective} and \emph{cumulative} fairness. We characterize a mechanism as fair if it satisfies both notions and present Fa… ▽ More 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 \emph{selective} and \emph{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 \textit{(i)} a \emph{report strength score} to remove the risk of random pairing with dishonest reporters, \textit{(ii)} a \emph{consistency score} to measure an agent's history of accurate reports and distinguish valuable reports, \textit{(iii)} a \emph{reliability score} to estimate the probability of an agent to collude with nearby agents and prevents agents from getting swayed, and \textit{(iv)} a \emph{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. △ Less

Submitted 10 June, 2019; originally announced June 2019.

Comments: 13 pages, IJCAI Main Track Extended version of "FaRM: Fair Reward Mechanism for Information Aggregation in Spontaneous Localized Settings"

Civic Crowdfunding for Agents with Negative Valuations and Agents with Asymmetric Beliefs

Authors: Sankarshan Damle, Moin Hussain Moti, Praphul Chandra, Sujit Gujar

Abstract: 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 asymmet… ▽ More 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. △ Less

Submitted 27 May, 2019; originally announced May 2019.

Comments: Accepted as full paper in IJCAI 2019