Name
Abstract | ||
|---|---|---|
We consider the problem of allocating routes in multiple-commodity networks. In such networks, a user can directly download the desired file from a server, or she can do this via a indirectly route to the server if others on the route choose to share their bandwidths. A key feature of such networks is that a user may benefit from exchanging her bandwidth with others to improve the download efficiency. However, she may be strategic about the amount of bandwidth he chooses to share with and may withhold her true bandwidth if it is optimal to do so. Our goal, described in terms of mechanism design, is to design a route allocation mechanism achieves maxmin and/or Pareto efficiency, subject to the participation as well as incentive compatible constraints. We make the following contributions. We first consider the setting where each user can only use a single route to download her file. We show that designing a feasible mechanism in this setting is NP-Complete. To circumvent this complexity, we then consider the setting where each user can use a collection of routes. We show that, optimal mechanisms that satisfy the participation constraints can be efficiently implemented via linear programming. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.5555/2615731.2616085 | AAMAS |
Keywords | Field | DocType |
pareto efficiency,following contribution,single route,participation constraint,mechanism design,multiple-commodity network,true bandwidth,optimal mechanism,route allocation mechanism,feasible mechanism,download efficiency | Incentive compatibility,Computer science,Commodity,Download,Computer network,Participation constraint,Bandwidth (signal processing),Mechanism design,Linear programming,Pareto efficiency,Distributed computing | Conference |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qipeng Liu | 1 | 76 | 10.36 |
| Yicheng Liu | 2 | 2 | 0.73 |
| Pingzhong Tang | 3 | 133 | 32.06 |