Competition Alleviates Present Bias in Task Completion

The most striking result is that there are graphs where the cost ratio (the ratio of the optimal agent’s cost to the biased agent’s cost) is exponential in the size of the graph. In addition, all graphs with exponential cost ratio have a shared structure – they all have a large $n$-fan as a graph minor (and graphs without exponential cost ratio do not) (Kleinberg and Oren, 2014; Tang et al., 2017). So this structure encodes the worst-case behavior for present bias in the standard model (and we later show how competition is especially effective in this graph). An $n$-fan is pictured in Figure 2.

The exponential cost ratio demonstrates the severe harm caused by present bias. How, then, can designers of a task limit the negative effects of present bias? Kleinberg and Oren (2014) propose a model where a reward is given after finishing the task, and where the agent will abandon the task if at any point, they perceive the remaining cost to be higher than the reward. Unlike an optimal agent, a biased agent may abandon a task partway through. Figure 3 uses the gym membership example from earlier to show this. As a result, they give the task designer the power to arbitrarily delete vertices and edges, which can model deadlines, as Figure 4 shows. They then investigate the structure of minimally motivating subgraphs – the smallest subgraph where the agent completes the task, for some fixed reward. Follow-up work of Tang et al. (2017) shows that finding any motivating subgraph is NP-hard. Instead of deleting edges, Albers and Kraft (2019) consider the problem of spreading a fixed reward onto arbitrary vertices to motivate an agent, and find that this too is NP-hard (with a constrained budget). For other recent work involving present bias, see (Gravin et al., 2016; Albers and Kraft, 2017; Yan and Yong, 2019; Oren and Soker, 2019; Ma et al., 2019).

The above results all focus on accommodating present bias rather than alleviating it. By that, we mean that the approaches all focus on whether the agent can be convinced to complete the task – via edge deletion or reward dispersal – but not on guarding the agent from suboptimal behavior induced by their bias. Kleinberg et al. (2016) partially investigates the latter question in a model involving sophisticated agents, who plan around their present bias. They consider several types of commitment devices – tools by which sophisticated agents can constrain their future selves. However, these tools may require more powerful agents or designers and don’t necessarily make sense for naive agents. We take a different approach – we show that adding competition can simultaneously explain why present-biased agents may not perform exponentially poorly in “natural” games and guide task designers in encouraging biased agents towards optimal behavior.

In our model, a task is still represented by a directed, acyclic graph $G$, with a designated source $s$ and sink $t$. There are two naive present-biased agents, $A_{1}$ and $A_{2}$, both with bias $b$, who compete to get to $t$ first. The cost of a path is the sum of the weights along the path, and time is represented by the number of edges in the path, which we call the length of the path. In other words, each edge represents one unit of time. The first agent to get to $t$ gets a reward of $r$; ties are resolved by evenly splitting the reward. Recall that naive agents believe that they will behave optimally in the future. Thus, an agent currently at $u$ considers the cost to reach the target $t$ to be $bc(u,v)$ plus the cost of the optimal path from $v$ to $t$ minus the reward of that path. More formally, let $\mathcal{P}(v\to t)$ denote the set of paths from $v\to t$ and let $P(s\to u)$ denote the path the agent has taken to $u$. Let $C_{n}(u,v)$ denote the remaining cost that the naive agent believes they will incur while at $u$ and planning to go to $v$. The subscript $n$ stands for “naive” (to help distinguish from $c(u,v)$, the cost of the edge $(u,v)$). Then:

where $c(P)=\sum_{e\in P}c(e)$ denotes the cost of path $P$ and $R_{A_{2}}(P)$ denotes the reward of taking path $P$ from $s$ to $t$. This reward depends on the path the other agent $A_{2}$ takes. Specifically, if $A_{2}$ takes a path of length $k$, and $P(s\to u)\cup(u,v)\cup P(v\to t)$ is a path of length $\ell$, then

We will often rewrite the second term in (1), for ease of notation, as $\min_{P_{v}}c(P_{v})-R_{A_{2}}(P_{s\to u,v\to t})$. We sometimes refer instead to the naive agent’s utility, which is the negation of this cost. Given this cost function, the naive agent chooses the successor of node $u$ via

See Figure 5 for an example.

We now consider how this model of competition might both explain the outcomes of natural games and inform task designers on how to elicit better behavior from biased agents. For a natural game, consider the classic example of two companies competing to expand into a new market. Both companies want to launch a similar product, and are thus considering the same task graph $G$. The companies are also present biased, since shareholders often prefer immediate profit maximization/loss minimization over long term optimal behavior. The first company to enter the market gains an insurmountable advantage, represented by reward $r$. If the companies both enter the market at the same time, they split the market share, each getting reward $r/2$. This arrangement can be modeled within our framework, and the competition between the companies should lead them to play a set of equilibrium strategies.

For a designed game, consider the problem of encouraging students to submit final projects before they are due. The instructor sets a deadline near the end of finals week to give students flexibility to complete the project when it best fits their schedule. The instructor also knows that (1) students tend to procrastinate and (2) trying to complete the final project in a few days is much more challenging than spreading it out. They would like to convince students to work on and possibly submit their assignments early, without changing the deadline (to allow flexibility for the students whom it suits best). One possible solution would be to give a small amount of extra credit to the first submission. How might they set this reward to encourage early submissions?

For another example of a designed game, consider a gym that enjoys increased enrollment at the start of the year. However, their new customers tend to not visit the gym frequently, and eventually cancel their membership. To remedy this, they try a new promotion, where new customers are offered free fitness classes, and the first customer(s) to attend 5 such classes gets a discount on their annual membership. How effective might such a scheme be at encouraging their new customers to regularly use their gym? Across these three examples, the intuition is that competition will alleviate the harms of present bias by driving agents towards optimal behavior.

We have introduced a model of competition for completing tasks along some graph. We warm up by analyzing these games absent present bias. Namely, we classify all Nash equilibria for an arbitrary task graph with unbiased agents. This analysis involves characterizing the set of paths which are the cheapest of a given length.

We then analyze these games when agents have equal present bias. We show that a very small reward induces a Nash equilibrium on the optimal path, for any graph with a dominant path. This is a substantial improvement over the exponential worst case cost ratio experienced without competition. We then discuss how time-inconsistency defeats the intuition that higher rewards cause agents to prefer quicker paths. Despite this complication, we provide an algorithm that, given arbitrary graph $G$ and path $Q$, determines the minimum reward needed to get a Nash equilibrium on $Q$, if possible.

Finally, we add an element of bias uncertainty to the model, by drawing agents’ biases iid from distribution $F$ and, for the $n$-fan, describe the relationship between $F$ and the reward required for a Bayes-Nash equilibrium on the optimal path. For a wide range of distributions, we find small rewards suffice to ensure that agents behave optimally (with high probability) in equilibrium. For the stronger goal of ensuring a constant expected cost ratio, it suffices to offer reward linear in $n$ when $F$ is not heavy-tailed; competition thus helps here as well.

We focus first on the $n$-fan since all graphs with exponential cost ratio for naive agents have a large $k$-fan as a graph minor (Kleinberg and Oren, 2014). For an example of the $n$-fan, refer back to Figure 2; note in particular that we assume the bias parameter $b>c>1$. We show that, with a very small amount of reward, competition encourages optimal behavior in naive agents (and further, we fully characterize all equilibria on the $n$-fan). To aid our proofs and discussions regarding the $n$-fan, we define $P_{i}$ as the path from $s$ to $t$ containing edge $(v_{i},t)$. Define $P_{0}$ as the direct path $(s,t)$.

The ability to enable optimal behavior with just a constant reward stands in striking contrast to the setting where agents can abandon the task at any time. With neither competition nor internal rewards, the designer would have to place an exponentially high reward on $t$ (i.e. $r\geq c^{n}$) for biased agents to finish the task.²²2However, with internal edge rewards, the designer could spend the same total reward to motivate two agents by directly adding a reward to the $(s,t)$ edge. This equivalence doesn’t hold in all graphs, as we show in the next section.

We now generalize our results to a larger category of graphs. To focus exclusively on the irrationality of present bias rather than the optimization problem of choosing between cheap, long paths and short, expensive paths, we focus on graphs with a dominant path – a cheapest path³³3There may be other cheapest paths which are longer. that is also the uniquely quickest path. This is the case in the $n$-fan. In this setting, the problem is trivial for unbiased agents; simply take this dominant path. But for biased agents, the problem is still interesting; as the example of the $n$-fan shows, they may take paths that are exponentially more costly than the dominant path. However, we prove that a small amount of competition and reward suffices to ensure the existence of a Nash equilibrium where both agents take the dominant path.

One might object to our claim that $r=2b\max_{e\in O}c(e)$ is “small”. To calibrate our expectations, notice that we can view this problem as an agent trying to pick between several options (i.e. paths), each with their own reward and cost structure. We want to convince the agent to pick one particular option – namely, the cheapest path. But it would be unreasonable to expect that a reward significantly smaller than the cost of any option would sway the agent’s decision. Our theorem above shows that a reward that is at most proportional to the cheapest option suffices; and in many cases the reward is only a fraction of the cost of the optimal path (e.g. when the optimal path has balanced cost among many edges).

For a point of comparison, even internal edge rewards (which required the same reward budget as competitive rewards for the $n$-fan) can require $O(n)$ times as much reward in some instances. To see the intuition, notice that internal edge rewards must be applied at every step where the agent might want to deviate. The agent also immediately “consumes” this reward; it doesn’t impact his future decision making. However, the competitive reward is “at stake” whenever the agent considers deviating; this reward can sway the agent’s behavior without being immediately consumed. For a concrete example, see Figure 6.

A very natural extension to this model would involve more than 2 agents competing. The winner takes all, and ties are split evenly among those who tied. However, this modification doesn’t change much when trying to get a Nash equilibrium on the dominant path. The only change is that if $m$ agents are competing, the reward needed is $O(m)$, as a single agent will get a $1/m$ fraction of the reward in a symmetric equilibrium. This is true because there is no way for any agent to beat the dominant path, and claim the entire $O(m)$ reward for themselves. So if the reward is scaled appropriately (i.e. in Theorem 3.2 set $r\geq mb\cdot\max_{e\in O}c(e)$), we will still guarantee a Nash equilibrium. Put another way, the per-agent reward needed for a Nash equilibrium on the dominant path does not change as the number of competitors varies.

The proof of Theorem 3.2 suggests the following algorithm for this problem. Start with a reward of $0$, and step along each vertex $u\in Q$, increasing the reward by just enough to ensure $A_{1}$ stays on $Q$ for one more step (assuming $A_{2}$ is taking $Q$). However, if $A_{1}$ wants to deviate onto a quicker/tied path at any point, return $\bot$; decreasing the reward would cause them to deviate earlier, and, intuitively, it seems that increasing the reward could not cause them to switch back to $Q$ from the quicker/tied path. After one pass, simply pass through again to ensure that the final reward doesn’t cause $A_{1}$ to deviate early on. The following lemma shows that this algorithm is tractable, by showing that we can compute the minimum reward required for $A_{1}$ to stay on $Q$ at any step (and determine whether $A_{1}$ wants to deviate onto a quicker path).

Unfortunately, while tractable, the approach described above does not yield a correct algorithm. This is because it relies implicitly on the following two properties, which formalize the intuition that increasing the reward causes agents to favor quicker paths.

Both properties are intuitive – if we increase the reward, that should motivate the agent to take a path that beats their opponent. And vice versa – increasing the reward shouldn’t cause them to shift onto a slower path or shift between equal length paths. But surprisingly, both properties are false, as the following examples demonstrate.