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

Sujit Gujar

Sujit Gujar 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 TheoryMachine LearningCryptography and SecurityComputer VisionDistributed, Parallel, and Cluster ComputingNetworking and Internet ArchitectureArtificial Intelligencecs.CYecon.THeess.IVMultiagent Systems

Catalog footprint

What is connected

21works
11topics
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

21 published item(s)

preprint2022arXiv

Budgeted Combinatorial Multi-Armed Bandits

We consider a budgeted combinatorial multi-armed bandit setting where, in every round, the algorithm selects a super-arm consisting of one or more arms. The goal is to minimize the total expected regret after all rounds within a limited budget. Existing techniques in this literature either fix the budget per round or fix the number of arms pulled in each round. Our setting is more general where based on the remaining budget and remaining number of rounds, the algorithm can decide how many arms to be pulled in each round. First, we propose CBwK-Greedy-UCB algorithm, which uses a greedy technique, CBwK-Greedy, to allocate the arms to the rounds. Next, we propose a reduction of this problem to Bandits with Knapsacks (BwK) with a single pull. With this reduction, we propose CBwK-LPUCB that uses PrimalDualBwK ingeniously. We rigorously prove regret bounds for CBwK-LP-UCB. We experimentally compare the two algorithms and observe that CBwK-Greedy-UCB performs incrementally better than CBwK-LP-UCB. We also show that for very high budgets, the regret goes to zero.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

F3: Fair and Federated Face Attribute Classification with Heterogeneous Data

Fairness across different demographic groups is an essential criterion for face-related tasks, Face Attribute Classification (FAC) being a prominent example. Apart from this trend, Federated Learning (FL) is increasingly gaining traction as a scalable paradigm for distributed training. Existing FL approaches require data homogeneity to ensure fairness. However, this assumption is too restrictive in real-world settings. We propose F3, a novel FL framework for fair FAC under data heterogeneity. F3 adopts multiple heuristics to improve fairness across different demographic groups without requiring data homogeneity assumption. We demonstrate the efficacy of F3 by reporting empirically observed fairness measures and accuracy guarantees on popular face datasets. Our results suggest that F3 strikes a practical balance between accuracy and fairness for FAC.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fair Allocation with Special Externalities

Most of the existing algorithms for fair division do not consider externalities. Under externalities, the utility an agent obtains depends not only on its allocation but also on the allocation of other agents. An agent has a positive (negative) value for the assigned goods (chores). This work focuses on a special case of externality, i.e., an agent receives positive or negative value for unassigned items independent of which other agent gets it. We show that it is possible to adapt existing algorithms using a transformation to ensure certain fairness and efficiency notions in this setting. Despite the positive results, fairness notions like proportionality need to be re-defined. Further, we prove that maximin share (MMS) may not have any multiplicative approximation in this setting. Studying this domain is a stepping stone towards full externalities where ensuring fairness is much more challenging.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Individual Fairness in Feature-Based Pricing for Monopoly Markets

We study fairness in the context of feature-based price discrimination in monopoly markets. We propose a new notion of individual fairness, namely, α-fairness, which guarantees that individuals with similar features face similar prices. First, we study discrete valuation space and give an analytical solution for optimal fair feature-based pricing. We show that the cost of fair pricing is defined as the ratio of expected revenue in an optimal feature-based pricing to the expected revenue in an optimal fair feature-based pricing (CoF) can be arbitrarily large in general. When the revenue function is continuous and concave with respect to the prices, we show that one can achieve CoF strictly less than 2, irrespective of the model parameters. Finally, we provide an algorithm to compute fair feature-based pricing strategy that achieves this CoF.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-unit Double Auctions: Equilibrium Analysis and Bidding Strategy using DDPG in Smart-grids

Periodic double auctions (PDA) have applications in many areas such as in e-commerce, intra-day equity markets, and day-ahead energy markets in smart-grids. While the trades accomplished using PDAs are worth trillions of dollars, finding a reliable bidding strategy in such auctions is still a challenge as it requires the consideration of future auctions. A participating buyer in a PDA has to design its bidding strategy by planning for current and future auctions. Many equilibrium-based bidding strategies proposed are complex to use in real-time. In the current exposition, we propose a scale-based bidding strategy for buyers participating in PDA. We first present an equilibrium analysis for single-buyer single-seller multi-unit single-shot k-Double auctions. Specifically, we analyze the situation when a seller and a buyer trade two identical units of quantity in a double auction where both the buyer and the seller deploy a simple, scale-based bidding strategy. The equilibrium analysis becomes intractable as the number of participants increases. To be useful in more complex settings such as wholesale markets in smart-grids, we model equilibrium bidding strategy as a learning problem. We develop a deep deterministic policy gradient (DDPG) based learning strategy, DDPGBBS, for a participating agent in PDAs to suggest an action at any auction instance. DDPGBBS, which empirically follows the obtained theoretical equilibrium, is easily extendable when the number of buyers/sellers increases. We take Power Trading Agent Competition's (PowerTAC) wholesale market PDA as a testbed to evaluate our novel bidding strategy. We benchmark our DDPG based strategy against several baselines and state-of-the-art bidding strategies of the PowerTAC wholesale market PDA and demonstrate the efficacy of DDPGBBS against several benchmarked strategies.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tiramisu: Layering Consensus Protocols for Scalable and Secure Blockchains

Cryptocurrencies are poised to revolutionize the modern economy by democratizing commerce. These currencies operate on top of blockchain-based distributed ledgers. Existing permissionless blockchain-based protocols offer unparalleled benefits like decentralization, anonymity, and transparency. However, these protocols suffer in performance which hinders their widespread adoption. In particular, high time-to-finality and low transaction rates keep them from replacing centralized payment systems such as the Visa network. Permissioned blockchain protocols offer attractive performance guarantees, but they are not considered suitable for deploying decentralized cryptocurrencies due to their centralized nature. Researchers have developed several multi-layered blockchain protocols that combine both permissioned and permissionless blockchain protocols to achieve high performance along with decentralization. The key idea with existing layered blockchain protocols in literature is to divide blockchain operations into two layers and use different types of blockchain protocols to manage each layer. However, many such works come with the assumptions of honest majority which may not accurately reflect the real world where the participants may be self-interested or rational. These assumptions may render the protocols susceptible to security threats in the real world, as highlighted by the literature focused on exploring game-theoretic attacks on these protocols. We generalize the "layered" approach taken by existing protocols in the literature and present a framework to analyze the system in the BAR Model and provide a generalized game-theoretic analysis of such protocols. Using our analysis, we identify the critical system parameters required for a distributed ledger's secure operation in a more realistic setting.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Multi-Arm Bandit Approach To Subset Selection Under Constraints

We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents' quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely \dpss\ that provides an exact solution to our ILP. We then consider the setting when the qualities of the agents are unknown. We model this as a Multi-Arm Bandit (MAB) problem and propose \newalgo\ to learn the qualities over multiple rounds. We show that after a certain number of rounds, $τ$, \newalgo\ outputs a subset of agents that satisfy the average quality constraint with a high probability. Next, we provide bounds on $τ$ and prove that after $τ$ rounds, the algorithm incurs a regret of $O(\ln T)$, where $T$ is the total number of rounds. We further illustrate the efficacy of \newalgo\ through simulations. To overcome the computational limitations of \dpss, we propose a polynomial-time greedy algorithm, namely \greedy, that provides an approximate solution to our ILP. We also compare the performance of \dpss\ and \greedy\ through experiments.

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
preprint2021arXiv

FASTEN: Fair and Secure Distributed Voting Using Smart Contracts

Electing democratic representatives via voting has been a common mechanism since the 17th century. However, these mechanisms raise concerns about fairness, privacy, vote concealment, fair calculations of tally, and proxies voting on their behalf for the voters. Ballot voting, and in recent times, electronic voting via electronic voting machines (EVMs) improves fairness by relying on centralized trust. Homomorphic encryption-based voting protocols also assure fairness but cannot scale to large scale elections such as presidential elections. In this paper, we leverage the blockchain technology of distributing trust to propose a smart contract-based protocol, namely, \proto. There are many existing protocols for voting using smart contracts. We observe that these either are not scalable or leak the vote tally during the voting stage, i.e., do not provide vote concealment. In contrast, we show that FASTEN preserves voter's privacy ensures vote concealment, immutability, and avoids double voting. We prove that the probability of privacy breaches is negligibly small. Further, our cost analysis of executing FASTEN over Ethereum is comparable to most of the existing cost of elections.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Towards Mobile Distributed Ledgers

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distributed ledgers to function. Distributed ledgers, such as blockchains and directed acyclic graphs (DAGs), employ consensus protocols to add data in the form of blocks. However, such protocols are designed for resourceful devices that are interconnected via the Internet. Moreover, existing distributed ledgers are not deployable to D2D ecosystems since their storage needs are continuously increasing. In this work, we introduce and analyse Mneme, a DAG-based distributed ledger that can be maintained solely by mobile devices. Mneme utilizes two novel consensus protocols: Proof-of-Context (PoC) and Proof-of-Equivalence (PoE). PoC employs users' context to add data on Mneme. PoE is executed periodically to summarize data and produce equivalent blocks that require less storage. We analyze Mneme's security and justify the ability of PoC and PoE to guarantee the characteristics of distributed ledgers: persistence and liveness. Furthermore, we analyze potential attacks from malicious users and prove that the probability of a successful attack is inversely proportional to the square of the number of mobile users who maintain Mneme.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

We might walk together, but I run faster: Network Fairness and Scalability in Blockchains

Blockchain-based Distributed Ledgers (DLs) promise to transform the existing financial system by making it truly democratic. In the past decade, blockchain technology has seen many novel applications ranging from the banking industry to real estate. However, in order to be adopted universally, blockchain systems must be scalable to support a high volume of transactions. As we increase the throughput of the DL system, the underlying peer-to-peer network might face multiple levels of challenges to keep up with the requirements. Due to varying network capacities, the slower nodes would be at a relative disadvantage compared to the faster ones, which could negatively impact their revenue. In order to quantify their relative advantage or disadvantage, we introduce two measures of network fairness, $p_f$, the probability of frontrunning and $α_f$, the publishing fairness. We show that as we scale the blockchain, both these measures deteriorate, implying that the slower nodes face a disadvantage at higher throughputs. It results in the faster nodes getting more than their fair share of the reward while the slower nodes (slow in terms of network quality) get less. Thus, fairness and scalability in blockchain systems do not go hand in hand. In a setting with rational miners, lack of fairness causes miners to deviate from the "longest chain rule" or undercut, which would reduce the blockchain's resilience against byzantine adversaries. Hence, fairness is not only a desirable property for a blockchain system but also essential for the security of the blockchain and any scalable blockchain protocol proposed must ensure fairness.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

BitcoinF: Achieving Fairness for Bitcoin in Transaction-Fee-Only Model

A blockchain, such as Bitcoin, is an append-only, secure, transparent, distributed ledger. A fair blockchain is expected to have healthy metrics; high honest mining power, low processing latency, i.e., low wait times for transactions and stable price of consumption, i.e., the minimum transaction fee required to have a transaction processed. As Bitcoin matures, the influx of transactions increases and the block rewards become insignificant. We show that under these conditions, it becomes hard to maintain the health of the blockchain. In Bitcoin, under these mature operating conditions (MOC), the miners would find it challenging to cover their mining costs as there would be no more revenue from merely mining a block. It may cause miners not to continue mining, threatening the blockchain's security. Further, as we show in this paper using simulations, the cost of acting in favor of the health of the blockchain, under MOC, is very high in Bitcoin, causing all miners to process transactions greedily. It leads to stranded transactions, i.e., transactions offering low transaction fees, experiencing unreasonably high processing latency. To make matters worse, a compounding effect of these stranded transactions is the rising price of consumption. Such phenomena not only induce unfairness as experienced by the miners and the users but also deteriorate the health of the blockchain. We propose BitcoinF transaction processing protocol, a simple, yet highly effective modification to the existing Bitcoin protocol to fix these issues of unfairness. BitcoinF resolves these issues of unfairness while preserving the ability of the users to express urgency and have their transactions prioritized.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Designing Truthful Contextual Multi-Armed Bandits based Sponsored Search Auctions

For sponsored search auctions, we consider contextual multi-armed bandit problem in the presence of strategic agents. In this setting, at each round, an advertising platform (center) runs an auction to select the best-suited ads relevant to the query posted by the user. It is in the best interest of the center to select an ad that has a high expected value (i.e., probability of getting a click $\times$ value it derives from a click of the ad). The probability of getting a click (CTR) is unknown to the center and depends on the user's profile (context) posting the query. Further, the value derived for a click is the private information to the advertiser and thus needs to be elicited truthfully. The existing solution in this setting is not practical as it suffers from very high regret ($O(T^{\frac{2}{3}})$).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Effect of Input Noise Dimension in GANs

Generative Adversarial Networks (GANs) are by far the most successful generative models. Learning the transformation which maps a low dimensional input noise to the data distribution forms the foundation for GANs. Although they have been applied in various domains, they are prone to certain challenges like mode collapse and unstable training. To overcome the challenges, researchers have proposed novel loss functions, architectures, and optimization methods. In our work here, unlike the previous approaches, we focus on the input noise and its role in the generation. We aim to quantitatively and qualitatively study the effect of the dimension of the input noise on the performance of GANs. For quantitative measures, typically \emph{Fréchet Inception Distance (FID)} and \emph{Inception Score (IS)} are used as performance measure on image data-sets. We compare the FID and IS values for DCGAN and WGAN-GP. We use three different image data-sets -- each consisting of different levels of complexity. Through our experiments, we show that the right dimension of input noise for optimal results depends on the data-set and architecture used. We also observe that the state of the art performance measures does not provide enough useful insights. Hence we conclude that we need further theoretical analysis for understanding the relationship between the low dimensional distribution and the generated images. We also require better performance measures.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

FNNC: Achieving Fairness through Neural Networks

In classification models fairness can be ensured by solving a constrained optimization problem. We focus on fairness constraints like Disparate Impact, Demographic Parity, and Equalized Odds, which are non-decomposable and non-convex. Researchers define convex surrogates of the constraints and then apply convex optimization frameworks to obtain fair classifiers. Surrogates serve only as an upper bound to the actual constraints, and convexifying fairness constraints might be challenging. We propose a neural network-based framework, \emph{FNNC}, to achieve fairness while maintaining high accuracy in classification. The above fairness constraints are included in the loss using Lagrangian multipliers. We prove bounds on generalization errors for the constrained losses which asymptotically go to zero. The network is optimized using two-step mini-batch stochastic gradient descent. Our experiments show that FNNC performs as good as the state of the art, if not better. The experimental evidence supplements our theoretical guarantees. In summary, we have an automated solution to achieve fairness in classification, which is easily extendable to many fairness constraints.

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

Redistribution Mechanisms for Assignment of Heterogeneous Objects

There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Optimal Multi-Unit Combinatorial Procurement Auction with Single Minded Bidders

The current art in optimal combinatorial auctions is limited to handling the case of single units of multiple items, with each bidder bidding on exactly one bundle (single minded bidders). This paper extends the current art by proposing an optimal auction for procuring multiple units of multiple items when the bidders are single minded. The auction minimizes the cost of procurement while satisfying Bayesian incentive compatibility and interim individual rationality. Under appropriate regularity conditions, this optimal auction also satisfies dominant strategy incentive compatibility.

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