Influence in Classification via Cooperative Game Theory

1 Introduction

A recent white house report [Podesta et al., 2014] highlights some of the major risks in the ubiquitous use of big data technologies. According to the report, one of the major issues with large scale data collection and analysis is a glaring lack of transparency. For example, a credit reporting company collects consumer data from third parties, and uses machine learning analysis to estimate individuals' credit score. On the one hand, this method is "impartial": an emotionless algorithm cannot be accused of being malicious (discriminatory behavior is not hard-coded). However, it is hardly transparent; indeed, it is difficult to tease out the determinants of one's credit score: it depends on the user's financial activities, age, address, the behavior of similar users and many other factors. This is a major issue: big-data analysis does not intend to discriminate, but inadvertent discrimination does occur: treating users differently based on unfair criteria (e.g. online retailers offering different discounts or goods based on place of residence or past purchases).

In summary, big data analysis leaves users vulnerable. They may be discriminated against, and no one (including the algorithm's developers!) may even know why; what's worse, traditional methods for preserving user anonymity (e.g. by "opting out" of data collection) offer little protection; big data techniques allow companies to infer individuals' data based on similar users [Barocas and Nissenbaum, 2014]. Since it is often difficult to "pop the hood" and understand the inner workings of classification algorithms, maintaining transparency in classification is a major challenge. In more concrete terms, transparency can be interpreted as understanding what influences the decisions of a black-box classifier. This is where our work comes in.

Suppose that we are given a dataset B of users; here, every user a ∈ B can be thought of as a vector of features (e.g. a = (age, gender, IP address . . . )), where the i-th coordinate of a corresponds to the state of the i-th feature. Each a has a value v(a) (say, the credit score of a). We are interested in the following question: given a dataset B of various feature vectors and their values, how influential was each feature in determining these values?

In more detail, given a set N = {1, . . . , n} of features, a dataset B of feature profiles, where every profile a has a value v(a), we would like to compute a measure φi(N, B, v) that corresponds to feature i's importance in determining the labels of the points in B. We see this work as an important first step towards a concrete methodology for transparency analysis of big-data algorithms.

Our Contribution: We take an axiomatic approach - which draws heavily on cooperative game theory - to define an influence measure. The merit of our approach lies in its independence of the underlying structure of the classification function; all we need is to collect data on its behavior.

We show that our influence measure is the unique measure satisfying some natural properties (Section 2). As a case study, we show that when the input values are given by a linear classifier, our influence measure has an intuitive geometric interpretation (Section 3). Finally, we show that our axioms can be extended in order to obtain other influence measures (Section 4). For example, our axioms can be used to obtain a measure of state influence, as well as influence measures where a prior distribution on the data is assumed, or a measure that uses pseudo-distance between user profiles to measure influence.

We complement our theoretical results with an implementation of our approach, which serves as a proof of concept (Section 5). Using our framework, we identify ads where certain user features have a significant influence on whether the ad is shown to users. Our experiments show that our influence measures behave in a desirable manner. In particular, a Spanish language ad - clearly biased towards Spanish speakers - demonstrated the highest influence of any feature among all ads.

A full version of this paper, which includes the full proofs, appears as a Cylab technical report (CMU-CyLab-15-001). 1

1.1 RelatedWork

Axiomatic characterizations have played an important role in the design of provably fair revenue divisions [Shapley, 1953; Young, 1985; Banzhaf, 1965; Lehrer, 1988]. Indeed, one can think of the setting we describe as a generalization of cooperative games, where agents can have more than one state - in cooperative games, agents are either present or absent from a coalition. Some papers extend cooperative games to settings where agents have more than one state, and define influence measures for such settings [Chalkiadakis et al., 2010; Zick et al., 2014]; however, our setting is far more general.

Our definition of influence measures the ability of a feature to affect the classification outcome if changed (e.g. how often does a change in gender cause a change in the display frequency of an ad); this idea is used in the analysis of cause [Halpern and Pearl, 2005; Tian and Pearl, 2000], and responsibility [Chockler and Halpern, 2004]; our influence measure can be seen as an application of these ideas to a classification setting.

Influence measures are somewhat related to feature selection [Blum and Langley, 1997]. Feature selection is the problem of finding the set of features that are most relevant to the classification task, in order to improve the performance of a classifier on the data; that is, it is the problem of finding a subset of features, such that if we train a classifier using just those features, the error rate is minimized. Some of the work on feature selection employs feature ranking methods; some even use the Shapley value as a method for selecting the most important features [Cohen et al., 2005]. Our work differs from feature selection both in its objectives and its methodology. Our measures can be used in order to rank features, but we are not interested in training classifiers; rather, we wish to decide which features influence the decision of an unknown classifier. That said, one can certainly employ our methodology in order to rank features in feature selection tasks.

When the classifier is linear, our influence measures take on a particularly intuitive interpretation as the aggregate volume between two hyperplanes [Marichal and Mossinghoff, 2006].

Recent years have seen tremendous progress on methods to enhance fairness in classification [Dwork et al., 2012; Kamishima et al., 2011], user privacy [Balebako et al., 2012; Pedreschi et al., 2008; Wills and Tatar, 2012] and the prevention of discrimination [Kamiran and Calders, 2009; Calders and Verwer, 2010; Luong et al., 2011]. Our work can potentially inform all of these research thrusts: a classifier can be deemed fair if the influence of certain features is low; for example, high gender influence may indicate discrimination against a certain gender. In terms of privacy, if a hidden feature (i.e. one that is not part of the input to the classifier)

1 https://www.cylab.cmu.edu/research/techreports/2015/ tr cylab15001.html

has high influence, this indicates a possible breach of user privacy.

2 Axiomatic Characterization

We begin by briefly presenting our model. Given a set of features N = {1, . . . , n}, let Ai be the set of possible values, or states that feature i can take; for example, the i-th feature could be gender, in which case Ai = {male, female, other}. We are given partial outputs of a function over a dataset containing feature profiles. That is, we are given a subset B of A = ∏i∈N Ai, and a valuation v(a) for every a ∈ B. By given, we mean that we do not know the actual structure of v, but we know what values it takes over the dataset B. Formally, our input is a tuple G = 〈N, B, v〉, where v : A → Q is a function assigning a value of v(a) to each data point a ∈ B. We refer to G as the dataset. When v(a) ∈ {0, 1} for all a ∈ B, v is a binary classifier. When B = A and |Ai| = 2 for all i ∈ N, the dataset corresponds to a standard TU cooperative game [Chalkiadakis et al., 2011] (and is a simple game if v(a) ∈ {0, 1}).

We are interested in answering the following question: how influential is feature i? Our desired output is a measure φi(G) that will be associated with each feature i. The measure φi(G) should be a good metric of the importance of i in determining the values of v over B.

Our goal in this section is to show that there exists a unique influence measure that satisfies certain natural axioms. We begin by describing the axioms, starting with symmetry.

Given a dataset G = 〈N,B, v〉 and a bijective mapping σ from N to itself, we define σG = 〈σN, σB, σv〉 in the natural way: σN has all of the features relabeled according to σ (i.e. the index of i is now σ(i)); σB is {σa | a ∈ B}, and σv(σa) = v(a) for all σa ∈ σB. Given a bijective mapping τ : Ai → Ai over the states of some feature i ∈ N, we define τG = 〈N, τB, τv〉 in a similar manner.

Definition 2.1. An influence measure φ satisfies the feature symmetry property if it is invariant under relabelings of features: given a dataset G = 〈N,B, v〉 and some bijection σ : N → N, φi(G) = φσ(i)(σG) for all i ∈ N. A influence measure φ satisfies the state symmetry property if it is invariant under relabelings of states: given a dataset G = 〈N,B, v〉, some i ∈ N, and some bijection τ : Ai → Ai, φj(G) = φj(τG) for all j ∈ N. Note that it is possible that i ̸= j. A measure satisfying both state and feature symmetry is said to satisfy the symmetry axiom (Sym).

Feature symmetry is a natural extension of the symmetry axiom defined for cooperative games (see e.g. [Banzhaf, 1965; Lehrer, 1988; Shapley, 1953]). However, state symmetry does not make much sense in classic cooperative games; it would translate to saying that for any set of players S ⊆ N and any j ∈ N, the value of i is the same if we treat S as S \{j}, and S \{j} as S. While in the context of cooperative games this is rather uninformative, we make non-trivial use of it in what follows.

We next describe a sufficient condition for a feature to have no influence: a feature should not have any influence if it does not affect the outcome in any way. Formally, a feature i ∈ N is a dummy if v(a) = v(a-i, b) for all a ∈ B, and all b ∈ Ai such that (a-i, b) ∈ B; here a-i is the vector a with the i-th coordinate omitted, and (a-i, b) is the vector a with the i-th coordinate set to b.

Definition 2.2. An influence measure φ satisfies the dummy (D) property if φi(G) = 0 whenever i is a dummy in the dataset G.

The dummy property is a standard extension of the dummy property used in value characterizations in cooperative games. However, when dealing with real datasets, it may very well be that there is no vector a ∈ B such that (a-i, b) ∈ B; this issue is discussed further in Section 6.

Cooperative game theory employs a notion of value additivity in the characterization of both the Shapley and Banzhaf values. Given two datasets G1 = 〈N,B, v1〉, G2 = 〈N,B, v2〉, we define G = 〈N,A, v〉 = G1 + G2 with v(a) = v1(a) + v2(a) for all a ∈ B.

Definition 2.3. An influence measure φ satisfies additivity (AD) if φi(G1 +G2) = φi(G1) +φi(G2) for any two datasets G1 = 〈N, B, v1〉, G2 = 〈N, B, v2〉.

The additivity axiom is commonly used in the axiomatic analysis of revenue division in cooperative games (see [Lehrer, 1988; Shapley, 1953]); however, it fails to capture a satisfactory notion of influence in our more general setting. We now show that any measure that satisfies additivity, in addition to the symmetry and dummy properties, must evaluate to zero for all features. To show this, we first define the following simple class of datasets.

Definition 2.4. Let Ua = 〈N,A, ua〉 be the dataset defined by the classifier ua, where ua(a′ ) = 1 if a′ = a, and is 0 otherwise. The dataset Ua is referred to as the singleton dataset over a.

It is an easy exercise to show that additivity implies that for any scalar α ∈ Q, φi(αG) = αφi(G), where the dataset αG has the value of every point scaled by a factor of α.

We emphasize that in all proofs appearing in this section we assume for ease of exposition that B = A, i.e. we are given all possible profiles. Our results can be extended to the general case (though the extension is at times non-trivial).

Proposition 2.5. Any influence measure that satisfies the (Sym), (D) and (AD) axioms evaluates to zero for all features.

Proof. First, we show that for any a, a′ ∈ A and any b ∈ Ai, it must be the case that φi(U(a-i,b)) = φi(U(a′-i ,b)). This is true because we can define a bijective mapping from U(a-i,b) to U(a′-i ,b): for every j ∈ N \ {i}, we swap aj and a′j . By state symmetry, φi(U(a-i,b)) = φi(U(a′-i ,b)).

Next, if φ is additive, then for any dataset G = 〈N,A, v〉, φi(G) = ∑a∈A v(a)φi(Ua). That is, the influence of a feature must be the sum of its influenceover singleton datasets, scaled by v(a).

Now, suppose for contradiction that there exists some singleton dataset U¯a (¯a ∈ A) for which some feature i ∈ N does not have an influence of zero. That is, we assume that φi(U¯a) ̸= 0. We define a dataset G = 〈N,A, v〉 in the following manner: for all a ∈ A such that a-i = ¯a-i, we set v(a) = 1, and v(a) = 0 if a-i ̸= ¯a-i. In the resulting dataset, v(a) is solely determined by the values of features in N \ {i}; in other words v(a) = v(a-i, b) for all b ∈ Ai, hence feature i is a dummy. According to the dummy axiom, we must have that φi(G) = 0; however,

where the first equality follows from the decomposition of G into singleton datasets, and the third equality holds by Symmetry, a contradiction.

As Proposition 2.5 shows, the additivity, symmetry and dummy properties do not lead to a meaningful description of influence. A reader familiar with the axiomatic characterization of the Shapley value [Shapley, 1953] will find this result rather disappointing: the classic characterizations of the Shapley and Banzhaf values assume additivity (that said, The axiomatization by Young [1985] does not assume additivity).

We now show that there is an influence measure uniquely defined by an alternative axiom, which echoes the unionintersection property described by Lehrer [1988]. In what follows, we assume that all datasets are classified by a binary classifier. We write W(B) to be the set of all profiles in B such that v(a) = 1, and L(B) to be the set of all profiles in B that have a value of 0. We refer to W(B) as the winning profiles in B, and to L(B) as the losing profiles in B. We can thus write φi(W(B),L(B)), rather than φi(G). Given two disjoint sets W,L ⊆ A, we can define the dataset as G = 〈W,L〉, and the influence of i as φi(W,L), without explicitly writing N, B and v. As we have seen, no measure can satisfy the additivity axiom (as well as symmetry and dummy axioms) without being trivial. We now propose an alternative influence measure, captured by the following axiom:

Definition 2.6. An influence measure φ satisfies the disjoint union (DU) property if for any Q ⊆ A, and any disjoint R,R′ ⊆ A \ Q, φi(Q,R) + φi(Q,R′ ) = φi(Q,R ∪ R′ ), and φi(R, Q) + φi(R′ , Q) = φi(R ∪ R′ , Q).

An influence measure φ satisfying the (DU) axiom is additive with respect to independent observations of the same type. Suppose that we are given the outputs of a binary classifier on two datasets: G1 = 〈W, L1〉 and G2 = 〈W, L2〉. The (DU) axiom states that the ability of a feature to affect the outcome on G1 is independent of its ability to affect the outcome in G2, if the winning states are the same in both datasets.

Replacing additivity with the disjoint union property yields a unique influence measure, with a rather simple form.

χ measures the number of times that a change in the state of i causes a change in the classification outcome. If we normalize χ and divide by |B|, the resulting measure has the following intuitive interpretation: pick a vector a ∈ B uniformly at random, and count the number of points in Ai for which (a-i, b) ∈ B and i changes the value of a. We note that when all features have two states and B = A, χ coincides with the (raw) Banzhaf power index [Banzhaf, 1965].

We now show that χ is a unique measure satisfying (D), (Sym) and (DU). We begin by presenting the following lemma, which characterizes influence measures satisfying (D), (Sym) and (DU) when dataset contains only a single feature. Again, we assume here that B = A.

Lemma 2.7. Let φ be an influence measure that satisfies state symmetry, and let G1 = 〈{i}, Ai, v1〉 and G2 = 〈{i}, Ai, v2〉 be two datasets with a single feature i; if the number of winning profiles under G1 and G2 is identical, then φi(G1) = φi(G2).

Proof Sketch. We simply construct a bijective mapping from the winning states of i under G1 and its winning states in G2. By state symmetry, φi(G1) = φi(G2).

Lemma 2.7 implies that for single feature games, the value of a feature only depends on the number of winning states, rather than their identity.

We are now ready to show the main theorem for this section: χ is the unique influence measure satisfying the three axioms above, up to a constant factor.

Theorem 2.8. An influence measure φ satisfies (D), (Sym) and (DU) if and only if there exists a constant C such that for every dataset G = 〈N, A, v〉 and all i ∈ N,

Proof. It is an easy exercise to verify that χ satisfies the three axioms, so we focus on the "only if" direction. Let us write W = W(A) and L = L(A). Given some a-i ∈ A-i, we write La-i = {¯a ∈ L | a-i = ¯a-i}, and Wa-i = {¯a ∈ W | a-i = ¯a-i}.

Using the disjoint union property, we can decompose φi(W, L) as follows:

Now, if ¯a-i ̸= a-i, then feature i is a dummy given the dataset provided. Indeed, state profiles are either in Wa-i or in L¯a-i ; that is, if v(a-i, b) = 0, then (a-i, b) is unobserved, and if v(¯a-i, b) = 1, then (¯a-i, b) is unobserved. We conclude that

Let us now consider φi(Wa-i ,La-i ). Since φ satisfies state symmetry, Lemma 2.7 implies that φi can only possibly depend on a-i, |Wa-i | and |La-i |. Next, for any a-i and a′-i such that |La-i | = |La′-i | and |Wa-i | = |Wa′-i |, so by Lemma 2.7 φi(Wa-i ,La-i ) = φi(Wa′-i ,La′-i ). In other words φi only depends on |Wa-i |, |La-i |, and not on the identity of a-i.

Thus, one can see φi for a single feature as a function of two parameters, w and l in N, where w is the number of winning states and l is the number of losing states. According to the dummy property, we know that φi(w, 0) = φi(0, l) = 0; moreover, the disjoint union property tells us that φi(x, l) +

φi(y, l) = φi(x + y, l), and that φi(w, x) + φi(w, y) = φi(w, x + y). We now show that φi(w, l) = φi(1, 1)wl.

Our proof is by induction on w+l. For w+l = 2 the claim is clear. Now, assume without loss of generality that w > 1 and l ≥ 1; then we can write w = x + y for x, y ∈ N such that 1 ≤ x, y < w. By our previous observation,

Now, φi(1, 1) is the influence of feature i when there is exactly one losing state profile, and one winning state profile. We write φi(1, 1) = ci.

Let us write Wi(a-i) = {b ∈ Ai | v(a-i, b) = 1} and Li(a-i) = Ai \ Wi(a-i). Thus, |Wa-i | = |Wi(a-i)|, and |La-i | = |Li(a-i)|. Putting it all together, we get that

We just need to show that the measure given in (4) equals χi (modulo ci). Indeed, (4) equals ∑a∈A: v(a)=0 |Wi(a-i)|, which in turn equals ∑a∈A: v(a)=0 ∑b∈Ai |v(a-i, b)-v(a)|. Similarly, (4) equals

in particular, for every dataset G = 〈N,A, v〉 and every i ∈ N, there is some constant Ci such that φi(G) = Ciχi(G). To conclude the proof, we must show that Ci = Cj for all i, j ∈ N. Let σ : N → N be the bijection that swaps i and j; then φi(G) = φσ(i)(σG). By feature symmetry, Ciχi(G) = φi(G) = φσ(i)(σG) = φj(σG) = Cjχj(σG) = Cjχi(G), thus Ci = Cj .

3 Case Study: Influence for Linear Classifiers

To further ground our results, we now present their application to the class of linear classifiers. For this class of functions, our influence measure takes on an intuitive interpretation.

A linear classifier is defined by a hyperplane in Rn ; all points that are on one side of the hyperplane are colored blue (in our setting, have value 1), and all points on the other side are colored red (have a value of 0). Formally, we associate a weight wi ∈ R with every one of the features in N (we assume that wi ̸= 0 for all i ∈ N); a point x ∈ Rn is blue if x· w ≥ q, where q ∈ R is a given parameter. The classification function v : Rn → {0, 1} is given by v(x) = 1 if x · w ≥ q, and v(x) = 0 otherwise.

Fixing the value of xi to some b ∈ R, let us consider the set Wi(b) = {x-i ∈ Rn-1 | v(x-i, b) = 1}; we observe that if b < b′ and wi > 0, then Wi(b) ⊂ Wi(b′ ) (if wi < 0 then Wi(b′ ) ⊂ Wi(b)). Given two values b, b′ ∈ R, we denote by

By our previous observation, if b < b′ then Di(b, b′ ) = Wi(b′ )\Wi(b), and if b > b′ then Di(b, b′ ) = Wi(b)\Wi(b′ ).

Suppose that rather than taking points in Rn , we only take points in [0, 1]n ; then we can define |Di(b, b′ )| = Vol (Di(b, b′ )), where

In other words, in order to measure the total influence of setting the state of feature i to b, we must take the total volume of Di(b, b′ ) for all b′ ∈ [0, 1], which equals ∫ 1 b′=0 Vol(Di(b, b′ ))∂b. Thus, the total influence of setting the state of i to b is ∫x∈[0,1]n |v(x-i, b) - v(x)|∂x. The total influence of i would then be naturally the total influence of its states, i.e.

The formula in Equation (5) is denoted by χi(w; q). Equation (1) is a discretized version of Equation (5); the results of Section 2 can be extended to the continuous setting, with only minimal changes to the proofs.

We now show that the measure given in (5) agrees with the weights in some natural manner. This intuition is captured in Theorem 3.1 (proof omitted).

Theorem 3.1. Let v be a linear classifier defined by w and q; then χi(G) ≥ χj(G) if and only if |wi| ≥ |wj|.

Given Theorem 3.1, one would expect the following to hold: suppose that we are given two weight vectors, w,w′ ∈ Rn such that wj = w′j for all j ̸= i, but wi < w′i . Let v be the linear classifier defined by w and q and v′ be the linear classifier defined by w′ and q. Is it the case that feature i is more influential under v′ than under v? In other words, does influence monotonicity hold when we increase the weight of an individual feature? The answer to this is negative.

Example 3.2. Let us consider a single feature game where N = {1}, A1 = [0, 1], and v(x) = 1 if wx ≥ q, and v(x) = 0 if wx < q for a given w > q. The fraction of times that 1 is pivotal is

simplifying, this expression is equal to (1- qw ) qw . We can show that χ1 = 2|Piv1|, we have that χ1 is maximized when q = 2w; in particular, χ1 is monotone increasing when q < w ≤ 2q, and it is monotone decreasing when w ≥ 2q.

Example 3.2 highlights the following phenomenon: fixing the other features to be a-i, the influence of i is maximized when |La-i | = |Wa-i |. This can be interpreted probabilistically: we sample a random feature from B, and assume that for any fixed a-i ∈ A-i, Pr[v(a-i, b) = 1] = 12 . The better a feature i agrees with our assumption, the more i is rewarded. More generally, an influence measure satisfies the agreement with prior assumption (APA) axiom if for any vector (p1, . . . , pn) ∈ [0, 1]n , and any fixed a-i ∈ A-i, i's influence increases as |Pr[v(a-i, b) = 1] - pi| decreases. A

variant of the symmetry axiom (that reflects changes in probabilities when labels change), along with the dummy and disjoint union axioms can give us a weighted influence measure as described in Section 4.2, that also satisfies the (APA) axiom.

4 Extensions of the Feature Influence Measure

Section 2 presents an axiomatic characterization of feature influence, where the value of each feature vector is either zero or 1. We now present a few possible extensions of the measure, and the variations on the axioms that they require.

4.1 State Influence

Section 2 provided an answer to questions of the following form: what is the impact of gender on classification outcomes? The answer provided in previous sections was that influence was a function of the feature's ability to change outcomes by changing its state.

It is also useful to ask a related question: what is the impact of the gender feature being set to "female" on classification outcomes? In other words, rather than measuring feature influence, we are measuring the influence of feature i being in a certain state. The results described in Section 2 can be easily extended to this setting. Moreover, the impossibility result described in Proposition 2.5 no longer holds when we measure state - rather than feature - influence: we can replace the disjoint union property with additivity to obtain an alternative classification of state influence.

4.2 Weighted Influence

Suppose that in addition to the dataset B, we are given a weight function w : B → R. w(a) can be thought of as the number of occurrences of the vector a in the dataset, the probability that a appears, or some intrinsic importance measure of a. Note that in Section 2 we implicitly assume that all points occur at the same frequency (are equally likely) and are equally important. A simple extension of the disjoint union and symmetry axioms to a weighted variant shows that the only weighted influence measure that satisfies these axioms is

4.3 General Distance Measures

Suppose that instead of a classifier v : A → {0, 1} we are given a pseudo-distance measure: that is, a function d : A× A → R that satisfies d(a, a′ ) = d(a′ , a), d(a, a) = 0 and the triangle inequality. Note that it is possible that d(a, a′ ) = 0 but a ̸= a′ . An axiomatic analysis in such general settings is possible, but requires more assumptions on the behavior of the influence measure. Such an axiomatic approach leads us to show that the influence measure

is uniquely defined via some natural axioms. The additional axioms are a simple extension of the disjoint union property, and a minimal requirement stating that when B = {a, (a-i, b)}, then the influence of a feature is αd((a-i, b), a) for some constant α independent of i. The extension to pseudo-distances proves to be particularly useful when we conduct empirical analysis of Google's display ads system, and the effects user metrics have on display ads.

5 Implementation

We implement our influence measure to study Google's display advertising system. Users can set demographics (like gender or age) on the Google Ad Settings page 2 ; these are used by the Google ad serving algorithm to determine which ads to serve. We apply our influence measure to study how demographic settings influence the targeted ads served by Google. We use the AdFisher tool [Datta et al., 2014] for automating browser activity and collect ads.

We pick the set of features: N = {gender, age, language}. Feature states are {male, female} for gender, {18-24, 3544, 55 - 64} for age, and {English, Spanish} for language; this gives us 2×3×2 = 12 possible user profiles. Using AdFisher, we launch twelve fresh browser instances, and assign each one a random user profile. For each browser instance, the corresponding settings are applied on the Ad Settings page, and Google ads on the BBC news page bbc.com/news are collected. For each browser, the news page is reloaded 10 times with 5 second intervals.

To eliminate ads differing due to random chance, we collect ads over 100 iterations, each comprising of 12 browser instances, thereby obtaining data for 1200 simulated users. In order to minimize confounding factors such as location and system specifications, all browser instances were run from the same stationary Ubuntu machine. The 1200 browsers received a total of 32, 451 ads (763 unique); in order to reduce the amount of noise, we focus only on ads that were displayed more than 100 times, leaving a total of 55 unique ads. Each user profile a thus has a frequency vector of all ads v′ (a) ∈ N55 , where the kth coordinate is the number of times ad k appeared for a user profile a. We normalize v′ (a) for each ad by the total number of times that ad appeared. Thus we obtain the final value-vectors by computing vk(a) = v′k (a)

Since user profile values are vectors, we use the general distance influence measure described in Section 4.3. The pseudo-distance we use is Cosine similarity: cosd(x, y) = 1 - x·y ||x||·||y|| ; this has been used Cosine similarity has been used by Tschantz et al. [2014] and Guha et al. [2010] to measure similarity between display ads. The influence measure for gender, age, and language were 0.124, 0.120, and 0.141 respectively; in other words, no specific feature has a strong influence over ads displayed.

We next turn to measuring feature effects on specific ads. Fixing an ad k, we define the value of a feature vector to be the number of times that ad k was displayed for users with that feature vector, and use χ to measure influence.

We compare the influence measures for each attribute across all the ads and identify the top ads that demonstrate high influence. The ad for which language had the highest influence (0.167) was a Spanish language ad, which was served only to browsers that set 'Spanish' as their language on the Ad Settings page. Comparing with statistics like mean and maximum over measures across all features given in Table 1, we can see that this influence was indeed high.

2 google.com/settings/ads

To conclude, using a general distance measure between two value-vectors, we identify that language has the highest influence on ads. By using a more fine-grained distance function, we can single out one ad which demonstrates high influence for language. While in this case the bias is acceptable, the experiment suggests that our framework is effective in pinpointing biased or discriminatory ads.

6 Conclusions and FutureWork

In this work, we analyze influence measures for classification tasks. Our influence measure is uniquely defined by a set of natural axioms, and is easily extended to other settings. The main advantage of our approach is the minimal knowledge we have of the classification algorithm. We show the applicability of our measure by analyzing the effects of user features on Google's display ads, despite having no knowledge of Google's (potentially complex) classification algorithm.

Dataset classification is a useful application of our methods; however, our work applies to extensions of TU cooperative games where agents have more than two states (e.g. OCF games [Chalkiadakis et al., 2010]).

The measure χ is trivially hard to compute exactly, as it generalizes the Banzhaf index, for which this task is known to be hard [Chalkiadakis et al., 2011]. That said, both the Shapley and Banzhaf values can be approximated via random sampling [Bachrach et al., 2010]. It is straightforward to show that random sampling provides good approximations for χ as well, assuming binary classifiers.

Our results can be extended in several ways. The measure χ is the number of times a change in a feature's state causes a change in the outcome. However, a partial dataset of observations may not contain any pair of vectors a, a′ ∈ B, such that a′ = (a-i, b). In Section 5, we control the dataset, so we ensure that all feature profiles appear. However, other datasets would not be as well-behaved. Extending our influence measure to accommodate non-immediate influence is an important step towards implementing our results to other classification domains.

Finally, our experimental results, while encouraging, are illustrative rather than informative: they tell us that Google's display ads algorithm is clever enough to assign Spanish ads to Spanish speakers. Our experimental results enumerate the number of displayed ads; this is not necessarily indicative of users' clickthrough rates. Since our users are virtual entities, we are not able to measure their clickthrough rates; a broader experiment, where user profiles correspond to actual human subjects, would provide better insights into the effects user profiling has on display advertising.

Acknowledgments: This research was partially supported by the National Science Foundation (NSF) under grants CCF0424422, CNS-1064688, CCF-1215883 and IIS-1350598, and by a Sloan Research Fellowship. The authors thank Joe Halpern for his insights regarding our results, as well as the inputs from IJCAI reviewers, which have substantially improved the paper.