Research (by topic)

 

My current research focuses majorly on (i) Online Resource Allocation and Algorithmic Pricing and (ii) Algorithmic Mechanism Design, both with applications in designing online marketplaces, platforms, and operations of non-profit organizations (or governmental agencies). As a minor focus of my research, I also occasionally work on problems related to (iii) Combinatorial Optimization in Machine Learning and Data Science. A few of my work fall into the intersection of more than one of these topics, but are only listed under one of them.

(i) Online Resource Allocation & Algorithmic Pricing

My current main research focus is on designing algorithms for real-time and dynamic decision making, e.g., making pricing and allocations decisions in online platforms. My research addresses various operational goals in practice. These goals range from designing computationally and economically efficient (or profitable) market algorithms in online marketplaces under combinatorial constraints, to designing socially-aware decision making policies (for equity, fairness, and non-discrimination) in operations of governmental agencies and non-profit organizations.

[Online Resource Allocation]

“Fair Dynamic Rationing”forthcoming in Management Science (MS),2022[SSRN] [arXiv]

  • With Vahideh Manshadi and Scott Rodilitz.
  • INFORMS AMD Section 2021 Rothkopf Junior Researcher Paper Prize (First place)
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2021
  • Presented as a spotlight talk at INFORMS RM&P Conference, 2021
  • Accepted for presentation at MSOM Service SIG, 2022
  • Covered by Chicago Booth Review and Yale Insights.

“Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization”forthcoming in Management Science (MS), 2022[SSRN] [arXiv]

  • With Negin Golrezaei, Joshua Wang, Fransisca Susan and Ashwinkumar Badanidiyuru.
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2021
  • Finalist for the 2021 INFORMS Data Mining Section Best Paper
  • Accepted for presentation at MSOM Conference, 2022

“Near-optimal Bayesian Online Assortment of Reusable Resources”major revision at Operations Research (OR). [SSRN]

  • With Yiding Feng and Amin Saberi.
  • The conference version accepted in ACM Conference on Economics & Computations (EC), 2022
  • An earlier online version of this paper was titled as "Linear Programming Based Online Policies for Real-time Assortment of Reusable Resources". [SSRN]

“Batching and Optimal Multi-stage Bipartite Allocations”, revise & resubmit at Management Science (MS)[SSRN]

  • With Yiding Feng.
  • An earlier version appeared in Innovations in Theoretical Computer Science (ITCS), 2021
  • Follow-up work on "Optimal Multi-stage Configuration Allocation with Applications to Video Advertising". [SSRN]

“Two-stage Matching and Pricing with Applications to Ride Hailing”forthcoming in Operations Research (OR), 2022. [SSRN]

  • With Yiding Feng and Amin Saberi.
  • An earlier version appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021
  • Presented as a spotlight talk at INFORMS RM&P Conference 2021

Online Bipartite Matching with Reusable Resourcesunder revision in Mathematics of Operations Research (MOR). [arXiv] [SSRN]

  • With Steven Delong, Alireza Farhadi, Balu Sivan and Rajan Udwani. 
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2022

“Online Resource Allocation with Buyback: Optimal Algorithms via Primal-Dual”, to be submitted soon. [arXiv] [SSRN]

  •  with Farbod Ekbatani and Yiding Feng.

Online Assortment of Reusable Resources with Exogenous Replenishmentto be submitted soon. [SSRN]
  • With Yiding Feng and Amin Saberi.

 

“Secretary Problems with Non-Uniform Arrival Order”, to be submitted soon[arXiv]

  • With Thomas Kesselheim and Bobby Kleinberg.
  • An earlier version appeared in ACM Symposium on Theory of Computing (STOC), 2015. [ink]
  • Presented at 1st Highlights of Algorithms (HALG), 2016

“Ranking, Routing, and Learning in Online Food Delivery”under preparation, with Rene Caldentey, Ozan Candogan, and Niusha Navidi.


“Non-discriminatory Search and Online Allocation”under preparation, with Mohammad Reza Aminian and Vahideh Manshadi.


[Online Algorithmic Pricing]

“Multi-scale Online Learning: Theory and Applications to Online Auctions and Pricing”Journal of Machine Learning Research (JMLR), 2020. [Link] [arXiv]

  • With Sébastien Bubeck, Nikhil Devanur and Zhiyi Huang.
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2017

“Stateful Posted Pricing with Vanishing Regret via Dynamic Deterministic Markov Decision Processes”major revision at Mathematics of Operations Research (MOR). [arXiv]

  • With Yuval Emek, Ron Lavi and Yangguang Shi.
  • An earlier version appeared in Conference on Neural Information Processing Systems (NeurIPS), 2020

 Descending Price Auctions with Bounded Number of Prices Levels and Batched Prophet Inequalityunder preparation. [SSRN] [arXiv]

  • With Saeed Alaei, Ali Makhdoumi, and Azarakhsh Malekian.
  • The conference version accepted in ACM Conference on Economics & Computations (EC), 2022
  • Accepted for presentation at Marketplace Innovation Workshop, 2022

“Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection”under preparation[SSRN]

  • With Nima Anari, Amin Saberi and Ali Shameli
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2019.
  • This paper is extended an earlier work  “Prophet Inequalities vs. Approximating Optimum Online”, with Amin Saberi and Ali Shameli, appeared in the Conference on Web and Internet Economics (WINE), 2018. [Link]

“Truth and Regret in Online Scheduling”, under preparation[arXiv]

  • With Nikhil Devanur, Shuchi Chawla, and Janardhan Kulkarni,
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2017. [Link]

(ii) Algorithmic Mechanism Design

My second major current research focus is on designing auctions and mechanisms in complex environments, with a keen focus on modern applications in online platforms, web-based marketplaces, and recommendation systems (e.g. sponsored search, display advertising, online retail, etc.). Ideally, I would like to achieve the dual operational goals of simplicity (or interpretability) and economic efficiency (or high revenue) in these application domains by designing simple, computationally efficient, and approximately optimal mechanisms. 

[Combinatorial Auctions in Practice]

Fast Core Pricing for Rich Advertising Auctions”Operations Research (OR), 2021. [Link] [SSRN]

  • With Jason Hartline, Mohammad Reza Khani, Nicole Immorlica, and Brendan Lucier.
  • An earlier version appeared in ACM Conference on Economics & Computations (EC), 2018

“Bernoulli Factories and Black-Box Reductions in Mechanism Design”Journal of the ACM (JACM)2021. [Link] [arXiv]

  • With Shaddin Dughmi, Jason Hartline and Bobby Kleinberg.
  • An earlier version appeared in ACM Symposium on Theory of Computing (STOC), 2017
  • Presented as at GAMES 2021
  • Selected for a plenary presentation in Highlights Beyond EC 2020 Plenary Session
  • Follow-up technical work on "Combinatorial Bernoulli Factories", forthcoming in Bernoulli Journal, 2022. [SSRN] [arXiv]

“GSP - The Cinderella of Mechanism Design”in proceedings of International World Wide Web Conference (WWW), 2017[Link] [arXiv]

  • With Chris Wilkens and Ruggiero Cavallo.
  • An extended version is available under the title "Mechanism Design for Value Maximizers", with Chris Wilkens, Ruggiero Cavallo, and Samuel Taggart. [arXiv]

“Competitive Equilibria for Non-quasilinear Bidders in Combinatorial Auctions”, in proceedings of Conference on Web and Internet Economics (WINE), 2016. [Link] [arXiv]

  • With Chris Wilkens.

[Simple vs. Optimal Mechanisms and Market Algorithms]

“Optimal Auctions vs. Anonymous Pricing”Games and Economic Behavior (GEB), 2018. [Link] [arXiv]

  • With Saeed Alaei, Jason Hartline, Yang Yuan, and Manolis Pountourakis.
  • An earlier version appeared in IEEE Foundations of Computer Science (FOCS), 2015
  • Selected as one of the best algorithmic game theory papers from STOC/FOCS/SODA 2014-15.

“Sequential Submodular Maximization and Applications to Ranking an Assortment of Productsforthcoming in Operations Research (OR), 2022[SSRN]

  • With Arash Asadpour, Amin Saberi and Ali Shameli.
  • The conference version accepted in ACM Conference on Economics & Computations (EC), 2022
  • Accepted for presentation at MSOM Conference, 2022

“Persuasion and Incentives Through the Lens of Duality”in proceedings of International World Wide Web Conference (WWW), 2019. [Link] [arXiv]

  • With Shaddin Dughmi, Alex Psomas, and Matt Weinberg.


Simple and Near-Optimal Mechanisms For Market Intermediation”in proceedings of Conference on Web and Internet Economics (WINE), 2014[Link] [arXiv]

  • With Yang Yuan and Bobby Kleinberg.

(iii) Combinatorial Optimization in Data Science and Machine Learning

A minor focus of my current research is on designing approximation algorithms and sampling methods in various machine learning and data science applications, some of which are related to market design and operations management. The tools I have developed help with designing exact sampling algorithms in combinatorial environments, improved MLE for detecting human poses in computer vision, designing improved randomized experiments in marketplaces, and designing more refined clustering algorithms. 

[Approximation Algorithms in Data Science and Machine Learning]

Correlated Cluster-Based Randomized Experiments: Robust Variance Minimization, major revision at Management Science (MS). [SSRN]

  • With Ozan Candogan and Chen Chen.
  • Presented as a spotlight talk at INFORMS RM&P Conference, 2021

Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization”Journal of Machine Learning Research (JMLR), 2020. [Link] [arXiv]

  • With Tim Roughgarden and Joshua Wang.
  • An earlier version appeared in Conference on Neural Information Processing Systems (NuerIPS), 2018
  • Selected as top 30 papers for full oral presentation at NeurIPS, out of 4.8k+ submitted papers
  • Follow-up ongoing work on "Constant Approximation for Maximizing Weak-DR Continuous Submodular Functions with Cardinality Constraint"under preparation, with Ashwinkumar Badanidiyuru and Joshua Wang. 

Data-driven Statistical Analysis in Ride Sharing”under preparation.

  •  With Lynn Xu and Amy Ward. 

Series of work on designing approximation algorithms for Hierarchical Clustering":

  • "Hierarchical Clustering for Euclidean Data",
    with Vaggos Chatziafratis, Moses Charikar and Grigory Yaroslavtsev,
    in Proc. 22nd International Conference on Artificial Intelligence and Statistics (AISTATS 2019)
    [Link] [arXiv]

  • "Hierarchical Clustering better than Average-Linkage",
    with Vaggos Chatziafratis and Moses Charikar,
    in Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
    [Link] [arXiv]

  • "Hierarchical Clustering with Structural Constraints",
    with Vaggos Chatziafratis and Moses Charikar,
    in Proc. 35th International Conference on Machine Learning (ICML 2018),
    [Link] [arXiv]

[Exact Simulation in Machine Learning]

“Combinatorial Bernoulli Factories: Matchings, Flows, and Other Polytopes”forthcoming in Bernoulli Journal, 2022. [SSRN] [arXiv]

  • With Renato Paes Leme and Jon Schneider.
  • An earlier version appeared in ACM Symposium on Theory of Computing (STOC), 2021
  • Follow-up ongoing work on “Bernoulli Factories for Flow-Based Polytopes”under preparation, with Jon Schneider and Renato Paes Leme.