Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Ad Types Problem
122
0
0.0
(
0
)
Added by
Okke Schrijvers
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Ad Types Problem (without gap rules) is a special case of the assignment problem in which there are $k$ types of nodes on one side (the ads), and an ordered set of nodes on the other side (the slots). The edge weight of an ad $i$ of type $theta$ to slot $j$ is $v_icdot alpha^{theta}_j$ where $v_i$ is an advertiser-specific value and each ad type $theta$ has a discount curve $alpha^{(theta)}_{1} ge alpha^{(theta)}_{2} ge ... ge 0$ over the slots that is common for ads of type $theta$. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in $O(n^2(k + log n))$ time for $n$ slots and $n$ ads of each type---cf. $O(kn^3)$ when using the Hungarian algorithm---, and 2) we show to do VCG pricing in asymptotically the same time, namely $O(n^2(k + log n))$, and apply reserve prices in $O(n^3(k + log n))$. The Ad Types Problem (with gap rules) includes a matrix $G$ such that after we show an ad of type $theta_i$, the next $G_{ij}$ slots cannot show an ad of type $theta_j$. We show that the problem is hard to approximate within $k^{1- epsilon}$ for any $epsilon > 0$ (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem (including discount curves) optimally and runs in $O(kcdot n^{2k + 1})$ time.
rate research
Read More
This paper studies equilibrium quality of semi-separable position auctions (known as the Ad Types setting) with greedy or optimal allocation combined with generalized second-price (GSP) or Vickrey-Clarke-Groves (VCG) pricing. We make three contributions: first, we give upper and lower bounds on the Price of Anarchy (PoA) for auctions which use greedy allocation with GSP pricing, greedy allocations with VCG pricing, and optimal allocation with GSP pricing. Second, we give Bayes-Nash equilibrium characterizations for two-player, two-slot instances (for all auction formats) and show that there exists both a revenue hierarchy and revenue equivalence across some formats. Finally, we use no-regret learning algorithms and bidding data from a large online advertising platform and no-regret learning algorithms to evaluate the performance of the mechanisms under semi-realistic conditions. For welfare, we find that the optimal-to-realized welfare ratio (an empirical PoA analogue) is broadly better than our upper bounds on PoA; For revenue, we find that the hierarchy in practice may sometimes agree with simple theory, but generally appears sensitive to the underlying distribution of bidder valuations.
We study how standard auction objectives in sponsored search markets change with refinements in the prediction of the relevance (click-through rates) of ads. We study mechanisms that optimize for a convex combination of efficiency and revenue. We show that the objective function of such a mechanism can only improve with refined (improved) relevance predictions, i.e., the search engine has no disincentive to perform these refinements. More interestingly, we show that under assumptions, refinements to relevance predictions can only improve the efficiency of any such mechanism. Our main technical contribution is to study how relevance refinements affect the similarity between ranking by virtual-value (revenue ranking) and ranking by value (efficiency ranking). Finally, we discuss implications of our results to the literature on signaling.
Modern ad auctions allow advertisers to target more specific segments of the user population. Unfortunately, this is not always in the best interest of the ad platform. In this paper, we examine the following basic question in the context of second-price ad auctions: how should an ad platform optimally reveal information about the ad opportunity to the advertisers in order to maximize revenue? We consider a model in which bidders valuations depend on a random state of the ad opportunity. Different from previous work, we focus on a more practical, and challenging, situation where the space of possible realizations of ad opportunities is extremely large. We thus focus on developing algorithms whose running time is independent of the number of ad opportunity realizations. We examine the auctioneers algorithmic question of designing the optimal signaling scheme. When the auctioneer is restricted to send a public signal to all bidders, we focus on a well-motivated Bayesian valuation setting in which the auctioneer and bidders both have private information, and present two main results: 1. we exhibit a characterization result regarding approximately optimal schemes and prove that any constant-approximate public signaling scheme must use exponentially many signals; 2. we present a simple public signaling scheme that serves as a constant approximation under mild assumptions. We then initiate an exploration on the power of being able to send different signals privately to different bidders. Here we examine a basic setting where the auctioneer knows bidders valuations, and exhibit a polynomial-time private scheme that extracts almost full surplus even in the worst Bayes Nash equilibrium. This illustrates the surprising power of private signaling schemes in extracting revenue.
Extensive games are tools largely used in economics to describe decision processes ofa community of agents. In this paper we propose a formal presentation based on theproof assistant COQ which focuses mostly on infinite extensive games and theircharacteristics. COQ proposes a feature called dependent types, which meansthat the type of an object may depend on the type of its components. For instance,the set of choices or the set of utilities of an agent may depend on the agentherself. Using dependent types, we describe formally a very general class of gamesand strategy profiles, which corresponds somewhat to what game theorists are used to.We also discuss the notions of infiniteness in game theory and how this can beprecisely described.
This paper proposes the Potluck Problem as a model for the behavior of independent producers and consumers under standard economic assumptions, as a problem of resource allocation in a multi-agent system in which there is no explicit communication among the agents.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
