Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Mechanism Design for Multicast Transmission
77
0
0.0
(
0
)
Added by
Nasimeh Heydaribeni
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the standard Mechanism Design framework (Hurwicz-Reiter), there is a central authority that gathers agents messages and subsequently determines the allocation and tax for each agent. We consider a scenario where, due to communication overhead and other constraints, such broadcasting of messages to a central authority cannot take place. Instead, only local message exchange is allowed between agents. As a result, each agent should be able to determine her own allocation and tax based on the messages in the local neighborhood, as defined by a given message graph describing the communication constraints. This scenario gives rise to a novel research direction that we call Distributed Mechanism Design. In this paper, we propose such a distributed mechanism for the problem of rate allocation in a multicast transmission network. The proposed mechanism fully implements the optimal allocation in Nash equilibria and its message space dimension is linear with respect to the number of agents in the network.
rate research
Read More
We describe a structured system for distributed mechanism design. It consists of a sequence of layers. The lower layers deal with the operations relevant for distributed computing only, while the upper layers are concerned only with communication among players, including broadcasting and multicasting, and distributed decision making. This yields a highly flexible distributed system whose specific applications are realized as instances of its top layer. This design supports fault-tolerance, prevents manipulations and makes it possible to implement distributed policing. The system is implemented in Java. We illustrate it by discussing a number of implemented examples.
In the standard Mechanism Design framework, agents messages are gathered at a central point and allocation/tax functions are calculated in a centralized manner, i.e., as functions of all network agents messages. This requirement may cause communication and computation overhead and necessitates the design of mechanisms that alleviate this bottleneck. We consider a scenario where message transmission can only be performed locally so that the mechanism allocation/tax functions can be calculated in a decentralized manner. Each agent transmits messages to her local neighborhood, as defined by a given message-exchange network, and her allocation/tax functions are only functions of the available neighborhood messages. This scenario gives rise to a novel research problem that we call Distributed Mechanism Design. In this paper, we propose two distributed mechanisms for network utility maximization problems that involve private and public goods with competition and cooperation between agents. As a concrete example, we use the problems of rate allocation in networks with either unicast or multirate multicast transmission protocols. The proposed mechanism for each of the protocols fully implements the optimal allocation in Nash equilibria and its message space dimensionality scales linearly with respect to the number of agents in the network.
A distributed machine learning platform needs to recruit many heterogeneous worker nodes to finish computation simultaneously. As a result, the overall performance may be degraded due to straggling workers. By introducing redundancy into computation, coded machine learning can effectively improve the runtime performance by recovering the final computation result through the first $k$ (out of the total $n$) workers who finish computation. While existing studies focus on designing efficient coding schemes, the issue of designing proper incentives to encourage worker participation is still under-explored. This paper studies the platforms optimal incentive mechanism for motivating proper workers participation in coded machine learning, despite the incomplete information about heterogeneous workers computation performances and costs. A key contribution of this work is to summarize workers multi-dimensional heterogeneity as a one-dimensional metric, which guides the platforms efficient selection of workers under incomplete information with a linear computation complexity. Moreover, we prove that the optimal recovery threshold $k$ is linearly proportional to the participator number $n$ if we use the widely adopted MDS (Maximum Distance Separable) codes for data encoding. We also show that the platforms increased cost due to incomplete information disappears when worker number is sufficiently large, but it does not monotonically decrease in worker number.
We consider revenue-optimal mechanism design in the interdimensional setting, where one dimension is the value of the buyer, and one is a type that captures some auxiliary information. One setting is the FedEx Problem, for which FGKK [2016] characterize the optimal mechanism for a single agent. We ask: how far can such characterizations go? In particular, we consider single-minded agents. A seller has heterogenous items. A buyer has a value v for a specific subset of items S, and obtains value v iff he gets (at least) all the items in S. We show: 1. Deterministic mechanisms are optimal for distributions that satisfy the declining marginal revenue (DMR) property; we give an explicit construction of the optimal mechanism. 2. Without DMR, the result depends on the structure of the directed acyclic graph (DAG) representing the partial order among types. When the DAG has out-degree at most 1, we characterize the optimal mechanism a la FedEx. 3. Without DMR, when the DAG has some node with out-degree at least 2, we show that in this case the menu complexity is unbounded: for any M, there exist distributions over (v,S) pairs such that the menu complexity of the optimal mechanism is at least M. 4. For the case of 3 types, we show that for all distributions there exists an optimal mechanism of finite menu complexity. This is in contrast to 2 additive heterogenous items or which the menu complexity could be uncountable [MV07; DDT15]. In addition, we prove that optimal mechanisms for Multi-Unit Pricing (without DMR) can have unbounded menu complexity. We also propose an extension where the menu complexity of optimal mechanisms can be countable but not uncountable. Together these results establish that optimal mechanisms in interdimensional settings are both much richer than single-dimensional settings, yet also vastly more structured than multi-dimensional settings.
Game theory is often used as a tool to analyze decentralized systems and their properties, in particular, blockchains. In this note, we take the opposite view. We argue that blockchains can and should be used to implement economic mechanisms because they can help to overcome problems that occur if trust in the mechanism designer cannot be assumed. Mechanism design deals with the allocation of resources to agents, often by extracting private information from them. Some mechanisms are immune to early information disclosure, while others may heavily depend on it. Some mechanisms have to randomize to achieve fairness and efficiency. Both issues, information disclosure, and randomness require trust in the mechanism designer. If there is no trust, mechanisms can be manipulated. We claim that mechanisms that use randomness or sequential information disclosure are much harder, if not impossible, to audit. Therefore, centralized implementation is often not a good solution. We consider some of the most frequently used mechanisms in practice and identify circumstances under which manipulation is possible. We propose a decentralized implementation of such mechanisms, that can be, in practical terms, realized by blockchain technology. Moreover, we argue in which environments a decentralized implementation of a mechanism brings a significant advantage.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
