Distributed algorithmic mechanism design

Last updated

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

Contents

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 their 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 that tolerate faulty agents and agents performing actions concurrently. On the other hand, 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, the 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 as there is in AMD. Thus, mechanisms must be implemented by the agents themselves. The solution preference assumption requires that each agent prefers any outcome to no outcome at all: thus, agents have no incentive to disagree on an outcome or cause the algorithm to fail. In other words, as 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 is considered to be truthful if the agents gain nothing by lying about their or other agents' values. A good example would be a leader election algorithm that selects a computation server within a network. The algorithm specifies that agents should send their total computational power to each other, after which the most powerful agent is chosen as the leader to complete the task. In this algorithm agents may lie about their true computation power because they are potentially in danger of being tasked with CPU-intensive jobs which will reduce their power to complete local jobs. This can be overcome with the help of truthful mechanisms which, without any a priori knowledge of the existing data and inputs of each agent, cause each agent to respond truthfully to requests. [4]

A well-known truthful mechanism in game theory is the Vickrey auction.

Classic distributed computing problems

Leader election (completely connected network, synchronous case)

Leader election is a fundamental problem in distributed computing and there are numerous protocols to solve this problem. System agents are assumed to be rational, and therefore prefer having a leader to not having one. The agents may also have different preferences regarding who becomes the leader (an agent may prefer that he himself becomes the leader). Standard protocols may choose leaders based on the lowest or highest ID of system agents. However, since agents have an incentive to lie about their ID in order to improve their utility such protocols are rendered useless in the setting of algorithmic mechanism design.
A protocol for leader election in the presence of rational agents has been introduced by Ittai et al.:

This protocol correctly elects a leader while reaching equilibrium and is truthful since no agent can benefit by lying about its input. [5]

See also

Related Research Articles

<span class="mw-page-title-main">Mechanism design</span> Field of economics and game theory

Mechanism design is a branch of economics and game theory. It studies how to construct rules—called mechanisms or institutions—that produce good outcomes according to some predefined metric, even when the designer does not know the players' true preferences or what information they have. Mechanism design thus focuses on the study of solution concepts for a class of private-information games.

In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information, and the strategy space of each player consists of the possible information values, a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility.

<span class="mw-page-title-main">Double auction</span> Process of buying and selling goods

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

The revelation principle is a fundamental result in mechanism design, social choice theory, and game theory which shows it is always possible to design a strategy-resistant implementation of a social decision-making mechanism. It can be seen as a kind of mirror image to Gibbard's theorem. The revelation principle says that if a social choice function can be implemented with some non-honest mechanism—one where players have an incentive to lie—the same function can be implemented by an incentive-compatible (honesty-promoting) mechanism with the same equilibrium outcome (payoffs).

Agent-based computational economics (ACE) is the area of computational economics that studies economic processes, including whole economies, as dynamic systems of interacting agents. As such, it falls in the paradigm of complex adaptive systems. In corresponding agent-based models, the "agents" are "computational objects modeled as interacting according to rules" over space and time, not real people. The rules are formulated to model behavior and social interactions based on incentives and information. Such rules could also be the result of optimization, realized through use of AI methods.

Implementation theory is an area of research in game theory concerned with whether a class of mechanisms can be designed whose equilibrium outcomes implement a given set of normative goals or welfare criteria.

Algorithmic mechanism design (AMD) lies at the intersection of economic game theory, optimization, and computer science. The prototypical problem in mechanism design is to design a system for multiple self-interested participants, such that the participants' self-interested actions at equilibrium lead to good system performance. Typical objectives studied include revenue maximization and social welfare maximization. Algorithmic mechanism design differs from classical economic mechanism design in several respects. It typically employs the analytic tools of theoretical computer science, such as worst case analysis and approximation ratios, in contrast to classical mechanism design in economics which often makes distributional assumptions about the agents. It also considers computational constraints to be of central importance: mechanisms that cannot be efficiently implemented in polynomial time are not considered to be viable solutions to a mechanism design problem. This often, for example, rules out the classic economic mechanism, the Vickrey–Clarke–Groves auction.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

<span class="mw-page-title-main">Market design</span>

Market design is an interdisciplinary, engineering-driven approach to economics and a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In market design, the focus is on the rules of exchange, meaning who gets allocated what and by what procedure. Market design is concerned with the workings of particular markets in order to fix them when they are broken or to build markets when they are missing. Practical applications of market design theory has included labor market matching, organ transplantation, school choice, university admissions, and more.

Incentive-centered design (ICD) is the science of designing a system or institution according to the alignment of individual and user incentives with the goals of the system. Using incentive-centered design, system designers can observe systematic and predictable tendencies in users in response to motivators to provide or manage incentives to induce a greater amount and more valuable participation. ICD is often considered when designing a system to induce desirable behaviors from users, such as participation and cooperation. It draws from principles in various areas such as economics, psychology, sociology, design, and engineering. ICD has been gaining attention in research communities due to the role it can play in helping systems benefit their users and ultimately achieve better results.

In mechanism design, the Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially optimal solution whenever monetary transfers are available. It generalizes the Vickrey–Clarke–Groves auction into a general-purpose mechanism for social choice, which can be used to select any outcome from a set of possible outcomes. However, the VCG mechanism also has several problems which keep it from fully solving the public goods problem, including its vulnerability to collusion and the issue of participants failing to pay their bids.

A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of these variables.

In game theory, asynchrony occurs when gameplay does not proceed in consistently paced rounds. A system is synchronous if agents in a game move in lockstep according to a global timing system, whereas "in an asynchronous system, there is no global clock. The agents in the system can run at arbitrary rates relative to each other."

Strategic fair division studies problems of fair division, in which participants cooperate to subdivide goods or resources fairly, from a point of view in which the participants are assumed to hide their preferences and act strategically in order to maximize their own utility, rather than playing sincerely according to their true preferences.

Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake.

Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources.

Course allocation is the problem of allocating seats in university courses among students. Many universities impose an upper bound on the number of students allowed to register to each course, in order to ensure that the teachers can give sufficient attention to each individual student. Since the demand for some courses is higher than the upper bound, a natural question is which students should be allowed to register to each course.

Amir Ronen is an Israeli computer scientist.

References

  1. ↑ Halpern, Joseph Y. (2008). "Computer science and game theory: A brief survey". The New Palgrave Dictionary of Economics. doi:10.1057/978-1-349-95121-5_2133-1.
  2. ↑ Martin, Osborne; Rubinstein, Ariel (1994). A course in game theory. MIT press.
  3. ↑ Afek, Yehuda; Ginzberg, Yehonatan; Feibish, Shir Landau; Sulamy, Moshe (2014). "Distributed computing building blocks for rational agents". Proceedings of the 2014 ACM symposium on Principles of distributed computing. pp. 406–415. doi:10.1145/2611462.2611481. ISBN   9781450329446. S2CID   2048291.
  4. ↑ Shneidman, Jeffrey; Parkes, David (2004). "Specification faithfulness in networks with rational nodes". Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. p. 88. doi:10.1145/1011767.1011781. ISBN   1581138024. S2CID   5518144.
  5. ↑ Abraham, Ittai; Dolev, Danny (2013). "Distributed Protocols for Leader Election: a Game-Theoretic Perspective". DISC: 61–75.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.