๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An efficient Nash-implementation mechanism for network resource allocation

โœ Scribed by Rahul Jain; Jean Walrand


Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
422 KB
Volume
46
Category
Article
ISSN
0005-1098

No coin nor oath required. For personal study only.

โœฆ Synopsis


We propose a mechanism for auctioning bundles of multiple divisible goods in a network where buyers want the same amount of bandwidth on each link in their route. Buyers can specify multiple routes (corresponding to a source-destination pair). The total flow can then be split among these multiple routes. We first propose a one-sided VCG-type mechanism. Players do not report a full valuation function but only a two-dimensional bid signal: the maximum quantity that they want and the per-unit price they are willing to pay. The proposed mechanism is a weak Nash implementation, i.e., it has a non-unique Nash equilibrium that implements the social-welfare maximizing allocation. We show the existence of an efficient Nash equilibrium in the corresponding auction game, though there may exist other Nash equilibria that are not efficient. We then generalize this to arbitrary bundles of various goods. Each buyer submits a bid separately for each good but their utility function is a general function of allocations of bundles of various divisible goods. We then present a double-sided auction mechanism for multiple divisible goods. We show that there exists a Nash equilibrium of this auction game which yields the efficient allocation with strong budget balance.


๐Ÿ“œ SIMILAR VOLUMES


An efficient anonymous authentication me
โœ Renwang Su; Zhenfu Cao ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 376 KB

Security and privacy are crucial to the wide deployments of delay tolerant networks. Without security and privacy guarantees, people are reluctant to accept such a new network paradigm. To address the security and privacy issues in delay tolerant networks, in this paper, based on ID-based ring signa