Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade
233
0
0.0
(
0
)
Added by
Yannai A. Gonczarowski
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The seminal impossibility result of Myerson and Satterthwaite (1983) states that for bilateral trade, there is no mechanism that is individually rational (IR), incentive compatible (IC), weakly budget balanced, and efficient. This has led follow-up work on two-sided trade settings to weaken the efficiency requirement and consider approximately efficient simple mechanisms, while still demanding the other properties. The current state-of-the-art of such mechanisms for two-sided markets can be categorized as giving one (but not both) of the following two types of approximation guarantees on the gains from trade: a constant ex-ante guarantee, measured with respect to the second-best efficiency benchmark, or an asymptotically optimal ex-post guarantee, measured with respect to the first-best efficiency benchmark. Here the second-best efficiency benchmark refers to the highest gains from trade attainable by any IR, IC and weakly budget balanced mechanism, while the first-best efficiency benchmark refers to the maximum gains from trade (attainable by the VCG mechanism, which is not weakly budget balanced). In this paper, we construct simple mechanisms for double-auction and matching markets that simultaneously achieve both types of guarantees: these are ex-post IR, Bayesian IC, and ex-post weakly budget balanced mechanisms that 1) ex-ante guarantee a constant fraction of the gains from trade of the second-best, and 2) ex-post guarantee a realization-dependent fraction of the gains from trade of the first-best, such that this realization-dependent fraction converges to 1 (full efficiency) as the market grows large.
rate research
Read More
We consider the problem of fair allocation of indivisible items among $n$ agents with additive valuations, when agents have equal entitlements to the goods, and there are no transfers. Best-of-Both-Worlds (BoBW) fairness mechanisms aim to give all agents both an ex-ante guarantee (such as getting the proportional share in expectation) and an ex-post guarantee. Prior BoBW results have focused on ex-post guarantees that are based on the up to one item paradigm, such as envy-free up to one item (EF1). In this work we attempt to give every agent a high value ex-post, and specifically, a constant fraction of his maximin share (MMS). The up to one item paradigm fails to give such a guarantee, and it is not difficult to present examples in which previous BoBW mechanisms give agents only a $frac{1}{n}$ fraction of their MMS. Our main result is a deterministic polynomial time algorithm that computes a distribution over allocations that is ex-ante proportional, and ex-post, every allocation gives every agent at least his proportional share up to one item, and more importantly, at least half of his MMS. Moreover, this last ex-post guarantee holds even with respect to a more demanding notion of a share, introduced in this paper, that we refer to as the truncated proportional share (TPS). Our guarantees are nearly best possible, in the sense that one cannot guarantee agents more than their proportional share ex-ante, and one cannot guarantee agents more than a $frac{n}{2n-1}$ fraction of their TPS ex-post.
We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through $T$ episodes, with the goal of achieving $widetilde{mathcal{O}}(sqrt{T})$ regret when the losses are adversarial and simultaneously $mathcal{O}(text{polylog}(T))$ regret when the losses are (almost) stochastic. Recent work by [Jin and Luo, 2020] achieves this goal when the fixed transition is known, and leaves the case of unknown transition as a major open question. In this work, we resolve this open problem by using the same Follow-the-Regularized-Leader ($text{FTRL}$) framework together with a set of new techniques. Specifically, we first propose a loss-shifting trick in the $text{FTRL}$ analysis, which greatly simplifies the approach of [Jin and Luo, 2020] and already improves their results for the known transition case. Then, we extend this idea to the unknown transition case and develop a novel analysis which upper bounds the transition estimation error by (a fraction of) the regret itself in the stochastic setting, a key property to ensure $mathcal{O}(text{polylog}(T))$ regret.
The past year has witnessed rapid advances in sequence-to-sequence (seq2seq) modeling for Machine Translation (MT). The classic RNN-based approaches to MT were first out-performed by the convolutional seq2seq model, which was then out-performed by the more recent Transformer model. Each of these new approaches consists of a fundamental architecture accompanied by a set of modeling and training techniques that are in principle applicable to other seq2seq architectures. In this paper, we tease apart the new architectures and their accompanying techniques in two ways. First, we identify several key modeling and training techniques, and apply them to the RNN architecture, yielding a new RNMT+ model that outperforms all of the three fundamental architectures on the benchmark WMT14 English to French and English to German tasks. Second, we analyze the properties of each fundamental seq2seq architecture and devise new hybrid architectures intended to combine their strengths. Our hybrid models obtain further improvements, outperforming the RNMT+ model on both benchmark datasets.
Interpretability techniques aim to provide the rationale behind a models decision, typically by explaining either an individual prediction (local explanation, e.g. `why is this patient diagnosed with this condition) or a class of predictions (global explanation, e.g. `why are patients diagnosed with this condition in general). While there are many methods focused on either one, few frameworks can provide both local and global explanations in a consistent manner. In this work, we combine two powerful existing techniques, one local (Integrated Gradients, IG) and one global (Testing with Concept Activation Vectors), to provide local, and global concept-based explanations. We first validate our idea using two synthetic datasets with a known ground truth, and further demonstrate with a benchmark natural image dataset. We test our method with various concepts, target classes, model architectures and IG baselines. We show that our method improves global explanations over TCAV when compared to ground truth, and provides useful insights. We hope our work provides a step towards building bridges between many existing local and global methods to get the best of both worlds.
Supermassive black holes at the centres of galaxies can cycle through periods of activity and quiescence. Characterising the duty cycle of active galactic nuclei is crucial for understanding the impact of the energy they release on the host galaxy. For radio AGN, this can be done by identifying dying (remnant) and restarted radio galaxies from their radio spectral properties. Using the combination of images at 1400 MHz produced by Apertif, the new phased-array feed receiver installed on the Westerbork Synthesis Radio Telescope, and images at 150 MHz provided by LOFAR, we have derived resolved spectral index images (at a resolution of ~15 arcsec) for all the sources within ~6 deg^2 area of the Lockman Hole region. We were able to select 15 extended radio sources with emission (partly or entirely) characterised by extremely steep spectral indices (steeper than 1.2). These objects represent radio sources in the remnant or the restarted phases of their life cycle. Our findings suggest this cycle to be relatively fast. They also show a variety of properties relevant for modelling the evolution of radio galaxies. For example, the restarted activity can occur while the remnant structure from a previous phase of activity is still visible. This provides constraints on the duration of the off (dying) phase. In extended remnants with ultra-steep spectra at low frequencies, the activity likely stopped a few hundred megayears ago, and they correspond to the older tail of the age distribution of radio galaxies, in agreement with simulations of radio source evolution. We find remnant radio sources with a variety of structures (from double-lobed to amorphous), suggesting different types of progenitors. The present work sets the stage for exploiting low-frequency spectral index studies of extended sources by taking advantage of the large areas common to the LOFAR and the Apertif surveys.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
