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 35
- Downloads 0
Control design for untimed Petri nets using Markov Decision Processes
Design of control sequences for discrete event systems (DESs) has been presented modelled by untimed Petri nets (PNs). PNs are well-known athematical and graphical models that are widely used to describe distributed DESs...
Equilibrium strategies in a fiscal-monetary game. A simulation analysis
The results from a simulation analysis of the policy-mix have been presented, carried out in a fiscal-monetary game, in which fiscal and monetary authorities make decisions from the point of view of realizing their own r...
Innovation management in Polish enterprises
The modern enterprise operates in a turbulent, demanding and unstable environment. Technical and technological progress as well as socioeconomic development create new opportunities but, at the same time, they force ente...
The time to completion of a legal merger: General concepts, statistical analysis and the case of Poland
The legal process involved in domestic mergers has been considered. European Union regulations were investigated, as well as their direct transposition into Polish legislation. The process itself always consists of manag...
Hybrid correlated data in risk assessment
A method for evaluating the risks in a situation has been presented where parameters in the calculation are expressed in the form of dependent fuzzy numbers and probability distributions. The procedure of risk estimation...