Research
      Publications
      Teaching/Service
      Brief biography
      Contact Info


       CS 880


       UW CS
       Theory Group

I recently moved to UT-Austin. You will be redirected to my new webpage shortly.



Some recent happenings

• I recently got done chairing SODA'20. Next up is EC'21 which I'm co-chairing with Federico Echenique.
• I feel honored to have been awarded the Chancellor's Teaching Innovation Award for 2020. Grateful to the CS department for their support!
• Excited to give a semi-plenary talk at GAMES'20 in Budapest next summer!
• Here is a survey talk I gave at the Dagstuhl scheduling workshop in Feb'20.
• I gave a keynote talk at WINE'19 in Dec'19. (Slides here.)
• I gave an invited talk on Online Resource Allocation at APPROX'19 in September'19. (Slides here.)


Research

Interests: design and analysis of algorithms, algorithmic game theory and mechanism design, combinatorial and stochastic optimization. I am also interested in algorithmic fairness, algorithmic issues in networks, and machine learning.

Sponsors: I am grateful for the generous support of the National Science Foundation, the Alfred P. Sloan Foundation, and Microsoft Research.


Selected publications and preprints (see complete list on dblp, arxiv, or my Google scholar profile)

Working papers
• Static pricing for multi-unit prophet inequalities, under submission.
• Fairness in ad auctions through inverse proportionality, under submission.
2020
• Pandora's Box with Correlations: Learning and Approximation, FOCS'20.
• The menu-size complexity and revenue continuity of buy-many mechanisms, EC'20.
• Themis: Fair and Efficient GPU Cluster Scheduling, NSDI'20.
• Individual fairness in sponsored search auctions, FAT*'20.
• Revenue Maximization for Query Pricing, PVLDB'20.
2019
• Buy-many mechanisms are not much better than item pricing, EC'19.
• Posted Pricing for Online Resource Allocation: Beyond Subadditive Values, SODA'19.
2018
• Dynamic Query Re-Planning using QOOP, OSDI'18.
• Timing Matters: Online Dynamics in Broadcast Games, WINE'18.
• Aversion to Uncertainty and Its Implications for Revenue Maximization, SODA'18.
• Mechanism Redesign, under submission. This journal version combines and improves upon the EC'14 and EC'16 papers below.
2017
• Truth and Regret in Online Scheduling, EC'17.
• Stability of Service under Time-of-Use Pricing, STOC'17.
2016
• Mechanism design for subadditive agents via an ex-ante relaxation, EC'16.
• A/B testing of auctions, EC'16.
• Simple pricing schemes for consumers with evolving values, (Previously: "How to sell an app?"), SODA'16 (+ talk at GAMES'16).
2015
• Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs, STOC'15.
2014
• A Survey on Bayesian Algorithmic Mechanism Design, SIGecom Letters, 2014.
• Network design with coverage costs, APPROX'14.
• Mechanism design for data science, EC'14.
• Approximate revenue maximization in interdependent value settings, EC'14 (+ talk at GAMES'16).
2013
• Prior-independent mechanisms for scheduling, STOC'13.
• Auctions with Unique Equilibria, EC'13 and AdAuctions'12.
2012
• On the impossibility of black-box transformations in mechanism design, STOC'12.
• A bicriteria approximation for the reordering buffer problem, ESA'12.
• Secretary problems with convex costs, ICALP'12.
• Traffic-redundancy aware network design, SODA'12.
• Optimal Crowdsourcing Contests, SODA'12; invited to Games and Economic Behavior.
2011
• Bayesian mechanism design for budget-constrained agents, EC'11.
• De-Ossifying Internet Routing through Intrinsic Support for End-Network and ISP Selfishness, SIGMETRICS'11 extended abstract.
2010
• The power of randomness in Bayesian optimal mechanism design, EC'10; to appear in Games and Economic Behavior.
• Sequential posted pricing and multi-parameter mechanism design, STOC'10.
• Pricing randomized allocations, SODA'10; invited to Journal of Economic Theory.
• Region growing for multi-route cuts, SODA'10.
• Threshold rules for online sample selection, COCOON'10.
Pre-2010
• The price of anarchy of Bertrand games, EC'09.
• Packing Multiway Cuts in Capacitated Graphs, SODA'09.
• Bertrand Competition in Networks, SAGT'08.


Past and present advisees

Current advisees: Yifeng Teng, Rojin Rezvan, Jeremy McMahan.

Graduate/postdoctoral alumni:
• Siddharth (Sid) Barman (Ph.D. 2012): Postdoc at Caltech CMI --> IISc
• Balasubramanian (Balu) Sivan (Ph.D. 2013): Postdoc at MSR Redmond --> Google Research NY
• David Malec (Ph.D. 2013): Postdoc at U. Maryland --> Cramton Associates
• Seeun (William) Umboh (Ph.D. 2015): Postdoc at Einhoven U. --> U. Sydney
• Amanda Strominger (M.S. 2017): Google Madison.
• Dimitris Paparas (Postdoc 2017): Google.
• Benjamin Miller (Ph.D. 2018): Google, New York.

Undergraduate alumni: Huck Bennett (NYU), Boyan Li (CMU), Andrew Morgan (Wisconsin), Ruimin Zhang (U. Chicago)


Teaching & Service

Current course:    Algorithmic Mechanism Design (CS 880)

Past courses:
     CS 520 Intro to Theoretical Computer Science: Spring 2008
     CS 577 Introduction to Algorithms: Fall 2006, Spring 2010, Fall 2010, Spring 2012, Fall 2012, Fall 2014, Spring 2016, Spring 2017, Spring 2018, Fall 2018, Spring 2020
     CS 787 Advanced Algorithms: Fall 2007, Fall 2009, Spring 2013, Fall 2015, Fall 2016, Spring 2019
     CS 880 Topics in Theory: Spring 2007 (Approximation Algorithms), Spring 2011 (Algorithmic Game Theory),
                  Spring 2015 (Beyond Worst-Case Analysis), Fall 2017 (Algorithms for Massive Datasets), Fall 2019 (Approximation and Online Algorithms)
     CMU 15-859 Randomized Algorithms: Fall 2004

Program Committees: FOCS'06, WINE'07, STOC'08, EC'08, EC'09, WINE'09, ICS'11, SODA'11, EC'11, FSTTCS'11, EC'12, APPROX'12, ITCS'13, STOC'13, EC'13, SAGT'13, EC'14, APPROX'14, FOCS'14, ISMP'15 (co-chair of game theory cluster), WWW'16, EC'16, ICALP'16, NetEcon'16, EC'17, HCOMP'17, EC'18, ESA'18, EC'19, FOCS'19, SODA'20 (chair), WINE'20, EC'21 (co-chair).

Organization committees: First Workshop on Bayesian Mechanism Design (WBMD'11), First Workshop on Algorithmic Game Theory and Data Science (Colocated with ACM EC'15 at FCRC'15), First Workshop on Mathematical Foundations of Human Computation (Colocated with HCOMP'16).

Current/recent editorial boards: SIAM Journal on Discrete Mathematics (2013-2019); ACM Transactions on Algorithms (2014-present); ACM Transactions on Economics and Computation (2015-present).

Other current/recent service commitments: SIGACT exec committee member-at-large; CATCS chair.


Brief Bio

Shuchi Chawla received her Ph.D. from Carnegie Mellon University and her B.Tech. from the Indian Institute of Technology, Delhi. She has held postdoctoral or visiting positions at Stanford University, Microsoft Research Silicon Valley, Microsoft Research Redmond, and the University of Washington. She is the recipient of an NSF Career award and a Sloan Foundation fellowship. She currently serves on the editorial boards of the SIAM Journal on Discrete Mathematics, ACM Transactions on Algorithms, and ACM Transactions on Economics and Computation. Shuchi is a member of the ACM SIGACT executive committee and the current chair of CATCS.
Personal: Shuchi is married to CS professor Aditya Akella and they have two adorable kids.


Contact Information

Please note: I get more email every day than I can respond to. If you email me and don't receive a response within 2-3 days, please send me a reminder.

Office: 4373 Computer Science
Phone: (608) 890 0027
Fax: (608) 262 9777
Mailing Address:
   Computer Sciences Department
   University of Wisconsin - Madison
   1210 W. Dayton Street,
   Madison, WI 53706.
Email: shuchi (AT) cs.wisc.edu