Página 13 dos resultados de 1418 itens digitais encontrados em 0.005 segundos

## Revisiting minimum profit conditions in uniform price day-ahead electricity auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 31/08/2015

Relevância na Pesquisa

26.94%

We examine the specific problem of clearing day-ahead electricity market
auctions where each bidder, whether a producer or consumer, can specify a
minimum profit or maximum payment condition constraining the acceptance of a
set of bid curves spanning multiple time periods in locations connected through
a transmission network with linear constraints. This helps describing e.g. the
recovery of start-up costs of a power plant, or analogously for a large
consumer, utility reduced by a constant term. We propose here a new market
model with a corresponding MILP formulation for uniform locational price
day-ahead auctions, handling bids with a minimum profit or maximum payment
condition, which we call MP bids, in a uniform and computationally-efficient
way. We also propose an exact decomposition procedure with sparse strengthened
Benders cuts derived from the MILP formulation. Both the MILP formulation and
the exact decomposition procedure are similar to computationally-efficient
approaches previously proposed to handle indivisible bids (so-called block
bids) according to European market rules, though the clearing conditions could
appear different at first sight. Indeed, the approach and the cuts proposed are
also valid to deal with both kinds of bids simultaneously...

Link permanente para citações:

## Multi-unit Auctions with Budget Constraints

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.94%

Motivated by sponsored search auctions, we study multi-unit auctions with
budget constraints. In the mechanism we propose, Sort-Cut, understating budgets
or values is weakly dominated. Since Sort-Cut's revenue is increasing in
budgets and values, all kinds of equilibrium deviations from true valuations
turn out to be beneficial to the auctioneer. We show that the revenue of
Sort-Cut can be an order of magnitude greater than that of the natural Market
Clearing Price mechanism, and we discuss the efficiency properties of its
ex-post Nash equilibrium.

Link permanente para citações:

## From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.94%

#Computer Science - Computer Science and Game Theory#Computer Science - Data Structures and Algorithms

We design an expected polynomial-time, truthful-in-expectation,
(1-1/e)-approximation mechanism for welfare maximization in a fundamental class
of combinatorial auctions. Our results apply to bidders with valuations that
are m matroid rank sums (MRS), which encompass most concrete examples of
submodular functions studied in this context, including coverage functions,
matroid weighted-rank functions, and convex combinations thereof. Our
approximation factor is the best possible, even for known and explicitly given
coverage valuations, assuming P != NP. Ours is the first
truthful-in-expectation and polynomial-time mechanism to achieve a
constant-factor approximation for an NP-hard welfare maximization problem in
combinatorial auctions with heterogeneous goods and restricted valuations.
Our mechanism is an instantiation of a new framework for designing
approximation mechanisms based on randomized rounding algorithms. A typical
such algorithm first optimizes over a fractional relaxation of the original
problem, and then randomly rounds the fractional solution to an integral one.
With rare exceptions, such algorithms cannot be converted into truthful
mechanisms. The high-level idea of our mechanism design framework is to
optimize directly over the (random) output of the rounding algorithm...

Link permanente para citações:

## Statistical properties of online auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 24/08/2006

Relevância na Pesquisa

26.94%

We characterize the statistical properties of a large number of online
auctions run on eBay. Both stationary and dynamic properties, like
distributions of prices, number of bids etc., as well as relations between
these quantities are studied. The analysis of the data reveals surprisingly
simple distributions and relations, typically of power-law form. Based on these
findings we introduce a simple method to identify suspicious auctions that
could be influenced by a form of fraud known as shill bidding. Furthermore the
influence of bidding strategies is discussed. The results indicate that the
observed behavior is related to a mixture of agents using a variety of
strategies.; Comment: 9 pages, 4 figures, to be published in Int. J. Mod. Phys. C

Link permanente para citações:

## Computational Analysis of Perfect-Information Position Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 04/08/2014

Relevância na Pesquisa

26.94%

After experimentation with other designs, the major search engines converged
on the weighted, generalized second-price auction (wGSP) for selling keyword
advertisements. Notably, this convergence occurred before position auctions
were well understood (or, indeed, widely studied) theoretically. While much
progress has been made since, theoretical analysis is still not able to settle
the question of why search engines found wGSP preferable to other position
auctions. We approach this question in a new way, adopting a new analytical
paradigm we dub "computational mechanism analysis." By sampling position
auction games from a given distribution, encoding them in a computationally
efficient representation language, computing their Nash equilibria, and then
calculating economic quantities of interest, we can quantitatively answer
questions that theoretical methods have not. We considered seven widely studied
valuation models from the literature and three position auction variants
(generalized first price, unweighted generalized second price, and wGSP). We
found that wGSP consistently showed the best ads of any position auction,
measured both by social welfare and by relevance (expected number of clicks).
Even in models where wGSP was already known to have bad worse-case efficiency...

Link permanente para citações:

## Clinching Auctions with Online Supply

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 04/10/2012

Relevância na Pesquisa

26.94%

Auctions for perishable goods such as internet ad inventory need to make
real-time allocation and pricing decisions as the supply of the good arrives in
an online manner, without knowing the entire supply in advance. These
allocation and pricing decisions get complicated when buyers have some global
constraints. In this work, we consider a multi-unit model where buyers have
global {\em budget} constraints, and the supply arrives in an online manner.
Our main contribution is to show that for this setting there is an
individually-rational, incentive-compatible and Pareto-optimal auction that
allocates these units and calculates prices on the fly, without knowledge of
the total supply. We do so by showing that the Adaptive Clinching Auction
satisfies a {\em supply-monotonicity} property.
We also analyze and discuss, using examples, how the insights gained by the
allocation and payment rule can be applied to design better ad allocation
heuristics in practice. Finally, while our main technical result concerns
multi-unit supply, we propose a formal model of online supply that captures
scenarios beyond multi-unit supply and has applications to sponsored search. We
conjecture that our results for multi-unit auctions can be extended to these
more general models.; Comment: Accepted to SODA'13

Link permanente para citações:

## Approximation Algorithms for Secondary Spectrum Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.94%

#Computer Science - Data Structures and Algorithms#Computer Science - Computer Science and Game Theory#Computer Science - Networking and Internet Architecture

We study combinatorial auctions for the secondary spectrum market. In this
market, short-term licenses shall be given to wireless nodes for communication
in their local neighborhood. In contrast to the primary market, channels can be
assigned to multiple bidders, provided that the corresponding devices are well
separated such that the interference is sufficiently low. Interference
conflicts are described in terms of a conflict graph in which the nodes
represent the bidders and the edges represent conflicts such that the feasible
allocations for a channel correspond to the independent sets in the conflict
graph.
In this paper, we suggest a novel LP formulation for combinatorial auctions
with conflict graph using a non-standard graph parameter, the so-called
inductive independence number. Taking into account this parameter enables us to
bypass the well-known lower bound of \Omega(n^{1-\epsilon}) on the
approximability of independent set in general graphs with n nodes (bidders). We
achieve significantly better approximation results by showing that interference
constraints for wireless networks yield conflict graphs with bounded inductive
independence number.
Our framework covers various established models of wireless communication...

Link permanente para citações:

## Prior-free Auctions for Budgeted Agents

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 23/12/2012

Relevância na Pesquisa

26.94%

We consider prior-free auctions for revenue and welfare maximization when
agents have a common budget. The abstract environments we consider are ones
where there is a downward-closed and symmetric feasibility constraint on the
probabilities of service of the agents. These environments include position
auctions where slots with decreasing click-through rates are auctioned to
advertisers. We generalize and characterize the envy-free benchmark from
Hartline and Yan (2011) to settings with budgets and characterize the optimal
envy-free outcomes for both welfare and revenue. We give prior-free mechanisms
that approximate these benchmarks. A building block in our mechanism is a
clinching auction for position auction environments. This auction is a
generalization of the multi-unit clinching auction of Dobzinski et al. (2008)
and a special case of the polyhedral clinching auction of Goel et al. (2012).
For welfare maximization, we show that this clinching auction is a good
approximation to the envy-free optimal welfare for position auction
environments. For profit maximization, we generalize the random sampling profit
extraction auction from Fiat et al. (2002) for digital goods to give a
10.0-approximation to the envy-free optimal revenue in symmetric...

Link permanente para citações:

## Bidding process in online auctions and winning strategy:rate equation approach

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 08/11/2005

Relevância na Pesquisa

26.94%

Online auctions have expanded rapidly over the last decade and have become a
fascinating new type of business or commercial transaction in this digital era.
Here we introduce a master equation for the bidding process that takes place in
online auctions. We find that the number of distinct bidders who bid $k$ times,
called the $k$-frequent bidder, up to the $t$-th bidding progresses as
$n_k(t)\sim tk^{-2.4}$. The successfully transmitted bidding rate by the
$k$-frequent bidder is obtained as $q_k(t) \sim k^{-1.4}$, independent of $t$
for large $t$. This theoretical prediction is in agreement with empirical data.
These results imply that bidding at the last moment is a rational and effective
strategy to win in an eBay auction.; Comment: 4 pages, 6 figures

Link permanente para citações:

## Clinching Auctions Beyond Hard Budget Constraints

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 19/04/2014

Relevância na Pesquisa

26.94%

Constraints on agent's ability to pay play a major role in auction design for
any setting where the magnitude of financial transactions is sufficiently
large. Those constraints have been traditionally modeled in mechanism design as
\emph{hard budget}, i.e., mechanism is not allowed to charge agents more than a
certain amount. Yet, real auction systems (such as Google AdWords) allow more
sophisticated constraints on agents' ability to pay, such as \emph{average
budgets}. In this work, we investigate the design of Pareto optimal and
incentive compatible auctions for agents with \emph{constrained quasi-linear
utilities}, which captures more realistic models of liquidity constraints that
the agents may have. Our result applies to a very general class of allocation
constraints known as polymatroidal environments, encompassing many settings of
interest such as multi-unit auctions, matching markets, video-on-demand and
advertisement systems.
Our design is based Ausubel's \emph{clinching framework}. Incentive
compatibility and feasibility with respect to ability-to-pay constraints are
direct consequences of the clinching framework. Pareto-optimality, on the other
hand, is considerably more challenging, since the no-trade condition that
characterizes it depends not only on whether agents have their budgets
exhausted or not...

Link permanente para citações:

## Equilibrium strategy and population-size effects in lowest unique bid auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Relevância na Pesquisa

26.94%

#Computer Science - Computer Science and Game Theory#Physics - Physics and Society#Quantitative Finance - General Finance

In lowest unique bid auctions, $N$ players bid for an item. The winner is
whoever places the \emph{lowest} bid, provided that it is also unique. We use a
grand canonical approach to derive an analytical expression for the equilibrium
distribution of strategies. We then study the properties of the solution as a
function of the mean number of players, and compare them with a large dataset
of internet auctions. The theory agrees with the data with striking accuracy
for small population size $N$, while for larger $N$ a qualitatively different
distribution is observed. We interpret this result as the emergence of two
different regimes, one in which adaptation is feasible and one in which it is
not. Our results question the actual possibility of a large population to adapt
and find the optimal strategy when participating in a collective game.; Comment: 6 pag. - 7 figs - added Supplementary Material. Changed affiliations.
Published version

Link permanente para citações:

## Concurrent Auctions Across The Supply Chain

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 30/06/2011

Relevância na Pesquisa

26.94%

With the recent technological feasibility of electronic commerce over the
Internet, much attention has been given to the design of electronic markets for
various types of electronically-tradable goods. Such markets, however, will
normally need to function in some relationship with markets for other related
goods, usually those downstream or upstream in the supply chain. Thus, for
example, an electronic market for rubber tires for trucks will likely need to
be strongly influenced by the rubber market as well as by the truck market. In
this paper we design protocols for exchange of information between a sequence
of markets along a single supply chain. These protocols allow each of these
markets to function separately, while the information exchanged ensures
efficient global behavior across the supply chain. Each market that forms a
link in the supply chain operates as a double auction, where the bids on one
side of the double auction come from bidders in the corresponding segment of
the industry, and the bids on the other side are synthetically generated by the
protocol to express the combined information from all other links in the chain.
The double auctions in each of the markets can be of several types, and we
study several variants of incentive compatible double auctions...

Link permanente para citações:

## E-loyalty networks in online auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 08/10/2010

Relevância na Pesquisa

26.94%

Creating a loyal customer base is one of the most important, and at the same
time, most difficult tasks a company faces. Creating loyalty online (e-loyalty)
is especially difficult since customers can ``switch'' to a competitor with the
click of a mouse. In this paper we investigate e-loyalty in online auctions.
Using a unique data set of over 30,000 auctions from one of the main
consumer-to-consumer online auction houses, we propose a novel measure of
e-loyalty via the associated network of transactions between bidders and
sellers. Using a bipartite network of bidder and seller nodes, two nodes are
linked when a bidder purchases from a seller and the number of repeat-purchases
determines the strength of that link. We employ ideas from functional principal
component analysis to derive, from this network, the loyalty distribution which
measures the perceived loyalty of every individual seller, and associated
loyalty scores which summarize this distribution in a parsimonious way. We then
investigate the effect of loyalty on the outcome of an auction. In doing so, we
are confronted with several statistical challenges in that standard statistical
models lead to a misrepresentation of the data and a violation of the model
assumptions. The reason is that loyalty networks result in an extreme
clustering of the data...

Link permanente para citações:

## Quantum Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 05/04/2007

Relevância na Pesquisa

26.94%

We present a quantum auction protocol using superpositions to represent bids
and distributed search to identify the winner(s). Measuring the final quantum
state gives the auction outcome while simultaneously destroying the
superposition. Thus non-winning bids are never revealed. Participants can use
entanglement to arrange for correlations among their bids, with the assurance
that this entanglement is not observable by others. The protocol is useful for
information hiding applications, such as partnership bidding with allocative
externality or concerns about revealing bidding preferences. The protocol
applies to a variety of auction types, e.g., first or second price, and to
auctions involving either a single item or arbitrary bundles of items (i.e.,
combinatorial auctions). We analyze the game-theoretical behavior of the
quantum protocol for the simple case of a sealed-bid quantum, and show how a
suitably designed adiabatic search reduces the possibilities for bidders to
game the auction. This design illustrates how incentive rather that
computational constraints affect quantum algorithm choices.; Comment: 38 pages, 3 figures

Link permanente para citações:

## Bid Optimization in Broad-Match Ad auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 23/01/2009

Relevância na Pesquisa

26.94%

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

Ad auctions in sponsored search support ``broad match'' that allows an
advertiser to target a large number of queries while bidding only on a limited
number. While giving more expressiveness to advertisers, this feature makes it
challenging to optimize bids to maximize their returns: choosing to bid on a
query as a broad match because it provides high profit results in one bidding
for related queries which may yield low or even negative profits.
We abstract and study the complexity of the {\em bid optimization problem}
which is to determine an advertiser's bids on a subset of keywords (possibly
using broad match) so that her profit is maximized. In the query language model
when the advertiser is allowed to bid on all queries as broad match, we present
an linear programming (LP)-based polynomial-time algorithm that gets the
optimal profit. In the model in which an advertiser can only bid on keywords,
ie., a subset of keywords as an exact or broad match, we show that this problem
is not approximable within any reasonable approximation factor unless P=NP. To
deal with this hardness result, we present a constant-factor approximation when
the optimal profit significantly exceeds the cost. This algorithm is based on
rounding a natural LP formulation of the problem. Finally...

Link permanente para citações:

## Secondary Spectrum Auctions for Symmetric and Submodular Bidders

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 26/10/2011

Relevância na Pesquisa

26.94%

#Computer Science - Data Structures and Algorithms#Computer Science - Computer Science and Game Theory#Computer Science - Networking and Internet Architecture

We study truthful auctions for secondary spectrum usage in wireless networks.
In this scenario, n communication requests need to be allocated to k available
channels that are subject to interference and noise. We present the first
truthful mechanisms for secondary spectrum auctions with symmetric or
submodular valuations. Our approach to model interference uses an edge-weighted
conflict graph, and our algorithms provide asymptotically almost optimal
approximation bounds for conflict graphs with a small inductive independence
number rho << n. This approach covers a large variety of interference models
such as, e.g., the protocol model or the recently popular physical model of
interference. For unweighted conflict graphs and symmetric valuations we use
LP-rounding to obtain $O(\rho)$-approximate mechanisms; for weighted conflict
graphs we get a factor of O(rho (log n + log k)). For submodular users we
combine the convex rounding framework of Dughmi et al [STOC 2011] with
randomized meta-rounding to obtain O(rho)-approximate mechanisms for
matroid-rank-sum valuations; for weighted conflict graphs we can fully drop the
dependence on k to get O(rho log n). We conclude with promising initialresults
for deterministically truthful mechanisms that allow approximation factors
based on rho.

Link permanente para citações:

## Self-Confirming Price Prediction Strategies for Simultaneous One-Shot Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 16/10/2012

Relevância na Pesquisa

26.94%

Bidding in simultaneous auctions is challenging because an agent's value for
a good in one auction may depend on the uncertain outcome of other auctions:
the so-called exposure problem. Given the gap in understanding of general
simultaneous auction games, previous works have tackled this problem with
heuristic strategies that employ probabilistic price predictions. We define a
concept of self-confirming prices, and show that within an independent private
value model, Bayes-Nash equilibrium can be fully characterized as a profile of
optimal price prediction strategies with self-confirming predictions. We
exhibit practical procedures to compute approximately optimal bids given a
probabilistic price prediction, and near self-confirming price predictions
given a price-prediction strategy. An extensive empirical game-theoretic
analysis demonstrates that self-confirming price prediction strategies are
effective in simultaneous auction games with both complementary and
substitutable preference structures.; Comment: Appears in Proceedings of the Twenty-Eighth Conference on Uncertainty
in Artificial Intelligence (UAI2012)

Link permanente para citações:

## Characterizing Optimal Adword Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 15/11/2006

Relevância na Pesquisa

26.94%

We present a number of models for the adword auctions used for pricing
advertising slots on search engines such as Google, Yahoo! etc. We begin with a
general problem formulation which allows the privately known valuation per
click to be a function of both the identity of the advertiser and the slot. We
present a compact characterization of the set of all deterministic incentive
compatible direct mechanisms for this model. This new characterization allows
us to conclude that there are incentive compatible mechanisms for this auction
with a multi-dimensional type-space that are {\em not} affine maximizers. Next,
we discuss two interesting special cases: slot independent valuation and slot
independent valuation up to a privately known slot and zero thereafter. For
both of these special cases, we characterize revenue maximizing and efficiency
maximizing mechanisms and show that these mechanisms can be computed with a
worst case computational complexity $O(n^2m^2)$ and $O(n^2m^3)$ respectively,
where $n$ is number of bidders and $m$ is number of slots. Next, we
characterize optimal rank based allocation rules and propose a new mechanism
that we call the customized rank based allocation. We report the results of a
numerical study that compare the revenue and efficiency of the proposed
mechanisms. The numerical results suggest that customized rank-based allocation
rule is significantly superior to the rank-based allocation rules.; Comment: 29 pages...

Link permanente para citações:

## Non-parametric Revenue Optimization for Generalized Second Price Auctions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 08/06/2015

Relevância na Pesquisa

26.94%

We present an extensive analysis of the key problem of learning optimal
reserve prices for generalized second price auctions. We describe two
algorithms for this task: one based on density estimation, and a novel
algorithm benefiting from solid theoretical guarantees and with a very
favorable running-time complexity of $O(n S \log (n S))$, where $n$ is the
sample size and $S$ the number of slots. Our theoretical guarantees are more
favorable than those previously presented in the literature. Additionally, we
show that even if bidders do not play at an equilibrium, our second algorithm
is still well defined and minimizes a quantity of interest. To our knowledge,
this is the first attempt to apply learning algorithms to the problem of
reserve price optimization in GSP auctions. Finally, we present the first
convergence analysis of empirical equilibrium bidding functions to the unique
symmetric Bayesian-Nash equilibrium of a GSP.; Comment: To be published in Proceedings of UAI 2015

Link permanente para citações:

## Single Parameter Combinatorial Auctions with Partially Public Valuations

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 20/07/2010

Relevância na Pesquisa

26.94%

We consider the problem of designing truthful auctions, when the bidders'
valuations have a public and a private component. In particular, we consider
combinatorial auctions where the valuation of an agent $i$ for a set $S$ of
items can be expressed as $v_if(S)$, where $v_i$ is a private single parameter
of the agent, and the function $f$ is publicly known. Our motivation behind
studying this problem is two-fold: (a) Such valuation functions arise naturally
in the case of ad-slots in broadcast media such as Television and Radio. For an
ad shown in a set $S$ of ad-slots, $f(S)$ is, say, the number of {\em unique}
viewers reached by the ad, and $v_i$ is the valuation per-unique-viewer. (b)
From a theoretical point of view, this factorization of the valuation function
simplifies the bidding language, and renders the combinatorial auction more
amenable to better approximation factors. We present a general technique, based
on maximal-in-range mechanisms, that converts any $\alpha$-approximation
non-truthful algorithm ($\alpha \leq 1$) for this problem into
$\Omega(\frac{\alpha}{\log{n}})$ and $\Omega(\alpha)$-approximate truthful
mechanisms which run in polynomial time and quasi-polynomial time,
respectively.

Link permanente para citações: