An approximation algorithm for multi-unit auctions: numerical and subject experiments
Journal Title: Operations Research and Decisions - Year 2018, Vol 28, Issue 1
Abstract
In multi-unit auctions for a single item, the Vickrey–Clarke–Groves mechanism (VCG) attains allocative efficiency but suffers from its computational complexity. Takahashi and Shigeno thus proposed a greedy based approximation algorithm (GBA). In a subject experiment there was truly a difference in efficiency rate but no significant difference in seller’s revenue between GBA and VCG. It is not clear in theory whether each bidder will submit his or her true unit valuations in GBA. We show, however, that in a subject experiment there was no significant difference in the number of bids that obey “almost” truth-telling between GBA and VCG. As for individual bidding behavior, GBA and VCG show a sharp contrast when a human bidder competes against machine bidders; underbidding was observed in GBA, while overbidding was observed in VCG. Some results in a numerical experiment are also provided prior to reporting those observations.
Authors and Affiliations
Satoshi TAKAHASHI, Yoichi IZUNAGA, Naoki WATANABE
Keywords
Related Articles
- EP ID EP455125
- DOI 10.5277/ord180105
- Views 26
- Downloads 0
Comparison of the Gini and Zenga indexes using some theoretical income distributions abstract
The most common measure of inequality used in scientific research is the Gini index. In 2007, Zenga proposed a new index of inequality that has all the appropriate properties of an measure of equality. In this paper, we...
Logic and risk as qualitative and quantitative dimensions of decision-making processes
Key problems in the field of decision-making have been considered. The authors’ aim was to in-dicate the extremely important for management role of logic and risk in relation to decisions taken under conditions of uncert...
On the state of budgetary balance over time via the one-way classification model
A study on the state of budgetary balance over time in an economy has been conducted. The planned revenues and expected expenditures contained in the budget statements over the years are used as economic instruments for...
Spectral analysis of business cycles in Poland and its major trading partners
The properties of business cycles in Poland and its major trading partners have been examined. The business cycle synchronization (BCS) between Poland and other countries was studied in order to assess the impact of inte...
On types of responsiveness in the theory of voting
In mathematics, monotonicity is used to denote the nature of the connection between variables. Hence for example, a variable is said to be a monotonically increasing function of another variable if an increase in the val...