# Coevolution of game and network structure: The temptation increases the
cooperator density

Shao-Meng Qin  Institute of Theoretical Physics, Lanzhou University, Lanzhou
$730000$, China  Guo-Yong Zhang  Institute of Theoretical Physics, Lanzhou
University, Lanzhou $730000$, China  Yong Chen  Corresponding author. Email:
<EMAIL_ADDRESS>Institute of Theoretical Physics, Lanzhou University,
Lanzhou $730000$, China

###### Abstract

Most papers about the evolutionary game on graph assume the statistic network
structure. However, social interaction could change the relationship of
people. And the changing social structure will affect the people’s strategy
too. We build a coevolutionary model of prisoner’s dilemma game and network
structure to study the dynamic interaction in the real world. Based on the
asynchronous update rule and Monte Carlo simulation, we find that, when
players prefer to rewire their links to the richer, the cooperation density
will increase. The reason of it has been analyzed.

###### pacs:

02.50.Le, 05.50.+q, 64.60.Ht, 87.23.Ge

##  I introduction

Cooperation is a key aspect in the real world, ranging from biological systems
to human behavior nature1 ; nature2 . Therefore, people restore to the game
theory to study the emergency and maintenance of cooperation in biology,
psychology, computer science, and economics biology ; book1 ; book2 ; PR .
Especially, the prisoner’s dilemma game (PDG), has become a metaphor to
approach the emergency of cooperation and altruism behavior. In the tradition
PDG, each of two players chooses a strategy from cooperation ($C$) or
defection ($D$) simultaneously and gets payoff. They both receive $R$ upon
mutual $C$ and $P$ upon mutual $D$. A defector gets $T$ when it plays game
with cooperator who gets $S$. In PDG, we have $T>R>P>S$ and $2R>S+T$. Because
the mutual $C$ get the highest total income, $D$ is the better choice than $C$
no mater what the other player’s strategy. Without any mechanism for the
evolution of cooperation, natural selection favors defection. The other widely
studied games include snowdrift game SNG ; SNG2 , public good game PGG , rock-
paper-scissors game RPS , and so on.

The complex network has also attracted lots of attentions in the past few
years. The complex network is ubiquitous in nature. The human society can also
be described as the systems composed of interacting agents. The classical
social network maps the individual into the node, and the connection between
individuals into the link. The evolutionary game theory in spatial structure
has became a unifying paradigm to study how cooperation may be sustained in a
structured population Nowak . It was found that the spatial extension is one
of several natural mechanisms to enforce cooperation. Network structure will
affect the behavior of strategy density structure . In lattice network, the
cooperation is usually get together to support each other to resist the
defection lattice1 ; lattice2 ; SNG2 . Santos and Pacheco found in Scale-Free
networks the strong correlation leads to the dominating trait throughout the
entire range of parameters of both games in scale-free networks SF . And also,
there are anmount of researches on other networks, like small-world SW  and
random network random .

When the player on the structure network chose the better strategy to play
game, in fact, not that the players select the proper strategy, but player’s
strategy is determined by the network structure. For example, in scale-free
networks, the large degree nodes (hubs) and the nodes which connect to hubs
tend to be occupied by $C$ SF .

The networks used in the most papers of this field are statistic. The
connection will never change once it is build. It is not realistic enough, as
the interactions themselves help shape the network SW . What is more, in the
real world, the relationship between the people is not constant. Sometimes
people cannot cut some relationship with their relatives, neighbors or
colleagues but they can end their old relationship and build a new one.
Sometimes this changing is caused by the results of the game, because people
would like to make friends in a reciprocal respect. For example, people always
like to make friends with rich one for a sake of pursuing fortune. So, when we
study the social model in network like PDG, the network structure should be
dynamical entities Arne . The nodes can remove or sustain their link in
network according to the game results.

Till now, there are few models studied the cooperative behaviors in a groups
with adaptive connections. Besides some early work eW1 ; eW , Arne build a
coevolution model of strategy and structure Arne . In this model, the
probability of forming or cutting link between node $A$ and $B$ is based on
their strategies. The changing of network structure is result from the
strategy changing in the network. Then it also affect the strategy density
back. However, the link could change even if the nodes’ strategy do not change
in their model. The rewire of link in this model is not the player’s own
decision. Li et al. also build a coevolution model that the node rewire its
link only for changing its strategy LRL . Moreover, in this model, the node
rewire its long range link based on the existed network structure, not the
playing game results.

In our opinion, a rational model for coevolution of game and network structure
should contain two features: (1) The nodes rewire their links only when agents
change their status; (2) The rewiring should be based on the playing results
of game. In this paper, we will present a coevolution model of the PDG and
network. We use PDG as a metaphor to studying cooperation between unrelated
individuals and consider a social networks with four fixed local links and one
adjustable long-range link (LRL). The agents in the network play game with
their network neighbors. They will change their strategies and adjust LRLs
according to the results of game. Then the network structure changing also
affect the cooperation density.

##  II Model

We set up a system of $N$ players arranged at the nodes of a ring lattice
network. Each node is connected with four local nodes. These local
interactions will not change during the whole process of the evolution.
Besides four fixed links, every node in this lattice has an adjustable LRL
which connects to another node and self-connections and the duplicate links
are excluded. We call the LRL out-link for the node to whom it belong or in-
link for the node to whom it connect. The node can select another node to
which the out-link wires, but it cannot give up the LRL. Therefore, each node
has at least one out-link and many possible in-links. When node changes its
strategy, it will also rewire its LRL. We will discuss when and how LRLs
rewire later.

As suggested by Nowak and May Nowak , we adopt $R=1$, $T=b$ $(1<b<2)$, and
$S=P=0$. Then $b$ can be considered as the temptation to $D$ against $C$.
Every player plays the PDGs with its neighbors on network and itself and get
the total payoff $W$. After each round of the game, players are allowed to
inspect their neighbors’ total payoffs and change their strategies in the next
round. The player $i$ updates its strategy by selecting one of its neighbors
$j$ with a probability $\gamma_{ij}$,

$\gamma_{ij}=\sum_{m\in\Omega_{i}}\frac{k_{j}(t)}{k_{m}(t)},$ (1)

where $\Omega_{i}$ is the community composed of the nearest neighbors of the
player $i$, and $k_{m}(t)$ is the degree of node $m$ at time $t$. In the
spirit of preferential attachment proposed by A.-L. Barábasi and R. Albert PS
, we incorporate the preferential selection rule to model social behaviors. In
Eq. 1, player with large degree has more probability to impact his neighbors.
That is true in the society that people who have great impact often have lots
of social relations and they are also focused by their friends. Node $i$ will
follow the node $j$’s strategy by the probability,

$W=\frac{1}{1+\exp\left[(W_{i}-W_{j})/\kappa\right]},$ (2)

where $W_{i}$ and $W_{j}$ are the total payoffs of node $i$ and $j$, and
$\kappa$ indicates the noise generated by the players allowing irrational
choices ka1 ; lattice1 ; lattice3 .

If node $j$ has the same strategy with $i$ or $i$ do not mimic $j$’s strategy,
node $i$ will do nothing. Otherwise, it will rewire its LRL to a new one.
There are two rewiring rules in our model: random rewiring and preferential
rewiring. With probability $p_{c}$, the density of cooperation in the network,
node $i$ will chose a new node randomly. For the rest probability $1-p_{c}$,
node $i$ will chose a new node according to the node’s payoff. In the
preferential rewiring rule, the node rewires its link according to the payoff
of all nodes in network,

$\lambda_{ij}=\sum_{m\in G}\frac{W_{j}^{\alpha}}{W_{m}^{\alpha}},$ (3)

where $\lambda_{ij}$ is the probability of node $i$ rewiring its link to $j$
and $G$ presents all nodes in the graph. $\alpha$ is used to change the effect
of payoff. $\alpha=0$ indicates that the payoff has no effect here and the
nodes rewire their links randomly. For $\alpha>0$, the node will prefer to
connect the node with larger payoffs. So it also looks like a kind of
preferential selection rule.

##  III Simulation Results

We run our simulations with varying $b$ and $\alpha$ for fixed $\kappa=0.1$
and the system size $N=1000$. All the results in this paper are obtained from
the average results with $100$ different Monte Carlo (MC) simulation trails.
We start with node linking its LRLs to other nodes randomly with equal
probability and random initial state with $p_{c}=0.5$ as the initial state.
The players update their strategies in random sequence. In every MC step, all
nodes have one chance to change their strategies and rewire their links.

###  III.1 Strategy evolution

Figure 1: (Color online) Frequency of cooperators $p_{c}$ for different
$\alpha$ as functions of the advantage of defectors $b$. Figure 2: (Color
online) Frequency of cooperators $p_{c}$ evolve with $t$ for systems at
different parameters on PDGs.

Figure 1 shows the frequency of cooperators $p_{c}$ in our model as the
functions of $b$ for different $\alpha$. Similar to evolutionary game in
regular network lattice1 ; lattice2 , we also find two thresholds in our
model. Full cooperation is achieved if $b$ does not exceed the threshold
$b_{c1}$. For $b>b_{c2}$, $C$ cannot resist the temptation of $b$ and cannot
survive in the network. In the region of $b_{c1}<b<b_{c2}$, $C$ and $D$ can
coexist in the network. Compared with the case of $\alpha=0$, the position of
$b_{c1}$ does not change with $\alpha$. However, $\alpha$ affect the $b_{c2}$
conspicuously.

The probability of node using preferential selection to rewire its LRL is
$1-p_{c}$. Therefore $\alpha$ does not work at $p_{c}$ close to $1$ or $b$
close to $b_{c1}$. When $\alpha<1.6$, the qualitative results $p_{c}$ remain
unaffected by $\alpha$ that $p_{c}$ decreases monotonous with $b$. When
$\alpha>1.6$, there exists a region of $b$ promoting cooperation obviously.
This promotion starts at $b=1.64$ ($\alpha=1.6$) and this region enlarge with
increasing $\alpha$. But the effect of promotion does not increase with
$\alpha$. We observe that $p_{c}$ does not change at $1.55<b<1.65$ for
$\alpha=1.7$, $1.8$, and $1.9$. Actually, the transition is caused by the
changing of network structure. We will discuss it in the next subsection.

In order to discuss how the $\alpha$ promotes $p_{c}$ in the promotion region,
we present the time evolutions of $p_{c}$ in Fig. 2 for fixed $b=1.5$ with
different $\alpha$ values. The red, blue, and black lines are the averages of
$100$ trials for $\alpha=0$, $1.5$, and $1.9$ respectively. The green one is
the $p_{c}$ time series of one trail in the black line. For $\alpha=0$ and
$1.5$, $p_{c}$ decreases with time to its station state quickly. As shown in
Fig. 1, $p_{c}$ for $\alpha=1.5$ is a little higher than that of $\alpha=0$.
However, for $\alpha=1.9$, $p_{c}$ decreases like $\alpha=0$ firstly, and then
the evolution of network drives $p_{c}$ increasing with time to $0.76$.
Considering that the black line is the average of $100$ trails, we believe the
green line in Fig. 2 contains more details of the evolution. In the early
stage of the green line, $p_{c}$ decreases to a temporary stable state in a
manner similar to but a little larger than $\alpha=1.5$. However, at $t=2000$,
there is a sharp increasing in the green line from about $0.4$ to $0.76$ which
is also the final level of the average result (the black line). It means that
the gradually increasing of the black line is caused by the average effect of
$100$ same sharply increase at different times.

###  III.2 Network structure

In this model the behavior of $p_{c}$ and the evolution of network structure
are equal important. The evolution of network structure results in the
transition of $p_{c}$.

In order to describe the network structure, we first present the degree
distribution $P(k)$ in Fig. 3. Panel (a) is $P(k)$ in the case of the stable
state of red line in Fig. 2. Here the preferential rewiring does not work and
all LRLs select the target nodes randomly. Considering the self-connection is
forbidden, we know

$P(k)=C_{N-5}^{k-5}\left(\dfrac{1}{N-4}\right)^{k-5}\left(1-\dfrac{1}{N-4}\right)^{N-k+5}.$

Here $N$ usually is large enough, so one can get

$P(k)=C_{N}^{k-5}\left(\dfrac{1}{N}\right)^{k-5}\left(1-\dfrac{1}{N}\right)^{N-k+5}.$

Figure 3(b) is $P(k)$ for the stable state of blue line in Fig. 2. $P(k)$ in
(b) is similar to that of (a) but the largest degree is $19$. Fig. 3(c) is
$P(k)$ for the stable state of gree line in Fig. 2 and (d) is for the green
line after the sharp increasing.

Both (c) and (d) in Fig. 3 are the degree distributions of one trial, but not
the cumulative stationary degree distribution of $100$ different trials. By
comparing (c) with (d), it is helpful to uncover the reason of the sharp
increasing in Fig. 2. In Fig. 3 (d), there is only one node that its degree is
larger than half of the other nodes connected to it. We name this node which
has the largest degree in the network as hub node (HN). As presented in Fig.
4, the other nodes can be divided into two types: the nodes connect their LRLs
to HN and the nodes do not. We name the first node as AN and the second one as
BN. The number of them are $N_{A}$ and $N_{B}$, respectively.

Figure 3: (Color online) The cumulative stationary degree distributions $P(k)$
in PDGs. Figure 4: (Color online) Illustration of HN, AN, and BN. Each node in
the network has four fixed links and there are five red nodes wire their LRLs
to the blue one. In order to make AN and HN prominent, we do not draw the LRLs
of other nodes. The blue node has the largest degree in this net, so blue node
is HN, and the red one is AN and the others are BN. We draw the arrows in the
figure to present these LRLs are out-links for AN and in-links for HN.

Now, we exam the detail of the network after the sharp increasing in the green
line ($\alpha=1.9$, $b=1.5$) of Fig. 2. Note that the strategy of HN is always
$C$ and the strategy of most ANs is also $C$. Before the sharp increasing or
in the case of other parameters without sharp increasing, the HNs are also
prefer to $C$. This phenomenon is also observed in some other networks with
hub nodes SF ; LRL . More detailed information of our model are listed in
Table 1.

In Table 1, $p_{Ac}$ is the cooperation density of AN and $p_{Bc}$ is for BN.
Almost all nodes of ANs chose the strategy $C$, so we do not need to present
the mean payoff of AN with $D$. What is more, it is found that $p_{Bc}=0.308$
is close to the case of $\alpha=0$ ($p_{c}=0.314$ for $b=1.5$, $p_{c}=0.235$
for $b=1.55$, and $p_{c}=0.179$ for $b=1.6$). It means that the existence of
AN does not affect the strategy density of BN. As discussed in Ref. LRL , AN
can resist the temptation of $b$ by mimicking the strategy of HN. After the
sharp increasing, the probability that AN mimics the strategy of HN is much
larger than that of other neighbors. The HN’s payoff is also larger because it
has a lots of in-link LRLs. We will discuss the details of these probabilities
in the next subsection. On the other hand, only the node with strategy $C$ can
grow into HN. If HN is occupied by $D$, HN will get higher payoff temporarily.
However, as we discussed above, AN will follow HN’s strategy and the strategy
of AN will be $D$. Then the HN cannot earn payoff from its in-link LRLs. Once
HN cannot earn enough payoff, both preferential and random rewiring will drive
ANs to rewire its LRL to other nodes. Then a new HN with strategy $C$ will
appear in the network. So it seems that strategy $C$ is a better choice for HN
because it can earn a stable higher payoff.

From Table 1, we also find that the BNs with $D$ earn the most payoff and the
payoff of BN with $C$ is close to the payoff of AN. However, although the mean
payoff of BN with $D$ is the highest, in fact, the density of cooperator
doesn’t decrease with time. It shows that the probability of $C$ mimicking $D$
strategy and $D$ mimicking $C$ strategy are the same.

Table 1: The detailed information of prisoner’s dilemma games ($\alpha=1.9$). | $b=1.5$ | $b=1.55$ | $b=1.6$
---|---|---|---
$N_{A}$ | $669$ | $621$ | $605$
$N_{B}$ | $330$ | $378$ | $394$
$p_{c}$ | $0.766$ | $0.686$ | $0.663$
$p_{Ac}$ | $0.992$ | $0.988$ | $0.987$
$p_{Bc}$ | $0.308$ | $0.191$ | $0.164$
payoff of AN | $5.213$ | $4.806$ | $4.682$
payoff of BN with $C$ | $5.222$ | $4.987$ | $5.025$
payoff of BN with $D$ | $5.713$ | $5.541$ | $5.561$
Figure 5: (Color online) Because the network structure in our model is one
dimension lattice, we can use a color line to present the snapshot of the
status of the network. The black and white dots present $C$ and $D$ in BN. The
green and red dots present $C$ and $D$ in AN. In order to know how the AN, BN,
and strategy evolve in network, we arrange these snapshots with time from top
to the botton at $1600<t<2100$ in the left panel for the green line in Fig. 2.
The right panel presents the time evolution of the number of AN at the same
time.

Each horizontal line in Fig. 5 presents a snapshot of the network. We arrange
these snapshots with time from top to the botton to show how the AN evolves
with time. So we can depict every player’s strategies in network and observe
the evolution of these strategies. The riht panel is $N_{A}$ at the same time
with the left. There is also a sharp increasing of $N_{A}$ at the same time
like the green line in Fig. 2 in looks. At $t=1750$, about $50$ MC steps
before the transition, $N_{A}$ increase gradually from about $10$ to $50$.
After the sharp increasing, $N_{A}$ still increase gradually to the final
stable state. Moreover, before the sharp increasing happened, one can observe
many black blocks (the upper part of the left panel in figure 5). It means the
model has the similar feature of PDG in regular network that the $C$ node
tends to get together for blocks to resist the $D$. These blocks start at a
few $C$s, maybe three or more, and then close to each other in the network
coincidentally. Then a block is established and it will grow to change their
neighbors’ strategies. After some MC steps, the block will shrink and then
disappears in the last. After the sharp increasing of $N_{A}$, there are too
few red dots ($D$ in AN). The green strip ($C$ in AN) indicates that the ANs
or BNs are very stable in the network. The probability of AN change to BN is
very small and vice versa.

###  III.3 Discussion

Based on the results in the above context, the effect of $\alpha$ is different
from various $b$ and $\alpha$. After the sharp increasing, the nodes in
network can be divided into AN and BN. Almost all AN are $C$ and the density
of $C$ in BN is close to the case of $\alpha=0$. So we can use the mean field
theory and some basic feature of stable state to explain why the sharp
increasing happened.

After the sharp increasing in Fig. 3, the system reaches the stable state
gradually. Then we have ${dN_{A}}/{dt}=0$ or $N_{A\rightarrow
B}=N_{B\rightarrow A}$, where $N_{A\rightarrow B}$ is the average number of
nodes changed from AN to BN in one MC step and $N_{B\rightarrow A}$ is that
changed from BN to AN.

Considering that there are too few $D$s in AN, we assume that $N_{A\rightarrow
B}$ is only caused by $C\rightarrow D$ and random rewire. Here, we neglect the
preferential rewiring. Because the contribution of preferential rewiring is
only about $2\%$ of random rewiring. Then we get

$\displaystyle N_{A\rightarrow B}$ $\displaystyle=$
$\displaystyle(1-p_{c})Q_{A\rightarrow B}p_{c}N_{A}$ (4)
$\displaystyle\frac{\left(5+\frac{N-N_{A}}{N}\right)\left(4+\frac{N-N_{A}}{N}\right)}{N_{A}+\left(5+\frac{N-N_{A}}{N}\right)\left(4+\frac{N-N_{A}}{N}\right)}.$

Here, $p_{c}$ means the change happened in the random rewiring, and
$5+(N-N_{A})/N$ is the mean degree of nodes in networks. We neglect self-
connection and multi-connection forbidden and we have $N\approx N-1$ here.
Because AN has the same strategy with HN, AN only mimics the strategy from
other $4+(N-N_{A})/N$ neighbors. The big fraction is the probability of AN do
not chose HN to mimic the strategy. The last $(1-p_{c})$ is the probability of
mimicked target with strategy $D$. We assume $Q_{A\rightarrow B}$ is the
probability of success in the mimicking.

Then $N_{B\rightarrow A}$ will be more complicate. We assume that BN change to
AN because they use the preferential rewiring. The contribution of random
rewiring is about $0.2\%$ of preferential rewiring, so we neglect it and
derive the following formula,

$\displaystyle N_{B\rightarrow A}$ $\displaystyle=$
$\displaystyle\left[p_{Bc}(1-p_{c})+(1-p_{Bc})p_{c}\right]Q_{B\rightarrow
A}(1-p_{c})N_{B}$ (5)
$\displaystyle\frac{(N_{A}+5)^{\alpha}}{(N_{A}+5)^{\alpha}+N_{A}(2+4p_{c})^{\alpha}+p_{Bc}N_{B}\left(1+(5+\frac{N-N_{A}}{N})p_{c}\right)^{\alpha}+N_{B}(1-p_{Bc})\left(b(5+\frac{N-N_{A}}{N})p_{c}\right)^{\alpha}},$

where $1-p_{c}$ means the preferential rewiring, and $p_{Bc}(1-p_{c})$ is the
probability of BN with strategy $C$ to mimic its $D$ neighbor and that $D$ try
to mimic its $C$ neighbor. The fraction here is the probability of node rewire
to HN using the preferential rewiring. We assume $Q_{B\rightarrow A}$ is the
probability of success in the mimicking.

Now, one can get $p_{Bc}$ from the simulation of $\alpha=0.0$ and
$p_{c}=(p_{Bc}N_{B}+N_{A})/N$, and then we know how $N_{A}$ evolves with time
by using $N_{B\rightarrow A}-N_{A\rightarrow B}$. If $N_{B\rightarrow
A}-N_{A\rightarrow B}=0$, $N_{A}$ will not change with time. And
$N_{B\rightarrow A}-N_{A\rightarrow B}>0$ means $N_{A}$ will increase in the
next MC step. However, we do not know $Q_{A\rightarrow B}$ and
$Q_{B\rightarrow A}$ yet. According that the mean payoff of $BN$ with $D$ is
larger than mean payoff of $AN$ in Tab. 1, we conjecture $M=Q_{B\rightarrow
A}/Q_{A\rightarrow B}$ and $M>1$. Indeed, we find $M=2.0$ is fit to our model.
We will take $b=1.5$ with $\alpha=1.9$ and $\alpha=1.3$ as examples. For
$b=1.5$ and $\alpha=0$ we get $p_{c}=0.314$ from the simulation.

Fig. 6 plots ${dN_{A}}/{dt}$ as different $N_{A}$. For $\alpha=1.3$ there are
two stable points at $N_{A}=3$ and $860$, and one unstable point at
$N_{A}=23$. For $\alpha=1.9$, there is only one stable state at $N_{A}=939$.
The unstable point will decrease with the increasing of $\alpha$ and
coincident with the first stable point at $\alpha=1.69$. However, even
$\alpha=0$, the maximal degree in the network is about $12$. So the first
stable point can be discarded. When the unstable point crosses $N_{A}=12$ or
there is only one stable point, the system will reach to the second stable
point.

Figure 6: (Color online) $N_{B\rightarrow A}-N_{A\rightarrow B}$ with various
$N_{A}$. Panel (b) is an enlargement of (a).

##  IV Conclusion

The coevolution of dynamics and network structure is rapidly becoming an
important field of the evolutionary game. It contains more details about the
social interaction in the real world. In this paper, we build a co-evolution
model of PDG and network structure. Each node in network has four fixed local
links and one adjustable LRL. When the node changes its strategy, it will
rewire its LRL to another node according to the node’s payoff and density of
cooperation. And we introduce a parameter $\alpha$ to denote the effect of
payoff.

Many early works eW1 ; ew; Arne ; LRL  also proved that the adaptive network
can enhance the cooperation. All these enhancements are caused by the
emergency of cooperator with large degree in the network. In eW1 , the
cooperation is very sensitive to the plasticity parameter and only the
adaptive network can enhance the cooperation.

In our model, the players rewire their LRLs for any $\alpha$, but the
cooperation is enhanced only in the case of $\alpha>0$ that this enhancement
is obvious for $\alpha>1.6$ in a certain region of $b$. However, our results
show that the enhancement of cooperation only happen in the case of changing
the network structure property. In our model, for $\alpha=0$, the node will
also rewire its LRL, but the network property will not change and the
cooperation level will not be enhanced. The cooperation is enhanced only when
the node rewires its LRL according to the payoff. Similar phenomena was also
observed in our simulations with snowdrift game (SG). We found that SG is more
sensitive to $\alpha$ than PDG and the obvious enhancement is for a smaller
$\alpha$. So we conjecture that the coevolution of network structure and game
is an important mechanics to maintain the cooperation in the real society.

Different from the results in eW1 ; eW ; Arne ; LRL  which the cooperation
always dominates in the adaptive network and the increasing of cooperation is
limited. That is caused by two reasons: (1) In the probability of $p_{c}$ the
player use the random rewiring. (2) The existance of four fixed links in
network can be regarded as a noise to prevent the preferential selection. In
eW , authors discussed the leaders and the global cascades. If every node
could change its strategy in a smaller probability, the global cascades of
coopertation is also observed in our model.

The analysis in this paper is based on the balance of AN and BN. However, when
the sharp increasing didn’t happen, perhaps there exist more than one HNs and
HN is changing from one node to another frequently. Because of the absense of
the information about spacial structure and Eq. 2, the presented analysis in
this model is not very precise any more. Actually, it is impossible to include
all the details for the analysis. We just hold on the main factors of the
model and it works well enough to explain the main features of our model.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China
under Grant No. $10305005$ and by the Fundamental Research Fund for Physics
and Mathematic of Lanzhou University. This study is supported by the high-
performance computer program in Lanzhou University.

## References

  * (1) R. Trivers, Q. Rev. Biol. 46, 35 (1971).
  * (2) R. Axelrod and W. D. Hamilton, Science 211,1390 (1981).
  * (3) P. E. Turner and L. Chao, Nature (London) 398, 441 (1999).
  * (4) J. M. Smith, Evolution and the Theory of Games (Cambridge University Press, Cambrideg, England, 1982).
  * (5) J. Hofbauer and K. Sigmund, Evolutionary Games and Popularion Dynamics (Cambridge University Press, Cambridge, 1998).
  * (6) G. Szabó and G. Fáth, Phys. Rep. 446, 97 (2007).
  * (7) C. Hauert and M. Doebeli, Nature (London) 428, 643 (2004).
  * (8) W. X. Wang, J. Ren, G. Chen, and B. H. Wang, Phys. Rev. E. 74, 056113 (2006).
  * (9) G. Szabó and C. Hauert, Rhys. Rev. Lett. 89, 118101 (2002); D. Semmann, H. J. R. Krambeck, and M. Milinski, Nature (London) 425, 390 (2003).
  * (10) M. Peltomäki and M. Alava, Phys. Pev. E 78, 031906 (2008).
  * (11) M. A. Nowak and R. M. May, Nature (London) 359, 826 (1992); M. A. Nowak and R. M. May, Int. J. Bifurcat. Chaos 3, 35 (1993).
  * (12) Z. X. Wu, X. J. Xu, Y. Chen, and Y. H. Wang, Phys. Rev. E. 71, 037103 (2005); J. Vukov, G. Szabó, and A. Szolnoki, ibid. 77, 026109 (2008).
  * (13) G. Szabó and C. Töke, Phys. Rev. E 58, 69 (1998).
  * (14) S. M. Qin, Y. Chen, X. Y. Zhao, and S. Jian, Phys. Rev. E 78, 041129 (2008).
  * (15) F. C. Santos and J. M. Pacheco, Phys. Rev. Lett. 95, 098104 (2005); F. C. Santos, J. M. Pacheco, and T. Lenaerts, Proc. Natl. Acad. Sci. U.S.A. 103, 3490 (2006).
  * (16) M. Tomassini, L. Luthi, and M. Giacobini, Phys. Rev. E 73, 016132 (2006).
  * (17) J. Ren, W.-X. Wang, and F. Qi, Phys. Rev. E 75, 045101 (2007).
  * (18) J. M. Pacheco, A. Traulsen, and M. A. Nowak, Phys. Rev. Lett. 97, 258103 (2006).
  * (19) M. G. Zimmermann, V. M. Eguíluz, and M. S. Miguel, Phys. Rev. E 69, 065102 (2004).
  * (20) M. G. Zimmermann and V. M. Eguíluz, Phys. Rev. E 72, 056118 (2005).
  * (21) W. Li, X.-M Zhang, and G. Hu, Phys. Rev. E 76, 045102 (2007).
  * (22) A.-L. Barábasi and R. Albert, Science 286, 509 (1999).
  * (23) G. Szabó and C. Hauert, Phys. Rev. E 66, 062903 (2002).
  * (24) G. Szabó, J. Vukov, and A. Szolnoki, Phys. Rev. E 72, 047107 (2005).


# Automatic Code Documentation Generation Using GPT-3

Junaed Younus Khan and Gias Uddin  DISA Lab, University of Calgary

(2022)

###### Abstract.

Source code documentation is an important artifact for efficient software
development. Code documentation could greatly benefit from automation since
manual documentation is often labouring, resource and time-intensive. In this
paper, we employed Codex for automatic code documentation creation. Codex is a
GPT-3 based model pre-trained on both natural and programming languages. We
find that Codex outperforms existing techniques even with basic settings like
one-shot learning (i.e., providing only one example for training). Codex
achieves an overall BLEU score of 20.6 for six different programming languages
(11.2% improvement over earlier state-of-the-art techniques). Thus, Codex
shows promise and warrants in-depth future studies for automatic code
documentation generation to support diverse development tasks.

code documentation, GPT-3, Machine Learning.

††journalyear: 2022††copyright: acmcopyright††conference: 37th IEEE/ACM
International Conference on Automated Software Engineering; October 10–14,
2022; Rochester, MI, USA††booktitle: 37th IEEE/ACM International Conference on
Automated Software Engineering (ASE ’22), October 10–14, 2022, Rochester, MI,
USA††price: 15.00††doi: 10.1145/3551349.3559548††isbn:
978-1-4503-9475-8/22/10††ccs: Software and its engineering Documentation††ccs:
Computing methodologies Natural language generation

##  1\. Introduction

In Software Engineering (SE), developers often try to figure out what a
specific code unit (e.g., method) does and how to use it (Xia et al., 2017).
They can do this by reading documentation of source code. Well-written
documentation is crucial for effective software development (de Souza et al.,
2005). The sudden shift to work from home during COVID-19 further showed the
needs for good documentation for developers, when the subject matter expert of
code base may be absent/unavailable (Uddin et al., 2022). However, such
documentation is costly and time-consuming to create and maintain. Most
developers often show unwillingness towards writing documentation as they find
it less productive and less rewarding (Parnas, 2011; McBurney et al., 2017).
As a result, manual documentation often becomes problematic or unusable
(Robillard, 2009; Aghajani et al., 2019, 2020; Uddin et al., 2021). Moreover,
documentation becomes obsolete over time with continuous modification or
update to the system (i.e., code-base) (Ibrahim et al., 2012; Uddin and
Robillard, 2015; Uddin et al., 2012).

Automated code documentation generation is currently attracting a lot of
attention from the researcher community to substitute or complement the manual
documentation efforts. Earlier works in this direction mostly focused on
template-based (Sridhara et al., 2010; McBurney and McMillan, 2014; Moreno et
al., 2013; Rai et al., 2017; Abid et al., 2015; Rastkar et al., 2011) and
information retrieval (IR)-based strategies (Haiduc et al., 2010a, b; Eddy et
al., 2013; Wong et al., 2013; Vassallo et al., 2014; Wong et al., 2015).
Template-based approaches are limited to the underlying set of templates and
so are finite/limited, while similarity measures in IR-based approaches can be
erroneous (Rai et al., 2022). Recently, researchers are investigating several
learning-based (e.g., deep learning) approaches for documentation generation.
For example, CODE-NN, presented by Iyer et al., can generate documentation of
C# and SQL code using LSTM attention networks (Iyer et al., 2016). Allamanis
et al. also used an attention neural network for code summarization (Allamanis
et al., 2016). Hu et al. developed DeepCom that produces code documentation
using NLP techniques and by combining the lexical and structure information of
source code (Hybrid-DeepCom) (Hu et al., 2018, 2020).

Recent success of pre-trained transformer models in several domains encouraged
researchers to also utilize those for automated documentation generation. In
fact, they are found to be the state-of the-art performers in this task.
CodeBERT, a BERT-based model pre-trained on large scale natural and
programming language data, showed great performance in automated documentation
generation (Feng et al., 2020). Some other transformer-based pre-trained
models i.e., PLBART (Ahmad et al., 2021), CoTexT (Phan et al., 2021) recently
outperformed CodeBERT in the context of documentation generation.

Although pre-trained transformer models have shown promise in code
documentation generation, we are aware of no study to evaluate the
effectiveness of GPT-3 in this direction. GPT-3 is the third generation
Generative Pre-trained Transformer model developed by OpenAI. GPT-3 has 175B
parameters and is trained on very large-scale internet data (Brown et al.,
2020). It has been found to achieve high performance in different
classification and generation tasks (Floridi and Chiriatti, 2020; Dale, 2021;
Chiu and Alexander, 2021; Chintagunta et al., 2021). Similar to other
transformer models, GPT-3 architecture can also be used in different software
engineering tasks that involve both natural and programming language
understanding. In fact, OpenAI released a dedicated model, Codex for this
task. Codex is a GPT-3 like model which is trained on large-scale GitHub data.
Codex is trained on over a dozen of programming languages like Python, Java,
PHP, JavaScript, and so on (Chen et al., 2021). The video demo of OpenAI shows
that Codex could generate source code from a given requirement specified in
Natural Language. Since then researchers have been investigating Codex for the
automation of several SE tasks like code generation (Finnie-Ansley et al.,
2022), code repair (Prenner and Robbes, 2021), security bug-fix (Pearce et
al., 2021), simulation modeling (Jackson and Saenz, 2022). The official
documentation of Codex mentions that it is also capable of automatic
documentation generation. However, we are not aware of any systematic
evaluation of Codex to produce code documentation.

In this paper, we conducted a preliminary case study to investigate the
effectiveness of Codex in code documentation. We analyzed the code
documentation automatically produced by Codex for six programming languages:
Python, Java, PHP, GO, JavaScript, Go, and Ruby. To be specific, we evaluated
Codex on CodeSearchNet dataset (Husain et al., 2019) and compared its
performance with existing models (Feng et al., 2020; Ahmad et al., 2021; Phan
et al., 2021; Parvez et al., 2021). Unlike other pre-trained transformer
models, GPT-3 often performs well at different downstream tasks without any
kind of re-training or fine-tuning. Instead, it is adapted to a task by one
(or few)-shot learning where the model is provided with a task description and
one (or few) example(s) of that task. In fact, simply providing the task
description without any examples (zero-shot learning) often yields good
results. In this study, we have experimented Codex with both zero and one-shot
learning. We found that Codex with one-shot learning shows state-of-the-art
overall performance in documentation generation outperforming all previous
models with an average BLEU score of 20.63. As per language specific
performance, it outperforms all the models in four out of six languages (i.e.,
Python, Ruby, JavaScript, GO) with good margin. For the other two languages
i.e., Java and PHP, it becomes the second best performer, where it was
slightly outperformed by REDCODER and CodeBERT, respectively. We also
conducted several qualitative analyses of the Codex documentations in terms of
Flesch-Kincaid Grade Level (readability), Documentation Length (quantity), and
TF-IDF (informativeness). We found that the generated documentations are close
to the actual ones based on these metrics. In fact, we observed that some
Codex generated documentation might contain more comprehensible information
than the actual ones. We found that even with very basic setup (one-shot
learning), Codex is capable of state-of-the-art performance in this field. To
the best of our knowledge, ours is the first systematic evaluation of GPT-3
Codex model in automated code documentation generation.

Replication Package. https://github.com/disa-lab/CodeDoc_GPT-3_ASE22

##  2\. Related Work

Related work on automatic code documentation can be three types: Template,
Information retrieval, and Learning-based.

Template-based uses an automatic tool to insert information according to pre-
defined rules and layout. Sridhara et al. utilized natural language templates
to capture the key statements from a Java method and build a method level
summary (Sridhara et al., 2010). Rastkar et al. and Moreno et al. used
heuristics to extract and summarize information from source code (Rastkar et
al., 2011; Moreno et al., 2013). Mcburney et al. merged contextual information
with method statements (McBurney and McMillan, 2014). Abid et al. produced
summary for C++ methods by stereotyping them with their source code analysis
framework (srcML) (Abid et al., 2015). Rai et al. summarized Java code that
uses code level nano-patterns (Rai et al., 2017).

Information Retrieval approaches like latent semantic indexing (LSI) and
vector space modeling (VSM) have been employed by Haiduc et al. to generate
documentation for classes and methods (Haiduc et al., 2010a, b). Eddy et al.
extended their work by exploiting a hierarchical topic model (Eddy et al.,
2013). Wong et al. employed code clone detection to find similar code snippets
from StackOverflow and automatically mined source code descriptions for
comment generation (Wong et al., 2013, 2015).

Learning-based approaches mostly use deep-learning techniques to learn latent
features from source-code. Iyer et al. proposed an LSTM-based network, CODE-
NN, that was trained on Stack Overflow data to generate C# and SQL code
summaries (Iyer et al., 2016). Allamanis et al. used an attention neural
network that employs convolution to learn local, time-invariant features
(Allamanis et al., 2016). Barone et al. built a dataset of Python functions
and their docstrings using GitHub data and employed Neural Machine Translation
(NMT) to generate docstrings from given functions (Barone and Sennrich, 2017).
Wan et al. proposed a reinforcement learning framework that incorporates the
abstract syntax tree (AST) along with the sequential code content (Wan et al.,
2018). Hu et al. developed DeepCom and Hybrid-Deepcom to generate code
comments by learning from a large corpus and by combining lexical and
structural information of code (Hu et al., 2018, 2020). Chen and Zhou designed
a neural framework called BVAE to improve code retrieval and summarization
tasks (Chen and Zhou, 2018). Several studies employed transformer-based
models, e.g., Ahmad et al. used self-attention based transformer model (Ahmad
et al., 2020) while Wang et al. developed a BERT-based model called Fret (Wang
et al., 2020). Feng et al. presented CodeBERT, pre-trained on 2.1M bimodal
data points (codes and descriptions) and 6.4M unimodal code across six
languages (Python, Java, JavaScript, PHP, Ruby, and Go) (Feng et al., 2020).
They evaluated CodeBERT on two downstream NL-PL tasks (code search and
documentation) by fine-tuning model parameters. Gao et al. proposed the
concept of Code Structure Guided Transformer for source code summarization
that incorporates code structural properties into transformer to improve
performance (Gao et al., 2021). Phan et al. presented CoTexT that learns the
representative context between natural & programming language and performs
several downstream tasks including code summarization (Phan et al., 2021).
Ahmad et al. developed PLBART, a sequence-to-sequence model, pre-trained on a
large set of Java and Python functions and their textual descriptions
collected from Github and Stack Overflow (Ahmad et al., 2021). Later, Parvez
et al. showed that the addition of relevant codes/summaries retrieved from a
database (such as GitHub and Stack Overflow) can improve the quality of
documentation produced by a generator model (Parvez et al., 2021).

Though transformer-based models showed promise in documentation generation,
GPT-3 model had not been systematically evaluated for this task yet in spite
of its success and popularity. Our study employed GPT-3 based Codex model for
documentation generation and compared its performance with existing
approaches.

##  3\. Experiment

In this section, we present the results of our preliminary investigation of
the effectiveness of GPT-3 for source code documentation generation. A
schematic overview of the major steps of our study is shown at Figure 1 and
are described below.

Figure 1. A schematic overview of our study

###  3.1. Dataset Collection and Preprocessing

To evaluate the effectiveness of our method, we used CodeSearchNet (Husain et
al., 2019), a widely used dataset for different downstream SE tasks. This
dataset is also included in CodeXGLUE (Lu et al., 2021), a machine learning
benchmark dataset for code understanding and generation. It incorporates a
large number of code and documentation pairs coming from six different
languages i.e., Java, Python, PHP, GO, JavaScript, and Ruby. We applied the
same data processing recommended by Feng et al. where they evaluated CodeBERT
for documentation generation (Feng et al., 2020). We first removed comments
from all the codes and then removed examples where i) the codes cannot be
parsed into an abstract syntax tree, ii) the number of tokens in the
documentation is less than 3 or greater than 256, iii) documentation contains
special tokens such as $<$img$>$, https://, etc., iv) the language is not
English. The statistics of the clean dataset are available at Table 1.

Table 1. Statistics of CodeSearchNet (Husain et al., 2019)

Language | Train | Valid | Test
---|---|---|---
Java | 164,923 | 5,183 | 10,955
Python | 251,820 | 13,914 | 14,918
PHP | 241,241 | 12,982 | 14,014
GO | 167,288 | 7,325 | 8,122
JavaScript | 58,025 | 3,885 | 3,291
Ruby | 24,927 | 1,400 | 1,261

###  3.2. GPT-3 Model and Parameter Setup

Model. Generative Pre-trained Transformer-3 (GPT-3) (Brown et al., 2020),
developed by OpenAI, is an autoregressive language model that employs deep
learning to generate human-like text. It has 175 billion parameters and 96
layers trained on $\sim$45 TB of text data coming from different web contents
(such as Wikipedia). It has promising results in various kinds of NLP tasks
e.g., question-answering, summarizing, translation. Not only that, GPT-3 has
also shown great success in software engineering tasks like code generation
from natural language command. Hence, we felt motivated to evaluate its
effectiveness in code documentation generation as well. For our experiment, we
used Codex, a descendant of GPT-3, that is trained on both natural language
and billions of lines of public code from GitHub. Codex can understand various
programming languages such as Python, Java, JavaScript, Go, Perl, PHP, Ruby,
etc. Codex has already been used successfully to automate several SE tasks
e.g., code generation (Finnie-Ansley et al., 2022), code repair (Prenner and
Robbes, 2021), security bug-fix (Pearce et al., 2021).

Prompt Engineering. The interaction with GPT-3/Codex takes via prompt
engineering, where a task description is provided as the input (prompt) and
the model (GPT-3) performs the desired task (generates text) accordingly.
There are several ways of prompting with GPT-3 models i.e., zero-shot, one-
shot, few-shot learning. In zero-shot learning, the model is expected to
generate an answer without providing any example. In fact, no additional
information other than the task description itself is given in the prompt. On
the other hand, one-shot and few-shot learning involve giving one (i.e., one-
shot) or more than one (i.e., few-shot) examples in the prompt, respectively.
In this study, we have experimented with zero-shot and one-shot learning. In
zero-shot learning, we just tell the model to generate a documentation for a
given source code in the prompt. In one-shot learning, we randomly select one
sample (i.e., code-documentation pair) from the train set of the corresponding
language (from CodeSearchNet), provide it in the prompt (as example) and then
ask the model to generate a documentation for another source code by learning
from the provided example of code-documentation pair. Figure 2 depicts the
one-shot prompt format we used for documentation generation.

⬇

Code:

def add(x, y):

return x+y

Documentation: Adds two numbers.

Code:

def subtract(x, y):

return x-y

Documentation: [To be generated by Codex]

Figure 2. Sample prompt format for one-shot learning

Parameter Settings. There are a number of parameters involved with GPT-3 based
models. One such parameter is Temperature that controls the randomness of the
generated output (range 0 to 1). Another randomness parameter is Top-p (range
0 to 1) that controls how unlikely words can get removed from the sampling
pool by choosing from the smallest possible set (of words) whose cumulative
probability exceeds p. As recommended by Codex official documentation, we set
the temperature at a low value (0.2) while keeping top-P at its default value
(1.0). We also keep Frequency and Presence penalties at their default values
(0.0) which control the level of word repetition in the generated text by
penalizing them based on their existing frequency and presence. We use the max
tokens size as 256 since our formatted dataset does not contain any larger
($>$256) documentation (see Section 3.1).

###  3.3. Evaluation of Generated Documentation

Since GPT-3 models are currently subject to response limit and cost, we used a
statistically significant sample size for this study instead of using the
whole test sets for different languages. As depicted in Table 1, the largest
test set in CodeSearchNet belongs to Python consisting of 14,918 samples and a
statistically significant sample size from that would be 375 with 95%
confidence interval and 5% error margin. However, we randomly selected 1000
($>$375) samples from each test set (i.e., total 6 sets of 1K samples for 6
languages) and evaluated Codex model on them. For evaluation, we used BLEU
score (Papineni et al., 2002), a popular evaluation metric for machine-
generated text that calculates the n-gram similarity of a generated and
reference text. Since the generated documentation can be short at times and
higher order n-gram might not overlap, we used smoothed BLEU score (Lin and
Och, 2004) as recommended by prior works (Feng et al., 2020; Ahmad et al.,
2021; Parvez et al., 2021).

####  3.3.1. Performance Analysis

Table 2 compares Codex’s performance with several SOTA models for
documentation generation: Seq2Seq (Sutskever et al., 2014), Transformer
(Vaswani et al., 2017), RoBERTa (Liu et al., 2019), CodeBERT (Feng et al.,
2020), PLBART (Ahmad et al., 2021), CoTexT (Phan et al., 2021), REDCODER
(Parvez et al., 2021). We observed that though Codex with zero-shot learning
could not achieve satisfactory results (mostly because it fails to learn the
expected documentation format), the performance greatly improves with one-shot
learning. In fact, Codex (with one-shot) shows the best overall performance
among all approaches with an average BLEU score of 20.63 while the nearest
competitor CoTexT achieves 18.55 (11.21% improvement). In language specific
performance, it significantly outperforms other models in all languages except
two i.e., Java and PHP. In Java and PHP, Codex achieves BLEU scores of 22.81
and 25.13, which are slightly outperformed by REDCODER (22.95) and CodeBERT
(25.16) respectively. Here, REDCODER is not an individual model on its own,
rather it is a retrieval approach that can be used with other generative
models to enhance their performances. In the original paper (Parvez et al.,
2021), the authors used PLBART (Ahmad et al., 2021) as the base model for
REDCODER where they retrieved relevant summaries from StackOverflow, GitHub,
etc. and provided them with the input of PLBART to enhance its performance.
Hence, it has some additional overhead (time and resource) while Codex is an
all-in-all model itself. Moreover, Codex can perform even better if used with
such additional retrieval approach (i.e., REDCODER). On the other hand,
CodeBERT and most other reported models had been (re)trained or fine-tuned on
task and language-specific datasets while Codex was provided with only zero or
one example in our evaluation.

Table 2. Results on documentation generation (BLEU score)

Model | Ruby | JavaScript | GO | Python | Java | PHP | Overall
---|---|---|---|---|---|---|---
Seq2Seq (Sutskever et al., 2014) | 9.64 | 10.21 | 13.98 | 15.93 | 15.09 | 21.08 | 14.32
Transformer (Vaswani et al., 2017) | 11.18 | 11.59 | 16.38 | 15.81 | 16.26 | 22.12 | 15.56
RoBERTa (Liu et al., 2019) | 11.17 | 11.90 | 17.72 | 18.14 | 16.47 | 24.02 | 16.57
CodeBERT (Feng et al., 2020) | 12.16 | 14.90 | 18.07 | 19.06 | 17.65 | 25.16 | 17.83
PLBART (Ahmad et al., 2021) | 14.11 | 15.56 | 18.91 | 19.30 | 18.45 | 23.58 | 18.32
CoTexT (2-CC) (Phan et al., 2021) | 13.07 | 14.77 | 19.37 | 19.52 | 19.1 | 24.47 | 18.38
CoTexT (1-CC) (Phan et al., 2021) | 14.02 | 14.96 | 18.86 | 19.73 | 19.06 | 24.58 | 18.55
REDCODER (Parvez et al., 2021) | - | - | - | 21.01 | 22.94 | - | N/A
REDCODER-EXT (Parvez et al., 2021) | - | - | - | 20.91 | 22.95 | - | N/A
Codex (0-shot) | 5.41 | 9.83 | 15.80 | 18.93 | 13.59 | 13.32 | 12.81
Codex (1-shot) | 16.04 | 16.58 | 20.94 | 22.28 | 22.81 | 25.13 | 20.63

####  3.3.2. Qualitative Analysis

As suggested by Schreck et al. (Schreck et al., 2007), we used Documentation
Length and Flesch-Kincaid Grade Level (DuBay, 2004) to measure the Quantity
and Readability of the generated documentation. We find that the average
Flesch-Kincaid score of the Codex generated documentations is 5.97 with an
average length of 8 words (per documentation) while the average Flesch-Kincaid
score of the actual documentations is 6.77 with an average length of 12 words.
Hence, the generated documentations are close to the actual ones in terms of
quantity and readability. We further analyzed the informativeness of the
generated documentation with respect to the actual ones using TF-IDF. To
calculate the TF-IDF of a particular documentation, we add TF-IDF scores of
all the words of the documentation (except stop-words). The average TF-IDF of
Codex generated documentations is 1.94 while for actual documentations it is
2.28. Hence, the informativeness of the generated documentation is
satisfactory in terms of comparative TF-IDF with the actual ones. We show some
examples of Codex generated documentations in Figure 3. We see that in some
cases, Codex can generate more comprehensible or additional information
compared to the actual ones. In the example of PHP mentioned in Figure 3,
Codex mentions “base-10 number” instead of “decimal” which is more
understandable for users. In the example of Ruby, Codex provides an extra
information “If the path is not present a noop is performed.” which is correct
but was not present in the actual documentation.

⬇

Java

protected ImageIcon createImageIcon(String path, String description) {

java.net.URL imgURL = getClass().getResource(path);

if (imgURL != null) {

return new ImageIcon(imgURL, description);

} else {

System.err.println("Couldn’t find file: " + path);

return null;

}

}

Actual: Returns an ImageIcon, or null if the path was invalid.

Codex: Returns an ImageIcon, or null if the path was invalid.

⬇

Python

def check_for_file(self, file_path):

try:

files = self.connection.glob(file_path, details=False, invalidate_cache=True)

return len(files) == 1

except FileNotFoundError:

return False

Actual: Check if a file exists on Azure Data Lake.

Codex: Check if a file exists on the remote machine.

⬇

PHP

public static function base256ToDec($number)

{

Validate::canCastAsString($number, ’number’);

$result = 0;

$base = 1;

for ($i = strlen($number) - 1; $i >= 0; $i\--) {

$result = bcadd($result, bcmul(ord($number[$i]), $base));

$base = bcmul($base, 256);

}

return $result;

}

Actual: Convert base 256 number to decimal number.

Codex: Converts a base 256 number to a base 10 number.

⬇

JavaScript

function validateProtocolOptions(protocolOptions) {

if (!protocolOptions) {

throw new TypeError(’protocolOptions not defined in options’);

}

const version = protocolOptions.maxVersion;

if (version && (typeof version !== ’number’ ||
!types.protocolVersion.isSupported(version))) {

throw new TypeError(util.format(’protocolOptions.maxVersion provided (%s) is
invalid’, version));

}

}

Actual: Validates the protocol options.

Codex: Validate protocol options.

⬇

Ruby

def remove_file(*paths)

path = File.join(*paths)

log.debug(log_key) { "Removing file {path}’” }

FileUtils.rm_f(path)

path

end

Actual: Remove the file at the given path.

Codex: Removes the file located at the given path. If the path is not present
a

noop is performed.

⬇

GO

func (os *orderedSet) append(s string) {

if _, ok := os.included[s]; !ok {

os.list = append(os.list, s)

os.included[s] = struct{}{}

}

}

Actual: append adds s to the end of os, only if it is not included already.

Codex: append adds s to the orderedSet if it is not already present.

Figure 3. Examples of documentation by Codex (1-shot)

##  4\. Conclusion and Future Work

We explored GPT-3 Codex for automatic documentation generation and compared
its performance with existing approaches. While previous approaches are
subject to task/language-specific retraining or fine-tuning, Codex shows SOTA
performance even with very basic settings. In future, we intend to investigate
Codex more in-depth in terms of parameter tuning, few shot learning, fine-
tuning to improve its performance even further. We also plan to employ Codex
to fix documentation issues (e.g., doc smells) that we found in our earlier
study (Khan et al., 2021). In particular, this study has a number of
limitations that we want to address in the future. First, we used 1K samples
for each languages to evaluate Codex generated documentation. Though the
sample size is statistically significant, we intend to test Codex on more
samples in the future. Second, we limited our investigation only to zero and
one-shot learning. We will extend the investigation by also analyzing few-shot
learning. Third, we randomly picked one sample from the corresponding train
set to use it in the one-shot learning. However, using different samples in
one-shot learning might yield different outcome which has not been explored.
Fourth, like other pre-trained transformer models, GPT-3 also supports fine-
tuning. However, latest versions of GPT-3 models (e.g., text-davinci, Codex)
are not available for fine-tuning. We could fine-tune GPT-3 when it is
available to do so. Finally, systematic investigation of the effect of
different parameters associated with GPT-3 has not been done in this study. We
picked the parameter values based on the official documentation.

Acknowledgement. This work was funded by Natural Sciences and Engineering
Research Council of Canada, University of Calgary, Alberta Innovates, and
Alberta Graduate Excellence Scholarship.

## References

  * (1)
  * Abid et al. (2015) Nahla J Abid, Natalia Dragan, Michael L Collard, and Jonathan I Maletic. 2015.  Using stereotypes in the automatic generation of natural language summaries for c++ methods. In _2015 IEEE International Conference on Software Maintenance and Evolution (ICSME)_. IEEE, 561–565.
  * Aghajani et al. (2020) Emad Aghajani, Csaba Nagy, Mario Linares-Vásquez, Laura Moreno, Gabriele Bavota, Michele Lanza, and David C. Shepherd. 2020.  Software Documentation: The Practitioners’ Perspective. In _42nd International Conference on Software Engineering_. 12.
  * Aghajani et al. (2019) Emad Aghajani, Csaba Nagy, Olga Lucero Vega-Márquez, Mario Linares-Vásquez, Laura Moreno, Gabriele Bavota, and Michele Lanza. 2019\.  Software documentation issues unveiled. In _41st International Conference on Software Engineering_. 1199–1210.
  * Ahmad et al. (2020) Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. 2020.  A transformer-based approach for source code summarization.  _arXiv preprint arXiv:2005.00653_ (2020).
  * Ahmad et al. (2021) Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. 2021.  Unified pre-training for program understanding and generation.  _arXiv preprint arXiv:2103.06333_ (2021).
  * Allamanis et al. (2016) Miltiadis Allamanis, Hao Peng, and Charles Sutton. 2016\.  A convolutional attention network for extreme summarization of source code. In _International conference on machine learning_. PMLR, 2091–2100.
  * Barone and Sennrich (2017) Antonio Valerio Miceli Barone and Rico Sennrich. 2017.  A parallel corpus of python functions and documentation strings for automated code documentation and code generation.  _arXiv preprint arXiv:1707.02275_ (2017).
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020\.  Language models are few-shot learners.  _Advances in neural information processing systems_ 33 (2020), 1877–1901.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021\.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Chen and Zhou (2018) Qingying Chen and Minghui Zhou. 2018.  A neural framework for retrieval and summarization of source code. In _2018 33rd IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 826–831.
  * Chintagunta et al. (2021) Bharath Chintagunta, Namit Katariya, Xavier Amatriain, and Anitha Kannan. 2021.  Medically aware GPT-3 as a data generator for medical dialogue summarization. In _Machine Learning for Healthcare Conference_. PMLR, 354–372.
  * Chiu and Alexander (2021) Ke-Li Chiu and Rohan Alexander. 2021.  Detecting hate speech with gpt-3.  _arXiv preprint arXiv:2103.12407_ (2021).
  * Dale (2021) Robert Dale. 2021\.  GPT-3: What’s it good for?  _Natural Language Engineering_ 27, 1 (2021), 113–118.
  * de Souza et al. (2005) Sergio Cozzetti B. de Souza, Nicolas Anquetil, and Káthia M. de Oliveira. 2005.  A study of the documentation essential to software maintenance. In _23rd annual international conference on Design of communication: documenting & designing for pervasive information_. 68–75.
  * DuBay (2004) William H DuBay. 2004\.  The principles of readability.  _Online Submission_ (2004).
  * Eddy et al. (2013) Brian P Eddy, Jeffrey A Robinson, Nicholas A Kraft, and Jeffrey C Carver. 2013.  Evaluating source code summarization techniques: Replication and expansion. In _2013 21st International Conference on Program Comprehension (ICPC)_. IEEE, 13–22.
  * Feng et al. (2020) Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al. 2020\.  Codebert: A pre-trained model for programming and natural languages.  _arXiv preprint arXiv:2002.08155_ (2020).
  * Finnie-Ansley et al. (2022) James Finnie-Ansley, Paul Denny, Brett A Becker, Andrew Luxton-Reilly, and James Prather. 2022\.  The Robots Are Coming: Exploring the Implications of OpenAI Codex on Introductory Programming. In _Australasian Computing Education Conference_. 10–19.
  * Floridi and Chiriatti (2020) Luciano Floridi and Massimo Chiriatti. 2020.  GPT-3: Its nature, scope, limits, and consequences.  _Minds and Machines_ 30, 4 (2020), 681–694.
  * Gao et al. (2021) Shuzheng Gao, Cuiyun Gao, Yulan He, Jichuan Zeng, Lun Yiu Nie, and Xin Xia. 2021\.  Code structure guided transformer for source code summarization.  _arXiv preprint arXiv:2104.09340_ (2021).
  * Haiduc et al. (2010a) Sonia Haiduc, Jairo Aponte, and Andrian Marcus. 2010a.  Supporting program comprehension with source code summarization. In _2010 acm/ieee 32nd international conference on software engineering_ , Vol. 2. IEEE, 223–226.
  * Haiduc et al. (2010b) Sonia Haiduc, Jairo Aponte, Laura Moreno, and Andrian Marcus. 2010b.  On the use of automated text summarization techniques for summarizing source code. In _2010 17th Working Conference on Reverse Engineering_. IEEE, 35–44.
  * Hu et al. (2018) Xing Hu, Ge Li, Xin Xia, David Lo, and Zhi Jin. 2018.  Deep code comment generation. In _2018 IEEE/ACM 26th International Conference on Program Comprehension (ICPC)_. IEEE, 200–20010.
  * Hu et al. (2020) Xing Hu, Ge Li, Xin Xia, David Lo, and Zhi Jin. 2020.  Deep code comment generation with hybrid lexical and syntactical information.  _Empirical Software Engineering_ 25, 3 (2020), 2179–2217.
  * Husain et al. (2019) Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt. 2019.  Codesearchnet challenge: Evaluating the state of semantic code search.  _arXiv preprint arXiv:1909.09436_ (2019).
  * Ibrahim et al. (2012) Walid M Ibrahim, Nicolas Bettenburg, Bram Adams, and Ahmed E Hassan. 2012.  On the relationship between comment update practices and software bugs.  _Journal of Systems and Software_ 85, 10 (2012), 2293–2304.
  * Iyer et al. (2016) Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. 2016.  Summarizing source code using a neural attention model. In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. 2073–2083.
  * Jackson and Saenz (2022) Ilya Jackson and Maria Jesus Saenz. 2022.  From Natural Language to Simulations: Applying GPT-3 Codex to Automate Simulation Modeling of Logistics Systems.  _arXiv preprint arXiv:2202.12107_ (2022).
  * Khan et al. (2021) Junaed Younus Khan, Md Tawkat Islam Khondaker, Gias Uddin, and Anindya Iqbal. 2021.  Automatic detection of five api documentation smells: Practitioners’ perspectives. In _2021 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 318–329.
  * Lin and Och (2004) Chin-Yew Lin and Franz Josef Och. 2004.  Orange: a method for evaluating automatic evaluation metrics for machine translation. In _COLING 2004: Proceedings of the 20th International Conference on Computational Linguistics_. 501–507.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_ (2019).
  * Lu et al. (2021) Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al. 2021\.  Codexglue: A machine learning benchmark dataset for code understanding and generation.  _arXiv preprint arXiv:2102.04664_ (2021).
  * McBurney et al. (2017) Paul W McBurney, Siyuan Jiang, Marouane Kessentini, Nicholas A Kraft, Ameer Armaly, Mohamed Wiem Mkaouer, and Collin McMillan. 2017\.  Towards prioritizing documentation effort.  _IEEE Transactions on Software Engineering_ 44, 9 (2017), 897–913.
  * McBurney and McMillan (2014) Paul W McBurney and Collin McMillan. 2014.  Automatic documentation generation via source code summarization of method context. In _Proceedings of the 22nd International Conference on Program Comprehension_. 279–290.
  * Moreno et al. (2013) Laura Moreno, Jairo Aponte, Giriprasad Sridhara, Andrian Marcus, Lori Pollock, and K Vijay-Shanker. 2013.  Automatic generation of natural language summaries for java classes. In _2013 21st International Conference on Program Comprehension (ICPC)_. IEEE, 23–32.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002\.  Bleu: a method for automatic evaluation of machine translation. In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_. 311–318.
  * Parnas (2011) David Lorge Parnas. 2011\.  Precise documentation: The key to better software.  In _The Future of Software Engineering_. Springer, 125–148.
  * Parvez et al. (2021) Md Rizwan Parvez, Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang. 2021\.  Retrieval Augmented Code Generation and Summarization.  _arXiv preprint arXiv:2108.11601_ (2021).
  * Pearce et al. (2021) Hammond Pearce, Benjamin Tan, Baleegh Ahmad, Ramesh Karri, and Brendan Dolan-Gavitt. 2021.  Can OpenAI Codex and Other Large Language Models Help Us Fix Security Bugs?  _arXiv preprint arXiv:2112.02125_ (2021).
  * Phan et al. (2021) Long Phan, Hieu Tran, Daniel Le, Hieu Nguyen, James Anibal, Alec Peltekian, and Yanfang Ye. 2021.  Cotext: Multi-task learning with code-text transformer.  _arXiv preprint arXiv:2105.08645_ (2021).
  * Prenner and Robbes (2021) Julian Aron Prenner and Romain Robbes. 2021.  Automatic Program Repair with OpenAI’s Codex: Evaluating QuixBugs.  _arXiv preprint arXiv:2111.03922_ (2021).
  * Rai et al. (2022) Sawan Rai, Ramesh Chandra Belwal, and Atul Gupta. 2022\.  A Review on Source Code Documentation.  _ACM Transactions on Intelligent Systems and Technology (TIST)_ (2022).
  * Rai et al. (2017) Sawan Rai, Tejaswini Gaikwad, Sparshi Jain, and Atul Gupta. 2017.  Method level text summarization for java code using nano-patterns. In _2017 24th Asia-Pacific Software Engineering Conference (APSEC)_. IEEE, 199–208.
  * Rastkar et al. (2011) Sarah Rastkar, Gail C Murphy, and Alexander WJ Bradley. 2011\.  Generating natural language summaries for crosscutting source code concerns. In _2011 27th IEEE International Conference on Software Maintenance (ICSM)_. IEEE, 103–112.
  * Robillard (2009) Martin P. Robillard. 2009\.  What Makes APIs Hard to Learn? Answers from Developers.  _IEEE Software_ 26, 6 (2009), 26–34.
  * Schreck et al. (2007) Daniel Schreck, Valentin Dallmeier, and Thomas Zimmermann. 2007\.  How documentation evolves over time. In _Ninth international workshop on Principles of software evolution: in conjunction with the 6th ESEC/FSE joint meeting_. 4–10.
  * Sridhara et al. (2010) Giriprasad Sridhara, Emily Hill, Divya Muppaneni, Lori Pollock, and K Vijay-Shanker. 2010.  Towards automatically generating summary comments for java methods. In _Proceedings of the IEEE/ACM international conference on Automated software engineering_. 43–52.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014\.  Sequence to sequence learning with neural networks.  _Advances in neural information processing systems_ 27 (2014).
  * Uddin et al. (2022) Gias Uddin, Omar Alam, and Alexander Serebrenik. 2022\.  A qualitative study of developers’ discussions of their problems and joys during the early COVID-19 months.  _Empirical Software Engineering_ 27, 5 (2022), 1–52.
  * Uddin et al. (2012) Gias Uddin, Barthélémy Dagenais, and Martin P. Robillard. 2012.  Temporal Analysis of API Usage Concepts. In _Proc. 34th IEEE/ACM Intl. Conf. on Software Engineering_. 804–814.
  * Uddin et al. (2021) Gias Uddin, Foutse Khomh, and Chanchal K Roy. 2021.  Automatic API Usage Scenario Documentation from Technical Q&A Sites.  _ACM Transactions on Software Engineering and Methodology_ 30, 3 (2021), 1–45.
  * Uddin and Robillard (2015) Gias Uddin and Martin P. Robillard. 2015.  How API Documentation Fails.  _IEEE Softawre_ 32, 4 (2015), 76–83.
  * Vassallo et al. (2014) Carmine Vassallo, Sebastiano Panichella, Massimiliano Di Penta, and Gerardo Canfora. 2014\.  Codes: Mining source code descriptions from developers discussions. In _Proceedings of the 22nd International Conference on Program Comprehension_. 106–109.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  _Advances in neural information processing systems_ 30 (2017).
  * Wan et al. (2018) Yao Wan, Zhou Zhao, Min Yang, Guandong Xu, Haochao Ying, Jian Wu, and Philip S Yu. 2018.  Improving automatic source code summarization via deep reinforcement learning. In _Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering_. 397–407.
  * Wang et al. (2020) Ruyun Wang, Hanwen Zhang, Guoliang Lu, Lei Lyu, and Chen Lyu. 2020.  Fret: Functional reinforced transformer with bert for code summarization.  _IEEE Access_ 8 (2020), 135591–135604.
  * Wong et al. (2015) Edmund Wong, Taiyue Liu, and Lin Tan. 2015.  Clocom: Mining existing source code for automatic comment generation. In _2015 IEEE 22nd International Conference on Software Analysis, Evolution, and Reengineering (SANER)_. IEEE, 380–389.
  * Wong et al. (2013) Edmund Wong, Jinqiu Yang, and Lin Tan. 2013.  Autocomment: Mining question and answer sites for automatic comment generation. In _2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE)_. IEEE, 562–567.
  * Xia et al. (2017) Xin Xia, Lingfeng Bao, David Lo, Zhenchang Xing, Ahmed E Hassan, and Shanping Li. 2017\.  Measuring program comprehension: A large-scale field study with professionals.  _IEEE Transactions on Software Engineering_ 44, 10 (2017), 951–976.