Página 1 dos resultados de 23 itens digitais encontrados em 0.003 segundos

## ‣ Seleção de fornecedores de serviço de transporte utilizando leilão combinatório de compras: adaptação e aplicação do algoritmo Iterative Deepening Search A* (IDA*).; Supplier selection of transportation services using reverse combinatorial auction: adaptation and aplication of Iterative Deepening Search A* (IDA*).

Higuita Salazar, Catalina
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
405.99168%

## ‣ Strong Activity Rules for Iterative Combinatorial Auctions

Harsha, Pavithra; Barnhart, Cynthia; Parkes, David C.; Zhang, Haoqi
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
407.32785%
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...

## ‣ A Modular Framework for Iterative Combinatorial Auctions

Lahaie, Sébastien; Parkes, David C.
Fonte: Association for Computing Machinery Publicador: Association for Computing Machinery
Tipo: Research Paper or Report
Português
Relevância na Pesquisa
401.38984%
We describe a modular elicitation framework for iterative combinatorial auctions. The framework includes proxy agents, each of which can adopt an individualized bidding language to represent partial value information of a bidder. The framework leverages algorithms from query learning to elicit value information via bids as the auction progresses. The approach reduces the multi-agent elicitation problem to isolated, single-agent learning problems, with competitive equilibrium prices used to facilitate auction clearing even without complete learning.; Engineering and Applied Sciences

## ‣ Models for Iterative Multiattribute Procurement Auctions

Parkes, David C.; Kalagnanam, Jayant
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
517.2985%
Multiattribute auctions extend traditional auction settings to allow negotiation over nonprice attributes such as weight, color, and terms of delivery, in addition to price and promise to improve market efficiency in markets with configurable goods. This paper provides an iterative auction design for an important special case of the multiattribute allocation problem with special (preferential independent) additive structure on the buyer value and seller costs. Auction Additive&Discrete provides a refined design for a price-based auction in which the price feedback decomposes to an additive part with a price for each attribute and an aggregate part that appears as a price discount for each supplier. In addition, this design also has excellent information revelation properties that are validated through computational experiments. The auction terminates with an outcome of a modified Vickrey-Clarke-Groves mechanism. This paper also develops Auction NonLinear&Discrete for the more general nonlinear case-a particularly simple design that solves the general multiattribute allocation problem, but requires that the auctioneer maintains prices on bundles of attribute levels.; Engineering and Applied Sciences

## ‣ An Iterative Generalized Vickrey Auction: Strategy-Proofness without Complete Revelation

Parkes, David C.
Tipo: Monograph or Book
Português
Relevância na Pesquisa
315.46605%
The generalized Vickrey auction (GVA) is a strategy-proof combinatorial auction, in which truthful bidding is the optimal strategy for an agent. In this paper we address a fundamental problem with the GVA, which is that it requires agents to compute and reveal their values for all combinations of items. This can be very difficult for bounded-rational agents with limited or costly computation. We propose an experimental design for an iterative combinatorial auction. We have a theoretical proof that the the auction implements the outcome of the Vickrey auction in special cases, and initial experimental results support our conjecture that the auction implements the outcome of the Vickrey auction in all cases. The auction has better information properties than the sealedbid GVA: in each round agents must only bid for the set of bundles that maximize their utility given current ask prices, which does not require agents to compute their exact values for every bundle.; Engineering and Applied Sciences

## ‣ Iterative Combinatorial Auctions: Theory and Practice

Parkes, David C.; Ungar, Lyle H.
Tipo: Monograph or Book
Português
Relevância na Pesquisa
305.99168%
Combinatorial auctions, which allow agents to bid directly for bundles of resources, are necessary for optimal auction-based solutions to resource allocation problems with agents that have non-additive values for resources, such as distributed scheduling and task assignment problems. We introduce iBundle, the first iterative combinatorial auction that is optimal for a reasonable agent bidding strategy, in this case myopic best-response bidding. Its optimality is proved with a novel connection to primal-dual optimization theory. We demonstrate orders of magnitude performance improvements over the only other known optimal combinatorial auction, the Generalized Vickrey Auction.; Engineering and Applied Sciences

## ‣ Preventing Strategic Manipulation in Iterative Auctions: Proxy Agents and Price-Adjustment

Parkes, David C.; Ungar, Lyle H.
Tipo: Monograph or Book
Português
Relevância na Pesquisa
315.58383%
Iterative auctions have many computational advantages over sealed-bid auctions, but can present new possibilities for strategic manipulation. We propose a two-stage technique to make iterative auctions that compute optimal allocations with myopic best-response bidding strategies more robust to manipulation. First, introduce proxy bidding agents to constrain bidding strategies to (possibly untruthful) myopic bestresponse. Second, after the auction terminates adjust the prices towards those given in the Vickrey auction, a sealedbid auction in which truth-revelation is optimal. We present an application of this methodology to iBundle, an iterative combinatorial auction which gives optimal allocations for myopic best-response agents.; Engineering and Applied Sciences

## ‣ Consensus-based auctions for decentralized task assignment

Brunet, Luc (Luc P. V.)
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 147 p.
Português
Relevância na Pesquisa
201.38984%
This thesis addresses the decentralized task assignment problem in cooperative autonomous search and track missions by presenting the Consensus-Based class of assignment algorithms. These algorithm make use of information consensus routines to converge on the assignment rather than the situational awareness of the fleet. A market-based approach is used as the mechanism for task selection, while the novel consensus stage of the algorithms allow for fast distributed conflict resolution. Three separate algorithms belonging to the Consensus-Based class of assignment strategies will be presented. The first is the Consensus-Based Auction Algorithm (CBAA), which is a single assignment auction strategy that is shown to be bounded within 50% of the optimal solution, while an upper-bound on convergence is presented. Two multi-assignment algorithms are then presented as extensions of the CBAA. The iterative CBAA executes the single assignment algorithm multiple times in order to build an assignment with multiple tasks. The second algorithm is the more general Consensus-Based Bundle Algorithm (CBBA) in which agents build a candidate bundle of tasks and bid on each task individually based on the improvement in score achieved by adding it to the bundle. Both algorithms are shown to be lower bounded by 50% optimality...

## ‣ Análisis de potencia en redes multiusuario mediante mecanismos de subastas

Aceituno Gómez, Daniel
Tipo: info:eu-repo/semantics/bachelorThesis; info:eu-repo/semantics/masterThesis Formato: application/pdf
Português
Relevância na Pesquisa
294.65553%

## ‣ Design of Auctions for Short-Term Allocation in Gas Markets Based on Virtual Hubs

VAZQUEZ, Miguel; HALLACK, Michelle
Fonte: Instituto Universitário Europeu Publicador: Instituto Universitário Europeu
Tipo: Trabalho em Andamento Formato: application/pdf
Português
Relevância na Pesquisa
297.7729%
Gas markets based on virtual hubs has been the preferred EU design. Such market designs are based on socializing network flexibility services. Nonetheless, shippers have different preferences about the network flexibility, which are not reflected in current allocation models. We propose the introduction of auction mechanisms to deal with network service allocation in the short term. The auction aims to represent simultaneously the diversity of players' preferences and the trade-offs implied by network constraints. Two sealed-bid auctions are proposed. On the one hand, an auction with one product allocates network services through the minimization of gas price differences. On the other, a multi-product (gas and line-pack storage) auction is designed to facilitate the revelation of preferences on line-pack storage.

## ‣ iBundle: An Efficient Ascending Price Bundle Auction

Parkes, David C.
Fonte: Association for Computing Machinery Publicador: Association for Computing Machinery
Tipo: Monograph or Book
Português
Relevância na Pesquisa
497.7729%
Standard auction mechanisms often break down in important e-commerce applications, where agents demand bundles of complementary resources, i.e. "I only want B if I also get A". This paper describes iBundle, an ascending-price auction that is guaranteed to compute optimal bundle allocations with agents that follow a best-response bidding strategy. The auction prices bundles directly and allows agents to place additive or exclusive-or bids over collections of bundles. Empirical results confirm that iBundle generates efficient allocations for hard resource allocation problems. Furthermore, we shoe that iBundle generates solutions without complete revelation (or computation) of agent preferences.; Engineering and Applied Sciences

## ‣ Maximum Weight Matching via Max-Product Belief Propagation

Bayati, Mohsen; Shah, Devavrat; Sharma, Mayank
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
179.6357%
Max-product "belief propagation" is an iterative, local, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding, computer vision and combinatorial optimization which involve graphs with many cycles, theoretical results about both correctness and convergence of the algorithm are known in few cases (Weiss-Freeman Wainwright, Yeddidia-Weiss-Freeman, Richardson-Urbanke}. In this paper we consider the problem of finding the Maximum Weight Matching (MWM) in a weighted complete bipartite graph. We define a probability distribution on the bipartite graph whose MAP assignment corresponds to the MWM. We use the max-product algorithm for finding the MAP of this distribution or equivalently, the MWM on the bipartite graph. Even though the underlying bipartite graph has many short cycles, we find that surprisingly, the max-product algorithm always converges to the correct MAP assignment as long as the MAP assignment is unique. We provide a bound on the number of iterations required by the algorithm and evaluate the computational cost of the algorithm. We find that for a graph of size $n$...

## ‣ Conservative collision prediction and avoidance for stochastic trajectories in continuous time and space

Calliess, Jan-Peter; Osborne, Michael; Roberts, Stephen
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
179.6357%
Existing work in multi-agent collision prediction and avoidance typically assumes discrete-time trajectories with Gaussian uncertainty or that are completely deterministic. We propose an approach that allows detection of collisions even between continuous, stochastic trajectories with the only restriction that means and variances can be computed. To this end, we employ probabilistic bounds to derive criterion functions whose negative sign provably is indicative of probable collisions. For criterion functions that are Lipschitz, an algorithm is provided to rapidly find negative values or prove their absence. We propose an iterative policy-search approach that avoids prior discretisations and yields collision-free trajectories with adjustably high certainty. We test our method with both fixed-priority and auction-based protocols for coordinating the iterative planning process. Results are provided in collision-avoidance simulations of feedback controlled plants.; Comment: This preprint is an extended version of a conference paper that is to appear in \textit{Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014)}

## ‣ Statistical mechanics of combinatorial auctions

Galla, Tobias; Leone, Michele; Marsili, Matteo; Sellitto, Mauro; Weigt, Martin; Zecchina, Riccardo
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
168.29953%
Combinatorial auctions are formulated as frustrated lattice gases on sparse random graphs, allowing the determination of the optimal revenue by methods of statistical physics. Transitions between computationally easy and hard regimes are found and interpreted in terms of the geometric structure of the space of solutions. We introduce an iterative algorithm to solve intermediate and large instances, and discuss competing states of optimal revenue and maximal number of satisfied bidders. The algorithm can be generalized to the hard phase and to more sophisticated auction protocols.; Comment: 4 pages, 4 figures, minor changes, references added. To appear on PRL

## ‣ Truthful Unsplittable Flow for Large Capacity Networks

Azar, Yossi; Gamzu, Iftah; Gutner, Shai
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
168.29953%
In this paper, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests characteristics, and may be dishonest about them. It is worth noting that in game theoretic settings many standard techniques, such as randomized rounding, violate certain monotonicity properties, which are imperative for truthfulness, and therefore cannot be employed. In light of this state of affairs, we design a monotone deterministic algorithm, which is based on a primal-dual machinery, which attains an approximation ratio of $\frac{e}{e-1}$, up to a disparity of $\epsilon$ away. This implies an improvement on the current best truthful mechanism, as well as an improvement on the current best combinatorial algorithm for the problem under consideration. Surprisingly, we demonstrate that any algorithm in the family of reasonable iterative path minimizing algorithms, cannot yield a better approximation ratio. Consequently, it follows that in order to achieve a monotone PTAS, if exists, one would have to exert different techniques. We also consider the large capacities \textit{single-minded multi-unit combinatorial auction problem}. This problem is closely related to the unsplittable flow problem since one can formulate it as a special case of the integer linear program of the unsplittable flow problem. Accordingly...

## ‣ An Iterative On-Line Mechanism for Demand-Side Aggregation

Chapman, Archie C.; Verbic, Gregor
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
305.99168%
This paper considers a demand-side aggregation scheme specifically for large numbers of small loads, such as households and small and medium-sized businesses. We introduce a novel auction format, called a staggered clock-proxy auction (SCPA), for on-line scheduling of these loads. This is a two phase format, consisting of: a sequence of overlapping iterative ascending-price clock auctions, one for each time-slot over a finite decision horizon, and; a set of proxy auctions that begin at the termination of each individual clock auction, and which determine the final price and allocation for each time-slot. The overlapping design of the clock phases grant bidders the ability to effectively bid on inter-temporal bundles of electricity use, thereby focusing on the most relevant parts of the price-quantity space. Since electricity is a divisible good, the proxy auction uses demand-schedule bids, which the aggregator uses to compute a uniform-price partial competitive equilibrium for each time slot. We show that, under mild assumptions on the bidders' utilities functions, the proxy phase implements the Vickrey-Clarke-Groves outcome, which makes straightforward bidding in the proxy phase a Bayes-Nash equilibrium. Furthermore, we demonstrate the SCPA in a scenario comprised of household agents with three different utility function types...

## ‣ Energy-Efficient Resource Allocation for Device-to-Device Underlay Communication

Wang, Feiran; Xu, Chen; Song, Lingyang; Han, Zhu
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
168.29953%
Device-to-device (D2D) communication underlaying cellular networks is expected to bring significant benefits for utilizing resources, improving user throughput and extending battery life of user equipments. However, the allocation of radio and power resources to D2D communication needs elaborate coordination, as D2D communication can cause interference to cellular communication. In this paper, we study joint channel and power allocation to improve the energy efficiency of user equipments. To solve the problem efficiently, we introduce an iterative combinatorial auction algorithm, where the D2D users are considered as bidders that compete for channel resources, and the cellular network is treated as the auctioneer. We also analyze important properties of D2D underlay communication, and present numerical simulations to verify the proposed algorithm.; Comment: IEEE Transactions on Wireless Communications

## ‣ Efficiency Resource Allocation for Device-to-Device Underlay Communication Systems: A Reverse Iterative Combinatorial Auction Based Approach

Xu, Chen; Song, Lingyang; Han, Zhu; Zhao, Qun; Wang, Xiaoli; Cheng, Xiang; Jiao, Bingli
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
313.06281%
Peer-to-peer communication has been recently considered as a popular issue for local area services. An innovative resource allocation scheme is proposed to improve the performance of mobile peer-to-peer, i.e., device-to-device (D2D), communications as an underlay in the downlink (DL) cellular networks. To optimize the system sum rate over the resource sharing of both D2D and cellular modes, we introduce a reverse iterative combinatorial auction as the allocation mechanism. In the auction, all the spectrum resources are considered as a set of resource units, which as bidders compete to obtain business while the packages of the D2D pairs are auctioned off as goods in each auction round. We first formulate the valuation of each resource unit, as a basis of the proposed auction. And then a detailed non-monotonic descending price auction algorithm is explained depending on the utility function that accounts for the channel gain from D2D and the costs for the system. Further, we prove that the proposed auction-based scheme is cheat-proof, and converges in a finite number of iteration rounds. We explain non-monotonicity in the price update process and show lower complexity compared to a traditional combinatorial allocation. The simulation results demonstrate that the algorithm efficiently leads to a good performance on the system sum rate.; Comment: 26 pages...

## ‣ Rate of Price Discovery in Iterative Combinatorial Auctions

Abernethy, Jacob; Lahaie, Sébastien; Telgarsky, Matus
Tipo: Artigo de Revista Científica