| Presentation | 2014-04-24 Time Complexity Analysis of Iterative Auctions with Multiple Differentiated Items Kazuo MUROTA, Akiyoshi SHIOURA, Zaifu YANG, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We address the problem of computing a Walrasian equilibrium price in an ascending auction with gross substitutes valuations. In particular, an auction market is considered where there are multiple differentiated items and each item may have multiple units. Although the ascending auction is known to find an equilibrium price vector in finite time, little is known about its time complexity. The main aim of this paper is to analyze the time complexity of the ascending auction globally and locally, by utilizing the theory of discrete convex analysis. An exact bound on the number of iterations is given in terms of the l_∞ distance between the initial price vector and an equilibrium, and an efficient algorithm to update a price vector is designed based on a min-max theorem for submodular function minimization. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | discrete optimization / submodular function / discrete convex function / Walrasian equilibrium / ascending auction |
| Paper # | COMP2014-7 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2014/4/17(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Time Complexity Analysis of Iterative Auctions with Multiple Differentiated Items |
| Sub Title (in English) | |
| Keyword(1) | discrete optimization |
| Keyword(2) | submodular function |
| Keyword(3) | discrete convex function |
| Keyword(4) | Walrasian equilibrium |
| Keyword(5) | ascending auction |
| 1st Author's Name | Kazuo MUROTA |
| 1st Author's Affiliation | Graduate School of Information Science and Technology, University of Tokyo() |
| 2nd Author's Name | Akiyoshi SHIOURA |
| 2nd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| 3rd Author's Name | Zaifu YANG |
| 3rd Author's Affiliation | Department of Economics, University of York |
| Date | 2014-04-24 |
| Paper # | COMP2014-7 |
| Volume (vol) | vol.114 |
| Number (no) | 19 |
| Page | pp.pp.- |
| #Pages | 7 |
| Date of Issue | |