William Guo

Week 0

Prior to the program starting, I did some background reading on asymptotic truth learning in social networks. Most notably, the work by Lu et al. from a previous iteration of this REU noted that ATL can be achieved so long as there exists an agent adjacent to \omega(1) independent neighbors (or technically any agent obtaining a high quality signal) that can then propagate the signal to the rest of the network. Bahar et al. analyzes a uniformly random decision ordering, under which a "celebrity graph" (bipartite graph with vastly uneven groups) can obtain ATL. In essence, the celebrities act as opinion leaders which will both obtain a high quality signal and propagate it to the rest of the network. Arieli et al. extended this by noting any graph in which each vertex has nearly-independent neighbors, known as the local learning requirement, can achieve ATl under a uniformly random decision ordering. I also briefly read up on the repeated learning settings, notably Mossel et al.

[citations to be added later]

Week 1

Entering this week, I was particularly interested in adversarial robustness of different topologies and non-Bayesian decision algorithms (weighted majority voting). I met with Prof. Jie Gao and Edward Xiong in-person for the first time, in which we discussed potential directions to take the project. I was convinced that finding weights for the weighted majority voting algorithm is equivalent to computing the CDF of a generalized Bernoulli distribution, which may be difficult to do efficiently. We then discussed pivoting to an entirely different setting, the naming game. As of writing this, I think we can push the current topic at least a little further, so I have started focused my efforts on robustness by looking at the effects of adversaries in the repeated learning setting.

There are different ways "robustness" can be defined, as seen in Bohren 2014 and Frick et al 2020, though the most similar to our setting that I read this week is perhaps Mueller-Frank 2018 in which at each iteration, an adversary can make an \epsilon-adjustment to the belief of a single agent (i.e. if the agent would have broadcasted opinion a, the adversary can change it to value in [a \pm \epsilon]). Interestingly, for any \epsilon > 0, such an adversary influencing an arbitrary agent can eventually sway a network using a DeGroot learning system to converge to any arbitrary belief, so DeGroot learning is not robust. This suggests repeated learning is surprisingly vulnerable to adversaries, though I'd believe that the adversary's power is significantly diminished in the sequential learning setting. Next week, I'll look into the effects of the graph topology on the robustness of Bayesian learners.

[more citations: Mossel et al, naming game, non-Bayesian voting algs]

Week 2

This week, I began working on sufficient conditions for adversarial robustness in the sequential learning setting. Since there wasn't much literature on this particular direction, I started with simple graphs permitting ATL under random orderings. For the celebrity graph, I noticed that in the presence of adversaries, it would be possible for the celebrities disagree with each other, which is typically impossible under a normal Bayesian setting and would confuse any Bayesian observer unaware of the presence of adversaries. Thus, I continued with the assumption that Bayesian agents are aware of the presence of adversaries, and thus can adjust their beliefs accordingly. With this in mind, and changing from picking k adversarial agents to all agents becoming adversarial independently w.p. k/n to simplify the analysis, it turns out that a variation of the improvement principle still holds in the presence of independent agents. In particular, as long as the distance of any vertex to an opinion leader is small (~o(n/k)), it still achieves a high learning rate. Moving forward, I hope to classify the diameter of random order graphs, or analyze the distance of arbitrary vertices to celebrities more specifically.

Interestingly, this implies there exist instances where agents act differently simply because of the presence of adversaries. For example, given a long chain of agents with a celebrity at one end, for a sufficiently long chain, the members at the end will assume the path to the celebrity is occluded by \geq 1 adversary and end up following their own private signal. In other words, agents near the end of the chain will follow their own independent signal instead of following the celebrity, which may actually induce ATL while the graph without adversaries would not.

In a similar vein, Edward has been working on finding graphs for which the exact value of q actually changes whether ATL is achieved or not. We found an interesting type of network where for high values of q, a large group of commoners can be dissuaded from revealing their private signals and all following a marginally stronger signal, while for low values of q, all commoners can give private signals that can be aggregated into a strong signal. A similar configuration gives a graph where for low values of q, the commoners aren't independent whereas they are for higher values of q. We hope to look into topologies/ordering assumptions that allow Bayesian commoners to be independent in weird edge cases as such.

Week 3

This week, I made a nice finding for adversarial random order networks: given a graph G with learning rate L(G) = 1 - \epsilon, the error rate in the presence of \sim k adversaries (i.e. adversaries chosen w.p. k/n) is O(\sqrt{k\epsilon}). The key combinatorial finding uses that for a random vertex ordering, the shortest path from any s to some reachable t is O(\sqrt{n}) whp. Then, so long as each vertex has in its subnetwork (set of vertices that can reach it) an ancestor with high learning rate, we only incur a (1 - k/\sqrt{n}) factor which is acceptable for k << \sqrt{n}. Indeed, since the small number of agents obtaining low learning rates are unaffected by the adversaries whp for sufficiently small k, the first few high learning rate agents are almost guaranteed to be unaffected by the adversaries, and can propagate their signal to the rest of the network.

This week, Edward and I also began chipping away at more properties of Bayesian learning. We both began working on the effect of removing/adding edges to a network, which unlike removing vertices requires a firm grasp on how Bayesian agents can improve the strength of a signal. This has proven to be quite tricky for a number of reasons, and we haven't been able to formalize much of our shared intuition. One thought I had was that in order to obtain a higher quality signal, an agent would need highly independent neighbors. However, removing an edge can actually reduce independence as follows: if two agents share a common ancestor with a learning rate similar to that of the ancestor, removing edges can weaken the signal of each agent, causing them to rely more on the ancestor's signal & increasing the probability of dependence. But interestingly, removing edges doesn't seem to harm more than 1 neighbor's dependence, which may help us bound the effect of removing random edges on any agent attempting to learn from its independent neighbors.

Independently, our group also began conjecturing properties of networks learning under random order. One interesting thought is whether low degree vertices can be removed; that is, if G learns under random order, then perhaps the k-core of G also learns under random order, k = \omega(1). Like Bayesian learning, it's been difficult to formalize our intuition, but I hope to find some more properties of random order ATL graphs in addition to shortest path lengths.

Week 4

This week, I continued characterizing graphs achieving ATL under random orderings. One would expect that agents with constant learning rates would have small degree, while agents with high learning rates would have large degree with many neighbors sharing similarly high learning rates. Indeed, agents with constant learning rate can only have constant many neighbors with learning rate \geq 1 - o(1), and generally an agent with learning rate 1 - \epsilon has at most O(\epsilon) edges to neighbors with learning rate \geq 1 - \epsilon / O(1). This directly gives us an upper bound on the connectivity of a graph achieving ATL, namely the number of edges/vertices needed to isolate all constant learning rate agents.

Regarding robustness against edge/vertex removal, Edward found a nice property that the learning rate of an agent is monotonic in its index. Using this property, one can show that k modifications (added/removed vertices or edges, potentially chosen strategically, and randomly chosen adversaries) to a graph G learning under random order with learning rate L(G) = 1 - \epsilon will still obtain learning rate at least 1 - 2k\epsilon. This is quite strong, directly improving upon our work from Weeks 2-3. The argument, though nuanced, is simple to intuit as an inherent strength of the random ordering: the first ~n/k agents in a network are w.h.p unaffected by perturbations, and by monotonicity any agent after the first n/k performs as least as well as if it were put early on in the ordering. Though the number of modifications k = o(1/\epsilon) isn't strong enough in combination with the above results, this was a critical insight in addressing the k-core conjecture from last week.

Aside, we still don't know of many graph families obtaining ATL under random orderings apart from the celebrity graphs & "egalitarian" expander graphs, so I showed that Erdos-Renyi random graphs with p \in [\omega(1/n), O(\log n)] should also work, which may be helpful for analyzing perturbations to networks learning under random orders.

Week 5

At the start of the week, I found a simple graph disproving the k-core conjecture, comprising of a K_n complete network with a small number of special vertices, each having \omega(1) leaves feeding independent signals to them. This graph family is different from the celebrity/egalitarian graphs, and shows that a graph can rely on a small number of vertices with constant degree to obtain ATL under random orderings.

We found it strange that such a small modification to the complete graph would allow it to obtain ATL, so we spent the second half of the week looking into the effect of adding vertices/edges to a graph. In particular, for any network G, what is the fewest number of edges that need to be added for the network to achieve ATL under random orderings? For general graphs, we were able to show that for any function f(n) = \omega(n), adding O(f(n)) edges (potentially with some vertices as well) would suffice. This bound is tight for graphs with many vertices with bounded degree, such as sparse graphs. For very dense graphs with arbitrarily small dominating sets, we have found that \omega(1) edges suffice. Moving forward, we hope to get better lower bounds for the number of edges needed to be added, as well as better upper bounds for specific graph families.

Week 6

Our goal this week was to find an algorithmic approach to adding a small number of edges to an arbitrary network to obtain ATL under random orderings. Our approach was to find strategic vertices in the network to boost, a topic related to the influence maximization framework by Kempe et al. 2003. For a fixed ordering, finding which agents to boost reduces to the set cover problem, as we seek to find a set of vertices containing all but o(n) vertices as predecessors. This is nice, since the set cover problem is O(\log(n))-approximable. However, it's unclear how this approach can generalize to the random ordering setting, as an agent covering most of the network in one ordering is all but guaranteed to cover most of the network in another ordering. We postulated that picking agents to boost proportional to their probability of being picked given a random ordering would be sufficient, but it isn't immediately obvious why this the case.

I spent some time playing around with simple heuristics for picking vertices to boost. One can note that for any graph G, each vertex only reaches vertices at most \Delta distance from it, where \Delta = \max_{v \in G} \deg(v). Furthermore, for a non-learning agent v to learn in the modified graph, it needs \omega(1) distinct boosted agents in its vicinity (as otherwise, v would have a constant probability of arriving before any of the boosted vertices, which would be of no help in v's decision making). While this gives a lower bound on the number of boosted vertices needed, there exist simple graphs where boosting \omega(1) vertices in each agent's local neighborhood isn't sufficient. There's also something that can be said about how the number of agents being boosted relates to the network's connectivity, though it's unclear to me whether this can be used to efficiently determine pick vertices to boost.

All in all, this week was a struggle, moreso than any other week thus far. It may very well be that the problem of finding edges to add to a graph to obtain random order ATL is provably hard. At the very least, solving this problem will require a better understanding of the necessary/sufficient properties of random order ATL graphs, which I hope to spend the next week looking into.

Week 7

We showed that the (slightly modified) greedy set cover approach serves as a O(\log^{1 + \epsilon} n) approximation algorithm for adding/deleting a minimal number of edges/vertices to a network G to ensure it can obtain random order ATL. The key insight was that boosting vertices is at least as effective as adding/deleting/moving edges already in G, and only loses an f(n) multiplicative factor for any f(n) = \omega(1). Unfortunately, this algorithm still requires a black box helper to determine whether a vertex is a learner or not; without knowing which vertices are/aren't learners, the algorithm could perform arbitrarily poorly.

Since the beginning, we've postulated that determining whether a vertex/network learns or not is a hard problem. This week, we acquired some tools to show this rigorously. Notably, the counterexample to the k-core conjecture from a couple weeks back suggests that any graph obtaining learning under strategic orderings can be used to boost a K_n graph to obtain ATL under random orderings (i.e. a graph learning under strategic orderings of size \log \log n has a \geq 1 / poly(n) probability of obtaining ATL under random orderings, and sufficiently many of these can be used to boost the K_n). Using this construction, I've tried to reduce from 3-SAT/independent set to show that determining whether a network learns under random orderings or not is hard, and will continue to work on this over the weekend before presentations next week.

Week 8

Proving hardness results has been pretty difficult. We did prove that a graph needs an independent set of size \omega(1) to obtain ATL under either strategic or random orderings with any tiebreaker rule. At first, we thought this would help us reduce from the independent set problem. However, we can't really append arbitrary graphs as a gadget for the K_n graph as suggested last week. The strategic ordering approach doesn't work since the social network would be doubly exponential in the size of the original instance. But more fundamentally, even if the graph has a large independent set, it doesn't necessarily yield \omega(1) independent signals (e.x. K_{n/2, n/2} has an independent set of size n/2, but a herd begins after the first 3 agents with constant probability). Next week (which is the final week of the program), I'd like to make a final push regarding hardness/relevant characterizations of graphs learning under random orderings, ideally before we begin our final writeup.

This week was quite special in many ways. I celebrated my 21st birthday on the day of the final presentations, and we also said sentimental goodbyes to some of the participants leaving early to visit Prague.

Resources

6/3/25 Intro Presentation