An official website of the United States government
This paper proposes Addax, a fast, verifiable, and private online ad exchange. When a user visits an ad-supported site, Addax runs an auction similar to those of leading exchanges; Addax requests bids, selects the winner, collects payment, and displays the ad to the user. A key distinction is that bids in Addax’s auctions are kept private and the outcome of the auction is publicly verifiable. Addax achieves these properties by adding public verifiability to the affine aggregatable encodings in Prio (NSDI’17) and by building an auction protocol out of them. Our implementation of Addax over WAN with hundreds of bidders can run roughly half the auctions per second as a non-private and non-verifiable exchange, while delivering ads to users in under 600 ms with little additional bandwidth requirements. This efficiency makes Addax the first architecture capable of bringing transparency to this otherwise opaque ecosystem.
more »
« less
Auctioning off a Non-Rivalrous Good with Interference
Auctions are a prevalent way to exchange goods and are well-studied for the exchange of rivalrous goods, but are less studied for non-rivalrous goods. I examine an auction framework where the good sold can be used simultaneously by multiple bidders if their use does not conflict with others; this simultaneous use directly affects the efficiency of the auction. A timely example includes the auctioning off of a radio spectrum by a licensed primary user to unlicensed secondary users who can use the spectrum simultaneously if they are located far enough apart to not cause interference. I examine a uniform price auction over non-conflicting groups and examine how non-rivalry impacts both efficiency and collusion. Conditions are given under which an auction over groups generates higher social welfare than an individual auction. Additional conditions are given under which collusion in a group auction results in higher prices.
more »
« less
- PAR ID:
- 10534923
- Publisher / Repository:
- MDPI
- Date Published:
- Journal Name:
- Games
- Volume:
- 15
- Issue:
- 4
- ISSN:
- 2073-4336
- Page Range / eLocation ID:
- 26
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract During reionization, intergalactic ionization fronts (I-fronts) are sources of Lyαline radiation produced by collisional excitation of hydrogen atoms within the fronts. In principle, detecting this emission could provide direct evidence for a reionizing intergalactic medium (IGM). In this paper, we use a suite of high-resolution one-dimensional radiative transfer simulations run on cosmological density fields to quantify the parameter space of I-front Lyαemission. We find that the Lyαproduction efficiency — the ratio of emitted Lyαflux to incident ionizing flux driving the front — depends mainly on the I-front speed and the spectral index of the ionizing radiation. IGM density fluctuations on scales smaller than the typical I-front width produce scatter in the efficiency, but they do not significantly boost its mean value. The Lyαflux emitted by an I-front is largest if 3 conditions are met simultaneously: (1) the incident ionizing flux is large; (2) the incident spectrum is hard, consisting of more energetic photons; (3) the I-front is traveling through a cosmological over-density, which causes it to propagate more slowly. We present a convenient parameterization of the efficiency in terms of I-front speed and incident spectral index. We make these results publicly available as an interpolation table and we provide a simple fitting function for a representative ionizing background spectrum. Our results can be applied as a sub-grid model for I-front Lyα emissions in reionization simulations with spatial and/or temporal resolutions too coarse to resolve I-front structure. In a companion paper, we use our results to explore the possibility of directly imaging Lyαemission around neutral islands during the last phases of reionization.more » « less
-
We consider a practically motivated variant of the canonical online fair allocation problem: a decision-maker has a budget of resources to allocate over a fixed number of rounds. Each round sees a random number of arrivals, and the decision-maker must commit to an allocation for these individuals before moving on to the next round. In contrast to prior work, we consider a setting in which resources are perishable and individuals' utilities are potentially non-linear (e.g., goods exhibit complementarities). The goal is to construct a sequence of allocations that is envy-free and efficient. We design an algorithm that takes as input (i) a prediction of the perishing order, and (ii) a desired bound on envy. Given the remaining budget in each period, the algorithm uses forecasts of future demand and perishing to adaptively choose one of two carefully constructed guardrail quantities. We characterize conditions under which our algorithm achieves the optimal envy-efficiency Pareto frontier. We moreover demonstrate its strong numerical performance using data from a partnering food bank.more » « less
-
null (Ed.)We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format A satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful O(1)-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17].more » « less
-
We develop a new framework for designing truth- ful, high-revenue (combinatorial) auctions for limited supply. Our mechanism learns within an instance. It generalizes and improves over previously-studied random-sampling mechanisms. It first samples a participatory group of bidders, then samples several learning groups of bidders from the remaining pool of bidders, learns a high- revenue auction from the learning groups, and fi- nally runs that auction on the participatory group. Previous work on random-sampling mechanisms focused primarily on unlimited supply. Limited supply poses additional significant technical chal- lenges, since allocations of items to bidders must be feasible. We prove guarantees on the performance of our mechanism based on a market-shrinkage term and a new complexity measure we coin par- tition discrepancy. Partition discrepancy simulta- neously measures the intrinsic complexity of the mechanism class and the uniformity of the set of bidders. We then introduce new auction classes that can be parameterized in a way that does not depend on the number of bidders participating, and prove strong guarantees for these classes. We show how our mechanism can be implemented efficiently by leveraging practically-efficient routines for solv- ing winner determination. Finally, we show how to use structural revenue maximization to decide what auction class to use with our framework when there is a constraint on the number of learning groups.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3390/g15040026
