Abstract

We propose a new approach to improving student outcomes - the provision of the dream option that allows a student with a job offer to participate in the placement process again. Comparing three different student preference structures, we show that the dream option improves stability; however, it does not always improve student happiness and rank efficiency. Nevertheless, imposing a particular structure on student preferences, namely the sequential preference condition, improves both student happiness and rank efficiency. We recommend when to use the dream option and when not to use it. © 2022 Published by Elsevier Ltd on behalf of Indian Institute of Management Bangalore. This is an open access article under the CC BY-NC-ND license

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 scalable blockchain protocols that demonstrate the potential to solve these challenges. However, many of these protocols come with the assumptions of honest majority and symmetric network access which may not accurately reflect the real world where the participants may be self-interested or rational. Secondly, these works show that their protocol works in an ideal environment where each party has equal access to the network whereas different parties have varying latencies and network speeds. These assumptions may render the protocols susceptible to security threats in the real world, as highlighted by the literature focused on exploring gametheoretic attacks on these protocols. We propose a scalable blockchain protocol, Interlude, which comes with the typical security guarantees while focusing on game-theoretic soundness and network fairness. The novelty of Interlude is that it has a relatively simple design consisting of a sequence of parallel blocks containing disjoint transaction sets that can be mined quickly followed by a series block that is slow to mine and gives the honest parties in the network time to synchronize. Thus, between the chaos of parallel blocks, our blockchain protocol masquerades an interlude moment of harmony in series blocks that synchronize the network.

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

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

Abstract

Community Question Answering Websites (CQAs) like Stack Overflow rely on continuous user contributions to keep their services active. Nevertheless, they often undergo a sharp decline in their user participation during the holiday season, undermining their performance. To address this issue, some CQAs have developed their own special promotional gamification schemes to incentivize users to maintain their contributions throughout the holiday season. These promotional gamification schemes are often time-limited, optional, and run alongside the default gamification schemes of their websites. However, the impact of such promotional gamification schemes on user behavior remains largely unexplored in the existing literature. This paper takes the first steps toward filling this knowledge gap by conducting a large-scale empirical study of a particular promotional gamification scheme called Winter Bash (WB) on the CQA of Stack Overflow. According to our findings, promotional gamification schemes may not be the panacea they are portrayed to be. For example, in the case of WB, we find that the scheme is not effective for improving the collective engagement of all users. Only some particular user types (i.e., experienced and reputable users) are often provoked under WB. Most novice users, who comprise the majority of Stack Overflow website’s user base, seem to be indifferent to such a gamification scheme. Our research also shows the importance of studying the quantity and quality of user engagement in unison to better understand the effectiveness of a gamification scheme. Previous gamification studies in the literature have focused predominantly on studying the quantity of user engagement alone. Last but not least, we conclude our paper by presenting some practical considerations for improving the design of future promotional gamification schemes in CQAs and similar platforms.

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

Abstract

We present a Nash equilibrium analysis for single-buyer singleseller multi-unit 𝑘-double auctions for scaling-based bidding strategies. We then design a Deep Deterministic Policy Gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent to suggest bids that approximately achieve the above Nash equilibrium. We expand DDPGBBS to be helpful in more complex settings with multiple buyers/sellers trading multiple units in a Periodic Double Auction (PDA), such as the wholesale market in smart-grids. We demonstrate the efficacy of DDPGBBS with Power Trading Agent Competition’s (PowerTAC) wholesale market PDA as a testbed.

Abstract

An autonomous broker that liaises between retail customers and power-generating companies (GenCos) is essential for the smart grid ecosystem. The effciency brought in by such brokers to the smart grid setup can be studied through a well-developed simulation environment. In this paper, we describe the design of one such intelligent energy broker called VidyutVanika21 (VV21) and analyze its performance using a simulation platform called PowerTAC (Power Trading Agent Competition). Specifcally, we discuss the retail (VV21–RM) and wholesale market (VV21–WM) modules of VV21 that help the broker achieve high net profts in a competitive setup. Supported by game-theoretic analysis, the VV21–RM designs tariff contracts that a) maintain a balanced portfolio of different types of customers; b) sustain an appropriate level of market share, and c) introduce surcharges on customers to reduce energy usage during peak demand times. The VV21–WM aims to reduce the cost of procurement by following the supply curve of the GenCo to identify its lowest ask for each auction which is then used to generate suitable bids. We further demonstrate the effcacy of the retail and wholesale strategies of VV21 in PowerTAC 2021 fnals and through several controlled experiments.

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 Iteration, Deep-Q Networks, and Vanilla Proximal Policy Optimization. We propose a new Privacy-Aware Inverse RL analysis framework (PRIL) that involves performing reward reconstruction as an adversarial attack on private policies that the agents may deploy. For this, we introduce the reward reconstruction attack, wherein we seek to reconstruct the original reward from a privacy-preserving policy using the Inverse RL algorithm. An adversary must do poorly at reconstructing the original reward function if the agent uses a tightly private policy. Using this framework, we empirically test the effectiveness of the privacy guarantee offered by the private algorithms on instances of the FrozenLake domain of varying complexities. Based on the analysis performed, we infer a gap between the current standard of privacy offered and the standard of privacy needed to protect reward functions in RL. We do so by quantifying the extent to which each private policy protects the reward function by measuring distances between the original and reconstructed rewards.

Abstract

Crowdfunding is an efficient method for raising funds for projects. When used for non-excludable public projects, the process is termed Civic Crowdfunding (CC) and is an active research area. Researchers have analyzed CC in game-theoretic settings assuming that agents are interested in (and contribute to) a single public project. Gen- eralizing the existing single project theory to determine agents’ equilibrium contributions for multiple projects is non-trivial – espe- cially with budget-constrained agents. This work hypothesizes that the agents can learn their equilibrium contributions with repeated participation in multi-project CC. We model CC as a game to vali- date the hypothesis and build an RL-based simulator: EqC-Learner. We first show that EqC-Learner learns a policy that mimics equi- librium contributions in a single project case for the existing CC mechanisms. To validate EqC-Learner for the multi-project case, we present certain theoretical results for the general multi-project case. Via extensive simulation-based experiments, we show that the learned contributions in EqC-Learner follow all the available theo- retical analysis. Thus, we believe that such an RL-based simulator can learn equilibrium contributions for the general multi-project CC mechanism