Social and other networks have been shown empirically to exhibit high edge clustering — that is, the density of local neighborhoods, as measured by the clustering coefficient, is often much larger ...than the overall edge density of the network. In social networks, a desire for tight-knit circles of friendships — the colloquial “social clique” — is often cited as the primary driver of such structure.
We introduce and analyze a new network formation game in which rational players must balance edge purchases with a desire to maximize their own clustering coefficient. Our results include the following:
Construction of a number of specific families of equilibrium networks, including ones showing that equilibria can have rather general binary tree-like structure, including highly asymmetric binary trees. This is in contrast to other network formation games that yield only symmetric equilibrium networks. Our equilibria also include ones with large or small diameter, and ones with wide variance of degrees.A general characterization of (non-degenerate) equilibrium networks, showing that such networks are always sparse and paid for by low-degree vertices, whereas high-degree “free riders” always have low utility.A proof that for edge cost α ≥ 1/2 the Price of Anarchy grows linearly with the population size n while for edge cost α less than 1/2, the Price of Anarchy of the formation game is bounded by a constant depending only on α, and independent of n. Moreover, an explicit upper bound is constructed when the edge cost is a ”simple” rational (small numerator) less than 1/2.A proof that for edge cost α less than 1/2 the average vertex clustering coefficient grows at least as fast as a function depending only on α, while the overall edge density goes to zero at a rate inversely proportional to the number of vertices in the network.Results establishing the intractability of even weakly approximating best response computations.
Several of our results hold even for weaker notions of equilibrium, such as those based on link stability.
Fair Algorithms for Learning in Allocation Problems Elzayn, Hadi; Jabbari, Shahin; Jung, Christopher ...
Proceedings of the Conference on Fairness, Accountability, and Transparency,
01/2019
Conference Proceeding
Odprti dostop
Settings such as lending and policing can be modeled by a centralized agent allocating a scarce resource (e.g. loans or police officers) amongst several groups, in order to maximize some objective ...(e.g. loans given that are repaid, or criminals that are apprehended). Often in such problems fairness is also a concern. One natural notion of fairness, based on general principles of equality of opportunity, asks that conditional on an individual being a candidate for the resource in question, the probability of actually receiving it is approximately independent of the individual's group. For example, in lending this would mean that equally creditworthy individuals in different racial groups have roughly equal chances of receiving a loan. In policing it would mean that two individuals committing the same crime in different districts would have roughly equal chances of being arrested.
In this paper, we formalize this general notion of fairness for allocation problems and investigate its algorithmic consequences. Our main technical results include an efficient learning algorithm that converges to an optimal fair allocation even when the allocator does not know the frequency of candidates (i.e. creditworthy individuals or criminals) in each group. This algorithm operates in a censored feedback model in which only the number of candidates who received the resource in a given allocation can be observed, rather than the true number of candidates in each group. This models the fact that we do not learn the creditworthiness of individuals we do not give loans to and do not learn about crimes committed if the police presence in a district is low.
As an application of our framework and algorithm, we consider the predictive policing problem, in which the resource being allocated to each group is the number of police officers assigned to each district. The learning algorithm is trained on arrest data gathered from its own deployments on previous days, resulting in a potential feedback loop that our algorithm provably overcomes. In this case, the fairness constraint asks that the probability that an individual who has committed a crime is arrested should be independent of the district in which they live. We investigate the performance of our learning algorithm on the Philadelphia Crime Incidents dataset.
Efficient noise-tolerant learning from statistical queries Kearns, Michael
Annual ACM Symposium on Theory of Computing: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing; 16-18 May 1993,
06/1993
Conference Proceeding
We study fairness in linear bandit problems. Starting from the notion of meritocratic fairness introduced in~\citeJKMR16, we carry out a more refined analysis of a more general problem, achieving ...better performance guarantees with fewer modelling assumptions on the number and structure of available choices as well as the number selected. We also analyze the previously-unstudied question of fairness in infinite linear bandit problems, obtaining instance-dependent regret upper bounds as well as lower bounds demonstrating that this instance-dependence is necessary. The result is a framework for meritocratic fairness in an online linear setting that is substantially more powerful, general, and realistic than the current state of the art.
We study the concept of bargaining solutions, which has been studied extensively in two-party settings, in a generalized setting involving arbitrary number of players and bilateral trade agreements ...over a social network. We define bargaining solutions in this setting, and show the existence of such solutions on all networks under some natural assumptions on the utility functions of the players. We also investigate the influence of network structure on equilibrium in our model, and note that approximate solutions can be computed efficiently when the networks are trees of bounded degree and the parties have nice utility functions.
We give a theoretical and experimental analysis of the generalization error of cross validation using two natural measures of the problem under consideration. The
measures the accuracy to which the ...target function can be ideally approximated as a function of the number of parameters, and thus captures the complexity of the target function with respect to the hypothesis model. The
measures the deviation between the training and generalization errors as a function of the number of parameters, and thus captures the extent to which the hypothesis model suffers from overfitting. Using these two measures, we give a rigorous and general bound on the error of the simplest form of cross validation. The bound clearly shows the dangers of making γ —the fraction of data saved for testing—too large or too small. By optimizing the bound with respect to γ, we then argue that the following qualitative properties of cross-validation behavior should be quite robust to significant changes in the underlying model selection problem:
New Models for Competitive Contagion Draief, Moez; Heidari, Hoda; Kearns, Michael
Proceedings of the ... AAAI Conference on Artificial Intelligence,
06/2014, Letnik:
28, Številka:
1
Journal Article
In this paper, we introduce and examine two new models for competitive contagion in networks, a game-theoretic generalization of the viral marketing problem. In our setting, firms compete to maximize ...their market share in a network of consumers whose adoption decisions are stochastically determined by the choices of their neighbors. Building on the switching-selecting framework introduced by Goyal and Kearns, we first introduce a new model in which the payoff to firms comprises not only the number of vertices who adopt their (competing) technologies, but also the network connectivity among those nodes. For a general class of stochastic dynamics driving the local adoption process, we derive upper bounds on (1) the (pure strategy) Price of Anarchy (PoA), which measures the inefficiency of resource use at equilibrium, and (2) the Budget Multiplier, which captures the extent to which the network amplifies the imbalances in the firms' initial budgets. These bounds depend on the firm budgets and the maximum degree of the network, but no other structural properties. In addition, we give general conditions under which the PoA and the Budget Multiplier can be unbounded. We also introduce a model in which budgeting decisions are endogenous, rather than externally given as is typical in the viral marketing problem. In this setting, the firms are allowed to choose the number of seeds to initially infect (at a fixed cost per seed), as well as which nodes to select as seeds. In sharp contrast to the results of Goyal and Kearns, we show that for almost any local adoption dynamics, there exists a family of graphs for which the PoA and Budget Multiplier are unbounded.
“Firmament” or “Fin” Michael Kearns
Writing for the Street, Writing in the Garret,
10/2020
Book Chapter
Dickinson’s famous statement that “I smile when you suggest that I delay ‘to publish’—that being foreign to my thought, as Firmament to Fin—” embodies her culture’s discourse on creativity and ...uniqueness (letter to Higginson of 7 June 1862, Letters L265). The statement is typically taken at what seems its face value: just as the air-breathing world is fundamentally unattainable to a fish, so Dickinson could not imagine that she might ever want to publish her poetry. Publication, she was telling Higginson, was foreign to her thought—incomprehensible or seeming to belong to another realm of being. There is
PDF
