Publications

Expand All | Collapse All

Working Papers

  1. Surprise in Elections
    Palash Dey, Pravesh K. Kothari, and Swaprava Nath
    Technical Report.
    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 esti- mated 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.

    [PDF]


  2. Separability and Decomposition in Mechanism Design with Transfers
    Debasis Mishra, Swaprava Nath, and Souvik Roy
    Technical Report.
    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

  1. Subset Selection Via Implicit Utilitarian Voting
    Ioannis Caragiannis, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
    Journal of Artificial Intelligence Research (JAIR), 2016, forthcoming.
    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]


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


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


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


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

  1. A Game-Theoretic Formalism of Human Partial Adaptation: Models and Experiments
    Stefanos Nikolaidis, Swaprava Nath, Ariel Procaccia, and Siddhartha Srinivasa
    Human Robot Interaction (HRI), March 6-9, 2017, Vienna, Austria, forthcoming.
    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]


  2. Preference Elicitation For Participatory Budgeting
    Gerdus Benade, Swaprava Nath, Ariel Procaccia, and Nisarg Shah
    Association for Advancement of Artificial Intelligence (AAAI), February 4 - 9, 2017, San Francisco, California, USA, forthcoming.
    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]


  3. Efficiency and Budget Balance
    Swaprava Nath and Tuomas Sandholm
    Web and Internet Economics (WINE), December 11 - 14, 2016, Montreal, Canada, forthcoming.
    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]


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


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


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


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


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


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

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


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


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


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