Schedule coordination through egalitarian recurrent multi-unit combinatorial auctions

When selfish industries are competing for limited shared resources, they need to coordinate their activities to handle possible conflicting situations. Moreover, this coordination should not affect the activities already planned by the industries, since this could have negative effects on their performance. Although agents may have buffers that allow them to delay the use of resources, these are of a finite capacity, and therefore cannot be used indiscriminately. Thus, we are faced with the problem of coordinating schedules that have already been generated by the agents. To address this task, we propose to use a recurrent auction mechanism to mediate between the agents. Through this auction mechanism, the agents can express their interest in using the resources, thus helping the scheduler to find the best distribution. We also introduce a priority mechanism to add fairness to the coordination process. The proposed coordination mechanism has been applied to a waste water treatment system scenario, where different industries need to discharge their waste. We have simulated the behavior of the system, and the results show that using our coordination mechanism the waste water treatment plant can successfully treat most of the discharges, while the production activity of the industries is almost not affected by it.     

Bidding strategies for realistic multi-unit sealed-bid auctions

When autonomous agents decide on their bidding strategies in real world auctions, they have a number of concerns that go beyond the models that are normally analyzed in traditional auction theory. Oftentimes, the agents have budget constraints and the auctions have a reserve price, both of which restrict the bids the agents can place. In addition, their attitude need not be risk-neutral and they may have uncertainty about the value of the goods they are buying. Some of these issues have been examined individually for single-unit sealed-bid auctions. However, in this paper, we extend this analysis to the multi-unit case, and also analyze the multi-unit sealed-bid auctions in which a combination of these issues are present, for unit-demand bidders. This analysis constitutes the main contribution of this paper. We then demonstrate the usefulness in practice of this analysis; we show in simulations that taking into account all these issues allows the bidders to maximize their utility. Furthermore, using this analysis allows a seller to improve her revenue, i.e. by selecting the optimal reserve price and auction format.     

Visualizing combinatorial auctions

We propose a novel scheme to visualize combinatorial auctions; auctions that involve the simultaneous sale of multiple items. Buyers bid on complementary sets of items, or bundles, where the utility of securing all the items in the bundle is more than the sum of the utility of the individual items. Our visualizations use concentric rings divided into arcs to visualize the bundles in an auction. The arcs’ positions and overlaps allow viewers to identify and follow bidding strategies. Properties of color, texture, and motion are used to represent different attributes of the auction, including active bundles, prices bid for each bundle, winning bids, and bidders’ interests. Keyframe animations are used to show changes in an auction over time. We demonstrate our visualization technique on a standard testbed dataset generated by researchers to evaluate combinatorial auction bid strategies, and on recent Federal Communications Commission (FCC) auctions designed to allocate wireless spectrum licenses to cell phone service providers.     

A multi-unit combinatorial auction based approach for decentralized multi-project scheduling

In industry, many problems are considered as the decentralized resource-constrained multi-project scheduling problem (DRCMPSP). Existing approaches encounter difficulties in dealing with large DRCMPSP cases while respecting the information privacy requirements of the project agents. In this paper, we tackle DRCMPSP by formulating it as a multi-unit combinatorial auction (Wellman et al. in Games Econ Behav 35(1):271–303, 2001), which does not require sensitive private project information. To handle the hardness of bidder valuation, we introduce the capacity query which uses different item capacity profiles to efficiently elicit valuation information from bidders. Based on the capacity query, we adopt two existing strategies (Gonen and Lehmann in Proceedings of the 2nd ACM conference on electronic commerce, pp 13–20, 2000) for solving multi-unit winner determination problems to find good allocations of the DRCMPSP auctions. The first strategy employs a greedy allocation process, which can rapidly find good allocations by allocating the bidder with the best answer after each query. The second strategy is based on a branch-and-bound process to improve the results of the first strategy, by searching for a better sequence of granting the bids from the bidders. Empirical results indicate that the two strategies can find good solutions with higher quality than state-of-the-art decentralized approaches, and scale well to large-scale problems with thousands of activities from tens of projects.     

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.     

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.     

Strong activity rules for iterative combinatorial auctions

Activity rules have emerged in recent years as an important aspect of practical auction design. The role of an activity rule in an iterative auction is to suppress strategic behavior by bidders and promote simple, continual, meaningful bidding and thus, price discovery. These rules find application in the design of iterative combinatorial auctions for real world scenarios, for example in spectrum auctions, in airline landing slot auctions, and in procurement auctions. We introduce the notion of strong activity rules, which allow simple, consistent bidding strategies while precluding all behaviors that cannot be rationalized in this way. We design such a rule for auctions with budget-constrained bidders, i.e., bidders with valuations for resources that are greater than their ability to pay. Such bidders are of practical importance in many market environments, and hindered from bidding in a simple and consistent way by the commonly used revealed-preference activity rule, which is too strong in such an environment. We consider issues of complexity, and provide two useful forms of information feedback to guide bidders in meeting strong activity rules. As a special case, we derive a strong activity rule for non-budget-constrained bidders. The ultimate choice of activity rule must depend, in part, on beliefs about the types of bidders likely to participate in an auction event because one cannot have a rule that is simultaneously strong for both budget-constrained bidders and quasi-linear bidders.     

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.     

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.     

Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions

In combinatorial auctions using VCG, a seller can sometimes increase revenue by dropping bidders. In this paper we investigate the extent to which this counterintuitive phenomenon can also occur under other deterministic, dominant-strategy combinatorial auction mechanisms. Our main result is that such failures of “revenue monotonicity” can occur under any such mechanism that is weakly maximal—meaning roughly that it chooses allocations that cannot be augmented to cause a losing bidder to win without hurting winning bidders—and that allows bidders to express arbitrary known single-minded preferences. We also give a set of other impossibility results as corollaries, concerning revenue when the set of goods changes, false-name-proofness, and the core.¹     

Assessing the benefits of group-buying-based combinatorial reverse auctions

Combinatorial reverse auctions represent a popular business model in procurement. For multiple buyers, different procurement models based on combinatorial reverse auctions may be applied. For example, each buyer may hold one combinatorial reverse auction independently. Alternatively, the buyers may delegate the auction to a group-buyer and let the group-buyer hold only one combinatorial reverse auction on behalf of all the buyers. A combination of a combinatorial reverse auctions with the group-buying model makes it possible to reduce the overall cost to acquire the required items significantly due to complementarities between items. However, combinatorial reverse auctions suffer from high computational complexity. To assess the advantage of combining group-buying with combinatorial reverse auctions, three issues must be addressed, including performance, computational efficiency and the scheme to reward the buyers. This motivates us to compare the performance and efficiency of the aforementioned two different combinatorial reverse auction models and to study the possible schemes to reward the buyers. To achieve these objectives, we first illustrate the advantage of group-buying-based combinatorial reverse auctions over multiple independent combinatorial reverse auctions. We then formulate the problems for these two combinatorial reverse auction models and propose solution algorithms for them. We compare performance and computational efficiency for these two combinatorial reverse auction models. Our analysis indicates that a group-buying-based combinatorial reverse auction not only outperforms multiple independent combinatorial reverse auctions but also is more efficient than multiple independent combinatorial reverse auctions. We also propose a non-uniform scheme to reward the buyers in group-buying based combinatorial reverse auctions.     

Comparing multiagent systems research in combinatorial auctions and voting

In a combinatorial auction, a set of items is for sale, and agents can bid on subsets of these items. In a voting setting, the agents decide among a set of alternatives by having each agent rank all the alternatives. Many of the key research issues in these two domains are similar. The aim of this paper is to give a convenient side-by-side comparison that will clarify the relation between the domains, and serve as a guide to future research.     

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.     

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.     

AND/OR Branch-and-Bound search for combinatorial optimization in graphical models

This is the first of two papers presenting and evaluating the power of a new framework for combinatorial optimization in graphical models, based on AND/OR search spaces. We introduce a new generation of depth-first Branch-and-Bound algorithms that explore the AND/OR search tree using static and dynamic variable orderings. The virtue of the AND/OR representation of the search space is that its size may be far smaller than that of a traditional OR representation, which can translate into significant time savings for search algorithms. The focus of this paper is on linear space search which explores the AND/OR search tree. In the second paper we explore memory intensive AND/OR search algorithms. In conjunction with the AND/OR search space we investigate the power of the mini-bucket heuristics in both static and dynamic setups. We focus on two most common optimization problems in graphical models: finding the Most Probable Explanation in Bayesian networks and solving Weighted CSPs. In extensive empirical evaluations we demonstrate that the new AND/OR Branch-and-Bound approach improves considerably over the traditional OR search strategy and show how various variable ordering schemes impact the performance of the AND/OR search scheme.     

Memory intensive AND/OR search for combinatorial optimization in graphical models

In this paper we explore the impact of caching during search in the context of the recent framework of AND/OR search in graphical models. Specifically, we extend the depth-first AND/OR Branch-and-Bound tree search algorithm to explore an AND/OR search graph by equipping it with an adaptive caching scheme similar to good and no-good recording. Furthermore, we present best-first search algorithms for traversing the same underlying AND/OR search graph and compare both algorithms empirically. We focus on two common optimization problems in graphical models: finding the Most Probable Explanation (MPE) in belief networks and solving Weighted CSPs (WCSP). In an extensive empirical evaluation we demonstrate conclusively the superiority of the memory intensive AND/OR search algorithms on a variety of benchmarks.     

A region-based formalism for picture processing

A set of structures and operations is proposed in terms of which picture processing algorithms can be expressed. The rectangular array model which has traditionally been used for this purpose is discussed and certain weaknesses in it are revealed. The structures and operations which comprise the formalism are described. They are based on the concept of a region. As an example an algorithm has been taken from the literature and is described using the formalism.