Publications

Expand All | Collapse All

Working Papers

  1. A Gale-Shapley View of Unique Stable Marriages
    Kartik Gokhale, Amit Kumar Mallik, Ankit Kumar Misra, and Swaprava Nath
    Technical Report.
    Abstract and Full Paper

    Stable marriage of a two-sided market with unit demand is a classic problem that arises in many real-world scenarios. In addition, a unique stable marriage in this market simplifies a host of downstream desiderata. In this paper, we explore a new set of sufficient conditions for unique stable matching (USM) under this setup. Unlike other approaches that also address this question using the structure of preference profiles, we use an algorithmic viewpoint and investigate if this question can be answered using the lens of the deferred acceptance (DA) algorithm (Gale and Shapley, 1962). Our results yield a set of sufficient conditions for USM (viz., MaxProp and MaxRou) and show that these are disjoint from the previously known sufficiency conditions like sequential preference and no crossing. We also provide a characterization of MaxProp that makes it efficiently verifiable, and shows the gap between MaxProp and the entire USM class. These results give a more detailed view of the sub-structures of the USM class.

    [PDF]


Journal

  1. Incentivizing Effort and Precision in Peer-grading
    Anujit Chakraborty, Jatin Jindal, and Swaprava Nath
    Journal of Artificial Intelligence Research (JAIR), To appear.
    Abstract and Full Paper

    Most peer-evaluation practices rely on the peer evaluator's goodwill for an accurate evaluation. But what if graders are competitive, i.e., enjoy higher utility when their peers get lower scores? We introduce a new mechanism, PEQA, that uses a score-assignment rule and a grading performance score to incentivize such graders. The score-assignment rule aggregates multiple peer-evaluations to assign a final score that is free from grader-bias. The rule and the performance score also guarantee that any grader's utility increases monotonically with her grading precision. In a class of assignment rules that generalize over the least squares estimator, our assignment rule uniquely satisfies this utility-precision monotonicity while allowing flexibility in how large performance scores need to be. PEQA implements the socially optimal effort-choices in an equilibrium of the peer-evaluation game among co-graders. Data from our classroom experiments confirm our theoretical assumptions and show that PEQA outperforms the popular median mechanism.

    [PDF] [code and data (academic use only)]


  2. Algorithmic Mechanism Design for Egalitarian and Congestion Aware Airport Slot Allocation
    Aasheesh Dixit*, Garima Shakya*, Suresh Kumar Jakhar, and Swaprava Nath (*equal contribution)
    Transportation Research Part E (2023): Volume 169, January 2023, 102971.
    Abstract and Full Paper

    We propose a mechanism to allocate slots fairly at congested airports. This mechanism: (a) ensures that the slots are allocated according to the true valuations of airlines, (b) provides fair opportunities to the flights connecting remote cities to large airports, and (c) controls the number of flights in each slot to minimize congestion. The mechanism draws inspiration from economic theory. It allocates the slots based on an affine maximizer allocation rule and charges payments to the airlines such that they are incentivized to reveal their true valuations. The allocation is also fair in providing more importance to the flights originating from cities with low-volume of air traffic. The allocation also optimizes the occupancy of every slot to keep them as uncongested as possible. The formulation solves an optimal integral solution in strongly polynomial time. We conduct experiments on the data collected from two major airports in India. We also compare our results with existing allocations and also with the allocations based on the International Air Transport Association (IATA) guidelines. The computational results show that the social utility generated using our mechanism is 20-30% higher than IATA and current allocations.

    [PDF] [Journal Link]


  3. Truthful ownership transfer with expert advice
    Ioannis Caragiannis, Aris Filos-Ratsikas, Swaprava Nath, and Alexandros A. Voudouris
    Mathematical Programming (2022): 1-30.
    Abstract and Full Paper

    When a company undergoes a merger or transfers its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, like the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the opinions of the internal experts. Motivated by such scenarios, we consider a social welfare maximizing approach to design and analyze truthful mechanisms in hybrid social choice settings, where payments can be imposed to the bidders, but not to the experts. Since this problem is a combination of mechanism design with and without monetary transfers, classical solutions like VCG cannot be applied, making this a novel mechanism design problem. We consider the scenario with one expert and two bidders, and provide tight approximation guarantees of the optimal social welfare. We distinguish between mechanisms that use ordinal and cardinal information, as well as between mechanisms that base their decisions on one of the two sides (either the bidders or the expert) or both. Our analysis shows that the cardinal setting is quite rich and admits several non-trivial randomized truthful mechanisms, and also allows for closer-to-optimal-welfare guarantees.

    [PDF] [Journal Link]


  4. A Parameterized Perspective on Protecting Elections
    Palash Dey, Neeldhara Misra, Swaprava Nath, and Garima Shakya
    Theoretical Computer Science (TCS), Jun 12, 2021; pp 874:15-31.
    Abstract and Full Paper

    We study the parameterized complexity of the OPTIMAL-DEFENSE and OPTIMAL-ATTACK problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers \(k_a\) and \(k_d\) corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the OPTIMAL-DEFENSE problem, we want to know if it is possible for the defender to commit to a strategy of defending at most \(k_d\) voter groups such that, no matter which \(k_a\) voter groups the attacker attacks, the outcome of the election does not change. In the OPTIMAL-ATTACK problem, we want to know if it is possible for the attacker to commit to a strategy of attacking \(k_a\) voter groups such that, no matter which \(k_d\) voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the OPTIMAL-DEFENSE problem and the OPTIMAL-ATTACK problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only \(3\) candidates. We also show that the OPTIMAL-DEFENSE problem for every scoring rule and the Condorcet voting rule is \(W[2]-hard\) for both the parameters \(k_a\) and \(k_d\), while it admits a fixed parameter tractable algorithm parameterized by the combined parameter \((k_a,k_d)\). The OPTIMAL-ATTACK problem for every scoring rule and the Condorcet voting rule turns out to be much harder -- it is \(W[1]-hard\) even for the combined parameter \((k_a,k_d)\). We propose two greedy algorithms for the OPTIMAL-DEFENSE problem and empirically show that they perform effectively on reasonable voting profiles.

    [PDF] [Journal Link]


  5. Preference Elicitation For Participatory Budgeting
    Gerdus Benadè, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah
    Management Science (MS) 67(5), pp 2813-2827, Sep 23, 2020.
    Abstract and Full Paper

    Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable real-world impact. But making the most of this new paradigm requires arethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We analytically compare four preference elicitation methods -- knapsack votes, rankings by value or value for money, and threshold approval votes -- through the lens ofimplicit utilitarian voting, and find that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections.

    [PDF] [Journal Link]


  6. Efficiency and Budget Balance in General Quasi-linear Domains
    Swaprava Nath and Tuomas Sandholm
    Games and Economic Behavior (GEB), Volume 113, 2019, pp. 673-693.
    Abstract and Full Paper

    We study efficiency and budget balance in mechanism design in the quasi-linear domain. Green and Laffont [1979] proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budget-balanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is given the payments made by the other agents. We assume the valuations of the agents are drawn from a bounded open interval. This result strengthens Green and Laffont’s impossibility result by showing that even in a restricted domain of valuations, there does not exist a mechanism that is strategyproof, budget balanced, and takes every agent’s valuation into consideration -- a corollary of which is that it cannot be efficient. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears when the number of agents is large -- a result close in spirit to Green and Laffont [1979, Theorem 9.4]. However, our results provide worst-case bounds and the best possible rate of convergence.
    Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that no deterministic mechanism can do asymptotically better than minimizing inefficiency alone.
    Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budget-balanced, randomized mechanisms. We also use an optimization-based approach --in the spirit of automated mechanism design-- to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism.
    Experiments with real data from two applications show that the inefficiency for a simple randomized mechanism is 5--100 times smaller than the worst case. This relative difference increases with the number of agents.

    [PDF] [Journal Link] [code]


  7. Separability and Decomposition in Mechanism Design with Transfers
    Debasis Mishra, Swaprava Nath, and Souvik Roy
    Games and Economic Behavior (GEB), Volume 109, 2018, pp 240-261.
    Abstract and Full Paper

    In private values quasi-linear environment, we consider problems where allocation decisions along multiple components have to be made. Every agent has additively separable valuation over the components. We show that every neutral and dominant strategy implementable allocation rule in this problem is a neutral component affine maximizer, which assigns non-negative weight vectors to agents in each component and chooses an alternative in each component by maximizing the weighted sum of valuations in that component. A corollary of our result is that every neutral and dominant strategy implementable allocation rule can be almost decomposed (modulo tie-breaking) into dominant strategy implementable allocation rules along each component.

    [PDF] [Journal Link]


  8. Subset Selection Via Implicit Utilitarian Voting
    Ioannis Caragiannis, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
    Journal of Artificial Intelligence Research (JAIR), Volume 58, 2017, pp 123-152.
    Abstract and Full Paper

    How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach -- which we refer to as implicit utilitarian voting -- assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of an upcoming social choice website.

    [PDF] [Journal Link]


  9. Dynamic Mechanism Design with Interdependent Valuations
    Swaprava Nath, Onno Zoeter, Y. Narahari, and Chris Dance
    Review of Economic Design (ROED), 19(3), 2015, pp 211-228.
    Abstract and Full Paper

    We consider an infinite horizon dynamic mechanism design problem with interdependent valuations. In this setting the types of the agents are assumed to be evolving according to a first order Markov process and the types are independent across agents in every round and across rounds. However, the valuations of the agents are functions of the types of all the agents, which makes the problem fall into an interdependent value model. Designing mechanisms in this setting is non-trivial in view of an impossibility result which says that for interdependent valuations, any efficient and ex-post incentive compatible mechanism must be a constant mechanism, even if the mechanism is static. Mezzetti circumvents this problem by splitting the decisions of allocation and payment into two stages. However, Mezzetti's result is limited to static setting and moreover in the second stage of that mechanism, agents are weakly indifferent about reporting their valuations truthfully. This paper provides a first attempt at designing a dynamic mechanism which is strict ex-post incentive compatible and efficient in interdependent value setting with Markovian type evolution. In a restricted domain, which appears often in real-world scenarios, we show that our mechanism is ex-post individually rational as well.

    [PDF] [Journal Link]


  10. Affine Maximizers in Domains with Selfish Valuations
    Swaprava Nath and Arunava Sen
    ACM Transactions on Economics and Computation (ACM-TEAC), 3(4), 2015, article 26, pp 26:1-19.
    Abstract and Full Paper

    We consider the domain of selfish and continuous preferences over a "rich" allocation space and show that onto, strategyproof and non-bossy social choice functions are affine maximizers. Roberts (1979) proves this result for a finite set of alternatives and an unrestricted valuation space. In this paper, we show that in a sub-domain of the unrestricted valuations with the additional assumption of non-bossiness, using the richness of the allocations, the strategyproof social choice functions can be shown to be affine maximizers. This work serves as an example that an affine maximizer result needs certain amount of richness split across valuations and allocations.

    [PDF] [Journal Link]


  11. A Strict Ex-post Incentive Compatible Mechanism for Interdependent Valuations
    Swaprava Nath and Onno Zoeter
    Economics Letters, 121(2), 2013, pp 321-325.
    Abstract and Full Paper

    The impossibility result by Jehiel and Moldovanu says that in a setting with interdependent valuations, any efficient and ex-post incentive compatible mechanism must be a constant mechanism. Mezzetti circumvents this problem by designing a two stage mechanism where the decision of allocation and payment are split over the two stages. This mechanism is elegant, however keeps a major weakness. In the second stage, agents are weakly indifferent about reporting their valuations truthfully: an agent's payment is independent of her reported valuation and truthtelling for this stage is by assumption. We propose a modified mechanism which makes truthful reporting in the second stage a strict equilibrium.

    [PDF] [Journal Link]


  12. Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks
    Swaprava Nath, Venkatesan N. E., Anurag Kumar, and P. Vijay Kumar
    ACM Transactions on Sensor Networks (ACM-TOSN), 8(4), 2012, pp 35:1-38.
    Abstract and Full Paper

    Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function.
    Localization algorithms that draw upon the above analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

    [PDF] [Journal Link]


Conference and Workshop

  1. Optimal Referral Auction Design
    Rangeet Bhattacharyya, Parvik Dave, Palash Dey, and Swaprava Nath
    Autonomous Agents and Multiagent Systems (AAMAS), May 2024, to appear.
    Abstract and Full Paper

    The auction of a single indivisible item is one of the most celebrated problems in mechanism design with transfers. Despite its simplicity, it provides arguably the cleanest and most insightful results in the literature. When the information that the auction is running is available to every participant, Myerson [20] provided a seminal result to characterize the incentive-compatible auctions along with revenue optimality. However, such a result does not hold in an auction on a network, where the information of the auction is spread via the agents, and they need incentives to forward the information. In recent times, a few auctions (e.g., [13, 18]) were designed that appropriately incentivized the intermediate nodes on the network to promulgate the information to potentially more valuable bidders. In this paper, we provide a Myerson-like characterization of incentive-compatible auctions on a network and show that the currently known auctions fall within this class of randomized auctions. We then consider a special class called the referral auctions that are inspired by the multi-level marketing mechanisms [1, 6, 7] and obtain the structure of a revenue optimal referral auction for i.i.d. bidders. Through experiments, we show that even for non-i.i.d. bidders there exist auctions following this characterization that can provide a higher revenue than the currently known auctions on networks.

    [Full paper] [AAMAS version]


  2. Charging Electric Vehicles Fairly and Efficiently
    Ramsundar Anandanarayanan, Swaprava Nath, and Rohit Vaish
    Autonomous Agents and Multiagent Systems (AAMAS), May 2024, to appear. (extended abstract)
    Abstract and Full Paper

    Motivated by electric vehicle (EV) charging, we formulate the problem of fair and efficient allocation of a divisible resource among agents that arrive and depart over time and consume the resource at different rates. The agents (i.e., the EVs) derive utility from the amount of charge gained, which depends on their own charging rate as well as that of the charging outlet. The goal is to allocate charging time at different outlets among the EVs such that the final allocation is envy-free, Pareto optimal, and in certain contexts, group-strategyproof. The differences in the charging rates of the outlets and the EVs, and a continuous time-window where the arrivals and departures occur make this a non-trivial combinatorial optimization problem. We show possibilities and impossibilities of achieving a combination of properties such as envy-freeness, Pareto optimality, leximin, and group-strategyproofness under different operational settings, e.g., when the EVs have (dis)similar charging technology, or when there are one or more dissimilar charging outlets. We complement the positive existence results with polynomial-time algorithms.

    [PDF]


  3. Fair Scheduling of Indivisible Chores
    Yatharth Kumar, Sarfaraz Equbal, Rohit Gurjar, Swaprava Nath and Rohit Vaish
    Autonomous Agents and Multiagent Systems (AAMAS), May 2024, to appear. (extended abstract)
    Abstract and Full Paper

    We study the problem of fairly assigning a set of discrete tasks (or chores) among a set of agents with additive valuations. Each chore is associated with an arrival time and a deadline, and each agent can perform at most one chore at any given time. The goal is to find a fair and efficient schedule of the chores, where fairness pertains to satisfying envy-freeness up to one chore (EF1) and efficiency pertains to maximality (i.e., no unallocated chore can be feasibly assigned to any agent). Our main result is a polynomial-time algorithm for computing an EF1 and maximal schedule for two agents under monotone valuations when the conflict constraints constitute an arbitrary interval graph. The algorithm uses a coloring technique in interval graphs that may be of independent interest. For an arbitrary number of agents, we provide an algorithm for finding a fair schedule under identical dichotomous valuations when the constraints constitute a path graph. We also rule out the existence of schedules satisfying stronger fairness and efficiency properties, including envy-freeness up to any chore (EFX) together with maximality and EF1 together with Pareto optimality.



  4. Truthful and Fair Lateral Transshipment in Multi-Retailer Systems
    Garima Shakya, Sai Koti Reddy Danda, Swaprava Nath, and Pankaj Dayama
    European Conference on Artificial Intelligence (ECAI), 2023, pp. 2113-2120.
    Abstract and Full Paper

    We consider a multi-retailer system where the sellers are connected with each other over a network and the transactions with the consumers happen on a platform. Since the demands and supplies to the sellers (e.g., the retailers on the platform) are stochastic in nature, supplies can be either in excess or in deficit. Lateral transshipment of such products is beneficial for the retailers since otherwise, the excess supply leads to wastage and the deficit in bad reputation. Only the sellers know their excess (which can be salvaged at a price or transshipped to another seller) and the deficit (which can be directly procured from a supplier or transshipped from another seller), both of which have information that is private. We propose a model that allows the lateral transshipment at a price and design mechanisms such that the sellers are incentivized to voluntarily participate and be truthful. Experimenting on different types of network topologies, we find that the sellers who are at more central locations in the network get an unfair advantage in the classical mechanism that aims for economic efficiency. We, therefore, propose a modified mechanism with tunable parameters which can ensure that the mechanism is more equitable for non-central retailers. Our synthetic data experiments show that such mechanisms do not compromise too much on efficiency, and also reduce budget imbalance.

    [PDF]


  5. Disentangling Societal Inequality from Model Biases: Gender Inequality in Divorce Court Proceedings
    Sujan Dutta, Parth Srivastava, Vaishnavi Solunke, Swaprava Nath, and Ashiqur R. KhudaBukhsh
    International Joint Conference on Artificial Intelligence (IJCAI), 2023, pp. 5959-5967.
    Abstract and Full Paper

    Divorce is the legal dissolution of a marriage by a court. Since this is usually an unpleasant outcome of a marital union, each party may have reasons to call the decision to quit which is generally documented in detail in the court proceedings. Via a substantial corpus of 17,306 court proceedings, this paper investigates gender inequality through the lens of divorce court proceedings. While emerging data sources (e.g., public court records) on sensitive societal issues hold promise in aiding social science research, biases present in cutting-edge natural language processing (NLP) methods may interfere with or affect such studies. We thus require a thorough analysis of potential gaps and limitations present in extant NLP resources. In this paper, on the methodological side, we demonstrate that existing NLP resources required several non-trivial modifications to quantify societal inequalities. On the substantive side, we find that while a large number of court cases perhaps suggest changing norms in India where women are increasingly challenging patriarchy, AI-powered analyses of these court proceedings indicate striking gender inequality with women often subjected to domestic violence.

    [PDF]


  6. Social Distancing via Social Scheduling
    Deepesh Kumar Lall, Garima Shakya, and Swaprava Nath
    Autonomous Agents and Multiagent Systems (AAMAS), May 2023, pp. 1858-1866.
    Abstract and Full Paper

    Motivated by the need for social distancing during a pandemic, we consider an approach to schedule the visitors of a facility. The algorithm takes input from citizens and schedules the time-slots of the store them based on their importance to visit the facility (e.g., a general store). Naturally, the formulation applies to several similar problems. We consider the single slot and multiple slot demand of the requests. The salient properties of our approach are: it (a) ensures social distancing by ensuring a maximum population in a given time-slot at the facility, (b) prioritizes individuals who mark their work as important, (c) maintains truthfulness of the reported importance by adding a cooling off period after their allocated time-slot, during which the individual cannot access the same facility again, (d) guarantees voluntary participation of the citizens, and yet (e) is computationally tractable. We show that the problem becomes NP-complete as soon as the multi-slot demands are indivisible, and provide a polynomial-time mechanism that is truthful, individually rational, and approximately optimal. Experiments show that visitors with more important jobs are allocated more preferred slots, which comes at the cost of a longer delay to re-access the store. We show that it reduces the social congestion significantly using users' visit data from a store. For the multi-slot indivisible jobs, our mechanism yields reasonable approximation while reducing the computation time significantly.

    [PDF] [code and data (academic use only)]


  7. OMCoRP: An Online Mechanism for Competitive Robot Prioritization
    Sankar Das, Swaprava Nath, and Indranil Saha
    International Conference on Automated Planning and Scheduling (ICAPS), May 17, 2021, Vol. 31, pp 112-121.
    Abstract and Full Paper

    We propose a collision-avoiding mechanism for a group of robots moving on a shared workspace. Existing algorithms solve this problem either (a) in an offline manner using the source-destination information of all the robots or (b) in an online manner with cooperative robots. We take a paradigm shift to the setting with competitive robots, that may strategically reveal their urgency of reaching the destinations and design online mechanisms that take decisions on-the-fly, reducing the overhead of an offline planning. We propose a mechanism OMCoRP in this setting that ensures truthful revelation of the robots' priorities using principles of economic theory and provides locally efficient movement of the robots. It is free from collisions and deadlocks, and handles dynamic arrival of robots. In practice, this mechanism gives a smaller delay for robots of higher priority and scales well for a large number of robots without compromising on the path optimality too much.

    [PDF] [Presentation video (10 min)]


  8. SkillCheck: An Incentive-based Certification System using Blockchains
    Jay Gupta and Swaprava Nath
    IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 3-6 May, 2020, Toronto, Canada, pp 1-3.
    Abstract and Full Paper

    Skill verification is a central problem in workforce hiring. Companies and academia often face the difficulty of ascertaining the skills of an applicant since the certifications of the skills claimed by a candidate are generally not immediately verifiable and costly to test. Blockchains have been proposed in the literature for skill verification and tamper-proof information storage in a decentralized manner. However, most of these approaches deal with storing the certificates issued by traditional universities on the blockchain. Among the few techniques that consider the certification procedure itself, questions like (a) scalability with limited staff, (b) uniformity of grades over multiple evaluators, or (c) honest effort extraction from the evaluators are usually not addressed. We propose a blockchain-based platform named SkillCheck, which considers the questions above, and ensure several desirable properties. The platform incentivizes effort in grading via payments with tokens which it generates from the payments of the users of the platform, e.g., the recruiters and test takers. We provide a detailed description of the design of the platform along with the provable properties of the algorithm.

    [PDF]


  9. SwaGrader: An Honest Effort Extracting, Modular Peer-Grading Tool
    Somu Prajapati, Ayushi Gupta, Shubham Kumar Nigam, and Swaprava Nath
    ACM IKDD Joint International Conference on Data Science & Management of Data (CoDS-COMAD), 2020, pp. 312-316.
    Abstract and Full Paper

    Massive open online courses pose a massive challenge for grading the answer scripts at a high accuracy. Peer grading is often viewed as a scalable solution to this challenge, which largely depends on the altruism of the peer graders. In this paper, we propose to demonstrate a tool designed for strategic peer-grading with the help of a structured and typical grading workflow. SwaGrader, a modular, secure and customizable (to any grading workflow) peer- grading tool enables the instructor to handle large courses (MOOCs and offline) with limited participation by teaching staff via a web- based application (extensible to any front-end framework based application) and a mechanism called TRUPEQA. TRUPEQA (a) uses a constant number of instructor-graded answer-scripts to quantitatively measure the accuracies of the peer graders and corrects the scores accordingly, and (b) penalizes deliberate underperforming. We show that this mechanism is unique in its class to satisfy certain properties. Our human subject experiments show that TRUPEQA improves the grading quality over the mechanisms currently used in standard MOOCs. Our mechanism outperforms several standard peer grading techniques used in practice, even at times when the graders are non-manipulative.

    [PDF]


  10. A Parameterized Perspective on Protecting Elections
    Palash Dey, Neeldhara Misra, Swaprava Nath, and Garima Shakya
    International Joint Conference on Artificial Intelligence (IJCAI), 2019, pp 238-244.
    Abstract and Full Paper

    We study the parameterized complexity of the OPTIMAL-DEFENSE and OPTIMAL-ATTACK problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers \(k_a\) and \(k_d\) corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the OPTIMAL-DEFENSE problem, we want to know if it is possible for the defender to commit to a strategy of defending at most \(k_d\) voter groups such that, no matter which \(k_a\) voter groups the attacker attacks, the outcome of the election does not change. In the OPTIMAL-ATTACK problem, we want to know if it is possible for the attacker to commit to a strategy of attacking \(k_a\) voter groups such that, no matter which \(k_d\) voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the OPTIMAL-DEFENSE problem and the OPTIMAL-ATTACK problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only \(3\) candidates. We also show that the OPTIMAL-DEFENSE problem for every scoring rule and the Condorcet voting rule is \(W[2]-hard\) for both the parameters \(k_a\) and \(k_d\), while it admits a fixed parameter tractable algorithm parameterized by the combined parameter \((k_a,k_d)\). The OPTIMAL-ATTACK problem for every scoring rule and the Condorcet voting rule turns out to be much harder -- it is \(W[1]-hard\) even for the combined parameter \((k_a,k_d)\). We propose two greedy algorithms for the OPTIMAL-DEFENSE problem and empirically show that they perform effectively on reasonable voting profiles.

    [PDF]


  11. Testing Preferential Domains Using Sampling
    Palash Dey, Swaprava Nath, and Garima Shakya
    International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019, pp 855-863.
    Abstract and Full Paper

    A preferential domain is a collection of sets of preferences which are linear orders over a set of alternatives. These domains have been studied extensively in social choice theory due to both its practical importance and theoretical elegance. Examples of some extensively studied preferential domains include single peaked, single crossing, Euclidean, etc. In this paper, we study the sample complexity of testing whether a given preference profile is close to some specific domain. We consider two notions of closeness: (a) closeness via preferences, and (b) closeness via alternatives. We further explore the effect of assuming that the outlier preferences/alternatives to be random (instead of arbitrary) on the sample complexity of the testing problem. In most cases, we show that the above testing problem can be solved with high probability for all commonly used domains by observing only a small number of samples (independent of the number of preferences, \(n\), and often the number of alternatives, \(m\)). In the remaining few cases, we prove either impossibility results or \(\Omega(n)\) lower bound on the sample complexity. We complement our theoretical findings with extensive simulations to figure out the actual constant factors of our asymptotic sample complexity bounds.

    [PDF]


  12. The Social Network Effect on Surprise in Elections
    Palash Dey, Pravesh K. Kothari, and Swaprava Nath
    ACM IKDD Joint International Conference on Data Science & Management of Data (CoDS-COMAD), pp. 1-9, ACM, 2019 [finalist for the best paper]. [Press coverage]
    Abstract and Full Paper

    Elections involving a very large voter population often lead to outcomes that surprise many. This is particularly important for the elections in which results affect the economy of a sizable population. A better prediction of the true outcome helps reduce the surprise (or shock) and keeps the voters prepared. This paper starts from the basic observation that individuals in the underlying population build estimates of the distribution of preferences of the whole population based on their local neighborhoods. The outcome of the election leads to a surprise/shock if these local estimates contradict the outcome of the election for some fixed voting rule. To get a quantitative understanding, we propose a simple mathematical model of the setting where the individuals in the population and their connections (through geographical proximity, social networks etc.) are described by a random graph with connection probabilities that are biased based on the preferences of the individuals. Each individual also has some estimate of the bias in their connections.
    We show that the election outcome leads to a surprise if the discrepancy between the estimated bias and the true bias in the local connections exceeds a certain threshold, and confirm the phenomenon that surprising outcomes are associated only with closely contested elections. We compare standard voting rules based on their performance on surprise and show that they have different behavior for different parts of the population. It also hints at an impossibility that a single voting rule will be less surprising for all parts of a population. Finally, we experiment with the UK-EU referendum (a.k.a. Brexit) dataset to see a real-world effect of estimation errors on surprise.

    [Full paper] [Conf ver]


  13. Truthful Mechanisms for Ownership Transfer with Expert Advice
    Ioannis Caragiannis, Aris Filos-Ratsikas, Swaprava Nath, and Alexandros A. Voudouris
    Workshop on Opinion Aggregation, Dynamics, and Elicitation (WADE)
    In conjunction with ACM Conference on Economics and Computation (EC), 2018.

    Abstract and Full Paper

    When a company undergoes a merger or transfer of its ownership, the existing governing body has an opinion on which buyer should take over as the new owner. Similar situations occur while assigning the host of big sports tournaments, e.g., the World Cup or the Olympics. In all these settings, the values of the external bidders are as important as the internal experts' opinions. Motivated by such questions, we consider a social welfare maximizing approach to design and analyze truthful mechanisms in these settings. We consider the problem with one expert and two bidders and provide tight approximation guarantees of the optimal social welfare. Since this problem is a combination of mechanism design with and without monetary transfers (payments can be imposed to the bidders but not to the expert), classical solutions like VCG cannot be applied, making this a unique mechanism design problem. We distinguish between mechanisms that use ordinal and cardinal information, as well as between mechanisms that base their decisions on one of the two sides (either the bidders or the expert) or both. Our analysis shows that the cardinal setting is quite rich and admits several non-trivial randomized truthful mechanisms, and also allows for closer-to-optimal-welfare guarantees.

    [PDF]


  14. A Game-Theoretic Formalism of Human Partial Adaptation: Models and Experiments
    Stefanos Nikolaidis, Swaprava Nath, Ariel Procaccia, and Siddhartha Srinivasa
    ACM/IEEE International Conference on Human-Robot Interaction (HRI), pp. 323-331. ACM, 2017.
    Abstract and Full Paper

    In human-robot collaborative tasks, humans often start with an inaccurate model of the robot capabilities. They then make inferences on what the robot can and cannot do through interaction, and update their strategy accordingly. This paper presents a game-theoretic formalism for human partial adaptation to the robot, which captures the evolution of the human strategy over time, as the human partner observes the outcome of the robot and their actions. The model allows the robot to reason in a probabilistic sense over how the human actions will change based on its own actions, and compute a policy that optimizes the tradeoff between conveying information to the human and maximizing the team payoff. We formally prove that under certain observability assumptions on the human state, the policy computation can be done very efficiently. Human subject experiment indicate that the proposed formalism can significantly improve human-robot team performance, compared to policies that assume complete adaptation of the human to the robot.

    [PDF]


  15. Preference Elicitation For Participatory Budgeting
    Gerdus Benade, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
    Association for Advancement of Artificial Intelligence (AAAI), pp. 376-382, 2017.
    Abstract and Full Paper

    Participatory budgeting enables the allocation of public funds by collecting and aggregating individual preferences; it has already had a sizable real-world impact. But making the most of this new paradigm requires a rethinking of some of the basics of computational social choice, including the very way in which individuals express their preferences. We analytically compare four preference elicitation methods -- knapsack votes, rankings by value or value for money, and threshold approval votes -- through the lens of implicit utilitarian voting, and find that threshold approval votes are qualitatively superior. This conclusion is supported by experiments using data from real participatory budgeting elections

    [PDF]


  16. Efficiency and Budget Balance
    Swaprava Nath and Tuomas Sandholm
    Web and Internet Economics (WINE), pp. 369-383, 2016.
    Abstract and Full Paper

    We study efficiency and budget balance in mechanism design in the quasi-linear domain. Green and Laffont [1979] proved that one cannot generically achieve both. We consider strategyproof budget-balanced mechanisms that are approximately efficient. For deterministic mechanisms, we show that a strategyproof and budget-balanced mechanism must have a sink agent whose valuation function is ignored in selecting an alternative, and she is given the payments made by the other agents. We assume the valuations of the agents are drawn from a bounded open interval. This result strengthens Green and Laffont’s impossibility result by showing that even in a restricted domain of valuations, there does not exist a mechanism that is strategyproof, budget balanced, and takes every agent’s valuation into consideration -- a corollary of which is that it cannot be efficient. Using this result, we find a tight lower bound on the inefficiencies of strategyproof, budget-balanced mechanisms in this domain. The bound shows that the inefficiency asymptotically disappears when the number of agents is large -- a result close in spirit to Green and Laffont [1979, Theorem 9.4]. However, our results provide worst-case bounds and the best possible rate of convergence.
    Next, we consider minimizing any convex combination of inefficiency and budget imbalance. We show that no deterministic mechanism can do asymptotically better than minimizing inefficiency alone.
    Finally, we investigate randomized mechanisms and provide improved lower bounds on expected inefficiency. We give a tight lower bound for an interesting class of strategyproof, budget-balanced, randomized mechanisms. We also use an optimization-based approach --in the spirit of automated mechanism design-- to provide a lower bound on the minimum achievable inefficiency of any randomized mechanism.

    [PDF] [code]


  17. Subset Selection Via Implicit Utilitarian Voting
    Ioannis Caragiannis, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
    International Joint Conference on Artificial Intelligence (IJCAI), July 9-15, 2016, New York, USA.
    Abstract and Full Paper

    How should one aggregate ordinal preferences expressed by voters into a measurably superior social choice? A well-established approach -- which we refer to as implicit utilitarian voting -- assumes that voters have latent utility functions that induce the reported rankings, and seeks voting rules that approximately maximize utilitarian social welfare. We extend this approach to the design of rules that select a subset of alternatives. We derive analytical bounds on the performance of optimal (deterministic as well as randomized) rules in terms of two measures, distortion and regret. Empirical results show that regret-based rules are more compelling than distortion-based rules, leading us to focus on developing a scalable implementation for the optimal (deterministic) regret-based rule. Our methods underlie the design and implementation of an upcoming social choice website.

    [PDF]


  18. Productive Output in Hierarchical Crowdsourcing
    Swaprava Nath and Balakrishnan Narayanaswamy
    Autonomous Agents and Multi-Agent Systems (AAMAS), May 5-9, 2014, Paris, France, pp 469-476.
    Abstract and Full Paper

    Organically grown crowdsourcing networks, which includes production firms and social network based crowdsourcing applications, tend to have a hierarchical structure. Considering the entire crowdsourcing system as a consolidated organization, a primary goal of a designer is to maximize the net productive output of this hierarchy using reward sharing as an incentive tool. Every individual in a hierarchy has a limited amount of effort that they can split between production and communication. Productive effort yields an agent a direct payoff, while the communication effort of an agent improves the productivity of other agents in her subtree. To understand how the net output of the crowdsourcing network is influenced by these components, we develop a game theoretic model that helps explain how the individuals trade off these two components depending on their position in the hierarchy and their shares of reward. We provide a detailed analysis of the Nash equilibrium efforts and a design recipe of the reward sharing scheme that maximizes the net productive output. Our results show that even under strategic behavior of the agents, it is sometimes possible to achieve the optimal output and also provide bounds on the achievability when this is not the case.

    [PDF]


  19. A Mechanism to Optimally Balance Cost and Quality of Labeling Tasks Outsourced to Strategic Agents
    Satyanath Bhat, Swaprava Nath, Onno Zoeter, Sujit Gujar, Y. Narahari, and Chris Dance
    Autonomous Agents and Multi-Agent Systems (AAMAS), May 5-9, 2014, Paris, France, pp 917-924.
    Abstract and Full Paper

    We consider a class of crowdsourcing problems where the owner of a task benefits from the high quality opinions provided by experts. Executing the task at an assured quality level in a cost effective manner in such situations becomes a mechanism design problem when the individual qualities are private information of the experts. The considered class of task execution problems falls into the category of interdependent values, where one cannot simultaneously achieve truthfulness and efficiency in the unrestricted setting due to an impossibility result (Jehiel and Moldovanu, 2001). We propose a mechanism QUEST, that leverages the structure of our special class of problems and guarantees allocative efficiency, ex-post incentive compatibility, ex-post individual rationality, and strict budget balance, which even the mechanism given by Mezzetti (2004) cannot achieve in this setting. The ex-post individual rationality comes under a tight sufficiency condition, and we show that the above four properties are not simultaneously satisfiable if the sufficient condition is violated. To the best of our knowledge, this is the first attempt in developing a quality assuring crowdsourcing mechanism in an interdependent value setting with quality levels held private by strategic agents.

    [PDF]


  20. On Profit Sharing and Hierarchies in Organizations
    Swaprava Nath, Balakrishnan Narayanaswamy, Kundan Kandhway, Bhushan Kotnis, and David C. Parkes
    Asian Meeting of the Econometric Society (AMES), December 20-22, 2012, New Delhi, India, paper 119, pp 1-19.
    Abstract and Full Paper

    We study the effect of hierarchies on the performance of an organization that exhibits both profit sharing and information sharing. We adopt a server-queue model of effort and intra-organizational competition and quantify the performance of an organization in terms of the overall efficiency and risk in meeting target production levels. On the one hand, we show that profit sharing leads to free riding at the Nash equilibrium and reduces overall effort. Introducing a form of information asymmetry, we then quantitatively establish the trade-off between free riding and the positive effects of information sharing in hierarchies. We formulate an optimal hierarchy design problem that captures both effects, and provide a simple algorithm that gives near optimal designs. We provide an analysis of the productive value of optimized hierarchies, considering their ability to attain target production levels with low risk.

    [PDF]


  21. Mechanism Design for Time Critical and Cost Critical Task Execution via Crowdsourcing
    Swaprava Nath, Pankaj Dayama, Dinesh Garg, Y. Narahari, and James Zou
    Web and Internet Economics (WINE), December 9 - 12, 2012, Liverpool, UK, pp 212-226.
    Abstract and Full Paper

    In recent times, crowdsourcing over social networks has emerged as an active tool for complex task execution. In this paper, we address the problem faced by a planner to incentivize agents in the network to execute a task and also help in recruiting other agents for this purpose. We study this mechanism design problem under two natural resource optimization settings: (1) cost critical tasks, where the planner's goal is to minimize the total cost, and (2) time critical tasks, where the goal is to minimize the total time elapsed before the task is executed. We define a set of fairness properties that should be ideally satisfied by a crowdsourcing mechanism. We prove that no mechanism can satisfy all these properties simultaneously. We relax some of these properties and define their approximate counterparts. Under appropriate approximate fairness criteria, we obtain a non-trivial family of payment mechanisms. Moreover, we provide precise characterizations of cost critical and time critical mechanisms.

    [PDF] [slides]


  22. Threats and Trade-offs in Resource Critical Crowdsourcing Tasks over Networks (student abstract)
    Swaprava Nath, Pankaj Dayama, Dinesh Garg, Y. Narahari, and James Zou
    Conference of the Association for Advancement Artificial Intelligence (AAAI), July 22-26, 2012, Toronto, Canada, pp 2447-2448.
    [PDF]

  23. Dynamic Mechanism Design for Markets with Strategic Resources
    Swaprava Nath, Onno Zoeter, Y. Narahari, and Chris Dance
    Conference on Uncertainty in Artificial Intelligence (UAI), July 14-17, 2011, Barcelona, Spain, pp 539-546.
    Abstract and Full Paper

    The assignment of tasks to multiple resources becomes an interesting game theoretic problem, when both the task owner and the resources are strategic. In the classical, non-strategic setting, where the states of the tasks and resources are observable by the controller, this problem is that of finding an optimal policy for a Markov decision process (MDP). When the states are held by strategic agents, the problem of an efficient task allocation extends beyond that of solving an MDP and becomes that of designing a mechanism. Motivated by this fact, we propose a general mechanism which decides on an allocation rule for the tasks and resources and a payment rule to incentivize agents' participation and truthful reports.
    In contrast to related dynamic strategic control problems studied in recent literature, the problem studied here has interdependent values: the benefit of an allocation to the task owner is not simply a function of the characteristics of the task itself and the allocation, but also of the state of the resources. We introduce a dynamic extension of Mezzetti's two phase mechanism for interdependent valuations. In this changed setting, the proposed dynamic mechanism is efficient, within period ex-post incentive compatible, and within period ex-post individually rational. It has, perhaps surprisingly, a computation time that is of the same order as of the non-strategic equivalent.
    We demonstrate the effectiveness of the approach with simulations, and observe that certain socially desirable properties may not be simultaneously satisfiable.

    [PDF] [slides]


  24. Dynamic Learning-based Mechanism Design for Dependent Valued Exchange Economies (PhD proposal)
    Swaprava Nath
    International World Wide Web Conference (WWW), March 28 - April 1, 2011, Hyderabad, India, pp 397-402.
    Abstract and Full Paper

    Learning private information from multiple strategic agents poses challenge in many Internet applications. Sponsored search auctions, crowdsourcing, Amazon’s mechanical turk, various online review forums are examples where we are interested in learning true values of the advertisers or true opinion of the reviewers. The common thread in these decision problems is that the optimal outcome depends on the private information of all the agents, while the decision of the outcome can be chosen only through reported information which may be manipulated by the strategic agents. The other important trait of these applications is their dynamic nature. The advertisers in an online auction or the users of mechanical turk arrive and depart, and when present, interact with the system repeatedly, giving the opportunity to learn their types. Dynamic mechanisms, which learn from the past interactions and make present decisions depending on the expected future evolution of the game, has been shown to improve performance over repeated versions of static mechanisms. In this paper, we will survey the past and current state-of-the-art dynamic mechanisms and analyze a new setting where the agents consist of buyers and sellers, known as exchange economies, and agents having value interdependency, which are relevant in applications illustrated through examples. We show that known results of dynamic mechanisms with independent value settings cannot guarantee certain desirable properties in this new significantly different setting. In the future work, we propose to analyze similar settings with dynamic types and population.

    [PDF]


  25. Performance Evaluation of Distance-Hop Proportionality on Geometric Graph Models of Dense Sensor Network
    Swaprava Nath and Anurag Kumar
    International Conference on Performance EVALUation MEthodologies and TOOLS (VALUETOOLS), October 21-23, 2008, Athens, Greece, pp 4247:1-10.
    Abstract and Full Paper

    Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes on a region in Euclidean space, e.g., the unit square. After deployment, the nodes self-organise into a mesh topology. In a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this paper, we analyse the performance of this approximation. We show that nodes with a certain hop distance from a fixed anchor node lie within a certain annulus with probability approaching unity as the number of nodes n → ∞.
    We take a uniform, i.i.d. deployment of n nodes on a unit square, and consider the geometric graph on these nodes with radius r(n) = c√1n n/n. We show that, for a given hop distance h of a node from a fixed anchor on the unit square, the Euclidean distance lies within [(1-ε)(h-1)r(n), hr(n)], for ε > 0, with probability approaching unity as n → ∞. This result shows that it is more likely to expect a node, with hop distance h from the anchor, to lie within this annulus centred at the anchor location, and of width roughly r(n), which decreases as n increases. We show that if the radius r of the geometric graph is fixed, the convergence of the probability is exponentially fast. Similar results hold for a randomised lattice deployment. We provide simulation results that illustrate the theory, and serve to show how large n needs to be for the asymptotics to be useful.

    [PDF] [slides]


  26. Linear Antenna Array with Suppressed Sidelobe and Sideband Levels using Time Modulation
    Swaprava Nath and Subrata Mitra
    International Conference On Computers And Devices For Communication (CODEC), December 2006, Kolkata, India.
    Abstract and Full Paper

    In this paper, the goal is to achieve an ultra low sidelobe level (SLL) and sideband levels (SBL) of a time modulated linear antenna array. The approach followed here is not to give fixed level of excitation to the elements of an array, but to change it dynamically with time. The excitation levels of the different array elements over time are varied to get the low sidelobe and sideband levels. The mathematics of getting the SLL and SBL furnished in detail and simulation is done using the mathematical results. The excitation pattern over time is optimized using Genetic Algorithm (GA). Since, the amplitudes of the excitations of the elements are varied within a finite limit, results show it gives better sidelobe and sideband suppression compared to previous time modulated arrays with uniform amplitude excitations.

    [PDF]


Unpublished

  1. TruthBot: An Automated Conversational Tool for Intent Learning, Curated Information Presenting, and Fake News Alerting
    Ankur Gupta*, Yash Varun*, Prarthana Das*, Nithya Muttineni*, Parth Srivastava*, Hamim Zafar, Swaprava Nath, and Tanmoy Chakraborty (*equal contribution)
    Technical Report.
    Abstract and Full Paper

    We present TruthBot, an all-in-one multilingual conversational chatbot designed for seeking truth (trustworthy and verified information) on specific topics. It helps users to obtain information specific to certain topics, fact-check information, and get recent news. The chatbot learns the intent of a query by training a deep neural network from the data of the previous intents and responds appropriately when it classifies the intent in one of the classes above. Each class is implemented as a separate module which uses either its own curated knowledge-base or searches the web to obtain the correct information. The topic of the chatbot is currently set to COVID-19. However, the bot can be easily customized to any topic-specific responses. Our experimental results show that each module performs significantly better than its closest competitor, which is verified both quantitatively and through several user-based surveys in multiple languages. TruthBot has been deployed in June 2020 and is currently running.

    [PDF] [code and data (academic use only)] [official webpage] [press]


  2. Improving Productive Output in Influencer-Influencee Networks
    Swaprava Nath and Balakrishnan Narayanaswamy
    Technical Report.
    Abstract and Full Paper

    In social or organizational networks, it is often observed that different individuals put different levels of production effort depending on their position in the network. One possible reason is reward sharing, which incentivizes particular agents to spend effort in sharing information with others and increasing their productivity. We model the effort level in a network as a strategic decision made by an agent on how much effort to expend on the complementary tasks of information sharing and production. We conduct a game-theoretic analysis of incentive and information sharing in both hierarchical and general influencer-influencee networks. Our particular interest is in understanding how different reward structures in a network influence this decision. We establish the existence of a unique pure-strategy Nash equilibrium in regard to the choice made by each agent, and study the effect of the quality and cost of communication, and the reward sharing on the effort levels at this equilibrium. Our results show that a larger reward share from an influencee incentivizes the influencer to spend more effort, in equilibrium, on communication, capturing a free-riding behavior of well placed agents. We also address the reverse question of designing an optimal reward sharing scheme that achieves the effort profile which maximizes the system output. In this direction, for a number of stylized networks, we study the Price of Anarchy for this output, and the interplay between information and incentive sharing on mitigating the loss in output due to agent self-interest.

    [PDF]


Dissertation

  1. Mechanism Design for Strategic Crowdsourcing
    Swaprava Nath
    PhD Thesis, Indian Institute of Science, Bangalore
    December 2013.
    Advisor: Y. Narahari
    Abstract and Full Thesis

    This thesis looks into the economics of crowdsourcing using game theoretic modeling. The art of aggregating information and expertise from a diverse population has been in practice since a long time. The Internet and the revolution in communication and computational technologies have made this task easier and given birth to a new era of online resource aggregation, which is now popularly referred to as crowdsourcing. Two important features of this aggregation technique are: (a) crowdsourcing is always human driven, hence the participants are rational and intelligent, and they have a payoff function that they aim to maximize, and (b) the participants are connected over a social network which helps to reach out to a large set of individuals. To understand the behavior and the outcome of such a strategic crowd, we need to understand the economics of a crowdsourcing network. In this thesis, we have considered the following three major facets of the strategic crowdsourcing problem.
    (i) Elicitation of the true qualities of the crowd workers: As the crowd is often unstructured and unknown to the designer, it is important to ensure if the crowdsourced job is indeed performed at the highest quality, and this requires elicitation of the true qualities which are typically the participants' private information.
    (ii) Resource critical task execution ensuring the authenticity of both the information and the identity of the participants: Due to the diverse geographical, cultural, socio-economic reasons, crowdsourcing entails certain manipulations that are unusual in the classical theory. The design has to be robust enough to handle fake identities or incorrect information provided by the crowd while performing crowdsourcing contests.
    (iii) Improving the productive output of the crowdsourcing network: As the designer's goal is to maximize a certain measurable output of the crowdsourcing system, an interesting question is how one can design the incentive scheme and/or the network so that the system performs at an optimal level taking into account the strategic nature of the individuals. In the thesis, we design novel mechanisms to solve the problems above using game theoretic modeling. Our investigation helps in understanding certain limits of achievability, and provides design protocols in order to make crowdsourcing more reliable, effective, and productive.

    [PDF] [Slides] [Presentation Video]

  2. My small contribution towards a nicer IISc Thesis Format.

  3. Self Organisation in Random Geometric Graph models of Wireless Sensor Networks
    Swaprava Nath
    Masters Thesis, Indian Institute of Science, Bangalore
    June 2008.
    Advisor: Anurag Kumar
    Abstract and Full Thesis

    We consider the problem of self-organisation in dense wireless sensor networks. Wireless sensor networks can be viewed in terms of deployment of a large number of nodes in an Euclidean space. After deployment, the nodes are required to build a topology to communicate among themselves and also to a base station. In this process they should meet some performance criteria, e.g. coverage of the area to be monitored, connectivity of all the nodes in the network, the capacity of the wireless network, etc. Also, once an event is detected in the network, we need to localise the occurrence of the event with the information reaching the base station in an energy efficient way with minimum delay. These performance objectives are the issues addressed in self-organisation of wireless sensor networks (WSN).
    In this report, we first introduce the problem of self-organisation in general and then present a survey of the existing literature in this area. Later we formalise a very commonly used approximation of proportionality between the hop-distance (the minimum number of hops) and Euclidean distance for three different scenarios in dense networks. Our proofs bank on a certain geometric construction and union bound, and provide a sufficient condition. We provide simulation results that illustrate the theoretical result, and serve to show how large the number of nodes needs to be before the asymptotics are useful. We propose a localisation algorithm that uses this theory for a fixed anchor and a random node. We also introduce another algorithm for localisation that uses the empirical distribution of Euclidean distance given the hop-distance, which performs better than the previous one. Finally, we discuss few more issues related to the non-idealities in real sensor networks that require more understanding of the stochastic geometry of these networks and theoretical formalisation.

    [PDF] [Slides]