実用的インターネットオークションシステムの開発による市場創造

通过开发实用的互联网拍卖系统来创造市场

• 批准号: 12J01920
• 负责人: 高橋 里司
• 金额: $ 0.64万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12J01920/
• 关键词: オークションシステム; 被験者実験; マッチングアルゴリズム; オークション理論; 仮想計算機パッキング; 消費電力最小化; 近似アルゴリズム

本研究では、実用的オークションシステムの開発のために、システムの内部設計にあたる「オークションの勝者決定問題に対する解法」の構築及び「解法の評価のための被験者実験」と、システムの効率的運用のための「仮想計算機パッキングアルゴリズムの開発」を行った。オークションの勝者決定問題とは、入札者への財の配分と、各入札者の支払価格を求める問題である。本研究では、具体的にVCGメカニズムを用いた単一財複数ユニットオークションを扱った。VCGメカニズムを用いた単一財複数ユニットークションの勝者決定問題は、ナップサック問題の特殊ケースでNP-困難と呼ばれる厳密解を求めるのが困難な問題の1つとして知られている問題である。本研究は、食欲法に基づく2-近似アルゴリズムと、線形ナップサック問題に緩和する線形時間2-近似アルゴリズムを提案した。これらの解法によって大規模なオークションの勝者決定問題を高速に解く事が出来た。また、近似精度でも最適値の95%以上の解を出力した。本研究では、提案した解法の評価のために被験者実験を行った。その結果、配分効率性は厳密解と比べ劣るものの、売手の利益に関しては、近似解法と厳密解法の違いが見られない事を統計的に明らかにした。さらに、オークションシステムの効率的運用のために、仮想計算機パッキング問題を扱った。仮想計算機パッキング問題とは、電力消費量が最小となるように、仮想計算機を物理計算機に配置する問題である。本研究では、仮想計算機の移動を制限する事によって1期間の配置問題が一般グラフのマッチング問題に帰着できる事を示し、マッチングに基づいた発見的解法を提案した。提案解法の評価のために、人工データだけでなく、実際に運用されているスーパーコンピュータのトレースデータを用いた実験を行った。電飾消費に関して線形と区分線形の2つのモデルを用いた実験によって、提案解法の効率性を評価することができた。

This study aims to construct a solution to the winner decision problem in the internal design of the system and to develop an ideal computer system in the application of the system efficiency. The winner of the game is determined by the distribution of the property of the participants and the support of the participants. This study is based on the specific VCG model. VCG This study proposes a 2-approximate linear time approach to appetite problem mitigation. The solution to this problem is large-scale, winner-decision problem, and high-speed solution. The approximate accuracy of the solution is more than 95%. This study was conducted on the basis of the evaluation of the proposed solutions. The result, distribution ratio, density ratio, distribution ratio, distribution In addition, the application of computer system efficiency is also discussed. The problem of minimizing the power consumption of a computer is the problem of configuring a physical computer. In this paper, we propose a solution to the general problem of computer configuration during the period of computer mobility restriction. The solution is to evaluate the situation, manually and effectively. For example, if a line shape is used to distinguish a line shape from a line shape, it is necessary to evaluate the effectiveness of the proposed solution.

项目成果

Virtual Machine packing algorithms for lower power consumption

• DOI: 10.1109/sc.companion.2012.300
• 发表时间: 2012-11
• 期刊: 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings
• 作者: Satoshi Takahashi;A. Takefusa;Maiko Shigeno;H. Nakada;T. Kudoh;Akiko Yoshise

2-approximation algorithms for the winner detenination problem in VCG based single-item multi-unit auctions

基于 VCG 的单品多单元拍卖中获胜者判定问题的 2 近似算法

• 发表时间: 2012
• 作者: Satoshi Takanashi;Yoichi Izunaga;Naoki Watanabe and Maiko Shigeno
• 通讯作者: Naoki Watanabe and Maiko Shigeno

An experimental evaluation of approximation algorithm for single-item multi-unit auctions

单品多单元拍卖近似算法的实验评估

• 发表时间: 2012
• 作者: Satoshi Takahashi;Yoichi Izunag;Naoki Watanabe
• 通讯作者: Naoki Watanabe

An experimental evaluation of approximat ion algorithm for single-item multi-unit auctions

单品多品拍卖近似算法的实验评估

• 发表时间: 2012
• 作者: Satoshi Takahashi;Yoichi Izunaga;Naoki Watanabe
• 通讯作者: Naoki Watanabe

Virtual Machine Packing Algorithms for Lower Power Consumption (Poster presentation)

降低功耗的虚拟机打包算法（海报演示）

• 发表时间: 2012
• 作者: Satoshi Takahashi;Atsuko;Takefusa;Maiko Shigeno;Hidemoto Nakada;Tomohiro Kudoh and Akiko Yoshise
• 通讯作者: Tomohiro Kudoh and Akiko Yoshise