The Experts below are selected from a list of 5355 Experts worldwide ranked by ideXlab platform
Makoto Yokoo - One of the best experts on this subject based on the ideXlab platform.
-
worst case efficiency ratio in false name proof Combinatorial Auction mechanisms
Adaptive Agents and Multi-Agents Systems, 2010Co-Authors: Atsushi Iwasaki, Yuko Sakurai, Vincent Conitzer, Yoshifusa Omori, Taiki Todo, Mingyu Guo, Makoto YokooAbstract:This paper analyzes the worst-case efficiency ratio of false-name-proof Combinatorial Auction mechanisms. False-name-proofness generalizes strategy-proofness by assuming that a bidder can submit multiple bids under fictitious identifiers. Even the well-known Vickrey-Clarke-Groves mechanism is not false-name-proof. It has previously been shown that there is no false-name-proof mechanism that always achieves a Pareto efficient allocation. Consequently, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplus must be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider the fraction of the Pareto efficient surplus that we obtain and try to maximize this fraction in the worst-case, under the constraint of false-name-proofness. As far as we are aware, this is the first attempt to examine the worst-case efficiency of false-name-proof mechanisms.We show that the worst-case efficiency ratio of any false-name-proof mechanism that satisfies some apparently minor assumptions is at most 2/(m + 1) for Auctions with m different goods. We also observe that the worst-case efficiency ratio of existing false-name-proof mechanisms is generally 1/m or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism that is false-name-proof when all bidders are single-minded. The worst-case efficiency ratio is 2/(m + 1), i.e., optimal.
-
false name proof Combinatorial Auction protocol groves mechanism with submodular approximation
Adaptive Agents and Multi-Agents Systems, 2006Co-Authors: Makoto Yokoo, Toshihiro Matsutani, Atsushi IwasakiAbstract:This paper develops a new Combinatorial Auction protocol called the Groves Mechanism with SubModular Approximation (GM-SMA). This protocol satisfies the following characteristics: (1) it is false-name-proof, (2) each winner is included in a Pareto efficient allocation, and (3) as long as a Pareto efficient allocation is achieved, the protocol is robust against the collusion of losers and the outcome is in the core. As far as the authors are aware, the GM-SMA is the first protocol that satisfies all three of these characteristics.The basic ideas of the GM-SMA are as follows: (i) It is based on the VCG protocol, i.e., the payment of a winner in this protocol is identical to the payment in one instance of the Groves mechanism, which is a class of protocols that includes the VCG. (ii) When calculating the payment of a bidder, we approximate the valuations of other bidders by using a submodular valuation function (submodular approximation). Simulation results show that the GM-SMA achieves a better social surplus and seller's revenue than existing false-name-proof protocols, as long as the submodular approximation is close enough to the original valuations.
-
a new strategy proof greedy allocation Combinatorial Auction protocol and its extension to open ascending Auction protocol
National Conference on Artificial Intelligence, 2005Co-Authors: Takayuki Ito, Makoto Yokoo, Atsushi Iwasaki, Shigeo MatsubaraAbstract:This paper proposes a new Combinatorial Auction protocol called Average-Max-Minimal-Bundle (AM-MB) protocol. The characteristics of the AM-MB protocol are as follows: (i) it is strategyproof, i.e., truth-telling is a dominant strategy, (ii) the computational overhead is very low, since it allocates bundles greedily thereby avoiding an explicit Combinatorial optimization problem, and (iii) it can obtain higher social surplus and revenue than can the Max-Minimal-Bundle (M-MB) protocol, which also satisfies (i) and (ii). Furthermore, this paper extends the AM-MB protocol to an open ascending-price protocol in which straightforward bidding is an ex-post Nash equilibrium.
-
characterization of strategy false name proof Combinatorial Auction protocols price oriented rationing free protocol
International Joint Conference on Artificial Intelligence, 2003Co-Authors: Makoto YokooAbstract:This paper introduces a new distinctive class of Combinatorial Auction protocols called price-oriented, rationing-free (PORF) protocols. The outline of a PORF protocol is as follows: (i) for each bidder, the price of each bundle of goods is determined independently of his/her own declaration (while it can depend on the declarations of other bidders), (ii) we allocate each bidder a bundle that maximizes his/her utility independently of the allocations of other bidders (i.e., rationing-free). Although a PORF protocol appears quite different from traditional protocol descriptions, surprisingly, it is a sufficient and necessary condition for a protocol to be strategy-proof. Furthermore, we show that a PORF protocol satisfying additional conditions is false-name-proof; at the same time, any false-name-proof protocol can be described as a PORF protocol that satisfies the additional conditions. A PORF protocol is an innovative characterization of strategy-proof protocols and the first attempt to characterize false-name-proof protocols. Such a characterization is not only theoretically significant but also useful in practice, since it can serve as a guideline for developing new strategy/false-name proof protocols. We present a new false-name-proof protocol based on the concept of a PORF protocol.
-
Financial Cryptography - Secure Combinatorial Auctions by dynamic programming with polynomial secret sharing
Financial Cryptography, 2003Co-Authors: Koutarou Suzuki, Makoto YokooAbstract:Combinatorial Auctions have recently attracted the interests of many researchers due to their promising applications such as the spectrum Auctions recently held by the FCC. In a Combinatorial Auction, multiple items with interdependent values are sold simultaneously and bidders are allowed to bid on any combination of items. This paper presents a method for implementing several secure Combinatorial Auction protocols based on our newly developed secure dynamic programming protocol. Dynamic programming is a very effective, widely used technique for tackling various Combinatorial optimization problems, including several types of Combinatorial Auctions. Our secure dynamic programming protocol utilizes secret sharing techniques and can obtain the optimal solution of a Combinatorial optimization problem, i.e., result of a Combinatorial Auction, without revealing the inputs of the problem, i.e., bidding prices. We discuss the application of the method to several Combinatorial Auctions, i.e., multiple-unit single-item Auctions, linear-goods Auctions, and general Combinatorial Auctions.
Daniel Grosu - One of the best experts on this subject based on the ideXlab platform.
-
a Combinatorial Auction based mechanism for dynamic vm provisioning and allocation in clouds
IEEE International Conference on Cloud Computing Technology and Science, 2013Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Cloud computing providers provision their resources into different types of virtual machine (VM) instances that are then allocated to the users for specific periods of time. The allocation of VM instances to users is usually determined through fixed-price allocation mechanisms that cannot guarantee an economically efficient allocation and the maximization of cloud provider's revenue. A better alternative would be to use Combinatorial Auction-based resource allocation mechanisms. This argument is supported by the economic theory; when the Auction costs are low, as is the case in the context of cloud computing, Auctions are especially efficient over the fixed-price markets because products are matched to customers having the highest valuation. The existing Combinatorial Auction-based VM allocation mechanisms do not take into account the user's demand when making provisioning decisions, that is, they assume that the VM instances are statically provisioned. We design an Auction-based mechanism for dynamic VM provisioning and allocation that takes into account the user demand, when making provisioning decisions. We prove that our mechanism is truthful (i.e., a user maximizes its utility only by bidding its true valuation for the requested bundle of VMs). We evaluate the proposed mechanism by performing extensive simulation experiments using real workload traces. The experiments show that the proposed mechanism yields higher revenue for the cloud provider and improves the utilization of cloud resources.
-
Combinatorial Auction-based allocation of virtual machine instances in clouds
Journal of Parallel and Distributed Computing, 2013Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Most of the current cloud computing providers allocate virtual machine instances to their users through fixed-price allocation mechanisms. We argue that Combinatorial Auction-based allocation mechanisms are especially efficient over the fixed-price mechanisms since the virtual machine instances are assigned to users having the highest valuation. We formulate the problem of virtual machine allocation in clouds as a Combinatorial Auction problem and propose two mechanisms to solve it. The proposed mechanisms are extensions of two existing Combinatorial Auction mechanisms. We perform extensive simulation experiments to compare the two proposed Combinatorial Auction-based mechanisms with the currently used fixed-price allocation mechanism. Our experiments reveal that the Combinatorial Auction-based mechanisms can significantly improve the allocation efficiency while generating higher revenue for the cloud providers.
-
Combinatorial Auction based mechanisms for vm provisioning and allocation in clouds
Cluster Computing and the Grid, 2012Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Current cloud providers use fixed-price based mechanisms to allocate Virtual Machine (VM) instances to their users. The fixed-price based mechanisms do not provide an efficient allocation of resources and do not maximize the revenue of the cloud providers. A better alternative would be to use Combinatorial Auction-based resource allocation mechanisms. In this PhD dissertation we will design, study and implement Combinatorial Auction-based mechanisms for efficient provisioning and allocation of VM instances in cloud computing environments. We present our preliminary results consisting of three Combinatorial Auction-based mechanisms for VM provisioning and allocation. We also present an efficient bidding algorithm that can be used by the cloud users to decide on how to bid for their requested bundles of VM instances.
-
Combinatorial Auction based dynamic vm provisioning and allocation in clouds
IEEE International Conference on Cloud Computing Technology and Science, 2011Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Efficient Virtual Machine (VM) provisioning and allocation allows the cloud providers to effectively utilize their available resources and obtain higher profits. Existing Combinatorial Auction-based mechanisms assume that the VM instances are already provisioned, that is they assume static VM provisioning. A better solution would be to take into account the users' demand when provisioning VM instances. We design an Auction-based mechanism for dynamic VM provisioning and allocation that takes into account the user demand for VMs when making VM provisioning decisions. We perform extensive simulation experiments using real workload traces and show that the proposed mechanism can improve the utilization, increase the efficiency of allocation, and yield higher revenue for the cloud provider.
-
Combinatorial Auction based allocation of virtual machine instances in clouds
IEEE International Conference on Cloud Computing Technology and Science, 2010Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:The current cloud computing platforms allocate virtual machine instances to their users through fixed-price allocation mechanisms. We argue that Combinatorial Auction-based allocation mechanisms are especially efficient over the fixed-price mechanisms since the virtual machine instances are assigned to users having the highest valuation. We formulate the problem of virtual machine allocation in clouds as a Combinatorial Auction problem and propose two mechanisms to solve it. We perform extensive simulation experiments to compare the two proposed Combinatorial Auction-based mechanisms with the currently used fixed-price allocation mechanism. Our experiments reveal that the Combinatorial Auction-based mechanisms can significantly improve the allocation efficiency while generating higher revenue for the cloud providers.
Soo Hong Chew - One of the best experts on this subject based on the ideXlab platform.
-
characterizing the vickrey Combinatorial Auction by induction
Economic Theory, 2007Co-Authors: Soo Hong Chew, Shigehiro SerizawaAbstract:This note studies the allocation of heterogeneous commodities to agents whose private values for combinations of these commodities are monotonic by inclusion. This setting can accommodate the presence of complementarity and substitutability among the heterogeneous commodities. By using induction logic, we provide an alternative proof of Holmstrom’s (Econometrica 47:1137–1144, 1979) characterization of the Vickrey Combinatorial Auction as the unique efficient, strategy-proof, and individually rational allocation rule on a smoothly connected domain of value profiles. Our approach is elementary, not involving smoothness, and intuitive in the sense that familiar properties of the single-item second-price Auction provide the first step in our induction on the number of Auctioned items. Moreover, our method of proof can be applied to domains which may not be smoothly connected, including nonconvex ones.
-
characterizing the vickrey Combinatorial Auction by induction
2005Co-Authors: Soo Hong Chew, Shigehiro SerizawaAbstract:This note studies the allocation of heterogeneous commodities to agents whose private values for combinations of these commodities are monotonic by inclusion. This setting can accommodate the presence of complementarity and substitutability among the heterogeneous commodities. By using induction logic, we provide an elementary proof of Holmstrom's (1919) characterization of the Vickrey Combinatorial Auction as the unique efficient, strategy-proof, and individually rational allocation rule. Our proof method can also be applied to domains to which his proof cannot be.
Bingli Jiao - One of the best experts on this subject based on the ideXlab platform.
-
Efficiency resource allocation for device-to-device underlay communication systems: A reverse iterative Combinatorial Auction based approach
IEEE Journal on Selected Areas in Communications, 2013Co-Authors: Chen Xu, Qun Zhao, Xiang Cheng, Lingyang Song, Xiaoli Wang, Zhu Han, Bingli JiaoAbstract:Peer-to-peer communication has been recently considered as a popular issue for local area services. An innovative resource allocation scheme is proposed to improve the performance of mobile peer-to-peer, i.e., device-to-device (D2D), communications as an underlay in the downlink (DL) cellular networks. To optimize the system sum rate over the resource sharing of both D2D and cellular modes, we introduce a reverse iterative Combinatorial Auction as the allocation mechanism. In the Auction, all the spectrum resources are considered as a set of resource units, which as bidders compete to obtain business while the packages of the D2D pairs are Auctioned off as goods in each Auction round. We first formulate the valuation of each resource unit, as a basis of the proposed Auction. And then a detailed non-monotonic descending price Auction algorithm is explained depending on the utility function that accounts for the channel gain from D2D and the costs for the system. Further, we prove that the proposed Auction-based scheme is cheat-proof, and converges in a finite number of iteration rounds. We explain non-monotonicity in the price update process and show lower complexity compared to a traditional Combinatorial allocation. The simulation results demonstrate that the algorithm efficiently leads to a good performance on the system sum rate.
-
resource allocation using a reverse iterative Combinatorial Auction for device to device underlay cellular networks
Global Communications Conference, 2012Co-Authors: Lingyang Song, Zhu Han, Bingli JiaoAbstract:An innovative Auction-based allocation scheme is proposed to improve the performance of device-to-device (D2D) communications as an underlay in the downlink (DL) cellular networks. To optimize the system sum rate over the resource sharing of both D2D and cellular modes, we introduce a reverse iterative Combinatorial Auction as the allocation mechanism. In the Auction, all the spectrum resources are considered as a set of resource units, which compete to obtain business as bidders while packages of D2D pairs are Auctioned off as goods in each Auction round. We first formulate the valuation of each resource unit for packages of D2D links. And then a detailed non-monotonic descending price Auction algorithm is explained. Further, we prove that the proposed scheme is cheat-proof, converges in a finite number of iteration rounds, and has lower complexity compared to a traditional Combinatorial allocation. The simulation results demonstrate that the algorithm efficiently leads to a good performance on the system sum rate.
Sharrukh Zaman - One of the best experts on this subject based on the ideXlab platform.
-
a Combinatorial Auction based mechanism for dynamic vm provisioning and allocation in clouds
IEEE International Conference on Cloud Computing Technology and Science, 2013Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Cloud computing providers provision their resources into different types of virtual machine (VM) instances that are then allocated to the users for specific periods of time. The allocation of VM instances to users is usually determined through fixed-price allocation mechanisms that cannot guarantee an economically efficient allocation and the maximization of cloud provider's revenue. A better alternative would be to use Combinatorial Auction-based resource allocation mechanisms. This argument is supported by the economic theory; when the Auction costs are low, as is the case in the context of cloud computing, Auctions are especially efficient over the fixed-price markets because products are matched to customers having the highest valuation. The existing Combinatorial Auction-based VM allocation mechanisms do not take into account the user's demand when making provisioning decisions, that is, they assume that the VM instances are statically provisioned. We design an Auction-based mechanism for dynamic VM provisioning and allocation that takes into account the user demand, when making provisioning decisions. We prove that our mechanism is truthful (i.e., a user maximizes its utility only by bidding its true valuation for the requested bundle of VMs). We evaluate the proposed mechanism by performing extensive simulation experiments using real workload traces. The experiments show that the proposed mechanism yields higher revenue for the cloud provider and improves the utilization of cloud resources.
-
Combinatorial Auction-based allocation of virtual machine instances in clouds
Journal of Parallel and Distributed Computing, 2013Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Most of the current cloud computing providers allocate virtual machine instances to their users through fixed-price allocation mechanisms. We argue that Combinatorial Auction-based allocation mechanisms are especially efficient over the fixed-price mechanisms since the virtual machine instances are assigned to users having the highest valuation. We formulate the problem of virtual machine allocation in clouds as a Combinatorial Auction problem and propose two mechanisms to solve it. The proposed mechanisms are extensions of two existing Combinatorial Auction mechanisms. We perform extensive simulation experiments to compare the two proposed Combinatorial Auction-based mechanisms with the currently used fixed-price allocation mechanism. Our experiments reveal that the Combinatorial Auction-based mechanisms can significantly improve the allocation efficiency while generating higher revenue for the cloud providers.
-
Combinatorial Auction based mechanisms for vm provisioning and allocation in clouds
Cluster Computing and the Grid, 2012Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Current cloud providers use fixed-price based mechanisms to allocate Virtual Machine (VM) instances to their users. The fixed-price based mechanisms do not provide an efficient allocation of resources and do not maximize the revenue of the cloud providers. A better alternative would be to use Combinatorial Auction-based resource allocation mechanisms. In this PhD dissertation we will design, study and implement Combinatorial Auction-based mechanisms for efficient provisioning and allocation of VM instances in cloud computing environments. We present our preliminary results consisting of three Combinatorial Auction-based mechanisms for VM provisioning and allocation. We also present an efficient bidding algorithm that can be used by the cloud users to decide on how to bid for their requested bundles of VM instances.
-
Combinatorial Auction based dynamic vm provisioning and allocation in clouds
IEEE International Conference on Cloud Computing Technology and Science, 2011Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:Efficient Virtual Machine (VM) provisioning and allocation allows the cloud providers to effectively utilize their available resources and obtain higher profits. Existing Combinatorial Auction-based mechanisms assume that the VM instances are already provisioned, that is they assume static VM provisioning. A better solution would be to take into account the users' demand when provisioning VM instances. We design an Auction-based mechanism for dynamic VM provisioning and allocation that takes into account the user demand for VMs when making VM provisioning decisions. We perform extensive simulation experiments using real workload traces and show that the proposed mechanism can improve the utilization, increase the efficiency of allocation, and yield higher revenue for the cloud provider.
-
Combinatorial Auction based allocation of virtual machine instances in clouds
IEEE International Conference on Cloud Computing Technology and Science, 2010Co-Authors: Sharrukh Zaman, Daniel GrosuAbstract:The current cloud computing platforms allocate virtual machine instances to their users through fixed-price allocation mechanisms. We argue that Combinatorial Auction-based allocation mechanisms are especially efficient over the fixed-price mechanisms since the virtual machine instances are assigned to users having the highest valuation. We formulate the problem of virtual machine allocation in clouds as a Combinatorial Auction problem and propose two mechanisms to solve it. We perform extensive simulation experiments to compare the two proposed Combinatorial Auction-based mechanisms with the currently used fixed-price allocation mechanism. Our experiments reveal that the Combinatorial Auction-based mechanisms can significantly improve the allocation efficiency while generating higher revenue for the cloud providers.