Tractable combinatorial auctions and b-matching

Auctions are the most widely used strategic game-theoretic mechanisms in the Internet. Auctions have been mostly studied from a game-theoretic and economic perspective, although recent work in AI and OR has been concerned with computational aspects of auctions as well. When faced from a computational perspective, combinatorial auctions are perhaps the most challenging type of auctions. Combinatorial auctions are auctions where agents may submit bids for bundles of goods. Given that finding an optimal allocation of the goods in a combinatorial auction is in general intractable, researchers have been concerned with exposing tractable instances of combinatorial auctions. In this work we expose the use of b-matching techniques in the context of combinatorial auctions, and apply them in a non-trivial manner in order to introduce polynomial solutions for a variety of combinatorial auctions.     

Computing price trajectories in combinatorial auctions with proxy bidding

Proxy bidding has proven useful in a variety of real auction formats – most notably eBay – and has been proposed for the nascent field of combinatorial auctions. Previous work on proxy bidding in combinatorial auctions requires the auctioneer to run the auction with myopic bidders to determine the outcome. In this paper, we present a radically different approach that computes the bidders’ allocation of their attention across the bundles only at “inflection points”. Inflections are caused by the introduction of a new bundle into an agent’s demand set, a change in the set of currently competitive allocations, or the withdrawal of an agent from the set of active bidders. This approach has several advantages over alternatives, including that it computes exact solutions and is invariant to the magnitude of the bids.     

Iterative Dutch combinatorial auctions

The combinatorial auction problem can be modeled as a weighted set packing problem. Similarly the reverse combinatorial auction can be modeled as a weighted set covering problem. We use the set packing and set covering formulations to suggest novel iterative Dutch auction algorithms for combinatorial auction problems. We use generalized Vickrey auctions (GVA) with reserve prices in each iteration. We prove the convergence of the algorithms and show that the solutions obtained using the algorithms lie within provable worst case bounds. We conduct numerical experiments to show that in general the solutions obtained using these algorithms are much better than the theoretical bounds.     

A multi-agent approach to Intelligent Transportation Systems modeling with combinatorial auctions

Challenges of urbanization require new, more flexible approaches to design of public transportation systems. Demand Responsive Transport systems (DRT) that provide a share transportation services with flexible routes and focus on optimizing of economic and environmental value are becoming an important part of public transportation. In this paper we propose a new approach to design of DRT models which considers DRT as a multi-agent system (MAS) where various autonomous agents represent interests of system’s stakeholders. The distributed nature of the MAS facilitates design of scalable implementations in modern cloud environments. We also propose a planning algorithm based on combinatorial auctions (CA) that allows to express commodity of multiple transportation scenarios by evident means of the bids. Using the mechanism of CA we may fully take into account the presence of complementariness and substitutability among the items that differ across bidders. Further, we describe design principles of our proposed software with a prototype implementation. We believe that our approach to multi-agent modeling is general enough to provide the flexibility necessary for adoption of DRT-services modeling into real-world scenarios. The results of modeling have been compared against several cases of a local bus provider and validated in a set of computational experiments.     

A public procurement combinatorial auction mechanism with quality assignment

This article focuses on mechanism design for quality assignment combinatorial procurement auctions. We model how the participants can maximize social surplus, the difference between gross utility and total cost in electronic procurement, while selecting appropriate quality standards for the procured items. In typical forward combinatorial auctions, the goal is to maximize the sum of all buyers' valuations. In our setting, however, to achieve high buyer utility with low supplier cost, the selected quality levels for the procured items from the suppliers must exceed some predetermined minimum threshold. So the identification of capable suppliers and the corresponding quality assignments are crucial, since buyer utility and supplier cost will be affected by the buyer's quality choice. We develop a novel mechanism to balance the interests of buyers and sellers. Our proposed quality assignment Vickrey-Groves-Clarke (QA-VCG) mechanism is incentive-compatible, provides constraints on partial participation, and is efficient in quasi-linear preferences. In consideration of the perspective of the buyer as a government auctioneer, we also propose a revised mechanism to implement the goal of achieving minimal procurement costs, and appropriate benefits for participating suppliers. We provide a numerical illustration of our QA-VCG mechanism, and an extension that addresses an iterative combinatorial auction mechanism design in our context.     

Multi-attribute auctions with different types of attributes: Enacting properties in multi-attribute auctions

Multi-attribute auctions allow agents to sell and purchase goods and services taking into account more attributes than just price (e.g. service time, tolerances, qualities, etc.). In this paper we analyze attributes involved during the auction process and propose to classify them between verifiable attributes, unverifiable attributes and auctioneer provided attributes. According to this classification we present VMA2, a new Vickrey-based reverse multi-attribute auction mechanism, which takes into account the different types of attributes involved in the auction and allows the auction customization in order to suit the auctioneer needs. On the one hand, the use of auctioneer provided attributes enables the inclusion of different auction concepts, such as social welfare, trust or robustness whilst, on the other hand, the use of verifiable attributes guarantee truthful bidding. The paper exemplifies the behavior of VMA2 describing how an egalitarian allocation can be achieved. The mechanism is then tested in a simulated manufacturing environment and compared with other existing auction allocation methods.     

A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction

Single unit combinatorial auction problem (CAP) and its multi-unit extension have received a lot of attention recently. This paper introduces yet another variant of CAP which generalizes the multi-unit CAP further to allow bids on collections of items that can come from bidder defined classes of items. A bidder may be indifferent to some items with different brands, specifications or qualities and consider them as substitutable. In this case, these items can be put in a class and hence the bids can be made by referring to the items in such classes. This model enables the bidder to express his requests by using less number of bids in case he does not discriminate between different items. Because of this, we call this problem multi-unit nondiscriminatory combinatorial auction (MUNCA) problem. An integer programming formulation is given for this problem. Since this problem is NP-hard, two fast heuristic algorithms have also been designed. The heuristics give quite good solutions when compared to the optimal solution.     

A combinatorial auction improves school meals in Chile: a case of OR in developing countries

The Chilean State delivers essential meal services at schools for low‐income students. Junta Nacional de Auxilio Escolar y Becas, the institution in charge of covering 1,300,000 children, leases the meal service to private enterprises. We developed an integer linear programming model to assign the meal contracts, in a process known as combinatorial auctions. The resulting model, which is NP‐hard, led to significant improvements in efficiency and also contributed to making the process more transparent. The results are apparent in substantial improvements in quality and coverage of the service, and important savings to the country, which are equivalent to feeding 300,000 children in addition. We developed techniques to solve the combinatorial models and also to analyze and compare multiple scenarios to find robust solutions. For the objective function of this problem, we analyzed several options to consider different kinds of social benefits. In this paper, we describe the problem, the methodology and the results. We also present empirical results based on 6 years of experience. Finally, we discuss the relevance and impact of using operations research in these central issues in developing countries.     

Bid evaluation in combinatorial auctions: optimization and learning

In combinatorial auctions bidders can post bids on groups of items. The problem of selecting the winning bids, called Winner Determination Problem, is NP‐hard. In this paper, we consider an interesting variant of this problem, called Bid Evaluation Problem (BEP), where items are services and are subject to precedence constraints and temporal windows. The BEP has many practical applications, such as, for instance, in transportation routes auctions and in take off and landing time slot allocation problems. We have developed a number of optimization algorithms based on Constraint Programming, on Integer Programming and on the combination of the two techniques. We first show that all algorithms proposed outperform the only commercial system for solving BEP instances called Multi AGent Negotiation Testbed, a more general tool for agent negotiation. Then, we evaluate the developed algorithms and use the decision tree machine learning technique for finding a relation between the instance structure and the solving algorithm and providing an automatic algorithm selection procedure. We show that we can achieve an accuracy of 90% in predicting the best algorithm given the instance to be solved with a significant time saving w.r.t. a single solving technique or a costless, but less accurate, prediction technique. Copyright © 2009 John Wiley & Sons, Ltd.     

A hybrid mechanism for heterogeneous e-procurement involving a combinatorial auction and bargaining

We discuss the design of a hybrid mechanism for e-procurement, which implements a multi-attribute combinatorial auction, followed by a bargaining process to achieve desirable procurement transaction outcomes. For the auction phase of the mechanism, we discuss incentive-compatible bidding strategies for suppliers, and how the buyer should determine the winning suppliers. In the follow-on bargaining phase, the buyer can implement a pricing strategy that views the winning suppliers as though they are in different groups. We develop a model and derive decision conditions for the buyer to formulate procurement strategy in this context. Our most important finding is that, compared with the classical Vickrey–Clarke–Groves mechanism, the proposed mechanism improves the transactional social surplus, by including the possibility of post-auction bargaining. We also consider the likelihood that such a hybrid mechanism will be able to provide sustainable business value so long as there is reasonable symmetry in bargaining power between the buyer and the supplier. We offer some thoughts on how to extend this research with approaches from behavioral economics and experimental methods.     

An optimal multiprocessor combinatorial auction solver

A combinatorial auction (CA) is an auction that permits bidders to bid on bundles of goods rather than just a single item. Unfortunately, winner determination for CAs is known to be NP-hard. In this paper, we propose a distributed algorithm to compute optimal solutions to this problem. The algorithm uses nagging, a technique for parallelizing search in heterogeneous distributed computing environments. Here, we show how nagging can be used to parallelize a branch-and-bound algorithm for this problem, and provide empirical results supporting both the performance advantage of nagging over more traditional partitioning methods as well as the superior scalability of nagging to larger numbers of processors.     

An interactive approach for multi-attribute auctions

Auction processes are commonly employed in many environments. With rapid advances in Internet and computing technologies, electronic auctions have become very popular. People sell and buy a wide range of goods and services online. There is a growing need for the proper management of online auctions and for providing support to parties involved. In this paper, we develop an interactive approach supporting both the buyer and the bidders in a multi-attribute, single-item, multi-round, reverse auction environment. We demonstrate the algorithm on a number of problems.     

Bidding strategies for real-life small loan auctions

We define and identify bidding strategies in real-life small loan auctions (Prosper.com). In such auctions, lenders bid for borrowers' loan listings and the winners get to fund the loan at an interest rate determined by the auction. The exceptionally large empirical database provided by Prosper.com offers a unique opportunity to test and further develop the theory of online auctions. This study shows that bidding behavior is not homogeneous among bidders, as the traditional auction theory suggests. Instead, bidders use many different bidding strategies. Moreover, learning and bidders' consistency over time in different auctions is studied.     

Bidding agents for online auctions with hidden bids

There is much active research into the design of automated bidding agents, particularly for environments that involve multiple decoupled auctions. These settings are complex partly because an agent’s strategy depends on information about other bidders’interests. When bidders’ valuation distributions are not known ex ante, machine learning techniques can be used to approximate them from historical data. It is a characteristic feature of auctions, however, that information about some bidders’valuations is systematically concealed. This occurs in the sense that some bidders may fail to bid at all because the asking price exceeds their valuations, and also in the sense that a high bidder may not be compelled to reveal her valuation. Ignoring these “hidden bids” can introduce bias into the estimation of valuation distributions. To overcome this problem, we propose an EM-based algorithm. We validate the algorithm experimentally using agents that react to their environments both decision-theoretically and game-theoretically, using both synthetic and real-world (eBay) datasets. We show that our approach estimates bidders’ valuation distributions and the distribution over the true number of bidders significantly more accurately than more straightforward density estimation techniques. Editors: Amy Greenwald and Michael Littman An earlier version of this work was presented at the Workshop on Game-Theoretic and Decision-Theoretic Agents (GTDT) 2005, Edinburgh, Scotland.     

Online auctions enabling the secondary computer market

The Internet is enabling new forms of commerce and novel markets. One example is the secondary computer market, facilitating exchange between quality sensitive sellers, oftentimes businesses, and price sensitive buyers. As this market does not have a viable physical counterpart with reference prices, it is developing via online auctions. One question of interest in the evolution of this market is the determinants of prices. Using a dataset of 2,000 laptop auctions in a seven-month period, this research provides support for accepted auction theory while raising questions that deserve further explanation. The negative relationship between supply and auction price supports standard supply and demand theory, while higher prices for better features is consistent with vertical differentiation. Even within accepted theory this research broadens the understanding of auction behavior. There is clear support for the “price decline anomaly” where prices in sequential auctions decline, violating the “law of one price.” One result that deserves further attention is that midweek auctions realize higher prices. A second is that price changes over time are not monotonic. Future research should replicate and explain these results, as well as extend them to other auction settings. As the secondary computer market evolves it will impact the primary computer market.     

A key pre-distribution scheme for wireless sensor networks: merging blocks in combinatorial design

In this paper, combinatorial design followed by randomized merging strategy is applied to key pre-distribution in sensor nodes. A transversal design is used to construct a (v, b, r, k) configuration and then randomly selected blocks are merged to form the sensor nodes. We present detailed mathematical analysis of the number of nodes, number of keys per node and the probability that a link gets affected if certain number of nodes are compromised. The technique is tunable to user requirements and it also compares favourably with state of the art design strategies. An important feature of our design is the presence of more number of common keys between any two nodes. Further, we study the situation when properly chosen blocks are merged to form sensor nodes such that the number of intra-node common key is minimized. We present a basic heuristic for this approach and show that it provides slight improvement in terms of certain parameters than our basic random merging strategy. This paper is an extended and revised version of the paper presented in 8th Information Security Conference, ISC'05, pp. 89–103, Lecture Notes in Computer Science, vol. 3650, Springer Verlag. Dibyendu Chakrabarti received his Master of Technology in Computer Science in the year 1998 from the Indian Statistical Institute, Kolkata. Currently he is pursuing his Ph.D. from the Indian Statistical Institute, Kolkata. He is working in the area of Sensor Networks. Subhamoy Maitra received his Bachelor of Electronics and Telecommunication Engineering degree in the year 1992 from Jadavpur University, Kolkata and Master of Technology in Computer Science in the year 1996 from the Indian Statistical Institute, Kolkata. He has completed Ph.D. from the Indian Statistical Institute in 2001. Currently he is an Associate Professor at the Indian Statistical Institute. His research interest is in Cryptology, Digital Watermarking, and Sensor Networks. Prof. Bimal Roy obtained his Master's degree from the Indian Statistical Institute, Calcutta, India in 1979 and Ph.D. from University of Waterloo, Canada in 1982. He is currently a professor at the Indian Statistical Institute, Kolkata. His research area includes Cryptography, Security, Combinatorics etc. His special topics of interest are: Sensor Networks, Visual Cryptography, Hash Functions and Stream Ciphers.     

Robust combinatorial auction protocol against false-name bids

This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence technologies. Although the Internet provides an excellent infrastructure for combinatorial auctions, we must consider the possibility of a new type of cheating, i.e., an agent tries to profit from submitting several bids under fictitious names (false-name bids). If there exists no false-name bid, the Generalized Vickrey Auction protocol (GVA) satisfies individual rationality, Pareto efficiency, and incentive compatibility. On the other hand, when false-name bids are possible, it is theoretically impossible for a combinatorial auction protocol to simultaneously satisfy these three properties.

Our newly developed Leveled Division Set (LDS) protocol, which is a modification of the GVA, utilizes reservation prices of auctioned goods for making decisions on whether to sell goods in a bundle or separately. The LDS protocol satisfies individual rationality and incentive compatibility even if agents can submit false-name bids, although it is not guaranteed to achieve a Pareto efficient social surplus. Simulation results show that the LDS protocol can achieve a better social surplus than that for a protocol that always sells goods in one bundle.     

Reducing mechanism design to algorithm design via machine learning

We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or β-approximation) algorithm for an algorithmic pricing problem, we can convert it into a (1+?)-approximation (or β(1+?)-approximation) for the incentive-compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the class of allowable pricings. We apply these results to the problem of auctioning a digital good, to the attribute auction problem which includes a wide variety of discriminatory pricing problems, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a machine learning perspective, these settings present several challenges: in particular, the “loss function” is discontinuous, is asymmetric, and has a large range. We address these issues in part by introducing a new form of covering-number bound that is especially well-suited to these problems and may be of independent interest.     

Design, development and validation of an agent-based model of electronic auctions

This paper presents the design, development and validation methodology of an agent-based computational model of the B2C electronic auction marketplace. It aims at a comprehensive understanding of the varied issues governing a B2C electronic auction, incorporating the behavior of all relevant agents such as the auctioneer, the consumer and the retailer; and the environment in which these agents operate and interact. In contrast with conventional methods, agent based modeling employs a bottom-up modeling approach where behaviors of individual agents and rules for their interaction, specified at the micro level, give rise to emergent macro level phenomenon. The development methodology should ensure that agent models are aligned with theory, current knowledge of the field and observed phenomena, and output validity of the model also needs to be ascertained. Beginning with a general introduction to agent based computational modeling, this paper formalizes this alignment and validation methodology and elaborates each step, noting the rationale and means for achieving these. The manner in which this process was used in modeling B2C auctions is then described.