Research

I work on algorithms for problems from the intersection of computer science and economics, including fair resource allocation, algorithmic game theory, and computational social choice. An area of growing interest to me is the application of these principles in algorithmic fairness to machine learning tasks like classification and clustering.

I am motivated by the intersection of algorithmic and normative challenges: what counts as a good and fair solution to problems in resource allocation, voting, or machine learning, and how can we compute such solutions? Many of the relevant techniques for my work come from game theory and approximation algorithms. While I enjoy formalizing problems mathematically, I am also particularly interested in how algorithmic techniques from computer science can yield practical insights for applied systems in the real world, a topic of ever more importance as algorithms take on a more pervasive role in the life of our society.

Algorithms and Fairness

As we consider the impact of data driven machine learning and algorithmic decision making in areas as diverse as granting loans and autonomous vehicles, there is growing concern about designing fair algorithms for making decisions. My particular approach to these problems comes from my background in fair resource allocation problems.

  • Pujol, D., Wu, Y., Fain, B., Machanavajjhala, A. Budget Sharing for Multi-Analyst Differential Privacy. In Proceedings of the 47th International Conference on Very Large Data Bases (VLDB) (2021), pp. 1805-1817 [arxiv link].
  • Lyu, L., Fain, B., Munagala, K., Wang, K. Centrality with Diversity. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining (WSDM) (2021), pp. 644-652. [acm dl link]
  • Chen, X., Fain, B., Lyu, L., Munagala, K. Proportionally Fair Clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML) (2019), pp. 5029–5037. [arxiv link]
  • Fain, B., Munagala, K., and Shah, N. Fair Allocation of Indivisible Public Goods. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC) (2018), pp. 575-592. [arxiv link]
  • Mayuresh K., Fain, B., Munagala, K., and Babu, S. ROBUS: Fair Cache Allocation for Data-parallel Workloads. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD) (2017), pp. 219-234. [arxiv link]
  • Fain, B., Goel, A., and Munagala, K. The Core of The Participatory Budgeting Problem. In Proceedings of the 12th International Conference on Web and Internet Economics (WINE) (2016), pp. 384-399. [arxiv link]

Computational Social Choice

Computational social choice concerns algorithmic issues around voting, or rules for selecting a public outcome given conflicting preferences of the constituency. My work has focused on designing simple algorithms in the implicit utilitarian model to provide welfare approximation guarantees with limited input information.

  • Fain, B., Fan, W., Munagala, K. Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI) (2020), pp. 110-116. [arxiv link]
  • Fain, B., Goel, A., Munagala, K., and Prabhu, N. Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (2019), pp. 1893-1900. [arxiv link]
  • Fain. B., Goel, A., Munagala, K., and Sakshuwong, S. Sequential Deliberation for Social Choice. In Proceedings of the 13th International Conference on Web and Internet Economics (WINE) (2017), pp. 177-190. [arxiv link]

Publications by Date

  1. Pujol, D., Wu, Y., Fain, B., Machanavajjhala, A. Budget Sharing for Multi-Analyst Differential Privacy. In Proceedings of the 47th International Conference on Very Large Data Bases (VLDB) (2021), pp. 1805-1817 [arxiv link].
  2. Lyu, L., Fain, B., Munagala, K., Wang, K. Centrality with Diversity. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining (WSDM) (2021), pp. 644-652. [acm dl link]
  3. Fain, B., Fan, W., Munagala, K. Concentration of Distortion: The Value of Extra Voters in Randomized Social Choice. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI) (2020), pp. 110-116. [arxiv link]
  4. Chen, X., Fain, B., Lyu, L., Munagala, K. Proportionally Fair Clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML) (2019), pp. 5029–5037. [arxiv link]
  5. Fain, B., Goel, A., Munagala, K., and Prabhu, N. Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (2019), pp. 1893-1900. [arxiv link]
  6. Fain, B., Munagala, K., and Shah, N. Fair Allocation of Indivisible Public Goods. In Proceedings of the 2018 ACM Conference on Economics and Computation (EC) (2018), pp. 575-592. [arxiv link]
  7. Fain. B., Goel, A., Munagala, K., and Sakshuwong, S. Sequential Deliberation for Social Choice. In Proceedings of the 13th International Conference on Web and Internet Economics (WINE) (2017), pp. 177-190. [arxiv link]
  8. Mayuresh K., Fain, B., Munagala, K., and Babu, S. ROBUS: Fair Cache Allocation for Data-parallel Workloads. In Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD) (2017), pp. 219-234. [arxiv link]
  9. Fain, B., Goel, A., and Munagala, K. The Core of The Participatory Budgeting Problem. In Proceedings of the 12th International Conference on Web and Internet Economics (WINE) (2016), pp. 384-399. [arxiv link]