Catálogo de publicaciones - libros

In this paper we consider the optimal design of English auctions with discrete bid levels. Such auctions are widely used in online internet settings and our aim is to automate their configuration in order that they generate the maximum revenue for the auctioneer. Specifically, we address the problem of estimating the values of the parameters necessary to perform this optimal auction design by observing the bidding in previous auctions. To this end, we derive a general expression that relates the expected revenue of the auction when discrete bid levels are implemented, but the number of participating bidders is unknown. We then use this result to show that the characteristics of these optimal bid levels are highly dependent on the expected number of bidders and on their valuation distribution. Finally, we derive and demonstrate an online algorithm based on Bayesian machine learning, that allows these unknown parameters to be estimated through observations of the closing price of previous auctions. We show experimentally that this algorithm converges rapidly toward the true parameter values and, in comparison with an auction using the more commonly implemented fixed bid increment, results in an increase in auction revenue.

There is an extensive body of literature concerning optimal bidding strategies for agents participating in single shot auctions for single, individually valued goods. However, it remains a largely open question how a bidder should formulate his bidding strategy when there is a sequence of auctions and, furthermore, there are complementarities in the valuation for the bundle of items acquired in the separate auctions. We investigate conditions for which adjusting the bidding horizon beyond the immediate auction is profitable for a bidder. We show how such a strategy, in the limit, reduces agents to zero marginal profits as predicted by the Bertrand economic theory. We support our experimental results by drawing a parallel to the nIPD.

Sequential auctions are an important mechanism for buying/selling multiple objects. Now existing work in the area has studied sequential auctions for objects that are exclusively either common value or private value. However, in many real-world cases an object has both features. Also, in such cases, the common value depends on how much each bidder values the object. Moreover, a bidder generally does not know the true common value (since it may not know how much the other bidders value it). Given this, our objective is to study settings that have both common and private value elements by treating each bidder’s information about the common value as . Each object is modelled with two signals: one for its common value and the other for its private value. The auctions are conducted using English auction rules. For this model, we first determine equilibrium bidding strategies for each auction in a sequence. On the basis of this equilibrium, we find the expected and the for each auction. We then show that even if the common and private values of objects are distributed identically across all objects, the revenue and the winner’s profit are not the same for all of them. We show that, in accordance with Ashenfelter’s experimental results [1], the revenue for our model can decline in later auctions.

The problem of optimal winner determination in combinatorial auctions consists of finding the set of bids that maximize the revenue for the sellers. Various solutions exist for solving this problem but they are all centralized. That is, they assume that all bids are sent to a centralized auctioneer who then determines the winning set of bids. In this paper we introduce the problem of distributed winner determination in combinatorial auctions which eliminates the centralized auctioneer. We present a set of distributed search-based algorithms for solving this problem and study their relative tradeoffs.

We study multi-unit double auctions accepting bids with indivisibility constraints. We propose different price-quote policies and study their influence on the efficiency of market-based allocation. Using a reconfigurable manufacturing scenario where agents trade large quantities of multiple goods, we demonstrate potential benefits of supporting indivisibility constraints in bidding. These benefits are highly sensitive to the form of price quote provided, indicating interesting tradeoffs in communication and allocation efficiency.

Vickrey-Clarke-Groves (VCG) mechanisms are a well-known framework for finding a solution to a distributed optimization problem in systems of self-interested agents. VCG mechanisms have received wide attention in the AI community because they are efficient and strategy-proof; a special case of the Groves family of mechanisms, VCG mechanisms are the direct-revelation mechanisms that are allocatively efficient and strategy-proof. Unfortunately, VCG mechanisms are only weakly budget-balanced.

We consider self-interested agents in a network flow domain, and show that in this domain, it possible to design a mechanism that is both allocatively-efficient and almost completely budget-balanced. This is done by choosing a mechanism that is not but rather . Instead of using the VCG mechanism, we propose a mechanism in which finding the most beneficial manipulation is an NP-complete problem, and the payments from the agents to the mechanism may be minimized as much as desired. This way, the mechanism is virtually strongly budget-balanced: for any > 0, we find a mechanism that is -budget-balanced.

The Shapley value provides a unique solution to coalition games and is used to evaluate a player’s prospects of playing a game. Although it provides a unique solution, there is an element of uncertainty associated with this value. This uncertainty in the solution of a game provides an additional dimension for evaluating a player’s prospects of playing the game. Thus, players want to know not only their Shapley value for a game, but also the associated uncertainty. Given this, our objective is to determine the Shapley value and its uncertainty and study the relationship between them for the voting game. But since the problem of determining the Shapley value for this game is -complete, we first present a new polynomial time randomized method for determining the approximate Shapley value. Using this method, we compute the Shapley value and correlate it with its uncertainty so as to allow agents to compare games on the basis of both their Shapley values and the associated uncertainties. Our study shows that, a player’s uncertainty first increases with its Shapley value and then decreases. This implies that the uncertainty is at its minimum when the value is at its maximum, and that agents do not always have to compromise value in order to reduce uncertainty.

We present and analyze results from the 2004 Trading Agent Competition supply chain management scenario. We identify behavioral differences between the agents that contributed to their performance in the competition. In the market for components, strategic early procurement remained an important factor despite rule changes from the previous year. We present a new experimental analysis of the impact of the rule changes on incentives for early procurement. In the finals, a novel strategy designed to block other agent’s access to suppliers at the start of the game was pivotal. Some agents did not respond effectively to this strategy and were badly hurt by their inability to get crucial components. Among the top three agents, average selling prices in the market for finished goods were the decisive difference. Our analysis shows that supply and demand were key factors in determining overall market prices, and that some agents were more adept than others at exploiting advantageous market conditions.

We present methods for an autonomous agent to identify dominant market conditions, such as over-supply or scarcity, and to forecast market changes. We show that market conditions can be characterized by distinguishable statistical patterns that can be learned from historic data and used, together with real-time observable information, to identify the current market regime and to forecast market changes. We use a Gaussian Mixture Model to represent the probabilities of market prices and, by clustering these probabilities, we identify different economic regimes. We show that the regimes so identified have properties that correlate with market factors that are not directly observable. We then present methods to predict regime changes. We validate our methods by presenting experimental results obtained with data from the Trading Agent Competition for Supply Chain Management.

The Trading Agent Competition (TAC) is an open-invitation forum designed to encourage research into electronic markets and trading agents. In this paper we present the Socrates trading agent and the strategies that were developed for and used in the TAC Supply Chain Management game as part of the 2004 competition. The resulting behaviour and performance in the TAC competition as well as in a series of controlled experiments are discussed.