Distributed algorithmic mechanism design

Distributed algorithmic mechanism design (DAMD) is an extension of algorithmic mechanism design.

DAMD differs from Algorithmic mechanism design since the algorithm is computed in a distributed manner rather than by a central authority. This greatly improves computation time since the burden is shared by all agents within a network

One major obstacle in DAMD is ensuring that agents reveal the true costs or preferences related to a given scenario. Often these agents would rather lie in order to improve his or her own utility. DAMD is full of new challenges since one can no longer assume an obedient networking and mechanism infrastructure where rational players control the message paths and mechanism computation.

Game Theoretic Model

Distributed computing and game theory are interested in much the same problems which is dealing with systems where there are many agents, facing uncertainty, and having possibly different goals. However, in distributed computing, the focus has been on problems such as fault tolerance, asynchrony, and proving correctness of algorithms; in game theory, the focus has been on strategic concerns.

Nash equilibrium

Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However Nash equilibrium does not deal with faulty or unexpected behavior. A protocol that reaches Nash equilibrium is guaranteed to execute correctly in the face of rational agents, with no agent being able to improve its utility by deviating from the protocol.

Solution Preference

We assume there is no trusted center like in AMD, mechanism must be done by the agents themselves. However, we do presume the existence of some central enforcer whose responsibility is to implement the outcome decided. The enforcer can impose severe penalties if the agents do not agree on an outcome or fail the algorithm. In other words, agents cannot gain if the algorithm fails. As a result, though agents have preferences, they have no incentive to fail the algorithm.

See also

• Algorithmic mechanism design
• Mechanism design
• Game theory
• Distributed computing

External links

• [1] Distributed Algorithmic Mechanism Design: Recent Results and Future Directions
• [2] Distributed algorithmic mechanism design and network security
• [3] Service Allocation in Selfish Mobile Ad Hoc Networks Using Vickrey Auction