Lam, Yim Hung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 40). / Abstract also in Chinese. / Chapter 1. --- Introduction --- p.1 / Chapter 2. --- Terminology --- p.4 / Chapter 3. --- Literature Review --- p.4 / Chapter 4. --- The Model --- p.13 / Chapter 5. --- Main Results --- p.18 / Chapter 6. --- Extensions / Chapter 6.1 --- Market with informed speculators and uninformed speculators --- p.26 / Chapter 6.2 --- "Market with informed speculators, uninformed speculators and noise traders" --- p.33 / Chapter 7. --- Conclusion --- p.36 / Appendix --- p.37 / References --- p.40

In my dissertation, I investigate the effects of budget-constraints in multi-unit auctions. This is done in three parts. First, I analyze a case where all bidders have a common budget constraint. Precisely, I analyze an auction where two units of an object are sold at two simultaneous, sealed bid, first-price auctions, to bidders who have demand for both units. Bidders differ with respect to their valuations for the units. All bidders have an identical budget constraint which binds their ability to spend in the auction. I show that if valuation distribution is atom-less, then their does not exist any symmetric equilibrium in this auction game. In the second and third parts of my thesis, I analyze the sale of licenses for the right to drill for oil and natural gas in the Outer Continental Shelf (OCS) of the United States. These sales are conducted using simultaneous sealed-bid first-price auctions for multiple licenses, each representing a specific area (called a tract). Using aspects of observed bidding-behavior, I first make a prima facie case that bidders are budget-constrained in these auctions. In order to formalize this argument, I develop a simple extension of the standard model (where bidders differ in their valuations for the objects) by incorporating (random) budgets for the bidders. The auction-game then has a two-dimensional set of types for each player. I study the theoretical properties of this auction, assuming for simplicity that two units are being sold. I show that this game has an equilibrium in pure strategies that is symmetric with respect to the players and with respect to the units. The strategies are essentially pure in the sense that each bidder-type has a unique split (up to a permutation) of his budget between the two auctions. I then characterize the equilibrium in terms of the bid-distribution and iso-bid curves in the value-budget space. I derive various qualitative features of this equilibrium, among which are: (1) under mild assumptions, there always exist bidder-types who submit unequal bids in equilibrium, (2) the equilibrium is monotonic in the sense that bidders with higher valuations prefer more unequal splits of their budgets than bidders with lower valuations and the same budget-level. With a formal theory in place, I carry out a quantitative exercise, using data from the 1970 OCS auction. I show that the model is able to match many aspects of the data. (1) In the data, the number of tracts bidders submit bids on is positively correlated with budgets (an R² of 0.84), even though this relationship is non-monotonic; my model is able to capture this non-monotonicity, while producing an R² of 0.89 (2) In the data, the average number of bids per tract is 8.21; for the model, this number is 10.09. (3) Auction revenue in the data was $1.927 billion; the model produced a mean revenue of $1.944 billion

There is evidence there is a global gender price gap in traditional global art auctions. Taking into account recent technological advances in the secondary art market, this study examines if there is a gender gap for the sale prices of female artists’ work in the contemporary, online art auction market. The analysis uses a unique data set of art works sold in Christie’s Online-Only Auctions for the year of 2018. We regress measures of price on gender and controls for various characteristics of the art work and artist. We find that while there is discount in prices of 17% for artwork created by female artists, further analysis indicates the difference is not necessarily the result of bidder’s biased prices, but rather rooted in the pre-sale estimates given by the auction houses.

In a deregulated power market financial transmission rights (FTR) serve as a mechanism for protecting market participants from price variation resulting from network congestion. Possession of FTRs allows participants to recover congestion related losses resulting from unequal locational marginal prices that arise from out of merit dispatch. There exists different strategies for allocating FTR which are in use in the deregulated market. Designing a comprehensive framework for market specific FTR allocation that includes factors like unbalanced FTR, FTR for losses and AC-OPF is currently a major research issue in the deregulated power industry. This thesis develops a method for allocation of financial transmission rights that maximizes revenue while satisfying the system security constraints of alternating current (AC) networks and the revenue adequacy constraint of the financial market. Both the maximization of the FTR revenue and maintaining the constraints are accomplished through solving a modified version of the optimal power flow program. The methodology developed here considers allocation of both balanced and unbalanced point to point FTR obligations. The design of the framework is centered around three main scenarios that arise in the allocation of FTR. In the first scenario the total FTR bid quantity is much less than the total generation quantity available in the network. To maximize revenue the ISO will allocate the entire quantity and needs to only determine the loss quantity associated with the FTR quantity. In the second scenario the total FTR bid quantity is much greater than the total generation quantity available in the network. The ISO is required to determine the maximum allocatable FTR bid per bus in the network for the given generation limit in the network. A novel adaptation of the OPF program that maximizes the total FTR quantity allocated is run in this case to determine the maximum allocatable bid quantities. The third scenario is when the total FTR bid quantity is less than the total generation quantity available in the network but when the losses stipulated by the FTR quantity are added to the bid quantity the total generation capacity is exceeded. Here the novel adaptation of the OPF program is run to determine the maximum allocatable FTR bid quantity per bus (ceiling values). The original FTR bid quantities are then allocated upto the ceiling values determined. When multiple FTR bids are offered on a point-to-point node pair, allocation of FTRs among the bidders for that node pair is done through an auction process. Various auction strategies such as first price uniform, discriminatory auction, and second price uniform auction are considered. The performance of the FTR allocation process is evaluated for the above auction strategies through sample IEEE networks with 9 and 32 buses, available in the MATPOWER software.

Thesis (M.C.S.)--Unitec New Zealand, 2007. / Includes bibliographical references (leaves 56-62).

<p>The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction.</p><p>In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter.</p><p>The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3.</p><p>In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices.</p><p>In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.</p>

The thesis consists of four papers on combinatorial auctions and a summary. The first part is more of a practical nature and contains two papers. In the first paper, we study the performance of a caching technique in an optimal algorithm for a multi-unit combinatorial auction. In the second paper, we compare the revenues from a second-price combinatorial auction against a second-price one-shot simultaneous auction. In particular, we show that when the synergy parameter is small, the combinatorial auction gives a higher expected revenue than the one-shot. This is in contrast to an earliear result by Krishna and Rosenthal. We also compare the two mechanisms under the assumption that bidders are risk-averse. Such bidders are more sensitive to financial loss (winner's curse) that they tend to bid less aggressively, which leads to lower revenues. Since a direct analytical approach turns out to be difficult, we present numerical results that show which auction mechanism maximizes the seller's revenue depending on the values of synergy and aversion parameter. The second part is more theoretical. Here, we analyze the asymptotic performance of a greedy algorithm for a problem inspired by combinatorial auctions. In particular, we consider a special case in which every bid contains exactly 3 items, and use a Poisson process to model an auction with a random (Poisson) No. of bids. For this restricted case, winner determination problem is equivalent to a maximal 3-set packing on a weighted hypergraph, and hence NP-complete. However, the greedy algorithm approximates this special case within a factor of 3. In the third paper, we compute the asymptotic expected size of the partial allocation and its corresponding expected total revenue from the greedy algorithm, for some distribution of bid prices. In the final paper, we study the case of a deterministic number of bids, which is proportional to the number of distinguishable items in the auction, say M. Then, we prove that the number of bids allocated, suitably normalized, converges to a Normal random variable as M goes to infinity. As a prelude, we also prove that, both the number of bids allocated and those submitted, again suitably normalized, jointly converge in distribution to a continuous 2-dimensional Gaussian process as M goes to infinity.

Combinatorial auctions (CAs) are an important mechanism for allocating multiple items while allowing agents to specify preferences over bundles of items. In order to communicate these preferences, agents submit bids, which consist of one or more items and a value indicating the agent’s preference for these items. The process of determining the allocation of items is known as the winner determination problem (WDP). WDP for CAs is known to be NP-complete in the general case. We consider two distinct graph representations of a CA; the bid graph and the item graph. In a bid graph, vertices represent bids, and two vertices are adjacent if and only if the bids share items in common. In an item graph, each vertex represents a unique item, there is a vertex for each item, and any bid submitted by any agent must induce a connected subgraph of the item graph. We introduce a new definition of combinatorial auction equivalence by declaring two CAs equivalent if and only if their bid graphs are isomorphic. Parameterized complexity theory can be used to further distinguish between NP-hard problems. In order to make use of parameterized complexity theory in the investigation of a problem, we aim to find one or more parameters that describe some aspect of the problem such that if we fix these parameters, then either the problem is still hard (fixed-parameter intractable), or the problem can be solved in polynomial time (fixed-parameter tractable). We analyze WDP using bid graphs from within the formal scope of parameterized complexity theory. This approach has not previously been used to analyze WDP for CAs, although it has been used to solve set packing, which is related to WDP for CAs and is discussed in detail. We investigate a few parameterizations of WDP; some of the parameterizations are shown to be fixed-parameter intractable, while others are fixed-parameter tractable. We also analyze WDP when the graph class of a bid graph is restricted. We also discuss relationships between item graphs and bid graphs. Although both graphs can represent the same problem, there is little previous work analyzing direct relationships between them. Our discussion on these relationships begins with a result by Conitzer et al. [7], which focuses on the item graph representation and its treewidth, a property of a graph that measures how close the graph is to a tree. From a result by Gavril, if an item graph has treewidth one, then the bid graph must be chordal [16]. To apply the other direction of Gavril’s theorem, we use our new definition of CA equivalence. With this new definition, Gavril’s result shows that if a bid graph of a CA is chordal, then we can construct an item graph that has treewidth one for some equivalent CA.

This paper explores the determinants of the number of bidders and final price of 1900s oil paintings auctioned by resellers or dealers on eBay art auctions. We find that starting price has negative effect on bidder’s decision whether to enter the auctions or not while seller reputation variables such as seller´s feedback, being top rate seller has a positive effect. Furthermore, auction theory is introduced to study the bidder´s behavior through auction characteristics and final price. We find that, interestingly, the seller´s reputation variables have no significant effect to the final price and the number of bidders has positive effect toward final price of art work. This evidence means that art auctions on eBay has a private value auctions characteristic. However, some specific characteristics of online auctions, which are the last minute bidding and the presence of experienced bidders, significantly affect the final price. Being an experienced winner or using last minute bidding as a strategy substantially pay more than inexperienced winners or winners who do not use last minute bidding in auctioned painting. This could result from different preference of bidders toward auctioned painting or information on which each bidder is holding.

Combinatorial auctions (CAs) are an important mechanism for allocating multiple items while allowing agents to specify preferences over bundles of items. In order to communicate these preferences, agents submit bids, which consist of one or more items and a value indicating the agent’s preference for these items. The process of determining the allocation of items is known as the winner determination problem (WDP). WDP for CAs is known to be NP-complete in the general case. We consider two distinct graph representations of a CA; the bid graph and the item graph. In a bid graph, vertices represent bids, and two vertices are adjacent if and only if the bids share items in common. In an item graph, each vertex represents a unique item, there is a vertex for each item, and any bid submitted by any agent must induce a connected subgraph of the item graph. We introduce a new definition of combinatorial auction equivalence by declaring two CAs equivalent if and only if their bid graphs are isomorphic. Parameterized complexity theory can be used to further distinguish between NP-hard problems. In order to make use of parameterized complexity theory in the investigation of a problem, we aim to find one or more parameters that describe some aspect of the problem such that if we fix these parameters, then either the problem is still hard (fixed-parameter intractable), or the problem can be solved in polynomial time (fixed-parameter tractable). We analyze WDP using bid graphs from within the formal scope of parameterized complexity theory. This approach has not previously been used to analyze WDP for CAs, although it has been used to solve set packing, which is related to WDP for CAs and is discussed in detail. We investigate a few parameterizations of WDP; some of the parameterizations are shown to be fixed-parameter intractable, while others are fixed-parameter tractable. We also analyze WDP when the graph class of a bid graph is restricted. We also discuss relationships between item graphs and bid graphs. Although both graphs can represent the same problem, there is little previous work analyzing direct relationships between them. Our discussion on these relationships begins with a result by Conitzer et al. [7], which focuses on the item graph representation and its treewidth, a property of a graph that measures how close the graph is to a tree. From a result by Gavril, if an item graph has treewidth one, then the bid graph must be chordal [16]. To apply the other direction of Gavril’s theorem, we use our new definition of CA equivalence. With this new definition, Gavril’s result shows that if a bid graph of a CA is chordal, then we can construct an item graph that has treewidth one for some equivalent CA.