Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions

In pay-per-click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their advertisements (ads for short). A sponsored search auction for a keyword is typically conducted for a number of rounds (say T). There are click probabilities mu(ij) associated with each agent slot pair (agent i and slot j). The search engine would like to maximize the social welfare of the advertisers, that is, the sum of values of the advertisers for the keyword. However, the search engine does not know the true values advertisers have for a click to their respective advertisements and also does not know the click probabilities. A key problem for the search engine therefore is to learn these click probabilities during the initial rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced. These mechanisms, due to their connection to the multi-armed bandit problem, are aptly referred to as multi-armed bandit (MAB) mechanisms. When m = 1, exact characterizations for truthful MAB mechanisms are available in the literature. Recent work has focused on the more realistic but non-trivial general case when m > 1 and a few promising results have started appearing. In this article, we consider this general case when m > 1 and prove several interesting results. Our contributions include: (1) When, mu(ij)s are unconstrained, we prove that any truthful mechanism must satisfy strong pointwise monotonicity and show that the regret will be Theta T7) for such mechanisms. (2) When the clicks on the ads follow a certain click precedence property, we show that weak pointwise monotonicity is necessary for MAB mechanisms to be truthful. (3) If the search engine has a certain coarse pre-estimate of mu(ij) values and wishes to update them during the course of the T rounds, we show that weak pointwise monotonicity and type-I separatedness are necessary while weak pointwise monotonicity and type-II separatedness are sufficient conditions for the MAB mechanisms to be truthful. (4) If the click probabilities are separable into agent-specific and slot-specific terms, we provide a characterization of MAB mechanisms that are truthful in expectation.

Mechanism design for green, truthful procurement auctions

Auction based mechanisms have become popular in industrial procurement settings. These mechanisms minimize the cost of procurement and at the same time achieve desirable properties such as truthful bidding by the suppliers. In this paper, we investigate the design of truthful procurement auctions taking into account an additional important issue namely carbon emissions. In particular, we focus on the following procurement problem: A buyer wishes to source multiple units of a homogeneous item from several competing suppliers who offer volume discount bids and who also provide emission curves that specify the cost of emissions as a function of volume of supply. We assume that emission curves are reported truthfully since that information is easily verifiable through standard sources. First we formulate the volume discount procurement auction problem with emission constraints under the assumption that the suppliers are honest (that is they report production costs truthfully). Next we describe a mechanism design formulation for green procurement with strategic suppliers. Our numerical experimentation shows that emission constraints can significantly alter sourcing decisions and affect the procurement costs dramatically. To the best of our knowledge, this is the first effort in explicitly taking into account carbon emissions in planning procurement auctions.

Resale in Auctions with Financial Constraints

This paper analyzes auctions where bidders face nancial constraints that may force them to resell part of the property of the good (or subcontract part of a project) at a resale market. First we show that the ine¢ cient speculative equilibria of second- price auctions (Garratt and Tröger, 2006) generalizes to situations with partial resale where only the high value bidder is nancially constrained. However, when all players face nancial constraints the ine¢ cient speculative equilibria disappear. Therefore, for auctioning big facilities or contracts where all bidders are nancially constrained and there is a resale market, the second price auction remains a simple and appropriate mechanism to achieve an e¢ cient allocation.

The von Neumann Minimax Theorem and its relatives and a study of externality in on-line auctions

This work consists of a theoretical part and an experimental one. The first part provides a simple treatment of the celebrated von Neumann minimax theorem as formulated by Nikaid6 and Sion. It also discusses its relationships with fundamental theorems of convex analysis. The second part is about externality in sponsored search auctions. It shows that in these auctions, advertisers have externality effects on each other which influence their bidding behavior. It proposes Hal R.Varian model and shows how adding externality to this model will affect its properties. In order to have a better understanding of the interaction among advertisers in on-line auctions, it studies the structure of the Google advertisements networ.k and shows that it is a small-world scale-free network.

Temporary and Permanent Buyout Prices in Online Auctions

Increasingly used in online auctions, buyout prices allow bidders to instantly purchase the item listed. We distinguish two types: a temporary buyout option disappears if a bid above the reserve price is made; a permanent one remains throughout the auction or until it is exercised. In a model featuring time-sensitive bidders with uniform valuations and Poisson arrivals but endogenous bidding times, we focus on finding temporary and permanent buyout prices maximizing the seller's discounted revenue, and examine the relative benefit of using each type of option in various environments. We characterize equilibrium bidder strategies in both cases and then solve the problem of maximizing seller's utility by simulation. Our numerical experiments suggest that buyout options may significantly increase a seller’s revenue. Additionally, while a temporary buyout option promotes early bidding, a permanent option gives an incentive to the bidders to bid late, thus leading to concentrated bids near the end of the auction.

Selecting Scientific Papers for Publication via Citation Auctions

The scientific community has been suffering from peer review for decades. This process (also called refereeing) subjects an author's scientific work or ideas to the scrutiny of one or more experts in the field. Publishers use it to select and screen manuscript submissions, and funding agencies use it to award research funds. The goal is to get authors to meet their discipline's standards and thus achieve scientific objectivity. Publications and awards that haven't undergone peer review are often regarded with suspicion by scholars and professionals in many fields. However, peer review, although universally used, has many drawbacks. We propose replacing peer review with an auction-based approach: the better the submitted paper, the more scientific currency the author likely bid to have it published. If the bid correctly reflects the paper's quality, the author is rewarded in this new scientific currency; otherwise, the author loses this currency. We argue that citations are an appropriate currency for all scientists. We believe that citation auctions encourage scientists to better control their submissions' quality. It also inspire them to prepare more exciting talks for accepted papers and to invite discussion of their results at congresses and conferences and among their colleagues. In the long run, citation auctions could have the power to greatly improve scientific research

Citation auctions as a method to improve selection of scientific papers

This paper describes the basis of citation auctions as a new approach to selecting scientific papers for publication. Our main idea is to use an auction for selecting papers for publication through - differently from the state of the art - bids that consist of the number of citations that a scientist expects to receive if the paper is published. Hence, a citation auction is the selection process itself, and no reviewers are involved. The benefits of the proposed approach are two-fold. First, the cost of refereeing will be either totally eliminated or significantly reduced, because the process of citation auction does not need prior understanding of the paper's content to judge the quality of its contribution. Additionally, the method will not prejudge the content of the paper, so it will increase the openness of publications to new ideas. Second, scientists will be much more committed to the quality of their papers, paying close attention to distributing and explaining their papers in detail to maximize the number of citations that the paper receives. Sample analyses of the number of citations collected in papers published in years 1999-2004 for one journal, and in years 2003-2005 for a series of conferences (in a totally different discipline), via Google scholar, are provided. Finally, a simple simulation of an auction is given to outline the behaviour of the citation auction approach

Information provision in procurement auctions

We analyze the optimal provision of information in a procurement auction with horizontally differentiated goods. The buyer has private information about her preferred location on the product space and has access to a costless communication device. A seller who pays the entry cost may submit a bid comprising a location and a minimum price. We characterize the optimal information structure and show that the buyer prefers to attract only two bids. Further, additional sellers are inefficient since they reduce total and consumer surplus, gross of entry costs. We show that the buyer will not find it optimal to send public information to all sellers. On the other hand, she may profit from setting a minimum price and that a severe hold-up problem arises if she lacks commitment to set up the rules of the auction ex-ante.

Egalitarian behaviour in multi unit combinatorial auctions

En entornos donde los recursos son precederos y la asignación de recursos se repite en el tiempo con el mismo conjunto o un conjunto muy similar de agentes, las subastas recurrentes pueden ser utilizadas. Una subasta recurrente es una secuencia de subastas donde el resultado de una subasta puede influenciar en las siguientes. De todas formas, este tipo de subastas tienen problemas particulares cuando la riqueza de los agentes esta desequilibrada y los recursos son precederos. En esta tesis se proponen algunos mecanismos justos o equitativos para minimizar los efectos de estos problemas. En una subasta recurrente una solución justa significa que todos los participantes consiguen a largo plazo sus objetivos en el mismo grado o en el grado más parecido posible, independientemente de su riqueza. Hemos demostrado experimentalmente que la inclusión de justicia incentiva a los bidders en permanecer en la subasta minimizando los problemas de las subastas recurrentes.

Effect of Information about benefits of biotechnology on consumer acceptance of genetically modified food; evidence from experimental auctions in the United States, England, and France

This study investigates the effect of information about potential benefits of biotechnology on consumer acceptance of genetically modified (GM) foods. Consumer willingness to accept compensation to consume a GM food was elicited using an incentive compatible auction mechanism in three US states (California, Florida, and Texas) and in two European countries (England and France). Results indicate that information on environmental benefits, health benefits and benefits to the third world significantly decreased the amount of money consumers demanded to consume GM food; however, the effect of information varied by type of information and location. Consistent with prior research, we find that initial attitudes toward biotechnology have a significant effect on how individuals responded to new information.

The role of undisclosed reserves in English open outcry auctions

This study considers the role that reserve prices may play in residential property auctions. In comparison to much of the previous empirical work, this study has access to undisclosed reserve prices from English auctions. Consistent with theoretical arguments in the auction literature, the results obtained illustrate that whilst higher reserve prices increase the revenue obtained for the seller, they also reduce the probability of sale. The findings also highlight the importance of auction participation, with the number of individual bidders and the number of bids significant in most specifications.

The role of undisclosed reserves in English open outcry auctions

This study considers the role that reserve prices may play in residential property auctions. In comparison to much of the previous empirical work, this study has access to undisclosed reserve prices from English auctions. Consistent with theoretical arguments in the auction literature, the results obtained illustrate that whilst higher reserve prices increase the revenue obtained for the seller, they also reduce the probability of sale. The findings also highlight the importance of auction participation, with the number of individual bidders and the number of bids significant in most specifications.

Modeling bidding competitiveness and position performance in multi-attribute construction auctions

Currently, multi-attribute auctions are becoming widespread awarding mechanisms for contracts in construction, and in these auctions, criteria other than price are taken into account for ranking bidder proposals. Therefore, being the lowest-price bidder is no longer a guarantee of being awarded, thus increasing the importance of measuring any bidder’s performance when not only the first position (lowest price) matters. Modeling position performance allows a tender manager to calculate the probability curves related to the more likely positions to be occupied by any bidder who enters a competitive auction irrespective of the actual number of future participating bidders. This paper details a practical methodology based on simple statistical calculations for modeling the performance of a single bidder or a group of bidders, constituting a useful resource for analyzing one’s own success while benchmarking potential bidding competitors.

Quick abnormal-bid-detection method for construction contract auctions

Noncompetitive bids have recently become a major concern in both public and private sector construction contract auctions. Consequently, several models have been developed to help identify bidders potentially involved in collusive practices. However, most of these models require complex calculations and extensive information that is difficult to obtain. The aim of this paper is to utilize recent developments for detecting abnormal bids in capped auctions (auctions with an upper bid limit set by the auctioner) and extend them to the more conventional uncapped auctions (where no such limits are set). To accomplish this, a new method is developed for estimating the values of bid distribution supports by using the solution to what has become known as the German Tank problem. The model is then demonstrated and tested on a sample of real construction bid data, and shown to detect cover bids with high accuracy. This paper contributes to an improved understanding of abnormal bid behavior as an aid to detecting and monitoring potential collusive bid practices.

Analysis of the distribution of the number of bidders in construction contract auctions

The number of bidders, N, involved in a construction procurement auction is known to have an important effect on the value of the lowest bid and the mark-up applied by bidders. In practice, for example, it is important for a bidder to have a good estimate of N when bidding for a current contract. One approach, instigated by Friedman in 1956, is to make such an estimate by statistical analysis and modelling. Since then, however, finding a suitable model for N has been an enduring problem for researchers and, despite intensive research activity in the subsequent 30 years, little progress has been made, due principally to the absence of new ideas and perspectives. The debate is resumed by checking old assumptions, providing new evidence relating to concomitant variables and proposing a new model. In doing this and in order to ensure universality, a novel approach is developed and tested by using a unique set of 12 construction tender databases from four continents. This shows the new model provides a significant advancement on previous versions. Several new research questions are also posed and other approaches identified for future study.