اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAre Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization
433
0
0.0
(
0
)
نشر من قبل
Yannai A. Gonczarowski
تاريخ النشر
2018
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The literature on mechanism design from samples, which has flourished in recent years at the interface of economics and computer science, offers a bridge between the classic computer-science approach of worst-case analysis (corresponding to no samples) and the classic economic approach of average-case analysis for a given Bayesian prior (conceptually corresponding to the number of samples tending to infinity). Nonetheless, the two directions studied so far are two extreme and almost diametrically opposed directions: that of asymptotic results where the number of samples grows large, and that where only a single sample is available. In this paper, we take a first step toward understanding the middle ground that bridges these two approaches: that of a fixed number of samples greater than one. In a variety of contexts, we ask what is possibly the most fundamental question in this direction: are two samples really better than one sample?. We present a few surprising negative results, and complement them with our main result: showing that the worst-case, over all regular distributions, expected-revenue guarantee of the Empirical Revenue Maximization algorithm given two samples is greater than that of this algorithm given one sample. The proof is technically challenging, and provides the first result that shows that some deterministic mechanism constructed using two samples can guarantee more than one half of the optimal revenue.
قيم البحث
اقرأ أيضاً
We present a polynomial-time algorithm that, given samples from the unknown valuation distribution of each bidder, learns an auction that approximately maximizes the auctioneers revenue in a variety of single-parameter auction environments including
matroid environments, position environments, and the public project environment. The valuation distributions may be arbitrary bounded distributions (in particular, they may be irregular, and may differ for the various bidders), thus resolving a problem left open by previous papers. The analysis uses basic tools, is performed in its entirety in value-space, and simplifies the analysis of previously known results for special cases. Furthermore, the analysis extends to certain single-parameter auction environments where precise revenue maximization is known to be intractable, such as knapsack environments.
The importance of a strict quarantine has been widely debated during the COVID-19 epidemic even from the purely epidemiological point of view. One argument against strict lockdown measures is that once the strict quarantine is lifted, the epidemic co
mes back, and so the cumulative number of infected individuals during the entire epidemic will stay the same. We consider an SIR model on a network and follow the disease dynamics, modeling the phases of quarantine by changing the node degree distribution. We show that the system reaches different steady states based on the history: the outcome of the epidemic is path-dependent despite the same final node degree distribution. The results indicate that two-phase route to the final node degree distribution (a strict phase followed by a soft phase) are always better than one phase (the same soft one) unless all the individuals have the same number of connections at the end (the same degree); in the latter case, the overall number of infected is indeed history-independent. The modeling also suggests that the optimal procedure of lifting the quarantine consists of releasing nodes in the order of their degree - highest first.
Fully occupied or unoccupied bands in a solid are often considered inert and irrelevant to a materials low-energy properties. But the discovery of enhanced superconductivity in heavily electron-doped FeSe-derived superconductors poses questions about
the possible role of incipient bands (those laying close to but not crossing the Fermi level) in pairing. To answer this question, researchers have studied pairing correlations in the bilayer Hubbard model, which has an incipient band for large interlayer hopping $t_perp$, using many-body perturbation theory and variational methods. They have generally found that superconductivity is enhanced as one of the bands approaches the Liftshiz transition and even when it becomes incipient. Here, we address this question using the nonperturbative quantum Monte Carlo (QMC) dynamical cluster approximation (DCA) to study the bilayer Hubbard models pairing correlations. We find that the model has robust $s_pm$ pairing correlations in the large $t_perp$ limit, which can become stronger as one band is made incipient. While this behavior is linked to changes in the effective interaction, we further find that it is counteracted by a suppression of the intrinsic pair-field susceptibility and does not translate to an increased $T_c$. Our results demonstrate that the highest achievable transition temperatures in the bilayer Hubbard model occur when the system has two bands crossing the Fermi level.
Most work in mechanism design assumes that buyers are risk neutral; some considers risk aversion arising due to a non-linear utility for money. Yet behavioral studies have established that real agents exhibit risk attitudes which cannot be captured b
y any expected utility model. We initiate the study of revenue-optimal mechanisms under buyer behavioral models beyond expected utility theory. We adopt a model from prospect theory which arose to explain these discrepancies and incorporates agents under-weighting uncertain outcomes. In our model, an event occurring with probability $x < 1$ is worth strictly less to the agent than $x$ times the value of the event when it occurs with certainty. In contrast to the risk-neutral setting, the optimal mechanism may be randomized and appears challenging to find, even for a single buyer and a single item for sale. Nevertheless, we give a characterization of the optimal mechanism which enables positive approximation results. In particular, we show that under a reasonable bounded-risk-aversion assumption, posted pricing obtains a constant approximation. Notably, this result is risk-robust in that it does not depend on the details of the buyers risk attitude. Finally, we examine a dynamic setting in which the buyer is uncertain about his future value. In contrast to positive results for a risk-neutral buyer, we show that the buyers risk aversion may prevent the seller from approximating the optimal revenue in a risk-robust manner.
We study mechanisms for selling a single item when buyers have private values for their outside options, which they forego by participating in the mechanism. This substantially changes the revenue maximization problem. For example, the seller can str
ictly benefit from selling lotteries already in the single-buyer setting. We bound the menu size and the sample complexity for the optimal single-buyer mechanism. We then show that posting a single price is in fact optimal under the assumption that either (1) the outside option value is independent of the item value, and the item value distribution has decreasing marginal revenue or monotone hazard rate; or (2) the outside option value is a concave function of the item value. Moreover, when there are multiple buyers, we show that sequential posted pricing guarantees a large fraction of the optimal revenue under similar conditions.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
