A key problem in designing marketplaces is how to efficiently allocate a collection of goods among multiple people. Auctions have emerged as a powerful tool with the promise to increase market efficiency by allocating goods to those who value them the most. Nevertheless, traditional auctions are unable to handle real-world market complexities. Over the past decade, there has been a trend towards allowing for package bids and other types of multidimensional bidding techniques that enable suppliers to take advantage of their unique abilities and put forth their best offers. In particular the application of iterative combinatorial auctions in procurement saves negotiation costs and time. Conceptually these auctions show a potential for improving the overall market efficiency. However, in practice they host several new challenges and difficulties. One challenge facing the auctioneer in an iterative combinatorial auction environment is to quickly find an acceptable solution for each round of the auction. Bidders require time to precisely evaluate, price, and communicate different possible combinations based on their current information of item prices. The auctioneer requires time to solve the underlying mathematical problem formulation based on the bids received, report back the feedback information and initiate a new round of the auction. In Chapter 3, we propose a Lagrangian-based heuristic to solve the auctioneer's winner determination problem. After generating the Lagrange multipliers from the solution of a linear relaxation, the heuristic applies several procedures to fix any potentially infeasible optimal Lagrange solutions. In addition to providing an efficient way of solving the winner determination problem, as compared with the leading commercial solver CPLEX, our approach provides Lagrange multipliers. The latter are used as proxies for prices in the auction feedback mechanism. In Chapter 4 we develop a model for the bidders pricing problem, an issue that has received much less attention in the literature. Using the auctioneer feedback, that includes the Lagrange multipliers, the pricing model maximizes the bidders' profit while at the same time keeping their bids competitive. We derive several optimality results for the underlying optimization problem. Interestingly, we analytically show that the auction converges to a point where no bidder is able to submit a bid that yields strictly better profit for him and is not less competitive than his previous bids submitted. We experimentally observe that this approach converges in an early stage. We also find that this iterative auction allows the bidders to improve their profit while providing lower and competitive prices to the auctioneer. In Chapter 5, we introduce a flexible auction model that allows for partial bids. Rather than the regular all-or-nothing indivisible package bids, divisible bids provide flexibility for the auctioneer with the possibility to accept parts of the bids and yet allow the suppliers to capture synergies among the items and provide quantity discounts. We show numerically that this approach improves the overall efficiency of the auction by increasing the suppliers' profit while decreasing the auctioneer's total price of procurement. In addition, we find that computationally the flexible auction outperforms the regular auction. / Thesis / Doctor of Philosophy (PhD)

A seleção de fornecedores de transporte é um desafio cada vez maior. O crescimento da rede de clientes a ser coberta demanda uma alocação eficiente em termos de custo não suprida por mecanismos tradicionais de negociação. Neste âmbito, o leilão combinatório torna-se uma alternativa de negociação ao permitir capturar sinergias entre os trajetos que devem ser atendidos. Em conseqüência disso, diminui-se o custo de transporte do fornecedor que se reflete nos menores preços de suas propostas e finalmente no custo total de compra do serviço. Por outro lado, esta decisão envolve fatores além do custo total; a mensuração destes torna-se importante para identificar fornecedores que melhor se ajustam aos requerimentos do comprador. No entanto, é fundamental escolher um método adequado para sua avaliação porque este influência a decisão final. Este problema de compra de serviços de transporte é conhecido na literatura como Winner Determination Problem (WDP) que, devido a sua complexidade, possui uma resolução limitada. Após revisão teórica, foi observado que os estudos relacionados à área de transporte focalizavam o desenvolvimento de modelos matemáticos que fossem representativos da realidade. Alguns destes modelos abordam a utilização de múltiplos critérios atribuindo um coeficiente que pondera cada critério. Evidenciou-se a necessidade do desenvolvimento de um algoritmo alternativo que além de facilitar sinergias entre trajetos, fosse abrangente o suficiente para tratar múltiplos critérios em instâncias compatíveis com problemas reais. Logo, com o intuito de contribuir com a literatura foi adaptado um algoritmo matemático otimizante ao problema de compras de fornecedores de transporte com base no algoritmo de Sandholm (2002). Este algoritmo aplica leilão combinatório de compras, apoiando-se na teoria da análise de decisão para mensurar critérios relevantes do comprador. Inicialmente, o algoritmo minimiza o custo total do comprador designando combinações de trajetos e fornecedores; depois é modificado para o tratamento multi-critério. Os resultados obtidos foram comparados com o software comercial CPLEX. / Selecting suppliers is a crescent challenge for the enterprises. The extent of the client web that needs to be served demands efficient allocations, in terms of cost, that are not addressed by traditional mechanisms. In this scenario, another mechanism came to be: the combinatorial auction. In this one, suppliers can express their synergies on routes they wish to supply. This leads to lowering their transportation costs, which is reflected in lower bidding prices as well as in the total cost of service. On the other hand, the selection of a supplier involves other criteria besides cost. The definition of these is essential to define which supplier fits the needs of the buyer. That is why it is of most importance to choose the right method to evaluate these needs, as it defines the final choice. This problem is known as Winner Determination Problem (WDP) and due to its complexity, possesses a feeble solution. After compiling what has been done about the subject, it was noticed that in the field of transport, studies are focused on mathematical models that represent reality. Some models address criteria assigning coefficients to the objective function by weighting on it. Clearly, there was a need for alternative algorithms that would, besides promoting synergies on routes, also treat multi-criteria problems close to reality. Therefore, searching for a valid contribution in the field, an adaption of an optimizing algorithm based on Sandholm (2002)s was made. The algorithm applies combinatorial auction, supported by decision analysis for measuring relevant buyers criteria. First, the main algorithms objective is to minimize buyers costs by combining routes and suppliers; then, a modified approach considers multi criteria. Results were then compared to the commercial software CPLEX.

A seleção de fornecedores de transporte é um desafio cada vez maior. O crescimento da rede de clientes a ser coberta demanda uma alocação eficiente em termos de custo não suprida por mecanismos tradicionais de negociação. Neste âmbito, o leilão combinatório torna-se uma alternativa de negociação ao permitir capturar sinergias entre os trajetos que devem ser atendidos. Em conseqüência disso, diminui-se o custo de transporte do fornecedor que se reflete nos menores preços de suas propostas e finalmente no custo total de compra do serviço. Por outro lado, esta decisão envolve fatores além do custo total; a mensuração destes torna-se importante para identificar fornecedores que melhor se ajustam aos requerimentos do comprador. No entanto, é fundamental escolher um método adequado para sua avaliação porque este influência a decisão final. Este problema de compra de serviços de transporte é conhecido na literatura como Winner Determination Problem (WDP) que, devido a sua complexidade, possui uma resolução limitada. Após revisão teórica, foi observado que os estudos relacionados à área de transporte focalizavam o desenvolvimento de modelos matemáticos que fossem representativos da realidade. Alguns destes modelos abordam a utilização de múltiplos critérios atribuindo um coeficiente que pondera cada critério. Evidenciou-se a necessidade do desenvolvimento de um algoritmo alternativo que além de facilitar sinergias entre trajetos, fosse abrangente o suficiente para tratar múltiplos critérios em instâncias compatíveis com problemas reais. Logo, com o intuito de contribuir com a literatura foi adaptado um algoritmo matemático otimizante ao problema de compras de fornecedores de transporte com base no algoritmo de Sandholm (2002). Este algoritmo aplica leilão combinatório de compras, apoiando-se na teoria da análise de decisão para mensurar critérios relevantes do comprador. Inicialmente, o algoritmo minimiza o custo total do comprador designando combinações de trajetos e fornecedores; depois é modificado para o tratamento multi-critério. Os resultados obtidos foram comparados com o software comercial CPLEX. / Selecting suppliers is a crescent challenge for the enterprises. The extent of the client web that needs to be served demands efficient allocations, in terms of cost, that are not addressed by traditional mechanisms. In this scenario, another mechanism came to be: the combinatorial auction. In this one, suppliers can express their synergies on routes they wish to supply. This leads to lowering their transportation costs, which is reflected in lower bidding prices as well as in the total cost of service. On the other hand, the selection of a supplier involves other criteria besides cost. The definition of these is essential to define which supplier fits the needs of the buyer. That is why it is of most importance to choose the right method to evaluate these needs, as it defines the final choice. This problem is known as Winner Determination Problem (WDP) and due to its complexity, possesses a feeble solution. After compiling what has been done about the subject, it was noticed that in the field of transport, studies are focused on mathematical models that represent reality. Some models address criteria assigning coefficients to the objective function by weighting on it. Clearly, there was a need for alternative algorithms that would, besides promoting synergies on routes, also treat multi-criteria problems close to reality. Therefore, searching for a valid contribution in the field, an adaption of an optimizing algorithm based on Sandholm (2002)s was made. The algorithm applies combinatorial auction, supported by decision analysis for measuring relevant buyers criteria. First, the main algorithms objective is to minimize buyers costs by combining routes and suppliers; then, a modified approach considers multi criteria. Results were then compared to the commercial software CPLEX.

To overcome constrained resources, firms can actively seek innovative opportunities from the external world. This innovation approach, called open innovation (Chesbrough 2003; Hippel 2005; Terwiesch and Ulrich 2009; Terwiesch and Xu 2008), is receiving more and more attention. Facilitated by the global Internet and emerging forms of information technology, it has become very easy for companies to generate large numbers of innovative solutions through the use of online open innovation contests or crowdsourcing contests (Archak and Sundararajan 2009; Terwiesch and Ulrich 2009; Terwiesch and Xu 2008; Yang et al. 2009).For an innovation project to succeed, it is necessary to generate not only a large number of good ideas or solutions, but also to identify those that are "exceptional" (Terwiesch and Ulrich 2009). This dissertation contains three studies that aim to improve our understanding of how best to use contests as a tool to aggregate external resources (collective intelligence) in the generation and evaluation of solutions. The first study views an innovation contest from the innovation seeker's perspective and provides insights on how to improve contest performance. The second study views an innovation contest from the innovation solver's perspective examining the characteristics and strategies of winners and solvers. Finally, in the third study, a new approach to the solution evaluation process is introduced, which is referred to as open evaluation. In this approach, a prediction market is used as an aggregation mechanism to coordinate the crowd in the evaluation of proposed solutions. These three studies make a number of contributions to the literature, addressing core issues in the area of online innovation contests. The analyses, which leverage large-scale empirical data, produce a number of profound results, which can help people to understand how best to use and design innovation contests in an online environment, for idea generation. Further, these studies present a variety of managerial implications associated with the aggregation of individual effort (collective intelligence) to evaluate the ideas that are generated by an innovation contest. We hope that our studies can help open innovation pioneers, such as Google, to systematically generate and identify exceptionally good ideas at much lower costs. By utilizing our findings, we expect that more firms will be able to adopt an open innovation strategy, both systematically and easily. / Business Administration/Management Information Systems

By the emergence of electronic commerce and low transaction costs on the Internet, an interest in the design of new auction mechanisms has been arisen. Recently many researchers in computer science, economics, business, and game theory have presented many valuable studies on the subject of online auctions, and auctions theory. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging ones. Combinatorial auctions, that is, auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auction mechanisms in multi-item multi-unit situations where the agents&rsquo / valuations of the items are not additive. However, determining the winners to maximize the revenue is NP-complete. In this study, we first analyze the existing approaches for combinatorial auction problem. Based on this analysis, we then choose three different approaches, which are search approach, descending simultaneous auctions approach, and IP (Integer Programming) formulation approach to build our models. The performances of the models are compared using computer simulations, where we model bandwidth allocation system. Finally a combinatorial auction tool is built which can be used for online auctions and e-procurement systems.

In many real world situations, especially involving multiagent systems and artificial intelligence, participating agents often need to agree upon a common alternative even if they have differing preferences over the available alternatives. Voting is one of the tools of choice in these situations. Common and classic applications of voting in modern applications include collaborative filtering and recommender systems, metasearch engines, coordination and planning among multiple automated agents etc. Agents in these applications usually have computational power at their disposal. This makes the study of computational aspects of voting crucial. This thesis is devoted to a study of computational complexity of several fundamental algorithmic and complexity-theoretic problems arising in the context of voting theory. The typical setting for our work is an “election”; an election consists of a set of voters or agents, a set of alternatives, and a voting rule. The vote of any agent can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile comprises a collection of votes of all the agents. Finally, a voting rule is a mapping that takes as input a voting profile and outputs an alternative, which is called the “winner” or “outcome” of the election. Our contributions in this thesis can be categorized into three parts and are described below. Part I: Preference Elicitation. In the first part of the thesis, we study the problem of eliciting the preferences of a set of voters by asking a small number of comparison queries (such as who a voter prefers between two given alternatives) for various interesting domains of preferences. We commence with considering the domain of single peaked preferences on trees in Chapter 3. This domain is a significant generalization of the classical well studied domain of single peaked preferences. The domain of single peaked preferences and its generalizations are hugely popular among political and social scientists. We show tight dependencies between query complexity of preference elicitation and various parameters of the single peaked tree, for example, number of leaves, diameter, path width, maximum degree of a node etc. We next consider preference elicitation for the domain of single crossing preference profiles in Chapter 4. This domain has also been studied extensively by political scientists, social choice theorists, and computer scientists. We establish that the query complexity of preference elicitation in this domain crucially depends on how the votes are accessed and on whether or not any single crossing ordering is a priori known. Part II: Winner Determination. In the second part of the thesis, we undertake a study of the computational complexity of several important problems related to determining winner of an election. We begin with a study of the following problem: Given an election, predict the winners of the election under some fixed voting rule by sampling as few votes as possible. We establish optimal or almost optimal bounds on the number of votes that one needs to sample for many commonly used voting rules when the margin of victory is at least n (n is the number of voters and is a parameter). We next study efficient sampling based algorithms for estimating the margin of victory of a given election for many common voting rules. The margin of victory of an election is a useful measure that captures the robustness of an election outcome. The above two works are presented in Chapter 5. In Chapter 6, we design an optimal algorithm for determining the plurality winner of an election when the votes are arriving one-by-one in a streaming fashion. This resolves an intriguing question on finding heavy hitters in a stream of items, that has remained open for more than 35 years in the data stream literature. We also provide near optimal algorithms for determining the winner of a stream of votes for other popular voting rules, for example, veto, Borda, maximin etc. Voters’ preferences are often partial orders instead of complete orders. This is known as the incomplete information setting in computational social choice theory. In an incomplete information setting, an extension of the winner determination problem which has been studied extensively is the problem of determining possible winners. We study the kernelization complexity (under the complexity-theoretic framework of parameterized complexity) of the possible winner problem in Chapter 7. We show that there do not exist kernels of size that is polynomial in the number of alternatives for this problem for commonly used voting rules under a plausible complexity theoretic assumption. However, we also show that the problem of coalitional manipulation which is an important special case of the possible winner problem admits a kernel whose size is polynomial bounded in the number of alternatives for common voting rules. \Part III: Election Control. In the final part of the thesis, we study the computational complexity of various interesting aspects of strategic behaviour in voting. First, we consider the impact of partial information in the context of strategic manipulation in Chapter 8. We show that lack of complete information makes the computational problem of manipulation intractable for many commonly used voting rules. In Chapter 9, we initiate the study of the computational problem of detecting possible instances of election manipulation. We show that detecting manipulation may be computationally easy under certain scenarios even when manipulation is intractable. The computational problem of bribery is an extensively studied problem in computational social choice theory. We study computational complexity of bribery when the briber is “frugal” in nature. We show for many common voting rules that the bribery problem remains intractable even when the briber’s behaviour is restricted to be frugal, thereby strengthening the intractability results from the literature. This forms the subject of Chapter 10.