BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Y. Narahari

Y. Narahari appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computer Science and Game TheoryMultiagent SystemsArtificial IntelligenceMachine LearningSocial and Information Networksphysics.soc-phComputation and Languagecs.CYData Structures and AlgorithmsDiscrete Mathematics

Catalog footprint

What is connected

27works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2022arXiv

Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations

We study the problem of allocating indivisible goods among agents in a fair manner. While envy-free allocations of indivisible goods are not guaranteed to exist, envy-freeness can be achieved by additionally providing some subsidy to the agents. These subsidies can be alternatively viewed as a divisible good (money) that is fractionally assigned among the agents to realize an envy-free outcome. In this setup, we bound the subsidy required to attain envy-freeness among agents with dichotomous valuations, i.e., among agents whose marginal value for any good is either zero or one. We prove that, under dichotomous valuations, there exists an allocation that achieves envy-freeness with a per-agent subsidy of either $0$ or $1$. Furthermore, such an envy-free solution can be computed efficiently in the standard value-oracle model. Notably, our results hold for general dichotomous valuations and, in particular, do not require the (dichotomous) valuations to be additive, submodular, or even subadditive. Also, our subsidy bounds are tight and provide a linear (in the number of agents) factor improvement over the bounds known for general monotone valuations.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Maxmin Participatory Budgeting

Participatory Budgeting (PB) is a popular voting method by which a limited budget is divided among a set of projects, based on the preferences of voters over the projects. PB is broadly categorised as divisible PB (if the projects are fractionally implementable) and indivisible PB (if the projects are atomic). Egalitarianism, an important objective in PB, has not received much attention in the context of indivisible PB. This paper addresses this gap through a detailed study of a natural egalitarian rule, Maxmin Participatory Budgeting (MPB), in the context of indivisible PB. Our study is in two parts: (1) computational (2) axiomatic. In the first part, we prove that MPB is computationally hard and give pseudo-polynomial time and polynomial-time algorithms when parameterized by certain well-motivated parameters. We propose an algorithm that achieves for MPB, additive approximation guarantees for restricted spaces of instances and empirically show that our algorithm in fact gives exact optimal solutions on real-world PB datasets. We also establish an upper bound on the approximation ratio achievable for MPB by the family of exhaustive strategy-proof PB algorithms. In the second part, we undertake an axiomatic study of the MPB rule by generalizing known axioms in the literature. Our study leads to the proposal of a new axiom, maximal coverage, which captures fairness aspects. We prove that MPB satisfies maximal coverage.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Nash Welfare Guarantees for Fair and Efficient Coverage

We study coverage problems in which, for a set of agents and a given threshold $T$, the goal is to select $T$ subsets (of the agents) that, while satisfying combinatorial constraints, achieve fair and efficient coverage among the agents. In this setting, the valuation of each agent is equated to the number of selected subsets that contain it, plus one. The current work utilizes the Nash social welfare function to quantify the extent of fairness and collective efficiency. We develop a polynomial-time $\left(18 + o(1) \right)$-approximation algorithm for maximizing Nash social welfare in coverage instances. Our algorithm applies to all instances wherein, for the underlying combinatorial constraints, there exists an FPTAS for weight maximization. We complement the algorithmic result by proving that Nash social welfare maximization is APX-hard in coverage instances.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Ballooning Multi-Armed Bandits

In this paper, we introduce Ballooning Multi-Armed Bandits (BL-MAB), a novel extension of the classical stochastic MAB model. In the BL-MAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regret in a BL-MAB setting is computed with respect to the best available arm at each time. We first observe that the existing stochastic MAB algorithms result in linear regret for the BL-MAB model. We prove that, if the best arm is equally likely to arrive at any time instant, a sub-linear regret cannot be achieved. Next, we show that if the best arm is more likely to arrive in the early rounds, one can achieve sub-linear regret. Our proposed algorithm determines (1) the fraction of the time horizon for which the newly arriving arms should be explored and (2) the sequence of arm pulls in the exploitation phase from among the explored arms. Making reasonable assumptions on the arrival distribution of the best arm in terms of the thinness of the distribution's tail, we prove that the proposed algorithm achieves sub-linear instance-independent regret. We further quantify explicit dependence of regret on the arrival distribution parameters. We reinforce our theoretical findings with extensive simulation results. We conclude by showing that our algorithm would achieve sub-linear regret even if (a) the distributional parameters are not exactly known, but are obtained using a reasonable learning mechanism or (b) the best arm is not more likely to arrive early, but a large fraction of arms is likely to arrive relatively early.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Dominant Strategy Truthful, Deterministic Multi-Armed Bandit Mechanism with Logarithmic Regret

Stochastic multi-armed bandit (MAB) mechanisms are widely used in sponsored search auctions, crowdsourcing, online procurement, etc. Existing stochastic MAB mechanisms with a deterministic payment rule, proposed in the literature, necessarily suffer a regret of $Ω(T^{2/3})$, where $T$ is the number of time steps. This happens because the existing mechanisms consider the worst case scenario where the means of the agents' stochastic rewards are separated by a very small amount that depends on $T$. We make, and, exploit the crucial observation that in most scenarios, the separation between the agents' rewards is rarely a function of $T$. Moreover, in the case that the rewards of the arms are arbitrarily close, the regret contributed by such sub-optimal arms is minimal. Our idea is to allow the center to indicate the resolution, $Δ$, with which the agents must be distinguished. This immediately leads us to introduce the notion of $Δ$-Regret. Using sponsored search auctions as a concrete example (the same idea applies for other applications as well), we propose a dominant strategy incentive compatible (DSIC) and individually rational (IR), deterministic MAB mechanism, based on ideas from the Upper Confidence Bound (UCB) family of MAB algorithms. Remarkably, the proposed mechanism $Δ$-UCB achieves a $Δ$-regret of $O(\log T)$ for the case of sponsored search auctions. We first establish the results for single slot sponsored search auctions and then non-trivially extend the results to the case where multiple slots are to be allocated.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Achieving Fairness in the Stochastic Multi-armed Bandit Problem

We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, called $r$-Regret, that takes into account the above fairness constraints and naturally extends the conventional notion of regret. Our primary contribution is characterizing a class of Fair-SMAB algorithms by two parameters: the unfairness tolerance and the learning algorithm used as a black-box. We provide a fairness guarantee for this class that holds uniformly over time irrespective of the choice of the learning algorithm. In particular, when the learning algorithm is UCB1, we show that our algorithm achieves $O(\ln T)$ $r$-Regret. Finally, we evaluate the cost of fairness in terms of the conventional notion of regret.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Robust UCB Scheme for Active Learning in Regression from Strategic Crowds

We study the problem of training an accurate linear regression model by procuring labels from multiple noisy crowd annotators, under a budget constraint. We propose a Bayesian model for linear regression in crowdsourcing and use variational inference for parameter estimation. To minimize the number of labels crowdsourced from the annotators, we adopt an active learning approach. In this specific context, we prove the equivalence of well-studied criteria of active learning like entropy minimization and expected error reduction. Interestingly, we observe that we can decouple the problems of identifying an optimal unlabeled instance and identifying an annotator to label it. We observe a useful connection between the multi-armed bandit framework and the annotator selection in active learning. Due to the nature of the distribution of the rewards on the arms, we use the Robust Upper Confidence Bound (UCB) scheme with truncated empirical mean estimator to solve the annotator selection problem. This yields provable guarantees on the regret. We further apply our model to the scenario where annotators are strategic and design suitable incentives to induce them to put in their best efforts.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An Iterative Transfer Learning Based Ensemble Technique for Automatic Short Answer Grading

Automatic short answer grading (ASAG) techniques are designed to automatically assess short answers to questions in natural language, having a length of a few words to a few sentences. Supervised ASAG techniques have been demonstrated to be effective but suffer from a couple of key practical limitations. They are greatly reliant on instructor provided model answers and need labeled training data in the form of graded student answers for every assessment task. To overcome these, in this paper, we introduce an ASAG technique with two novel features. We propose an iterative technique on an ensemble of (a) a text classifier of student answers and (b) a classifier using numeric features derived from various similarity measures with respect to model answers. Second, we employ canonical correlation analysis based transfer learning on a common feature representation to build the classifier ensemble for questions having no labelled data. The proposed technique handsomely beats all winning supervised entries on the SCIENTSBANK dataset from the Student Response Analysis task of SemEval 2013. Additionally, we demonstrate generalizability and benefits of the proposed technique through evaluation on multiple ASAG datasets from different subject topics and standards.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Referral-Embedded Provision Point Mechanisms for Crowdfunding of Public Projects

Civic Crowdfunding is emerging as a popular means to mobilize funding from citizens for public projects. A popular mechanism deployed on civic crowdfunding platforms is a provision point mechanism, wherein, the total contributions must reach a predetermined threshold in order for the project to be provisioned (undertaken). Such a mechanism may have multiple equilibria; unfortunately, in many of these equilibria, the project is not funded even if it is highly valued among the agents. Recent work has proposed mechanisms with refund bonuses where the project gets funded in equilibrium if its net value is higher than a threshold among the agents who are aware of the crowdfunding effort. In this paper, we formalize the notion of social desirability of a public project and propose mechanisms which use the idea of referrals to expand the pool of participants and achieve an equilibrium in which the project gets funded if its net value exceeds a threshold among the entire agent population. We call this new class of mechanisms Referral-Embedded Provision Point Mechanisms (REPPM). We specifically propose two variants of REPPM and both these mechanisms have the remarkable property that, at equilibrium, referral bonuses are offered but there is no need for actual payment of these bonuses. We establish that any given agent's equilibrium strategy is to refer other agents and to contribute in proportion to the agent's true value for the project. By referring others to contribute, an agent can, in fact, reduce his equilibrium contribution. In our view, the proposed mechanisms will lead to an increase in the number of projects that are funded on civic crowdfunding platforms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Topic Model Based Multi-Label Classification from the Crowd

Multi-label classification is a common supervised machine learning problem where each instance is associated with multiple classes. The key challenge in this problem is learning the correlations between the classes. An additional challenge arises when the labels of the training instances are provided by noisy, heterogeneous crowdworkers with unknown qualities. We first assume labels from a perfect source and propose a novel topic model where the present as well as the absent classes generate the latent topics and hence the words. We non-trivially extend our topic model to the scenario where the labels are provided by noisy crowdworkers. Extensive experimentation on real world datasets reveals the superior performance of the proposed model. The proposed model learns the qualities of the annotators as well, even with minimal training data.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Multi-phase Approach for Improving Information Diffusion in Social Networks

For maximizing influence spread in a social network, given a certain budget on the number of seed nodes, we investigate the effects of selecting and activating the seed nodes in multiple phases. In particular, we formulate an appropriate objective function for two-phase influence maximization under the independent cascade model, investigate its properties, and propose algorithms for determining the seed nodes in the two phases. We also study the problem of determining an optimal budget-split and delay between the two phases.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Incentive Compatible Multi-Armed-Bandit Crowdsourcing Mechanism with Quality Assurance

Consider a requester who wishes to crowdsource a series of identical binary labeling tasks to a pool of workers so as to achieve an assured accuracy for each task, in a cost optimal way. The workers are heterogeneous with unknown but fixed qualities and their costs are private. The problem is to select for each task an optimal subset of workers so that the outcome obtained from the selected workers guarantees a target accuracy level. The problem is a challenging one even in a non strategic setting since the accuracy of aggregated label depends on unknown qualities. We develop a novel multi-armed bandit (MAB) mechanism for solving this problem. First, we propose a framework, Assured Accuracy Bandit (AAB), which leads to an MAB algorithm, Constrained Confidence Bound for a Non Strategic setting (CCB-NS). We derive an upper bound on the number of time steps the algorithm chooses a sub-optimal set that depends on the target accuracy level and true qualities. A more challenging situation arises when the requester not only has to learn the qualities of the workers but also elicit their true costs. We modify the CCB-NS algorithm to obtain an adaptive exploration separated algorithm which we call { \em Constrained Confidence Bound for a Strategic setting (CCB-S)}. CCB-S algorithm produces an ex-post monotone allocation rule and thus can be transformed into an ex-post incentive compatible and ex-post individually rational mechanism that learns the qualities of the workers and guarantees a given target accuracy level in a cost optimal way. We provide a lower bound on the number of times any algorithm should select a sub-optimal set and we see that the lower bound matches our upper bound upto a constant factor. We provide insights on the practical implementation of this framework through an illustrative example and we show the efficacy of our algorithms through simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Optimal Bidimensional Multi-Armed Bandit Auction for Multi-unit Procurement

We study the problem of a buyer (aka auctioneer) who gains stochastic rewards by procuring multiple units of a service or item from a pool of heterogeneous strategic agents. The reward obtained for a single unit from an allocated agent depends on the inherent quality of the agent; the agent's quality is fixed but unknown. Each agent can only supply a limited number of units (capacity of the agent). The costs incurred per unit and capacities are private information of the agents. The auctioneer is required to elicit costs as well as capacities (making the mechanism design bidimensional) and further, learn the qualities of the agents as well, with a view to maximize her utility. Motivated by this, we design a bidimensional multi-armed bandit procurement auction that seeks to maximize the expected utility of the auctioneer subject to incentive compatibility and individual rationality while simultaneously learning the unknown qualities of the agents. We first assume that the qualities are known and propose an optimal, truthful mechanism 2D-OPT for the auctioneer to elicit costs and capacities. Next, in order to learn the qualities of the agents in addition, we provide sufficient conditions for a learning algorithm to be Bayesian incentive compatible and individually rational. We finally design a novel learning mechanism, 2D-UCB that is stochastic Bayesian incentive compatible and individually rational.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic Collusion-Proofness of Voting Rules: The Case of Large Number of Candidates

Classical results in voting theory show that strategic manipulation by voters is inevitable if a voting rule simultaneously satisfy certain desirable properties. Motivated by this, we study the relevant question of how often a voting rule is manipulable. It is well known that elections with a large number of voters are rarely manipulable under impartial culture (IC) assumption. However, the manipulability of voting rules when the number of candidates is large has hardly been addressed in the literature and our paper focuses on this problem. First, we propose two properties (1) asymptotic strategy-proofness and (2) asymptotic collusion-proofness, with respect to new voters, which makes the two notions more relevant from the perspective of computational problem of manipulation. In addition to IC, we explore a new culture of society where all score vectors of the candidates are equally likely. This new notion has its motivation in computational social choice and we call it impartial scores culture (ISC) assumption. We study asymptotic strategy-proofness and asymptotic collusion-proofness for plurality, veto, $k$-approval, and Borda voting rules under IC as well as ISC assumptions. Specifically, we prove bounds for the fraction of manipulable profiles when the number of candidates is large. Our results show that the size of the coalition and the tie-breaking rule play a crucial role in determining whether or not a voting rule satisfies the above two properties.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Detecting Possible Manipulators in Elections

Manipulation is a problem of fundamental importance in the context of voting in which the voters exercise their votes strategically instead of voting honestly to prevent selection of an alternative that is less preferred. The Gibbard-Satterthwaite theorem shows that there is no strategy-proof voting rule that simultaneously satisfies certain combinations of desirable properties. Researchers have attempted to get around the impossibility results in several ways such as domain restriction and computational hardness of manipulation. However these approaches have been shown to have limitations. Since prevention of manipulation seems to be elusive, an interesting research direction therefore is detection of manipulation. Motivated by this, we initiate the study of detection of possible manipulators in an election. We formulate two pertinent computational problems - Coalitional Possible Manipulators (CPM) and Coalitional Possible Manipulators given Winner (CPMW), where a suspect group of voters is provided as input to compute whether they can be a potential coalition of possible manipulators. In the absence of any suspect group, we formulate two more computational problems namely Coalitional Possible Manipulators Search (CPMS), and Coalitional Possible Manipulators Search given Winner (CPMSW). We provide polynomial time algorithms for these problems, for several popular voting rules. For a few other voting rules, we show that these problems are in NP-complete. We observe that detecting manipulation maybe easy even when manipulation is hard, as seen for example, in the case of the Borda voting rule.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Dynamic Mechanism Design with Interdependent Valuations

We consider an infinite horizon dynamic mechanism design problem with interdependent valuations. In this setting the type of each agent is assumed to be evolving according to a first order Markov process and is independent of the types of other agents. However, the valuation of an agent can depend on the types of other agents, which makes the problem fall into an interdependent valuation setting. Designing truthful 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 in a static setting. Mezzetti (2004) circumvents this problem by splitting the decisions of allocation and payment into two stages. However, Mezzetti's result is limited to a 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 efficient, `strict' ex-post incentive compatible and ex-post individually rational in a setting with interdependent values and Markovian type evolution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Estimating the Margin of Victory of an Election using Sampling

The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling etc. In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the \textsc{$(c, ε, δ)$--Margin of Victory} problem, where given an election $\mathcal{E}$ on $n$ voters, the goal is to estimate the margin of victory $M(\mathcal{E})$ of $\mathcal{E}$ within an additive factor of $c MoV(\mathcal{E})+εn$. We study the \textsc{$(c, ε, δ)$--Margin of Victory} problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copeland$^α.$ We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copeland$^α$ voting rules.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Kernelization Complexity of Possible Winner and Coalitional Manipulation Problems in Voting

In the Possible Winner problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the Possible Winner problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge. In this paper, we settle this open question for many common voting rules. We show that the Possible Winner problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that include the Borda voting rule do not admit a polynomial kernel with the number of candidates as the parameter. We show however that the Coalitional Manipulation problem which is an important special case of the Possible Winner problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the Possible Winner problem is harder than the Coalitional Manipulation problem since the Coalitional Manipulation problem admits a polynomial kernel whereas the Possible Winner problem does not admit a polynomial kernel.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Manipulation is Harder with Incomplete Votes

The Coalitional Manipulation (CM) problem has been studied extensively in the literature for many voting rules. The CM problem, however, has been studied only in the complete information setting, that is, when the manipulators know the votes of the non-manipulators. A more realistic scenario is an incomplete information setting where the manipulators do not know the exact votes of the non- manipulators but may have some partial knowledge of the votes. In this paper, we study a setting where the manipulators know a partial order for each voter that is consistent with the vote of that voter. In this setting, we introduce and study two natural computational problems - (1) Weak Manipulation (WM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in at least one extension of the partial votes of the non-manipulators; (2) Strong Manipulation (SM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in all possible extensions of the partial votes of the non-manipulators. We study the computational complexity of the WM and the SM problems for commonly used voting rules such as plurality, veto, k-approval, k-veto, maximin, Copeland, and Bucklin. Our key finding is that, barring a few exceptions, manipulation becomes a significantly harder problem in the setting of incomplete votes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On Choosing Committees Based on Approval Votes in the Presence of Outliers

We study the computational complexity of committee selection problem for several approval-based voting rules in the presence of outliers. Our first result shows that outlier consideration makes committee selection problem intractable for approval, net approval, and minisum approval voting rules. We then study parameterized complexity of this problem with five natural parameters, namely the target score, the size of the committee (and its dual parameter, the number of candidates outside the committee), the number of outliers (and its dual parameter, the number of non-outliers). For net approval and minisum approval voting rules, we provide a dichotomous result, resolving the parameterized complexity of this problem for all subsets of five natural parameters considered (by showing either FPT or W[1]-hardness for all subsets of parameters). For the approval voting rule, we resolve the parameterized complexity of this problem for all subsets of parameters except one. We also study approximation algorithms for this problem. We show that there does not exist any alpha(.) factor approximation algorithm for approval and net approval voting rules, for any computable function alpha(.), unless P=NP. For the minisum voting rule, we provide a pseudopolynomial (1+eps) factor approximation algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Profit Maximizing Prior-free Multi-unit Procurement Auctions with Capacitated Sellers

In this paper, we derive bounds for profit maximizing prior-free procurement auctions where a buyer wishes to procure multiple units of a homogeneous item from n sellers who are strategic about their per unit valuation. The buyer earns the profit by reselling these units in an external consumer market. The paper looks at three scenarios of increasing complexity. First, we look at unit capacity sellers where per unit valuation is private information of each seller and the revenue curve is concave. For this setting, we define two benchmarks. We show that no randomized prior free auction can be constant competitive against any of these two benchmarks. However, for a lightly constrained benchmark we design a prior-free auction PEPA (Profit Extracting Procurement Auction) which is 4-competitive and we show this bound is tight. Second, we study a setting where the sellers have non-unit capacities that are common knowledge and derive similar results. In particular, we propose a prior free auction PEPAC (Profit Extracting Procurement Auction with Capacity) which is truthful for any concave revenue curve. Third, we obtain results in the inherently harder bi-dimensional case where per unit valuation as well as capacities are private information of the sellers. We show that PEPAC is truthful and constant competitive for the specific case of linear revenue curves. We believe that this paper represents the first set of results on single dimensional and bi-dimensional profit maximizing prior-free multi-unit procurement auctions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sufficient Conditions for Formation of a Network Topology by Self-interested Agents

Networks such as organizational network of a global company play an important role in a variety of knowledge management and information diffusion tasks. The nodes in these networks correspond to individuals who are self-interested. The topology of these networks often plays a crucial role in deciding the ease and speed with which certain tasks can be accomplished using these networks. Consequently, growing a stable network having a certain topology is of interest. Motivated by this, we study the following important problem: given a certain desired network topology, under what conditions would best response (link addition/deletion) strategies played by self-interested agents lead to formation of a pairwise stable network with only that topology. We study this interesting reverse engineering problem by proposing a natural model of recursive network formation. In this model, nodes enter the network sequentially and the utility of a node captures principal determinants of network formation, namely (1) benefits from immediate neighbors, (2) costs of maintaining links with immediate neighbors, (3) benefits from indirect neighbors, (4) bridging benefits, and (5) network entry fee. Based on this model, we analyze relevant network topologies such as star graph, complete graph, bipartite Turan graph, and multiple stars with interconnected centers, and derive a set of sufficient conditions under which these topologies emerge as pairwise stable networks. We also study the social welfare properties of the above topologies.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Mechanism Design for Time Critical and Cost Critical Task Execution via Crowdsourcing

An exciting application of crowdsourcing is to use social networks in complex task execution. In this paper, we address the problem of a planner who needs to incentivize agents within a network in order to seek their help in executing an {\em atomic task} as well as in recruiting other agents to execute the task. 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 identify a set of desirable properties that should ideally be satisfied by a crowdsourcing mechanism. In particular, {\em sybil-proofness} and {\em collapse-proofness} are two complementary properties in our desiderata. We prove that no mechanism can satisfy all the desirable properties simultaneously. This leads us naturally to explore approximate versions of the critical properties. We focus our attention on approximate sybil-proofness and our exploration leads to a parametrized family of payment mechanisms which satisfy collapse-proofness. We characterize the approximate versions of the desirable properties in cost critical and time critical domain.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Optimal Mix of Incentive Strategies for Product Marketing on Social Networks

We consider the problem of devising incentive strategies for viral marketing of a product. In particular, we assume that the seller can influence penetration of the product by offering two incentive programs: a) direct incentives to potential buyers (influence) and b) referral rewards for customers who influence potential buyers to make the purchase (exploit connections). The problem is to determine the optimal timing of these programs over a finite time horizon. In contrast to algorithmic perspective popular in the literature, we take a mean-field approach and formulate the problem as a continuous-time deterministic optimal control problem. We show that the optimal strategy for the seller has a simple structure and can take both forms, namely, influence-and-exploit and exploit-and-influence. We also show that in some cases it may optimal for the seller to deploy incentive programs mostly for low degree nodes. We support our theoretical results through numerical studies and provide practical insights by analyzing various scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Incentive Compatible Influence Maximization in Social Networks and Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. We first work with a simple model, the influencer model, where we assume that each user knows the level of influence she has on her neighbors but this is private information. In the second model, the influencer-influencee model, which is more realistic, we determine influence probabilities by combining the probability values reported by the influencers and influencees. In the context of the first model, we present how VCG (Vickrey-Clarke-Groves) mechanisms could be used for truthfully eliciting the influence probabilities. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms when the scoring rules are proper and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use. We also discuss briefly the implementation of such a mechanism in viral marketing applications.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Topologies and Price of Stability of Complex Strategic Networks with Localized Payoffs : Analytical and Simulation Studies

We analyze a network formation game in a strategic setting where payoffs of individuals depend only on their immediate neighbourhood. We call these payoffs as localized payoffs. In this game, the payoff of each individual captures (1) the gain from immediate neighbors, (2) the bridging benefits, and (3) the cost to form links. This implies that the payoff of each individual can be computed using only its single-hop neighbourhood information. Based on this simple model of network formation, our study explores the structure of networks that form, satisfying one or both of the properties, namely, pairwise stability and efficiency. We analytically prove the pairwise stability of several interesting network structures, notably, the complete bi-partite network, complete equi-k-partite network, complete network and cycle network, under various configurations of the model. We validate and extend these results through extensive simulations. We characterize topologies of efficient networks by drawing upon classical results from extremal graph theory and discover that the Turan graph (or the complete equi-bi-partite network) is the unique efficient network under many configurations of parameters. We examine the tradeoffs between topologies of pairwise stable networks and efficient networks using the notion of price of stability, which is the ratio of the sum of payoffs of the players in an optimal pairwise stable network to that of an efficient network. Interestingly, we find that price of stability is equal to 1 for almost all configurations of parameters in the proposed model; and for the rest of the configurations of the parameters, we obtain a lower bound of 0.5 on the price of stability. This leads to another key insight of this paper: under mild conditions, efficient networks will form when strategic individuals choose to add or delete links based on only localized payoffs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Search Auctions

In pay-per click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with each agent-slot pairs. The goal of the search engine is to maximize social welfare of the advertisers, that is, the sum of values of the advertisers. The search engine does not know the true values advertisers have for a click to their respective ads and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these click probabilities during the T rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced and are aptly referred to as multi-armed-bandit (MAB) mechanisms. When m = 1, characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but non-trivial general case when m > 1 and obtain several interesting results.

0 citations0 reviewsNo code linkedOpen access