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 32
- 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...
Efficiency measurement in dynamic two-stage network structures with flexible intermediate materials
Data envelopment analysis (DEA) is a nonparametric method for evaluating the relative efficiency of decision making units (DMUs) described by multiple inputs and multiple outputs. Since DEA was introduced in the 1970s, i...
Innovative advantages ranking. A new approach
Assessing/ranking the innovative advantages of countries is a problem of current interest. However, the set of tools used for this purpose are very narrow and often prone to criticism. The aim of this study is to somewha...
Branch and bound algorithm for discrete multi- level linear fractional programming problem
An algorithm is proposed to find an integer solution for bilevel linear fractional programming problem with discrete variables. The method develops a cut that removes the integer solutions which are not bilevel feasible....
A study on the influence of the discretisation unit on the effectiveness of modelling currency exchange rates using the binary-temporal representation
An exchange rate can be expressed in the form of a binary-temporal representation. Such a representation is based on a discretization of movements in the exchange rate, in which to each change in the value - equal to a g...