See also Google Scholar.

Working Papers

  1. Dropping Standardized Testing for Admissions: Differential Variance and Access [abstract | pdf]
    Nikhil Garg, Hannah Li, and Faidra Monachou
    (Conference version published in FAccT‘21.)

    The University of California suspended through 2024 the requirement that applicants from California submit SAT scores, upending the major role standardized testing has played in college admissions. We study the impact of such decisions and its interplay with other intervention such as affirmative action on admitted class composition. More specifically, this paper develops a theoretical framework to study the effect of requiring test scores on academic merit and diversity in college admissions. The model has a college and set of potential students. Each student an unobserved noisy skill level, and multiple observed application components and group membership. The college is Bayesian and maximizes an objective that depends on both diversity and merit. It estimates each applicant’s true skill level using the observed features, and then admits students with or without affirmative action. We characterize the trade-off between the (potentially positive) informational role of standardized testing in college admissions and its (negative) exclusionary nature. Dropping test scores may exacerbate disparities by decreasing the amount of information available for each applicant, especially those from non-traditional backgrounds. However, if there are substantial barriers to testing, removing the test improves both academic merit and diversity by increasing the size of the applicant pool. The overall effect of testing depends on both the variance of the test score noise and the amount of people excluded by the test requirement. Finally, using application and transcript data from the University of Texas at Austin, we demonstrate how an admissions committee could measure the trade-off in practice.

  2. The Stereotyping Problem in Collaboratively Filtered Recommender Systems [abstract | pdf]
    Wenshuo Guo, Karl Krauth, Michael I. Jordan, and Nikhil Garg

    Recommender systems – and especially matrix factorization-based collaborative filtering algorithms – play a crucial role in mediating our access to online information. We show that such algorithms induce a particular kind of stereotyping: if preferences for a set of items are anti-correlated in the general user population, then those items may not be recommended together to a user, regardless of that user’s preferences and ratings history. First, we introduce a notion of joint accessibility, which measures the extent to which a set of items can jointly be accessed by users. We then study joint accessibility under the standard factorization-based collaborative filtering framework, and provide theoretical necessary and sufficient conditions when joint accessibility is violated. Moreover, we show that these conditions can easily be violated when the users are represented by a single feature vector. To improve joint accessibility, we further propose an alternative modelling fix, which is designed to capture the diverse multiple interests of each user using a multi-vector representation. We conduct extensive experiments on real and simulated datasets, demonstrating the stereotyping problem with standard single-vector matrix factorization models.

  3. Strategic Ranking [abstract]
    Lydia Liu, Nikhil Garg, and Christian Borgs

    Strategic classification studies the design of a classifier robust to the manipulation of input by strategic individuals. However, the existing literature does not consider the effect of competition among individuals as induced by the algorithm design. Motivated by constrained allocation settings such as college admissions, we introduce strategic ranking, in which the (designed) individual reward depends on an applicant’s post-effort rank in a measurement of interest. Our results illustrate how competition among applicants affects the resulting equilibria and model insights. We analyze how various ranking reward designs trade off applicant, school, and societal utility and in particular how ranking design can counter inequities arising from disparate access to resources to improve one’s measured score: We find that randomization in the ranking reward design can mitigate two measures of disparate impact, welfare gap and access, whereas non-randomization may induce a high level of competition that systematically excludes a disadvantaged group.

  4. Test-optional Policies: Overcoming Strategic Behavior and Informational Gaps [abstract | pdf]
    Zhi Liu and Nikhil Garg

    Due to the Covid-19 pandemic, more than 500 US-based colleges and universities went “test-optional” for admissions and promised that they would not penalize applicants for not submitting test scores, part of a longer trend to rethink the role of testing in college admissions. However, it remains unclear how (and whether) a college can simultaneously use test scores for those who submit them, while not penalizing those who do not–and what that promise even means. We formalize these questions, and study how a college can overcome two challenges with optional testing: strategic applicants (when those with low test scores can pretend to not have taken the test), and informational gaps (it has more information on those who submit a test score than those who do not). We find that colleges can indeed do so, if and only if they are able to use information on who has test access and are willing to randomize admissions.

  5. Combatting Gerrymandering with Social Choice: the Design of Multi-member Districts [abstract | pdf]
    Nikhil Garg, Wes Gurnee, David Rothschild, and David Shmoys

    Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States – winner-take-all single-member districts – both enables substantial partisan gerrymandering and constrains ‘fair’ redistricting, preventing proportional representation in legislatures. We study the design of multi-member districts (MMDs), in which each district elects multiple representatives, potentially through a non-winner-takes-all voting rule. We carry out large-scale analyses for the U.S. House of Representatives under MMDs with different social choice functions, under algorithmically generated maps optimized for either partisan benefit or proportionality. Doing so requires efficiently incorporating predicted partisan outcomes – under various multi-winner social choice functions – into an algorithm that optimizes over an ensemble of maps. We find that with three-member districts using Single Transferable Vote, fairness-minded independent commissions would be able to achieve proportional outcomes in every state up to rounding, and advantage-seeking partisans would have their power to gerrymander significantly curtailed. Simultaneously, such districts would preserve geographic cohesion, an arguably important aspect of representative democracies. In the process, we open up a rich research agenda at the intersection of social choice and computational redistricting.

Journal Articles

  1.  2018  Word Embeddings Quantify 100 Years of Gender and Ethnic Stereotypes [abstract | pdf | code & data | talk]
    Nikhil Garg, Londa Schiebinger, Dan Jurafsky, and James Zou
    Proceedings of the National Academy of Sciences (PNAS)
    Media: Stanford News (and EE department), Science Magazine, Smithsonian Magazine (in print), The World Economic Forum, Futurity, etc.

    Word embeddings are a powerful machine-learning framework that represents each English word by a vector. The geometric relationship between these vectors captures meaningful semantic relationships between the corresponding words. In this paper, we develop a framework to demonstrate how the temporal dynamics of the embedding helps to quantify changes in stereotypes and attitudes toward women and ethnic minorities in the 20th and 21st centuries in the United States. We integrate word embeddings trained on 100 y of text data with the US Census to show that changes in the embedding track closely with demographic and occupation shifts over time. The embedding captures societal shifts - e.g., the women’s movement in the 1960s and Asian immigration into the United States - and also illuminates how specific adjectives and occupations became more closely associated with certain populations over time. Our framework for temporal analysis of word embedding opens up a fruitful intersection between machine learning and quantitative social science.

  2.  2019  Iterative Local Voting for Collective Decision-making in Continuous Spaces [abstract | demo | pdf]
    Nikhil Garg, Vijay Kamble, Ashish Goel, David Marn, and Kamesh Munagala
    Journal of Artificial Intelligence Research (JAIR)
    (Conference version published in WWW‘17.)

    Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called Iterative Local Voting for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters’ utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution. We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by various L-Norm balls. We make several observations that inform future implementations of such a procedure.
    We have a demo of our Mechanical Turk experiment available live here. It can be used as follows:
    1. If the URL is entered without any parameters, it uses the current radius (based on previous uses of the demo, going down by $1/N$) and uses the $\mathcal{L}^2$ mechanism.
    2. To set the mechanism, navigate to[option]/, where instead of [option] use either, l1, l2, linf, or full, for the respective mechanisms.
    3. To set the radius, navigate to[number]/, where any integer can be entered instead of [number]. This option resets the starting radius for the specific mechanism, which will go down by $1/N$ in subsequent accesses.
    4. To set both the mechanism and the radius, navigate to[number]/mechanism/[option]/, with the above options.

  3.  2020  Designing Informative Rating Systems: Evidence from an Online Labor Market [abstract | pdf | talk | official link]
    Nikhil Garg and Ramesh Johari
    Manufacturing & Service Operations Management
    Media: New York Times, Stanford Engineering magazine.
    M&SOM student paper award (2nd place), 2020
    (Conference version published in EC‘20.)

    Platforms critically rely on rating systems to learn the quality of market participants. In practice, however, these ratings are often highly inflated, drastically reducing the signal available to distinguish quality. We consider two questions: First, can rating systems better discriminate quality by altering the meaning and relative importance of the levels in the rating system? And second, if so, how should the platform optimize these choices in the design of the rating system? We first analyze the results of a randomized controlled trial on an online labor market in which an additional question was added to the feedback form. Between treatment conditions, we vary the question phrasing and answer choices. We further run an experiment on Amazon Mechanical Turk with similar structure, to confirm the labor market findings. Our tests reveal that current inflationary norms can in fact be countered by re-anchoring the meaning of the levels of the rating system. In particular, scales that are positive-skewed and provide specific interpretations for what each label means yield rating distributions that are much more informative about quality. Second, we develop a theoretical framework to optimize the design of a rating system by choosing answer labels and their numeric interpretations in a manner that maximizes the rate of convergence to the true underlying quality distribution. Finally, we run simulations with an empirically calibrated model and use these to study the implications for optimal rating system design. Our simulations demonstrate that our modeling and optimization approach can substantially improve the quality of information obtained over baseline designs. Overall, our study illustrates that rating systems that are informative in practice can be designed, and demonstrates how to design them in a principled manner.

  4.  2020  Markets for Public Decision-making [abstract | pdf | official link]
    Nikhil Garg, Ashish Goel, and Ben Plaut
    Social Choice and Welfare
    (Conference version published in WINE‘18.)

    A public decision-making problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each issue. We study adaptations of market economies to this setting, focusing on binary issues. Issues have prices, and each agent is endowed with artificial currency that she can use to purchase probability for her preferred alternatives (we allow randomized outcomes). We first show that when each issue has a single price that is common to all agents, market equilibria can be arbitrarily bad. This negative result motivates a different approach. We present a novel technique called "pairwise issue expansion", which transforms any public decision-making instance into an equivalent Fisher market, the simplest type of private goods market. This is done by expanding each issue into many goods: one for each pair of agents who disagree on that issue. We show that the equilibrium prices in the constructed Fisher market yield a "pairwise pricing equilibrium" in the original public decision-making problem which maximizes Nash welfare. More broadly, pairwise issue expansion uncovers a powerful connection between the public decision-making and private goods settings; this immediately yields several interesting results about public decisions markets, and furthers the hope that we will be able to find a simple iterative voting protocol that leads to near-optimum decisions.

  5.  2021  Driver Surge Pricing [abstract | pdf | code & data | talk]
    Nikhil Garg and Hamid Nazerzadeh
    Management Science, Accepted
    (Conference version published in EC‘20.)

    Ride-hailing marketplaces like Uber and Lyft use dynamic pricing, often called surge, to balance the supply of available drivers with the demand for rides. We study pricing mechanisms for such marketplaces from the perspective of drivers, presenting the theoretical foundation that has informed the design of Uber’s new additive driver surge mechanism. We present a dynamic stochastic model to capture the impact of surge pricing on driver earnings and their strategies to maximize such earnings. In this setting, some time periods (surge) are more valuable than others (non-surge), and so trips of different time lengths vary in the opportunity cost they impose on drivers. First, we show that multiplicative surge, historically the standard on ride-hailing platforms, is not incentive compatible in a dynamic setting. We then propose a structured, incentive-compatible pricing mechanism. This closed-form mechanism has a simple form and is well-approximated by Uber’s new additive surge mechanism. Finally, through both numerical analysis and real data from a ride-hailing marketplace, we show that additive surge is more approximately incentive compatible in practice than multiplicative surge, providing more stable earnings to drivers.

Peer Reviewed Conference Proceedings (without journal versions)

  1.  2015  Impact of Dual Slope Path Loss on User Association in HetNets [abstract | pdf]
    Nikhil Garg, Sarabjot Singh, and Jeffrey Andrews
    IEEE Globecom Workshop

    Intelligent load balancing is essential to fully realize the benefits of dense heterogeneous networks. Current techniques have largely been studied with single slope path loss models, though multi-slope models are known to more closely match real deployments. This paper develops insight into the performance of biasing and uplink/downlink decoupling for user association in HetNets with dual slope path loss models. It is shown that dual slope path loss models change the tradeoffs inherent in biasing and reduce gains from both biasing and uplink/downlink decoupling. The results show that with the dual slope path loss models, the bias maximizing the median rate is not optimal for other users, e.g., edge users. Furthermore, optimal downlink biasing is shown to realize most of the gains from downlink-uplink decoupling. Moreover, the user association gains in dense networks are observed to be quite sensitive to the path loss exponent beyond the critical distance in a dual slope model.

  2.  2019  Designing Optimal Binary Rating Systems [abstract | pdf]
    Nikhil Garg and Ramesh Johari
    International Conference on Artificial Intelligence and Statistics (AISTATS ‘19)

    Modern online platforms rely on effective rating systems to learn about items. We consider the optimal design of rating systems that collect binary feedback after transactions. We make three contributions. First, we formalize the performance of a rating system as the speed with which it recovers the true underlying ranking on items (in a large deviations sense), accounting for both items’ underlying match rates and the platform’s preferences. Second, we provide an efficient algorithm to compute the binary feedback system that yields the highest such performance. Finally, we show how this theoretical perspective can be used to empirically design an implementable, approximately optimal rating system, and validate our approach using real-world experimental data collected on Amazon Mechanical Turk.

  3.  2019  Analyzing Polarization in Social Media: Method and Application to Tweets on 21 Mass Shootings [abstract | pdf | code & data]
    Dorottya Demszky, Nikhil Garg, Rob Voigt, James Zou, Jesse Shapiro, Matthew Gentzkow, and Dan Jurafsky
    Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL ‘19)
    Media: Washington Post, Stanford News.

    We provide an NLP framework to uncover four linguistic dimensions of political polarization in social media: topic choice, framing, affect and illocutionary force. We quantify these aspects with existing lexical methods, and propose clustering of tweet embeddings as a means to identify salient topics for analysis across events; human evaluations show that our approach generates more cohesive topics than traditional LDA-based models. We apply our methods to study 4.4M tweets on 21 mass shootings. We provide evidence that the discussion of these events is highly polarized politically and that this polarization is primarily driven by partisan differences in framing rather than topic choice. We identify framing devices, such as grounding and the contrasting use of the terms "terrorist" and "crazy", that contribute to polarization. Results pertaining to topic choice, affect and illocutionary force suggest that Republicans focus more on the shooter and event-specific facts (news) while Democrats focus more on the victims and call for policy changes. Our work contributes to a deeper understanding of the way group divisions manifest in language and to computational methods for studying them.

  4.  2019  Who is in Your Top Three? Optimizing Learning in Elections with Many Candidates [abstract | pdf]
    Nikhil Garg, Lodewijk Gelauff, Sukolsak Sakshuwong, and Ashish Goel
    AAAI Conference on Human Computation and Crowdsourcing (HCOMP ‘19)

    Elections and opinion polls often have many candidates, with the aim to either rank the candidates or identify a small set of winners according to voters’ preferences. In practice, voters do not provide a full ranking; instead, each voter provides their favorite K candidates, potentially in ranked order. The election organizer must choose K and an aggregation rule. We provide a theoretical framework to make these choices. Each K-Approval or K-partial ranking mechanism (with a corresponding positional scoring rule) induces a learning rate for the speed at which the election correctly recovers the asymptotic outcome. Given the voter choice distribution, the election planner can thus identify the rate optimal mechanism. Earlier work in this area provides coarse order-of-magnitude guaranties which are not sufficient to make such choices. Our framework further resolves questions of when randomizing between multiple mechanisms may improve learning, for arbitrary voter noise models. Finally, we use data from 5 large participatory budgeting elections that we organized across several US cities, along with other ranking data, to demonstrate the utility of our methods. In particular, we find that historically such elections have set K too low and that picking the right mechanism can be the difference between identifying the correct winner with only a 80% probability or a 99.9% probability after 500 voters.

  5.  2020  Fair Allocation through Selective Information Acquisition [abstract | pdf]
    William Cai, Johann Gaebler, Nikhil Garg, and Sharad Goel
    AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES ‘20)

    Public and private institutions must often allocate scare resources under uncertainty. Banks, for example, extend credit to loan applicants based in part on their estimated likelihood of repaying a loan. But when the quality of information differs across candidates (e.g., if some applicants lack traditional credit histories), common lending strategies can lead to disparities across groups. Here we consider a setting in which decision makers—before allocating resources—can choose to spend some of their limited budget further screening select individuals. We present a computationally efficient algorithm for deciding whom to screen that maximizes a standard measure of social welfare. Intuitively, decision makers should screen candidates on the margin, for whom the additional information could plausibly alter the allocation. We formalize this idea by showing the problem can be reduced to solving a series of linear programs. Both on synthetic and real-world datasets, this strategy improves utility, illustrating the value of targeted information acquisition in such decisions. Further, when there is social value for distributing resources to groups for whom we have a priori poor information—like those without credit scores—our approach can substantially improve the allocation of limited assets.

Other (workshops and technical reports)

  1.  2013  Multi-Modal, Multi-State, Real-Time Crew State Monitoring System [abstract | pdf]
    Kier Fortier, Nikhil Garg, and Elizabeth Pickering
    NASA Glenn Research Center Research Report

    I helped develop a Real-time, Multi-Modal, Crew State Monitoring System that integrates EEG, GSR, and HRV. I was in charge of overall design, EEG processing, machine learning, and multi-modal integration. I developed robust artifact rejection to detect and remove blinks and other artifacts from the EEG data; EEG feature extraction to represent blocks of data with frequency characteristics, statistical measures, and blink rate; and a machine learning classification system (through Support Vector Machines) that uses the features and characterizes data from a block of time as originating from either a state of rest or a state of concentration. I then integrated EEG and GSR features for joint classification, and we demoed a end-to-end system that collected data from multiple sensors, extracted features, and trained and used the classifier to predict subject state. The system successfully classified 80 percent of subject states.

  2.  2015  Use of Electroencephalography and Galvanic Skin Response in the Prediction of an Attentive Cognitive State [abstract | pdf]
    Beth Lewandowski, Kier Fortier, Nikhil Garg, Victor Rielly, Jeff Mackey, Tristan Hearn, Angela Harrivel, and Bradford Fenton
    Health and Human Performance Research Summit, Dayton, CO

    As part of an effort aimed at improving aviation safety, the Crew State Monitoring Element of the NASA Vehicle Systems Safety Technologies Project is developing a monitoring system capable of detecting cognitive states that may be associated with unsafe piloting conditions. The long term goal is a real-time, integrated system, that uses multiple physiological sensing modalities to detect multiple cognitive states with high accuracy, which can be used to help optimize human performance. Prior to realizing an integrated system, individual sensing modalities are being investigated, including the use of electroencephalographic (EEG) and galvanic skin response (GSR) signals, in the determination of an attentive or inattentive state. EEG and GSR data are collected during periods of rest and as subjects perform psychological tests including the psychomotor vigilance test, the Mackwork clock test and the attention network test. Subjects also perform tasks designed to simulate piloting tasks within the NASA multi-attribute task battery (MATB-II) program. The signals are filtered, the artifacts are rejected and the power spectral density (PSD) of the signals are found. Comparisons of the PSD between the rest and test blocks are made, along with the change in PSD over the time course of the blocks. Future work includes the collection of heart rate data and the investigation of heart rate variability as an additional measure to use in the prediction of attentive state, as well as the investigation of additional EEG signal processing methods such as source localization, multi- scale entropy and coherence measures. Preliminary results will be presented to highlight the methods used and to discuss our hypotheses. The challenges associated with realizing a real-time, accurate, multi-modal, cognitive state monitoring system are numerous. A discussion of some of the challenges will be provided, including real-time artifact rejection methods, quantification of inter- and intra-subject variability, determination of what information within the signals provides the best measurement of attention and determination of how information from the different modalities can be integrated to improve the overall accuracy of the system.

  3.  2015  Fair Use and Innovation in Unlicensed Wireless Spectrum: LTE unlicensed and Wi-Fi in the 5 GHz unlicensed band [pdf]
    Nikhil Garg
    IEEE-USA Journal of Technology and Public Policy

  4.  2016  Transfer Learning: The Impact of Test Set Word Vectors, with Applications to Political Tweets [abstract | pdf]
    Nikhil Garg and Arjun Seshadri

    A major difficulty in applying deep learning in novel domains is the expense associated with acquiring sufficient training data. In this work, we extend literature in deep transfer learning by studying the role of initializing the embedding matrix with word vectors from GLoVe on a target dataset before training models with data from another domain. We study transfer learning on variants of four models (2 RNNs, a CNN, and an LSTM) and three datasets. We conclude that 1) the simple idea of initializing word vectors significantly and robustly improves transfer learning performance, 2) cross-domain learning occurs in fewer iterations than in-domain learning, considerably reduces train time, and 3) blending various out-of-domain datasets before training improves transfer learning. We then apply our models to a dataset of over 400k tweets by politicians, classifying sentiment and subjectivity vs. objectivity. This dataset was provided unlabeled, motivating an unsupervised and transfer learning approach. With transfer learning, we achieve reasonable performance on sentiment classification, but fail in classifying subjectivity vs. objectivity.

  5.  2018  Comparing Voting Methods for Budget Decisions on the ASSU Ballot [abstract | pdf]
    Lodewijk Gelauff, Sukolsak Sakshuwong, Nikhil Garg, and Ashish Goel

    During the 2018 Associated Students of Stanford University (ASSU; Stanford’s student body) election and annual grants process, the Stanford Crowdsourced Democracy Team (SCDT) ran a research ballot and survey to develop insights into voting behavior on the budget component of the ballot (annual grants) where multiple grant requests are considered. We provided voters with additional voting methods for the budget component, collected further insights through a survey and demonstrated the viability of the proposed workflow. Some of our findings are directly relevant to ASSU. Furthermore, the (appropriately anonymized) data gathered in this year’s research ballots is beneficial for research purposes. Overall, our platform and pipeline (PB Stanford) with post-validation of ballots functioned well on a large scale. In particular, the knapsack ballot mechanism shows promise in voter feedback.

  6.  2019  Deliberative Democracy with the Online Deliberation Platform
    James Fishkin, Nikhil Garg, Lodewijk Gelauff, Ashish Goel, Kamesh Munagala, Sukolsak Sakshuwong, Alice Siu, and Sravya Yandamuri
    AAAI Conference on Human Computation and Crowdsourcing Demo Track


  1.  2015  Downlink and Uplink User Association in Dense Next-Generation Wireless Networks [abstract | pdf]
    Nikhil Garg
    Bachelors Thesis, University of Texas at Austin.

  2.  2020  Designing Marketplaces and Civic Engagement Platforms: Learning, Incentives, and Pricing [abstract | pdf | summary | talk | short talk]
    Nikhil Garg
    PhD Dissertation, Stanford University
    INFORMS George Dantzig Dissertation Award, 2020
    ACM SIGecom dissertation award (Honorable mention), 2021

    Platforms increasingly mediate interactions between people: both helping us find work and transportation, and supporting our civic society through discussion and decision-making. Principled system design requires formalizing the platform’s objective and understanding the incentives, behavioral tendencies, and capabilities of participants; in turn, the design influences participant behavior. In this dissertation, I describe work designing platforms in two domains – two-sided marketplaces and civic engagement platforms – combining both theoretical and empirical analyses of such systems. First, I consider the design of surge pricing that is incentive compatible for drivers in ride-hailing platforms. Second, I tackle rating system inflation and design on online platforms. Finally, I study the design and deployment of systems for participatory budgeting. The work in this dissertation has informed deployments at Uber, a large online labor platform, and in participatory budgeting elections across the U.S.