# Grounding Language about Belief in a Bayesian Theory-of-Mind

Lance Ying∗12, Tan Zhi-Xuan∗1, Lionel Wong1, Vikash Mansinghka1, Joshua
Tenenbaum1
1Massachusetts Institute of Technology, Cambridge, MA, USA
2Harvard University, Cambridge, MA, USA

###### Abstract

Despite the fact that beliefs are mental states that cannot be directly
observed, humans talk about each others’ beliefs on a regular basis, often
using rich compositional language to describe what others think and know. What
explains this capacity to interpret the hidden epistemic content of other
minds? In this paper, we take a step towards an answer by grounding the
semantics of belief statements in a Bayesian theory-of-mind: By modeling how
humans jointly infer _coherent_ sets of goals, beliefs, and plans that explain
an agent’s actions, then evaluating statements about the agent’s beliefs
against these inferences via epistemic logic, our framework provides a
conceptual role semantics for belief, explaining the gradedness and
compositionality of human belief attributions, as well as their intimate
connection with goals and plans. We evaluate this framework by studying how
humans attribute goals and beliefs while watching an agent solve a doors-and-
keys gridworld puzzle that requires instrumental reasoning about hidden
objects. In contrast to pure logical deduction, non-mentalizing baselines, and
mentalizing that ignores the role of instrumental plans, our model provides a
much better fit to human goal and belief attributions, demonstrating the
importance of theory-of-mind for a semantics of belief.

Keywords: theory-of-mind, belief modeling, social cognition, epistemic
language, semantics

††footnotetext: ∗Equal Contribution

## Introduction

Language about belief is pervasive in social life. Whether one is telling a
friend about a mutual friend’s aspirations (_”She seems to think she’ll get
the role she’s applying for…”_), speculating about the insider knowledge
behind an investment decision (_”Meta probably thinks this technology is going
to be a big deal…”_), or listening to news commentators explain the actions of
governments (_”The UK believes that this policy will improve…”_), language
provides an incredibly rich medium for communicating about our mental models
of the world. Remarkably, we often talk about belief despite not knowing what
other people truly think, instead inferring beliefs from what they say or do.
Belief, after all, is a guide to rational action, and there are many things a
person would or would not do if they believed some fact to be true.

How do people understand language about belief, in light of this intimate
connection? Put another way, what do people take as the _meaning_ of belief
statements, given the tight links between language, thought, and action? While
philosophers and linguists have long studied the semantics of belief sentences
(?, ?, ?, ?, ?), these inquiries have focused on the relationship between a
belief sentence and the proposition it embeds, not how people use and
interpret such sentences in everyday contexts. On the other hand,
computational cognitive scientists have developed numerous models that explain
how people attribute beliefs and goals to other agents (?, ?, ?, ?, ?).
Building upon the work of ? (?), these models formulate mental state
attributions as the product of a Bayesian theory-of-mind (BToM): Since beliefs
and goals play a _functional_ role in guiding plans and actions (?, ?), it is
possible to _interpret_ an agent’s actions as driven by particular goals and
beliefs through a process of Bayesian inference. However, prior work in this
paradigm has not studied the rich compositional nature of belief sentences, or
how humans might interpret them.

Figure 1: Overview of our proposed model. (a) Given a series of actions
$a_{1:T}$, we simulate possible mental states (combinations of the agent’s
goals, beliefs, and plans), assigning a posterior probability $p_{i}$ to each
hypothesis via Bayesian inverse planning. (b) We translate belief statements
$\sigma_{i}$ from English into first-order epistemic logic with a large
language model (LLM). (c) Each logical formula $\psi_{i}$ can then be
evaluated against the inferred mental states to produce a probability rating
$P(\psi_{i}|a_{1:T})$.

In this paper, we ground _natural language statements_ of belief in the
conceptual role semantics (?, ?) afforded by a Bayesian theory-of-mind. By
representing statements about other agent’s beliefs in first-order epistemic
logic (?, ?), then evaluating the likelihood of such statements in a
probabilistic model of an agent’s beliefs, goals, and actions, we are able to
explain not just the graded nature of what humans think other agents believe,
but also the structured, compositional nature of these belief statements, and
how these belief statements are sensitive to our inferences about the goals
and plans of others. To implement this framework, we combine the strengths of
machine learning methods with the coherence and precision of Bayesian and
logical reasoning (?, ?, ?), using a large language model (LLM) to translate
natural language statements into logical form (?, ?), then interpreting these
statements with respect to the inferences produced by a probabilistic
programming architecture for Bayesian inverse planning (?, ?).

To evaluate this framework, we design an experiment where human participants
are shown animations of a player navigating a gridworld puzzle game (see
Figure 1). In these puzzles, the player’s goal is to collect one of the
valuable gems. These gems are sometimes locked behind doors, so the player may
have to collect keys located inside opaque boxes in order to reach their
desired gem. For simplicity, we assume that the player _knows_ where the keys
are located. However, participants observing the scenario do not — as such,
they have _infer_ the player’s goals and beliefs from the actions they
observe. We elicit these inferences by having participants select which
goal(s) they think the player is pursuing, and by rating their confidence in a
set of natural language statements about the player’s beliefs. By comparing
our model’s outputs to human ratings, we evaluate how well it explains
people’s interpretations of language about belief.

## Computational Model

To explain how human observers attribute goals and beliefs to other agents, we
model them as performing approximately Bayesian inference over a generative
model of an agent’s goals, beliefs, and actions in an environment:

Goal Prior: $\displaystyle\quad g\sim P(g)$ (1) State Prior:
$\displaystyle\quad s_{0}\sim P(s_{0})$ (2) Belief Update: $\displaystyle\quad
b_{t}\sim P(b_{t}|s_{t})$ (3) Action Selection: $\displaystyle\quad a_{t}\sim
P(a_{t}|b_{t-1},g)$ (4) State Transition: $\displaystyle\quad s_{t}\sim
P(s_{t}|s_{t-1},a_{t})$ (5)

where $g$ is the agent’s goal, and at each timestep $t$, $s_{t}$ is the
environment’s state, $b_{t}$ is the agent’s belief about the environment, and
$a_{t}$ is the agent’s action. Notably in our setting, we model the agent as
having both _complete knowledge_ and _veridical perception_ of the
environment, such that their belief at each step $t$ is always equivalent to
the environment state $b_{t}\equiv s_{t}$. Nonetheless, an observer will still
have uncertainty over what the agent believes, since they have uncertainty
over the initial state $s_{0}$.

### Representing Environment and Belief States

For us to ground natural language statements about an agent’s belief states
$b_{t}$, we require an expressive representation of such beliefs, as well as
the environment states $s_{t}$ they corresponds to. As such, we represent both
using the Planning Domain Definition Language (PDDL), a first-order language
for model-based planning and reasoning (?, ?). In a PDDL domain, a set of
predicates $\mathcal{P}$ are used to describe a set of objects $\mathcal{O}$,
each of which has a type $\tau\in\mathcal{T}$. For example, to represent the
fact that key1 is red in color, we write (iscolor key1 red), with predicate
$\texttt{iscolor}\in\mathcal{P}$ and objects
$\texttt{key1},\texttt{red}\in\mathcal{O}$, with types
$\texttt{key},\texttt{color}\in\mathcal{T}$ respectively. Each environment
state $s$ is essentially a list of such predicate terms, stating which
relations are true or false for every valid combination of objects.

Since PDDL is first-order, we can evaluate whether a sentence $\phi$ is true
in a state $s$, where $\phi$ is compositionally defined in terms of logical
operations and (typed) quantifiers over predicates, and predicates can take
either objects $o\in\mathcal{O}$ or variables ?v as arguments $x_{i}$:

$\displaystyle\phi::=$ $\displaystyle\texttt{($P$ $x_{1}$ $...$
$x_{n}$)}|\texttt{(not $\phi$)}|\texttt{(and $\phi_{1}$
$\phi_{2}$)}|\texttt{(or $\phi_{1}$ $\phi_{2}$)}|$
$\displaystyle\texttt{(exists (?v - $\tau$) $\phi$)}|\texttt{(forall (?v -
$\tau$) $\phi$)}$

This expressivity allows us to determine the truth value of not just
individual relations, but also general queries about whether some property
holds for some class of objects. We will use this when modeling how statements
about agent’s beliefs can be quantitatively interpreted by an observer.

### Modeling Goal-Directed Actions

Following the principle of rational action (?, ?, ?), we assume that observers
model others as goal-directed agents who _plan_ to efficiently achieve to
goals. This principle can be captured probabilistically by adopting a
Boltzmann-rational model of action selection, given the agent’s goal $g$ and
their belief $b_{t-1}$:

$P(a_{t}|b_{t-1},g)=\frac{\exp\left(-\beta\hat{Q}_{g}(b_{t-1},a)\right)}{\sum_{a^{\prime}}\exp\left(-\beta\hat{Q}_{g}(b_{t-1},a^{\prime})\right)}$
(6)

Here $\hat{Q}_{g}(b_{t-1},a)$ represents the estimated cost of the optimal
plan to achieve goal $g$ after taking action $a$ starting at state $s_{t-1}$,
where $s_{t-1}$ is assumed equal to the agent’s belief $b_{t-1}$. $\beta$ is a
“rationality” parameter, controlling how optimal the agent’s actions are (high
$\beta$ is more optimal). To compute $\hat{Q}_{g}(b_{t-1},a)$ efficiently, we
leverage recent advances in sequential inverse planning (?, ?, ?), using real-
time heuristic search (?, ?, ?, ?, ?) as an _incremental_ planning algorithm
that rapidly estimates the cost to the goal $g$ from a state $s$, while
reusing past planning results to accelerate planning. Unlike earlier BToM
models which use offline value iteration algorithms (?, ?, ?), this approach
better captures and exploits the online nature of human planning.

### Joint Inference of Goals and Beliefs

Following ? (?), we model observers as performing joint inference over the
agent’s goal $g$ and belief history $b_{0:T}$ given a series of observed
actions $a_{1:T}$, The corresponding posterior $P(g,b_{0:T}|a_{1:T})$
factorizes as follows:

$P(g,b_{0:T}|a_{1:T})\propto\textstyle\sum_{s_{0:T}}P(g)P(s_{0})P(b_{0}|s_{0})\\\
\textstyle\prod_{t=1}^{T}P(a_{t}|b_{t-1},g)P(s_{t}|s_{t-1},a_{t})P(b_{t}|s_{t})$
(7)

Since we assume the agent has perfect knowledge of the environment
($b_{t}\equiv s_{t}$), this reduces to inferring $g$ and $s_{0:T}$:

$P(g,s_{0:T}|a_{1:T})\propto\\\
P(g)P(s_{0})\textstyle\prod_{t=1}^{T}P(a_{t}|s_{t-1},g)P(s_{t}|s_{t-1},a_{t})$
(8)

To compute this distribution, we initialize a set of weighted samples
$\\{(g^{i},s_{0}^{i},w^{i})\\}_{i=1}^{N}$ by enumerating over all possible
combinations of goals and initial states††In settings where there are too many
possibilities to enumerate over, we can sample a representative set of goals
and states instead., where $N$ is the number of combinations, and $w^{i}$ is
initialized to $P(g^{i})P(s_{0}^{i})$. Then we sequentially update each sample
$i$, multiplying $w^{i}$ by the likelihood $P(a_{t}|s_{t-1}^{i},g^{i})$ of
observing action $a_{t}$, and simulating the next state $s_{t}$ that results
from $a_{t}$:

$w^{i}\leftarrow w^{i}\cdot P(a_{t}|s_{t-1}^{i},g^{i})\qquad s_{t}\sim
P(s_{t}^{i}|s_{t-1}^{i},a_{t})$

Each weight $w^{i}$ represents the _unnormalized_ probability of the pair
$(g^{i},s_{0:t}^{i})$ at step $t$. Normalizing the weights gives us the
probability $P(g^{i},s_{0:t}^{i}|a_{1:t})=w^{i}/\textstyle\sum_{j=1}^{N}w_{j}$

In environments where state transitions $P(s_{t}|s_{t-1},a_{t})$ are
stochastic, the procedure above corresponds to a particle filtering or
sequential Monte Carlo algorithm (?, ?). However, since our environment is
deterministic, this algorithm reduces to _exact_ Bayesian filtering, which we
implement efficiently as a variant of Sequential Inverse Plan Search (?, ?)
using the Gen probabilistic programming system (?, ?).

### Quantitatively Interpreting Belief Statements

Having computed the posterior $P(g,b_{0:T}|a_{1:T})$, we model the
interpretation of belief statements in two steps: First, we _translate_ the
statement $\sigma$ from natural language into an appropriate formal
representation $\psi$. Second, we _evaluate_ the expected truth value of the
translated sentence $\psi$ with respect to inferred distribution over belief
states $b_{T}$, thereby grounding the meaning of the sentence in a Bayesian
theory-of-mind.

What formal language should statements like _“The player believes that there
is a red key in box 1”_ be translated into? PDDL is insufficient, since it
only describes objects and their (physical) properties. As such, we extend
PDDL with a believes operator, allowing us to translate the example above as
(believes player (exists (?k - key) (and (iscolor ?k red) (inside ?k box1))).
In general, any first-order PDDL sentence $\phi$ can be nested in the believes
operator parameterized by some agent $x$, such that (believes $x$ $\phi$) says
that agent $x$ believes $\phi$. This corresponds to a restricted fragment of
epistemic first-order logic (?, ?).

To perform the translation itself, we make use of large language models (LLMs)
as general purpose semantic parsers (?, ?). By constructing a small dataset of
example translations $\varepsilon$ from natural language to first-order
epistemic sentences, then prompting the language model with those examples and
the belief statement $\sigma$, we induce a distribution
$P(\psi|\sigma,\epsilon)$ over possible interpretations $\psi$ of $\sigma$. We
can then sample or greedily decode $\psi$ from this distribution.

Finally, to evaluate the observer’s credence in $\psi:=\texttt{(believes $x$
$\phi$)}$, we extract the sentence $\phi$ attributed to the agent $x$. We then
compute the expected value of $\phi$ being true in the belief state $b_{T}$:

$\displaystyle P(\psi|a_{1:T})$ $\displaystyle=\mathbb{E}_{b_{T}\sim
P(b_{T}|a_{1:T})}[\phi\text{ is true in }b_{T}]$
$\displaystyle=\textstyle\sum_{i=1}^{N}w_{i}\cdot[\phi\text{ is true in
}b_{T}^{i}]/\textstyle\sum_{j=1}^{N}w_{j}$

One notable aspect of this formulation is that the value of $P(\psi|a_{1:T})$
depends on the prior over belief states $P(b_{0})=P(s_{0})$. However, it is
not obvious what priors $P(b_{0})$ human observers bring to bear. As such, we
experiment with two possibilities: $U_{S_{0}}(s_{0})$ is uniform over the set
of possible initial states $s_{0}\in S_{0}$, and $U_{\psi}(s_{0})$ induces a
uniform prior $P(\psi)=0.5$ over the _statement_ being true. In the second
case, $P(\psi|a_{1:T})$ becomes a kind of (normalized) likelihood
$\bar{L}(\psi|a_{1:T})=\frac{P(a_{1:T}|\psi)}{P(a_{1:T}|\psi)+P(a_{1:T}|\neg\psi)}$,
which rates how much more evidence there is for the statement $\psi$ as
opposed to its negation $\neg\psi$. In the absence of evidence,
$\bar{L}(\psi|a_{1:T})=0.5$.

## Experiments

To evaluate our model as an account of how humans interpret belief statements,
we designed an experiment where human participants had to infer the goals,
plans, and beliefs of an agent solving a gridworld puzzle game called Doors,
Keys, & Gems (?, ?). In these puzzles, an agent has to pick up keys and unlock
doors in order to reach a valuable gem. Doors can only be opened by keys of
the same color and each key can be used once. To introduce partial
observability, we modified the domain to include boxes, where each box might
be empty or contain exactly one key.

Figure 2: Human and model inferences across 6 illustrative scenarios.
Judgement points are shown in the map as tooltips annotating the trajectory.
Below each map, we show goal inferences, followed by belief inferences
(assuming a $U_{\psi}$ as our belief prior for the BToM model). Overall, our
model closely matches human responses.

### Scenario Generation

We constructed 18 scenarios in the Doors, Keys, & Gems environment with
different maze designs and item locations (see Figure 2). In each scenario,
there were 4 goal gems of different shapes (triangle, square, hexagon,
circle), and 2 to 3 boxes. Each scenario was paired with two English
statements describing the agent’s beliefs about the contents of the boxes,
such as _“The player believes that there is a red key in box 1.”_ To test
compositional language understanding, we also created negated, conjunctive,
and disjunctive belief statements (e.g. _“The player believes that there is a
blue or red key in either box 2 or box 3.”_)

### Experiment Design

Our study was conducted online through a custom experimental interface.
Participants first completed a tutorial, along with a comprehension quiz.
During each scenario, participants rated the goals and beliefs of the observed
agent at several judgement points. For goal ratings, participants were
presented with a checkbox for each gem, and asked to select all gems that were
likely to be the agent’s goal. For belief ratings, participants were shown a
scale from 1 to 7 below each belief statement, with 1 representing ”Definitely
False”, 7 representing ”Definitely True”, and 4 representing ”Equally Likely
to be True or False”. In our analysis, we normalized these ratings to lie
between 0 and 1.

### Participants

We recruited 100 US participants through Prolific (mean age = 39.57, 50
female, 49 male, 1 agender). Each participant rated 9 out of the 18 scenarios.
Participants were paid US$15/hr, and received a bonus for correctly inferring
the agents’ goals ($\$0.05/n$ for each judgment point where they selected $n$
goals, one of which was correct).

Table 1: Human-model correlations for both goal attributions and belief statement ratings. Bootstrap confidence intervals with a 95% confidence level are reported in brackets. Model | Belief Prior | Goal Attributions | Belief Statements
---|---|---|---
Full BToM | Uniform over Statements ($U_{\psi}$) | 0.93 [0.91, 0.94] | 0.92 [0.91, 0.93]
Full BToM | Uniform over States ($U_{S_{0}}$) | 0.86 [0.85, 0.87]
Heuristic Mentalizer | Uniform over Statements ($U_{\psi}$) | 0.17[0.13, 0.19] | 0.04 [0.02, 0.06]
Heuristic Mentalizer | Uniform over States ($U_{S_{0}}$) | 0.19 [-0.03, 0.40]
Non-Mentalizer | Uniform over States ($U_{S_{0}}$) | — | 0.19 [-0.03, 0.40]
Omniscient Observer | — | — | 0.64 [0.48, 0.75]
Ignorant Observer | — | — | —
Figure 3: Correlation plots comparing belief judgments from humans ($y$-axis)
against models ($x$-axis). Our full BToM model shows a significant better fit
to human belief ratings than alternative models

### Alternative Models

Since our account of the semantics of belief statements crucially involves the
ability to understand and infer the mental states of other agents, we compare
our model against baselines that either do not perform such mentalizing at
all, or perform limited versions of such mentalizing. These baselines are as
follows:

#### Omniscient Observer:

Possesses complete knowledge of the validity of the belief statements. This
models what epistemic logic would deduce about the agent’s beliefs, given the
premise that the agent knows everything about the world, and given that the
observer does too.

#### Ignorant Observer:

Rates all belief statements as false due to insufficient premises. This models
what epistemic logic would (fail to) conclude about the agent’s beliefs,
following a semantics of negation as failure to deduce facts.

#### (Uncertain) Non-Mentalizing Observer:

Rates all belief statements according to the prior probability that they are
true, according to the uniform prior $U_{S_{0}}$ over states.

#### Heuristic Mentalizer:

Assumes that the agents will always move physically closer to their desired
goal, ignoring instrumental actions like picking up keys. This baseline shows
the importance of accounting for means-ends coherence when inferring an
agent’s beliefs from their actions.

## Results

### Qualitative Analysis

Figure 2 shows the inferences of both humans and our model in 6 illustrative
scenarios. These examples demonstrate qualitatively how our model fits human
data. Due to space constraints, we describe only the first 3 examples.

In the first two examples, once the player picks up a red key, both human
participants and our model rate the circle to be the only likely goal. This is
because the circle is the only goal that requires picking up a red key. Once
the player walks down the corridor past box 1, both humans and our model rate
statement 1 (_“The player believes that there is a blue key in box 1.”_) to be
highly improbable. This is because the player needs a blue key to reach the
inferred goal and a rational agent would not walk past box 1 if they knew it
contained a blue key. As the agent walks towards box 2 in Example 1, both
humans and our model find it likely that there is a blue key in box 2, whereas
in Example 2, once the player walks past box 2, both human participants and
our model assign a higher likelihood for statement 2 (_“The player believes
that there is a blue key in box 3.”_)

In Example 3, once the player picks up a blue key, both humans and our model
infer the square and the hexagon to be the likely goals, since they are locked
behind a blue door nearby. As the player walks past the blue door and towards
boxes 2 and 3, these inferences veer towards the circle. It also becomes more
likely for there to be a red key than a blue key among boxes 2 and 3, since
the player needs a red key to reach the goal.

### Quantitative Analysis

Correlation plots between human and model belief judgments are shown in Figure
3, and a summary of key results is presented in Table 1. We find that our full
BToM model has a much better fit with human ratings than the baselines. This
demonstrates the importance of a theory-of-mind for a semantics of belief
statements: Without accounting for the coherence between an agent’s beliefs,
goals, and actions, observers cannot infer an agent’s beliefs, and hence
cannot evaluate the probability of such belief statements. Our results also
demonstrate the importance of a _probabilistic_ theory-of-mind. Human
judgments about what agents believe are not all-or-nothing phenomena. Our
account provides a semantics for such graded judgments, unlike logical models
which judge statements to be either false or true.

Interestingly, while both versions of our full model correlated well with
human belief judgments (Table 1, rows 1–2), the model assuming a uniform
statement prior $U_{\psi}$ had a significantly better fit. We found that this
was because certain statements are true in _more possible worlds_ (e.g. _”The
agent believes that there is a red key in box 1 or box 2.”_ vs _”The agent
believes that there is a red key in box 1.”_), such that they have a higher
_base rate_ of being true if all states $s_{0}$ are equally probable. Our
participants did not seem to take into account these base rates when providing
responses. Instead, they tended to rate a statement more highly only if there
was more _evidence_ for that statement, consistent with our earlier suggestion
that belief ratings might correspond to a normalized likelihood
$\bar{L}(\psi|a_{1:T})$. While this is not Bayesian in the orthodox sense, it
is semantically and pragmatically quite reasonable — it suggests that people
are only willing to say that a person believes that $\phi$ if there is
evidence for that belief.

## Discussion

In this study, we explored how humans reason about other agents’ beliefs and
interpret beliefs formulated through natural language. Our experiment shows
the deep connection between how we interpret language about belief, and how we
understand other agents’ minds: People are able to interpret and adjust their
evaluations of natural language statements as new actions come to light,
demonstrating the importance of grounding such language in a theory of how
agents’ beliefs and goals are connected to their plans and actions.

All that said, there is much work to be done before a model like ours can
account for all the ways in which people use and interpret language about
beliefs. A key limitation of our current model is that it only explains the
_deterministic_ beliefs of other agents, under the assumption that what other
agents believe is what they _know_. But of course, one of the hallmarks about
belief — and how we reason and talk about it — is that it can come apart from
reality in all sorts of ways. People have uncertain beliefs (just like our
observer model does), which we express in language using modals like ”might”
or ”unlikely”. People have false beliefs, and we form sentences describing
them all the time (_“He thinks that …, but actually…”_). People might be
ignorant or possess only partial knowledge, and we describe this differently
from mere uncertainty. Relatedly, people often think and talk about belief in
abstract terms, without concretizing those beliefs into concrete worlds like
our model does. If we are to explain such phenomena, we will need a much
richer theory-of-mind than our model currently offers — one that models our
uncertainty about other’s uncertainty (?, ?, ?), as well as the abstract ways
we represent both the world and each others’ minds (?, ?).

## Acknowledgements

This work was funded in part by the DARPA Machine Common Sense, AFOSR, and ONR
Science of AI programs, along with the MIT-IBM Watson AI Lab, and gifts from
Reid Hoffman and the Siegel Family Foundation. Tan Zhi-Xuan is supported by an
Open Philanthropy AI Fellowship.

We thank our colleagues Brian Leahy, Cedegao Zhang, and Megan Wei for helpful
discussions and suggestions during the development of this project

## References

  * Baker et al.Baker et al. Baker, C. L., Jara-Ettinger, J., Saxe, R., Tenenbaum, J. B.  (2017).  Rational quantitative attribution of beliefs, desires and percepts in human mentalizing.  _Nature Human Behaviour_ , _1_(4), 1–10.
  * Baker et al.Baker et al. Baker, C. L., Saxe, R., Tenenbaum, J. B.  (2009).  Action understanding as inverse planning.  _Cognition_ , _113_(3), 329–349.
  * Barto et al.Barto et al. Barto, A. G., Bradtke, S. J., Singh, S. P.  (1995).  Learning to act using real-time dynamic programming.  _Artificial intelligence_ , _72_(1-2), 81–138.
  * Bigelow et al.Bigelow et al. Bigelow, E. J., McCoy, J. P., Ullman, T. D.  (2023).  Non-commitment in mental imagery.  _Cognition_ , _238_ , 105498.
  * ChisholmChisholm Chisholm, R. M.  (1955).  Sentences about believing.  In _Proceedings of the aristotelian society_ (Vol. 56, pp. 125–148).
  * Cusumano-Towner et al.Cusumano-Towner et al. Cusumano-Towner, M. F., Saad, F. A., Lew, A. K., Mansinghka, V. K.  (2019).  Gen: a general-purpose probabilistic programming system with programmable inference.  In _Proceedings of the 40th acm sigplan conference on programming language design and implementation_ (pp. 221–236).
  * Del Moral et al.Del Moral et al. Del Moral, P., Doucet, A., Jasra, A.  (2006).  Sequential Monte Carlo samplers.  _Journal of the Royal Statistical Society Series B: Statistical Methodology_ , _68_(3), 411–436.
  * DennettDennett Dennett, D. C.  (1989).  _The intentional stance_.  MIT press.
  * Gergely CsibraGergely Csibra Gergely, G., Csibra, G.  (2003).  Teleological reasoning in infancy: The naıve theory of rational action.  _Trends in cognitive sciences_ , _7_(7), 287–292.
  * Gmytrasiewicz DoshiGmytrasiewicz Doshi Gmytrasiewicz, P. J., Doshi, P.  (2005).  A framework for sequential planning in multi-agent settings.  _Journal of Artificial Intelligence Research_ , _24_ , 49–79.
  * Gochet GribomontGochet Gribomont Gochet, P., Gribomont, P.  (2006).  Epistemic logic.  In _Handbook of the history of logic_ (Vol. 7, pp. 99–195).  Elsevier.
  * HarmanHarman Harman, G.  (1982).  Conceptual role semantics.  _Notre Dame Journal of Formal Logic_ , _23_(2), 242–256.
  * Hernández et al.Hernández et al. Hernández, C., Sun, X., Koenig, S., Meseguer, P.  (2011).  Tree adaptive a.  In _The 10th international conference on autonomous agents and multiagent systems-volume 1_ (pp. 123–130).
  * Houlihan et al.Houlihan et al. Houlihan, S. D., Kleiman-Weiner, M., Hewitt, L. B., Tenenbaum, J. B., Saxe, R.  (2023).  Emotion prediction as computation over a generative theory of mind.  _Philosophical Transactions of the Royal Society A_ , _381_(2251), 20220047.
  * Jara-Ettinger et al.Jara-Ettinger et al. Jara-Ettinger, J., Schulz, L., Tenenbaum, J.  (2019).  The naive utility calculus as a unified, quantitative framework for action understanding.  _PsyArXiv_.
  * Koenig LikhachevKoenig Likhachev Koenig, S., Likhachev, M.  (2006).  Real-Time Adaptive A*.  In _Proceedings of the fifth international joint conference on autonomous agents and multiagent systems_ (pp. 281–288).
  * KorfKorf Korf, R. E.  (1990).  Real-time heuristic search.  _Artificial intelligence_ , _42_(2-3), 189–211.
  * McDermott et al.McDermott et al. McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., … Wilkins, D.  (1998).  _PDDL - the Planning Domain Definition Language._ Technical Report CVC TR-98-003/DCS TR-1165, Yale Center for Computational ….
  * ParteePartee Partee, B. H.  (1973).  The semantics of belief-sentences.  In _Approaches to natural language: Proceedings of the 1970 stanford workshop on grammar and semantics_ (pp. 309–336).
  * Pöppel KoppPöppel Kopp Pöppel, J., Kopp, S.  (2019).  Satisficing mentalizing: Bayesian models of theory of mind reasoning in scenarios with different uncertainties.  _arXiv preprint arXiv:1909.10419_.
  * Shin et al.Shin et al. Shin, R., Lin, C. H., Thomson, S., Chen, C., Roy, S., Platanios, E. A., … Van Durme, B.  (2021).  Constrained language models yield few-shot semantic parsers.  _arXiv preprint arXiv:2104.08768_.
  * StalnakerStalnaker Stalnaker, R.  (1987).  Semantics for belief.  _Philosophical Topics_ , _15_(1), 177–190.
  * Wong et al.Wong et al. Wong, L., Grand, G., Lew, A. K., Goodman, N. D., Mansinghka, V. K., Andreas, J., Tenenbaum, J. B.  (2023).  From word models to world models: Translating from natural language to the probabilistic language of thought.  _arXiv preprint arXiv:2306.12672_.
  * Ying, Collins, et al.Ying, Collins, et al. Ying, L., Collins, K. M., Wei, M., Zhang, C. E., Zhi-Xuan, T., Weller, A., … Wong, L.  (2023).  The neuro-symbolic inverse planning engine (nipe): Modeling probabilistic social inferences from linguistic inputs.  _arXiv preprint arXiv:2306.14325_.
  * Ying, Zhi-Xuan, et al.Ying, Zhi-Xuan, et al. Ying, L., Zhi-Xuan, T., Mansinghka, V., Tenenbaum, J. B.  (2023).  Inferring the goals of communicating agents from actions and instructions.  In _Proceedings of the aaai symposium series_ (Vol. 2, pp. 26–33).
  * Zhi-Xuan et al.Zhi-Xuan et al. Zhi-Xuan, T., Mann, J., Silver, T., Tenenbaum, J., Mansinghka, V.  (2020).  Online bayesian goal inference for boundedly rational planning agents.  _Advances in Neural Information Processing Systems_ , _33_.


11institutetext: Algorand Inc, Boston, MA 02116, USA 22institutetext:
Department of Computer Science, Stony Brook University, NY 11794, USA
22email<EMAIL_ADDRESS>33institutetext: Department of Computing, Hong Kong
Polytechnic University, Hong Kong, China
33email<EMAIL_ADDRESS>
# Maximal Information Propagation via Lotteries††thanks:  The authors thank
Costantinos Daskalakis, Yossi Gilad, Victor Luchangco, and Silvio Micali for
helpful discussions in the early stage of this work, and several anonymous
reviewers for helpful comments. Part of this work was done when Bo Li was an
intern at Algorand. Bo Li is partially supported by the Hong Kong Polytechnic
University (No. P0034420).

Jing Chen 1122 Bo Li 33

###### Abstract

Propagating information to more people through their friends is becoming an
increasingly important technology used in domains such as blockchain,
advertising, and social media. To incentivize people to broadcast the
information, the designer may use a monetary rewarding scheme, which specifies
who gets how much, to compensate for the propagation. Several properties are
desirable for the rewarding scheme, such as budget feasible, individually
rational, incentive compatible and Sybil-proof. In this work, we design a free
market with lotteries, where every participant can decide by herself how much
of the reward she wants to withhold before propagating to others. We show that
in the free market, the participants have a strong incentive to maximally
propagate the information and all the above properties are satisfied
automatically.

###### Keywords:

Information propagation Nash equilibrium Free market design.

##  1 Introduction

Propagating information to more people through their friends is becoming an
increasingly important technique used in many fields including advertising,
social media [12] and blockchain [3, 14]. To incentivize people to broadcast
the information, the information holder, i.e., the mechanism designer, may use
a monetary rewarding scheme $\mathbf{r}=(r_{1},\cdots,r_{n})$ to compensate
people, where $r_{i}$ is the reward assigned to player $i$. The rewarding
scheme is expected to satisfy several properties, such as being incentive
compatible, (strongly) budget feasible, individual rational, and Sybil-proof.
Informally, incentive compatibility requires that each player does not
decrease her utility by propagating the information, budget feasibility
requires $\sum_{i}r_{i}\leq B$ when the mechanism designer has a budget of
$B$, strong budget feasibility requires $\sum_{i}r_{i}=B$, individual
rationality requires $r_{i}\geq 0$ for all $i$, and Sybil-proofness requires
the players do not benefit by making fake copies in the information
propagation process. Accordingly, designing a rewarding scheme to satisfy all
or some of the above properties establishes a large research agenda. For
example, maximal information propagation with budgets is studied in [26],
where a rewarding scheme that is incentive compatible, strongly budget
feasible and individual rational is proposed. But the scheme is not Sybil-
proof. A Sybil-proof rewarding scheme is designed in [6], but it is not
strongly budget feasible, where a small portion of the claimed reward is
distributed among the players. In this work, instead of designing a
centralized rewarding scheme, we propose a free market with lotteries where
everyone can decide how much of the reward she wants to withhold before
propagating to others. We show that in such a market, the players have strong
incentives to fully propagate the information and all above properties are
satisfied automatically.

To illustrate our design, let us first consider a toy game. Initially, a
seller sends her promotion information to a small number of players she is
able to reach, denoted by $N$ and $n=|N|$ who are called aware players. The
information is associated with a lottery such that one winner among aware
players will be uniformly and randomly selected to get a reward normalized to
$1. When nobody propagates the information, everyone’s expected reward is
$1/n$. For player $i\in N$, she has a set of friends $F_{i}$ such that
$f_{i}=|F_{i}|\geq 1$ and $N\cap F_{i}=\emptyset$. If $i$ signs an agreement
with $F_{i}$ such that if anyone in $F_{i}$ is selected to be the winner, the
reward is given $i$, then by propagating the information to $F_{i}$, player
$i$’s reward, which equals to the probability that the winner is selected from
$F_{i}\cup\\{i\\}$, is

$\displaystyle\frac{1+f_{i}}{n+f_{i}}>\frac{1}{n}.$ (1)

That is $i$ can increase her reward by propagating the information to her
friends, and thus no propagation for $N$ is not a Nash equilibrium. Actually,
since Inequality 1 holds for any $n\geq 2$, everyone’s dominate strategy is to
propagate the formation to their friends. But to what extent will they
propagate?

Assuming all players in $N$ except $i$ inform the information to their friends
and withhold the complete reward, let us see what $i$ will do. If $i$ does not
withhold the complete reward but shares a small amount, say $0<c<1$, with
$F_{i}$, $i$ can again improve her utility. For $j\in F_{i}$, let $F_{j}$ be
$j$’s friends who are not in the game. Supposing all $j\in F_{j}$ adopts the
same strategy with $N\setminus\\{i\\}$, i.e., fully propagating the
information to their friends and withholding the complete reward $c$, we
compare two cases for player $i$: (1) $i$ does not leave any reward to $j$,
and (2) $i$ leaves $c$ to $j$. To ease the notation, suppose there are
$n^{\prime}$ players who are in the game except $j$’s friends $F_{j}$ for
every $j\in F_{i}$. It is not hard to see that for case (1), player $i$’s
reward is $(1+f_{i})/n^{\prime}$ and for case (2), her reward is

$\frac{1+(1-c)\cdot\sum_{j\in F_{i}}f_{j}}{\sum_{j\in
F_{i}}f_{j}+n^{\prime}}>\frac{1+f_{i}}{n^{\prime}},$

as long as for all $j\in F_{i}$,

$f_{j}>\frac{n+1}{n(1-c)-1}\to 1\text{ if $c\to 0$.}$

Thus we conclude that withholding the complete reward from propagation is not
a Nash equilibrium, and every player wants to leave partial reward to her
friends for incentivizing them to further propagate the information.

We note that the initial $n$ aware players are in the Prisoner’s dilemma. If
they do not propagate the information, each of them has expected utility of
$1/n$. However, it is dominant for each of them to refer their friends by
sacrificing partial reward, resulting the expected utility strictly smaller
than $1/n$. This dilemma actually motivates the information propagation in the
free market.

A more practical example for the above scenario is the mining game of Bitcoin
[23]. In Bitcoin, when a user makes a transaction (the information sender),
she wants the transaction to be broadcasted (with other necessary information
such as account information, transfer amount, crypto signature and etc) in the
network so that the miners can authorize the validity of the transaction and
assemble newly verified transactions into blocks. The miners compete to
propose their blocks to the public chain by solving a computationally hard
puzzle, and the winning probability is proportional to the share of each
miner’s computation power in the system. Accordingly, the transaction maker
can reward the winning miner who authorizes her transaction a fixed amount of
Bitcoins. At first glance, it seems that the miners may not want to broadcast
the transaction since only the miners who know the transaction can be
rewarded. A centralized rewarding scheme is proposed in [3] which not only
rewards the winner but also other miners who helped broadcast the transaction.
By carefully designing who gets much, their scheme is Sybil-proof in tree
networks. However, as we will show in this work, the design of free market
with lotteries automatically incentivizes the miners to propagate the
transaction and satisfies all other desired properties as well. Thus the take-
home message of this work is that

> the mechanism designer does not need to specify each player’s reward, the
> market itself already provides incentives for maximal propagation.

###  1.1 Our Contribution

We model the problem, and the Bitcoin example, as an information propagation
game in a free market, where a sender has a single piece of information to be
broadcasted. For simplicity, we first assume the players are connected by a
complete $d$-ary tree with $d\geq 3$, and all players’ winning probabilities
are the same. If there is an edge between two players, they are friends and
one can be informed the information by the other. A strategy profile is called
full propagation if every player withholds a minimum charge and leaves the
remaining reward to all her friends, so that a maximum number of people could
be aware of the information. We show that full propagation forms a Nash
equilibrium which satisfies extra properties and thus is more stable than an
arbitrary one.

First, full propagation is robust to collective deviations of friends, i.e.,
connected coalition-proof [4]. In the seminal work by Myerson [22], the
communication game is proposed where the network on players represents the
possible communication between them. Originally, it is associated with
cooperative games and only coalitions formed by players who can communicate
with each other (i.e., connected subgraphs in the network) are concerned. We
adapt this principle to our problem and show that any deviation of a connected
coalition of players from full propagation makes at least one of them worse
off.

Second, full propagation survives in any order of iterative elimination of
dominated strategies, and uniquely survives in a particular one. This result
coincides with and generalizes the result of [3], where a centralized
rewarding scheme is designed. In a centralized rewarding scheme, a player can
only misbehave by withholding the information and claiming Sybil copies, while
in a free market a player can arbitrarily claim how much of the reward she
wants to deduct before propagating to others. We formally discuss the
difference between our work and [3] at the end of Section 3. Recall that
strategy $s$ (weakly) dominating $s^{\prime}$, denoted by $s\preceq
s^{\prime}$, means choosing $s$ always gives at least as good an outcome as
choosing $s^{\prime}$, no matter what the other players do, and there is at
least one profile of opponents’ actions for which $s$ gives a strictly better
outcome than $s^{\prime}$. We prove that full propagation is the unique
strategy profile that survives in an interval-based monotone elimination of
dominated strategies, coinciding with the players’ reasoning process as
illustrated in the introduction.

Our main results can be summarized as follows.

Main Result 1. (Theorems 3.1 and 3.2) In the tree-structured free market with
lotteries, full propagation achieves maximal propagation and satisfies the
following:

  1. 1.

Full propagation is a Nash equilibrium;

  2. 2.

Any deviation of a coalition of friends hurts at least one of them;

  3. 3.

Full propagation survives in any order of iterative elimination of dominated
strategies;

  4. 4.

There is an order of iterative elimination of dominated strategies such that
full propagation is the unique surviving strategy.

We then extend the above results to non-tree networks. For arbitrary networks,
we introduce stronger relationships than friends, good friends and best
friends, using shortest paths from the information sender to players. Although
properties 3 and 4 in Main Result 1 do not hold, we show that if every player
has at least three good friends, full propagation is a Nash equilibrium that
is also connected coalition-proof on the induced good-friendship subgraph. It
is noted that $d$-ary tree with $d\geq 3$ is a special case satisfying this
condition.

Main Result 2. (Theorem 4.1) If every player has at least 3 good friends, then
full propagation is a Nash equilibrium that is connected coalition-proof on
the good-friendship subgraph.

In conclusion, if the network is well structured, the free market with
lotteries is incentive compatible where players are willing to fully propagate
the information. It is not hard to check that our scheme also satisfies other
properties mentioned in the introduction. It is strongly budget feasible and
individual rational, as the full reward will be given to the players and none
of them needs to pay. Our scheme is also Sybil-proof, as in our game, the
players are required to provide certificates on how many people they have
referred to. For example, in Bitcoin each miner needs to contribute their
computing power on authorizing the transaction; and in sales promotion, only
people who physically appear in the market can be selected as the winner.
Therefore, as everyone in our game can arbitrarily decide how much reward she
wants to get back from friends, making Sybil identities is the same as
withholding a higher fraction of the reward.

Finally, it is an interesting future direction to generalize our results to
random networks. We believe full propagation brings players high utility in a
broader class of networks. To shed more light in this direction, we conduct
experiments in Section 5 for our scheme under general random networks. In all
experiments, full propagation brings a player the maximum utility. Moreover,
the utility gap between full propagation and other strategies is actually
large.

###  1.2 Related Works

Our work is partially motivated by the extensive study of incentivizing relays
in a blockchain network to propagate transactions. While this has been studied
in the literature, most of them focus on centralized algorithms where each
relay’s reward is fixed and decided by the algorithm. With these algorithms,
to gain higher utility, a strategic relay may claim fake copies, i.e., Sybil
attack [11]. Accordingly, in works such as [3, 15], Sybil-proof algorithms are
studied. Since in our free market each relay is able to arbitrarily decide how
much reward she is willing to withhold, it is superfluous for them to make
fake copies, and thus, our results directly imply Sybil-proofness. The free
market ideas have also been discussed independently in [1] and [7] without a
systematic analysis.

Our work also aligns with the fundamental study of what the optimal way is to
reward miners for their work on authorizing transactions. Currently, the most
popular rewarding scheme, as adopted by Bitcoin, is to reward miners
proportionally to their share of the total contributed computational power. As
shown in [9], the proportional allocation rule is the unique rule that is
simultaneously non-negative, budget-balanced, symmetric, Sybil-proof, and
collusion-proof. In reality, however, to earn steady rewards, miners pool
themselves together, and the pools are vulnerable to security attacks, such as
selfish mining attack [16, 18, 20, 10], block withholding attack [24, 25], and
denial of service attack [17]. Cooperative games are used in [21] to show that
under high transaction loads, it is hard for managers to distribute rewards in
a stable way.

Outside the scope of blockchain, information propagation has also been studied
in multi-level marketing [13, 12] and query incentive networks [19, 2, 6, 5,
8]. There are major differences between the transaction propagation in a
blockchain network and the query retrieval in peer-to-peer network. The
players in a query incentive network do not compete with the ones who
forwarded the message to them, and cannot generate an answer that they do not
have. Whereas in a blockchain network, every aware player is a potential
authorizer with probability proportional to their stakes or computational
powers.

##  2 Game Theoretic Model and Preliminaries

For technical simplicity, we first assume all players are connected by a tree
$\mathcal{G}=(V,E)$. Let $s$ be the root of $\mathcal{G}$ who is the sender of
the information. Note that $s$ is not a player in our game. Suppose $s$ has
$f$ children and thus excluding $s$ from $G$, there are $f$ subtrees denoted
by $\\{T_{1},\cdots,T_{f}\\}$. When there is no confusion, we also use each
$T_{i}$ to denote the set of nodes in it. Assume all these subtrees are
complete $d$-ary and $f\geq d\geq 3$. Call $N=V\setminus\\{s\\}$ the set of
players and denote by $n=|N|$. To make the players distinguishable from the
sender, we stop calling $s$ the root and only call her sender. Instead, we
call the roots of these subtrees roots on depth 0, who are the initial players
of the game, as shown in the following figure. In a similar fashion, the
children of these subtree roots are viewed to be on depth 1 and so on. For
each node $i\in V$, let $NB_{i}$ be the set of her children in $\mathcal{G}$,
and thus $NB_{s}$ contains all initial players.

$\mbox{Sender }s$$\mbox{Depth }0$(Roots)$\mbox{Depth
}1$...$T_{1}$$T_{2}$$T_{3}$...... Figure 1: An illustration of the tree
structure.

We next define the propagation game $\Gamma=(N,{\bf S},{\bf u})$ on
$\mathcal{G}$. Without loss of generality, we assume the initial reward set by
the sender is 1. Denote by $S_{i}$ the strategy space of each player $i\in N$.
Let ${\bf S}=S_{1}\times\cdots\times S_{n}$ be the strategy profiles. Any
strategy $s_{i}\in S_{i}$ is a mapping from $\mathbb{R}^{+}$ to
$(\mathbb{R}^{+}\cup\\{\bot\\})^{|NB_{i}|}$, where
$\mathbb{R}^{+}=[0,+\infty)$. That is, upon receiving the information with
remaining reward $x_{i}$, player $i$ decides how much reward
$s_{i}(x_{i})_{j}$ to leave to her child $j$ by sending the information to $j$
or not to inform $j$ if $s_{i}(x_{i})_{j}=\bot$. Denote by
$s_{i}(x_{i})=(s_{i}(x_{i})_{1},\cdots,s_{i}(x_{i})_{|NB_{i}|})$. A feasible
strategy is that for all $j\in NB_{i}$, if $x_{i}\geq x_{\min}$, $0\leq
s_{i}(x_{i})_{j}\leq x_{i}-x_{\min}$ or $s_{i}(x_{i})_{j}=\bot$; otherwise,
$s_{i}(x_{i})_{j}\equiv\bot$. Here $x_{\min}>0$ is a sufficiently small number
prefixed by the system. Denote by ${\bf s}=s_{1}\times\cdots\times s_{n}$ a
strategy profile. For any strategy profile ${\bf s}\in{\bf S}$ and an initial
reward, there is a fixed set of players who can be informed the information,
called aware players and denoted by $N^{*}({\bf s})$. When ${\bf s}$ is clear
in the context, we simply write $N^{*}$. To avoid cumbersome calculations, all
aware players will get the reward with equal probability of
$\frac{1}{|N^{*}|}$, and the winner needs to share the reward with her
ancestors from her to the sender as committed. Thus, a player $i$’s (expected)
utility consists of two parts: authorizing utility and referring utility,

$u_{i}({\bf s};x_{i})=x_{i}\cdot\frac{1}{|N^{*}|}+\sum_{j\in
NB_{i},s_{i}(x_{i})_{j}\neq\bot}(x_{i}-s_{i}(x_{i})_{j})\cdot\frac{n_{ij}}{|N^{*}|},$

where $n_{ij}$ is the number of aware players following $j$ and including $j$.

Next we formulate the intuition in Inequality 1 by the following lemma, which
shows it is always (strictly) better for a player to propagate the
information.

###### Lemma 1

For any player $i$, let ${\bf s}_{-i}$ be $-i$’s strategy profile such that
the remaining reward $x_{i}$ to $i$ is at least $x_{\min}$. Let
$s_{i}(x_{i})=(z_{1},\cdots,z_{j},\cdots,z_{|NB_{i}|})$ be a strategy with
$z_{j}=\bot$ for some $j$ and
$s^{\prime}_{i}(x_{i})=(z_{1},\cdots,z^{\prime}_{j},\cdots,z_{|NB_{i}|})$ be a
new strategy by changing $j$’s action from $\bot$ to $0$. Then
$u_{i}(s_{i},{\bf s}_{-i})<u_{i}(s^{\prime}_{i},{\bf s}_{-i})$.

We prove Lemma 1 in the appendix. By Lemma 1, every aware player does not get
hurt by propagating the information to all her neighbours, and thus in what
follows, we assume without loss of generality $s_{i}(x_{i})_{j}\geq 0$ for any
$x_{i}\geq x_{\min}$ and $j\in NB_{i}$. Moreover, in the following sections,
we will see that the aware players actually want to maximally propagate the
information. A feasible strategy $s_{i}$ is called full propagation (FP for
short) if $s_{i}(x_{i})_{j}=(k-1)x_{\min}$ for all $j$ and $kx_{\min}\leq
x_{i}<(k+1)x_{\min}$ with $k\geq 1$. That is in an FP strategy, a player wants
to inform all her neighbours by leaving the maximal reward to them. A feasible
strategy profile ${\bf s}=(s_{i})_{i\in N}$ is called FP if every $s_{i}$ is
FP. Denote by ${\bf s}^{*}=(s_{i}^{*})_{i\in N}$ the FP strategy profile.

##  3 Main Results

To ease formulas, we define the following notations. For each subtree $T$, let

$G(k)=\sum_{j=1}^{k}d^{j-1}=\frac{d^{k}-1}{d-1}$

be the number of nodes from depth 0 to depth $k-1$. Note that when $d\geq 3$
and $k\geq 1$, $G(k)\geq 2k-1$. Moreover, for any $k\geq 1$,

$\displaystyle(f-1)G(k+1)$ $\displaystyle\geq
d^{k+1}-1>d(d^{k}-1)\geq\frac{d+1}{d-1}(d^{k}-1)$ $\displaystyle=(d+1)G(k)\geq
dG(k)+2k-1.$ (2)

Denote by $H\cdot x_{\min}=1$ the sender’s initial reward, where $H>1$ is an
integer. Then $H$ is the maximal depth that the information can reach. For any
player $i$ in depth $j\geq 0$, no matter what $i$’s previous players do, $i$
is not able to receive the information with remaining reward more than
$(H-j)\cdot x_{\min}$ since each of $i$’s ancestors needs to withhold at least
$x_{\min}$. Moreover, all the users in and below depth $H$ are not considered
as strategic players. Finally, under FP strategies, the number of aware
players is $f\cdot G(H+1)$.

###  3.1 Technical Lemmas

We next introduce two technical lemmas which are crucial to prove the main
results. For a subtree $T$, let $\pi_{0}(T)$ be the number of players outside
of $T$ who are aware of the information. If $T$ is clear from the context, we
write $\pi_{0}$ for short.

###### Lemma 2

Consider the sub-game induced on a single subtree $T$, where $r$ is the root
player and $g$ is one of $r$’s descendants. Assume $r$ receives the
information with reward $x_{r}$ and $k\cdot x_{\min}\leq x_{r}<(k+1)\cdot
x_{\min}$ for some $k\geq 1$. If $d\geq 3$ and $\pi_{0}\geq d\cdot G(k)+2k-1$,
$r$’s utility is maximized when $g$ plays FP strategy, taking the actions of
the others as given.

###### Proof

Note that if $x_{r}<2x_{\min}$ or the information cannot reach $g$, $r$’s
utility does not depend on $g$’s action, thus the statement is trivially true.
In the following we assume $x_{r}\geq 2x_{\min}$.

Taking the actions of the players (including $r$) except $g$ as given, let
$\Delta_{j}$ be the total number of $r$’s referred players from $r$’s child
$j$ and $\Delta=\sum_{j\in NB_{r}}\Delta_{j}$. Let $g^{\prime}$ be $g$’s
ancestor who is $r$’s direct child or $g^{\prime}=g$ when $g$ is $r$’s child.
Thus $g$’s strategy can only change $\Delta_{g^{\prime}}$, which is the single
variable of $r$’s utility. Formally, $r$’s utility can be written as (assuming
$\pi_{0}$ includes $r$ to simplify notions)

$\displaystyle u_{r}(\Delta_{g^{\prime}})$
$\displaystyle=x_{r}\frac{1}{\pi_{0}+\Delta}+\sum_{j\in
NB_{r}}(x_{r}-s_{r}(x_{r})_{j})\frac{\Delta_{j}}{\pi_{0}+\Delta}$
$\displaystyle=\frac{x_{r}+\sum_{j\in
NB_{r}}(x_{r}-s_{r}(x_{r})_{j})\Delta_{j}}{\pi_{0}+\Delta}.$

Calculating the derivative of $u_{r}(\Delta_{g^{\prime}})$, we have

$\displaystyle u^{\prime}_{r}(\Delta_{g^{\prime}})$ $\displaystyle=$
$\displaystyle\dfrac{(x_{r}-s_{r}(x_{r})_{g^{\prime}})(\pi_{0}+\Delta)-(x_{r}+\sum_{j\in
NB_{r}}(x_{r}-s_{r}(x_{r})_{j})\Delta_{j})}{(\pi_{0}+\Delta)^{2}}$
$\displaystyle=$
$\displaystyle\dfrac{(x_{r}-s_{r}(x_{r})_{g^{\prime}})\pi_{0}-x_{r}-\sum_{j\neq
g^{\prime}}(s_{r}(x_{r})_{g^{\prime}}-s_{r}(x_{r})_{j})\Delta_{j}}{(\pi_{0}+\Delta)^{2}}$
$\displaystyle\geq$ $\displaystyle\dfrac{x_{\min}\pi_{0}-x_{r}-\sum_{j\neq
g^{\prime}}(x_{r}-s_{r}(x_{r})_{j})\Delta_{j}}{(\pi_{0}+\Delta)^{2}},$

where the inequality is because $s_{r}(x_{r})_{j}\leq x_{r}-x_{\min}$ for any
$j$. Let

$\displaystyle f_{j}(y_{j})$ $\displaystyle=$
$\displaystyle(k+1-y_{j})G(\lfloor y_{j}\rfloor)=(k+1-y_{j})\frac{d^{\lfloor
y_{j}\rfloor}-1}{d-1}$ $\displaystyle\leq$
$\displaystyle(k+1-y_{j})\frac{d^{y_{j}}-1}{d-1}.$

###### Claim 0

For $d\geq 3$ and $0\leq y_{j}<k$,
$\bar{f}_{j}(y_{j})=(k+1-y_{j})\cdot\frac{d^{y_{j}}-1}{d-1}$ monotone
increases with respect to $y_{j}$.

To prove the above claim, it suffices to calculate the derivative of
$\bar{f}_{j}(y_{j})$, and we omit the details. By Claim  ‣ 3.1,
$f_{j}(y_{j})\leq\bar{f}_{j}(y_{j})\leq G(k)$ for any $0\leq y_{j}<k$. Thus,

$\displaystyle u^{\prime}_{r}(\Delta_{g^{\prime}})$ $\displaystyle\geq$
$\displaystyle\dfrac{x_{\min}\pi_{0}-x_{r}-\sum_{j\neq
g^{\prime}}(x_{r}-s_{r}(x_{r})_{j})\Delta_{j}}{(\pi_{0}+\Delta)^{2}}$
$\displaystyle\geq$
$\displaystyle\dfrac{x_{\min}\pi_{0}-x_{r}-G(k)(d-1)x_{\min}}{(\pi_{0}+\Delta)^{2}}$
$\displaystyle\geq$
$\displaystyle\dfrac{x_{\min}(\pi_{0}-k-1-G(k)(d-1))}{(\pi_{0}+\Delta)^{2}}\geq
0.$

The last inequality is because $\pi_{0}\geq dG(k)+2k-1$ and $k\geq 2$.

In conclusion, if $g$ receives the information with remaining reward at least
$x_{\min}$, $u^{\prime}_{r}(\Delta_{g^{\prime}})>0$, which means $r$’s utility
is maximized when $g$ plays FP strategy, which finishes the proof. ∎

Lemma 2 implies that, if the information is known to a sufficiently large
number of players, for an arbitrary player, her utility is maximized when all
her descendants play FP strategies. Next we show that the other direction of
Lemma 2 also holds: for an arbitrary player, if the information is aware to a
sufficiently large number of players and all her descendants play FP
strategies, her utility is maximized when she plays FP strategy.

Fixing a tree $T$, let $i$ be some player in depth $j$ of $T$. Assume the
remaining reward $i$ has received is $kx_{\min}\leq x_{i}<(k+1)x_{\min}$ for
some $0\leq k\leq H-j-1$, and all her descendants play FP strategies. Given
any strategy $s_{i}(x_{i})$, define

$s^{\prime}_{i}(x_{i})=\left(\lfloor\frac{s_{i}(x_{i})_{1}}{x_{\min}}\rfloor\cdot
x_{\min},\cdots,\lfloor\frac{s_{i}(x_{i})_{d}}{x_{\min}}\rfloor\cdot
x_{\min}\right).$

Note that given her descendants playing FP strategies, $s^{\prime}_{i}(x_{i})$
brings $i$ utility at least as much as $s_{i}(x_{i})$ does. The set of all
possible $s^{\prime}_{i}(x_{i})$ is called reasonable strategies. Thus given
all $i$’s descendants playing FP strategies, to study $i$’s best response, it
suffices to consider reasonable strategies. For convenience, we use
$(d_{0},d_{1},\cdots,d_{k})$ to represent a reasonable strategy, where
$d_{l}\in[d]$ means $i$ selects $d_{l}$ children to propagate to next $l$
depths by leaving $(l-1)x_{\min}$ to these children, and $d_{0}$ means $i$
selects $d_{0}$ children to not propagate. Thus $\sum_{l=0}^{k}d_{l}=d$. Note
that it does not matter which $d_{l}$ children are selected since all $i$’s
children are symmetric. In the following, we use
$u_{i}((d_{0},d_{1},\cdots,d_{k});x_{i})$ to denote $i$’s utility when she
receives reward $x_{i}$ and her action is $(d_{0},d_{1},\cdots,d_{k})$, given
all other players adopting FP strategies.

###### Lemma 3

Consider the sub-game on a single subtree $T$, where $r$ is the root player.
Assume $r$ receives the information with reward $x_{r}$ and $k\cdot
x_{\min}\leq x_{r}<(k+1)\cdot x_{\min}$ for some $k\geq 1$. If $d\geq 3$,
$\pi_{0}\geq d\cdot G(k)+2k-1$, and all $r$’s descendants adopting FP
strategies, for any reasonable strategy $(d_{0},d_{1},\cdots,d_{k})$, $r$’s
utility increases by moving a unit from $0\leq l<k$ to $l+1$. Formally, if for
some $0\leq l<k$ such that $d_{l}>0$, then

$u_{r}((d_{0},\cdots,d_{l},\cdots,d_{k});x_{r})<u_{r}((d_{0},\cdots,d_{l}-1,d_{l+1}+1,\cdots,d_{k});x_{r}).$

###### Proof

To simplify our notions, we ignore the index $r$ for the root player, and let
$x$ be the propagation reward that the root receives. When $kx_{\min}\leq
x<(k+1)x_{\min}$ and $k\geq 1$, the root is able to leave a proper reward to
the players in depth 1 so that the information can be reached to at most depth
$k$. When it is convenient, we write $x=(k+\epsilon)x_{\min}$ and
$0\leq\epsilon<1$. Given any strategy $(d_{0},\cdots,d_{k})$ such that
$\sum_{j=0}^{k}d_{j}=d$ and $d_{i}>0$ for some $0\leq i<k$, we compare
$u((d_{0},\cdots,d_{l},\cdots,d_{k});x)$ and
$u((d_{0},\cdots,d_{l}-1,d_{l+1}+1,\cdots,d_{k});x)$.

If $l=0$, Lemma 3 degenerates to Lemma 1 restricted to trees, which is
trivially true. Thus in the following, we assume $l\geq 1$.

If $x_{\min}\leq x<2x_{\min}$, the remaining reward a player in depth 1
receives is always smaller than $x_{\min}$; that is there is no way the
information can reach depth 2. Let $1<d_{0}\leq d$ and $d_{1}=d-d_{0}$. It is
not hard to check that by notifying one more player,

$u((d_{0},d_{1});x)=\frac{(d_{1}+1)x}{\pi_{0}+1+d_{1}}<\frac{(d_{1}+2)x}{\pi_{0}+1+d_{1}+1}=u((d_{0}-1,d_{1}+1);x),$

where the inequality is because $\pi_{0}\geq F(1)>2$.

Next we assume $k\geq 2$. Denote

$Q=x+\sum_{j=1}^{k}d_{j}G(j)(x-(j-1)x_{\min}),$

and

$W=\pi_{0}+1+\sum_{j=1}^{k}d_{j}G(j).$

Thus the utility for $(d_{0},\cdots,d_{l},\cdots,d_{k})$ is

$U=u((d_{1},\cdots,d_{k});x)=\frac{Q}{W},$

and the utility for $(d_{0},\cdots,d_{l}-1,d_{l+1}+1,\cdots,d_{k})$ is

$\displaystyle U^{\prime}$
$\displaystyle=u((d_{0},\cdots,d_{l}-1,d_{l+1}+1,\cdots,d_{k});x)$
$\displaystyle=\frac{Q+G(i+1)(x-ix_{\min})-G(i)(x-(i-1)x_{\min}))}{W+G(i+1)-G(i)}$
$\displaystyle=\frac{Q+xd^{i}-x_{\min}(iG(i+1)-(i-1)G(i))}{W+d^{i}}.$

To show $U^{\prime}>U$, it equivalent to show

$\frac{xd^{i}-x_{\min}(iG(i+1)-(i-1)G(i))}{d^{i}}>\frac{Q}{W},$

or

$W\left(xd^{i}-x_{\min}\left(iG(i+1)-(i-1)G(i)\right)\right)>d^{i}Q.$

Note that

$\displaystyle W\left(xd^{i}-x_{\min}(iG(i+1)-(i-1)G(i))\right)$
$\displaystyle=$ $\displaystyle
W\left(xd^{i}-x_{\min}(G(i+1)-(i-1)d^{i})\right)$ $\displaystyle>$
$\displaystyle
W\left(kx_{\min}d^{i}-x_{\min}(\frac{d^{i+1}}{d-1}-(i-1)d^{i})\right)$
$\displaystyle=$ $\displaystyle
Wx_{\min}d^{i}\left(k+\epsilon-\frac{d}{d-1}-(i-1)\right)$ $\displaystyle\geq$
$\displaystyle(\frac{1}{2}+\epsilon)Wx_{\min}d^{i},$

where the first inequality is because $x=(k+\epsilon)x_{\min}$ and

$G(i+1)=\sum_{j=0}^{i+1}d^{j}=\frac{d^{i+1}-1}{d-1}<\frac{d^{i+1}}{d-1};$

the second inequality is because $k\geq i+1$ and $d\geq 3$. Thus to show
Theorem 3, it suffices to show $(1+2\epsilon)Wx_{\min}>2Q$.

###### Claim 0

$(1+2\epsilon)Wx_{\min}>2Q$.

To prove Claim  ‣ 3.1, we note that

$\displaystyle(1+2\epsilon)W-\frac{2Q}{x_{\min}}$ $\displaystyle=$
$\displaystyle(1+2\epsilon)\left(\pi_{0}+1+\sum_{j=1}^{k}d_{j}G(j)\right)-2\left(k+\epsilon+\sum_{j=1}^{k}d_{j}G(j)(k+\epsilon-j+1)\right)$
$\displaystyle\geq$
$\displaystyle\pi_{0}-2k+1-\sum_{i=1}^{k}d_{i}G(i)(2k-2i+1)$ $\displaystyle>$
$\displaystyle\pi_{0}+1-2k-dG(k)\geq 0.$

The first equation is because $x=(k+\epsilon)x_{\min}$; the first inequality
is because $\epsilon\geq 0$; the second inequality is because the following
Claim  ‣ 3.1; and the last inequality is because $\pi_{0}\geq dG(k)+2k-1$.

###### Claim 0

$\sum_{i=1}^{k}d_{i}G(i)(2k-2i+1)<dG(k)$.

We prove Claim  ‣ 3.1 in the appendix. ∎

Lemma 3 is essentially a generalization of Lemma 1 to tree structures, which
means if the information is already known to a sufficiently large number of
players, it is always beneficial for a player to make the information reach
players in one deeper level. By induction, we have the following corollary.

###### Corollary 1

Consider the sub-game on a single subtree $T$, where $r$ is the root player.
Assume $r$ receives the information with reward $x_{r}$ and $k\cdot
x_{\min}\leq x_{r}<(k+1)\cdot x_{\min}$ for some $k\geq 1$. If $d\geq 3$,
$\pi_{0}\geq dG(k)+2k-1$, and all $r$’s descendants adopt FP strategies, $r$’s
(unique) best strategy is $((k-1)\cdot x_{\min},\cdots,(k-1)\cdot x_{\min})$.

Note that Lemmas 2, 3 and Corollary 1 do not only hold for the root players,
but also for any player in a subtree $T$.

###  3.2 Main Results

Given Lemma 2 and Corollary 1, it is not hard to verify that FP strategy
profile ${\bf s}^{*}$ is a Nash equilibrium, as for each fixed tree, the
information is known to the other $f-1$ trees, and thus the number of aware
players is at least

$(f-1)G(H+1)\geq(d-1)G(H+1)\geq(d+1)G(H).$

However, ${\bf s}^{*}$ is not the unique Nash equilibrium. Consider the
following strategy profile. Denote by 0 the root player of an arbitrary
subtree $T$ and by $1,\cdots,d$ her children. Consider the strategy profile
${\bf s}^{\prime}$: for all $x\geq x_{\min}$, $s_{0}(x)=(0,\cdots,0)$ and
$s_{i}(x)=(\bot,\cdots,\bot)$ for all $i\in\\{1,\cdots,d\\}$; all the other
players in $T$ and all players not in $T$ play arbitrary strategies. That is
by notifying the players in depth 1, the root 0 withholds the complete reward
no matter how much the initial reward is, and the players in depth 1 do not
propagate the information at all no matter how much reward the root player
leaves for them. Next, we claim strategy profile ${\bf s}^{\prime}$ is a Nash
equilibrium and for simplicity, we assume $d\geq 4$. First, for each player
not in tree $T$, as there are at least $f-2$ other trees play FP,
$\pi_{0}\geq(f-2)G(H+1)>dG(k)+2k-1$ for any $k\geq 0$. By Corollary 1, the
best response of them is FP, thus all these players will not deviate. Second,
the root player 0 does not deviate, as all her children do not propagate the
information and her best strategy is to withhold all the reward; Finally, no
player in $\\{1,\cdots,d\\}$ deviates, as the remaining reward for the
information is 0. We can observe that in ${\bf s}^{\prime}$, all
$\\{0,1,\cdots,d\\}$ played “bad” strategies. By deviating to FP strategies
simultaneously, all of them can improve their utilities, which means ${\bf
s}^{*}$ is more stable equilibrium than ${\bf s}^{\prime}$.

We next define connected coalition-proof Nash equilibria on graphs, which are
stronger than an arbitrary Nash equilibrium. Let $\Gamma=(N,{\bf S},u)$ be any
game with $n$ players, and for any $C\subseteq N$, denote ${\bf
S}_{C}=\times_{i\in C}S_{i}$. Let $G=(N,E)$ be a graph defined on players with
$(i,j)\in E$ meaning players $i$ and $j$ can communicate with each other
directly. A Nash equilibrium ${\bf s}\in{\bf S}$ is called connected
coalition-proof on $G$ if there is no coalition $C\subseteq N$ with the
induced subgraph of $C$ on $G$ being connected such that by deviating to ${\bf
s}^{\prime}_{C}$, $u_{i}({\bf s}^{\prime}_{C},{\bf s}_{N\setminus C})\geq
u_{i}({\bf s})$ for any $i\in C$ and there is one $j\in C$ such that
$u_{j}({\bf s}^{\prime}_{C},{\bf s}_{N\setminus C})>u_{j}({\bf s})$. It is
easy to see that any strong Nash equilibrium is connected coalition-proof on a
complete graph and any Nash equilibrium is connected coalition-proof on an
empty graph. As pointed out by Myerson in [22], the requirement of connected
coalition-proof is practical as the players in any deviating coalition should
be able to communicate.

###### Theorem 3.1

For $f\geq d\geq 3$, full propagation strategy profile ${\bf s}^{*}$ is a
connected coalition-proof Nash equilibrium on $\mathcal{G}$.

###### Proof

For any coalition $C\subseteq N$, denote by $\mathcal{G}(C)$ the induced
subgraph of $C$ in $\mathcal{G}$. We first observe that $\mathcal{G}(C)$ being
connected implies $\mathcal{G}(C)$ being a subtree in some $T$. Then to prove
the theorem, it suffices to show for any deviation ${\bf s}^{\prime}_{C}$ from
${\bf s}^{*}_{C}$, there is at least one player whose utility is smaller than
the case when all of them play FP. Let $r$ be the root of $\mathcal{G}(C)$.
Without loss of generality, we reorder the players in $C\setminus\\{r\\}$ by
$\\{1,2,\cdots,c\\}$ where $c=|C\setminus\\{r\\}|$.

Given the other players not in $T$ play FP strategies, the information will be
known to at least $\pi_{0}$ players, and when $d\geq 3$, by Equation 2,

$\pi_{0}\geq(f-1)G(H+1)>dG(H)+2H-1.$

If $r$ is in depth $H-1$, all players in $C\setminus\\{r\\}$ are dummy, whose
actions do not affect $r$’s utility. Thus by Lemma 1, any deviation from ${\bf
s}^{*}_{C}$ will strictly decreases $r$’s utility. In the following, we assume
$r$ is above depth $H-1$.

Since $\pi_{0}\geq dG(H)+2H-1$, by Lemma 2,

$u_{r}({\bf s}^{\prime}_{C},{\bf s}^{*}_{N\setminus C})\leq u_{r}({\bf
s}^{\prime}_{C\setminus\\{1\\}},{\bf s}^{*}_{\\{1\\}\cup(N\setminus C)}).$

That is by changing player $1$’s strategy to FP, $r$’s utility can only
increase. We continue this procedure for player $i=2,\cdots,c$ by changing her
strategy from $s_{i}$ to $s^{*}_{i}$, and we have

$\displaystyle u_{r}({\bf s}^{\prime}_{\\{r,i,\cdots,c\\}},{\bf
s}^{*}_{\\{1,\cdots,i-1\\}\cup N\setminus C})\leq u_{r}({\bf
s}^{\prime}_{\\{r,i+1,\cdots,c\\}},{\bf s}^{*}_{\\{1,\cdots,i\\}\cup
N\setminus C}).$

Eventually, we obtain

$u_{r}({\bf s}^{\prime}_{C},{\bf s}^{*}_{N\setminus C})\leq u_{r}({\bf
s}^{\prime}_{r},{\bf s}^{*}_{N\setminus\\{r\\}}).$

By Corollary 1, when all $i$’s descendants play FP strategies,

$u_{r}({\bf s}^{\prime}_{r},{\bf s}^{*}_{N\setminus\\{r\\}})<u_{r}({\bf
s}^{*}).$

Thus, $u_{r}({\bf s}^{\prime}_{C},{\bf s}^{*}_{N\setminus C})<u_{r}({\bf
s}^{*})$, which finishes the proof. ∎

By Theorem 3.1, we have shown that ${\bf s}^{*}$ is more stable than an
ordinary Nash equilibrium. But ${\bf s}^{*}$ is not a strong Nash equilibrium,
because all the $f$ root players can form a deviating coalition such that none
of them propagates the information, which brings each root player utility
$\frac{1}{f}$. However, as we have seen in the introduction, no propagation of
these $f$ players is not an equilibrium.

Next we show that ${\bf s}^{*}$ survives in any possible order of elimination
of dominated strategies, and uniquely survives in an almost monotonic order of
elimination of dominated strategies, which surpasses the result in [3]. We
call an elimination order monotonic if for any player $i$ and any two
eliminated strategies $s_{i}$ and $s^{\prime}_{i}$,
$\min_{j}s_{i}(x^{*}_{i})_{j}<\min_{j}s^{\prime}_{i}(x^{*}_{i})_{j}$ implies
that $s_{i}$ is not eliminated after $s^{\prime}_{i}$, where $x^{*}_{i}$ is
the minimum $x_{i}$ such that
$\min_{j}s_{i}(x_{i})_{j}\neq\min_{j}s^{\prime}_{i}(x_{i})_{j}$. Assume
$\bot<0$. We call an elimination order almost monotonic if the condition is
relaxed to
$s_{i}(x^{*}_{i})_{j^{*}}<s^{\prime}_{i}(x^{*}_{i})_{j^{*}}+x_{\min}$ implying
$s_{i}$ is not eliminated after $s^{\prime}_{j}$.

###### Theorem 3.2

For $f>d\geq 3$, ${\bf s}^{*}$ survives in any possible order of elimination
of dominated strategies. Moreover, ${\bf s}^{*}$ is the unique Nash
equilibrium survives in an almost monotonic order of elimination of dominated
strategies.

Theorem 3.2 is proved in the appendix. Note that all our results in this
section hold as long as each player has at least $d$ children, where $d\geq
3$. Actually, similar results also hold for the case of $d=1,2$, but the
players may withhold multiples of $x_{\min}$.

#### Remark.

Theorem 3.2 is similar to the result in [3]. They designed a hybrid rewarding
scheme, which combines two nearly-uniform algorithms, that is Sybil-proof.
Each player in a nearly-uniform algorithm A nearly-uniform algorithm specifies
a maximal length $H$ of rewarding path and rewards winning player in a chain
of length $h$ a reward of $1+\beta\cdot(H-h+1)$. All the players between the
sender and the winner are rewarded $\beta$. Though $\beta$ plays a similar
role with our $x_{\min}$, there are several differences. One of the main
differences is that, by the design of the free market, the players can
arbitrarily decide her own charge as long as the charge is at least of
$x_{\min}$, which is not restricted to be integer multiples of $x_{\min}$
(i.e., Sybil copies). A second difference is that we do not combine two
different schemes. The advantage of the free market design is that the system
does not need to (carefully) specify who gets how much, and the players
themselves are already motivated to maximally propagate the information, which
is also the main take-home message of the current paper.

##  4 A Class of Non-tree Networks

In this section, we investigate the extent to which our results for trees can
be extended to general networks. In a non-tree network, a player may get the
information from multiple neighbours and she will claim the one who leaves the
highest reward to her, where tie is broken arbitrarily but consistently. Again
let $\mathcal{G}=(V,E)$ be an arbitrary network and $s\in V$ be the initial
sender. We first introduce the notions of good friends and best friends. For
two players $i$ and $j$, $i$ is $j$’s best friend if (1) $i$ and $j$ are
connected, and (2) every shortest path from sender $s$ to $j$ passes $i$. If
$i$ is $j$’s best friend, then $j$ is called $i$’s good friend. Note that each
player can have at most one best friend but multiple good friends. For
example, in Fig 2(a), $a,b$, and $d$ are the best friends of $c,e$, and $g$,
respectively. However, $d$ and $f$ do not have any best friend as each of them
has two disjoint shortest paths to $s$. Let $\mathcal{T}=(V,E^{\prime})$ be
the subgraph of $\mathcal{G}$, where $E^{\prime}\subseteq E$ and $(i,j)\in
E^{\prime}$ if $i$ is $j$’s good or best friend. Note that $\mathcal{T}$ is a
spanning forest of $\mathcal{G}$, and the root of each tree is either $s$ or a
player who does not have best friend. As an example, the solid lines in Fig
2(a) form a good-friendship graph.

(a) Good-Friendship Graph $\mathcal{T}$.

(b) Information Propagation Tree $T^{*}$.

Figure 2: Illustration of Good-Friendship Graph and Information Propagation
Tree.

Next we prove that if every player has at least three good friends, then full
propagation is a Nash equilibrium. Moreover, this equilibrium is robust to
collective deviations of good friends. Note that the case of $d$-ary tree with
$d\geq 3$ in Section 3 is a special case of this situation where
$\mathcal{G}=\mathcal{T}$.

###### Theorem 4.1

If every player has at least 3 good friends, then FP strategies ${\bf s}^{*}$
is a Nash equilibrium. Moreover, it is connected coalition-proof on
$\mathcal{T}$.

###### Proof

If every player has at least 3 good friends, then every node in $\mathcal{T}$
has at least 3 children in its corresponding tree. Let $T^{*}$ be the
corresponding information propagation tree under ${\bf s}^{*}$, where $i$ is
connected to $j$ if $j$ claims $i$ as the ancestor. Essentially, $T^{*}$
connects all the trees in $\mathcal{T}$ as shown in Fig 2(b). We first prove
${\bf s}^{*}$ is a Nash equilibrium. Suppose, for the sake of contradiction,
some player $i$ wants to deviate from ${\bf s}^{*}$. We partition $i$’s
neighbours into two sets $S_{1}$ and $S_{2}$, where $S_{1}$ contains the
players whose distance to $s$ is at most $i$’s distance to $s$, and $S_{2}$
contains the players whose distance to $s$ is longer than $i$’s distance to
$s$. Note that player $i$’s action does not affect players in $S_{1}$ and
their descendants in $T^{*}$. We further partition $S_{2}$ into $S_{21}$ and
$S_{22}$, where $S_{21}$ contains all $i$’s good friends and
$S_{22}=S_{2}\setminus S_{21}$. If $i$ does not fully propagate to players in
$S_{22}$, $i$ loses all the referring utility from $S_{22}$ because they can
still be informed via other paths, which decreases $i$’s utility. By the
condition of the lemma, $|S_{21}|\geq 3$, and only players in $S_{21}$ are
connected with $i$ in $\mathcal{T}$. Moreover, under ${\bf s}^{*}$, $i$ will
be claimed as the ancestor with higher priority by all her descendants in
$\mathcal{T}$. Then our problem degenerates to the case of trees in the
previous section, and by Lemma 3, $i$’s utility is maximized by FP, which
means ${\bf s}^{*}$ is a Nash equilibrium. Moreover, the reason why ${\bf
s}^{*}$ is connected coalition-proof on $\mathcal{T}$ is in the same with
Theorem 3.1: Any connected subgraph in $\mathcal{T}$ forms a subtree with a
root player $i$, whose utility decreases by deviating from ${\bf s}^{*}$. ∎

Here we note that ${\bf s}^{*}$ may not be connected coalition-proof on the
original network $\mathcal{G}$. To see this, if all senders’ direct neighbours
are connected with each other, they can form a connected coalition and do not
propagate the information to others, which brings each of them higher utility
than full propagation.

##  5 Experiments

Finally, we conduct experiments to confirm the validity of the free market
design in random networks. We first introduce the parameters in our
experiments. Given a parameter $d$, there are $n$ players and each player is
randomly connected to $\frac{d}{2}$ other players, so that the expected degree
of each player is $d$. We study the utility of a fixed player and the sender
is randomly selected from the other players. Fix all other players’ strategies
to be full propagation. Set the initial reward to $1$ and
$x_{\min}=\frac{1}{H}$. In each experiment, we randomly generate $K$ networks.
For simplicity, we only consider the strategies that withhold integral
multiples of $x_{\min}$, and calculate the expected utility of the studied
player for each strategy.

Figure 3: When all players have the same expected degree.

In Fig 3, we set $n=1000$ and $H=6$. For each $d=6/10/14$, we randomly
construct $K=100$ networks. We observe that full propagation (by withholding
$x_{\min}$) brings a significantly higher utility on average than the other
strategies (by withholding $kx_{\min}$ for $k>1$). Then we revise the
experiments by making the studied player more powerful or less powerful than
the others, where a powerful player has higher degree than the others and a
powerless player has lower degree than the others. In Fig 4, the degree for
the powerful player is set to $2d$ and for the powerless player it is set to
be $\frac{d}{2}$. Similarly, we observe that in both cases, full propagation
brings significantly higher utility than the other strategies.

Figure 4: When the player is powerful or powerless.

Note that full propagation is not always optimal. If a player $i$ exclusively
controls some players (i.e., the sender’s information can only be reached to
them via $i$) and these players form a complete graph, the optimal local
strategy for $i$ is to leave 0 to all of them instead of full propagation.
Thus, if the network structure is known to players, the players can compute
their optimal propagating strategies, which may not be full propagation.
However, such “bad” networks barely happen in random networks and never happen
in reality. To further avoid security threats, such as in a blockchain
protocol, the players can be randomly re-connected periodically so that it is
not beneficial for players to spend effort on learning network structures any
more.

##  6 Conclusion and Future Directions

In this work, we design a free market with lotteries to incentivize players to
maximally propagate information to their friends. For trees and a large class
of non-tree networks, we prove that full propagation is robust against
connected coalitions of players. Particularly, full propagation in tree
networks uniquely survives in an interval-based monotone iterative elimination
of dominated strategies. For future directions, from a theoretical
perspective, it is intriguing to analyze players’ behaviours in the free
market within arbitrary or random networks and consider non-uniform lotteries.
For example, if the property of every node having 3 good friends holds for
certain random graphs, then Theorem 4.1 holds for such graphs as well. In
addition, in the current market only the final winner and the players on the
propagation path reaching her get rewarded. It would be interesting to see if
there is a way to select and reward more than one winners and corresponding
propagation paths. In a blockchain, this could correspond to multiple block
proposers whose blocks are not eventually finalized, and may help reducing the
players’ risk, so as to encourage more to participate in a risk-avert model.
Moreover, it is interesting and challenging to design new reward schemes to
incentivize information propagation in more complex networks. Finally, from a
practical perspective, experiments on synthetic and real-world data for
complex networks may reveal important insights on the behavior of a free
market in such networks, further enabling market design for them.

## Appendix

##  Appendix 0.A Missing Proofs

###  0.A.1 Proof of Lemma 1

Lemma 1 (restated). For any player $i$, let ${\bf s}_{-i}$ be $-i$’s strategy
profile such that the remaining reward $x_{i}$ to $i$ is at least $x_{\min}$.
Let $s_{i}(x_{i})=(z_{1},\cdots,z_{j},\cdots,z_{|NB_{i}|})$ be a strategy with
$z_{j}=\bot$ for some $j$ and
$s^{\prime}_{i}(x_{i})=(z_{1},\cdots,z^{\prime}_{j},\cdots,z_{|NB_{i}|})$ be a
new strategy by changing $j$’s action from $\bot$ to $0$. Then
$u_{i}(s_{i},{\bf s}_{-i})<u_{i}(s^{\prime}_{i},{\bf s}_{-i})$.

###### Proof

We first consider player $i$’s utility under strategy profile $(s_{i},{\bf
s}_{-i})$. For $l\in[|NB_{i}|]$, let $\Delta_{l}\geq 0$ be the number of
players $i$ successfully refers through neighbour $l$ and $\pi_{0}$ be the
total number of players who are aware of the information. Then $i$’s utility
is

$u_{i}(s_{i},{\bf
s}_{-i})=\frac{x_{i}+\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}}{\pi_{0}}.$

Now consider $i$’s utility under strategy profile $(s^{\prime}_{i},{\bf
s}_{-i})$. By changing $z_{j}=\bot$ to $z_{j}=0$, $j$ may or may not claim $i$
as her ancestor. If not, it means that $j$ is already aware of the
information, but someone else leaves a higher utility for her, thus $i$’s
utility does not change, i.e., $u_{i}(s^{\prime}_{i},{\bf
s}_{-i})=u_{i}(s_{i},{\bf s}_{-i})$.

If $j$ claims $i$ as her ancestor, there are two cases: (1) $j$ is already
aware of the information, but $i$ is on the shortest path or the tie breaking
rule is in favour of $j$, thus $s^{\prime}_{i}$ does not increase $\pi_{0}$;
(2) $j$ is not aware of the information, thus $s^{\prime}_{i}$ increase
$\pi_{0}$ by 1. In any case, $i$’s utility is at least

$u_{i}(s^{\prime}_{i},{\bf
s}_{-i})=\frac{2x_{i}+\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}}{\pi_{0}+1}.$

To show $u_{i}(s^{\prime}_{i},{\bf s}_{-i})\geq u_{i}(s_{i},{\bf s}_{-i})$, it
suffices to see the following inequalities.

$\displaystyle\frac{2x_{i}+\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}}{\pi_{0}+1}-\frac{x_{i}+\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}}{\pi_{0}}$
$\displaystyle=$
$\displaystyle\frac{1}{\pi_{0}(\pi_{0}+1)}\bigg{(}2\pi_{0}x_{i}+\pi_{0}\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}$
$\displaystyle-(\pi_{0}+1)x_{i}-(\pi_{0}+1)\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}\bigg{)}$
$\displaystyle=$
$\displaystyle\frac{(\pi_{0}-1)x_{i}-\sum_{z_{l}\neq\bot}(x_{i}-z_{l})\Delta_{l}}{\pi_{0}(\pi_{0}+1)}$
$\displaystyle>$
$\displaystyle\frac{(\pi_{0}-1)x_{i}-(\pi_{0}-1)x_{i}}{\pi_{0}(\pi_{0}+1)}=0.$

The inequality above is because $\sum_{l}\Delta_{l}<\pi_{0}-1$ and
$x_{i}-z_{l}\leq x_{i}$. Thus $u_{i}(s^{\prime}_{i},{\bf s}_{-i})\geq
u_{i}(s_{i},{\bf s}_{-i})$ and we complete the proof.∎

###  0.A.2 Proof of Claim  ‣ 3.1

Claim  ‣ 3.1 (restated). $\sum_{i=1}^{k}d_{i}G(i)(2k-2i+1)<dG(k)$.

###### Proof

Let

$\displaystyle f(y)$ $\displaystyle=$ $\displaystyle G(\lfloor
y\rfloor)(2k-2y+1)=\frac{d^{\lfloor y\rfloor}-1}{d-1}(2k-2y+1)$
$\displaystyle\leq$ $\displaystyle\frac{d^{y}-1}{d-1}(2k-2y+1)=\bar{f}(y).$

Note that as $\sum_{i=1}^{k}d_{i}=d$, to prove the claim, we only need to show
$\bar{f}(y)<G(k)=\bar{f}(k)$. It is not hard to see when $y\leq k-1$ and
$d\geq 3$,

$\bar{f}^{\prime}(y)=\frac{d^{y}}{d-1}\left((2k-2y+1)\ln{d}-2\right)+\frac{2}{d-1}>0.$

That is $\bar{f}(y)<\bar{f}(k-1)$ for all $y<k-1$. Then we are left to compare
$\bar{f}(k)$ and $\bar{f}(k-1)$,

$\bar{f}(k)=\frac{d^{k}-1}{d-1}>\frac{d\cdot d^{k-1}-3}{d-1}\geq
3\frac{d^{k-1}-1}{d-1}=\bar{f}(k-1),$

where the first inequality is also because of $d\geq 3$. This finishes the
proof of Claim  ‣ 3.1. ∎

###  0.A.3 Proof of Theorem 3.2

Theorem 3.2 (restated). For $f>d\geq 3$, ${\bf s}^{*}$ survives in any
possible order of elimination of dominated strategies. Moreover, ${\bf s}^{*}$
is the unique Nash equilibrium survives in an almost monotonic order of
elimination of dominated strategies.

###### Proof

We prove the first part via contradiction. For any order of elimination of
dominated strategies, consider the first time that some player $i$’s FP
strategy $s_{i}^{*}$ is eliminated. Note that $s_{i}^{*}$ being dominated by
$s_{i}^{\prime}$ means for all ${\bf s}_{-i}$, $s_{i}^{\prime}$ brings utility
as least as much as $s_{i}^{*}$. Particularly, $u_{i}(s_{i}^{*},{\bf
s}_{-i}^{*})\leq u_{i}(s_{i}^{\prime},{\bf s}_{-i}^{*})$. However, given all
other players play FP strategies, the information will be known to least
$(f-1)G(H+1)$ players. Thus, by Corollary 1, $u_{i}(s_{i}^{*},{\bf
s}_{-i}^{*})>u_{i}(s_{i}^{\prime},{\bf s}_{-i}^{*})$, where we reach the
contradiction. Next, we prove the second part.

For every player $i$, when the reward $x_{i}$ is clear, we denote by
$s_{i}(x_{i})=(z_{1},\cdots,z_{d})$. If $x_{i}<x_{\min}$, it is not possible
for $i$ to propagate the information, and the unique action is
$s_{i}(x_{i})=(\bot,\cdots,\bot)$, thus we assume $x_{i}\geq x_{\min}$. In the
following, we explicitly give the elimination order of dominated strategies.

Let $\pi_{0}$ be the number of players who are aware of the information. As
all root players know the information, by default, $\pi_{0}\geq d+1$.

#### Round 1.

For any $x_{i}\geq x_{\min}$,

$\displaystyle
s_{i}(x_{i})=(z_{1},\cdots,0<z_{j}<x_{\min},\cdots,z_{d})\preceq
s^{\prime}_{i}(x_{i})=(z_{1},\cdots,0,\cdots,z_{d}).$

Note that leaving less than $x_{\min}$ to $j$, $j$ is not able to propagate
the information. That is for any ${\bf s}_{-i}$, under both strategy profiles
$(s_{i},{\bf s}_{-i})$ and $(s^{\prime}_{i},{\bf s}_{-i})$, the numbers of
aware players are the same. As $s^{\prime}_{i}$ potentially brings higher
referring utility, $u_{i}(s_{i},{\bf s}_{-i})\leq u_{i}(s^{\prime}_{i},{\bf
s}_{-i})$. Particularly, if ${\bf s}_{-i}$ is the one that $i$ receives
exactly $x_{i}$ from her parent111If $i$ is in depth 0, we consider $x_{i}$ as
the initial reward from the sender., $u_{i}(s_{i},{\bf
s}_{-i})<u_{i}(s^{\prime}_{i},{\bf s}_{-i})$. Thus $s_{i}(x_{i})\preceq
s^{\prime}_{i}(x_{i})$. Eliminate all such dominated strategies for all
players.

If $x_{\min}\leq x_{i}<2x_{\min}$, as $0\leq z_{j}\leq
x_{i}-x_{\min}<x_{\min}$ for all $j$, for any remaining strategy $s_{i}$,
$s_{i}(x_{i})=(0,\cdots,0)$. That is when the remaining reward to a player is
less than $2x_{\min}$, she will fully propagate the information.

As all root players are aware of the information and all of them will notify
the players in depth 1, after this round, for all possible strategy profiles,
$\pi_{0}\geq fG(2)\geq(d+1)G(2)$.

#### Round 2.

First, for any $x_{i}\geq 2x_{\min}$,

$\displaystyle s_{i}(x_{i})=(z_{1},\cdots,z_{j}=0,\cdots,z_{d})\preceq
s^{\prime}_{i}(x_{i})=(z_{1},\cdots,x_{\min},\cdots,z_{d}).$

This is because after the first round, all players who receives $x_{\min}$
will propagate the information to the next level, i.e. full propagation. By
Corollary 1 and the fact that $\pi_{0}\geq(d+1)G(2)>G(2)+3$,
$s_{i}(x_{i})\preceq s^{\prime}_{i}(x_{i})$. Eliminate all such dominated
strategies for all players.

By induction, we have the following.

#### Round $l>2$.

First, for any $x_{i}\geq lx_{\min}$ and $g\in\\{0,1,\cdots,l-2\\}$,

$\displaystyle s_{i}(x_{i})=(z_{1},\cdots,z_{j}=gx_{\min},\cdots,z_{d})\preceq
s^{\prime}_{i}(x_{i})=(z_{1},\cdots,(l-1)x_{\min},\cdots,z_{d}).$

To see why, note that after the first $l-1$ rounds, $\pi_{0}\geq
fG(l)\geq(d+1)G(l)>dG(l)+2l-1$ and if $j$ receives $(l-1)x_{\min}$, she and
her descendants fully propagate the information. By Corollary 1,
$s_{i}(x_{i})\preceq s^{\prime}_{i}(x_{i})$. Eliminate all such dominated
strategies for all players.

Second, for any $x_{i}\geq lx_{\min}$,

$\displaystyle s_{i}(x_{i})=(z_{1},\cdots,z_{j},\cdots,z_{d})\preceq
s^{\prime}_{i}(x_{i})=(z_{1},\cdots,(l-1)x_{\min},\cdots,z_{d}),$

where $(l-1)x_{\min}<z_{j}<lx_{\min}$. This is because after round $l-1$, if
$(l-1)x_{\min}\leq z_{j}<lx_{\min}$, by induction, child $j$’s only possible
action is $s_{j}(z_{j})=((l-2)x_{\min},\cdots,(l-2)x_{\min})$. Then leaving
$z_{j}$ to child $j$, $j$ will not notify more nodes than leaving
$(l-1)x_{\min}$ to him. That is for any ${\bf s}_{-i}$, under both strategy
profiles $(s_{i},{\bf s}_{-i})$ and $(s^{\prime}_{i},{\bf s}_{-i})$, the
numbers of aware players are the same. As $s^{\prime}_{i}$ potentially brings
higher referring utility, $u_{i}(s_{i},{\bf s}_{-i})\leq
u_{i}(s^{\prime}_{i},{\bf s}_{-i})$. Moreover, if ${\bf s}_{-i}$ is the one
such that $i$ receives exactly $x_{i}$ from her parent, $u_{i}(s_{i},{\bf
s}_{-i})<u_{i}(s^{\prime}_{i},{\bf s}_{-i})$. Thus $s_{i}(x_{i})\preceq
s^{\prime}_{i}(x_{i})$. Eliminate all such dominated strategies for all
players.

Note that if $lx_{\min}\leq x_{i}<(l+1)x_{\min}$, as $0\leq z_{j}\leq
x_{i}-x_{\min}<lx_{\min}$ for any $j$, for any remaining strategy $s_{i}$
after the first $l$ rounds,
$s_{i}(x_{i})=((l-1)x_{\min},\cdots,(l-1)x_{\min})$. Combining with previous
rounds, when the remaining reward to a player is less than $(l+1)x_{\min}$,
she will fully propagate the information.

Moreover, after this round, all the players in depth $l+1$ are also aware of
the information, $\pi_{0}\geq fG(l+1)\geq(d+1)G(l+1)\geq dG(l+1)+2(l+1)-1$.

From above analysis, we observe that for $kx_{\min}\leq x_{i}<(k+1)x_{\min}$,
the only remaining strategy is
$s_{i}(x_{i})=((k-1)x_{\min},\cdots,(k+-1)x_{\min})$, i.e., full propagation.
Moreover, the elimination order of dominated strategies is almost monotonic. ∎

## References

  * [1] Abraham, I., Malkhi, D., Nayak, K., Ren, L., Spiegelman, A.: Solidus: An incentive-compatible cryptocurrency based on permissionless byzantine consensus (2016)
  * [2] Arcaute, E., Kirsch, A., Kumar, R., Liben-Nowell, D., Vassilvitskii, S.: On threshold behavior in query incentive networks. In: EC. pp. 66–74. ACM (2007)
  * [3] Babaioff, M., Dobzinski, S., Oren, S., Zohar, A.: On bitcoin and red balloons. In: EC. pp. 56–73. ACM (2012)
  * [4] Bernheim, B.D., Peleg, B., Whinston, M.D.: Coalition-proof nash equilibria i. concepts. Journal of economic theory 42(1), 1–12 (1987)
  * [5] Cebrián, M., Coviello, L., Vattani, A., Voulgaris, P.: Finding red balloons with split contracts: robustness to individuals’ selfishness. In: STOC. pp. 775–788. ACM (2012)
  * [6] Chen, B.B., Chan, M.C.: Mobicent: a credit-based incentive system for disruption tolerant network. In: INFOCOM. pp. 875–883. IEEE (2010)
  * [7] Chen, J., Gilad, Y.: A relay market for the algorand blockchain. Manuscript (2018)
  * [8] Chen, W., Wang, Y., Yu, D., Zhang, L.: Sybil-proof mechanisms in query incentive networks. In: EC. pp. 197–214. ACM (2013)
  * [9] Chen, X., Papadimitriou, C.H., Roughgarden, T.: An axiomatic approach to block rewards. In: AFT. pp. 124–131. ACM (2019)
  * [10] Cossío, F.J.M., Brigham, E., Sela, B., Katz, J.: Competing (semi-)selfish miners in bitcoin. In: AFT. pp. 89–109. ACM (2019)
  * [11] Douceur, J.R.: The sybil attack. In: IPTPS. Lecture Notes in Computer Science, vol. 2429, pp. 251–260. Springer (2002)
  * [12] Drucker, F., Fleischer, L.: Simpler sybil-proof mechanisms for multi-level marketing. In: EC. pp. 441–458. ACM (2012)
  * [13] Emek, Y., Karidi, R., Tennenholtz, M., Zohar, A.: Mechanisms for multi-level marketing. In: EC. pp. 209–218. ACM (2011)
  * [14] Ersoy, O., Erkin, Z., Lagendijk, R.L.: Decentralized incentive-compatible and sybil-proof transaction advertisement. In: MARBLE. pp. 151–165. Springer (2019)
  * [15] Ersoy, O., Ren, Z., Erkin, Z., Lagendijk, R.L.: Transaction propagation on permissionless blockchains: Incentive and routing mechanisms. In: CVCBT. pp. 20–30. IEEE (2018)
  * [16] Eyal, I., Sirer, E.G.: Majority is not enough: Bitcoin mining is vulnerable. In: Christin, N., Safavi-Naini, R. (eds.) Financial Cryptography and Data Security. pp. 436–454 (2014)
  * [17] Johnson, B., Laszka, A., Grossklags, J., Vasek, M., Moore, T.: Game-theoretic analysis of ddos attacks against bitcoin mining pools. In: International Conference on Financial Cryptography and Data Security. pp. 72–86 (2014)
  * [18] Kiayias, A., Koutsoupias, E., Kyropoulou, M., Tselekounis, Y.: Blockchain mining games. In: EC. pp. 365–382. ACM (2016)
  * [19] Kleinberg, J.M., Raghavan, P.: Query incentive networks. In: FOCS. pp. 132–141. IEEE Computer Society (2005)
  * [20] Koutsoupias, E., Lazos, P., Ogunlana, F., Serafino, P.: Blockchain mining games with pay forward. In: WWW. pp. 917–927. ACM (2019)
  * [21] Lewenberg, Y., Bachrach, Y., Sompolinsky, Y., Zohar, A., Rosenschein, J.S.: Bitcoin mining pools: A cooperative game theoretic analysis. In: AAMAS. pp. 919–927. ACM (2015)
  * [22] Myerson, R.B.: Graphs and cooperation in games. Math. Oper. Res. 2(3), 225–229 (1977)
  * [23] Nakamoto, S.: Bitcoin: A peer-to-peer electronic cash system (2008)
  * [24] Rosenfeld, M.: Analysis of bitcoin pooled mining reward systems. CoRR abs/1112.4980 (2011)
  * [25] Schrijvers, O., Bonneau, J., Boneh, D., Roughgarden, T.: Incentive compatibility of bitcoin mining pool reward functions. In: Financial Cryptography. Lecture Notes in Computer Science, vol. 9603, pp. 477–498. Springer (2016)
  * [26] Shi, H., Zhang, Y., Si, Z., Wang, L., Zhao, D.: Maximal information propagation with budgets. In: ECAI. Frontiers in Artificial Intelligence and Applications, vol. 325, pp. 211–218. IOS Press (2020)