The theory of auction has become an active research area spanning multiple disciplines such as economics, finance, marketing and management science. But a close examination of it reveals that most of the existing studies deal with ascending (i.e., English) auctions in which it is assumed that the bid increments are continuous. There is a clear lack of research on optimal descending (i.e., Dutch) auction design with discrete bid levels. This dissertation aims to fill this void by considering single-unit, open-bid, first price Dutch auctions in which the bid levels are restricted to a finite set of values, the number of bidders may be certain or uncertain, and a secret reserve price may be present or absent. These types of auctions are most attractive for selling products that are perishable (e.g., flowers) or whose value decreases with time (e.g., air flight seats and concert tickets) (Carare and Rothkopf, 2005). I began by conducting a comprehensive survey of the current literature to identify the key dimensions of an auction model. I then zeroed in on the particular combination of parameters that characterize the Dutch auctions of interest. As a significant departure from the traditional methods employed by applied economists and game theorists, a novel approach is taken by formulating the auctioning problem as a constrained mathematical program and applying standard nonlinear optimization techniques to solve it. In each of the basic Dutch auction model and its two extensions, interesting properties possessed by the optimal bid levels and the auctioneer's maximum expected revenue are uncovered. Numerical examples are provided to illustrate the major propositions where appropriate. The superiority of the optimal strategy recommended in this study over two commonly-used heuristic procedures for setting bid levels is also demonstrated both theoretically and empirically. Finally, economic as well as managerial implications of the findings reported in this dissertation research are discussed.

Industrial online-reverse-auctions have become a common procurement strategy used by many firms to reduce the cost of purchased goods and services. The advantages of online-reverse-auctions include significant price reductions, increased purchasing and selling efficiencies, and access to new supply and purchasing markets. Despite these benefits, practitioners and academics alike have raised concerns with respect to the impact of online-reverse-auctions on the buyer-supplier relationship. Previous research suggests that the parameters and characteristics of an online-reverse-auction can influence the perceptions of online-reverse-auction participants. This dissertation investigates this phenomenon by examining how the design of an online-reverse-auction influences the supplier's perception of the buyer-supplier relationship. Specifically, this research considers the effects of online-reverse-auction design in terms of the independent variables of auction control, auction bid visibility, and auction award rules and the dependent variables of supplier commitment to the buyer and supplier trust in the buyer. Using a 2 x 2 x 2 quasi-experimental design and the statistical technique of MANCOVA, this study tests hypotheses related to how different online-reverse-auction design characteristics influence supplier commitment to the buyer and supplier trust in the buyer. The results of the study suggest that the type of online-reverse-auctions buyers utilize can have an impact on supplier perceptions of the buyer supplier relationship. Overall, the result suggest that supplier trust is influenced by the type of auction design buyers utilize, however, supplier commitment is not. Auctions utilizing third party auction providers, partial bid visibility, and post auction negotiations tended to result in higher levels of trust on the part of suppliers. This study makes a contribution to the literature in the following areas. First, this study is one of only a handful of empirical studies examining the effects of online-reverse-auction designs on the buyer-supplier relationship. While a considerable debate exists within the literature concerning the pros and cons of online-reverse-auctions, little empirical work exists. This study makes a contribution by providing insight with respect to how online-reverse-auction designs influence supplier perceptions of the buyer-supplier relationships. Secondly, this analysis considers the buyer-supplier relationship in terms of commitment and trust. Previous studies have largely neglected these constructs despite their prominence in the buyer-supplier relationship literature. Finally, given that the use of online-reverse-auctions seems well entrenched in the purchasing strategies of many buying organizations; this study provides guidance for the design of online-reverse-auctions such that buyers can potentially reduce the negative aspects of the process.

Unit-demand auctions have been well studied with applications in several areas. In this dissertation, we discuss new variants of the unit-demand auction that are motivated by practical applications. We design mechanisms for these variants that have strong properties related to truthfulness, efficiency, scalability, and privacy. The main contributions of this dissertation can be divided into two parts. In the first part, we introduce a new variant of the classic sealed-bid unit-demand auction in which each item is associated with a put option; the put option of an item gives the seller the right to sell the item at a specified strike price to a specified bidder, regardless of market conditions. We motivate our unit-demand auction setting by discussing applications to the reassignment of leases, and to the design of multi-round auctions. For the classic sealed-bid unit-demand framework, the VCG mechanism provides a truthful auction with strong associated guarantees, including efficiency and envy-freedom. For an item in our auction, the strike price of the associated put imposes a lower bound on the auction price. Due to these lower bound constraints on auction prices, we find that the VCG mechanism is not suitable for our setting. Instead, our work draws on two fundamental techniques, one from the realm of mechanism design for numerical preferences -- the dynamic unit-demand approximate auction of Demange, Gale, and Sotomayor -- and one from the realm of mechanism design for ordinal preferences -- the Top Trading Cycles algorithm -- to obtain a natural auction that satisfies the lower bound constraints on auction prices. While we cannot, in general, achieve either efficiency or envy-freedom in our setting, our auction achieves suitably relaxed versions of these properties. For example, this auction is envy-free for all bidders who do not acquire an item via the exercise of a put. We provide a polynomial time implementation of this auction. By breaking ties in an appropriate manner, we are able to prove that this auction is truthful. In the second part, we specify rules for a dynamic unit-demand auction that supports arbitrary bid revision. In each round, the dynamic auction takes a tentative allocation and pricing as part of the input, and allows each bidder -- including a tentatively allocated bidder -- to submit an arbitrary unit-demand bid. Each round of our dynamic auction is implemented via a single application of the sealed-bid unit-demand auction proposed in the first part. We show that our dynamic auction satisfies strong properties related to truthfulness and efficiency. Using a certain privacy preservation property of each round of the auction, we show that the overall dynamic auction is highly resistant to shilling. We present a fast algorithm for implementing the proposed auction. Using this algorithm, the amortized cost of processing each bidding operation is upper bounded by the complexity of solving a single-source shortest paths problem on a graph with nonnegative edge weights and a node for each item in the auction. We also propose a dynamic price adjustment scheme that discourages sniping by providing bidders with incentives to bid early in the auction. / text

This dissertation develops Bayesian methods to analyze data from auctions and produce policy recommendations for auction design. The essay, "Auction Design Using Bayesian Methods," proposes a decision theoretic method to choose a reserve price in an auction using data from past auctions. Our method formally incorporates parameter uncertainty and the payoff structure into the decision procedure. When the sample size is modest, it produces higher expected revenue than the plug-in methods. Monte Carlo evidence for this is provided. The second essay, "Flexible Bayesian Analysis of First Price Auctions Using Simulated Likelihood," develops an empirical framework that fully exploits all the shape restrictions arising from economic theory: bidding monotonicity and density affiliation. We directly model the valuation density so that bidding monotonicity is automatically satisfied, and restrict the parameter space to rule out all the nonaffiliated densities. Our method uses a simulated likelihood to allow for a very exible specification, but the posterior analysis is exact for the chosen likelihood. Our method controls the smoothness and tail behavior of the valuation density and provides a decision theoretic framework for auction design. We reanalyze a dataset of auctions for drilling rights in the Outer Continental Shelf that has been widely used in past studies. Our approach gives significantly different policy prescriptions on the choice of reserve price than previous methods, suggesting the importance of the theoretical shape restrictions. Lastly, in the essay, "Simple Approximation Methods for Bayesian Auction Design," we propose simple approximation methods for Bayesian decision making in auction design problems. Asymptotic posterior distributions replace the true posteriors in the Bayesian decision framework, which are typically a Gaussian model (second price auction) or a shifted exponential model (first price auction). Our method first approximates the posterior payoff using the limiting models and then maximizes the approximate posterior payoff. Both the approximate and exact Bayes rules converge to the true revenue maximizing reserve price under certain conditions. Monte Carlo studies show that my method closely approximates the exact procedure even for fairly small samples.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

In this thesis, we examine stochastic techniques for overcoming game theoretic and computational issues in the collective decision making process of self-interested individuals. In particular, we examine truthful, stochastic mechanisms, for settings with a strong budget balance constraint (i.e. there is no net flow of money into or away from the agents). Building on past results in AI and computational social choice, we characterise affine-maximising social choice functions that are implementable in truthful mechanisms for the setting of heterogeneous item allocation with unit demand agents. We further provide a characterisation of affine maximisers with the strong budget balance constraint. These mechanisms reveal impossibility results and poor worst-case performance that motivates us to examine stochastic solutions. To adequately compare stochastic mechanisms, we introduce and discuss measures that capture the behaviour of stochastic mechanisms, based on techniques used in stochastic algorithm design. When applied to deterministic mechanisms, these measures correspond directly to existing deterministic measures. While these approaches have more general applicability, in this work we assess mechanisms based on overall agent utility (efficiency and social surplus ratio) as well as fairness (envy and envy-freeness). We observe that mechanisms can (and typically must) achieve truthfulness and strong budget balance using one of two techniques: labelling a subset of agents as ``auctioneers'' who cannot affect the outcome, but collect any surplus; and partitioning agents into disjoint groups, such that each partition solves a subproblem of the overall decision making process. Worst-case analysis of random-auctioneer and random-partition stochastic mechanisms show large improvements over deterministic mechanisms for heterogeneous item allocation. In addition to this allocation problem, we apply our techniques to envy-freeness in the room assignment-rent division problem, for which no truthful deterministic mechanism is possible. We show how stochastic mechanisms give an improved probability of envy-freeness and low expected level of envy for a truthful mechanism. The random-auctioneer technique also improves the worst-case performance of the public good (or public project) problem. Communication and computational complexity are two other important concerns of computational social choice. Both the random-auctioneer and random-partition approaches offer a flexible trade-off between low complexity of the mechanism, and high overall outcome quality measured, for example, by total agent utility. They enable truthful and feasible solutions to be incrementally improved on as the mechanism receives more information and is allowed more processing time. The majority of our results are based on optimising worst-case performance, since this provides guarantees on how a mechanism will perform, regardless of the agents that use it. To complement these results, we perform empirical, average-case analyses on our mechanisms. Finally, while strong budget balance is a fixed constraint in our particular social choice problems, we show empirically that this can improve the overall utility of agents compared to a utility-maximising assignment that requires a budget imbalanced mechanism.

Στην παρούσα διατριβή μελετάμε αγορές δημοπρασιών και εξετάζουμε διάφορες ιδιότητές τους καθώς και τον τρόπο που αυτές επηρεάζονται από τον τρόπο που συμπεριφέρονται και δρουν οι συμμετέχοντες. Η έννοια δημοπρασία αναφέρεται σε κάθε μηχανισμό, ή σύνολο κανόνων, που διέπει μια διαδικασία ανάθεσης αγαθών. Τέτοιοι μηχανισμοί είναι επιρρεπείς σε στρατηγικούς χειρισμούς (χειραγώγηση) από τους συμμετέχοντες, γεγονός που δικαιολογεί την έμφυτη δυσκολία στον σχεδιασμό τους. Σκοπός αυτής της εργασίας είναι η μελέτη σε θεωρητικό επίπεδο των ιδιοτήτων μηχανισμών δημοπρασίας έτσι ώστε να είμαστε σε θέση να προβλέψουμε, να εξηγήσουμε, ακόμα και να τροποποιήσουμε την απόδοσή τους στην πράξη. Εστιάζουμε την προσοχή μας σε δημοπρασίες χρηματοδοτούμενης αναζήτησης, οι οποίες αποτελούν την επικρατέστερη διαδικασία για την προβολή διαφημίσεων στο Διαδίκτυο. Υιοθετούμε παιγνιοθεωρητική προσέγγιση και υπολογίζουμε το Τίμημα της Αναρχίας για να φράξουμε την απώλεια αποδοτικότητας εξαιτίας της στρατηγικής συμπεριφοράς των παιχτών. Επίσης, αποδεικνύουμε εγγυήσεις εσόδων για να φράξουμε την απώλεια των εσόδων του μηχανισμού δημοπρασίας GSP (γενικευμένος μηχανισμός δεύτερης τιμής) σε αυτό το πλαίσιο. Για την ακρίβεια, ορίζουμε παραλλαγές του μηχανισμού δημοπρασίας GSP που δίνουν καλές εγγυήσεις εσόδων. Στη συνέχεια εξετάζουμε το πρόβλημα του σχεδιασμού της βέλτιστης δημοπρασίας ενός αντικειμένου. Αποδεικνύουμε ένα υπολογίσιμο φράγμα δυσκολίας στην προσέγγιση για την περίπτωση με τρεις παίχτες. Επίσης, αποδεικνύουμε ότι υπάρχει αξιοσημείωτη διαφορά ανάμεσα στα έσοδα που προκύπτουν από ντετερμινιστικούς φιλαλήθεις μηχανισμούς και πιθανοτικούς μηχανισμούς που είναι φιλαλήθεις κατά μέσο όρο. / In this dissertation we consider auction markets and examine their properties and how these are affected by the way the participants act. An auction may refer to any mechanism or set of rules governing a resource allocation process. Designing such a mechanism is not an easy task and this is partly due to their vulnerability to strategic manipulation by the participants. Our goal is to examine the theoretical properties of auction mechanisms in order to predict, explain, or even adjust their behavior in practice in terms of some desired features. We focus on sponsored search auctions, which constitute the leading procedure in Internet advertising. We adopt a game-theoretic approach and provide Price of Anarchy bounds in order to measure the efficiency loss due to the strategic behavior of the players. Moreover, we prove revenue guarantees to bound the suboptimality of GSP (generalized second price mechanism) in that respect. Ιn particular, we define variants of the GSP auction mechanism that yield good revenue guarantees. We also consider the problem of designing an optimal auction in the single-item setting. We prove a strong APX-hardness result that applies to the 3-player case. We furthermore give a separation result between the revenue of deterministic and randomized optimal auctions.