Search Results

Sourcing is the process by which companies acquire goods and services for their operations. Drawing from personal experiences of designing and fielding over 800 sourcing auctions worth over $60 billion, this chapter examines issues that arise in very-large-scale generalized combinatorial auctions. It discusses how combinatorial and multi-attribute auctions can be hybridized. It addresses preference and constraint expression languages for the bidders and the bid taker, as well as techniques for effectively using them. It presents scalable optimization techniques for the market clearing (a.k.a. winner determination) problem. It also considers other issues that this study uncovered as well as the significant efficiency gains and other benefits that followed.

This chapter discusses the current practices being applied while using the combinatorial auctions (CAs) format for industrial procurement. It begins with a discussion of industrial procurement operations and defines the role of industrial procurement managers in the procurement process. The chapter emphasizes that software vendors and procurement managers in the business-to-business domain have started taking interest and even using CAs, but this format has not yet become a standard business practice. It describes features of procurement auction applications and current practice in this domain by providing a case study of procurement auctions at Mars, Incorporated. In this case study, the impact of the winner determination problem and allocation constraints on Mars is described.

This chapter offers information on iterative combinatorial auctions (CAs) that help in solving the problem of costly preference elicitation that arises due to the hard problem of winner determination. In this auction mechanism, bidders are allowed to submit multiple bids and are also provided with information feedback so that they can use this feedback and price discovery in expressing their preferences. Iterative CAs help in the verification and validation of an auction outcome, and also enhance revenue and efficiency in single item auctions by facilitating exchange of value information between bidders. The chapter also discusses the concepts of minimal competitive equilibrium (CE) prices and universal CE prices for CAs, which have a role in the preference elicitation problem. Several other issues, including the design space of iterative CAs and price-based iterative CAs, and a case study of an efficient ascending price auction, are also presented.

This book presents an integrated, comprehensive, and interdisciplinary study of combinatorial auctions (CA) in which bids are accepted for packages of items. Applications of CA in various industries including truckload transportation, bus routes, airport takeoff and landing slots, industrial procurement, and the allocation of radio spectrum for wireless communications services. The book starts with a discussion of variety of CA mechanisms including the Vickrey-Clarke-Groves mechanism, iterative combinatorial auctions, simultaneous ascending auctions, and clock-proxy auctions, and also addresses a number of challenges regarding bidding languages and questions of efficiency. Testing of solutions to the winner determination problem that have been proposed is discussed, and an assessment is made of the Combinatorial Auction Test Suite, a software package used for the prediction of the running times of algorithms for the winner determination problem. Further development of this emerging field of CA is expected with the integration of the disciplines of economics, operations research, and computer science.

This chapter discusses a variety of ways that can be helpful in overcoming, reducing, or avoiding computational problems in combinatorial auctions (CA). It begins with an analysis and discussion of the computational difficulties in CA design and looks at opportunities for overcoming these problems at four points in the auction process that include before the submission of bid, at the time of bid submission, and after bid submission. The chapter further looks at how the obstacle of the winner determination problem and other computationally intractable issues in CA are overcome by allowing biddable combinations. It describes how good efficiency and fairness can be achieved in large and complicated CA by providing a chance to bidders to challenge and improve upon a proposed allocation before it is made final. The chapter also discusses the context of auction design, and properties that have to be taken into account by the auction designers before choosing the auction format and procedures.

This chapter reports on the use of combinatorial auctions (CA) for the procurement of commercial freight transportation services in the truckload (TL) market in the U.S. It also explores how CA in the transportation sector, consisting of shippers and carriers, are affected by the nature of shipper– carrier relationships. The chapter begins with a discussion of the uncertainties associated with the three-step transportation procurement process. It analyses the characteristics and elements of transportation auctions along with a discussion of the attributes of transportation that make CA attractive. The chapter focuses on the type of bids used in the transportation TL industry, which include simple lane bids, static package bids, flexible package bids, and tier bids. It also highlights the areas, including carrier bidding behavior and cross shipper auctions, that require further research.

This chapter reports on the clock-proxy auction, a hybrid combinatorial auction design in which the process of auction begins with a clock phase and ends with a proxy round to promote efficiency. This format combines the advantages of both the designs as the efficiency of the proxy auction is complemented with the logical price discovery of the clock auction. A comparison between the clock-proxy auction and the simultaneous ascending auction that establishes the superiority of the former on the efficiency and revenues front is also made. The chapter concludes that this auction format has been used in more than two dozen high-stake auctions across a range of industries in several countries as it has no exposure problem, eliminates incentives for demand reduction, and does not allow the use of collusive bidding strategies.

This chapter presents the format of the combinatorial auction (CA) that was adopted by London Regional Transport (LRT) along with a discussion of its properties. Major options and issues that were faced by LRT when deciding on the auction format are also discussed. The chapter reports on the normative implications of the motivations for submitting a package bid, and provides a discussion of a new method for inferring bidders’ cost structure. It emphasizes that adoption of a CA format for procurement of public transport services in the Greater London area by LRT is the first example of the usage of such format in public procurement. The chapter concludes with a detailed description of the data used in this project together with summary of the statistics, and emphasizes that the LRT auctions have proved to be a success as they have led to improved quality of service and lower costs.

This chapter presents the Combinatorial Auction Test Suite (CATS), a publicly available software package that attempts to model realistic bidding behavior and generates several winner determination problems (WDP). It further discusses the computational hardness of the CATS distributions and shows how the hardest possible instances with a specified number of nondominated bids are generated from a given distribution. This test suite for combinatorial auction (CA) optimization algorithms is better than other techniques for CA testing due to its features, which are economically motivated and present distributions based on real-world problems and historical distributions used by researchers in this area. The chapter concludes that the CATS has been used extensively as a test suite for WDP algorithms.

In this chapter, an iterative combinatorial auction procedure called Progressive Adaptive User Selection Environment (PAUSE) that was proposed by Frank Kelly and Richard Steinberg, is presented. In this procedure, which progresses in stages, the auctioneer does not face the winner determination problem as the responsibility and burden of evaluating a combinatorial bid is transferred to the bidder who is making the bid. The PAUSE procedure, which is conducted in two stages and in an environment similar to the Adaptive User Selection Mechanism (AUSM) of Banks, is a progressive mechanism as it is equipped with features called computational tractability, transparency, and envy-freeness. The chapter also focuses on bidder behavior under PAUSE by presenting a case of two-item combinatorial auction and a specific pattern of valuations.

In this chapter, the connection between efficient auctions for multiple, indivisible items and the duality theory of linear programming is investigated. Vickrey auctions are the focus of this investigation as they are efficient auctions well known for their incentive properties. The chapter begins with a description of the basic results for the assignment model that concerns allocations with indivisibilities and defines the combinatorial auction model and pricing equilibria, which is an extension of Walrasian equilibrium. It further discusses an equivalence between the sealed-bid Vickrey auction and pricing equilibrium. The chapter emphasizes that various combinatorial ascending price auctions are incentive compatible if an MP pricing equilibrium is implemented by them. It also discusses the implementation of dual algorithms, the subgradient algorithm, and the primal dual algorithm for solving linear programming problems.

This chapter discusses the ways that can be helpful in handling the preference elicitation problem in combinatorial auctions. It begins with a discussion of a general elicitation framework and describes relevant concepts such as certificates, incentives, and constraint network that have an impact on a number of elicitation techniques. The chapter further discusses elicitation algorithms that use rank, demand, bound-approximation, and value queries. It emphasizes that only a small fraction of the preferences needs to be revealed in practice. The chapter highlights the need for future research in the field that is focused on the query types and new elicitation policies.

This chapter describes the simultaneous ascending auction (SAA), along with its extensions. It also discusses the success of this method since it was first developed and adopted for the U.S. Federal Communications Commission’s spectrum auctions in 1994. Ascending bids in this mechanism enable price discovery, which helps in increasing efficiency and decreasing transaction costs. SAA, which is not a combinatorial auction, allows bidders to withdraw their bids and provides them with the information that helps in reducing bidder uncertainty. The chapter concludes that the SAA mechanism is to give priority if many items are to be auctioned as a competitive equilibrium is produced in simple settings.

In this chapter, the effects of pseudonymous bidding, which can be considered a very restricted subclass of collusion on combinatorial auctions (CA), are analyzed and discussed. Detection of such manipulation is very difficult because identification of a single bidder acting as multiple bidders on the Internet is virtually impossible. The chapter begins with the development of a formal CA model in which pseudonymous bids are possible in order to show the impact of such procedure on CA. It explores the effect of pseudonymous bids in the Vickrey-Clarke-Groves (VCG) mechanism by deriving the gross substitutes condition for the VCG to become pseudonymous-bid-proof. The chapter also discusses the specifications and efficiency of a pseudonymous-bid-proof protocol called the Leveled Division Set (LDS) protocol, along with some examples showing the application of the protocol.

This chapter analyses the extent of information about bidders’ preferences that is required to be communicated to find an efficient allocation in combinatorial auctions. It also discusses the extensions of this analysis to procurement auctions, deterministic and nondeterministic communication, incentive-compatible communication, and other social choice problems. The chapter defines the deterministic and nondeterministic communication burden of an allocation rule and discusses how the communication burden of approximate efficiency is analyzed. It emphasizes that the communication problem it discusses and the winner determination problem are not similar. The chapter concludes that it is important for any mechanism to discover supporting prices along with the computation of an efficient allocation.

This chapter discusses the optimal winner determination algorithm, which is used for solving the general problem where bids are not restricted. It further focuses on different fundamental design dimensions of search algorithms for winner determination, which include search formulation, search strategy, decomposition techniques, random restart techniques, and caching techniques. The chapter also discusses winner determination under fully expressive bidding languages such as XOR bidding language and OR bidding language, where substitutability is exhibited using XOR-constraints between different bids. It concludes that the various techniques it has discussed are applicable in generalized combinatorial markets, which include combinatorial reverse auctions and combinatorial exchanges.

This chapter examines a number of convenient bidding languages for combinatorial auctions and discusses their properties. It states that the basic aim of a bidding language is to draw a balance between the goals of expressiveness and simplicity. The chapter begins with some examples of valuations, both symmetric and asymmetric, and discusses the leading paradigm for bidding languages in combinatorial auctions. It further describes the computational complexity issues associated with bidding language including expression complexity, complexity of winner determination, and complexity of evaluation. The chapter concludes with the presentation of the technical proofs for the theorems related to both the OR and XOR bidding languages.

This chapter presents modifications of the Vickrey-Clarke-Groves (VCG) mechanism of combinatorial auctions (CAs) that are computationally easy, and which restore individual rationality and incentive compatibility. These modifications are second-chance mechanisms, which satisfy individual rationality and can be applied whenever other mechanisms such as VCG, weighted VCG, or compensation and bonus mechanisms are applicable. The chapter discusses the game theoretic properties of non-optimal incentive compatible VCG mechanisms, which are individually rational and, as a result, lead to poor economic efficiency. It further describes the effects of limited computation but unlimited communication in VCG mechanisms, along with a discussion of various non-VCG approximation mechanisms for restricted CAs. The chapter also discusses all three categories of alternative approaches to the intractability of VCG mechanisms for CAs.

In this chapter we describe the supposed greatest triumph of the market designers, the FCC spectrum auctions. Careful recap of the history reveals that none of the touted benefits of the auction finally settled upon actually were realized; and further, the supposed central role of game theory in the choice of auction was dubious. What economists did accomplish was to deliver the types of licenses preferred by their patrons at good prices. This suggests market design has mostly delivered a new role for economists in the political economy, rather than some generic public benefit.

How many kinds of tasks does a typical em worker regularly do in the course of their job? Looking at job performance today, we see that while extreme specialization can give maximum productivity in the short run, over a longer time a modest degree of task variation is often more productive, because of improved learning and engagement ( Staats and Gino 2012 ). Ems add an important new consideration to this usual tradeoff between task specialization and task variety. Whereas human minds have a limited rate at which they can do tasks, em minds can run at different speeds. So the limited subjective career length of an em can be spent either on more scope in tasks or on more scope in time. That is, an em worker can either run faster and simultaneously do and coordinate more related tasks, or it can run slower and coordinate fewer tasks over a longer period of time, and improve at those tasks in the process. Some tasks require a continual response to external drivers. These tasks include managing physical systems, such as driving cars. Such tasks usually require mental response times as fast as the slower of two rates: the rate at which outside disturbances arise to which it is useful to respond, and the rate at which the managed system such as a car is capable of responding to such disturbances. When choosing between mind speeds faster than this minimum response rate, one of the main tradeoff s is between getting really good at each task, and coordinating more related tasks. One can either do a more specific task more times over a longer narrower career, or do a wider range of related tasks over a shorter career. During either sort of career one could split off many spurs to do short-term tasks that do not need to be well remembered. Long, narrow careers can achieve high levels of competence while adapting to changing job detail, but require expensive communication between workers to coordinate related tasks. In contrast, having the same worker do a wider range of tasks allows for flexible coordination without communication across those tasks, but comes at the cost of more transitions for each worker between different tasks (Wout et al. 2015), and often lower competence because of less task specialization and a shorter career.