| Presentation | 2008-03-10 An extension of the auction algorithm for the duty model and its implementation Toru MIYAZAWA, Yoshinori TAKEI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The ability of forecasting the equilibrium price in a market is valuable for both consumers and suppliers because it would lead to an efficient use of limited resources. The producer model, a kind of market model, and an auction algorithm for it which derives an approximate solution of the equilibrium price efficiently were proposed in [Kapoor, Mehta, Vazirani; WINE2005]. In this report, we extend the producer model by introducing the notion of duty so that the resulting model is more realistic. Moreover, we extend the auction algorithm of Kapoor etal. to one which works under the duty model, calculating the approximate equilibrium price within the step time proportional to the square of the number of consumers, to the square of the number of species of goods, to the square of the number of producers, to the total budget of the consumers, and to the square of the reciprocal (to the resiprocal; if the duty is uniform with respect to the goods and depends only on the producers) of the error bound of the approximate equilibrium price. We also present an implementation of the proposed algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | auction algorithms / approximation algorithms / the equilibrium price |
| Paper # | COMP2007-62 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2008/3/3(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 | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | An extension of the auction algorithm for the duty model and its implementation |
| Sub Title (in English) | |
| Keyword(1) | auction algorithms |
| Keyword(2) | approximation algorithms |
| Keyword(3) | the equilibrium price |
| 1st Author's Name | Toru MIYAZAWA |
| 1st Author's Affiliation | Department of Electrical Engineering, Nagaoka University of Technology() |
| 2nd Author's Name | Yoshinori TAKEI |
| 2nd Author's Affiliation | Department of Electrical Engineering, Nagaoka University of Technology |
| Date | 2008-03-10 |
| Paper # | COMP2007-62 |
| Volume (vol) | vol.107 |
| Number (no) | 537 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |