## Publications

Expand All | Collapse All

Working Papers

1. Egalitarian and Congestion Aware Truthful Airport Slot Allocation Mechanism
Aasheesh Dixit*, Garima Shakya*, Suresh Kumar Jakhar, and Swaprava Nath (*equal contribution)
Technical Report.
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]

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

3. Prior-free Strategic Multiagent Scheduling with focus on Social Distancing
Deepesh Kumar Lall, Garima Shakya, and Swaprava Nath
Technical Report.
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 approximately optimal mechanism performs well in practice.

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

4. Incentivizing Effort and Precision in Peer-grading
Anujit Chakraborty, Jatin Jindal, and Swaprava Nath
Technical Report.
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]

5. Hybrid social choice: Mechanism design with and without money
Ioannis Caragiannis, Aris Filos-Ratsikas, Swaprava Nath, and Alexandros A. Voudouris
Technical Report.
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

1. Preference Elicitation For Participatory Budgeting
Gerdus Benadè, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah
Management Science (MS), Forthcoming. [supersedes the previous version]
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]

2. 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. [supersedes the previous version]
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.

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

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

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

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

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

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

Conference and Workshop

1. OMCoRP: An Online Mechanism for Competitive Robot Prioritization
Sankar Das, Swaprava Nath, and Indranil Saha
International Conference on Automated Planning and Scheduling (ICAPS), 2021, to appear.
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]

2. SkillCheck: An Incentive-based Certification System using Blockchains
Jay Gupta and Swaprava Nath
IEEE International Conference on Blockchain and Cryptocurrency (ICBC), 2020, to appear.
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]

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

[PDF]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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