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
Game theory and distributed computing both deal with a system with many agents, in which the agents may possibly pursue different goals. However they have different focuses. For instance one of the concerns of distributed computing is to prove the correctness of algorithms for tolerance of faulty agents and concurrency of agents. Whereas In game theory the focus is on devising a strategy which leads us to an equilibrium in the system. [1]
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.[2]
Solution Preference
There is no trusted center like in AMD, mechanism must be done by the agents themselves. However, we have a central enforcer whose responsibility is to force agents decide on an outcome. The enforcer can impose severe penalties if the agents do not agree on an outcome or fail the algorithm. In other words, as Yehuda Afek et. Al. said “agents cannot gain if the algorithm fails”[3]. As a result, though agents have preferences, they have no incentive to fail the algorithm.
Truthfulness
A mechanism consider to be truthful if agents don’t intend to lie in the system and gain nothing by lying about their or other agents values. For example, imagine we have a leader election algorithm to select a computation server in a network. The leader have to run some CPU-intensive tasks. The designer specify an algorithm which agents should send their computation power, and the most powerful agent will be chosen to do the task. In this algorithm agents may lie and did not participate truthfully since by saying the true computation power, agents are in danger of being tasked with a CPU intensive jobs that will take their local job resources. To overcome this, truthful mechanisms should design and regardless of any a-priori knowledge of the inputs make agent to be truthful.[4]
A well-known truthful mechanism in game theory is Vickrey auction
Classic distributed computing problems
Leader Election(Completely connected network, synchronous case)
Leader election Leader election is a fundamental problem in distributed computing. Not surprisingly, there are numerous protocols for this problem. The agents are assumed to be rational and according to the solution preference all the agents prefer to have a leader to not having a leader. The agents also have different preferences regarding who becomes the leader (an agent may prefer that he himself becomes the leader). Since agents have an incentive to lie about their id to improve their utility, The standard protocols which assume that each agent has a distinct id, and electing the agent with the lowest or the highest id, as the leader do not work;
The protocol for leader election in the presence of rational agents which is introduced by Ittai et al. is :
- At round 1, each agent i sends everyone his id;
- At round 2, i sends each other agent j the set of ids that he (i) has received (including his own). If the sets received by agent i are not all identical or if i does not receive an id from some agent, then i sets its output to Null, and leader election fails. Otherwise, let n be the cardinality of the set of ids.
- Agent i chooses a random number Ni in {0, ..., n-1} and sends it to all the other agents.
- Each agent i then computes ∑i=1n Ni (mod n), and then takes the agent with the Nth highest id in the set to be the leader. (If some agent j does not send i a random number, then i sets its output to Null.)
This protocol correctly elects a leader while reaching equilibrium is truthful since no agent can benefit by lying about its input[5].
See also
References
- ^ Halpern, Joseph Y. (2008). "Computer science and game theory: A brief survey". The New Palgrave Dictionary of Economics.
- ^ Martin, Osborne; Rubinstein, Ariel (1994). A course in game theory. MIT press.
- ^ Afek, Yehuda; Ginzberg, Yehonatan; Feibish, Shir Landau; Sulamy, Moshe (2014). "Distributed computing building blocks for rational agents". PODC '14 Proceedings of the 2014 ACM symposium on Principles of distributed computing.
- ^ hneidman, Jeffrey; Parkes, David (2004). "Specification faithfulness in networks with rational nodes". twenty-third annual ACM symposium on principles of distributed computing: PODC.
- ^ Abraham, Ittai; Dolev, Danny (2013). "Distributed Protocols for Leader Election: a Game-Theoretic Perspective". DISC: 61–75.