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*).

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%

#Algoritmo otimizante#Combinatorial auction#Fornecedor#Leilão combinatório#Multi-criteria#Multiplos critérios#Optimizing algorithm#Supplier#Winner Determination Problem (WDP)#Winner Determination Problem (WDP)

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...

Link permanente para citações:

## Strong Activity Rules for Iterative Combinatorial Auctions

Fonte: Elsevier
Publicador: Elsevier

Tipo: Artigo de Revista Científica

EN_US

Relevância na Pesquisa

36.68%

#combinatorial auctions#activity rules#budget-constrained bidders#bidding#utility-preference: theory

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...

Link permanente para citações:

## A Modular Framework for Iterative Combinatorial Auctions

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

Link permanente para citações:

## Models for Iterative Multiattribute Procurement Auctions

Fonte: INFORMS
Publicador: INFORMS

Tipo: Artigo de Revista Científica

EN_US

Relevância na Pesquisa

46.84%

#Vickrey-Clarke-Groves mechanism#ex post Nash equilibrium#iterative auctions#multiattribute negotiation#price-based feedback#procurement#straightforward bidding

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

Link permanente para citações:

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

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

Link permanente para citações:

## Iterative Combinatorial Auctions: Theory and Practice

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

Link permanente para citações:

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

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

Link permanente para citações:

## Consensus-based auctions for decentralized task assignment

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...

Link permanente para citações:

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

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%

#CDMA#Compartición de espectro#Teoría de juegos#Subastas#Spectrum sharing#Game theory#Auction#Telecomunicaciones

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...

Link permanente para citações:

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

Fonte: Instituto Universitário Europeu
Publicador: Instituto Universitário Europeu

Tipo: Trabalho em Andamento
Formato: application/pdf

EN

Relevância na Pesquisa

26.53%

#auction design#gas markets#gas balancing#entry/exit allocation#iterative and combinatorial auctions

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.

Link permanente para citações:

## iBundle: An Efficient Ascending Price Bundle Auction

Fonte: Association for Computing Machinery
Publicador: Association for Computing Machinery

Tipo: Monograph or Book

EN_US

Relevância na Pesquisa

46.53%

#agent-mediated electronic commerce#bunding problem#iterative auction#price discrimination#resource allocation

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

Link permanente para citações:

## Maximum Weight Matching via Max-Product Belief Propagation

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$...

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

16.25%

#Computer Science - Artificial Intelligence#Computer Science - Multiagent Systems#Computer Science - Robotics

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)}

Link permanente para citações:

## Statistical mechanics of combinatorial auctions

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

Link permanente para citações:

## Truthful Unsplittable Flow for Large Capacity Networks

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 14/04/2008

Relevância na Pesquisa

16.07%

#Computer Science - Data Structures and Algorithms#Computer Science - Computer Science and Game Theory#F.2

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...

Link permanente para citações:

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

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...

Link permanente para citações:

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

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 09/11/2012

Relevância na Pesquisa

26.77%

#Computer Science - Computer Science and Game Theory#Computer Science - Networking and Internet Architecture

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...

Link permanente para citações:

## Rate of Price Discovery in Iterative Combinatorial Auctions

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.

Link permanente para citações:

## Multiattribute Auctions Based on Generalized Additive Independence

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.

Link permanente para citações: