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

Tipo: Artigo de Revista Científica
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...

## Multi-unit Auctions with Budget Constraints

Hafalir, I.; Ravi, R.; Sayedi, A.
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.

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

Dughmi, Shaddin; Roughgarden, Tim; Yan, Qiqi
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.94%
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...

## Statistical properties of online auctions

Tipo: Artigo de Revista Científica
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

## Computational Analysis of Perfect-Information Position Auctions

Thompson, David R. M; Leyton-Brown, Kevin
Tipo: Artigo de Revista Científica
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...

## Clinching Auctions with Online Supply

Goel, Gagan; Mirrokni, Vahab; Leme, Renato Paes
Tipo: Artigo de Revista Científica
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

## Approximation Algorithms for Secondary Spectrum Auctions

Hoefer, Martin; Kesselheim, Thomas; Vöcking, Berthold
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.94%
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...

## Prior-free Auctions for Budgeted Agents

Devanur, Nikhil R.; Ha, Bach Q.; Hartline, Jason D.
Tipo: Artigo de Revista Científica
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...

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

Yang, I.; Kahng, B.
Tipo: Artigo de Revista Científica
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

## Clinching Auctions Beyond Hard Budget Constraints

Goel, Gagan; Mirrokni, Vahab; Leme, Renato Paes
Tipo: Artigo de Revista Científica
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...

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

Pigolotti, Simone; Bernhardsson, Sebastian; Juul, Jeppe; Galster, Gorm; Vivo, Pierpaolo
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.94%
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

## Concurrent Auctions Across The Supply Chain

Babaioff, M.; Nisan, N.
Tipo: Artigo de Revista Científica
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...

## E-loyalty networks in online auctions

Jank, Wolfgang; Yahav, Inbal
Tipo: Artigo de Revista Científica
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...

## Quantum Auctions

Hogg, Tad; Harsha, Pavithra; Chen, Kay-Yut
Tipo: Artigo de Revista Científica
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

Even-dar, Eyal; Mansour, Yishay; Mirrokni, Vahab; Muthukrishnan, S.; Nadav, Uri
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.94%
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...

## Secondary Spectrum Auctions for Symmetric and Submodular Bidders

Hoefer, Martin; Kesselheim, Thomas
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
26.94%
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.

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

Wellman, Michael P.; Sodomka, Eric; Greenwald, Amy
Tipo: Artigo de Revista Científica
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)

Iyengar, Garud; Kumar, Anuj
Tipo: Artigo de Revista Científica
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...

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

Mohri, Mehryar; Medina, Andres Munoz
Tipo: Artigo de Revista Científica
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
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.