Auctions have a long history and are an effective method to distributed resources. In the era of Internet and e-commerce, electronic sealed-bid auction play an important role in business. However, it is a risk to run a sealed-bid auction through the Internet, which is an open and unreliable environment. There are many security concerns about correctness and fairness of the auction and privacy of the bidders in electronic sealed-bid auctions. Cryptology seems to be the only security solution for electronic sealed-bid auction. On the other hand, a practical electronic sealed-bid auction scheme must be efficient. So efficient application of cryptographic tools to electronic sealed-bid auction is the focus of this thesis. Firstly, security requirements of sealed-bid auctions are surveyed. The auction result must be determined correctly according to the submitted bids and the pre-defined auction rule. The bidders must compete with each other in a fair play and none of them can take advantage of others. The auction must be publicly verifiable, so that the auction result is acceptable by everyone. Usually, a losing bidder hopes to keep his bid secret, so the losing bids should be kept secret. In different applications, different auction rules may be applied. So, to avoid a tie, a large number of biddable prices must be accepted in some applications. Secondly, the currently known sealed-bid auction schemes are classified. In recent years, many sealed-bid auction schemes based on various cryptographic primitives have been proposed. Nearly all of them can be classified into five models. In the Model 1, each bid is known to the auctioneers, who can find the winning bid and winner very efficiently. Bid privacy is not implemented in Model 1. In Model 2 homomorphic bid opening is employed, so that the winning bid and winner can be found while the losing bids are kept secret. In Model 3 very strong bid privacy is achieved through a Dutch-style bid opening, which is highly inefficient. In Model 4, the link between the bids and bidders instead of confidentiality of the bids is kept secret. This kind of confidentiality is weaker than normal bid privacy and called relative bid privacy in this thesis. (Complete confidentiality of the bids in the end of the auction is called absolute bid privacy.) Implementation of relative bid privacy can be very efficient if an efficient anonymous channel can be constructed. Model 5 uses secure evaluation to open the bids and find the auction result and makes it possible to achieve absolute bid privacy efficiently. Three main cryptographic primitives are explored and employed to design new auction schemes in four auction models. The first tool is batch verification, which can improve computational efficiency in auction schemes. The second is mix network, which can be used to implement anonymous channels in Model 4 and Model 5. Two new efficient mix networks are designed and used in Model 2, Model 4 and Model 5. The third is secure evaluation, which is employed in two new auction schemes in Model 5 to achieve strong bid privacy efficiently. Other cryptographic primitives employed in the auction schemes include efficient 1-out-of-w oblivious transfer in Model 2 and key chain in Model 3. Five new auction schemes are proposed. The first scheme in Model 2 batch verifies bid validity to improve efficiency. The second scheme optimises the key chain used in Model 3 to obtain a more advanced auction scheme. The third scheme implements a concrete anonymous channel in Model 4 for the first time and achieves relative bid privacy and high efficiency convincingly. The last two employ new secure evaluation techniques to achieve absolute bid privacy and high efficiency. With these five new auction schemes, better solutions are achieved in various auction applications.

This thesis concerns the interdisciplinary field of combinatorial auctions, combining the fields of computer science, optimization and economics. A combinatorial auction is an auction where many items are sold simultaneously and where bidders may submit indivisible combinatorial bids on groups of items. It is commonly believed that good solutions to the allocation problem can be achieved by allowing combinatorial bidding. Determining who wins in a combinatorial auction is fundamentally different from a traditional single-item auction because we are faced with a hard and potentially intractable optimization problem. Also, unless we are limited to truthful mechanisms, game theoretic analysis of the strategic behavior of bidders is still an open problem. We have chosen primarily to study the first-price combinatorial auction, a natural auction widely used in practice. Theoretical analysis of this type of auction is difficult and little has been done previously. In this thesis we investigate and discuss three fundamental questions with significant practical implications for combinatorial auctions. First, because the number of possible bids grows exponentially with the number of items, limitations on the number of bids are typically required. This gives rise to a problem since bidders are unlikely to choose the "correct" bids that make up the globally optimal solution. We provide evidence that an expressive and compact bidding language can be more important than finding the optimal solution. Second, given a first-price (sealed-bid) combinatorial auction, the question of equilibrium bidding strategies remains an open problem. We propose a heuristic for finding such strategies and also present feasible strategies. And finally, is a first-price combinatorial auction worth pursuing compared to the simpler simultaneous (single-item) auction? We prove, through a model capturing many fundamental properties of multiple items scenarios with synergies, that the first-price combinatorial auction produces higher revenue than simultaneous single-item auctions. We provide bounds on revenue, given a significantly more general model, in contrast to previous work.

O objetivo deste trabalho foi analisar o mercado de concessões de prestação do serviço de transmissão de energia elétrica do Brasil. Essa concessão dura trinta anos e, se for considerado que houve muitos interessados em ganhar as concessões, para a maioria dos leilões realizados até 2005 o resultado dos leilões podem ser considerados um grande sucesso. Esses leilões são recentes, se iniciaram em 1999. Antes disso o setor passava por dificuldades de investimento. Após reformulação de algumas leis, o setor elétrico deixou de ser dependente de financiamentos governamentais. O setor privado começou a investir de forma controlada nesses projetos de grande porte e a obrigação do governo passou a ser o de fiscalizar e formular as leis do setor. Como houve muitos interessados em prestar o serviço público, os leilões foram a forma escolhida para decidir qual era a empresa mais eficiente. Os leilões são descendentes de primeiro preço em dois estágios em que o primeiro estágio é secreto em envelope fechado. Caso a diferença entre o menor valor e os outros lances seja menor do que 5%, o leilão passa para o segundo estágio que ocorre em viva-voz. Como o objeto leiloado é uma concessão, o valor que os participantes tem de decidir não é o preço a pagar, mas sim o valor da receita máxima que a concessionária aceitará receber para prestar o serviço. Uma das características da transmissão que determinou o tipo de regulação a ser utilizado foi o fato da transmissão de energia elétrica ser um monopólio natural, por isso o valor cobrado dos usuários deve ser controlado. O valor desse único lance contém as expectativas dos agentes sobre o valor dos custos estimados para prestar o serviço, contém também as expectativas de lucro possível, da probabilidade de vitória do leilão dada a concorrência etc. A análise deste trabalho se concentra nos leilões realizados no período de 1999 até 2005 em que ocorreram dez leilões com várias linhas sendo leiloadas em cada leilão. Para determinar o que tornou esse mercado tão interessante para as empresas privadas, foram consideradas as características de cada empresa. A característica mais importante é a interdependência. Essa interdependência permite custos menores quanto mais projetos de transmissão a empresa possui, por isso os resultados do leilão podem ser determinados por essa característica especial. Além dessa variável, foram consideradas a concorrência, a competitividade entre os participantes, o tipo de empresa, ou seja, em que setor a empresa possui especialidade na realização de projetos e o fato dos leilões serem seqüenciais. / This work analised the concession market of electricity transmission lines in Brazil. This market was recently created by a major restructuring in the regulation laws. The reason for this change was the investment crisis that the sector was going through before 1999. Those concessions are decided by an auction and lasts for thirty years. It has been considered a major success, due to the interest of many companies in acquiring this permits. The government no longer invested on it but instead decided de the laws to control the sector. One of the key changes in the diferent aspect of the regulation the participation of the private sector. Investments were no longer dependent on government for financial suport. This alteration made the market more competitive, eficient and lucrative. The auctions are classified as a descending first-price with two stages. The first stage is made with a sealed bid and in case the diference of the lowest bid and the other bids are less than 5%, the auction goes to the second stage with a oral auction. The object auctioned is a permit to provide a public service for a period o time, so this is the reason the auction is descending one. The bids made by the participants is the value of a maximum annual income permited by the regulator. The reason for this maximum is a result of the fact that this public service is a natural monopoly. It prevents the concessionare to take advantage over it´s clients by charging a high fee when they don´t have a choice of another provider of this service. When the participants of the auctions choose the value of the bid, this only bid contains all of their expectations of costs, profits, the probability of winning the auction when considering the competition etc. This work uses the data of all the auctions of transmission lines that happened between 1999 and 2005. in this period ocorred ten auctions, with many lines auctioned in each one. In order to determine what made this market so interesting for private companies some caracteristics of those companies were considered. The results of this study finds that the most important caracteristic is interdependencies. It allows lower costs the many concessions the company owns. This result is so powerful that sometimes it may determine the winner of the auction. Other variables analised were the competitiveness of this sequential auctions, the competitiveness of the participants, the kind of work the company is specialized in, as a real option when deciding what kind of company to participate, for exemple, in a joint venture, and the benefits of this decision.

I have developed a multiagent system platform that provides a valuable complement to the alternative research methods. The platform facilitates the development of heterogeneous agents in complex environments. The first application of the multiagent system is to the study of sealed-bid auctions with two-dimensional value signals from pure private to pure common value. I find that several auction outcomes are significantly nonlinear across the two-dimensional value signals. As the common value percent increases, profit, revenue, and efficiency all decrease monotonically, but they decrease in different ways. Finally, I find that forcing revelation by the auction winner of the true common value may have beneficial revenue effects when the common-value percent is high and there is a high degree of uncertainty about the common value. The second application of the multiagent system is to the study of English auctions with two-dimensional value signals using agents that learn a signal-averaging factor. I find that signal averaging increases nonlinearly as the common value percent increases, decreases with the number of bidders, and decreases at high common value percents when the common value signal is more uncertain. Using signal averaging, agents increase their profit when the value is more uncertain. The most obvious effect of signal averaging is on reducing the percentage of auctions won by bidders with the highest common value signal. The third application of the multiagent system is to the study of the optimal payment rule in Treasury auctions using Canadian rules. The model encompasses the when-issued, auction, and secondary markets, as well as constraints for primary dealers. I find that the Spanish payment rule is revenue inferior to the Discriminatory payment rule across all market price spreads, but the Average rule is revenue superior. For most market-price spreads, Uniform payment results in less revenue than Discriminatory, but there are many cases in which Vickrey payment produces more revenue.

I have developed a multiagent system platform that provides a valuable complement to the alternative research methods. The platform facilitates the development of heterogeneous agents in complex environments. The first application of the multiagent system is to the study of sealed-bid auctions with two-dimensional value signals from pure private to pure common value. I find that several auction outcomes are significantly nonlinear across the two-dimensional value signals. As the common value percent increases, profit, revenue, and efficiency all decrease monotonically, but they decrease in different ways. Finally, I find that forcing revelation by the auction winner of the true common value may have beneficial revenue effects when the common-value percent is high and there is a high degree of uncertainty about the common value. The second application of the multiagent system is to the study of English auctions with two-dimensional value signals using agents that learn a signal-averaging factor. I find that signal averaging increases nonlinearly as the common value percent increases, decreases with the number of bidders, and decreases at high common value percents when the common value signal is more uncertain. Using signal averaging, agents increase their profit when the value is more uncertain. The most obvious effect of signal averaging is on reducing the percentage of auctions won by bidders with the highest common value signal. The third application of the multiagent system is to the study of the optimal payment rule in Treasury auctions using Canadian rules. The model encompasses the when-issued, auction, and secondary markets, as well as constraints for primary dealers. I find that the Spanish payment rule is revenue inferior to the Discriminatory payment rule across all market price spreads, but the Average rule is revenue superior. For most market-price spreads, Uniform payment results in less revenue than Discriminatory, but there are many cases in which Vickrey payment produces more revenue.

I have developed a multiagent system platform that provides a valuable complement to the alternative research methods. The platform facilitates the development of heterogeneous agents in complex environments. The first application of the multiagent system is to the study of sealed-bid auctions with two-dimensional value signals from pure private to pure common value. I find that several auction outcomes are significantly nonlinear across the two-dimensional value signals. As the common value percent increases, profit, revenue, and efficiency all decrease monotonically, but they decrease in different ways. Finally, I find that forcing revelation by the auction winner of the true common value may have beneficial revenue effects when the common-value percent is high and there is a high degree of uncertainty about the common value. The second application of the multiagent system is to the study of English auctions with two-dimensional value signals using agents that learn a signal-averaging factor. I find that signal averaging increases nonlinearly as the common value percent increases, decreases with the number of bidders, and decreases at high common value percents when the common value signal is more uncertain. Using signal averaging, agents increase their profit when the value is more uncertain. The most obvious effect of signal averaging is on reducing the percentage of auctions won by bidders with the highest common value signal. The third application of the multiagent system is to the study of the optimal payment rule in Treasury auctions using Canadian rules. The model encompasses the when-issued, auction, and secondary markets, as well as constraints for primary dealers. I find that the Spanish payment rule is revenue inferior to the Discriminatory payment rule across all market price spreads, but the Average rule is revenue superior. For most market-price spreads, Uniform payment results in less revenue than Discriminatory, but there are many cases in which Vickrey payment produces more revenue.

Submitted by Marcos Paulo de Jesus (mpj@gvmail.br) on 2018-07-11T20:46:04Z No. of bitstreams: 1 Jesus - Um estudo de caso entre 3 tipos de leilão reverso sob a perspectiva de uma organização de compras.pdf: 883117 bytes, checksum: 78501c0ba874ec5e74051216e041b45a (MD5) / Approved for entry into archive by Mayara Costa de Sousa (mayara.sousa@fgv.br) on 2018-07-13T22:22:34Z (GMT) No. of bitstreams: 1 Jesus - Um estudo de caso entre 3 tipos de leilão reverso sob a perspectiva de uma organização de compras.pdf: 883117 bytes, checksum: 78501c0ba874ec5e74051216e041b45a (MD5) / Approved for entry into archive by Suzane Guimarães (suzane.guimaraes@fgv.br) on 2018-07-16T13:29:20Z (GMT) No. of bitstreams: 1 Jesus - Um estudo de caso entre 3 tipos de leilão reverso sob a perspectiva de uma organização de compras.pdf: 883117 bytes, checksum: 78501c0ba874ec5e74051216e041b45a (MD5) / Made available in DSpace on 2018-07-16T13:29:20Z (GMT). No. of bitstreams: 1 Jesus - Um estudo de caso entre 3 tipos de leilão reverso sob a perspectiva de uma organização de compras.pdf: 883117 bytes, checksum: 78501c0ba874ec5e74051216e041b45a (MD5) Previous issue date: 2018-06-11 / Essa dissertação é um estudo de caso experimental em laboratório com três tipos de leilão reverso, visando aplicar as lições aprendidas no experimento a um caso real. Como há diversos tipos de leilão disponíveis, selecionar a modalidade mais indicada para um processo de compras torna-se um problema relevante para que uma empresa compradora consiga o melhor resultado do ponto de vista de redução de custo e continuidade do negócio. Fundamentado nisso, o objetivo dessa dissertação é identificar qual a modalidade de leilão pode trazer o melhor resultado do ponto de vista da empresa que está realizando a compra. Dessa forma, foi selecionado um item específico a ser comprado pela empresa, nesse caso um serviço de transporte de carga excedentes, e solicitado a fornecedores selecionados que enviassem propostas de fornecimento com o objetivo de atender à solicitação de cotação (RFQ, ou request for quotation) e, baseado nessas propostas, foi elaborada uma série de simulações em laboratório de três tipos de leilão: leilão reverso inglês, leilão reverso japonês e leilão de primeiro preço em envelope fechado. Após a execução desse experimento, foi selecionada a modalidade de leilão que gerou os melhores resultados esperados pela companhia, nesse caso o menor lance entre os participantes, e aplicada em um caso real, cujo resultado foi reportado nesse trabalho para enriquecer a aplicabilidade dessa dissertação. Com base nesses resultados foi possível comparar o efeito de redução de custos entre esses três tipos de leilão para então aplicá-los em situações futuras. / This dissertation is an experimental case study with three different types of reverse auction in a laboratory aiming to apply the lessons learned in the simulations to a real case. As there are several auctions types available in the software used by companies, selecting the most suitable type for a specific procurement process becomes a relevant problem for a company aiming to get the best result regarding cost reduction and business continuity. Based on that, the goal of this dissertation is to identify which type of auction may lead to the best result from the perspective of the buyer. Thus, it was selected one specific item to be purchased by the company, in this case heavy lift transportation services and it was asked to some suppliers to submit proposals to meet the request for quotation (RFQ). Based on these proposals, it was designed a series of auctions simulations in a laboratory of three types of auctions (reverse English auction, reverse Japanese auction and first price sealed envelope auction). After the performance of these simulations in a laboratory, the type of auction that generated the best results expected by the company, in this case the one with the lowest winning bid from bidders, was selected, applied in a real case situation and the result was reported to enrich the application of this dissertation. Based on these results it is possible to infer the cost reduction effect of these three types of auction and apply it further in the procurement processes.

O objetivo deste trabalho foi analisar o mercado de concessões de prestação do serviço de transmissão de energia elétrica do Brasil. Essa concessão dura trinta anos e, se for considerado que houve muitos interessados em ganhar as concessões, para a maioria dos leilões realizados até 2005 o resultado dos leilões podem ser considerados um grande sucesso. Esses leilões são recentes, se iniciaram em 1999. Antes disso o setor passava por dificuldades de investimento. Após reformulação de algumas leis, o setor elétrico deixou de ser dependente de financiamentos governamentais. O setor privado começou a investir de forma controlada nesses projetos de grande porte e a obrigação do governo passou a ser o de fiscalizar e formular as leis do setor. Como houve muitos interessados em prestar o serviço público, os leilões foram a forma escolhida para decidir qual era a empresa mais eficiente. Os leilões são descendentes de primeiro preço em dois estágios em que o primeiro estágio é secreto em envelope fechado. Caso a diferença entre o menor valor e os outros lances seja menor do que 5%, o leilão passa para o segundo estágio que ocorre em viva-voz. Como o objeto leiloado é uma concessão, o valor que os participantes tem de decidir não é o preço a pagar, mas sim o valor da receita máxima que a concessionária aceitará receber para prestar o serviço. Uma das características da transmissão que determinou o tipo de regulação a ser utilizado foi o fato da transmissão de energia elétrica ser um monopólio natural, por isso o valor cobrado dos usuários deve ser controlado. O valor desse único lance contém as expectativas dos agentes sobre o valor dos custos estimados para prestar o serviço, contém também as expectativas de lucro possível, da probabilidade de vitória do leilão dada a concorrência etc. A análise deste trabalho se concentra nos leilões realizados no período de 1999 até 2005 em que ocorreram dez leilões com várias linhas sendo leiloadas em cada leilão. Para determinar o que tornou esse mercado tão interessante para as empresas privadas, foram consideradas as características de cada empresa. A característica mais importante é a interdependência. Essa interdependência permite custos menores quanto mais projetos de transmissão a empresa possui, por isso os resultados do leilão podem ser determinados por essa característica especial. Além dessa variável, foram consideradas a concorrência, a competitividade entre os participantes, o tipo de empresa, ou seja, em que setor a empresa possui especialidade na realização de projetos e o fato dos leilões serem seqüenciais. / This work analised the concession market of electricity transmission lines in Brazil. This market was recently created by a major restructuring in the regulation laws. The reason for this change was the investment crisis that the sector was going through before 1999. Those concessions are decided by an auction and lasts for thirty years. It has been considered a major success, due to the interest of many companies in acquiring this permits. The government no longer invested on it but instead decided de the laws to control the sector. One of the key changes in the diferent aspect of the regulation the participation of the private sector. Investments were no longer dependent on government for financial suport. This alteration made the market more competitive, eficient and lucrative. The auctions are classified as a descending first-price with two stages. The first stage is made with a sealed bid and in case the diference of the lowest bid and the other bids are less than 5%, the auction goes to the second stage with a oral auction. The object auctioned is a permit to provide a public service for a period o time, so this is the reason the auction is descending one. The bids made by the participants is the value of a maximum annual income permited by the regulator. The reason for this maximum is a result of the fact that this public service is a natural monopoly. It prevents the concessionare to take advantage over it´s clients by charging a high fee when they don´t have a choice of another provider of this service. When the participants of the auctions choose the value of the bid, this only bid contains all of their expectations of costs, profits, the probability of winning the auction when considering the competition etc. This work uses the data of all the auctions of transmission lines that happened between 1999 and 2005. in this period ocorred ten auctions, with many lines auctioned in each one. In order to determine what made this market so interesting for private companies some caracteristics of those companies were considered. The results of this study finds that the most important caracteristic is interdependencies. It allows lower costs the many concessions the company owns. This result is so powerful that sometimes it may determine the winner of the auction. Other variables analised were the competitiveness of this sequential auctions, the competitiveness of the participants, the kind of work the company is specialized in, as a real option when deciding what kind of company to participate, for exemple, in a joint venture, and the benefits of this decision.

Many people still confused and misunderstand the differences between auction types: In fact, we have only two major types of auctions which are the forward auction and Reverse auction[22]. In a forward auction a single seller offers an item for sale with many competitive buyers driving the price upward: In a Reverse Auction, a single buyer wants to purchase a service or an item from many sellers, they drive the price downward: There are many differences between these type of auction: Including the progress of the auctions; winner selection criterion and other factors: The Reverse Auction nowadays is one of the most preferred types of online auctions: It gains popularity rapidly because of representing the buyers' side and helps him to drive prices down in contrary with the forward auction or traditional auction. The aim of this study is to identify the most common types of the Reverse auctions and compare them to one another to determine when should be used by a buyer and propose the most efficient implementation model for some types: The results of this study are: achieve a written report and a small demonstrator model on how to implement English Auction and Second-Sealed bid Auction.

[pt] Nesta de tese de doutorado é proposta uma metodologia alternativa para obter estratégias ótimas de oferta sob incerteza que maximizam o lucro de um agente em mercados dotados de um leilão de preço uniforme e envelope fechado com multiplos produtos divisíveis. A estratégia ótima de um agente price maker depende amplamente da informação conhecida dos agentes rivais. Reconhecendo que a oferta dos agentes rivais pode desviar do equilíbrio de mercado e é de difícil caracterização probabilística, nós propomos um modelo de otimização robusta dois estágios com restrições de equilíbrio para obter estratégias de oferta ótimas avessas a risco. O modelo proposto é um modelo de otimização de três níveis passível de ser reescrito como uma instância particular de um programa binível com restrições de equilíbrio. Um conjunto de procedimentos é proposto a fim de construir uma formulação equivalente de de nível único adequado para aplicação de algoritmos de Geração de Coluna e Restrição (GCC). Diferentemente de trabalhos publicados anteriormente em modelos de otimização dois estágios, nossa metodologia de solução não aplica o método de GCC para iterativamente identificar os cenários mais violados dos fatores de incerteza, variáveis que são identificadas através de variáveis contínuas. Na metodologia de solução proposta, o algoritmo GCC é aplicado para identificar um pequeno subconjunto de condições de otimalidade para o modelo de terceiro nível capaz de representar as restrições de equilíbrio do leilão na solução ótima do problema master (problema de oferta). Um estudo de caso numérico baseado em mercados de energia de curto prazo é apresentado para ilustrar a aplicabilidade do modelo robusto proposto. Resultados indicam que mesmo em um caso em que é observada uma imprecisão de 1 porcento na oferta de equilíbrio de Nash dos agentes rivais, a solução robusta provê uma redução significativa de risco em uma análise fora da amostra. / [en] We propose an alternative methodology to devise profit-maximizing strategic bids under uncertainty in markets endowed with a sealed-bid uniformprice auction with multiple divisible products. The optimal strategic bid of a price maker agent largely depends on the knowledge (information) of the rivals bidding strategy. By recognizing that the bid of rival competitors may deviate from the equilibrium and are of difficult probabilistic characterization, we proposed a two-stage robust optimization model with equilibrium constraints to devise an risk-averse strategic bid in the auction. The proposed model is a trilevel optimization problem that can be recast as a particular instance of a bilevel program with equilibrium constraints. Reformulation procedures are proposed to construct a single-level-equivalent formulation suitable for column and constraint generation (CCG) algorithm. Differently from previously reported works on two-stage robust optimization, our solution methodology does not employ the CCG algorithm to iteratively identify violated scenarios for the uncertain factors, which in this thesis are obtained through continuous variables. In the proposed solution methodology, the CCG is applied to identify a small subset of optimality conditions for the third-level model capable of representing the auction equilibrium constraints at the optimum solution of the master (bidding) problem. A numerical case study based on short-term electricity markets is presented to illustrate the applicability of the proposed robust model. Results show that even for the case where an impression of 1 percent on the rivals offer at the Nash equilibrium is observed, the robust solution provides a non-negligible risk reduction in out-of-sample analysis.