Mohammad Mahdian
Authored Publications
Google Publications
Other Publications
Sort By
Efficiency of the Generalized Second-Price Auction for Value Maximizers
Jieming Mao
Hanrui Zhang
Song Zuo
Proceedings of the ACM on Web Conference 2024, 46–56
Preview abstract
We study the price of anarchy of the generalized second-price auction where bidders are value maximizers (i.e., autobidders). We show that in general the price of anarchy can be as bad as 0. For comparison, the price of anarchy of running VCG is 1/2 in the autobidding world. We further show a fined-grained price of anarchy with respect to the discount factors (i.e., the ratios of click probabilities between lower slots and the highest slot in each auction) in the generalized second-price auction, which highlights the qualitative relation between the smoothness of the discount factors and the efficiency of the generalized second-price auction.
View details
Fair Hierarchical Clustering
Benjamin Moseley
Marina Knittel
Ravi Kumar Ravikumar
Yuyan Wang
Neurips 2020
Preview abstract
As machine learning has become more and more integrated into our businesses and lifestyles, researchers have begun to recognize the necessity of ensuring machine learning systems are fair. Recently, there has been an interest in defining a notion of fairness that mitigates over-representation in traditional clustering.
In this paper we extend this notion to hierarchical clustering, where the goal is to recursively partition the data to optimize a certain objective~\cite{dasgupta}. For various natural objectives, we obtain simple, efficient algorithms to find a provably good fair hierarchical clustering. Empirically, we show that our algorithms can find a fair hierarchical clustering, surprisingly, with only a negligible loss in the objective.
View details
Fair Correlation clustering
Ravi Kumar
23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020)(2020) (to appear)
Preview abstract
In this paper, we study correlation clustering under fairness constraints. Fair variants of k-median and k-center clustering have been studied recently, and approximation algorithms using a notion called fairlet decomposition have been proposed. We obtain approximation algorithms for fair correlation clustering under several important types of fairness constraints.
Our results hinge on obtaining a fairlet decomposition for correlation clustering by introducing a novel combinatorial optimization problem. We define a fairlet decomposition with cost similar to the k-median cost and this allows us to obtain approximation algorithms for a wide range of fairness constraints.
We complement our theoretical results with an in-depth analysis of our algorithms on real graphs where we show that fair solutions to correlation clustering can be obtained with limited increase in cost compared to the state-of-the-art (unfair) algorithms.
View details
Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
Vaggos Chatziafratis
AISTATS, AISTATS, AISTATS(2020), AISTATS (to appear)
Preview abstract
Hierarchical Clustering is an unsupervised data analysis method which has been widely used for decades. Despite its popularity, it had an underdeveloped analytical foundation and to address this, Dasgupta recently introduced an optimization view-point of hierarchical clustering with pair-
wise similarity information that spurred a line of work shedding light on old algorithms (e.g., Average-Linkage), but also designing new algorithms. Here, for the maximization dual of Dasgupta’s objec-
tive (introduced by Moseley-Wang), we present polynomial-time 42.46% approximation algorithms that use Max-Uncut Bisection as a subroutine. The previous best worst-case approximation factor in polynomial time was 33.6%, improving only slightly over Average-Linkage which achieves 33.3%. Finally, we complement our positive results by providing APX-hardness (even for 0-1 similarities), under the Small Set Expansion hypothesis.
View details
Preview abstract
Clustering is a fundamental problem in unsupervised machine learning. In many applications, clustering needs to be performed in presence of additional constraints, such as fairness or diversity constraints.
In this paper, we formulate the problem of k-center clustering without over-representation, and propose approximation algorithms to solve the problem, as well as hardness results. We empirically evaluate our clusterings on real-world dataset and show that fairness can be obtained with limited effect on clustering quality.
View details
Response Prediction for Low-Regret Agents
Sadra Yazdanbod
Web and Internet Economics 2019
Preview abstract
Companies like Google and Microsoft run billions of auctions every day to sell advertising opportunities. Any change to the rules of these auctions can have a tremendous effect on the revenue of the company and the welfare of the advertisers and the users. Therefore, any change requires careful evaluation of its potential impacts. Currently, such impacts are often evaluated by running simulations or small controlled experiments. This, however, misses the important factor that the advertisers respond to changes. Our goal is to build a theoretical framework for predicting the actions of an agent (the advertiser) that is optimizing her actions in an uncertain environment. We model this problem using a variant of the multi armed bandit setting where playing an arm is costly. The cost of each arm changes over time and is publicly observable. The value of playing an arm is drawn stochastically from a static distribution and is observed by the agent and not by us. We, however, observe the actions of the agent. Our main result is that assuming the agent is playing a strategy with a regret of at most f(T) within the first T rounds, we can learn to play the multi-armed bandits game without observing the rewards) in such a way that the regret of our selected actions is at most O(k^4 (f(T) + 1) log(T)).
View details
Incentive-Aware Learning for Large Markets
Song Zuo
Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pp. 1369-1378
Preview abstract
In a typical learning problem, one key step is to use training data to pick one model from a collection of models that optimizes an objective function. In many multi-agent settings, the training data is generated through the actions of the agents, and the model is
used to make a decision (e.g., how to sell an item) that affects the agents. An illustrative example of this is the problem of learning the
reserve price in an auction. In such cases, the agents have an incentive to influence the training data (e.g., by manipulating their bids in
the case of an auction) to game the system and achieve a more favorable outcome. In this paper, we study such incentive-aware learning
problem in a general setting and show that it is possible to approximately optimize the objective function under two assumptions:
(i) each individual agent is a “small” (part of the market); and (ii) there is a cost associated with manipulation. For our illustrative
application, this nicely translates to a mechanism for setting approximately optimal reserve prices in auctions where no individual
agent has significant market share. For this application, we also show that the second assumption (that manipulations are costly) is
not necessary since we can “perturb” any auction to make it costly for the agents to manipulate.
View details
Preview abstract
In online advertising, advertisers purchase ad placements by participating in a long sequence of repeated auctions. One of the most important features advertising platforms often provide, and advertisers often use, is budget management, which allows advertisers to control their cumulative expenditures. Advertisers typically declare the maximum daily amount they are willing to pay, and the platform adjusts allocations and payments to guarantee that cumulative expenditures do not exceed budgets. There are multiple ways to achieve this goal, and each one, when applied to all budget-constrained advertisers simultaneously, steers the system toward a different equilibrium. While previous research focused on online stochastic optimization techniques or game-theoretic equilibria of such settings, our goal in this paper is to compare the ``system equilibria'' of a range of budget management strategies in terms of the seller's profit and buyers' utility. In particular, we consider six different budget management strategies including probabilistic throttling, thresholding, bid shading, reserve pricing, and multiplicative boosting. We show these methods admit a system equilibrium in a rather general setting, and prove dominance relations between them in a simplified setting. Our study sheds light on the impact of budget management strategies on the tradeoff between the seller's profit and buyers' utility. Finally, we also empirically compare the system equilibria of these strategies using real ad auction data in sponsored search and randomly generated bids. The empirical study confirms our theoretical findings about the relative performances of budget management strategies.
View details
Pricing a low-regret seller
Hoda Heidari
Umar Syed
Sadra Yazdanbod
Proceedings of the Thirty-Third International Conference on Machine Learning (ICML 2016)
Preview abstract
As the number of ad exchanges has grown, publishers have turned to low regret learning algorithms to decide which exchange offers the best price for their inventory. This in turn opens the following question for the exchange: how to set prices to attract as many sellers as possible and maximize revenue. In this work we formulate this precisely as a learning problem, and present algorithms showing that by simply knowing that the counterparty is using a low regret algorithm is enough for the exchange to have its own low regret learning algorithm to find the optimal price.
View details
Preview abstract
In this paper we consider efficient construction of “composable
core-sets” for basic diversity and coverage maximization
problems. A core-set for a point-set in a metric space is a
subset of the point-set with the property that an approximate
solution to the whole point-set can be obtained given
the core-set alone. A composable core-set has the property
that for a collection of sets, the approximate solution to the
union of the sets in the collection can be obtained given the
union of the composable core-sets for the point sets in the
collection. Using composable core-sets one can obtain effi-
cient solutions to a wide variety of massive data processing
applications, including nearest neighbor search, streaming
algorithms and map-reduce computation.
Our main results are algorithms for constructing composable
core-sets for several notions of “diversity objective
functions”, a topic that attracted a significant amount of
research over the last few years. The composable core-sets
we construct are small and accurate: their approximation
factor almost matches that of the best “off-line” algorithms
for the relevant optimization problems (up to a constant
factor). Moreover, we also show applications of our results
to diverse nearest neighbor search, streaming algorithms and
map-reduce computation. Finally, we show that for an alternative
notion of diversity maximization based on the maximum
coverage problem small composable core-sets do not
exist.
View details
Designing Markets for Daily Deals
Preview
Yang Cai
Bo Waggoner
Conference on Web and Internet Economics (WINE)(2013) (to appear)
Ad auctions with data
Preview
Hu Fu
Patrick R. Jordan
Uri Nadav
Inbal Talgam-Cohen
INFOCOM Workshops(2012), pp. 184-189
To match or not to match: economics of cookie matching in online advertising
Preview
Arpita Ghosh
Preston McAfee
Proceedings of the 13th ACM Conference on Electronic Commerce, ACM, New York, NY, USA(2012), pp. 741-753
Christmas Gift Exchange Games
Online Optimization with Uncertain Information
Algorithms on evolving graphs
TrustBets: betting over an IOU network
Special Section on Foundations of Computer Science
Scott Aaronson
Jeff Erickson
R. Ravi
Emanuele Viola
SIAM J. Comput., 40(2011), pp. 770
Fighting censorship with algorithms
ACM Crossroads, 18(2011), pp. 41
Stochastic kronecker graphs
Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs
The Multiple Attribution Problem in Pay-Per-Conversion Advertising
Sorting and selection on dynamic data
Aris Anagnostopoulos
Ravi Kumar
Eli Upfal
Theor. Comput. Sci., 412(2011), pp. 2564-2576
Dynamics of conversations
Fighting Censorship with Algorithms
FUN(2010), pp. 296-306
Advertisement allocation for generalized second-pricing schemes
Value of Learning in Sponsored Search Auctions
Secure Overlay Network Design
Christmas Gift Exchange Games
Approximating Matches Made in Heaven
Mechanism Design for Complexity-Constrained Bidders
The Minimum Distance of Turbo-Like Codes
Louay Bazzi
Daniel A. Spielman
IEEE Transactions on Information Theory, 55(2009), pp. 6-15
Clustering-Based Bidding Languages for Sponsored Search
Sort Me If You Can: How to Sort Dynamic Data
Limitations of cross-monotonic cost-sharing schemes
Deterministic Decentralized Search in Random Graphs
Esteban Arcaute
Ning Chen
Ravi Kumar
David Liben-Nowell
Hamid Nazerzadeh
Ying Xu 0002
Internet Mathematics, 5(2008), pp. 141-154
A Cascade Model for Externalities in Sponsored Search
The Secretary Problem with a Hazard Rate Condition
Externalities in online advertising
Charity auctions on social networks
Influence and correlation in social networks
Facility Location
Rainbow solutions to the Sidon equation
Balloon Popping With Applications to Ascending Auctions
The role of compatibility in the diffusion of technologies through social networks
Nicole Immorlica
Jon M. Kleinberg
Tom Wexler
ACM Conference on Electronic Commerce(2007), pp. 75-83
Deterministic Decentralized Search in Random Graphs
Esteban Arcaute
Ning Chen
Ravi Kumar
David Liben-Nowell
Hamid Nazerzadeh
Ying Xu 0002
WAW(2007), pp. 187-194
Dynamics of bid optimization in online advertisement auctions
Christian Borgs
Jennifer T. Chayes
Nicole Immorlica
Kamal Jain
Omid Etesami
WWW(2007), pp. 531-540
Stochastic Kronecker Graphs
Robust Combinatorial Optimization with Exponential Scenarios
Mechanism Design on Trust Networks
Towards a pay-per-action model in sponsored search
Pay-per-action Model for Online Advertising
Allocating online advertisement space with unreliable estimates
Hamid Nazerzadeh
Amin Saberi
ACM Conference on Electronic Commerce(2007), pp. 288-294
Comparing Partial Rankings
Ronald Fagin
Ravi Kumar
D. Sivakumar
Erik Vee
SIAM J. Discrete Math., 20(2006), pp. 628-648
Game-Theoretic Aspects of Designing Hyperlink Structures
Secure Overlay Network Design
Multi-unit auctions with unknown supply
Approximation Algorithms for Metric Facility Location Problems
Finding small balanced separators
Random popular matchings
ACM Conference on Electronic Commerce(2006), pp. 238-242
Secretary Problems with Competing Employers
Limitations of cross-monotonic cost sharing schemes
Computing Equilibria in a Fisher Market with Linear Single-Constraint Production Units
Cycle Cover with Short Cycles
Online auctions with re-usable goods
Mohammad Taghi Hajiaghayi
Robert D. Kleinberg
David C. Parkes
ACM Conference on Electronic Commerce(2005), pp. 165-174
Click Fraud Resistant Methods for Learning Click-Through Rates
Minimizing Makespan in No-Wait Job Shops
Multi-unit auctions with budget-constrained bidders
Christian Borgs
Jennifer T. Chayes
Nicole Immorlica
Amin Saberi
ACM Conference on Electronic Commerce(2005), pp. 44-51
Marriage, honesty, and stability
On the forced matching numbers of bipartite graphs
Further Improvements in Competitive Guarantees for QoS Buffering
Nikhil Bansal
Lisa Fleischer
Tracy Kimbrel
Baruch Schieber
Maxim Sviridenko
ICALP(2004), pp. 196-207
Exploring the community structure of newsgroups
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games
Comparing and Aggregating Rankings with Ties
Optimizing the Placement of Internet TAPs in Wireless Neighborhood Networks
A 2-Approximation Algorithm for the Soft-Capacitated Facility Location Problem
Rainbow Arithmetic Progressions and Anti-Ramsey Results
Veselin Jungic
Jacob Licht
Jaroslav Nesetril
Rados Radoicic
Combinatorics, Probability & Computing, 12(2003), pp. 599-620
Approximating Market Equilibria
The facility location problem with general cost functions
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
Kamal Jain
Evangelos Markakis
Amin Saberi
Vijay V. Vazirani
J. ACM, 50(2003), pp. 795-824
Packing Steiner trees
Universal Facility Location
A new greedy approach for facility location problems
Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP
Kamal Jain
Evangelos Markakis
Amin Saberi
Vijay V. Vazirani
CoRR, cs.DS/0207028(2002)
On the computational complexity of strong edge coloring
Discrete Applied Mathematics, 118(2002), pp. 239-248
Improved Approximation Algorithms for Metric Facility Location Problems
Length-constrained path-matchings in graphs
Mohammad Ghodsi
Mohammad Taghi Hajiaghayi
Networks, 39(2002), pp. 210-215
A Greedy Facility Location Algorithm Analyzed Using Dual Fitting
The strong chromatic index of C4-free graphs
Random Struct. Algorithms, 17(2000), pp. 357-375
On a conjecture of Keedwell and the cycle double cover conjecture
Ebadollah S. Mahmoodian
Amin Saberi
Mohammad R. Salavatipour
Ruzbeh Tusserkani
Discrete Mathematics, 216(2000), pp. 287-292
A Characterization of Uniquely 2-List Colorable Graphs