Grant Schoenebeck

Search for another author

Author Description

Ask a Question About This Mathematician

Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms

2010-01-01

Anupam Gupta , Aaron Roth , Grant Schoenebeck +1 more

View PDF Chat

Optimal Testing of Reed-Muller Codes

2010-10-01

Arnab Bhattacharyya , Swastik Kopparty , Grant Schoenebeck +2 more

We consider the problem of testing if a given function f:F 2 n → F 2 is close to any degree d polynomial in … We consider the problem of testing if a given function f:F 2 n → F 2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al. [1] proposed and analyzed a natural 2 d+1 -query test for this problem. This test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Ω(1)-far with probability Ω(1/(d2 d )). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Ω(2 -d )-far with Ω(1)probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1) st -Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by induction on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F 2 n to F 2 . The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our result has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every function q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

View PDF Chat

Conducting truthful surveys, cheaply

2012-06-04

Aaron Roth , Grant Schoenebeck

We consider the problem of conducting a survey with the goal of obtaining an unbiased estimator of some population statistic when individuals have unknown costs (drawn from a known prior) … We consider the problem of conducting a survey with the goal of obtaining an unbiased estimator of some population statistic when individuals have unknown costs (drawn from a known prior) for participating in the survey. Individuals must be compensated for their participation and are strategic agents, and so the payment scheme must incentivize truthful behavior. We derive optimal truthful mechanisms for this problem for the two goals of minimizing the variance of the estimator given a fixed budget, and minimizing the expected cost of the survey given a fixed variance goal.

View PDF Chat

Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality

2018-01-01

Xingjun Ma , Bo Li , Yisen Wang +6 more

Deep Neural Networks (DNNs) have recently been shown to be vulnerable against adversarial examples, which are carefully crafted instances that can mislead DNNs to make errors during prediction. To better … Deep Neural Networks (DNNs) have recently been shown to be vulnerable against adversarial examples, which are carefully crafted instances that can mislead DNNs to make errors during prediction. To better understand such attacks, a characterization is needed of the properties of regions (the so-called 'adversarial subspaces') in which adversarial examples lie. We tackle this challenge by characterizing the dimensional properties of adversarial regions, via the use of Local Intrinsic Dimensionality (LID). LID assesses the space-filling capability of the region surrounding a reference example, based on the distance distribution of the example to its neighbors. We first provide explanations about how adversarial perturbation can affect the LID characteristic of adversarial regions, and then show empirically that LID characteristics can facilitate the distinction of adversarial examples generated using state-of-the-art attacks. As a proof-of-concept, we show that a potential application of LID is to distinguish adversarial examples, and the preliminary results show that it can outperform several state-of-the-art detection measures by large margins for five attack strategies considered in this paper across three benchmark datasets. Our analysis of the LID characteristic for adversarial regions not only motivates new directions of effective adversarial defense, but also opens up more challenges for developing new attacks to better understand the vulnerabilities of DNNs.

Buying private data without verification

2014-05-30

Arpita Ghosh , Katrina Ligett , Aaron Roth +1 more

We consider the problem of designing a survey to aggregate non-verifiable information from a privacy-sensitive population: an analyst wants to compute some aggregate statistic from the private bits held by … We consider the problem of designing a survey to aggregate non-verifiable information from a privacy-sensitive population: an analyst wants to compute some aggregate statistic from the private bits held by each member of a population, but cannot verify the correctness of the bits reported by participants in his survey. Individuals in the population are strategic agents with a cost for privacy, ie, they not only account for the payments they expect to receive from the mechanism, but also their privacy costs from any information revealed about them by the mechanism's outcome---the computed statistic as well as the payments---to determine their utilities. How can the analyst design payments to obtain an accurate estimate of the population statistic when individuals strategically decide both whether to participate and whether to truthfully report their sensitive information'

View PDF Chat

An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling

2019-01-25

Yuqing Kong , Grant Schoenebeck

In the setting where information cannot be verified, we propose a simple yet powerful information theoretical framework—the Mutual Information Paradigm—for information elicitation mechanisms. Our framework pays every agent a measure … In the setting where information cannot be verified, we propose a simple yet powerful information theoretical framework—the Mutual Information Paradigm—for information elicitation mechanisms. Our framework pays every agent a measure of mutual information between her signal and a peer’s signal. We require that the mutual information measurement has the key property that any “data processing” on the two random variables will decrease the mutual information between them. We identify such information measures that generalize Shannon mutual information. Our Mutual Information Paradigm overcomes the two main challenges in information elicitation without verification: (1) how to incentivize high-quality reports and avoid agents colluding to report random or identical responses; (2) how to motivate agents who believe they are in the minority to report truthfully. Aided by the information measures, we found (1) we use the paradigm to design a family of novel mechanisms where truth-telling is a dominant strategy and pays better than any other strategy profile (in the multi-question, detail free, minimal setting where the number of questions is large); (2) we show the versatility of our framework by providing a unified theoretical understanding of existing mechanisms—Bayesian Truth Serum Prelec (2004) and Dasgupta and Ghosh (2013)—by mapping them into our framework such that theoretical results of those existing mechanisms can be reconstructed easily. We also give an impossibility result that illustrates, in a certain sense, the the optimality of our framework.

View PDF Chat

Putting Peer Prediction Under the Micro(economic)scope and Making Truth-Telling Focal

2016-01-01

Yuqing Kong , Katrina Ligett , Grant Schoenebeck

View PDF Chat

Social Learning in a Changing World

2011-01-01

Rafael Frongillo , Grant Schoenebeck , Omer Tamuz

View PDF Chat

Potential networks, contagious communities, and understanding social network structure

2013-05-13

Grant Schoenebeck

View PDF Chat

Putting Peer Prediction Under the Micro(economic)scope and Making Truth-telling Focal

2016-01-01

Yuqing Kong , Grant Schoenebeck , Katrina Ligett

Peer-prediction is a (meta-)mechanism which, given any proper scoring rule, produces a mechanism to elicit privately-held, non-verifiable information from self-interested agents. Formally, truth-telling is a strict Nash equilibrium of the … Peer-prediction is a (meta-)mechanism which, given any proper scoring rule, produces a mechanism to elicit privately-held, non-verifiable information from self-interested agents. Formally, truth-telling is a strict Nash equilibrium of the mechanism. Unfortunately, there may be other equilibria as well (including uninformative equilibria where all players simply report the same fixed signal, regardless of their true signal) and, typically, the truth-telling equilibrium does not have the highest expected payoff. The main result of this paper is to show that, in the symmetric binary setting, by tweaking peer-prediction, in part by carefully selecting the proper scoring rule it is based on, we can make the truth-telling equilibrium focal---that is, truth-telling has higher expected payoff than any other equilibrium. Along the way, we prove the following: in the setting where agents receive binary signals we 1) classify all equilibria of the peer-prediction mechanism; 2) introduce a new technical tool for understanding scoring rules, which allows us to make truth-telling pay better than any other informative equilibrium; 3) leverage this tool to provide an optimal version of the previous result; that is, we optimize the gap between the expected payoff of truth-telling and other informative equilibria; and 4) show that with a slight modification to the peer prediction framework, we can, in general, make the truth-telling equilibrium focal---that is, truth-telling pays more than any other equilibrium (including the uninformative equilibria).

View PDF Chat

Eliciting Expertise without Verification

2018-06-11

Yuqing Kong , Grant Schoenebeck

A central question of crowdsourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. A key challenge is that sophisticated agents … A central question of crowdsourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. A key challenge is that sophisticated agents may strategically withhold effort or information when they believe their payoff will be based upon comparison with other agents whose reports will likely omit this information due to lack of effort or expertise. Our work defines a natural model for this setting based on the assumption that more sophisticated agents know the beliefs of less sophisticated agents. We then provide a mechanism design framework for this setting. From this framework, we design several novel mechanisms, for both the single and multiple tasks settings, that (1) encourage agents to invest effort and provide their information honestly; (2) output a correct "hierarchy" of the information when agents are rational.

View PDF Chat

Don’t Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

2017-01-01

Rico Angell , Grant Schoenebeck

View PDF Chat

Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity

2016-01-01

Yuqing Kong , Grant Schoenebeck

Peer-prediction is a mechanism which elicits privately-held, non-variable information from self-interested agents---formally, truth-telling is a strict Bayes Nash equilibrium of the mechanism. The original Peer-prediction mechanism suffers from two main … Peer-prediction is a mechanism which elicits privately-held, non-variable information from self-interested agents---formally, truth-telling is a strict Bayes Nash equilibrium of the mechanism. The original Peer-prediction mechanism suffers from two main limitations: (1) the mechanism must know the "common prior" of agents' signals; (2) additional undesirable and non-truthful equilibria exist which often have a greater expected payoff than the truth-telling equilibrium. A series of results has successfully weakened the known common prior assumption. However, the equilibrium multiplicity issue remains a challenge. In this paper, we address the above two problems. In the setting where a common prior exists but is not known to the mechanism we show (1) a general negative result applying to a large class of mechanisms showing truth-telling can never pay strictly more in expectation than a particular set of equilibria where agents collude to "relabel" the signals and tell the truth after relabeling signals; (2) provide a mechanism that has no information about the common prior but where truth-telling pays as much in expectation as any relabeling equilibrium and pays strictly more than any other symmetric equilibrium; (3) moreover in our mechanism, if the number of agents is sufficiently large, truth-telling pays similarly to any equilibrium close to a "relabeling" equilibrium and pays strictly more than any equilibrium that is not close to a relabeling equilibrium.

On the Complexity of Nash Equilibria of Action-Graph Games

2009-01-04

Constantinos Daskalakis , Grant Schoenebeck , Gregory Valiant +1 more

In light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of Nash equilibria yet remains as expressive as possible, we investigate … In light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of Nash equilibria yet remains as expressive as possible, we investigate the computational complexity of Nash equilibria in the recently proposed model of action-graph games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, are succinct representations of games that encapsulate both local dependencies as in graphical games, and partial indifference to other agents’ identities as in anonymous games, which occur in many natural settings such as financial markets. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a simple Fully Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant degree, constant treewidth and a constant number of agent types (but an arbitrary number of strategies), and extend this algorithm to a broader set of instances. However, the main results of this paper are negative, showing that when either of the latter conditions are relaxed the problem becomes intractable. In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP–complete to decide the existence of a pure-strategy Nash equilibrium and PPAD–complete to compute a mixed Nash equilibrium (even an approximate one). Similarly for AGGs with a constant number of agent types but unconstrained treewidth. These hardness results suggest that, in some sense, our FPTAS is as strong a positive result as one can expect. In the broader context of trying to pin down the boundary where the equilibria of multi-player games can be computed efficiently, these results complement recent hardness results for graphical games and algorithmic results for anonymous games.

View PDF Chat

Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization

2019-04-02

Grant Schoenebeck , Biaoshuai Tao

We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as the influence maximization problem … We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as the influence maximization problem . It admits a (1−1/e)-factor approximation algorithm if the influence function is submodular . Otherwise, in the worst case, the problem is NP-hard to approximate to within a factor of N 1−ε . This article studies whether this worst-case hardness result can be circumvented by making assumptions about either the underlying network topology or the cascade model. All our assumptions are motivated by many real-life social network cascades. First, we present strong inapproximability results for a very restricted class of networks called the (stochastic) hierarchical blockmodel , a special case of the well-studied (stochastic) blockmodel in which relationships between blocks admit a tree structure. We also provide a dynamic-programming-based polynomial time algorithm, which optimally computes a directed variant of the influence maximization problem on hierarchical blockmodel networks. Our algorithm indicates that the inapproximability result is due to the bidirectionality of influence between agent-blocks. Second, we present strong inapproximability results for a class of influence functions that are “almost” submodular, called 2-quasi-submodular . Our inapproximability results hold even for any 2-quasi-submodular f fixed in advance. This result also indicates that the “threshold” between submodularity and nonsubmodularity is sharp, regarding the approximability of influence maximization.

View PDF Chat

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

2017-01-01

Grant Schoenebeck , Biaoshuai Tao

View PDF Chat

Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization

2020-04-03

Wei Chen , Binghui Peng , Grant Schoenebeck +1 more

We consider the *adaptive influence maximization problem*: given a network and a budget $k$, iteratively select $k$ seeds in the network to maximize the expected number of adopters. In the … We consider the *adaptive influence maximization problem*: given a network and a budget $k$, iteratively select $k$ seeds in the network to maximize the expected number of adopters. In the *full-adoption feedback model*, after selecting each seed, the seed-picker observes all the resulting adoptions. In the *myopic feedback model*, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of *greedy adaptivity gap*, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a $(1-1/e)$-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a $(1-1/e)$ fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the *independent cascade model* and the *linear threshold model*. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a $(1-1/e)$-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular diffusion model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.

View PDF Chat

Complex Contagions in Kleinberg's Small World Model

2015-01-11

Roozbeh Ebrahimi , Jie Gao , Golnaz Ghasemiesfeh +1 more

Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires influence by two or more neighbors. In a k-complex contagion, a cluster of nodes are … Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires influence by two or more neighbors. In a k-complex contagion, a cluster of nodes are initially infected, and additional nodes become infected in the next round if they have at least k already infected neighbors. It has been argued that complex contagions better model behavioral changes such as adoption of new beliefs, fashion trends or expensive technology innovations. This has motivated rigorous understanding of spreading of complex contagions in social networks. Despite simple contagions (k=1) that spread fast in all small world graphs, how complex contagions spread is much less understood. Previous work [11] analyzes complex contagions in Kleinberg's small world model [14] where edges are randomly added according to a spatial distribution (with exponent γ) on top of a two dimensional grid structure. It has been shown in [11] that the speed of complex contagions differs exponentially when γ=0 compared to when γ=2.

View PDF Chat

A Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling.

2016-05-03

Yuqing Kong , Grant Schoenebeck

Information elicitation mechanisms, such as Peer Prediction [Miller 2005] and Bayesian Truth Serum [Prelec 2004], are designed to reward agents for honestly reporting their private information, even when this cannot … Information elicitation mechanisms, such as Peer Prediction [Miller 2005] and Bayesian Truth Serum [Prelec 2004], are designed to reward agents for honestly reporting their private information, even when this cannot be directly verified. Information elicitation mechanisms, such as these, are cleverly designed so that truth-telling is a strict Bayesian Nash Equilibrium. However, a key challenge that has arisen is that there are typically many other non-truthful equilibrium as well, and it is important that truth-telling not only be an equilibrium, but be paid more than other equilibrium so that agents do not coordinate on a non-informative equilibria. Several past works have overcome this challenge in various setting using clever techniques, but a new technique was required for each new setting. Our main contribution in this paper is providing a framework for designing elicitation mechanisms where truth-telling is the highest paid equilibrium, even when the mechanism does not know the common prior. We define monotone functions which can measure the amount of information contained in agents' reports such that the function is greater in the truthful equilibrium than in non-truthful equilibria. We provide several interesting monotone functions ( f -disagreement, f-mutual information, f -information gain) in different settings. Aided by these theoretical tools, we (1) extend Dasgupta and Ghosh[2013]'s mechanism to the non-binary setting with an additional assumption that agents are asked to answer a large number of a priori similar questions; (2) reprove the main results of Prelec[2004], Dasgupta and Ghosh[2013] and a weaker version of Kong and Schoenebeck[2016] in our framework. Our framework thus provides both new mechanisms and a deeper understanding of prior results.

Conducting Truthful Surveys, Cheaply

2012-03-02

Aaron Roth , Grant Schoenebeck

Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization

2022-05-26

Wei Chen , Binghui Peng , Grant Schoenebeck +1 more

We consider the adaptive influence maximization problem: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the … We consider the adaptive influence maximization problem: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the full-adoption feedback model, after selecting each seed, the seed-picker observes all the resulting adoptions. In the myopic feedback model, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of greedy adaptivity gap, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a (1 − 1/e)-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a (1−1/e) fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the independent cascade model and the linear threshold model. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a (1 − 1/e)-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular diffusion model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.

View PDF Chat

Graph Isomorphism and the Lasserre Hierarchy

2014-01-01

Aaron Snook , Grant Schoenebeck , Paolo Codenotti

In this paper we show lower bounds for a certain large class of algorithms solving the Graph Isomorphism problem, even on expander graph instances. Spielman [25] shows an algorithm for … In this paper we show lower bounds for a certain large class of algorithms solving the Graph Isomorphism problem, even on expander graph instances. Spielman [25] shows an algorithm for isomorphism of strongly regular expander graphs that runs in time exp(O(n^(1/3)) (this bound was recently improved to expf O(n^(1/5) [5]). It has since been an open question to remove the requirement that the graph be strongly regular. Recent algorithmic results show that for many problems the Lasserre hierarchy works surprisingly well when the underlying graph has expansion properties. Moreover, recent work of Atserias and Maneva [3] shows that k rounds of the Lasserre hierarchy is a generalization of the k-dimensional Weisfeiler-Lehman algorithm for Graph Isomorphism. These two facts combined make the Lasserre hierarchy a good candidate for solving graph isomorphism on expander graphs. Our main result rules out this promising direction by showing that even Omega(n) rounds of the Lasserre semidefinite program hierarchy fail to solve the Graph Isomorphism problem even on expander graphs.

Water from Two Rocks: Maximizing the Mutual Information

2018-01-01

Yuqing Kong , Grant Schoenebeck

We build a natural connection between the learning problem, co-training, and forecast elicitation without verification (related to peer-prediction) and address them simultaneously using the same information theoretic approach. In co-training/multiview … We build a natural connection between the learning problem, co-training, and forecast elicitation without verification (related to peer-prediction) and address them simultaneously using the same information theoretic approach. In co-training/multiview learning, the goal is to aggregate two views of data into a prediction for a latent label. We show how to optimally combine two views of data by reducing the problem to an optimization problem. Our work gives a unified and rigorous approach to the general setting. In forecast elicitation without verification we seek to design a mechanism that elicits high quality forecasts from agents in the setting where the mechanism does not have access to the ground truth. By assuming the agents' information is independent conditioning on the outcome, we propose mechanisms where truth-telling is a strict equilibrium for both the single-task and multi-task settings. Our multi-task mechanism additionally has the property that the truth-telling equilibrium pays better than any other strategy profile and strictly better than any other "non-permutation" strategy profile when the prior satisfies some mild conditions.

Optimal Testing of Reed-Muller Codes

2010-01-01

Arnab Bhattacharyya , Swastik Kopparty , Grant Schoenebeck +2 more

View PDF Chat

Characterizing strategic cascades on networks

2014-05-30

Travis Martin , Grant Schoenebeck , Michael P. Wellman

Transmission of disease, spread of information and rumors, adoption of new products, and many other network phenomena can be fruitfully modeled as cascading processes, where actions chosen by nodes influence … Transmission of disease, spread of information and rumors, adoption of new products, and many other network phenomena can be fruitfully modeled as cascading processes, where actions chosen by nodes influence the subsequent behavior of neighbors in the network graph. Current literature on cascades tends to assume nodes choose myopically based on the state of choices already taken by other nodes. We examine the possibility of strategic choice, where agents representing nodes anticipate the choices of others who have not yet decided, and take into account their own influence on such choices. Our study employs the framework of Chierichetti et al. [2012], who (under assumption of myopic node behavior) investigate the scheduling of node decisions to promote cascades of product adoptions preferred by the scheduler. We show that when nodes behave strategically, outcomes can be extremely different. We exhibit cases where in the strategic setting 100% of agents adopt, but in the myopic setting only an arbitrarily small ε do. Conversely, we present cases where in the strategic setting 0% of agents adopt, but in the myopic setting (100-ε)% do, for any constant ε > 0. Additionally, we prove some properties of cascade processes with strategic agents, both in general and for particular classes of graphs.

View PDF Chat

How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks

2014-01-01

Roozbeh Ebrahimi , Jie Gao , Golnaz Ghasemiesfeh +1 more

In this paper, we study the spreading speed of complex contagions in a social network. A $k$-complex contagion starts from a set of initially infected seeds such that any node … In this paper, we study the spreading speed of complex contagions in a social network. A $k$-complex contagion starts from a set of initially infected seeds such that any node with at least $k$ infected neighbors gets infected. Simple contagions, i.e., $k=1$, quickly spread to the entire network in small world graphs. However, fast spreading of complex contagions appears to be less likely and more delicate; the successful cases depend crucially on the network structure~\cite{G08,Ghasemiesfeh:2013:CCW}. Our main result shows that complex contagions can spread fast in a general family of time-evolving networks that includes the preferential attachment model~\cite{barabasi99emergence}. We prove that if the initial seeds are chosen as the oldest nodes in a network of this family, a $k$-complex contagion covers the entire network of $n$ nodes in $O(\log n)$ steps. We show that the choice of the initial seeds is crucial. If the initial seeds are uniformly randomly chosen in the PA model, even with a polynomial number of them, a complex contagion would stop prematurely. The oldest nodes in a preferential attachment model are likely to have high degrees. However, we remark that it is actually not the power law degree distribution per se that facilitates fast spreading of complex contagions, but rather the evolutionary graph structure of such models. Some members of the said family do not even have a power-law distribution. We also prove that complex contagions are fast in the copy model~\cite{KumarRaRa00}, a variant of the preferential attachment family. Finally, we prove that when a complex contagion starts from an arbitrary set of initial seeds on a general graph, determining if the number of infected vertices is above a given threshold is $\mathbf{P}$-complete. Thus, one cannot hope to categorize all the settings in which complex contagions percolate in a graph.

Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

2011-01-01

Sanjeev Arora , Rong Ge , Sushant Sachdeva +1 more

A "community" in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is … A "community" in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concept in most domains where networks arise: social, technological, biological, etc. For many years algorithms for finding communities implicitly assumed communities are nonoverlapping (leading to use of clustering-based approaches) but there is increasing interest in finding overlapping communities. A barrier to finding communities is that the solution concept is often defined in terms of an NP-complete problem such as Clique or Hierarchical Clustering. This paper seeks to initiate a rigorous approach to the problem of finding overlapping communities, where "rigorous" means that we clearly state the following: (a) the object sought by our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running time. Our assumptions about the network lie between worst-case and average-case. An average case analysis would require a precise probabilistic model of the network, on which there is currently no consensus. However, some plausible assumptions about network parameters can be gleaned from a long body of work in the sociology community spanning five decades focusing on the study of individual communities and ego-centric networks. Thus our assumptions are somewhat "local" in nature. Nevertheless they suffice to permit a rigorous analysis of running time of algorithms that recover global structure. Our algorithms use random sampling similar to that in property testing and algorithms for dense graphs. However, our networks are not necessarily dense graphs, not even in local neighborhoods. Our algorithms explore a local-global relationship between ego-centric and socio-centric networks that we hope will provide a fruitful framework for future work both in computer science and sociology.

Limitations of Greed: Influence Maximization in Undirected Networks Re-visited

2020-01-01

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

We consider the influence maximization problem (selecting $k$ seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we … We consider the influence maximization problem (selecting $k$ seeds in a network maximizing the expected total influence) on undirected graphs under the linear threshold model. On the one hand, we prove that the greedy algorithm always achieves a $(1 - (1 - 1/k)^k + \Omega(1/k^3))$-approximation, showing that the greedy algorithm does slightly better on undirected graphs than the generic $(1- (1 - 1/k)^k)$ bound which also applies to directed graphs. On the other hand, we show that substantial improvement on this bound is impossible by presenting an example where the greedy algorithm can obtain at most a $(1- (1 - 1/k)^k + O(1/k^{0.2}))$ approximation. This result stands in contrast to the previous work on the independent cascade model. Like the linear threshold model, the greedy algorithm obtains a $(1-(1-1/k)^k)$-approximation on directed graphs in the independent cascade model. However, Khanna and Lucier showed that, in undirected graphs, the greedy algorithm performs substantially better: a $(1-(1-1/k)^k + c)$ approximation for constant $c > 0$. Our results show that, surprisingly, no such improvement occurs in the linear threshold model. Finally, we show that, under the linear threshold model, the approximation ratio $(1 - (1 - 1/k)^k)$ is tight if 1) the graph is directed or 2) the vertices are weighted. In other words, under either of these two settings, the greedy algorithm cannot achieve a $(1 - (1 - 1/k)^k + f(k))$-approximation for any positive function $f(k)$. The result in setting 2) is again in a sharp contrast to Khanna and Lucier's $(1 - (1 - 1/k)^k + c)$-approximation result for the independent cascade model, where the $(1 - (1 - 1/k)^k + c)$ approximation guarantee can be extended to the setting where vertices are weighted. We also discuss extensions to more generalized settings including those with edge-weighted graphs.

Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach

2020-01-01

Grant Schoenebeck , Fang-Yi Yu

Peer prediction mechanisms incentivize agents to truthfully report their signals even in the absence of verification by comparing agents' reports with those of their peers. In the detail-free multi-task setting, … Peer prediction mechanisms incentivize agents to truthfully report their signals even in the absence of verification by comparing agents' reports with those of their peers. In the detail-free multi-task setting, agents respond to multiple independent and identically distributed tasks, and the mechanism does not know the prior distribution of agents' signals. The goal is to provide an $\epsilon$-strongly truthful mechanism where truth-telling rewards agents "strictly" more than any other strategy profile (with $\epsilon$ additive error), and to do so while requiring as few tasks as possible. We design a family of mechanisms with a scoring function that maps a pair of reports to a score. The mechanism is strongly truthful if the scoring function is "prior ideal," and $\epsilon$-strongly truthful as long as the scoring function is sufficiently close to the ideal one. This reduces the above mechanism design problem to a learning problem -- specifically learning an ideal scoring function. We leverage this reduction to obtain the following three results. 1) We show how to derive good bounds on the number of tasks required for different types of priors. Our reduction applies to myriad continuous signal space settings. This is the first peer-prediction mechanism on continuous signals designed for the multi-task setting. 2) We show how to turn a soft-predictor of an agent's signals (given the other agents' signals) into a mechanism. This allows the practical use of machine learning algorithms that give good results even when many agents provide noisy information. 3) For finite signal spaces, we obtain $\epsilon$-strongly truthful mechanisms on any stochastically relevant prior, which is the maximal possible prior. In contrast, prior work only achieves a weaker notion of truthfulness (informed truthfulness) or requires stronger assumptions on the prior.

View PDF Chat

Survey Equivalence: A Procedure for Measuring Classifier Accuracy Against Human Labels

2021-01-01

Paul Resnick , Yuqing Kong , Grant Schoenebeck +1 more

In many classification tasks, the ground truth is either noisy or subjective. Examples include: which of two alternative paper titles is better? is this comment toxic? what is the political … In many classification tasks, the ground truth is either noisy or subjective. Examples include: which of two alternative paper titles is better? is this comment toxic? what is the political leaning of this news article? We refer to such tasks as survey settings because the ground truth is defined through a survey of one or more human raters. In survey settings, conventional measurements of classifier accuracy such as precision, recall, and cross-entropy confound the quality of the classifier with the level of agreement among human raters. Thus, they have no meaningful interpretation on their own. We describe a procedure that, given a dataset with predictions from a classifier and K ratings per item, rescales any accuracy measure into one that has an intuitive interpretation. The key insight is to score the classifier not against the best proxy for the ground truth, such as a majority vote of the raters, but against a single human rater at a time. That score can be compared to other predictors' scores, in particular predictors created by combining labels from several other human raters. The survey equivalence of any classifier is the minimum number of raters needed to produce the same expected score as that found for the classifier.

Think globally, act locally: On the optimal seeding for nonsubmodular influence maximization

2022-05-01

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

View PDF Chat

An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling

2016-01-01

Yuqing Kong , Grant Schoenebeck

In the setting where information cannot be verified, we propose a simple yet powerful information theoretical framework---the Mutual Information Paradigm---for information elicitation mechanisms. Our framework pays every agent a measure … In the setting where information cannot be verified, we propose a simple yet powerful information theoretical framework---the Mutual Information Paradigm---for information elicitation mechanisms. Our framework pays every agent a measure of mutual information between her signal and a peer's signal. We require that the mutual information measurement has the key property that any "data processing" on the two random variables will decrease the mutual information between them. We identify such information measures that generalize Shannon mutual information. Our Mutual Information Paradigm overcomes the two main challenges in information elicitation without verification: (1) how to incentivize effort and avoid agents colluding to report random or identical responses (2) how to motivate agents who believe they are in the minority to report truthfully. Aided by the information measures we found, (1) we use the paradigm to design a family of novel mechanisms where truth-telling is a dominant strategy and any other strategy will decrease every agent's expected payment (in the multi-question, detail free, minimal setting where the number of questions is large); (2) we show the versatility of our framework by providing a unified theoretical understanding of existing mechanisms---Peer Prediction [Miller 2005], Bayesian Truth Serum [Prelec 2004], and Dasgupta and Ghosh [2013]---by mapping them into our framework such that theoretical results of those existing mechanisms can be reconstructed easily. We also give an impossibility result which illustrates, in a certain sense, the the optimality of our framework.

View PDF Chat

Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

2016-09-21

Rico Angell , Grant Schoenebeck

We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds --- a central problem in the study of … We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds --- a central problem in the study of network cascades. The majority of existing work on this problem, formally referred to as the influence maximization problem, is designed for submodular cascades. Despite the empirical evidence that many cascades are non-submodular, little work has been done focusing on non-submodular influence maximization. We propose a new heuristic for solving the influence maximization problem and show via simulations on real-world and synthetic networks that our algorithm outputs more influential seed sets than the state-of-the-art greedy algorithm in many natural cases, with average improvements of 7% for submodular cascades, and 55% for non-submodular cascades. Our heuristic uses a dynamic programming approach on a hierarchical decomposition of the social network to leverage the relation between the spread of cascades and the community structure of social networks. We verify the importance of network structure by showing the quality of the hierarchical decomposition impacts the quality of seed set output by our algorithm. We also present worst-case theoretical results proving that in certain settings our algorithm outputs seed sets that are a factor of $\Theta(\sqrt{n})$ more influential than those of the greedy algorithm, where $n$ is the number of nodes in the network. Finally, we generalize our algorithm to a message passing version that can be used to find seed sets that have at least as much influence as the dynamic programming algorithms.

Social Learning in a Changing World

2011-09-26

Rafael Frongillo , Grant Schoenebeck , Omer Tamuz

We study a model of learning on social networks in dynamic environments, describing a group of agents who are each trying to estimate an underlying state that varies over time, … We study a model of learning on social networks in dynamic environments, describing a group of agents who are each trying to estimate an underlying state that varies over time, given access to weak signals and the estimates of their social network neighbors. We study three models of agent behavior. In the model, agents use a fixed linear combination to incorporate information from their peers into their own estimate. This can be thought of as an extension of the DeGroot model to a dynamic setting. In the model, players calculate minimum variance linear estimators of the underlying state. We show that regardless of the initial configuration, fixed response dynamics converge to a steady state, and that the same holds for best response on the complete graph. We show that best response dynamics can, in the long term, lead to estimators with higher variance than is achievable using well chosen fixed responses. The penultimate prediction model is an elaboration of the best response model. While this model only slightly complicates the computations required of the agents, we show that in some cases it greatly increases the efficiency of learning, and on complete graphs is in fact optimal, in a strong sense.

Social learning with questions

2019-06-28

Shih-Tang Su , Vijay Subramanian , Grant Schoenebeck

In social networks, agents use information from (a) private signals (knowledge) they have, (b) learning past agents actions (observations), and (c) comments from contactable experienced agents (experts) to guide their … In social networks, agents use information from (a) private signals (knowledge) they have, (b) learning past agents actions (observations), and (c) comments from contactable experienced agents (experts) to guide their own decisions. With fully observable history and bounded likelihood ratio of signal, Information Cascade occurs almost surely when it is optimal for agents to ignore their private signals for decision making after observing the history. Though individually optimal, this may lead to a socially sub-optimal outcome. Literature studying social learning, i.e., making socially optimal decisions, is mainly focused on using channels (a) and (b) above for Bayes-rational agents by either relaxing the assumption of bounded signal strength or allowing the distortion of the history. In this work, we enable a limited communication capacity to let Bayes-rational agents querying their predecessors, motivated by the real-world behavior that people usually consult several friends before making decisions. We allow each Bayes-rational agent to ask a single, private and finite-capacity (for response) question of each among a subset of predecessors. Note that the Maximum Aposteriori Probability (MAP) rule is still individually optimally and will be used by each agent for her decision. With an endowed communication capacity, we want to answer the following two questions: 1) What is the suitable framework to model the help that questions provide on information aggregation? 2) Can we construct a set of questions that will achieve learning by querying the minimum set of agents with the minimum capacity requirements (in terms of bits)?

View PDF Chat

Measurement Integrity in Peer Prediction: A Peer Assessment Case Study

2023-07-07

Noah Burrell , Grant Schoenebeck

View PDF Chat

A System-Level Analysis of Conference Peer Review

2022-07-12

Yichi Zhang , Fang-Yi Yu , Grant Schoenebeck +1 more

The conference peer review process involves three constituencies with different objectives: authors want their papers accepted at prestigious venues (and quickly), conferences want to present a program with many high-quality … The conference peer review process involves three constituencies with different objectives: authors want their papers accepted at prestigious venues (and quickly), conferences want to present a program with many high-quality and few low-quality papers, and reviewers want to avoid being overburdened by reviews. These objectives are far from aligned, primarily because the evaluation of a submission is inherently noisy. Over the years, conferences have experimented with numerous policies to navigate the tradeoffs. These experiments include setting various bars for acceptance, varying the number of reviews per submission, requiring prior reviews to be included with resubmissions, and others. In this work, we investigate, both analytically and empirically, how well various policies work, and more importantly, why they do or do not work. We model the conference-author interactions as a Stackelberg game in which a prestigious conference commits to an acceptance policy; the authors best-respond by (re)submitting or not (re)submitting to the conference in each round of review, the alternative being a "sure accept" (such as a lightly refereed venue). Our main results include the following observations: 1) the conference should typically set a higher acceptance threshold than the actual desired quality; we call this the "resubmission gap". 2) the reviewing load is heavily driven by resubmissions of borderline papers - therefore, a judicious choice of acceptance threshold may lead to fewer reviews while incurring an acceptable loss in conference quality. 3) conference prestige, reviewer inaccuracy, and author patience increase the resubmission gap, and thus increase the review load for a fixed level of conference quality. For robustness, we further consider different models of paper quality and compare our theoretical results to simulations based on plausible parameters estimated from real data.

View PDF Chat

Filter Bubble or Homogenization? Disentangling the Long-Term Effects of Recommendations on User Consumption Patterns

2024-05-08

Md Sanzeed Anwar , Grant Schoenebeck , Paramveer S. Dhillon

Recommendation algorithms play a pivotal role in shaping our media choices, which makes it crucial to comprehend their long-term impact on user behavior.These algorithms are often linked to two critical … Recommendation algorithms play a pivotal role in shaping our media choices, which makes it crucial to comprehend their long-term impact on user behavior.These algorithms are often linked to two critical outcomes: homogenization, wherein users consume similar content despite disparate underlying preferences, and the filter bubble effect, wherein individuals with differing preferences only consume content aligned with their preferences (without much overlap with other users).Prior research assumes a trade-off between homogenization and filter bubble effects and then shows that personalized recommendations mitigate filter bubbles by fostering homogenization.However, because of this assumption of a tradeoff between these two effects, prior work cannot develop a more nuanced view of how recommendation systems may independently impact homogenization and filter bubble effects.We develop a more refined definition of homogenization and the filter bubble effect by decomposing them into two key metrics: how different the average consumption is between users (inter-user diversity) and how varied an individual's consumption is (intra-user diversity).We then use a novel agent-based simulation framework that enables a holistic view of the impact of recommendation systems on homogenization and filter bubble effects.Our simulations show that traditional recommendation algorithms (based on past behavior) mainly reduce filter bubbles by affecting inter-user diversity without significantly impacting intra-user diversity.Building on these findings, we introduce two new recommendation algorithms that take a more nuanced approach by accounting for both types of diversity.

View PDF Chat

Outsourcing Computation: The Minimal Refereed Mechanism

2019-01-01

Yuqing Kong , Chris Peikert , Grant Schoenebeck +1 more

View PDF Chat

Measurement Integrity in Peer Prediction: A Peer Assessment Case Study

2021-01-01

Noah Burrell , Grant Schoenebeck

We propose measurement integrity, a property related to ex post reward fairness, as a novel desideratum for peer prediction mechanisms in many natural applications. Like robustness against strategic reporting, the … We propose measurement integrity, a property related to ex post reward fairness, as a novel desideratum for peer prediction mechanisms in many natural applications. Like robustness against strategic reporting, the property that has been the primary focus of the peer prediction literature, measurement integrity is an important consideration for understanding the practical performance of peer prediction mechanisms. We perform computational experiments, both with an agent-based model and with real data, to empirically evaluate peer prediction mechanisms according to both of these important properties. Our evaluations simulate the application of peer prediction mechanisms to peer assessment -- a setting in which ex post fairness concerns are particularly salient. We find that peer prediction mechanisms, as proposed in the literature, largely fail to demonstrate significant measurement integrity in our experiments. We also find that theoretical properties concerning robustness against strategic reporting are somewhat noisy predictors of empirical performance. Further, there is an apparent trade-off between our two dimensions of analysis. The best-performing mechanisms in terms of measurement integrity are highly susceptible to strategic reporting. Ultimately, however, we show that supplementing mechanisms with realistic parametric statistical models can, in some cases, improve performance along both dimensions of our analysis and result in mechanisms that strike the best balance between them.

View PDF Chat

Potential Networks, Contagious Communities, and Understanding Social Network Structure

2013-01-01

Grant Schoenebeck

In this paper we study how the network of agents adopting a particular technology relates to the structure of the underlying network over which the technology adoption spreads. We develop … In this paper we study how the network of agents adopting a particular technology relates to the structure of the underlying network over which the technology adoption spreads. We develop a model and show that the network of agents adopting a particular technology may have characteristics that differ significantly from the social network of agents over which the technology spreads. For example, the network induced by a cascade may have a heavy-tailed degree distribution even if the original network does not. This provides evidence that online social networks created by technology adoption over an underlying social network may look fundamentally different from social networks and indicates that using data from many online social networks may mislead us if we try to use it to directly infer the structure of social networks. Our results provide an alternate explanation for certain properties repeatedly observed in data sets, for example: heavy-tailed degree distribution, network densification, shrinking diameter, and network community profile. These properties could be caused by a sort of `sampling bias' rather than by attributes of the underlying social structure. By generating networks using cascades over traditional network models that do not themselves contain these properties, we can nevertheless reliably produce networks that contain all these properties. An opportunity for interesting future research is developing new methods that correctly infer underlying network structure from data about a network that is generated via a cascade spread over the underlying network.

How Complex Contagions Spread and Spread Quickly.

2014-04-10

Roozbeh Ebrahimi , Jie Gao , Golnaz Ghasemiesfeh +1 more

General Hardness Amplification of Predicates and Puzzles

2010-02-18

Thomas Holenstein , Grant Schoenebeck

We give new proofs for the hardness amplification of efficiently samplable predicates and of weakly verifiable puzzles which generalize to new settings. More concretely, in the first part of the … We give new proofs for the hardness amplification of efficiently samplable predicates and of weakly verifiable puzzles which generalize to new settings. More concretely, in the first part of the paper, we give a new proof of Yao's XOR-Lemma that additionally applies to related theorems in the cryptographic setting. Our proof seems simpler than previous ones, yet immediately generalizes to statements similar in spirit such as the extraction lemma used to obtain pseudo-random generators from one-way functions [Hastad, Impagliazzo, Levin, Luby, SIAM J. on Comp. 1999]. In the second part of the paper, we give a new proof of hardness amplification for weakly verifiable puzzles, which is more general than previous ones in that it gives the right bound even for an arbitrary monotone function applied to the checking circuit of the underlying puzzle. Both our proofs are applicable in many settings of interactive cryptographic protocols because they satisfy a property that we call non-rewinding. In particular, we show that any weak cryptographic protocol whose security is given by the unpredictability of single bits can be strengthened with a natural information theoretic protocol. As an example, we show how these theorems solve the main open question from [Halevi and Rabin, TCC2008] concerning bit commitment.

Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization.

2019-01-01

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

We study the r-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of … We study the r-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the r-complex contagion model, each uninfected vertex in the network becomes infected if it has at least r infected neighbors. In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the well-studied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability omega (n^{-(1+1/r)}), under certain mild assumptions, we prove that the optimal seeding strategy is to put all the seeds in a single community. This matches the intuition that in a nonsubmodular cascade model placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e.g., the independent cascade model and the linear threshold model) in which nearby seeds tend to erode each others' effects. Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in omega (n^{-(1+1/r)}) or in o (n^{-2}).

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

2021-01-01

Grant Schoenebeck , Biaoshuai Tao

We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. … We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. Voters may be "contingent" with different preferences in different states; or predetermined with the same preference in every state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased. We present an easy-to-deploy mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).

View PDF Chat

SURPRISE! and When to Schedule It.

2021-08-01

Zhihuan Huang , Shengwei Xu , Shan You +4 more

Information flow measures, over the duration of a game, the audience’s belief of who will win, and thus can reflect the amount of surprise in a game. To quantify the … Information flow measures, over the duration of a game, the audience’s belief of who will win, and thus can reflect the amount of surprise in a game. To quantify the relationship between information flow and audiences' perceived quality, we conduct a case study where subjects watch one of the world’s biggest esports events, LOL S10. In addition to eliciting information flow, we also ask subjects to report their rating for each game. We find that the amount of surprise in the end of the game plays a dominant role in predicting the rating. This suggests the importance of incorporating when the surprise occurs, in addition to the amount of surprise, in perceived quality models. For content providers, it implies that everything else being equal, it is better for twists to be more likely to happen toward the end of a show rather than uniformly throughout.

View PDF Chat

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

2021-12-06

Grant Schoenebeck , Biaoshuai Tao

We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. … We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. Voters may be with different preferences in different states; or predetermined with the same preference in every state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased. We present an easy-to-deploy mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).

Bayesian Persuasion in Sequential Trials

2022-01-01

Shih-Tang Su , Vijay Subramanian , Grant Schoenebeck

View PDF Chat

Optimal Local Bayesian Differential Privacy over Markov Chains

2022-01-01

Darshan Chakrabarti , Jie Gao , Aditya Saraf +2 more

In the literature of data privacy, differential privacy is the most popular model. An algorithm is differentially private if its outputs with and without any individual's data are indistinguishable. In … In the literature of data privacy, differential privacy is the most popular model. An algorithm is differentially private if its outputs with and without any individual's data are indistinguishable. In this paper, we focus on data generated from a Markov chain and argue that Bayesian differential privacy (BDP) offers more meaningful guarantees in this context. Our main theoretical contribution is providing a mechanism for achieving BDP when data is drawn from a binary Markov chain. We improve on the state-of-the-art BDP mechanism and show that our mechanism provides the optimal noise-privacy tradeoffs for any local mechanism up to negligible factors. We also briefly discuss a non-local mechanism which adds correlated noise. Lastly, we perform experiments on synthetic data that detail when DP is insufficient, and experiments on real data to show that our privacy guarantees are robust to underlying distributions that are not simple Markov chains.

View PDF Chat

Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms

2010-01-01

Anupam Gupta , Aaron Roth , Grant Schoenebeck +1 more

Constrained submodular maximization problems have long been studied, with near-optimal results known under a variety of constraints when the submodular function is monotone. The case of non-monotone submodular maximization is … Constrained submodular maximization problems have long been studied, with near-optimal results known under a variety of constraints when the submodular function is monotone. The case of non-monotone submodular maximization is less understood: the first approximation algorithms even for the unconstrainted setting were given by Feige et al. (FOCS '07). More recently, Lee et al. (STOC '09, APPROX '09) show how to approximately maximize non-monotone submodular functions when the constraints are given by the intersection of p matroid constraints; their algorithm is based on local-search procedures that consider p-swaps, and hence the running time may be n^Omega(p), implying their algorithm is polynomial-time only for constantly many matroids. In this paper, we give algorithms that work for p-independence systems (which generalize constraints given by the intersection of p matroids), where the running time is poly(n,p). Our algorithm essentially reduces the non-monotone maximization problem to multiple runs of the greedy algorithm previously used in the monotone case. Our idea of using existing algorithms for monotone functions to solve the non-monotone case also works for maximizing a submodular function with respect to a knapsack constraint: we get a simple greedy-based constant-factor approximation for this problem. With these simpler algorithms, we are able to adapt our approach to constrained non-monotone submodular maximization to the (online) secretary setting, where elements arrive one at a time in random order, and the algorithm must make irrevocable decisions about whether or not to select each element as it arrives. We give constant approximations in this secretary setting when the algorithm is constrained subject to a uniform matroid or a partition matroid, and give an O(log k) approximation when it is constrained by a general matroid of rank k.

View PDF Chat

Strong Equilibria in Bayesian Games with Bounded Group Size

2025-04-22

Qishen Han , Grant Schoenebeck , Biaoshuai Tao +1 more

We study the group strategic behaviors in Bayesian games. Equilibria in previous work do not consider group strategic behaviors with bounded sizes and are too ``strong'' to exist in many … We study the group strategic behaviors in Bayesian games. Equilibria in previous work do not consider group strategic behaviors with bounded sizes and are too ``strong'' to exist in many scenarios. We propose the ex-ante Bayesian $k$-strong equilibrium and the Bayesian $k$-strong equilibrium, where no group of at most $k$ agents can benefit from deviation. The two solution concepts differ in how agents calculate their utilities when contemplating whether a deviation is beneficial. Intuitively, agents are more conservative in the Bayesian $k$-strong equilibrium than in the ex-ante Bayesian $k$-strong equilibrium. With our solution concepts, we study collusion in the peer prediction mechanisms, as a representative of the Bayesian games with group strategic behaviors. We characterize the thresholds of the group size $k$ so that truthful reporting in the peer prediction mechanism is an equilibrium for each solution concept, respectively. Our solution concepts can serve as criteria to evaluate the robustness of a peer prediction mechanism against collusion. Besides the peer prediction problem, we also discuss two other potential applications of our new solution concepts, voting and Blotto games, where introducing bounded group sizes provides more fine-grained insights into the behavior of strategic agents.

View PDF Chat

Recommendation and Temptation

2024-12-13

Md Sanzeed Anwar , Paramveer S. Dhillon , Grant Schoenebeck

Traditional recommender systems based on utility maximization and revealed preferences often fail to capture users' dual-self nature, where consumption choices are driven by both long-term benefits (enrichment) and desire for … Traditional recommender systems based on utility maximization and revealed preferences often fail to capture users' dual-self nature, where consumption choices are driven by both long-term benefits (enrichment) and desire for instant gratification (temptation). Consequently, these systems may generate recommendations that fail to provide long-lasting satisfaction to users. To address this issue, we propose a novel user model that accounts for this dual-self behavior and develop an optimal recommendation strategy to maximize enrichment from consumption. We highlight the limitations of historical consumption data in implementing this strategy and present an estimation framework that makes minimal assumptions and leverages explicit user feedback and implicit choice data to overcome these constraints. We evaluate our approach through both synthetic simulations and simulations based on real-world data from the MovieLens dataset. Results demonstrate that our proposed recommender can deliver superior enrichment compared to several competitive baseline algorithms that assume a single utility type and rely solely on revealed preferences. Our work emphasizes the critical importance of optimizing for enrichment in recommender systems, particularly in temptation-laden consumption contexts. Our findings have significant implications for content platforms, user experience design, and the development of responsible AI systems, paving the way for more nuanced and user-centric recommendation approaches.

View PDF Chat

Eliciting Informative Text Evaluations with Large Language Models

2024-05-23

Yuxuan Lu , Shengwei Xu , Yichi Zhang +2 more

Peer prediction mechanisms motivate high-quality feedback with provable guarantees. However, current methods only apply to rather simple reports, like multiple-choice or scalar numbers. We aim to broaden these techniques to … Peer prediction mechanisms motivate high-quality feedback with provable guarantees. However, current methods only apply to rather simple reports, like multiple-choice or scalar numbers. We aim to broaden these techniques to the larger domain of text-based reports, drawing on the recent developments in large language models. This vastly increases the applicability of peer prediction mechanisms as textual feedback is the norm in a large variety of feedback channels: peer reviews, e-commerce customer reviews, and comments on social media. We introduce two mechanisms, the Generative Peer Prediction Mechanism (GPPM) and the Generative Synopsis Peer Prediction Mechanism (GSPPM). These mechanisms utilize LLMs as predictors, mapping from one agent's report to a prediction of her peer's report. Theoretically, we show that when the LLM prediction is sufficiently accurate, our mechanisms can incentivize high effort and truth-telling as an (approximate) Bayesian Nash equilibrium. Empirically, we confirm the efficacy of our mechanisms through experiments conducted on two real datasets: the Yelp review dataset and the ICLR OpenReview dataset. We highlight the results that on the ICLR dataset, our mechanisms can differentiate three quality levels -- human-written reviews, GPT-4-generated reviews, and GPT-3.5-generated reviews in terms of expected scores. Additionally, GSPPM penalizes LLM-generated reviews more effectively than GPPM.

View PDF Chat

Exit Ripple Effects: Understanding the Disruption of Socialization Networks Following Employee Departures

2024-05-08

David Gamba , Yulin Yu , Yuan Yuan +2 more

Amidst growing uncertainty and frequent restructurings, the impacts of employee exits are becoming one of the central concerns for organizations. Using rich communication data from a large holding company, we … Amidst growing uncertainty and frequent restructurings, the impacts of employee exits are becoming one of the central concerns for organizations. Using rich communication data from a large holding company, we examine the effects of employee departures on socialization networks among the remaining coworkers. Specifically, we investigate how network metrics change among people who historically interacted with departing employees. We find evidence of ``breakdown" in communication among the remaining coworkers, who tend to become less connected with fewer interactions after their coworkers' departure. This effect appears to be moderated by both external factors, such as periods of high organizational stress, and internal factors, such as the characteristics of the departing employee. At the external level, periods of high stress correspond to greater communication breakdown; at the internal level, however, we find patterns suggesting individuals may end up better positioned in their networks after a network neighbor's departure. Overall, our study provides critical insights into managing workforce changes and preserving communication dynamics in the face of employee exits.

View PDF Chat

Filter Bubble or Homogenization? Disentangling the Long-Term Effects of Recommendations on User Consumption Patterns

2024-05-08

Md Sanzeed Anwar , Grant Schoenebeck , Paramveer S. Dhillon

View PDF Chat

Spot Check Equivalence: An Interpretable Metric for Information Elicitation Mechanisms

2024-05-08

Shengwei Xu , Yichi Zhang , Paul Resnick +1 more

Because high-quality data is like oxygen for AI systems, effectively eliciting information from crowdsourcing workers has become a first-order problem for developing high-performance machine learning algorithms. Two prevalent paradigms, spot-checking … Because high-quality data is like oxygen for AI systems, effectively eliciting information from crowdsourcing workers has become a first-order problem for developing high-performance machine learning algorithms. Two prevalent paradigms, spot-checking and peer prediction, enable the design of mechanisms to evaluate and incentivize high-quality data from human labelers. So far, at least three metrics have been proposed to compare the performances of these techniques \citepzhang2022high,gao2016incentivizing,burrell2021measurement. However, different metrics lead to divergent and even contradictory results in various contexts. In this paper, we harmonize these divergent stories, showing that two of these metrics are actually the same within certain contexts and explain the divergence of the third. Moreover, we unify these different contexts by introducingSpot Check Equivalence, which offers an interpretable metric for the effectiveness of a peer prediction mechanism. Finally, we present two approaches to compute spot check equivalence in various contexts, where simulation results verify the effectiveness of our proposed metric.

View PDF Chat

Eliciting Honest Information from Authors Using Sequential Review

2024-03-24

Yichi Zhang , Grant Schoenebeck , Weijie Su

In the setting of conference peer review, the conference aims to accept high-quality papers and reject low-quality papers based on noisy review scores. A recent work proposes the isotonic mechanism, … In the setting of conference peer review, the conference aims to accept high-quality papers and reject low-quality papers based on noisy review scores. A recent work proposes the isotonic mechanism, which can elicit the ranking of paper qualities from an author with multiple submissions to help improve the conference's decisions. However, the isotonic mechanism relies on the assumption that the author's utility is both an increasing and a convex function with respect to the review score, which is often violated in realistic settings (e.g.~when authors aim to maximize the number of accepted papers). In this paper, we propose a sequential review mechanism that can truthfully elicit the ranking information from authors while only assuming the agent's utility is increasing with respect to the true quality of her accepted papers. The key idea is to review the papers of an author in a sequence based on the provided ranking and conditioning the review of the next paper on the review scores of the previous papers. Advantages of the sequential review mechanism include: 1) eliciting truthful ranking information in a more realistic setting than prior work; 2) reducing the reviewing workload and increasing the average quality of papers being reviewed; 3) incentivizing authors to write fewer papers of higher quality.

View PDF Chat

Filter Bubble or Homogenization? Disentangling the Long-Term Effects of Recommendations on User Consumption Patterns

2024-02-22

Md Sanzeed Anwar , Grant Schoenebeck , Paramveer S. Dhillon

Recommendation algorithms play a pivotal role in shaping our media choices, which makes it crucial to comprehend their long-term impact on user behavior. These algorithms are often linked to two … Recommendation algorithms play a pivotal role in shaping our media choices, which makes it crucial to comprehend their long-term impact on user behavior. These algorithms are often linked to two critical outcomes: homogenization, wherein users consume similar content despite disparate underlying preferences, and the filter bubble effect, wherein individuals with differing preferences only consume content aligned with their preferences (without much overlap with other users). Prior research assumes a trade-off between homogenization and filter bubble effects and then shows that personalized recommendations mitigate filter bubbles by fostering homogenization. However, because of this assumption of a tradeoff between these two effects, prior work cannot develop a more nuanced view of how recommendation systems may independently impact homogenization and filter bubble effects. We develop a more refined definition of homogenization and the filter bubble effect by decomposing them into two key metrics: how different the average consumption is between users (inter-user diversity) and how varied an individual's consumption is (intra-user diversity). We then use a novel agent-based simulation framework that enables a holistic view of the impact of recommendation systems on homogenization and filter bubble effects. Our simulations show that traditional recommendation algorithms (based on past behavior) mainly reduce filter bubbles by affecting inter-user diversity without significantly impacting intra-user diversity. Building on these findings, we introduce two new recommendation algorithms that take a more nuanced approach by accounting for both types of diversity.

View PDF Chat

Spot Check Equivalence: an Interpretable Metric for Information Elicitation Mechanisms

2024-02-21

Shengwei Xu , Yichi Zhang , Paul Resnick +1 more

Because high-quality data is like oxygen for AI systems, effectively eliciting information from crowdsourcing workers has become a first-order problem for developing high-performance machine learning algorithms. Two prevalent paradigms, spot-checking … Because high-quality data is like oxygen for AI systems, effectively eliciting information from crowdsourcing workers has become a first-order problem for developing high-performance machine learning algorithms. Two prevalent paradigms, spot-checking and peer prediction, enable the design of mechanisms to evaluate and incentivize high-quality data from human labelers. So far, at least three metrics have been proposed to compare the performances of these techniques [33, 8, 3]. However, different metrics lead to divergent and even contradictory results in various contexts. In this paper, we harmonize these divergent stories, showing that two of these metrics are actually the same within certain contexts and explain the divergence of the third. Moreover, we unify these different contexts by introducing \textit{Spot Check Equivalence}, which offers an interpretable metric for the effectiveness of a peer prediction mechanism. Finally, we present two approaches to compute spot check equivalence in various contexts, where simulation results verify the effectiveness of our proposed metric.

View PDF Chat

Measurement Integrity in Peer Prediction: A Peer Assessment Case Study

2023-07-07

Noah Burrell , Grant Schoenebeck

View PDF Chat

The Wisdom of Strategic Voting

2023-07-07

Qishen Han , Grant Schoenebeck , Biaoshuai Tao +1 more

We study the voting game where agents' preferences are endogenously decided by the information they receive, and they can collaborate in a group. We show that strategic voting behaviors have … We study the voting game where agents' preferences are endogenously decided by the information they receive, and they can collaborate in a group. We show that strategic voting behaviors have a positive impact on leading to the ``correct'' decision, outperforming the common non-strategic behavior of informative voting and sincere voting. Our results give merit to strategic voting for making good decisions. To this end, we investigate a natural model, where voters' preferences between two alternatives depend on a discrete state variable that is not directly observable. Each voter receives a private signal that is correlated with the state variable. We reveal a surprising equilibrium between a strategy profile being a strong equilibrium and leading to the decision favored by the majority of agents conditioned on them knowing the ground truth (referred to as the informed majority decision): as the size of the vote goes to infinity, every $\varepsilon$-strong Bayes Nash Equilibrium with $\varepsilon$ converging to $0$ formed by strategic agents leads to the informed majority decision with probability converging to $1$. On the other hand, we show that informative voting leads to the informed majority decision only under unbiased instances, and sincere voting leads to the informed majority decision only when it also forms an equilibrium.

View PDF Chat

The Wisdom of Strategic Voting

2023-01-01

Qishen Han , Grant Schoenebeck , Biaoshuai Tao +1 more

Eliciting Honest Information From Authors Using Sequential Review

2023-01-01

Yichi Zhang , Grant Schoenebeck , Weijie Su

In the setting of conference peer review, the conference aims to accept high-quality papers and reject low-quality papers based on noisy review scores. A recent work proposes the isotonic mechanism, … In the setting of conference peer review, the conference aims to accept high-quality papers and reject low-quality papers based on noisy review scores. A recent work proposes the isotonic mechanism, which can elicit the ranking of paper qualities from an author with multiple submissions to help improve the conference's decisions. However, the isotonic mechanism relies on the assumption that the author's utility is both an increasing and a convex function with respect to the review score, which is often violated in peer review settings (e.g.~when authors aim to maximize the number of accepted papers). In this paper, we propose a sequential review mechanism that can truthfully elicit the ranking information from authors while only assuming the agent's utility is increasing with respect to the true quality of her accepted papers. The key idea is to review the papers of an author in a sequence based on the provided ranking and conditioning the review of the next paper on the review scores of the previous papers. Advantages of the sequential review mechanism include 1) eliciting truthful ranking information in a more realistic setting than prior work; 2) improving the quality of accepted papers, reducing the reviewing workload and increasing the average quality of papers being reviewed; 3) incentivizing authors to write fewer papers of higher quality.

View PDF Chat

A System-Level Analysis of Conference Peer Review

2022-07-12

Yichi Zhang , Fang-Yi Yu , Grant Schoenebeck +1 more

View PDF Chat

Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization

2022-05-26

Wei Chen , Binghui Peng , Grant Schoenebeck +1 more

View PDF Chat

Think globally, act locally: On the optimal seeding for nonsubmodular influence maximization

2022-05-01

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

View PDF Chat

BONUS! Maximizing Surprise

2022-04-25

Zhihuan Huang , Yuqing Kong , Tracy Xiao Liu +2 more

Multi-round competitions often double or triple the points awarded in the final round, calling it a bonus, to maximize spectators' excitement. In a two-player competition with n rounds, we aim … Multi-round competitions often double or triple the points awarded in the final round, calling it a bonus, to maximize spectators' excitement. In a two-player competition with n rounds, we aim to derive the optimal bonus size to maximize the audience's overall expected surprise (as defined in [7]). We model the audience's prior belief over the two players' ability levels as a beta distribution. Using a novel analysis that clarifies and simplifies the computation, we find that the optimal bonus depends greatly upon the prior belief and obtain solutions of various forms for both the case of a finite number of rounds and the asymptotic case. In an interesting special case, we show that the optimal bonus approximately and asymptotically equals to the "expected lead", the number of points the weaker player will need to come back in expectation. Moreover, we observe that priors with a higher skewness lead to a higher optimal bonus size, and in the symmetric case, priors with a higher uncertainty also lead to a higher optimal bonus size. This matches our intuition since a highly asymmetric prior leads to a high "expected lead", and a highly uncertain symmetric prior often leads to a lopsided game, which again benefits from a larger bonus.

View PDF Chat

Bayesian Persuasion in Sequential Trials

2022-01-01

Shih-Tang Su , Vijay Subramanian , Grant Schoenebeck

View PDF Chat

False Consensus, Information Theory, and Prediction Markets

2022-01-01

Yuqing Kong , Grant Schoenebeck

We study a setting where Bayesian agents with a common prior have private information related to an event's outcome and sequentially make public announcements relating to their information. Our main … We study a setting where Bayesian agents with a common prior have private information related to an event's outcome and sequentially make public announcements relating to their information. Our main result shows that when agents' private information is independent conditioning on the event's outcome whenever agents have similar beliefs about the outcome, their information is aggregated. That is, there is no false consensus. Our main result has a short proof based on a natural information theoretic framework. A key ingredient of the framework is the equivalence between the sign of the ``interaction information'' and a super/sub-additive property of the value of people's information. This provides an intuitive interpretation and an interesting application of the interaction information, which measures the amount of information shared by three random variables. We illustrate the power of this information theoretic framework by reproving two additional results within it: 1) that agents quickly agree when announcing (summaries of) beliefs in round robin fashion [Aaronson 2005]; and 2) results from [Chen et al 2010] on when prediction market agents should release information to maximize their payment. We also interpret the information theoretic framework and the above results in prediction markets by proving that the expected reward of revealing information is the conditional mutual information of the information revealed.

View PDF Chat

Optimal Local Bayesian Differential Privacy over Markov Chains

2022-01-01

Darshan Chakrabarti , Jie Gao , Aditya Saraf +2 more

View PDF Chat

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

2021-12-06

Grant Schoenebeck , Biaoshuai Tao

We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. … We consider two-alternative elections where voters' preferences depend on a state variable that is not directly observable. Each voter receives a private signal that is correlated to the state variable. Voters may be with different preferences in different states; or predetermined with the same preference in every state. In this setting, even if every voter is a contingent voter, agents voting according to their private information need not result in the adoption of the universally preferred alternative, because the signals can be systematically biased. We present an easy-to-deploy mechanism that elicits and aggregates the private signals from the voters, and outputs the alternative that is favored by the majority. In particular, voters truthfully reporting their signals forms a strong Bayes Nash equilibrium (where no coalition of voters can deviate and receive a better outcome).

SURPRISE! and When to Schedule It.

2021-08-01

Zhihuan Huang , Shengwei Xu , Shan You +4 more

View PDF Chat

Survey Equivalence: A Procedure for Measuring Classifier Accuracy Against Human Labels

2021-01-01

Paul Resnick , Yuqing Kong , Grant Schoenebeck +1 more

SURPRISE! and When to Schedule It

2021-01-01

Zhihuan Huang , Shengwei Xu , Shan You +4 more

Information flow measures, over the duration of a game, the audience's belief of who will win, and thus can reflect the amount of surprise in a game. To quantify the … Information flow measures, over the duration of a game, the audience's belief of who will win, and thus can reflect the amount of surprise in a game. To quantify the relationship between information flow and audiences' perceived quality, we conduct a case study where subjects watch one of the world's biggest esports events, LOL S10. In addition to eliciting information flow, we also ask subjects to report their rating for each game. We find that the amount of surprise in the end of the game plays a dominant role in predicting the rating. This suggests the importance of incorporating when the surprise occurs, in addition to the amount of surprise, in perceived quality models. For content providers, it implies that everything else being equal, it is better for twists to be more likely to happen toward the end of a show rather than uniformly throughout.

View PDF Chat

Wisdom of the Crowd Voting: Truthful Aggregation of Voter Information and Preferences

2021-01-01

Grant Schoenebeck , Biaoshuai Tao

View PDF Chat

Bayesian Persuasion in Sequential Trials

2021-01-01

Shih-Tang Su , Vijay Subramanian , Grant Schoenebeck

We consider a Bayesian persuasion or information design problem where the sender tries to persuade the receiver to take a particular action via a sequence of signals. This we model … We consider a Bayesian persuasion or information design problem where the sender tries to persuade the receiver to take a particular action via a sequence of signals. This we model by considering multi-phase trials with different experiments conducted based on the outcomes of prior experiments. In contrast to most of the literature, we consider the problem with constraints on signals imposed on the sender. This we achieve by fixing some of the experiments in an exogenous manner; these are called determined experiments. This modeling helps us understand real-world situations where this occurs: e.g., multi-phase drug trials where the FDA determines some of the experiments, funding of a startup by a venture capital firm, start-up acquisition by big firms where late-stage assessments are determined by the potential acquirer, multi-round job interviews where the candidates signal initially by presenting their qualifications but the rest of the screening procedures are determined by the interviewer. The non-determined experiments (signals) in the multi-phase trial are to be chosen by the sender in order to persuade the receiver best. With a binary state of the world, we start by deriving the optimal signaling policy in the only non-trivial configuration of a two-phase trial with binary-outcome experiments. We then generalize to multi-phase trials with binary-outcome experiments where the determined experiments can be placed at any chosen node in the trial tree. Here we present a dynamic programming algorithm to derive the optimal signaling policy that uses the two-phase trial solution's structural insights. We also contrast the optimal signaling policy structure with classical Bayesian persuasion strategies to highlight the impact of the signaling constraints on the sender.

View PDF Chat

Measurement Integrity in Peer Prediction: A Peer Assessment Case Study

2021-01-01

Noah Burrell , Grant Schoenebeck

View PDF Chat

BONUS! Maximizing Surprise

2021-01-01

Zhihuan Huang , Yuqing Kong , Tracy Xiao Liu +2 more

Multi-round competitions often double or triple the points awarded in the final round, calling it a bonus, to maximize spectators' excitement. In a two-player competition with $n$ rounds, we aim … Multi-round competitions often double or triple the points awarded in the final round, calling it a bonus, to maximize spectators' excitement. In a two-player competition with $n$ rounds, we aim to derive the optimal bonus size to maximize the audience's overall expected surprise (as defined in [7]). We model the audience's prior belief over the two players' ability levels as a beta distribution. Using a novel analysis that clarifies and simplifies the computation, we find that the optimal bonus depends greatly upon the prior belief and obtain solutions of various forms for both the case of a finite number of rounds and the asymptotic case. In an interesting special case, we show that the optimal bonus approximately and asymptotically equals to the "expected lead", the number of points the weaker player will need to come back in expectation. Moreover, we observe that priors with a higher skewness lead to a higher optimal bonus size, and in the symmetric case, priors with a higher uncertainty also lead to a higher optimal bonus size. This matches our intuition since a highly asymmetric prior leads to a high "expected lead", and a highly uncertain symmetric prior often leads to a lopsided game, which again benefits from a larger bonus.

View PDF Chat

Relaxing Common Belief for Social Networks

2020-09-27

Noah Burrell , Grant Schoenebeck

We propose a relaxation of common belief called factional belief that is suitable for the analysis of strategic coordination on social networks. We show how this definition can be used … We propose a relaxation of common belief called factional belief that is suitable for the analysis of strategic coordination on social networks. We show how this definition can be used to analyze revolt games on general graphs, including by giving an efficient algorithm that characterizes a structural result about the possible equilibria of such games. This extends prior work on common knowledge and common belief, which has been too restrictive for use in understanding strategic coordination and cooperation in social network settings.

Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization

2020-04-03

Wei Chen , Binghui Peng , Grant Schoenebeck +1 more

View PDF Chat

Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization

2020-03-23

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

We study the $r$-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of … We study the $r$-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the $r$-complex contagion model, each uninfected vertex in the network becomes infected if it has at least $r$ infected neighbors. In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the well-studied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability $\omega(n^{-(1+1/r)})$, under certain mild assumptions, we prove that the optimal seeding strategy is to put all the seeds in a single community. This matches the intuition that in a nonsubmodular cascade model placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e.g., the independent cascade model and the linear threshold model) in which nearby seeds tend to erode each others' effects. Our key technique is a novel time-asynchronized coupling of four cascade processes. Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in $\omega(n^{-(1+1/r)})$ or in $o(n^{-2})$.

Limitations of Greed: Influence Maximization in Undirected Networks Re-visited

2020-02-26

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

Limitations of Greed: Influence Maximization in Undirected Networks Re-visited

2020-01-01

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach

2020-01-01

Grant Schoenebeck , Fang-Yi Yu

View PDF Chat

Timely Information from Prediction Markets

2020-01-01

Grant Schoenebeck , Chenkai Yu , Fang-Yi Yu

Prediction markets are powerful tools to elicit and aggregate beliefs from strategic agents. However, in current prediction markets, agents may exhaust the social welfare by competing to be the first … Prediction markets are powerful tools to elicit and aggregate beliefs from strategic agents. However, in current prediction markets, agents may exhaust the social welfare by competing to be the first to update the market. We initiate the study of the trade-off between how quickly information is aggregated by the market, and how much this information costs. We design markets to aggregate timely information from strategic agents to maximize social welfare. To this end, the market must incentivize agents to invest the correct amount of effort to acquire information: quickly enough to be useful, but not faster (and more expensively) than necessary. The market also must ensure that agents report their information truthfully and on time. We consider two settings: in the first, information is only valuable before a deadline; in the second, the value of information decreases as time passes. We use both theorems and simulations to demonstrate the mechanisms.

View PDF Chat

Relaxing Common Belief for Social Networks

2020-01-01

Noah Burrell , Grant Schoenebeck

View PDF Chat

Social learning with questions

2019-06-28

Shih-Tang Su , Vijay Subramanian , Grant Schoenebeck

View PDF Chat

Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization

2019-04-02

Grant Schoenebeck , Biaoshuai Tao

View PDF Chat

An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling

2019-01-25

Yuqing Kong , Grant Schoenebeck

View PDF Chat

Outsourcing Computation: The Minimal Refereed Mechanism

2019-01-01

Yuqing Kong , Chris Peikert , Grant Schoenebeck +1 more

View PDF Chat

Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization.

2019-01-01

Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

Social Learning with Questions.

2018-11-01

Grant Schoenebeck , Shih-Tang Su , Vijay Subramanian

This work studies sequential social learning (also known as Bayesian observational learning), and how private communication can enable agents to avoid herding to the wrong action/state. Starting from the seminal … This work studies sequential social learning (also known as Bayesian observational learning), and how private communication can enable agents to avoid herding to the wrong action/state. Starting from the seminal BHW (Bikhchandani, Hirshleifer, and Welch, 1992) model where asymptotic learning does not occur, we allow agents to ask private and finite questions to a bounded subset of their predecessors. While retaining the publicly observed history of the agents and their Bayes rationality from the BHW model, we further assume that both the ability to ask questions and the questions themselves are common knowledge. Then interpreting asking questions as partitioning information sets, we study whether asymptotic learning can be achieved with finite capacity questions. Restricting our attention to the network where every agent is only allowed to query her immediate predecessor, an explicit construction shows that a 1-bit question from each agent is enough to enable asymptotic learning.

Eliciting Expertise without Verification

2018-06-11

Yuqing Kong , Grant Schoenebeck

View PDF Chat

Characterizing Adversarial Subspaces Using Local Intrinsic Dimensionality

2018-01-01

Xingjun Ma , Bo Li , Yisen Wang +6 more

Eliciting Expertise without Verification

2018-01-01

Yuqing Kong , Grant Schoenebeck

A central question of crowd-sourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. A key challenge is that sophisticated agents … A central question of crowd-sourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. A key challenge is that sophisticated agents may strategically withhold effort or information when they believe their payoff will be based upon comparison with other agents whose reports will likely omit this information due to lack of effort or expertise. Our work defines a natural model for this setting based on the assumption that \emph{more sophisticated agents know the beliefs of less sophisticated agents}. We then provide a mechanism design framework for this setting. From this framework, we design several novel mechanisms, for both the single and multiple question settings, that (1) encourage agents to invest effort and provide their information honestly; (2) output a correct "hierarchy" of the information when agents are rational.

View PDF Chat

Water from Two Rocks: Maximizing the Mutual Information

2018-01-01

Yuqing Kong , Grant Schoenebeck

Social Learning with Questions

2018-01-01

Grant Schoenebeck , Shih-Tang Su , Vijay Subramanian

View PDF Chat

Don’t Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

2017-01-01

Rico Angell , Grant Schoenebeck

View PDF Chat

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

2017-01-01

Grant Schoenebeck , Biaoshuai Tao

View PDF Chat

Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

2016-09-21

Rico Angell , Grant Schoenebeck

Coauthor	Papers Together
Yuqing Kong	17
Biaoshuai Tao	15
Fang-Yi Yu	9
Aaron Roth	8
Yichi Zhang	6
Vijay Subramanian	6
Shengwei Xu	6
Shih-Tang Su	5
Golnaz Ghasemiesfeh	5
Roozbeh Ebrahimi	5
Katrina Ligett	5
Noah Burrell	4
Zhihuan Huang	4
Tracy Xiao Liu	4
Jie Gao	4
Michael P. Wellman	3
Lirong Xia	3
Md Sanzeed Anwar	3
Arnab Bhattacharyya	3
Rico Angell	3
Paul Resnick	3
Swastik Kopparty	3
David Zuckerman	3
Qishen Han	3
Arpita Ghosh	3
Madhu Sudan	3
Rafael Frongillo	3
Yuxuan Lu	3
Omer Tamuz	3
Paramveer S. Dhillon	3
Wei Chen	2
Thomas Holenstein	2
Constantinos Daskalakis	2
Paul Valiant	2
Travis Martin	2
Anupam Gupta	2
Gregory Valiant	2
Kunal Talwar	2
Weijie Su	2
Shan You	2
Jie Gao	2
Binghui Peng	2
Aditya Saraf	1
Yulin Yu	1
Sanjeev Arora	1
Tim Weninger	1
Darshan Chakrabarti	1
Chris Peikert	1
Sudanthi Wijewickrema	1
Shih-Tang Su	1

Crowdsourced judgement elicitation with endogenous proficiency

2013-05-13

Anirban Dasgupta , Arpita Ghosh

Crowdsourcing is now widely used to replace judgement or evaluation by an expert authority with an aggregate evaluation from a number of non-experts, in applications ranging from rating and categorizing … Crowdsourcing is now widely used to replace judgement or evaluation by an expert authority with an aggregate evaluation from a number of non-experts, in applications ranging from rating and categorizing online content all the way to evaluation of student assignments in massively open online courses (MOOCs) via peer grading. A key issue in these settings, where direct monitoring of both effort and accuracy is infeasible, is incentivizing agents in the 'crowd' to put in effort to make good evaluations, as well as to truthfully report their evaluations. We study the design of mechanisms for crowdsourced judgement elicitation when workers strategically choose both their reports and the effort they put into their evaluations. This leads to a new family of information elicitation problems with unobservable ground truth, where an agent's proficiency--- the probability with which she correctly evaluates the underlying ground truth--- is endogenously determined by her strategic choice of how much effort to put into the task.

View PDF Chat

Informed Truthfulness in Multi-Task Peer Prediction

2016-07-21

Victor Shnayder , Arpit Agarwal , Rafael Frongillo +1 more

The problem of peer prediction is to elicit information from agents in settings without any objective ground truth against which to score reports. Peer prediction mechanisms seek to exploit correlations … The problem of peer prediction is to elicit information from agents in settings without any objective ground truth against which to score reports. Peer prediction mechanisms seek to exploit correlations between signals to align incentives with truthful reports. A long-standing concern has been the possibility of uninformative equilibria. For binary signals, a multi-task mechanism achieves strong truthfulness, so that the truthful equilibrium strictly maximizes payoff. We characterize conditions on the signal distribution for which this mechanism remains strongly-truthful with non-binary signals, also providing a greatly simplified proof. We introduce the Correlated Agreement (CA) mechanism, which handles multiple signals and provides informed truthfulness: no strategy profile provides more payoff in equilibrium than truthful reporting, and the truthful equilibrium is strictly better than any uninformed strategy (where an agent avoids the effort of obtaining a signal). The CA mechanism is maximally strongly truthful, in that no mechanism in a broad class of mechanisms is strongly truthful on a larger family of signal distributions. We also give a detail-free version of the mechanism that removes any knowledge requirements on the part of the designer, using reports on many tasks to learn statistics while retaining epsilon-informed truthfulness.

View PDF Chat

Mechanisms for Making Crowds Truthful

2009-03-17

Radu Jurca , Boi Faltings

We consider schemes for obtaining truthful reports on a common but hidden signal from large groups of rational, self-interested agents. One example are online feedback mechanisms, where users provide observations … We consider schemes for obtaining truthful reports on a common but hidden signal from large groups of rational, self-interested agents. One example are online feedback mechanisms, where users provide observations about the quality of a product or service so that other users can have an accurate idea of what quality they can expect. However, (i) providing such feedback is costly, and (ii) there are many motivations for providing incorrect feedback. Both problems can be addressed by reward schemes which (i) cover the cost of obtaining and reporting feedback, and (ii) maximize the expected reward of a rational agent who reports truthfully. We address the design of such incentive-compatible rewards for feedback generated in environments with pure adverse selection. Here, the correlation between the true knowledge of an agent and her beliefs regarding the likelihoods of reports of other agents can be exploited to make honest reporting a Nash equilibrium. In this paper we extend existing methods for designing incentive-compatible rewards by also considering collusion. We analyze different scenarios, where, for example, some or all of the agents collude. For each scenario we investigate whether a collusion-resistant, incentive-compatible reward scheme exists, and use automated mechanism design to specify an algorithm for deriving an efficient reward mechanism.

View PDF Chat

Bootstrap percolation on a Bethe lattice

1979-01-14

J. Chalupa , P. L. Leath , Gary Reich

A new percolation problem is posed which can exhibit a first-order transition. In bootstrap percolation, sites on an empty lattice are first randomly occupied, and then all occupied sites with … A new percolation problem is posed which can exhibit a first-order transition. In bootstrap percolation, sites on an empty lattice are first randomly occupied, and then all occupied sites with less than a given number m of occupied neighbours are successively removed until a stable configuration is reached. On any lattice for sufficiently large m, the ensuing clusters can only be infinite. On a Bethe lattice for m>or=3, the fraction of the lattice occupied by infinite clusters discontinuously jumps from zero at the percolation threshold. From an analysis of stable and metastable ground states of the dilute Blume-Capel model (1966), it is concluded that effects like bootstrap percolation may occur in some real magnets.

Emergence of Scaling in Random Networks

1999-10-15

Albert‐László Barabási , Réka Albert

Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex … Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.

View PDF Chat

Eliciting Expertise without Verification

2018-06-11

Yuqing Kong , Grant Schoenebeck

View PDF Chat

The dynamics of viral marketing

2006-06-11

Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman

We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observe the propagation of recommendations … We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observe the propagation of recommendations and the cascade sizes, which we explain by a simple stochastic model. We then establish how the recommendation network grows over time and how effective it is from the viewpoint of the sender and receiver of the recommendations. While on average recommendations are not very effective at inducing purchases and do not spread very far, we present a model that successfully identifies product and pricing categories for which viral marketing seems to be very effective.

View PDF Chat

Bootstrap percolation on the random regular graph

2006-12-13

József Balogh , Boris Pittel

Abstract The k ‐parameter bootstrap percolation on a graph is a model of an interacting particle system, which can also be viewed as a variant of a cellular automaton growth … Abstract The k ‐parameter bootstrap percolation on a graph is a model of an interacting particle system, which can also be viewed as a variant of a cellular automaton growth process with threshold k ≥ 2. At the start, each of the graph vertices is active with probability p and inactive with probability 1 − p , independently of other vertices. Presence of active vertices triggers a bootstrap percolation process controlled by a recursive rule: an active vertex remains active forever, and a currently inactive vertex becomes active when at least k of its neighbors are active. The basic problem is to identify, for a given graph, p − and p + such that for p p + resp.) the probability that all vertices are eventually active is very close to 0 (1 resp.). The bootstrap percolation process is a deterministic process on the space of subsets of the vertex set, which is easy to describe but hard to analyze rigorously in general. We study the percolation on the random d ‐regular graph, d ≥ 3, via analysis of the process on the multigraph counterpart of the graph. Here, thanks to a “principle of deferred decisions,” the percolation dynamics is described by a surprisingly simple Markov chain. Its generic state is formed by the counts of currently active and nonactive vertices having various degrees of activation capabilities. We replace the chain by a deterministic dynamical system, and use its integrals to show—via exponential supermartingales—that the percolation process undergoes relatively small fluctuations around the deterministic trajectory. This allows us to show existence of the phase transition within an interval [ p − ( n ), p + ( n )], such that (1) p ± ( n ) → p * = 1 − min y ∈(0,1) y /ℙ(Bin( d − 1,1 − y ) < k ); (2) p + ( n ) − p − ( n ) is of order n −1/2 for k < d − 1, and n , (ε n ↓ 0, ε n log n → ∞ ), for k = d − 1. Note that p * is the same as the critical probability of the process on the corresponding infinite regular tree. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 30, 257–286, 2007

Bootstrap percolation on the random graph $G_{n,p}$

2012-10-01

Svante Janson , Tomasz Łuczak , Tatyana S. Turova +1 more

Bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At … Bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least $r\geq2$ active neighbors become active as well. We study the size $A^*$ of the final active set. The parameters of the model are, besides $r$ (fixed) and $n$ (tending to $\infty$), the size $a=a(n)$ of the initially active set and the probability $p=p(n)$ of the edges in the graph. We show that the model exhibits a sharp phase transition: depending on the parameters of the model, the final size of activation with a high probability is either $n-o(n)$ or it is $o(n)$. We provide a complete description of the phase diagram on the space of the parameters of the model. In particular, we find the phase transition and compute the asymptotics (in probability) for $A^*$; we also prove a central limit theorem for $A^*$ in some ranges. Furthermore, we provide the asymptotics for the number of steps until the process stops.

View PDF Chat

Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization

2019-04-02

Grant Schoenebeck , Biaoshuai Tao

View PDF Chat

Hierarchical structure and the prediction of missing links in networks

2008-04-30

Aaron Clauset , Cristopher Moore , M. E. J. Newman

View PDF Chat

Bootstrap Percolation and Diffusion in Random Graphs with Given Vertex Degrees

2010-02-08

Hamed Amini

We consider diffusion in random graphs with given vertex degrees. Our diffusion model can be viewed as a variant of a cellular automaton growth process: assume that each node can … We consider diffusion in random graphs with given vertex degrees. Our diffusion model can be viewed as a variant of a cellular automaton growth process: assume that each node can be in one of the two possible states, inactive or active. The parameters of the model are two given functions $\theta: {\Bbb N} \rightarrow {\Bbb N}$ and $\alpha:{\Bbb N} \rightarrow [0,1]$. At the beginning of the process, each node $v$ of degree $d_v$ becomes active with probability $\alpha(d_v)$ independently of the other vertices. Presence of the active vertices triggers a percolation process: if a node $v$ is active, it remains active forever. And if it is inactive, it will become active when at least $\theta(d_v)$ of its neighbors are active. In the case where $\alpha(d) =\alpha$ and $\theta(d) =\theta$, for each $d \in {\Bbb N}$, our diffusion model is equivalent to what is called bootstrap percolation. The main result of this paper is a theorem which enables us to find the final proportion of the active vertices in the asymptotic case, i.e., when $n \rightarrow \infty$. This is done via analysis of the process on the multigraph counterpart of the graph model.

View PDF Chat

Putting Peer Prediction Under the Micro(economic)scope and Making Truth-Telling Focal

2016-01-01

Yuqing Kong , Katrina Ligett , Grant Schoenebeck

View PDF Chat

Incentivizing Evaluation via Limited Access to Ground Truth: Peer-Prediction Makes Things Worse

2016-01-01

Alice L. L. Gao , James R. Wright , Kevin Leyton‐Brown

In many settings, an effective way of evaluating objects of interest is to collect evaluations from dispersed individuals and to aggregate these evaluations together. Some examples are categorizing online content … In many settings, an effective way of evaluating objects of interest is to collect evaluations from dispersed individuals and to aggregate these evaluations together. Some examples are categorizing online content and evaluating student assignments via peer grading. For this data science problem, one challenge is to motivate participants to conduct such evaluations carefully and to report them honestly, particularly when doing so is costly. Existing approaches, notably peer-prediction mechanisms, can incentivize truth telling in equilibrium. However, they also give rise to equilibria in which agents do not pay the costs required to evaluate accurately, and hence fail to elicit useful information. We show that this problem is unavoidable whenever agents are able to coordinate using low-cost signals about the items being evaluated (e.g., text labels or pictures). We then consider ways of circumventing this problem by comparing agents' reports to ground truth, which is available in practice when there exist trusted evaluators---such as teaching assistants in the peer grading scenario---who can perform a limited number of unbiased (but noisy) evaluations. Of course, when such ground truth is available, a simpler approach is also possible: rewarding each agent based on agreement with ground truth with some probability, and unconditionally rewarding the agent otherwise. Surprisingly, we show that the simpler mechanism achieves stronger incentive guarantees given less access to ground truth than a large set of peer-prediction mechanisms.

Don’t Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

2017-01-01

Rico Angell , Grant Schoenebeck

View PDF Chat

Information Contagion: An Empirical Study of the Spread of News on Digg and Twitter Social Networks

2010-05-16

Kristina Lerman , Rumi Ghosh

Social networks have emerged as a critical factor in information dissemination, search, marketing, expertise and influence discovery, and potentially an important tool for mobilizing people. Social media has made social … Social networks have emerged as a critical factor in information dissemination, search, marketing, expertise and influence discovery, and potentially an important tool for mobilizing people. Social media has made social networks ubiquitous, and also given researchers access to massive quantities of data for empirical analysis. These data sets offer a rich source of evidence for studying dynamics of individual and group behavior, the structure of networks and global patterns of the flow of information on them. However, in most previous studies, the structure of the underlying networks was not directly visible but had to be inferred from the flow of information from one individual to another. As a result, we do not yet understand dynamics of information spread on networks or how the structure of the network affects it. We address this gap by analyzing data from two popular social news sites. Specifically, we extract social networks of active users on Digg and Twitter, and track how interest in news stories spreads among them. We show that social networks play a crucial role in the spread of information on these sites, and that network structure affects dynamics of information flow.

View PDF Chat

What I Tell You Three Times Is True: Bootstrap Percolation in Small Worlds

2012-01-01

Hamed Amini , Nikolaos Fountoulakis

A Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling.

2016-05-03

Yuqing Kong , Grant Schoenebeck

Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity

2016-01-01

Yuqing Kong , Grant Schoenebeck

A General Class of Coefficients of Divergence of One Distribution from Another

1966-01-01

Syed Mustafa Ali , S. D. Silvey

Summary Let p1 and p2 be two probability measures on the same space and let φ be the generalized Radon-Nikodym derivative of p2 with respect to p1. If C is … Summary Let p1 and p2 be two probability measures on the same space and let φ be the generalized Radon-Nikodym derivative of p2 with respect to p1. If C is a continuous convex function of a real variable such that the p1-expectation (generalized as in Section 3) of C(φ) provides a reasonable coefficient of the p1-dispersion of φ, then this expectation has basic properties which it is natural to demand of a coefficient of divergence of p2 from p1. A general class of coefficients of divergence is generated in this way and it is shown that various available measures of divergence, distance, discriminatory information, etc., are members of this class.

Competitive contagion in networks

2012-05-19

Sanjeev Goyal , Michael Kearns

We develop a game-theoretic framework for the study of competition between firms who have budgets to "seed" the initial adoption of their products by consumers located in a social network. … We develop a game-theoretic framework for the study of competition between firms who have budgets to "seed" the initial adoption of their products by consumers located in a social network. The payoffs to the firms are the eventual number of adoptions of their product through a competitive stochastic diffusion process in the network. This framework yields a rich class of competitive strategies, which depend in subtle ways on the stochastic dynamics of adoption, the relative budgets of the players, and the underlying structure of the social network.

View PDF Chat

Information Contagion: an Empirical Study of the Spread of News on Digg and Twitter Social Networks

2010-03-13

Kristina Lerman , Rumi Ghosh

Information geometry of divergence functions

2010-03-01

Шун-ичи Амари , Andrzej Cichocki

Information geometry of divergence functions Measures of divergence between two points play a key role in many engineering problems. One such measure is a distance function, but there are many … Information geometry of divergence functions Measures of divergence between two points play a key role in many engineering problems. One such measure is a distance function, but there are many important measures which do not satisfy the properties of the distance. The Bregman divergence, Kullback-Leibler divergence and f -divergence are such measures. In the present article, we study the differential-geometrical structure of a manifold induced by a divergence function. It consists of a Riemannian metric, and a pair of dually coupled affine connections, which are studied in information geometry. The class of Bregman divergences are characterized by a dually flat structure, which is originated from the Legendre duality. A dually flat space admits a generalized Pythagorean theorem. The class of f -divergences, defined on a manifold of probability distributions, is characterized by information monotonicity, and the Kullback-Leibler divergence belongs to the intersection of both classes. The f -divergence always gives the α-geometry, which consists of the Fisher information metric and a dual pair of ±α-connections. The α-divergence is a special class of f -divergences. This is unique, sitting at the intersection of the f -divergence and Bregman divergence classes in a manifold of positive measures. The geometry derived from the Tsallis q -entropy and related divergences are also addressed.

View PDF Chat

The dynamics of viral marketing

2007-05-01

Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman

We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observe the propagation of recommendations … We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observe the propagation of recommendations and the cascade sizes, which we explain by a simple stochastic model. We analyze how user behavior varies within user communities defined by a recommendation network. Product purchases follow a ‘long tail’ where a significant share of purchases belongs to rarely sold items. We establish how the recommendation network grows over time and how effective it is from the viewpoint of the sender and receiver of the recommendations. While on average recommendations are not very effective at inducing purchases and do not spread very far, we present a model that successfully identifies communities, product, and pricing categories for which viral marketing seems to be very effective.

View PDF Chat

Equivalent Comparisons of Experiments

1953-06-01

David Blackwell

Sherman [8] and Stein [9] have shown that a method given by the author [1] for comparing two experiments is equivalent, for experiments with a finite number of outcomes, to … Sherman [8] and Stein [9] have shown that a method given by the author [1] for comparing two experiments is equivalent, for experiments with a finite number of outcomes, to the original method introduced by Bohnenblust, Shapley, and Sherman [4]. A new proof of this result is given, and the restriction to experiments with a finite number of outcomes is removed. A class of weaker comparisons--comparison in $k$-decision problems--is introduced, in three equivalent forms. For dichotomies, all methods are equivalent, and can be described in terms of errors of the first and second kinds.

View PDF Chat

Maximizing Social Influence in Nearly Optimal Time

2013-12-18

Christian Borgs , Michael Brautbar , Jennifer Chayes +1 more

Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of … Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of k initial seed nodes in a network so that the expected size of the resulting cascade is maximized, under the standard independent cascade model of network diffusion. Runtime is a primary consideration for this problem due to the massive size of the relevant input networks. We provide a fast algorithm for the influence maximization problem, obtaining the near-optimal approximation factor of (1 - 1/e - epsilon), for any epsilon > 0, in time O((m+n)k log(n) / epsilon^2). Our algorithm is runtime-optimal (up to a logarithmic factor) and substantially improves upon the previously best-known algorithms which run in time Omega(mnk POLY(1/epsilon)). Furthermore, our algorithm can be modified to allow early termination: if it is terminated after O(beta(m+n)k log(n)) steps for some beta < 1 (which can depend on n), then it returns a solution with approximation factor O(beta). Finally, we show that this runtime is optimal (up to logarithmic factors) for any beta and fixed seed size k.

View PDF Chat

Majority dynamics and aggregation of information in social networks

2013-06-10

Elchanan Mossel , Joe Neeman , Omer Tamuz

View PDF Chat

Sketch-based Influence Maximization and Computation

2014-11-03

Edith Cohen , Daniel Delling , Thomas Pajor +1 more

Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specified by a … Propagation of contagion through networks is a fundamental process. It is used to model the spread of information, influence, or a viral infection. Diffusion patterns can be specified by a probabilistic model, such as Independent Cascade (IC), or captured by a set of representative traces.

View PDF Chat

IRIE: Scalable and Robust Influence Maximization in Social Networks

2012-12-01

Kyomin Jung , Wooram Heo , Wei Chen

Influence maximization is the problem of selecting top k seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose … Influence maximization is the problem of selecting top k seed nodes in a social network to maximize their influence coverage under certain influence diffusion models. In this paper, we propose a novel algorithm IRIE that integrates the advantages of influence ranking (IR) and influence estimation (IE) methods for influence maximization in both the independent cascade (IC) model and its extension IC-N that incorporates negative opinion propagations. Through extensive experiments, we demonstrate that IRIE matches the influence coverage of other algorithms while scales much better than all other algorithms. Moreover IRIE is much more robust and stable than other algorithms both in running time and memory usage for various density of networks and cascade size. It runs up to two orders of magnitude faster than other state-of-the-art algorithms such as PMIA for large networks with tens of millions of nodes and edges, while using only a fraction of memory.

View PDF Chat

An Information Theoretic Framework For Designing Information Elicitation Mechanisms That Reward Truth-telling

2019-01-25

Yuqing Kong , Grant Schoenebeck

View PDF Chat

A Truth Serum for Large-Scale Evaluations

2015-07-25

Vijay Kamble , David Marn , Nihar B. Shah +2 more

A major challenge in obtaining large-scale evaluations, e.g., product or service reviews on online platforms, labeling images, grading in online courses, etc., is that of eliciting honest responses from agents … A major challenge in obtaining large-scale evaluations, e.g., product or service reviews on online platforms, labeling images, grading in online courses, etc., is that of eliciting honest responses from agents in the absence of verifiability. We propose a new reward mechanism with strong incentive properties applicable in a wide variety of such settings. This mechanism has a simple and intuitive output agreement structure: an agent gets a reward only if her response for an evaluation matches that of her peer. But instead of the reward being the same across different answers, it is inversely proportional to a popularity index of each answer. This index is a second order population statistic that captures how frequently two agents performing the same evaluation agree on the particular answer. Rare agreements thus earn a higher reward than agreements that are relatively more common. In the regime where there are a large number of evaluation tasks, we show that truthful behavior is a strict Bayes-Nash equilibrium of the game induced by the mechanism. Further, we show that the truthful equilibrium is approximately optimal in terms of expected payoffs to the agents across all symmetric equilibria, where the approximation error vanishes in the number of evaluation tasks. Moreover, under a mild condition on strategy space, we show that any symmetric equilibrium that gives a higher expected payoff than the truthful equilibrium must be close to being fully informative if the number of evaluations is large. These last two results are driven by a new notion of an agreement measure that is shown to be monotonic in information loss. This notion and its properties are of independent interest.

Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization

2017-01-01

Grant Schoenebeck , Biaoshuai Tao

View PDF Chat

Robust Influence Maximization

2016-08-08

Wei Chen , Tian Lin , Zihan Tan +2 more

In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding k seed … In this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding k seed nodes in a social network to maximize the influence spread. We propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.

View PDF Chat

Don't Be Greedy: Leveraging Community Structure to Find High Quality Seed Sets for Influence Maximization

2016-09-21

Rico Angell , Grant Schoenebeck

The asymptotic number of labeled graphs with given degree sequences

1978-05-01

Edward A. Bender , E. Rodney Canfield

Diameters in Preferential Attachment Models

2010-01-21

Sander Dommers , Remco van der Hofstad , Gerard Hooghiemstra

In this paper, we investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. The models studied here are such that edges … In this paper, we investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. The models studied here are such that edges are attached to older vertices proportional to the degree plus a constant, i.e., we consider affine PA-models. There is a substantial amount of literature proving that, quite generally, PA-graphs possess power-law degree sequences with a power-law exponent τ>2. We prove that the diameter of the PA-model is bounded above by a constant times log t, where t is the size of the graph. When the power-law exponent τ exceeds 3, then we prove that log t is the right order, by proving a lower bound of this order, both for the diameter as well as for the typical distance. This shows that, for τ>3, distances are of the order log t. For τ∈(2,3), we improve the upper bound to a constant times log log t, and prove a lower bound of the same order for the diameter. Unfortunately, this proof does not extend to typical distances. These results do show that the diameter is of order log log t. These bounds partially prove predictions by physicists that the typical distance in PA-graphs are similar to the ones in other scale-free random graphs, such as the configuration model and various inhomogeneous random graph models, where typical distances have been shown to be of order log log t when τ∈(2,3), and of order log t when τ>3.

View PDF Chat

On determinants of random symmetric matrices over Z_m

2010-01-01

Richard P. Brent , Brendan D. McKay

We determine the probability that a random n x n symmetric matrix over {1, 2, ... , m} has determinant divisible by m. We determine the probability that a random n x n symmetric matrix over {1, 2, ... , m} has determinant divisible by m.

Graphical Models for Game Theory

2013-01-01

Michael Kearns , Michael L. Littman , Satinder Singh

In this work, we introduce graphical modelsfor multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An n-player game is given by an undirected … In this work, we introduce graphical modelsfor multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An n-player game is given by an undirected graph on n nodes and a set of n local matrices. The interpretation is that the payoff to player i is determined entirely by the actions of player i and his neighbors in the graph, and thus the payoff matrix to player i is indexed only by these players. We thus view the global n-player game as being composed of interacting local games, each involving many fewer players. Each player's action may have global impact, but it occurs through the propagation of local influences.Our main technical result is an efficient algorithm for computing Nash equilibria when the underlying graph is a tree (or can be turned into a tree with few node mergings). The algorithm runs in time polynomial in the size of the representation (the graph and theassociated local game matrices), and comes in two related but distinct flavors. The first version involves an approximation step, and computes a representation of all approximate Nash equilibria (of which there may be an exponential number in general). The second version allows the exact computation of Nash equilibria at the expense of weakened complexity bounds. The algorithm requires only local message-passing between nodes (and thus can be implemented by the players themselves in a distributed manner). Despite an analogy to inference in Bayes nets that we develop, the analysis of our algorithm is more involved than that for the polytree algorithm in, owing partially to the fact that we must either compute, or select from, an exponential number of potential solutions. We discuss a number of extensions, such as the computation of equilibria with desirable global properties (e.g. maximizing global return), and directions for further research.

Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters

2009-01-01

Jure Leskovec , Kevin Lang , Anirban Dasgupta +1 more

A large body of work has been devoted to defining and identifying clusters or communities in social and information networks, i.e., in graphs in which the nodes represent underlying social … A large body of work has been devoted to defining and identifying clusters or communities in social and information networks, i.e., in graphs in which the nodes represent underlying social entities and the edges represent some sort of interaction between pairs of nodes. Most such research begins with the premise that a community or a cluster should be thought of as a set of nodes that has more and/or better connections between its members than to the remainder of the network. In this paper, we explore from a novel perspective several questions related to identifying meaningful communities in large social and information networks, and we come to several striking conclusions. Rather than defining a procedure to extract sets of nodes from a graph and then attempting to interpret these sets as "real" communities, we employ approximation algorithms for the graph-partitioning problem to characterize as a function of size the statistical and structural properties of partitions of graphs that could plausibly be interpreted as communities. In particular, we define the _network community profile plot_, which characterizes the "best" possible community—according to the conductance measure—over a wide range of size scales. We study over one hundred large real-world networks, ranging from traditional and online social networks, to technological and information networks and web graphs, and ranging in size from thousands up to tens of millions of nodes. Our results suggest a significantly more refined picture of community structure in large networks than has been appreciated previously. Our observations agree with previous work on small networks, but we show that large networks have a very different structure. In particular, we observe tight communities that are barely connected to the rest of the network at very small size scales (up to ≈ 100 nodes); and communities of size scale beyond ≈ 100 nodes gradually "blend into" the expander-like core of the network and thus become less "community-like," with a roughly inverse relationship between community size and optimal community quality. This observation agrees well with the so-called Dunbar number, which gives a limit to the size of a well-functioning community. However, this behavior is not explained, even at a qualitative level, by any of the commonly used network-generation models. Moreover, it is exactly the opposite of what one would expect based on intuition from expander graphs, low-dimensional or manifold-like graphs, and from small social networks that have served as test beds of community-detection algorithms. The relatively gradual increase of the network community profile plot as a function of increasing community size depends in a subtle manner on the way in which local clustering information is propagated from smaller to larger size scales in the network. We have found that a generative graph model, in which new edges are added via an iterative "forest fire" burning process, is able to produce graphs exhibiting a network community profile plot similar to what we observe in our network data sets.

View PDF Chat

Analyzing and characterizing small-world graphs

2005-01-23

Văn Đức Nguyễn , Chip Martel

We study variants of Kleinberg's small-world model where we start with a k-dimensional grid and add a random directed edge from each node. The probability u's random edge is to … We study variants of Kleinberg's small-world model where we start with a k-dimensional grid and add a random directed edge from each node. The probability u's random edge is to v is proportional to d(u,v)-r where d(u,v) is the lattice distance and r is a parameter of the model.For a k-dimensional grid, we show that these graphs have poly-log expected diameter when k 2k. This shows an interesting phase-transition between small-world and large-world graphs.We also present a general framework to construct classes of small-world graphs with Θ(log n) expected diameter, which includes several existing settings such as Kleinberg's grid-based and tree-based settings [15].We also generalize the idea of 'adding links with probability α the inverse distance' to design small-world graphs. We use semi-metric and metric functions to abstract distance to create a class of random graphs where almost all pairs of nodes are connected by a path of length O (log n), and using only local information we can find paths of poly-log length.

Mafia: A theoretical study of players and coalitions in a partial information environment

2008-05-26

Mark Braverman , Omid Etesami , Elchanan Mossel

In this paper, we study a game called “Mafia,” in which different players have different types of information, communication and functionality. The players communicate and function in a way that … In this paper, we study a game called “Mafia,” in which different players have different types of information, communication and functionality. The players communicate and function in a way that resembles some real-life situations. We consider two types of operations. First, there are operations that follow an open democratic discussion. Second, some subgroups of players who may have different interests make decisions based on their own group interest. A key ingredient here is that the identity of each subgroup is known only to the members of that group. In this paper, we are interested in the best strategies for the different groups in such scenarios and in evaluating their relative power. The main focus of the paper is the question: How large and strong should a subgroup be in order to dominate the game? The concrete model studied here is based on the popular game “Mafia.” In this game, there are three groups of players: Mafia, detectives and ordinary citizens. Initially, each player is given only his/her own identity, except the mafia, who are given the identities of all mafia members. At each “open” round, a vote is made to determine which player to eliminate. Additionally, there are collective decisions made by the mafia where they decide to eliminate a citizen. Finally, each detective accumulates data on the mafia/citizen status of players. The citizens win if they eliminate all mafia members. Otherwise, the mafia wins. We first find a randomized strategy that is optimal in the absence of detectives. This leads to a stochastic asymptotic analysis where it is shown that the two groups have comparable probabilities of winning exactly when the total population size is R and the mafia size is of order $\sqrt{R}$. We then show that even a single detective changes the qualitative behavior of the game dramatically. Here, the mafia and citizens have comparable winning probabilities only for a mafia size linear in R. Finally, we provide a summary of simulations complementing the theoretical results obtained in the paper.

View PDF Chat

How to Schedule the Marketing of Products with Negative Externalities

2013-01-01

Zhigang Cao , Xujin Chen , Changjun Wang

View PDF Chat

On Divergences and Informations in Statistics and Information Theory

2006-09-29

Friedrich Liese , Igor Vajda

The paper deals with the f-divergences of Csiszar generalizing the discrimination information of Kullback, the total variation distance, the Hellinger divergence, and the Pearson divergence. All basic properties of f-divergences … The paper deals with the f-divergences of Csiszar generalizing the discrimination information of Kullback, the total variation distance, the Hellinger divergence, and the Pearson divergence. All basic properties of f-divergences including relations to the decision errors are proved in a new manner replacing the classical Jensen inequality by a new generalized Taylor expansion of convex functions. Some new properties are proved too, e.g., relations to the statistical sufficiency and deficiency. The generalized Taylor expansion also shows very easily that all f-divergences are average statistical informations (differences between prior and posterior Bayes errors) mutually differing only in the weights imposed on various prior distributions. The statistical information introduced by De Groot and the classical information of Shannon are shown to be extremal cases corresponding to alpha=0 and alpha=1 in the class of the so-called Arimoto alpha-informations introduced in this paper for 0<alpha<1 by means of the Arimoto alpha-entropies. Some new examples of f-divergences are introduced as well, namely, the Shannon divergences and the Arimoto alpha-divergences leading for alphauarr1 to the Shannon divergences. Square roots of all these divergences are shown to be metrics satisfying the triangle inequality. The last section introduces statistical tests and estimators based on the minimal f-divergence with the empirical distribution achieved in the families of hypothetic distributions. For the Kullback divergence this leads to the classical likelihood ratio test and estimator

AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM

2008-02-01

Ben Green , Terence Tao

Abstract There has been much recent progress in the study of arithmetic progressions in various sets, such as dense subsets of the integers or of the primes. One key tool … Abstract There has been much recent progress in the study of arithmetic progressions in various sets, such as dense subsets of the integers or of the primes. One key tool in these developments has been the sequence of Gowers uniformity norms $U^d(G)$, $d=1,2,3,\dots$, on a finite additive group $G$; in particular, to detect arithmetic progressions of length $k$ in $G$ it is important to know under what circumstances the $U^{k-1}(G)$ norm can be large. The $U^1(G)$ norm is trivial, and the $U^2(G)$ norm can be easily described in terms of the Fourier transform. In this paper we systematically study the $U^3(G)$ norm, defined for any function $f:G\to\mathbb{C}$ on a finite additive group $G$ by the formula \begin{multline*} \qquad\|f\|_{U^3(G)}:=|G|^{-4}\sum_{x,a,b,c\in G}(f(x)\overline{f(x+a)f(x+b)f(x+c)}f(x+a+b) \\ \times f(x+b+c)f(x+c+a)\overline{f(x+a+b+c)})^{1/8}.\qquad \end{multline*} We give an inverse theorem for the $U^3(G)$ norm on an arbitrary group $G$. In the finite-field case $G=\mathbb{F}_5^n$ we show that a bounded function $f:G\to\mathbb{C}$ has large $U^3(G)$ norm if and only if it has a large inner product with a function $e(\phi)$, where $e(x):=\mathrm{e}^{2\pi\ri x}$ and $\phi:\mathbb{F}_5^n\to\mathbb{R}/\mathbb{Z}$ is a quadratic phase function. In a general $G$ the statement is more complicated: the phase $\phi$ is quadratic only locally on a Bohr neighbourhood in $G$. As an application we extend Gowers's proof of Szemerédi's theorem for progressions of length four to arbitrary abelian $G$. More precisely, writing $r_4(G)$ for the size of the largest $A\subseteq G$ which does not contain a progression of length four, we prove that $$ r_4(G)\ll|G|(\log\log|G|)^{-c}, $$ where $c$ is an absolute constant. We also discuss links between our ideas and recent results of Host, Kra and Ziegler in ergodic theory. In future papers we will apply variants of our inverse theorems to obtain an asymptotic for the number of quadruples $p_1\ltp_2\ltp_3\ltp_4\leq N$ of primes in arithmetic progression, and to obtain significantly stronger bounds for $r_4(G)$.

View PDF Chat

The Sum of D Small-Bias Generators Fools Polynomials of Degree D

2009-06-01

Emanuele Viola

View PDF Chat

Finding community structure in very large networks

2004-12-06

Aaron Clauset , M. E. J. Newman , Cristopher Moore

The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very … The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with $n$ vertices and $m$ edges is $O(md\phantom{\rule{0.2em}{0ex}}\mathrm{log}\phantom{\rule{0.2em}{0ex}}n)$ where $d$ is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with $m\ensuremath{\sim}n$ and $d\ensuremath{\sim}\mathrm{log}\phantom{\rule{0.2em}{0ex}}n$, in which case our algorithm runs in essentially linear time, $O(n\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}^{2}\phantom{\rule{0.2em}{0ex}}n)$. As an example of the application of this algorithm we use it to analyze a network of items for sale on the web site of a large on-line retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and $2\ifmmode\times\else\texttimes\fi{}{10}^{6}$ edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

Mathematical results on scale‐free random graphs

2002-11-08

Béla Bollobás , Oliver Riordan

Introduction Classical models of random graphs Results for classical random graphs The Watts-Strogatz ‘small-world’ model Scale-free models The Barabási-Albert model The LCD model and Gm(n) The Buckley-Osthus model The copying … Introduction Classical models of random graphs Results for classical random graphs The Watts-Strogatz ‘small-world’ model Scale-free models The Barabási-Albert model The LCD model and Gm(n) The Buckley-Osthus model The copying model The Cooper-Frieze model Directed scale-free graphs Clustering coefficient and small subgraphs Pairings on [0, 1] and the diameter of the LCD model Robustness and vulnerability The case [0, 1]: plane-oriented recursive trees Conclusion References

View PDF Chat

Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization

2010-01-01

Daniel Golovin , Andreas Krause

Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this paper, we introduce the … Solving stochastic optimization problems under partial observability, where one needs to adaptively make decisions with uncertain outcomes, is a fundamental but notoriously difficult challenge. In this paper, we introduce the concept of adaptive submodularity, generalizing submodular set functions to adaptive policies. We prove that if a problem satisfies this property, a simple adaptive greedy algorithm is guaranteed to be competitive with the optimal policy. In addition to providing performance guarantees for both stochastic maximization and coverage, adaptive submodularity can be exploited to drastically speed up the greedy algorithm by using lazy evaluations. We illustrate the usefulness of the concept by giving several examples of adaptive submodular objectives arising in diverse applications including sensor placement, viral marketing and active learning. Proving adaptive submodularity for these problems allows us to recover existing results in these applications as special cases, improve approximation guarantees and handle natural generalizations.

Competition and multiscaling in evolving networks

2001-05-01

Ginestra Bianconi , Albert‐László Barabási

The rate at which nodes in a network increase their connectivity depends on their fitness to compete for links. For example, in social networks some individuals acquire more social links … The rate at which nodes in a network increase their connectivity depends on their fitness to compete for links. For example, in social networks some individuals acquire more social links than others, or on the www some webpages attract considerably more links than others. We find that this competition for links translates into multiscaling, i.e. a fitness-dependent dynamic exponent, allowing fitter nodes to overcome the more connected but less fit ones. Uncovering this fitter-gets-richer phenomenon can help us understand in quantitative terms the evolution of many competitive systems in nature and society.

View PDF Chat

Inverse conjecture for the gowers norm is false

2008-05-17

Shachar Lovett , Roy Meshulam , Alex Samorodnitsky

Let p be a fixed prime number and N be a large integer. The "Inverse Conjecture for the Gowers Norm" states that if the "d-th Gowers norm" of a function … Let p be a fixed prime number and N be a large integer. The "Inverse Conjecture for the Gowers Norm" states that if the "d-th Gowers norm" of a function f:FNp to Fp is non-negligible, that is larger than a constant independent of N, then f has a non-trivial correlation with a degree d-1 polynomial. The conjecture is known to hold for d=2,3 and for any prime p. In this paper we show the conjecture to be false for p=2 and for d=4, by presenting an explicit function whose 4-th Gowers norm is non-negligible, but whose correlation with any polynomial of degree 3 is exponentially small. Essentially the same result, with different bounds for correlation, was independently obtained by Green and Tao. Their analysis uses a modification of a Ramsey-type argument of Alon and Beigel to show inapproximability of certain functions by low-degree polynomials. We observe that a combination of our results with the argument of Alon and Beigel implies the inverse conjecture to be false for any prime p, for d = p2.

View PDF Chat