Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-quasi-linear Agents in Quasi-linear Mechanisms
177
0
0.0
(
0
)
Added by
Brendan Lucier
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks.
rate research
Read More
We consider agents with non-linear preferences given by private values and private budgets. We quantify the extent to which posted pricing approximately optimizes welfare and revenue for a single agent. We give a reduction framework that extends the approximation of multi-agent pricing-based mechanisms from linear utility to nonlinear utility. This reduction framework is broadly applicable as Alaei et al. (2012) have shown that mechanisms for linear agents can generally be interpreted as pricing-based mechanisms. We give example applications of the framework to oblivious posted pricing (e.g., Chawla et al., 2010), sequential posted pricing (e.g., Yan, 2011), and virtual surplus maximization (Myerson, 1981).
Without monetary payments, the Gibbard-Satterthwaite theorem proves that under mild requirements all truthful social choice mechanisms must be dictatorships. When payments are allowed, the Vickrey-Clarke-Groves (VCG) mechanism implements the value-maximizing choice, and has many other good properties: it is strategy-proof, onto, deterministic, individually rational, and does not make positive transfers to the agents. By Roberts theorem, with three or more alternatives, the weighted VCG mechanisms are essentially unique for domains with quasi-linear utilities. The goal of this paper is to characterize domains of non-quasi-linear utilities where reasonable mechanisms (with VCG-like properties) exist. Our main result is a tight characterization of the maximal non quasi-linear utility domain, which we call the largest parallel domain. We extend Roberts theorem to parallel domains, and use the generalized theorem to prove two impossibility results. First, any reasonable mechanism must be dictatorial when the utility domain is quasi-linear together with any single non-parallel type. Second, for richer utility domains that still differ very slightly from quasi-linearity, every strategy-proof, onto and deterministic mechanism must be a dictatorship.
We analyse and compare the complexity of several algorithms for computing modular polynomials. We show that an algorithm relying on floating point evaluation of modular functions and on interpolation, which has received little attention in the literature, has a complexity that is essentially (up to logarithmic factors) linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomials $Phi_ell$ of prime level $ell$ in time O (ell^3 log^4 ell log log ell). Besides treating modular polynomials for $Gamma^0 (ell)$, which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schlafli polynomials and their generalisations. Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around 10000 in less than two weeks on ten processors.
We address the question of whether or not assembly bias arises in the absence of highly non-linear effects such as tidal stripping of halos near larger mass concentrations. Therefore, we use a simplified dynamical scheme where these effects are not modeled. We choose the punctuated Zeldovich (PZ) approximation, which prevents orbit mixing by coalescing particles coming within a critical distance of each other. A numerical implementation of this approximation is fast, allowing us to run a large number of simulations to study assembly bias. We measure an assembly bias from 60 PZ simulations, each with 512^3 cold particles in a 128h^-1 Mpc cubic box. The assembly bias estimated from the correlation functions at separations < 5h^-1 Mpc for objects (halos) at z=0 is comparable to that obtained in full N-body simulations. For masses 4x10^11 h^-1 Mo the oldest 10% haloes are 3-5 times more correlated than the youngest 10%. The bias weakens with increasing mass, also in agreement with full N-body simulations. We find that that halo ages are correlated with the dimensionality of the surrounding linear structures as measured by the parameter (lambda_1+lambda_2+lambda_3)/ (lambda_1^2+lambda_2^2+lambda_3^2)^{1/2} where lambda_i are proportional to the eigenvalues of the velocity deformation tensor. Our results suggest that assembly bias may already be encoded in the early stages of the evolution.
For a class of divergence type quasi-linear degenerate parabolic equations with a Radon measure on the right hand side we derive pointwise estimates for solutions via nonlinear Wolff potentials.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
