Working Papers

1. Dropping Standardized Testing for Admissions: Differential Variance and Access [abstract | arxiv]
   Nikhil Garg, Hannah Li, and Faidra Monachou
   EAAMO‘21 Best Student Paper Award
   (Conference version published in FAccT‘21 and EAAMO‘21.)
   Appeared in the 2021 NBER Decentralization Conference
   

   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. Combatting Gerrymandering with Social Choice: the Design of Multi-member Districts [abstract | arxiv]
   Nikhil Garg, Wes Gurnee, David Rothschild, and David Shmoys
   Conference version published in ACM Conference on Economics and Computation (EC‘22)
   Media: Cornell Chronicle.
   

   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.
   

3. Equity in Resident Crowdsourcing: Measuring Under-reporting without Ground Truth Data [abstract | arxiv | talk]
   Zhi Liu and Nikhil Garg
   Conference version published in ACM Conference on Economics and Computation (EC‘22)
   

   Modern city governance relies heavily on crowdsourcing (or "co-production") to identify problems such as downed trees and power-lines. A major concern in these systems is that residents do not report problems at the same rates, leading to an inequitable allocation of government resources. However, measuring such under-reporting is a difficult statistical task, as, almost by definition, we do not observe incidents that are not reported. Thus, distinguishing between low reporting rates and low ground-truth incident rates is challenging. We develop a method to identify (heterogeneous) reporting rates, without using external (proxy) ground truth data. Our insight is that rates on duplicate reports about the same incident can be leveraged, to turn the question into a standard Poisson rate estimation task – even though the full incident reporting interval is also unobserved. We apply our method to over 100,000 resident reports made to the New York City Department of Parks and Recreation, finding that there are substantial spatial and socio-economic disparities in reporting rates, even after controlling for incident characteristics.
   

4. Coarse race data conceals disparities in clinical risk score performance [abstract | arxiv]
   Rajiv Movva, Divya Shanmugam, Kaihua Hou, Priya Pathak, John Guttag, Nikhil Garg, and Emma Pierson
   

   Healthcare data in the United States often records only a patient’s coarse race group: for example, both Indian and Chinese patients are typically coded as “Asian.” It is unknown, however, whether this coarse coding conceals meaningful disparities in the performance of clinical risk scores across granular race groups. Here we show that it does. Using data from 418K emergency department visits, we assess clinical risk score performance disparities across granular race groups for three outcomes, five risk scores, and four performance metrics. Across outcomes and metrics, we show that there are significant granular disparities in performance within coarse race categories. In fact, variation in performance metrics within coarse groups often exceeds the variation between coarse groups. We explore why these disparities arise, finding that outcome rates, feature distributions, and the relationships between features and outcomes all vary significantly across granular race categories. Our results suggest that healthcare providers, hospital systems, and machine learning researchers should strive to collect, release, and use granular race data in place of coarse race data, and that existing analyses may significantly underestimate racial disparities in performance.
   

5. Detecting disparities in capacity-constrained allocations [abstract]
   Benjamin Laufer, Emma Pierson, and Nikhil Garg
   

   Government agencies spend substantial resources to maintain infrastructure and respond to residents’ needs. It is important to audit the efficiency and equity of agency decisions: that is, does the agency prioritize the riskiest situations and avoid unduly prioritizing one neighborhood over another? Previous methods for auditing the efficiency and equity of decision-making fail to account for a crucial feature of our setting: government agencies are capacity constrained in how many inspections they can conduct per week, and must make comparative decisions across incidents. In this paper, we first show that existing methods for auditing decision-making for efficiency and equity produce erroneous results in the presence of capacity constraints. We then develop a statistical method – sequential risk adjusted choice modeling – to correctly account for capacity constraints. Finally, we apply our method to analyze allocation decisions made by the New York City Department of Parks and Recreation and find disparities along a number of neighborhood demographic attributes.
   

6. How diverse are accurate recommendations? [abstract]
   Kenny Peng, Manish Raghavan, Emma Pierson, Jon Kleinberg, and Nikhil Garg
   

   Diversity is often considered an axiomatic good in tension with measures of accuracy in settings such as product recommendation, employment, and admissions. Here we show that optimizing for accuracy (i.e., maximizing utility) can naturally promote diversity in recommendations in a range of settings. In our model, an intermediary recommends a set of items for a user to choose from. Each item has a type, and the intermediary is uncertain about which type the user prefers. We theoretically characterize the diversity of the most accurate set. In our main result, we show that (1) when the user is able to utilize all recommended items, the most accurate set is homogeneous, and (2) when the user is only able to utilize a fixed number of items, the amount of diversity depends on the tail behavior of item quality, ranging from equal representation to proportional representation to near-complete homogeneity.
   

7. Balancing Producer Fairness and Efficiency via Bayesian Rating System Design [abstract | arxiv]
   Thomas Ma, Michael Bernstein, Ramesh Johari, and Nikhil Garg
   

   Online marketplaces use rating systems to promote discovery of high quality products. However, these systems also lead to high variance in producers’ economic outcomes: a new producer who sells high-quality items, may, by luck, receive one low rating early on, negatively impacting their popularity with future customers. We investigate the design of rating systems that balance the goals of identifying high quality products ("efficiency") and minimizing the variance in economic outcomes of producers of similar quality (individual "producer fairness"). We observe that there is a trade-off between these two goals: rating systems that promote efficiency are necessarily less individually fair to producers. We introduce Bayesian rating systems as an approach to managing this trade-off. Informally, the systems we propose set a system-wide prior for the quality of an incoming product, and subsequently the system updates that prior to a Bayesian posterior on quality based on user-generated ratings over time. Through calibrated simulations, we show that the strength of the prior directly determines the operating point on the identified trade-off: the stronger the prior, the more the marketplace discounts early ratings data (so individual producer fairness increases), but the slower the platform is in learning about true item quality (so efficiency suffers). Importantly, the prevailing method of ratings aggregation – displaying the sample mean of ratings – is an extreme point in this design space, that maximally prioritizes efficiency at the expense of producer fairness. Instead, by choosing a Bayesian rating system design with an appropriately set prior, a platform can be intentional about the consequential choice of a balance between efficiency and producer fairness.
   

8. Supply-Side Equilibria in Recommender Systems [abstract | arxiv]
   Meena Jagadeesan, Nikhil Garg, and Jacob Steinhardt
   

   Digital recommender systems such as Spotify and Netflix affect not only consumer behavior but also producer incentives: producers seek to supply content that will be recommended by the system. But what content will be produced? In this paper, we investigate the supply-side equilibria in content recommender systems. We model users and content as D-dimensional vectors, and recommend the content that has the highest dot product with each user. The main features of our model are that the producer decision space is high-dimensional and the user base is heterogeneous. This gives rise to new qualitative phenomena at equilibrium: First, the formation of genres, where producers specialize to compete for subsets of users. Using a duality argument, we derive necessary and sufficient conditions for this specialization to occur. Second, we show that producers can achieve positive profit at equilibrium, which is typically impossible under perfect competition. We derive sufficient conditions for this to occur, and show it is closely connected to specialization of content. In both results, the interplay between the geometry of the users and the structure of producer costs influences the structure of the supply-side equilibria. At a conceptual level, our work serves as a starting point to investigate how recommender systems shape supply-side competition between producers.
   

Journal Articles

1.  2018  Word Embeddings Quantify 100 Years of Gender and Ethnic Stereotypes [abstract | official link | 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 | official link]
   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 http://54.183.140.235/mechanism/[option]/, where instead of [option] use either, l1, l2, linf, or full, for the respective mechanisms.
   3. To set the radius, navigate to http://54.183.140.235/mechanism/[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 http://54.183.140.235/radius/[number]/mechanism/[option]/, with the above options.

3.  2020  Designing Informative Rating Systems: Evidence from an Online Labor Market [abstract | arxiv | 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 | arxiv | 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 | ssrn | code & data | talk | official link]
   Nikhil Garg and Hamid Nazerzadeh
   Management Science
   (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 | official link]
   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 | official link]
   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 | arxiv | 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 | arxiv]
   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 | arxiv]
   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.
   

6.  2021  Test-optional Policies: Overcoming Strategic Behavior and Informational Gaps [abstract | arxiv]
   Zhi Liu and Nikhil Garg
   AAAI/ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO‘21)
   

   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.
   

7.  2021  The Stereotyping Problem in Collaboratively Filtered Recommender Systems [abstract | arxiv]
   Wenshuo Guo, Karl Krauth, Michael I. Jordan, and Nikhil Garg
   AAAI/ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization (EAAMO‘21)
   

   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.
   

8.  2022  Strategic Ranking [abstract | arxiv]
   Lydia Liu, Nikhil Garg, and Christian Borgs
   International Conference on Artificial Intelligence and Statistics (AISTATS‘22)
   

   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.
   

9.  2022  Fair ranking: a critical review, challenges, and future directions [abstract | arxiv | official link]
   Gourab K Patro, Lorenzo Porcaro, Laura Mitchell, Qiuyue Zhang, Meike Zehlike, and Nikhil Garg
   ACM Conference on Fairness, Accountability, and Transparency (FAccT‘22)
   This work was written as part of a distributed, student-led working group of Mechanism Design for Social Good
   

   Ranking, recommendation, and retrieval systems are widely used in online platforms and other societal systems, including e-commerce, media-streaming, admissions, gig platforms, and hiring. In the recent past, a large "fair ranking" research literature has been developed around making these systems fair to the individuals, providers, or content that are being ranked. Most of this literature defines fairness for a single instance of retrieval, or as a simple additive notion for multiple instances of retrievals over time. This work provides a critical overview of this literature, detailing the often context-specific concerns that such an approach misses: the gap between high ranking placements and true provider utility, spillovers and compounding effects over time, induced strategic incentives, and the effect of statistical uncertainty. We then provide a path forward for a more holistic and impact-oriented fair ranking research agenda, including methodological lessons from other fields and the role of the broader stakeholder community in overcoming data bottlenecks and designing effective regulatory environments.
   

10.  2022  Trucks Don’t Mean Trump: Diagnosing Human Error in Image Analysis [abstract | arxiv | official link]
    J.D. Zamfirescu-Pereira, Jerry Chen, Emily Wen, Allison Koenecke, Nikhil Garg, and Emma Pierson
    ACM Conference on Fairness, Accountability, and Transparency (FAccT‘22)
    Media: Cornell News.
    

    Algorithms provide powerful tools for detecting and dissecting human bias and error. Here, we develop machine learning methods to to analyze how humans err in a particular high-stakes task: image interpretation. We leverage a unique dataset of 16,135,392 human predictions of whether a neighborhood voted for Donald Trump or Joe Biden in the 2020 US election, based on a Google Street View image. We show that by training a machine learning estimator of the Bayes optimal decision for each image, we can provide an actionable decomposition of human error into bias, variance, and noise terms, and further identify specific features (like pickup trucks) which lead humans astray. Our methods can be applied to ensure that human-in-the-loop decision-making is accurate and fair and are also applicable to black-box algorithmic systems.
    

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
   

Theses

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

   5G, the next-generation cellular network, must serve an aggregate data rate of 1000 times that of current 4G networks while reducing data latency by a factor of ten. To meet these requirements, 5G networks will be far denser than existing networks, and small cells (femtocells and picocells) will augment network capacity. However, dense networks raise questions regarding interference, user association, and handoff between base stations. Where recent papers have demonstrated that interference from small cells will not be prohibitive under multi-slope path loss models, this thesis describes how the use of different path loss models affects the design of such dense, multi-tier networks. This thesis concludes that the gains realized by downlink biasing and uplink/downlink decoupling are strongly dependent on the path loss model assumed and the density differential between base station tiers. Furthermore, this thesis argues that the gains from uplink/downlink decoupling are reduced by a factor of 50% when optimal biasing for the downlink is used.
   

2.  2020  Designing Marketplaces and Civic Engagement Platforms: Learning, Incentives, and Pricing [abstract | official link | 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.