Paul Erdös ---- Anthony B. Evans ---- Krishnasamy Thiru Arasu ---- P. Vijay Kumar ---- You know who
Graduate Aptitude Test in Engineering (GATE, Indian Entrance Test for Graduate Studies
in Engineering) 2006.
All India Rank 34 out of approximately 40,000
candidates in Electronics and Communication stream.
Bronze medal for securing
the second highest aggregate of marks among all the courses of the
Bachelor of Engineering Examination 2006, Jadavpur University, Kolkata,
out of approximately 800 students in 13 departments.
State
Level Joint Entrance Examination (WBJEE, Entrance test for
undergraduate studies in Engineering) 2002.
Rank 25 (Engineering) out
of approximately 80,000 candidates.
Publications
Conference
Threats and Trade-offs in Resource Critical Crowdsourcing Tasks over Networks (Short Paper)
Swaprava Nath, Pankaj Dayama, Dinesh Garg, Yadati Narahari, James Zou Conference of the Association for Advancement Artificial Intelligence (AAAI), July 22-26, 2012, Toronto, CANADA. To appear. [abstract]
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.
Dynamic Mechanism Design for Markets with Strategic Resources
Swaprava Nath, Onno Zoeter, Yadati Narahari, Chris Dance Conference on Uncertainty in Artificial Intelligence, July 14-17, 2011, Barcelona, SPAIN. [abstract] [PDF]
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.
Performance Evaluation of Distance-Hop Proportionality on Geometric Graph Models of
Dense Sensor Network
Swaprava Nath, Anurag Kumar Valuetools 2008, ACM, October 21-23, 2008, Athens, GREECE. [abstract] [PDF] [slides]
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.
Linear Antenna Array with Suppressed Sidelobe and Sideband Levels using Time
Modulation
Swaprava Nath, Subrata Mitra International Conference On Computers And Devices For
Communication, CODEC 2006, Kolkata, INDIA.
Journal
Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph
Models of Dense Sensor Networks
Swaprava Nath, Venkatesan N. E., Anurag Kumar, P. Vijay Kumar to appear in ACM Transactions on Sensor Networks (TOSN). [abstract]
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.
Other
Dynamic Learning-based Mechanism Design for Dependent Valued Exchange Economies (PhD Proposal)
Swaprava Nath International World Wide Web Conference, March 28 - April 1, 2011, Hyderabad, INDIA. [abstract] [PDF] [slides]
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.
Some good books on Game Theory and Mechanism Design:
Flipkart is a wonderful website to find good books at competitive prices in Indian market.
Page last modified:
Visitor Count
Personal Corner
I love to play soccer and to travel. I have traveled almost all major tourist destinations in India. I'm curious about the international destinations outside India. I had been to some cities in Europe. I took some photos while interning at Cambridge, MA. In addition, I write reviews in travel forums like tripadvisor. The photo on top of the page was taken at Fort de la Bastille, Grenoble, France. Below is a map where I have traveled so far. I also listen to Indian and Western Classical Music. I'm long out of practice, but sometimes I sit down with paper and charcoal, result 1, result 2.
