Systems
I implemented the following systems to make some of my NPCs lie:
Trait System
When each NPC is generated they are randomly assigned personality traits. I suggest using weighted randomness for more control over which traits show up more often. One of the traits that a NPC can get is the Liar trait.
Memory System
Each NPC has a memory which is a dictionary that contains other dictionaries. For example, inside of NPC.memory there is a dictionary called aliases. The aliases dictionary contains all of the aliases of the other NPCs that they know the alias of.
Conversation System
Aside from making the game world feel more alive, the main point of the conversation system is to share information, both correct and incorrect information. If NPC A asks NPC B, who has the Liar trait, what their name (alias) is, NPC B will randomly pick a name from a list of possible names to give to NPC A. If NPC B's actual name is in that list of names, there's a chance that it will be selected and NPC A will get their true name. Otherwise, the wrong name will be given. Regardless of whether or not NPC A receives the correct name, the name is saved in NPC A's memory. From now on, NPC A will use that name to refer to NPC B when talking to them and talking about them.
Example Scenario
Let's assume that NPC A is a gang member who is looking for someone who killed a fellow member and they ask NPC B if they happen to know who did it. NPC B doesn't know who did it but they randomly give NPC A the name of one of the people they have in their memory. With that false information, NPC A leaves to find and exact revenge on the wrong person. If that wrong person is in a different gang, the situation has the possibility to spiral into a gang war, all because of NPC B's lie.