The field of algorithmic mechanism design is concerned with the design of computationally efficient algorithms for use when inputs are provided by rational agents, who may misreport their private values in order to strategically manipulate the algorithm for their own benefit. We revisit classic problems in this field by considering settings of incomplete information, where the players' private values are drawn from publicly-known distributions. Such Bayesian models of partial information are common in economics, but have been largely unexplored by the computer science community. In the first part of this thesis we show that, for a very broad class of single-parameter problems, any computationally efficient algorithm can be converted without loss into a mechanism that is truthful in the Bayesian sense of partial information. That is, we exhibit a transformation that generates mechanisms for which it is in each agent's best (expected) interest to refrain from strategic manipulation. The problem of constructing mechanisms for use by rational agents therefore reduces to the design of approximation algorithms without consideration of game-theoretic issues. We furthermore prove that no such general transformation is possible if we require mechanisms that are truthful in the stronger non-Bayesian sense of dominant strategies. In the second part of the thesis we study simple greedy methods for resolving complex auctions. We show that while such greedy algorithms are not truthful, they suffer very little loss in worst-case performance bounds when agents apply strategies at equilibrium, even in settings of partial information. Our analysis applies to various different equilibrium concepts, including Bayes-Nash equilibrium, regret-minimizing strategies, and asynchronous best-response dynamics. Thus, even though greedy auctions are not truthful, they may be appropriate for use as mechanisms under the goal of achieving high social efficiency at equilibrium. Moreover, we prove that no algorithm in a broad class of greedy-like methods can be used to create a deterministic truthful mechanism while retaining a non-trivial approximation to the optimal social welfare. Our overall conclusion is that while full-information models of agent rationality currently dominate the algorithmic mechanism design literature, a relaxation to settings of partial information is well-motivated and provides additional power in solving central problems in the field.

<p>We design algorithms for markets consisting of multiple items, and agents with budget constraints on the maximum amount of money they can afford to spend. This problem can be considered under two broad frameworks. (a) From the standpoint of Auction Theory, the agents valuation functions over the items are private knowledge. Here, a "truthful auction" computes the subset of items received by every agent and her payment, and ensures that no agent can manipulate the scheme to her advantage by misreporting her valuation function. The question is to design a truthful auction whose outcome can be computed in polynomial time. (b) A different, but equally </p><p>important, question is to investigate if and when the market is in "equilibrium", </p><p>meaning that every item is assigned a price, every agent gets her utility-maximizing subset of items under the current prices, and every unallocated item is priced at zero. </p><p>First, we consider the setting of multiple heterogeneous items and present approximation algorithms for revenue-optimal truthful auctions. When the items are homogeneous, we give an efficient algorithm whose outcome defines a truthful and Pareto-optimal auction. Finally, we focus on the notion of "competitive equilibrium", which is a well known solution concept for market clearing. We present efficient algorithms for finding competitive equilibria in markets with budget constrained agents, and show that these equilibria outcomes have strong revenue guarantees.</p> / Dissertation

This thesis provides a discussion on some analytical and empirical models of online auctions. The objective is to provide an alternative framework for analyzing online auctions, and to characterize the distribution of intermediate prices. Chapter 1 provides a mathematical formulation of the eBay auction format and background to the data used in the empirical analysis. Chapter 2 analyzes policies for optimally disposing inventory using online auctions. It is assumed a seller has a fixed number of items to sell using a sequence of, possibly overlapping, single-item auctions. The decision the seller must make is when to start each auction. The decision involves a trade-off between a holding cost for each period an item remains unsold, and a cannibalization effect among competing auctions. Consequently the seller must trade-off the expected marginal gain for the ongoing auctions with the expected marginal cost of the unreleased items by further deferring their release. The problem is formulated as a discrete time Markov Decision Problem. Conditions are derived to ensure that the optimal release policy is a control limit policy in the current price of the ongoing auctions. Chapter 2 focuses on the two item case which has sufficient complexity to raise challenging questions. An underlying assumption in Chapter 2 is that the auction dynamics can be captured by a set of transition probabilities. Chapter 3 shows with two fixed bidding strategies how the transition probabilities can be derived for a given auction format and bidder arrival process. The two specific bidding strategies analyzed are when bidders bid: 1) a minimal increment, and 2) their true valuation. Chapters 4 and 5 provides empirical analyzes of 4,000 eBay auctions conducted by Dell. Chapter 4 provides a statistical model where over discrete time periods, prices of online auctions follow a zero-inflated gamma distribution. Chapter 5 provides an analysis of the 44,000 bids placed in the auctions, based on bids following a gamma distribution. Both models presented in Chapters 4 and 5 are based on conditional probabilities given the price and elapsed time of an auction, and certain parameters of the competing auctions. Chapter 6 concludes the thesis with a discussion of the main results and possible extensions.

Consumer-to-consumer (C2C) online auctions represent an important new marketplace from which consumers can access the goods they require, an alternative marketplace to bricks-and-mortar and online retail stores. Sellers are often ordinary consumers and the items on sale are often second-hand household items, although, modern C2C auction sites also accommodate small businesses selling unused products. Consumer behaviour in online C2C auctions is unlike consumer behaviour in bricks-and-mortar or online retail stores. While considerable research has been conducted into the dynamics of bidding in online C2C auctions little research has addressed the motives for consumers’ ongoing participation in this marketplace. The concept of consumer involvement may explain the amount of time and money consumers are spending in online C2C auctions and the frequency of their visits to auction sites. In the context of this thesis, involvement is defined as the long-term and enduring relevance, connection and relatedness of online auctions to a consumer’s life. The aim of this research is to explore the ways in which the consumer involvement construct offers an explanation for variation in buyers’ ongoing use of online auctions. The thesis also seeks to discover which consumer motives contribute to buyers’ enduring involvement with online auctions. TradeMe is New Zealand’s most popular online C2C auction site. In a country of just four million people, the TradeMe auction site has more than 2 million members and accounts for more than 50 per cent of Internet traffic originating from New Zealand websites. This study of buyers who use the TradeMe auction site, offers the opportunity to study online auction consumers in this unique context. Based on an extensive literature review, eighteen propositions were developed regarding buyer motives for enduring involvement with online C2C auctions. In-depth, semi-structured interviews were conducted with twenty TradeMe users, to test these propositions and to identify any further motives for enduring involvement with auctions that had not been revealed in the literature review. Interviews were audio-recorded and transcribed in full. NVivo8 qualitative data analysis software was used to code the interview transcripts. Thematic analysis reveals six themes representing buyer motives for enduring involvement with online auctions. The significant contribution of this thesis is to identify involvement as a useful construct for explaining consumer behaviour in online auctions. In addition to utilitarian and hedonic motives for involvement with online auctions, the interviews reveal that the buyers have a number of social and personal motives for involvement with online auctions. Analysis of the qualitative dataset also reveals a set of marketer activities which encourage ongoing use of the auction site, and a number of factors (anti-motives) which discourage use of the auction site. The research reveals the existence of an off-line community of auction users who value the social contact they experience with one another outside the auction site. Ongoing buyer-seller relationships are also shown to develop outside the auction site, prompted by an initial auction transaction. TradeMe users often express loyalty to the TradeMe website because they are proud of its New Zealand origins, feel secure in using a local auction website, believe they are supporting small New Zealand businesses by buying from TradeMe, and believe they are practicing sustainable consumption behaviour by purchasing second-hand goods. Future research should develop a multi-item, quantitative measure of buyers’ enduring involvement with online auctions and test the validity of this measure with further empirical data.

Consumer-to-consumer (C2C) online auctions represent an important new marketplace from which consumers can access the goods they require, an alternative marketplace to bricks-and-mortar and online retail stores. Sellers are often ordinary consumers and the items on sale are often second-hand household items, although, modern C2C auction sites also accommodate small businesses selling unused products. Consumer behaviour in online C2C auctions is unlike consumer behaviour in bricks-and-mortar or online retail stores. While considerable research has been conducted into the dynamics of bidding in online C2C auctions little research has addressed the motives for consumers’ ongoing participation in this marketplace. The concept of consumer involvement may explain the amount of time and money consumers are spending in online C2C auctions and the frequency of their visits to auction sites. In the context of this thesis, involvement is defined as the long-term and enduring relevance, connection and relatedness of online auctions to a consumer’s life. The aim of this research is to explore the ways in which the consumer involvement construct offers an explanation for variation in buyers’ ongoing use of online auctions. The thesis also seeks to discover which consumer motives contribute to buyers’ enduring involvement with online auctions. TradeMe is New Zealand’s most popular online C2C auction site. In a country of just four million people, the TradeMe auction site has more than 2 million members and accounts for more than 50 per cent of Internet traffic originating from New Zealand websites. This study of buyers who use the TradeMe auction site, offers the opportunity to study online auction consumers in this unique context. Based on an extensive literature review, eighteen propositions were developed regarding buyer motives for enduring involvement with online C2C auctions. In-depth, semi-structured interviews were conducted with twenty TradeMe users, to test these propositions and to identify any further motives for enduring involvement with auctions that had not been revealed in the literature review. Interviews were audio-recorded and transcribed in full. NVivo8 qualitative data analysis software was used to code the interview transcripts. Thematic analysis reveals six themes representing buyer motives for enduring involvement with online auctions. The significant contribution of this thesis is to identify involvement as a useful construct for explaining consumer behaviour in online auctions. In addition to utilitarian and hedonic motives for involvement with online auctions, the interviews reveal that the buyers have a number of social and personal motives for involvement with online auctions. Analysis of the qualitative dataset also reveals a set of marketer activities which encourage ongoing use of the auction site, and a number of factors (anti-motives) which discourage use of the auction site. The research reveals the existence of an off-line community of auction users who value the social contact they experience with one another outside the auction site. Ongoing buyer-seller relationships are also shown to develop outside the auction site, prompted by an initial auction transaction. TradeMe users often express loyalty to the TradeMe website because they are proud of its New Zealand origins, feel secure in using a local auction website, believe they are supporting small New Zealand businesses by buying from TradeMe, and believe they are practicing sustainable consumption behaviour by purchasing second-hand goods. Future research should develop a multi-item, quantitative measure of buyers’ enduring involvement with online auctions and test the validity of this measure with further empirical data.

Thesis (Ph. D.)--University of Texas at Austin, 1998. / Vita. Includes bibliographical references (leaves 143-150). Available also in a digital version from Dissertation Abstracts.

Thesis (M.M.S.)--Memorial University of Newfoundland, 2004. / Bibliography: leaves 69-70.

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 62-69).

Thesis (Ph. D.)--Ohio State University, 2007. / Title from first page of PDF file. Includes bibliographical references (p. 166-169).

Esta dissertação tem como objetivo estimar a renda de informação apropriada pelos vencedores dos leilões para exploração e produção de petróleo e gás natural no Brasil. Assume-se um modelo estrutural de leilão de valor privado independente. Foram estimadas as distribuições dos lances e dos valores privados dos lançadores de forma não-paramétrica, assumindo assimetria entre os participantes (Petrobras+OGX versus outros). Para isso, explorou-se um banco de dados construído a partir de informações de todos os leilões realizados entre 1999 e 2008. Tal estudo é relevante por tentar avaliar o sucesso do governo brasileiro e das empresas licitantes nestes leilões, principalmente diante da discussão do novo marco regulatório do pré-sal. Os resultados sugerem que a Petrobras e a OGX obtiveram rendas de informação significativamente maiores que as demais concorrentes. Tais rendas variam entre 14% e 63%, dependendo do número de competidores e de seu tipo. De maneira geral, o governo tende a extrair maior parte do preço de reserva do vencedor do leilão quando este não é a Petrobras ou a OGX e quanto maior for o número de concorrentes. / This dissertation aims to estimate the information rent grabbed by the winners of auctions for exploration and production of oil and natural gas in Brazil. It assumes a structural model of independent private values for the auctions. We estimated non-parametrically both the distributions of bids and the distribution of private values from bidders, assuming asymmetry between the participants (Petrobras + OGX versus others). For this, we explored a database with information about all the auctions held between 1999 and 2008. This study is relevant since it tries to assess the success of the Brazilian government and bidders in these auctions, especially before the discussion on the new regulatory framework of pre-salt. Results suggest that Petrobras and OGX obtained information rents significantly higher than other competitors. These rents vary between 14% and 63%, depending on the number of competitors and on their types. In general, the government tends to capture most of the reserve price of the winning bidder when it is not Petrobras or OGX and the greater the number of competitors.