Página 1 dos resultados de 23 itens digitais encontrados em 0.001 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
Publicado em 15/12/2011 PT
Relevância na Pesquisa
36.66%
A seleção de fornecedores de transporte é um desafio cada vez maior. O crescimento da rede de clientes a ser coberta demanda uma alocação eficiente em termos de custo não suprida por mecanismos tradicionais de negociação. Neste âmbito, o leilão combinatório torna-se uma alternativa de negociação ao permitir capturar sinergias entre os trajetos que devem ser atendidos. Em conseqüência disso, diminui-se o custo de transporte do fornecedor que se reflete nos menores preços de suas propostas e finalmente no custo total de compra do serviço. Por outro lado, esta decisão envolve fatores além do custo total; a mensuração destes torna-se importante para identificar fornecedores que melhor se ajustam aos requerimentos do comprador. No entanto, é fundamental escolher um método adequado para sua avaliação porque este influência a decisão final. Este problema de compra de serviços de transporte é conhecido na literatura como Winner Determination Problem (WDP) que, devido a sua complexidade, possui uma resolução limitada. Após revisão teórica, foi observado que os estudos relacionados à área de transporte focalizavam o desenvolvimento de modelos matemáticos que fossem representativos da realidade. Alguns destes modelos abordam a utilização de múltiplos critérios atribuindo um coeficiente que pondera cada critério. Evidenciou-se a necessidade do desenvolvimento de um algoritmo alternativo que além de facilitar sinergias entre trajetos...

Strong Activity Rules for Iterative Combinatorial Auctions

Harsha, Pavithra; Barnhart, Cynthia; Parkes, David C.; Zhang, Haoqi
Fonte: Elsevier Publicador: Elsevier
Tipo: Artigo de Revista Científica
EN_US
Relevância na Pesquisa
36.68%
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
EN_US
Relevância na Pesquisa
36.59%
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
Fonte: INFORMS Publicador: INFORMS
Tipo: Artigo de Revista Científica
EN_US
Relevância na Pesquisa
46.84%
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.
Fonte: Association for the Advancement of Artificial Intelligence Publicador: Association for the Advancement of Artificial Intelligence
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
26.81%
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.
Fonte: Association for the Advancement of Artificial Intelligence Publicador: Association for the Advancement of Artificial Intelligence
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
26.66%
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.
Fonte: Association for the Advancement of Artificial Intelligence Publicador: Association for the Advancement of Artificial Intelligence
Tipo: Monograph or Book
EN_US
Relevância na Pesquisa
26.81%
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.
ENG
Relevância na Pesquisa
16.59%
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
Fonte: Universidade Carlos III de Madrid Publicador: Universidade Carlos III de Madrid
Tipo: info:eu-repo/semantics/bachelorThesis; info:eu-repo/semantics/masterThesis Formato: application/pdf
SPA
Relevância na Pesquisa
26.48%
Se ha estudiado un mecanismo de subasta para la compartición de espectro entre un grupo de usuarios. Todo ello bajo la restricción de la temperatura de interferencia en un punto de medida. Los usuarios acceden al canal usando la técnica de espectro ensanchado CDMA. Cada uno recibe una utilidad que es función de la relación señal a interferencia más ruido, SINR. Se ha propuesto un mecanismo para asignar la potencia recibida en el que al usuario se le cobra por la SINR recibida. Combinado con utilidades logarítmicas, esto conduce a una asignación justa basada en pesos. Por último, se ha formulado e implementado un algoritmo distribuido e iterativo de actualización de apuestas que converge al equilibrio de Nash de la subasta.-------------------------------------------------------------------------; We study an auction mechanism for sharing spectrum among a group of users, subject to a constraint on the interference temperature at a measurement point. The users access the channel using spread spectrum signaling CDMA. Each user receives a utility that is a function of the received signal-to-interference plus noise ratio. We propose an auction mechanism for allocating the received power in which users are charged for received SINR...

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
EN
Relevância na Pesquisa
26.53%
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
EN_US
Relevância na Pesquisa
46.53%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.25%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.25%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
16.07%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/04/2008
Relevância na Pesquisa
16.07%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 01/06/2015
Relevância na Pesquisa
26.66%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/12/2014
Relevância na Pesquisa
16.07%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/11/2012
Relevância na Pesquisa
26.77%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 18/11/2015
Relevância na Pesquisa
26.25%
We study a class of iterative combinatorial auctions which can be viewed as subgradient descent methods for the problem of pricing bundles to balance supply and demand. We provide concrete convergence rates for auctions in this class, bounding the number of auction rounds needed to reach clearing prices. Our analysis allows for a variety of pricing schemes, including item, bundle, and polynomial pricing, and the respective convergence rates confirm that more expressive pricing schemes come at the cost of slower convergence. We consider two models of bidder behavior. In the first model, bidders behave stochastically according to a random utility model, which includes standard best-response bidding as a special case. In the second model, bidders behave arbitrarily (even adversarially), and meaningful convergence relies on properly designed activity rules.

Multiattribute Auctions Based on Generalized Additive Independence

Engel, Yagil; Wellman, Michael P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/01/2014
Relevância na Pesquisa
26.41%
We develop multiattribute auctions that accommodate generalized additive independent (GAI) preferences. We propose an iterative auction mechanism that maintains prices on potentially overlapping GAI clusters of attributes, thus decreases elicitation and computational burden, and creates an open competition among suppliers over a multidimensional domain. Most significantly, the auction is guaranteed to achieve surplus which approximates optimal welfare up to a small additive factor, under reasonable equilibrium strategies of traders. The main departure of GAI auctions from previous literature is to accommodate non-additive trader preferences, hence allowing traders to condition their evaluation of specific attributes on the value of other attributes. At the same time, the GAI structure supports a compact representation of prices, enabling a tractable auction process. We perform a simulation study, demonstrating and quantifying the significant efficiency advantage of more expressive preference modeling. We draw random GAI-structured utility functions with various internal structures, generate additive functions that approximate the GAI utility, and compare the performance of the auctions using the two representations. We find that allowing traders to express existing dependencies among attributes improves the economic efficiency of multiattribute auctions.