Abstract
Abstract. Privacy protection appears as a fundamental concern when personal data is collected, stored, and published. Several anonymization methods have been proposed to address privacy issues in private datasets. Every anonymization method has at least one parameter to adjust the level of privacy protection considering some utility for the collected data. Choosing a desirable level of privacy protection is a crucial decision and so far no systematic mechanism exists to provide directions on how to set the privacy parameter. In this paper, we model this challenge in a game theoretic framework to find consensual privacy protection levels and recognize the characteristics of each anonymization method. Our model can potentially be used to compare different anonymization methods and distinguish the settings that make one anonymization method more appealing than the others. We describe the general approach to solve such games and elaborate the procedure using k-anonymity as a sample anonymization method. Our simulations of the game results in the case of k-anonymity reveals how the equilibrium values of k depend on the number of quasi-identifiers, maximum number of repetitive records, anonymization cost, and public's privacy behaviour.
Introduction
Massive data collection about individuals on the Web raises the fundamental issue of privacy protection. A common approach to address privacy concerns is to use data anonymization methods [1] [2] [3] [4] [5] . During data anonymization identifiers are removed and data perturbation, generalization, and/or suppression methods are applied to data records.
Data anonymization promises privacy up to a certain level specified by some privacy parameter(s). In setting the privacy parameter, usually the amount of the expected data utility is considered and hence the level of privacy offered by an anonymization method is never set to the maximum. Since the risk to privacy is not completely removed, we postulate that data providers must be informed about the amount of privacy risk involved (represented as the privacy parameter's value) before deciding to provide their personal data to data collectors.
To bring data providers' privacy opinion into the cycle of data anonymization, we propose a game theoretic model that finds consensual privacy and utility levels by considering preferences of data providers as well as data collectors and data users. More specifically, we analyze the privacy/utility trade-off from the perspective of three different parties: a data user who wants to perform data analysis on a dataset and is willing to pay for it; a data collector who collects and provides privacy protected data to the data user; and data providers who can choose to participate in data collection if they see it as worthwhile. As these parties try to maximize their "profit" (payoff), the collective outcome of the game produces the equilibria [6] in our trade-off system. In an equilibrium state, no single player can achieve higher profits by changing their actions. Therefore, equilibria represent shared agreements (hence the term consensus) in which none of the players would attempt to behave differently. Using these equilibria, we are able to examine privacy trade-offs and analyze different characteristics of an anonymization technique such as the expected amount of privacy, precision, database size, and each party's profit. We believe that features of an anonymization technique must be inspected at equilibrium stages to provide more reliable evaluation results. The proposed model can be used as an evaluation framework to compare various anonymization methods from different perspectives. This is the first attempt to use game theory to analyze trade-offs in a private data collection system by considering preferences of data providers.
Paper organization: The remainder of this paper is organized as follows: Section 2 discusses the related work. Section 3 describes basic definitions in game theory. Section 4 explains our game model and its ingredients. Section 5 provides a general solution to the game. Section 6 demonstrates a sample application of our model for the case of k-anonymity. Section 7 provides conclusions and suggests future directions.
Related Work
The issue of protecting individual's privacy while collecting personal information has motivated several research projects in literature. Our work mostly relates to anonymization techniques such as k-anonymity [1, 2] , l-diversity [3] , t-closeness [4] , and differential privacy [5] . Anonymization techniques provide data privacy at the cost of losing some information. Several methods [7] [8] [9] [10] [11] have been proposed to evaluate the trade-off of privacy/utility. When data usage is unspecified, similarity between the original data and the privacy protected data is considered as information loss. The average size of equivalence classes [7] and discernibility [8] in k-anonymity are two examples of such generic metrics. However, most scholars have noticed that more reliable utility measures must be defined in the context of data application (e.g.,data mining and queries). Various measures of utility such as information-gain-privacy-loss ratio [9] and clustering and partitioning based measure [12] have been proposed to determine the next generalization step within anonymization algorithms. Sramka et al. [10] developed a data mining framework that examins the privacy/utility trade-off after the anonymization has been done using a mining utility. Machanavajjhala et al. [11] defines an accuracy metric for differential privacy in the context of social recommendation systems and analyzes the trade-off between accuracy and privacy. The existing privacy/utility trade-off methods all assume that a dataset already exists before choosing the privacy protection level for it. These methods do not consider the effect of privacy protection level on data providers' decision and hence the volume of the collected information.
In this work we use game theory to investigate steady levels of privacy protection by adopting a broader view of affecting parameters. Game theory has been successfully applied to analyze privacy issues from legal [13] and economic perspectives [14] [15] [16] [17] . Kleinberg et al. [15] describe three scenarios modeled as coalition games [6] and use core and shapely values to find a "fair" reward allocation method in exchange for private information. The underlying assumption in these scenarios is that any amount of reward compensates for the loss of privacy protection. We believe this assumption oversimplifies the nature of privacy concerns and is not compatible with our perception of privacy. Calzolari and Pavan [16] use game theory to explore the optimum flow of customers' private information between two interested firms. The perspective of their work is possibly closest to ours but their model is substantially different from our work since they define a privacy policy as probability of revealing detailed customers' information to another party. Game theory has also been used as a means to address more technical aspects of privacy such as attacks on private location data [18] , implementation of dynamic privacy [17] , and questioning the assumption of honest behavior in multiparty privacy preserving data mining [19] . Our work builds on a commonly accepted definition of privacy among computer and social science scholars and adopts a game theoretical approach to find steady privacy levels. The novelty of our research lies on bringing the economic perspective to data anonymization issues and utilizing game theory for the first time to address privacy/utility trade-offs in a more realistic setting.
Preliminaries and Assumptions
In this paper we propose a game-theoretic framework to find steady level(s) of privacy protection for any arbitrary anonymization technique. We assume that the data providers are informed about having their personal information collected and the data collector is trustworthy in the sense that he fulfills his promises. Every instance of the game is modeled according to a chosen anonymization technique. A common factor between these techniques is a privacy parameter such as k in k-anonymity, l in l-diversity, and 1/ in differential privacy that indicates the level of privacy protection guaranteed by the corresponding privacy mechanism. To provide a generic game model, we use the letter δ to denote the privacy parameter. For any chosen anonymization technique, larger values for δ lead to higher privacy protection and lower data utility. The exact meaning of δ has to be interpreted according to the privacy definition chosen for the game. In this section we provide a brief overview of the game theoretic definitions used in this paper.
Sequential Game Model
Game theory is a mathematical approach to study interdependencies between individual's decisions in strategic situations (games). A game is explained by a set of players (decision makers), their strategies (available moves), and payoffs to each player for every possible strategy combination of all players (strategy profile). A strategy profile is a Nash equilibrium if none of the players can do better by changing their strategy assuming that other players adhere to theirs. Nash equilibrium is commonly used to predict stable outcomes of games and since it represents a steady state of a game [6] , we use the term "stable" through the rest of the paper to denote the strategies found in the equilibrium. To capture a pre-specified order for players' turn to move, a game tree is used to represent a sequential game. In this tree each node is a point of choice for a player and the branches correspond to possible actions. A sequence of actions from the root to any intermediate node or to a leaf node is called a history or a terminal history, respectively [6] . Payoff functions define Preferences of players over each terminal history. A player's strategy explains his decision at any point in the game that he has to move.
Since the sequential structure of extensive form games is not considered in the concept of Nash equilibrium, the notion of "subgame-perfect Nash equilibrium" [6] is normally used to determine the robust steady states of such games. Every sub-tree of the original game tree represents a subgame. A strategy profile is a subgame perfect equilibrium if it induces a Nash equilibrium in every subgame [6] . The principle of Backward induction is a common method to deduce subgame-perfect equilibria of sequential games. Backward induction simply states that when a player has to move, he first deduces the consequences of every available action (how the subsequent player rationally reacts to his decision) and chooses the action that results in the most preferred terminal history.
The challenge of setting a desirable value for privacy parameter δ defines strategic situation with some ordering on players' turn to move. As a result, we model the problem as a sequential game.
Game Description
To define a game-theoretic model for the challenge of finding a balanced value of δ, we must specify the decision makers (players), their preferences, and the rules of the sequential game. The following sections explain the details of our model.
Players
Players of the game are the following three parties:
Data providers-Data providers are individuals that decide whether to provide their personal information at a specific privacy level δ and use the service offered by the data collector or to reject the offer. For example the service could be a discount on some online purchase activity or a software application offered for free. Since privacy preferences of each data provider is affected by several demographic and socioeconomic factors [20] [21] [22] , it is practically infeasible to determine how much utility is gained by each data provider for each combination of δ and incentive. In an alternative approach, we rely on the assumption that data providers' behavior is captured by a model based on some observation rather than a game theoretic analysis. Our assumed model is a regression model which captures how the number of data providers increases as the values of δ and incentive increase. Although this specific model has not been developed yet, similar studies have been conducted to explore the effects of other parameters (such as knowledge of privacy risks, trust, age, income level, etc.) on public's privacy behavior [20, 22, 23] . A regression model that explains the effects of δ and incentive seems to be a natural extension to those studies. The assumed model generally considers data providers who are interested in both privacy and incentive and is defined as:
Privacy Consensus in Anonymization Systems Via Game Theory   5 where N represents total number of individuals who accept the offer as a function of δ and incentive I (in terms of a monetary value). h 1 and h 2 are functions of δ and I. Parameters β 0 , β 1 , and β 2 are the intercept and marginal effects of h 1 (δ) and h 2 (I) on individual's decision to participate in the data collection procedure. The functions h 1 and h 2 can be any non-decreasing functions of δ and I. This regression model does not assume accurate knowledge about privacy risks for data providers and as this knowledge increases, we expect to have larger β 1 to reflect a higher level of privacy concerns.
By assuming a regression model, we mostly observe data providers' behavior rather than directly analyzing it. This assumption trims the game tree by removing the data providers from the analysis of the game. Nevertheless, the effect of data providers' decisions is reflected in other players' payoff functions and paying specific attention to their impact on the final level of privacy is one of the distinctive strengths of our work.
Data collector-A data collector is the entity who collects a dataset of personal data and provides it to some data users. The data collector receives offers from the data users, and based on their needs and the expected cardinality of the collected dataset announces a privacy level and some incentive to collect data from individuals. Once a data collector collects a dataset of personal information, he protects the privacy of the data providers at the consented level δ and provides the private dataset to the data user.
The data collector generally prefers to receive more money from the data user and spend less money on the amount of incentive he pays the data providers. Consequently, cardinality of the dataset (number of data providers) affects the payoff to the data collector. A detailed formulation of data collector's payoff is provided in Sect. 4 
.3.
Data user-A data user is an entity interested in accessing personal information for some data analysis purposes. A data user prefers a dataset with higher quality (more accurate query results) and higher cardinality (results with higher statistical significance). Privacy parameter δ affects these requirements in positive and negative ways. Therefore a data user chooses a value δ that balances the needs and initiates the game by offering some value for parameter δ and some price, p, for each data record. We give the detailed analysis for games with a single data user. The approach to model multiple data users and data reuse is explained elsewhere [24] .
Game Rules
We model interactions between the data collector and the data user as a sequential game with perfect (players are aware of the actions taken by previous players) and complete (players are aware of the available strategies and payoff functions of all other players) information. More specifically, both players know data the provider's behavior model. The data user also knows the data collector's available actions and preferences 1 . The game starts with an offer from the data user to the data collector. In the offer, the required value for privacy parameter δ and the price p (per each record) must be specified. We denote an offer by Of = δ, p . Once the data collector receives the offer he can either reject or accept it. In case of a rejection, the game terminates with payoff zero to both the data user and the data collector. If the data collector decides to accept then he needs to announce an incentive in exchange for collecting personal information. Here, we assume that I represents monetary value of the incentive and its domain is R ≥0 . The terminal histories of this game are either of the form (Of, I) or (Of, Reject). At any terminal history, the number of data providers who will opt-in is determined by plugging the values of δ and I into Eq(1). Consequently, preferences of the data user and the data collector over all terminal histories are determined based on the payoff function defined over cardinality of dataset and values of δ, p, and I. The interactions and mutual effects of players' decision are captured in Fig. 1(a) . Based on the game's dynamics, Fig. 1(b) illustrates the game tree (triangles represent ranges of possible offers and incentives).
Payoffs
Payoff to the Data Collector: The data collector receives some money, p, from the data user for each data record. The total number of data records in the dataset is the same as the number of data providers who participate in the data collection procedure and is defined by N in Eq(1). Consequently, the income of the data collector is:
income DC = p N (2) Data collection procedure, data anonymization, and storing the dataset are costly and we denote these costs by C. Moreover, the data collector has to pay some incentive, I, to each data provider. As a result, the expenses to the data collector can be defined as:
For simplicity of analysis we have assumed a fixed cost C for data collector. This assumption can be dropped easily by defining cost as a function of the size of the dataset and privacy level δ without any significant modification to our analysis. The payoff to the data collector is therefore defined as:
Payoff to the Data User:
The data user wants to run some data analysis on the privacy protected dataset T * . As the cardinality of this dataset increases, the dataset will have higher value to the data user. Let a denote the economic value of each record to the data user, i.e., a represents Privacy Consensus in Anonymization Systems Via Game Theory 7 the net revenue of a data record if the data user gets the record for free. If the number of data records collected from individuals is denoted by N we can initially define the data user's income as a * N . However, after anonymization the utility of data drops due to imprecision introduced to results of the queries. We use parameter 0 ≤ P recision ≤ 1 as a coefficient of the data user's income to show how the value of the dataset decreases as data become less precise. The income of the data user is:
income DU = a N P recision (5) To estimate the precision of query results on a private dataset, various parameters must be considered. These parameters include the semantics of the query, the anonymization method and algorithm used, database schema, level of privacy protection δ, number of data records N , and etc.. For each instance of the game, all of these parameters except for δ and N are fixed (and assumed to be a common knowledge of the game). Therefore, P recision = prec(δ,
General Approach to Find Subgame Perfect Equilibria
In this section we explain the steps involved in the process of finding the game's subgame perfect equilibria using backward induction [6] . In the next section, we show the details of this process for k-anonymity as an example.
Equilibrium Strategies of Data Collector
The first step to find subgame perfect equilibria is to find the optimal actions of the data collector in each subgame of length 1. Subgames of length 1 are represented by subtrees at which the data collector has to move based on a history of the form (Of ).
Where Of = δ, p is an offer made by the data user. The data collector can estimate the expected cardinality of the dataset for each δ and I based on Eq(1). If we plug this equation into the U DC formula from Eq(4), the data collector's payoff after accepting Of = δ, p will be:
For each offer Of = δ, p , the values of δ and p are fixed. The data collector needs to find the optimum I (denoted byÎ) for which the function U DC attains its maximum value. To findÎ we must find the argument of the maximum:
Subject to the constraint thatÎ ≥ 0.
2 Notice that N is also an increasing function of δ (see Eq(1)) and therefore
is not always greater than or equal to zero.
If the maximum U DC ,Û DC , is greater than zero the data collector accepts the offer. IfÛ DC = 0 then the data collector will be indifferent between accepting and rejecting and in the case whereÛ DC < 0 the data collector rejects. Therefore, the data collector's best response, BR DC , to an offer Of = δ, p is: [25] , U DC reaches its maximum at least once and thereforeÎ is guaranteed to exist.
Equilibrium Strategies of Data User
The next step to find the subgame perfect equilibria is to find the most profitable action of the data user; Knowing the data collector's best response (Sect. (8), ifÎ is unique for every combination of δ and p, thenÎ can be defined as a function of δ and p (i.e.,Î =î(δ, p)). Without loss of generality, we assume that this is the case. If multiple values of I maximize U DC , the one that also maximizes the data user's payoff is in the equilibria of the game.
According to Sect. 5.1, if the data collector accepts the offer he starts collecting personal information at privacy level δ with incentiveÎ =î(δ, p). Otherwise, no dataset will be provided to the data user. As a result, the anticipated number of records N can be determined as:
Plugging the function definition ofÎ =î(δ, p) into Eq(10), N = n 2 (δ, p) becomes a function of δ and p as well. Recall that P recision = prec(δ, N ) is defined as a function of δ and N . Since N is a function of δ and p, we can define P recision = prec 2 (δ, p) as a function of δ and p as well. After substituting N and P recision with n 2 (δ, p) and prec 2 (δ, p), the U DU function from Eq(6) becomes a function of two variables δ and p. The most profitable strategy for the data user is to choose values of δ and p that maximize his payoff:
By definition, the lower bounds on p and δ is zero, i.e., p ≥ 0 and δ ≥ 0. Moreover, since P recision ≤ 1 then (a * prec 2 (δ, p)) ≤ a. Choosing a value p > a leads to a negative payoff to the data user and he can always do better by choosing p = 0 (which leads to payoff zero). Therefore, the upper bound for p is a. Parameter δ is not necessarily bounded from above. Consequently, we cannot use the Extreme value theorem to guarantee an equilibrium. If U DU has an absolute maximum subject to the bounds defined on δ and p, the game has subgame perfect equilibria of the forms ((δ,p), reject) or ((δ,p) ,Î). The first form occurs when the data collector cannot find any profitable amount of incentive (regardless of δ and p chosen by the data user) and the negotiation is unsuccessful. The second format occurs in games where there are at least one combination of δ and p of which the data collector can make profit. The two types of equilibria provide a means to determine whether an anonymization technique is practical or impractical given other problem settings. If the cost of implementing an anonymization technique is too high and the public's trust in the method is not high enough, the game might become an instance of unsuccessful negotiations and we have a case of impractical anonymization.
Game Theoretic Analysis for k-Anonymity
To demonstrate the details of the steps explained in Sect. 5, we use k-anonymity as the anonymization technique and provide a P recision function for it. The game solution is described and a simulation of the results is provided at the end of this section.
k-Anonymity Overview
A dataset to be released contains some sensitive attributes, identifying attributes, and quasi-identifying attributes. Even after removing the identifying attributes, the values of quasi-identifying attributes can be used to uniquely identify at least a single individual in the dataset via linking attacks. Every subset of tuples in dataset that share the same values for quasi-identifiers is often referred to as an equivalence class. A released dataset is said to satisfy k-anonymity, if for each existing combination of quasi-identifier attribute values in the dataset, there are at least k − 1 other records in the database that contain such a combination.
There are several methods to achieve k-anonymity. Our work is built on Mondrian algorithm [26] . This greedy algorithm implements multidimensional recoding (with no cell suppression) which allows finer-grained search and thus often leads to a better data quality. In Mondrian algorithm all the identifying attributes are suppressed first. Then records are recursively partitioned into d−dimensional rectangular boxes (equivalence classes), where d is the number of quasi-identifiers. To partition each box, a quasiidentifier attribute (a dimension) is selected and the median value along this attribute is used as a binary cut to split the box into two smaller boxes. Once partitioning is done, records in each partition are generalized so that they all share the same quasi-identifier value, to form an equivalence class. A copy of this algorithm is provided in Fig. 3(b) .
Data Providers' Privacy Model
Based on Sect. 4.1, we assume a regression model to explain data providers' reaction (at an aggregate level) to each combination of privacy protection levels and incentives.
This model is explained in Eq(1). In k-anonymity, privacy parameter is k. Here, we consider the identity function for the incentive (because of its simplicity) and logarithmic function for parameter k. In other words :
To understand our choice of log function for h 1 , notice that when k-anonymity is used, it is assumed that the probability of re-identifying an individual is 1 k . For example, when k is 1, the probability of re-identification is 1 and the guaranteed privacy is 0. When k becomes 2, the probability of re-identification becomes 1 2 and the amount of uncertainty about the identity of the individual increases from 0 (log1) to 1 (log2). However, this increase in uncertainty about the identity of individuals (privacy) is not the same as k changes from 99 to 100 because the probability changes from 
Precision Estimate
To determine the payoff to the data user (see Eq(6)) we need a metric to calculate P recision. A reasonable estimate on the amount of imprecision caused by anonymization depends on the data application. We have briefly discussed the nature of imprecision that can be introduced to the results of any SELECT query executed against an anonymized dataset elsewhere [24] . In this paper we provide the precision estimates for a specific SELECT query type and consider this query as the data analysis purpose. Our SELECT query is of the following form:
Q i ≡ SELECT sensitiveAtt FROM T * WHERE q = v i In this query sensitiveAtt represents the value of sensitive attribute, T * is the anonymized dataset, q is one of the quasi-identifiers, and v i is the i th possible value for attribute q. For example, a query Q 20 can be the following:
Q 20 ≡ SELECT disease FROM T * WHERE age = 20 Let |Q i (T )| denote cardinality of the result set of query Q i on dataset T . When Q i is run against T * , the result set Q i (T * ) contains two groups of records: a subset of them satisfy the condition q = v i and the rest of them are just included in the result because they are partitioned into the same equivalence class as the points with q = v i . The latter introduce some quantity imprecision in the result. LeFevre et al. [27] introduce an imprecision metric to find the best cuts while running the Mondrian algorithm [26] on experimental datasets. After normalizing this metric, we define P recision as:
As a result, to calculate P recision we first need to estimate |Q i (T )| and |Q i (T * )|. Let P r i denote the portion of the records in the dataset that have value v i for quasi-identifier q. Then the expected value of |Q i (T )| is:
Through Theorems 1 and 2 we provide an estimate for |Q i (T * )|. In Mondrian algorithm the minimum and maximum number of records in each equivalence class are k Privacy Consensus in Anonymization Systems Via Game Theory 11 and 2d(k − 1) + m, where m denotes the maximum number of records with identical values for all quasi-identifiers [26] . Since the distribution of equivalence class sizes are not known a priori, with a simplifying assumption of uniform distribution, we can estimate the average number of records in each equivalence class, ec AV G , as:
Theorem 1. If the average size of each equivalence class is determined by Eq(15), then the depth of the recursive calls, l, in Mondrian algorithm [26] can be estimated as:
Proof. (sketch) Mondrian algorithm starts with the original dataset as a single equivalence class and chooses the median value of one of the dimensions to recursively cut each equivalence class into two smaller ones. It stops when there is no more possible cuts for any of the equivalence classes. For this estimate, we assume that the algorithm stops at the point where the size of each class reaches ec AV G from Eq (15) . By solving the recursive definition, we get Eq (16) . A complete proof is available [24] .
Theorem 2.
If N denotes the number of records in a dataset T , the cardinality of the result set of query Q i on T * can be estimated as:
where d is the number of quasi-identifiers and l is the depth of recursive calls estimated in Theorem 1.
Proof. (sketch) The core idea of this proof is to note that during the partitioning process, for each equivalence class if the dimension q is chosen as the cutting dimension then half of the records in the class will be partitioned into a new class that will not be included in the result set of Q i . Otherwise the cut does not reduce the size of the result set. A complete proof is available [24] .
Consequently, P recision is defined as:
We can also use Theorem 2 to define pr i based on the parameters. In real instances of the problem pr i is independent of any specific algorithm and estimates; it is a property of the dataset. However, since we have made some simplifying assumptions for other estimates the assumptions should also be applied to pr i to produce a meaningful estimate. Theorem 2 provides an estimate on |Q i (T * )|. When k = 1, there are no irrelevant records in the result set. Therefore, |Q i (T * k=1 )| provides an estimate on the number of records that satisfy the condition q = v i and |Q i (T * k=1 )|/N can be used as an estimate for pr i .
Consequently, we can refine Equation (18) as:
Subgame Perfect Equilibria
As explained in Sect. 5.1, the first step to find the game's subgame perfect equilibria is to determine the optimum incentiveÎ from Eq (8) . If the data collector accepts the offer Of = k, p with incentive I, his payoff will be:
Calculating the derivative of U DC with respect to I and setting it to zero reveals the maximizing I:
) I is the local maximum since the second derivative of the function is negative. The restriction here is I ≥ 0. IfÎ < 0, the maximizing I will be zero. The lower bound on I leads us to consider two separate cases:
Case 1: β 2 p ≥ β 1 log 2 (k) + β 0 -In this case the amount of incentive that maximizes
. PluggingÎ into Eq (20) gives us the maximum payoff to the data collector for Case 1 (denoted asÛ 1 DC ):
The data collector will accept the offer Of = k, p ifÛ 1 DC ≥ 0. In other words, the data collector accepts if:
Case 2: β 2 p < β 1 log 2 (k) + β 0 -The optimum incentive in this case would beÎ = 0. With this incentive the maximum payoff to the data collector (denoted asÛ
The data collector will accept this offer ifÛ 2 DC ≥ 0. More precisely, the data collector accepts the offer if:
If the values ofÎ (from the two cases) are plugged into Eq(10), we can define the cardinality of the private dataset as a piecewise function of k and p:
If the new definition of N is plugged into the P recision function, precision becomes a function of k and p. As a result, U DU from Eq(6) becomes a function of k and p. The best strategy for the data user is to computek andp according to Eq (11) . The optimum offer is Of = δ ,p and this completes the process of finding perfect equilibria. 
Simulation Results
If the players of the game are rational and have the required information, the equilibria of the game would always conform to what Sect. 6.4 suggests because we used an analytical method to find the game's equilibria. In our proposed method, a dataset does not exist before the game is complete and the specifications of the collected dataset depend on the parameters chosen while the game is played. Therefore, running experiments on real databases does not provide meaningful results for this work. Alternatively, we choose to simulate the game and visualize the results by testing multiple parameter settings using MATLAB R2008a. In every setting, the effect of one of the parameters a, C,d, m, and β is examined on the stable values of k (while the values of the rest of the parameters are fixed to β 0 = 7000, β 1 = 2000, β 2 = 20, a = $10, C = $20, 000, m = 5, and d = 4). The results are shown in Fig. 2 .
The values for a and C are randomly selected as an estimate of reasonable values commonly used in real instances of the problem. We assumed a population size of 55,000 potential data providers and the values selected for parameters β 0 , β 1 , and β 2 are chosen to reflect Westin's privacy indexes [28] . Based on the maximum values of k (k = 100) and p (p = a), β 1 and β 2 are chosen such that the effect of maximum privacy is almost the same as maximum incentive. The value of β 0 is chosen such that 17% of the data providers fall in the privacy unconcerned category [28] . Figure 2(a) shows how stable values of k increase as the number of quasi-identifiers increase. To understand the reason, we have provided another diagram in Fig. 3(a) which illustrates the precision curves for different values of d. According to this figure, with fewer quasi-identifiers the precision curve decreases at a higher rate. Therefore, as the number of quasi-identifiers increase, offering larger values for k becomes a better option for the data user since it can increase the size of the dataset without severely affecting data quality.
In Fig. 2(b) we can see the effect of m (maximum number of data providers with identical quasi-identifier values) on the stable values of k. We have chosen the values of m from {1, ..., 30}. As the value of m increases the stable value of k increases. To understand this counter-intuitive result, notice that as m increases less generalization will be needed to group the tuples in equivalence classes of size k. Therefore, compared to the cases with smaller m, the same precision can be achieved with higher values of k. Larger values of k attract more data providers without largely affecting the precision of query results and consequently, the data user can make more profit in this case.
The effects of anonymization, and maintenance cost (C) on stable values of k are illustrated in Fig. 2(c) . Based on the settings chosen for other parameters, after a certain point the cost becomes too high for condition of the Eq(25) to be satisfied and case 1 (from Sect. 6.4) happens. In this case, the data collector is receiving a payment high enough to announce non-zero incentives. This incentive convinces several privacy concerned data providers to participate even with a low privacy protection level. As a result, the data user simply asks for no privacy protection since he is confident that enough data providers will participate to receive the incentive. Finally, after a certain value for C, the game reaches a point (demonstrated by a shaded rectangle) where no combination of k, p can be found that is acceptable by the data collector and U DU ≥ 0. This situation represents an instance of impractical anonymization.
Figures 2(d), 2(e), and 2(f) represent the effects of data providers' privacy attitude on stable values of k. According to Fig. 2(d) as the number of privacy unconcerned group (data providers who provide their personal information without any privacy or incentive) increase, the data user can receive larger volume of data without asking for sanitized dataset. By increasing the value of β 1 we model a privacy aware population. As can be seen in Fig. 2(e) , when privacy has more significant impact on data providers' decisions, data will be sanitized with larger values of k. In Fig. 2(f) we showed how the value of β 2 impacts stable values of k. If β 2 is less than a certain level then it mostly affects the price of information and not the level of privacy protection. However if the weight of incentive on data providers' privacy decisions becomes heavier than a certain point, case 1 (refer to Sect. 6.4) happens and the data user can maximize his benefit by just increasing the price and asking for no privacy. These diagrams show how public's privacy awareness can force the firms to protect privacy of data providers. 
Anonymize(partition)
if (no allowable multidimensional cut for partition) return : partition ! summary else dim choose dimension() fs frequency set(partition, dim) splitV al find median(fs) lhs {t 2 partition : t.dim  splitV al} rhs {t 2 partition : t.dim > splitV al} return Anonymize(rhs) [ Anonymize(lhs) 
Conclusions and Future Work
In this paper we modeled the process of private data collection as a sequential game to achieve consensus on the level of privacy protection. We explained the general approach to solve the game and as an example provided the details of game analysis for k-anonymity. Players of the game are a data user, a data collector, and a group of data providers. We use the method of backward induction to explore the game's subgame perfect equilibria. Equilibria of the game suggest stable values of the privacy parameter that are unlikely to be changed when other parties move according to their equilibria strategies. For the k-anonymity case, we found the stable values of k and showed that these values are related to number of quasi-identifiers, maximum number of identical tuples (in their quasi-identifier values), cost of data sanitization and storage, and coefficients of public's privacy behavior model. Our results illustrate the significant impact of the number of quasi-identifiers on the decision about the value of k.
We are plannig to analyze other privacy definitions such as l-diversity [3] and differential privacy [5] and for each privacy definition, distinguish the settings which make it the most profitable option to the players of the game. We are also planning to improve the model by dropping the assumption about the amount of information available to the data collector and data user. Our goal is to design a new evaluation framework that uses our game theoretic model to compare different anonymization methods and distinguish the settings that make one anonymization method more appealing than another.

{'paper_id': '13951713', 'title': 'Privacy consensus in anonymization systems via game theory', 's2_url': 'https://api.semanticscholar.org/CorpusID:13951713', 'source': 'S2ORC'}