User:Hakerh400/TFNP

This is still a work in progress. It may be changed in the future.

TFNP (stands for Totally Fair Negotiation Protocol) is a concept invented by User:Hakerh400 for determining what actions should be taken based on some external event. This concept is a part of a much larger project (the author did not decide yet what the name of the project will be). The project is something like an advanced interactive simulator for discrete systems (something like cellular automata, but in which all cells are Turing machines), but the interactive part means that user interactions (or even multiplayer interactions) can be applied.

In this article we do not explain anything in details and we do not provide any formal specifications. This article is more like an idea that can be integrated in various systems.

Problem

The problem TFNP tries to solve is the problem of deciding what to do based on an event that happened in the system. Basically, we have a system with a lot of entities. Each entity has its own needs (what it wants to achieve or do) and they all interact with each other. The problem is that a common situation is when two or more entities want to perform different actions that cannot co-exist. For example, if one entity wants to open the door and the other wants to close the door, we need some way to determine which action (if any) will be performed and why, based on the parameters of the entities.

Comparison with democracy

When talking about deciding what to do, one may think about democracy. By democracy we mean some sort of a voting system in which each entity can give a vote for the action it wants to be performed. Then the system counts all the votes and performs the action that received the most votes. However, while the effectiveness of conflict solving via democracy voting systems is disputable in real-world scenarios, the author of TFNP believes that in a virtual, simulated systems there are better decision making algorithms than democracy for several reasons:

• In democracy each vote weights equaly. Even if we exclude some entities (for example, like in real-world democracy systems in which kids cannot vote in elections), there are still a lot of entities who are not equaly competent to advocate, or even understand their own vote.
• Not everyone understands the topic. If the event that happened is strictly related to a specific topic, the entities that do not understand that topic should not vote, which is against democracy principles and not always applicable in a real-world democracy systems. In virtual, simulated systems we want to prevent spam of votes coming from entities that neither understand the topic, nor are they concerned with the event that happened.
• Not everyone is interested in each event. For example, if we want to strictly follow democracy rules and to force everyone to give a vote for an action for each event that happens, it would require a lot of time and resources, and will unnecessarily encumber entities that could do some other useful stuff in the meantime. In TFNP we introduce event listeners and only entities that listen for a specific event will react to it.
• Not everyone should know everything. Instead of performing a poll on the entire system, we create a lot of separated polls. In each poll only a small amount of entities can participate and information between polls can be shared only in a restricted manner. Real-world example: you own a company and you organize a survey for your employees to determine what your organization should do next. The results of that survey can help you understand the needs of your employees, so you can better decide what vote you should make on some meeting with owners of other organizations, but you do not share all survey information with them. However, this relation does not necessarily need to be hierarchical, but it should be modular.
• Democracy suffers from corruption. It means that if some entity really wants something to happen and the entity suspects that there will not be enough votes for that action, it can bribe others to vote for the thing it likes, especially if they do not understand the topic they are asked to vote for, or if they do not care for the poll results. That would require the entity to have resources to bribe others, but even the fact that it is usually expected that some entities are more powerful than others in terms of owned reosurces, it is still a sign of a bad voting system if the resources can influence the results of voting.
• People may change opinion based on other votes. This is actually a good thing, but democracy does not support it. TFNP allows voting participants to partially see the results of voting before the voting actually ends. This may yield changing of already given vote. Furthermore, it can cause changes of all votes that are given by entities who are influenced by that vote. However, TFNP provides a mechanism for preventing infinite loops.
• The only solution democracy provides for resolving ties on elections is to repeat the election. In bigger systems with thousands or millions of entities this is not a problem, because a lot of things can happen in the meantime (between two elections). However, as we already said, in modular systems where we have a lot of smaller groups and a poll in each of them, there is a big chance that some of the polls will result in identical tie (equal number of votes for two or more actions) over and over again. TFNP provides a way for resolving this problem by a two-step algorithm.

For the abovementioned reasons, we conclude that democracy is not an ideal voting mechanism and that we should invent a better mechanism. TFNP is intended for virtual, simulated systems, but we also compare it with real-world situations to show that it may be applicable in real-world decision making events.

Terminology

Entity

Entities are active components of the system. They can perform actions and interact with each other. Each entity has several parameters, among which are priority and the set of event listeners. Priority is a quantity that describes how "strong" the entity is. In other words, if there is a conflict (two or more entities want to perform mutually exclusive actions), the system will permit the action which is created by the entity with the highest priority. An entity can create other entities, but it can delegate them only smaller or equal priority than itself. An entity can decrease its own priority, but cannot increase it. An entity can increase priority of other entities, but not higher than its own priority.

Event

Event is something that happens outside the system and the participants in the system can only observe the event once it happens. It is an external stimulus that evokes reactions of some entities in the system. It can be a user interaction event (like a key press, mouse click, etc), it can be a timer even (a scheduled timer fires once after a certain timeout, or each time after a certain time interval), a new player joined (in case of a multiplayer implementation), etc.

Event target

Event target is source of events of a certain type. Each event instance is bound to exactly one event target. For example, keyboard is an event target and it emits events of key press type. Entity is also an event target and it may emit events like entity creation, deletion, movement, property change, etc.

Event listener

Each entity can define a number of event listeners. Event listener is bound to a specific event target and it represents a sort of a function that is executed in the context of the entity who created that event listener when an event of certain type is emitted by that event target. There may be some constraints regarding which entity can define which event listeners for which targets.

Negotiation

Negotiation is a process which gets triggered by a single event and encompasses all proposals that are created by entities who directly or indirectly react to that event. Negotiation ends when no more entities want to create new proposals, or the system prevents creating new proposals to prevent infinite loops. Each negotiation has a proposal container. When a negotiation ends, it yields zero or more actions.

Proposal container

It is bound to a single negotiation and contains proposals. Proposals can be added, but cannot be removed from a proposal container.

Proposal

When an event listener is invoked, the entity who defined that listener creates zero or more proposals and adds them to the proposal container of the current negotiation. A proposal can then trigger event listeners of other entities (a proposal is like an event, but the entities who react to them know that they are only proposals and not committed yet). Each proposal has a priority, which is set by the entity who created it and that priority can only be lower or equal to the priority of the entity who created it. Proposals cannot be deleted. If an entity wants to cancel its own proposal, or some other proposal that has lower or equal priority than the entity itself, the entity must create a new canceling proposal targeting the original one. There are several different types of proposals:

• Action request: An entity wants to perform an action which modifies the system in some way (create, delete, move, or edit entities, display something on the screen, change some system parameters, etc).
• Canceling proposal: An entity wants to cancel a previously created proposal, which is created either by that entity, or some other entity.
• Upgrade: An entity accepts some previously created proposal, but it wants to do something after the proposal is committed as an action. Real-world example: Bob wants to go to the store and buy a beer, while Alice also wants to go to the store, but she wants to buy a chocolate. Alice does not need to cancels Bob's request. She can simply tell him to buy both a beer and a chocolate.
• Merge: An entity detects two identical, or very similar proposals and wants to merge them in a single proposal. Real-world example: the light bulb in your room burned out, so you decided to buy a new light bulb. You live with a college roommate, who also decides to buy a new light bulb. However, since you live in the same room, you don't need two light bulbs, one is enough.

Each proposal triggers all event listeners that would react to that proposal like it is an event, or the entities who defined them created the proposal which is being altered by this proposal. New proposals are added in iterations, and in each iteration the system enumerates all the entities who react to the current proposal container state and execute their event listeners simultaneously. All new proposals are then added to the container. This is repeat until no new proposals are generated. Then the negotiation ends and the system enumerates all proposals that are not in a conflict and turns them into actions that are then committed.