Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDistributed Mechanism Design for Network Resource Allocation Problems
80
0
0.0
(
0
)
Added by
Nasimeh Heydaribeni
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We formulate and study the algorithmic mechanism design problem for a general class of resource allocation settings, where the center redistributes the private resources brought by individuals. Money transfer is forbidden. Distinct from the standard literature, which assumes the amount of resources brought by an individual to be public information, we consider this amount as an agents private, possibly multi-dimensional type. Our goal is to design truthful mechanisms that achieve two objectives: max-min and Pareto efficiency. For each objective, we provide a reduction that converts any optimal algorithm into a strategy-proof mechanism that achieves the same objective. Our reductions do not inspect the input algorithms but only query these algorithms as oracles. Applying the reductions, we produce strategy-proof mechanisms in a non-trivial application: network route allocation. Our models and result in the application are valuable on their own rights.
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 (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.
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.
The study of approximate mechanism design for facility location problems has been in the center of research at the intersection of artificial intelligence and economics for the last decades, largely due to its practical importance in various domains, such as social planning and clustering. At a high level, the goal is to design mechanisms to select a set of locations on which to build a set of facilities, aiming to optimize some social objective and ensure desirable properties based on the preferences of strategic agents, who might have incentives to misreport their private information such as their locations. This paper presents a comprehensive survey of the significant progress that has been made since the introduction of the problem, highlighting the different variants and methodologies, as well as the most interesting directions for future research.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
