Author name cluster

S. Muthukrishnan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

AAMAS Conference 2018 Conference Paper

Arbitrage-free Pricing in User-based Markets

Chaolun Xia
S. Muthukrishnan

Users have various attributes, and in user-based markets there are buyers who wish to buy a target set of users with specific sets of attributes. The problem we address is that, given a set of demand from the buyers, how to allocate users to buyers, and how to price the transactions. This problem arises in online advertising, and is particularly relevant in advertising in social platforms like Facebook, LinkedIn and others where users are represented with many attributes, and advertisers are buyers with specific targets. This problem also arises more generally in selling data about online users, in a variety of data markets. We introduce arbitrage-free pricing, that is, pricing that prevents buyers from acquiring a lower unit price for their true target by strategically choosing substitute targets and combining them suitably. We show that uniform pricing – pricing where all the targets have identical price – can be computed in polynomial time, and while this is arbitrage-free, it is also a logarithmic approximation to the maximum revenue arbitrage-free pricing solution. We also design a different arbitrage-free non-uniform pricing – pricing where different targets have different prices – solution which has the same guarantee as the arbitrage-free uniform pricing but is empirically more effective as we show through experiments. We also study more general versions of this problem and present hardness and approximation results.

PDF

AAAI Conference 2014 Conference Paper

Large-Scale Optimistic Adaptive Submodularity

Victor Gabillon
Branislav Kveton
Zheng Wen
Brian Eriksson
S. Muthukrishnan

Maximization of submodular functions has wide applications in artificial intelligence and machine learning. In this paper, we propose a scalable learning algorithm for maximizing an adaptive submodular function. The key structural assumption in our solution is that the state of each item is distributed according to a generalized linear model, which is conditioned on the feature vector of the item. Our objective is to learn the parameters of this model. We analyze the performance of our algorithm, and show that its regret is polylogarithmic in time and quadratic in the number of features. Finally, we evaluate our solution on two problems, preference elicitation and face detection, and show that high-quality policies can be learned sample efficiently.

PDF Details

NeurIPS Conference 2013 Conference Paper

Adaptive Submodular Maximization in Bandit Setting

Victor Gabillon
Branislav Kveton
Zheng Wen
Brian Eriksson
S. Muthukrishnan

Maximization of submodular functions has wide applications in machine learning and artificial intelligence. Adaptive submodular maximization has been traditionally studied under the assumption that the model of the world, the expected gain of choosing an item given previously selected items and their states, is known. In this paper, we study the scenario where the expected gain is initially unknown and it is learned by interacting repeatedly with the optimized function. We propose an efficient algorithm for solving our problem and prove that its expected cumulative regret increases logarithmically with time. Our regret bound captures the inherent property of submodular maximization, earlier mistakes are more costly than later ones. We refer to our approach as Optimistic Adaptive Submodular Maximization (OASM) because it trades off exploration and exploitation based on the optimism in the face of uncertainty principle. We evaluate our method on a preference elicitation problem and show that non-trivial K-step policies can be learned from just a few hundred interactions with the problem.

PDF Details

TCS Journal 2008 Journal Article