Tokyo Tech News
Tokyo Institute of Technology merged with Tokyo Medical and Dental University to form Institute of Science Tokyo (Science Tokyo) on October 1, 2024.
Over time, content on this site will be migrated to the Science Tokyo Web. Any information published on this site will be valid in relation to Science Tokyo.
Tokyo Tech News
Published: April 21, 2016
Researchers are investigating auction models where there are many different indivisible goods such as houses and cars. Notably, algorithms known as iterative auctions are often used to compute equilibrium prices of goods.
However, the theoretical behavior of iterative auction algorithms is not fully understood. In particular, there are only a few scattered results of research on the theoretical analysis for time bounds of iterative auctions to-date, even though the theoretical bounds on the number of iterations are interesting as research topics in their own right and important for practical applications.
Here, Akiyoshi Shioura at Tokyo Tech and colleagues at Tokyo Metropolitan University, and University of York, UK, describe a unified method of analysis for iterative auctions based on discrete convex analysis—a theory of discrete optimization problems. A key tool in the analysis is the concept of the Lyapunov function in auction theory. The researchers show that the Lyapunov function has a useful property called discrete convexity. By making use of this property, the team derived exact bounds on the number of iterations in terms of the distance between the initial price vector and the resulting equilibrium.
The results of this research extend and unify the iterative auction algorithms for a variety of auction models, offering computational complexity results for these algorithms, and reinforcing the connection between auction theory and discrete convex analysis.
Figure 1. Behavior of the iterative auction algorithm
Reference
Authors: |
Kazuo Murota1, Akiyoshi Shioura2, Zaifu Yang3 |
Title of original paper: |
Time Bounds for Iterative Auctions: A Unified Approach by Discrete Convex Analysis |
Journal, volume, pages and year: |
Discrete Optimization, 19, pp.36-62, (2016). |
DOI : |
|
Affiliations: |
1School of Business Administration, Tokyo Metropolitan University, 2Department of Social Engineering, Tokyo Institute of Technology, 3Department of Economics, University of York |
School of Engineering
—Creating New Industries and Advancing Civilization—
Information on School of Engineering inaugurated in April 2016
Further information
Associate Professor Akiyoshi Shioura
Department of Industrial Engineering and Economics
School of Engineering