Computational and Game-Theoretic Approaches for Modeling Bounded Rationality


Update content

Title Computational and Game-Theoretic Approaches for Modeling Bounded Rationality
Period 01 / 2007 - 10 / 2011
Status Completed
Dissertation Yes
Research number OND1328776
Data Supplier Website ERIM


Research into auctions of multiple heterogeneous items has received a lot ofattention in the last decade. Much research by economists has been stimu-lated by the government auctions of radio spectrum licenses that have takenplace all over the world since the 1990s [15]. Especially the Federal Commu-nications Commission (FCC) spectrum auctions in the United States, whichstarted in 1994, have given rise to many new ideas (e.g. [25]). Another im-portant development in the last decade has been the use of the Internet forconducting procurement auctions (also called reverse auctions). Nowadays,electronic auctions for sourcing direct and indirect materials from a supplybase are a widespread phenomenon [13]. An electronic procurement auctiontypically involves many di®erent items [11, 13, 30], and therefore the issueof auctioning multiple heterogeneous items has also received considerableattention in the procurement context (e.g. [3, 12, 14, 23]).In auctions of multiple heterogeneous items, dependencies between itemsare an important issue. It may be the case that a bidder regards two itemsas substitutes and that the bidder therefore is only interested in obtainingone of the items and not in obtaining both of them. Conversely, a biddermay regard two items as complements and therefore only be interested inobtaining both of the items and not in obtaining just one of them. In general,three approaches are possible for auctioning multiple heterogeneous items.The items can be auctioned either sequentially, or simultaneously, or using acombinatorial auction mechanism. Each of these approaches deals with theissue of dependencies between items in a di®erent way. Next, I will brie°ydiscuss each approach.When items are auctioned sequentially, for each item a separate auctionis organized and the auctions are run one after another. According to [13],electronic procurement auctions are typically conducted in a sequential fash-ion. Sequential auctions may cause a so-called exposure problem for bidders(e.g. [29]). This happens when a bidder regards some items as complements,that is, when a bidder's value for the combination of some items is higherthan the sum of the bidder's values for the individual items. Suppose, forexample, that two items, A and B, are auctioned sequentially, ¯rst A andthen B, and that a ¯rst-price sealed-bid format is used in the auctions. Sup-pose further that A and B are each worth 100 to a certain bidder while thecombination of A and B is worth 300 to that bidder. What should the bidderbid in the ¯rst auction, that is, in the auction of A? The bidder may chooseto bid 125 in the ¯rst auction. If he wins the ¯rst auction, he may again bid125 in the second auction. The bidder then makes a pro¯t of 50 if he alsowins the second auction. However, if he does not win the second auction, he makes a loss of 25. So, bidding 125 in the ¯rst auction may result in a lossbecause of the possibility of winning the ¯rst auction and losing the secondauction. This is an example of the exposure problem. To avoid the risk ofmaking a loss, the bidder may choose to bid at most 100 in the ¯rst auction.In that case, however, he may lose the ¯rst auction and make no pro¯t whilehe may have made a pro¯t by bidding more than 100 in the ¯rst auctionand winning both the ¯rst and the second auction. So the bidder faces adilemma. Should he bid above his valuation for A in the ¯rst auction andtake the risk of the exposure problem, that is, the risk of making a loss ifthe ¯rst auction is won but the second is not? Or should he bid at most hisvaluation for A in the ¯rst auction and take the risk of missing the pro¯tthat he may have made by bidding higher and winning both auctions? Ofcourse, the exposure problem not only a®ects the bidders in an auction butalso a®ects the auctioneer. Bidders that want to avoid the risk of losses maychoose not to take into account complementarities between items in theirbids. Most likely, the revenue for the auctioneer will then decrease.The second approach to auctioning multiple heterogeneous items is toauction the items simultaneously. In this approach, a separate auction is or-ganized for each item and the auctions are all run at the same time. Like insequential auctions, complementarities between items may cause an exposureproblem in simultaneous auctions. Conversely, when items are regarded assubstitutes by bidders, there may also be a problem. Items are regarded assubstitutes by a bidder when a bidder's value for a combination of items islower than the sum of the bidder's values for the individual items. Suppose,for example, that two items, A and B, are auctioned simultaneously using a¯rst-price sealed-bid format. For each item, the auctioneer has determineda reserve price of 100. Suppose further that A and B are each worth 150to a certain bidder while the combination of A and B is worth 200 to thatbidder. What should the bidder bid on each item? The bidder may chooseto bid 125 on each item, hoping to win one of the auctions and not bothof them. If the bidder does indeed win one auction, he makes a pro¯t of25. However, if he wins both auctions, he makes a loss of 50. To avoid therisk of making a loss, the bidder may choose to bid 125 on one of the items,let's say A, and not to bid on the other item. Clearly, such a strategy maylead to an ine±cient outcome. For example, suppose that there is one otherbidder participating in the auction. This bidder also regards A and B assubstitutes and also wants to avoid the risk of making a loss. If this bidderalso chooses to bid on A and not to bid on B, there will be no bids on B andB will consequently remain in the hands of the auctioneer. This outcome isine±cient and does not maximize the revenue for the auctioneer. In simul-taneous auctions, the problems associated with items being substitutes or complements can be partially overcome by choosing an appropriate auctionformat. The use of an ascending-price format rather than a sealed-bid formatreduces these problems considerably. In fact, the mechanism of the so-calledsimultaneous ascending auction [24, 25] has been used in spectrum auctionsin the United States and other countries and is considered to have been quitesuccessful (e.g. [7]).The third approach to auctioning multiple heterogeneous items is to auc-tion the items using a combinatorial auction mechanism [8, 28]. In a combi-natorial auction (also called a package auction), multiple items are auctionedat the same time and bidders can bid on individual items as well as on com-binations of items. Bids can be overlapping in the sense that an item can bepart of more than one bid from the same bidder. A bidder can therefore bidon each of the 2n ¡ 1 di®erent combinations of items, where n denotes thenumber of items in the auction. This allows a bidder to fully express his val-uations, which means that a bidder can incorporate in his bids all the e®ectsof items being substitutes or complements. The winning bids in a combina-torial auction are found by solving the winner determination problem (e.g.[20]). This problem consists of ¯nding, for a given set of bids, an alloca-tion of items to bidders that maximizes the auctioneer's revenue. Althoughcombinatorial auctions are a relatively recent phenomenon, quite a numberof practical applications have already been reported in the literature (e.g.[3, 4, 5, 9, 10, 12, 18, 23]). Most of these applications are in the procurementcontext.Because a combinatorial auction allows bidders to fully express their val-uations, one might expect such an auction to result in a higher revenue anda higher e±ciency than sequential and simultaneous auctions. However, thisneed not necessarily be the case. Whether a combinatorial auction resultsin a higher revenue and a higher e±ciency than sequential and simultaneousauctions depends on the strategies used by bidders in the di®erent auctionmechanisms and perhaps also on speci¯c characteristics of the mechanisms(like sealed bid or ascending price). Furthermore, the outcome of a combina-torial auction may be a®ected negatively by the so-called threshold problem(e.g. [7, 29]). Because theoretical knowledge on the revenue and e±ciencyproperties of mechanisms for auctioning multiple heterogeneous items is quitelimited (e.g. [1, 15, 16, 25, 26]), it is usually di±cult to say whether one mech-anism performs better than another. Especially theoretical results on auctionrevenues are very scarce, and theoretical comparisons of the revenues fromdi®erent mechanisms are therefore typically impossible. Because of the di±-culties of theoretically analyzing mechanisms for auctioning multiple hetero-geneous items, the performance of these mechanisms is sometimes evaluatedusing laboratory experiments (e.g. [2, 17, 19, 28]) or computer simulations (e.g. [32]). Furthermore, if a mechanism has been applied in practice, indica-tions of its performance may be obtained from ¯eld data. However, becausebidders' true valuations are not known in practice, ¯eld data only permit anindirect evaluation of a mechanism's performance. An example of the useof ¯eld data is provided in [7], where the application of the simultaneousascending auction mechanism in the FCC spectrum auctions is evaluated.When examining the performance of mechanisms for auctioning multipleheterogeneous items, there are a number of issues that may be given specialattention. Here, I want to brie°y discuss three of these issues. The ¯rstissue is concerned with bidders' equilibrium strategies. The performance ofsingle-item auctions is usually evaluated under the assumption that biddersuse equilibrium strategies (e.g. [15, 16, 22]). Because multi-item auctionsare typically much more complicated than single-item auctions, in practicebidders in multi-item auctions are not always able to determine an equilib-rium strategy [25]. It may therefore sometimes be better not to evaluatethe performance of multi-item auctions under the assumption of equilibriumbidding strategies. Instead, one may consider one or more simple biddingstrategies and examine their e®ect on auction performance. The second issueis concerned with the bundling of items in lots (e.g. [11, 13, 14, 16, 27, 30]).Bundling items in lots and auctioning the lots rather than the individualitems reduces transaction costs and may mitigate the exposure problem insequential and simultaneous auctions. In fact, bundling items may increasean auctioneer's revenue even if bidders regard the items as independent, thatis, as neither substitutes nor complements [6]. At the moment, there is lit-tle theoretical knowledge on optimal lotting strategies. It may therefore beinteresting to investigate the e®ects of di®erent lotting strategies on auctionperformance. Finally, the third issue is the valuation problem faced by bid-ders in a combinatorial auction. In the literature on combinatorial auctions,it is often assumed that a bidder knows his valuation for each of the 2n ¡ 1combinations of items. In practice, however, this is usually not the case, andit is usually costly for a bidder to calculate his valuation for a combinationof items (e.g. [31]). A bidder may then decide not to bid on a combinationof items because the cost of calculating his valuation outweigh the expectedrevenue from bidding. It seems interesting to investigate the consequencesof the valuation problem on bidding strategies and auction performance.

Related organisations

Related people

Supervisor R. Dekker
Supervisor U. Kaymak
Doctoral/PhD student Dr. L.R. Waltman


D43000 Economics

Go to page top
Go back to contents
Go back to site navigation