@inproceedings{10748, abstract = {The study of fluxoid states and fluxoid dynamics in mesoscopic iron-based superconducting rings is valuable for characterizing the basic properties of the superconductor, and may also provide important insight into the superconducting paring symmetry. We report the fabrications of micron-sized rings and disks from thin films of Fe(Se, Te) grown by molecular beam epitaxy. In order to study fluxoid states in rings we developed a custom-tailored version of magnetic force microscopy (MFM). This technique has a number of qualitative advantages for working with mesoscopic superconducting samples in comparison to the conventional MFM and other imaging techniques. We observed metastable fluxoid states in rings of different sizes. Thermally activated fluxoid dynamics of these states was studied and modeled. In addition, we found different regimes of interaction between Fe(Se, Te) ring and MFM tip which are explained. Possibilities of the existence of exotic vortex states and proposals for experiments to test the symmetry of the superconducting order parameter in iron based superconductors are analyzed.}, author = {Polshyn, Hryhoriy and Zhang, Can and Naibert, Tyler and Eckstein, James and Budakian, Raffi}, booktitle = {APS March Meeting 2015}, issn = {0003-0503}, location = {San Antonio, TX, United States}, number = {1}, publisher = {American Physical Society}, title = {{Study of Fe (Se, Te) micron-sized rings by magnetic force microscopy}}, volume = {60}, year = {2015}, } @article{10794, abstract = {Mathematical models are of fundamental importance in the understanding of complex population dynamics. For instance, they can be used to predict the population evolution starting from different initial conditions or to test how a system responds to external perturbations. For this analysis to be meaningful in real applications, however, it is of paramount importance to choose an appropriate model structure and to infer the model parameters from measured data. While many parameter inference methods are available for models based on deterministic ordinary differential equations, the same does not hold for more detailed individual-based models. Here we consider, in particular, stochastic models in which the time evolution of the species abundances is described by a continuous-time Markov chain. These models are governed by a master equation that is typically difficult to solve. Consequently, traditional inference methods that rely on iterative evaluation of parameter likelihoods are computationally intractable. The aim of this paper is to present recent advances in parameter inference for continuous-time Markov chain models, based on a moment closure approximation of the parameter likelihood, and to investigate how these results can help in understanding, and ultimately controlling, complex systems in ecology. Specifically, we illustrate through an agricultural pest case study how parameters of a stochastic individual-based model can be identified from measured data and how the resulting model can be used to solve an optimal control problem in a stochastic setting. In particular, we show how the matter of determining the optimal combination of two different pest control methods can be formulated as a chance constrained optimization problem where the control action is modeled as a state reset, leading to a hybrid system formulation.}, author = {Parise, Francesca and Lygeros, John and Ruess, Jakob}, issn = {2296-665X}, journal = {Frontiers in Environmental Science}, keywords = {General Environmental Science}, publisher = {Frontiers}, title = {{Bayesian inference for stochastic individual-based models of ecological systems: a pest control simulation study}}, doi = {10.3389/fenvs.2015.00042}, volume = {3}, year = {2015}, } @inproceedings{10796, abstract = {We consider concurrent mean-payoff games, a very well-studied class of two-player (player 1 vs player 2) zero-sum games on finite-state graphs where every transition is assigned a reward between 0 and 1, and the payoff function is the long-run average of the rewards. The value is the maximal expected payoff that player 1 can guarantee against all strategies of player 2. We consider the computation of the set of states with value 1 under finite-memory strategies for player 1, and our main results for the problem are as follows: (1) we present a polynomial-time algorithm; (2) we show that whenever there is a finite-memory strategy, there is a stationary strategy that does not need memory at all; and (3) we present an optimal bound (which is double exponential) on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy).}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus}, booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {978-161197374-7}, location = {San Diego, CA, United States}, number = {1}, pages = {1018--1029}, publisher = {SIAM}, title = {{The value 1 problem under finite-memory strategies for concurrent mean-payoff games}}, doi = {10.1137/1.9781611973730.69}, volume = {2015}, year = {2015}, } @article{1106, abstract = {Circumferential skin creases Kunze type (CSC-KT) is a specific congenital entity with an unknown genetic cause. The disease phenotype comprises characteristic circumferential skin creases accompanied by intellectual disability, a cleft palate, short stature, and dysmorphic features. Here, we report that mutations in either MAPRE2 or TUBB underlie the genetic origin of this syndrome. MAPRE2 encodes a member of the microtubule end-binding family of proteins that bind to the guanosine triphosphate cap at growing microtubule plus ends, and TUBB encodes a β-tubulin isotype that is expressed abundantly in the developing brain. Functional analyses of the TUBB mutants show multiple defects in the chaperone-dependent tubulin heterodimer folding and assembly pathway that leads to a compromised yield of native heterodimers. The TUBB mutations also have an impact on microtubule dynamics. For MAPRE2, we show that the mutations result in enhanced MAPRE2 binding to microtubules, implying an increased dwell time at microtubule plus ends. Further, in vivo analysis of MAPRE2 mutations in a zebrafish model of craniofacial development shows that the variants most likely perturb the patterning of branchial arches, either through excessive activity (under a recessive paradigm) or through haploinsufficiency (dominant de novo paradigm). Taken together, our data add CSC-KT to the growing list of tubulinopathies and highlight how multiple inheritance paradigms can affect dosage-sensitive biological systems so as to result in the same clinical defect.}, author = {Isrie, Mala and Breuss, Martin and Tian, Guoling and Hansen, Andi H and Cristofoli, Francesca and Morandell, Jasmin and Kupchinsky, Zachari A and Sifrim, Alejandro and Rodriguez Rodriguez, Celia and Dapena, Elena P and Doonanco, Kurston and Leonard, Norma and Tinsa, Faten and Moortgat, Stéphanie and Ulucan, Hakan and Koparir, Erkan and Karaca, Ender and Katsanis, Nicholas and Marton, Valeria and Vermeesch, Joris R and Davis, Erica E and Cowan, Nicholas J and Keays, David and Van Esch, Hilde}, journal = {The American Journal of Human Genetics}, number = {6}, pages = {790 -- 800}, publisher = {Cell Press}, title = {{Mutations in either TUBB or MAPRE2 cause circumferential skin creases Kunze type}}, doi = {10.1016/j.ajhg.2015.10.014}, volume = {97}, year = {2015}, } @article{11079, abstract = {Aging is a major risk factor for many human diseases, and in vitro generation of human neurons is an attractive approach for modeling aging-related brain disorders. However, modeling aging in differentiated human neurons has proved challenging. We generated neurons from human donors across a broad range of ages, either by iPSC-based reprogramming and differentiation or by direct conversion into induced neurons (iNs). While iPSCs and derived neurons did not retain aging-associated gene signatures, iNs displayed age-specific transcriptional profiles and revealed age-associated decreases in the nuclear transport receptor RanBP17. We detected an age-dependent loss of nucleocytoplasmic compartmentalization (NCC) in donor fibroblasts and corresponding iNs and found that reduced RanBP17 impaired NCC in young cells, while iPSC rejuvenation restored NCC in aged cells. These results show that iNs retain important aging-related signatures, thus allowing modeling of the aging process in vitro, and they identify impaired NCC as an important factor in human aging.}, author = {Mertens, Jerome and Paquola, Apuã C.M. and Ku, Manching and Hatch, Emily and Böhnke, Lena and Ladjevardi, Shauheen and McGrath, Sean and Campbell, Benjamin and Lee, Hyungjun and Herdy, Joseph R. and Gonçalves, J. Tiago and Toda, Tomohisa and Kim, Yongsung and Winkler, Jürgen and Yao, Jun and HETZER, Martin W and Gage, Fred H.}, issn = {1934-5909}, journal = {Cell Stem Cell}, keywords = {Cell Biology, Genetics, Molecular Medicine}, number = {6}, pages = {705--718}, publisher = {Elsevier}, title = {{Directly reprogrammed human neurons retain aging-associated transcriptomic signatures and reveal age-related nucleocytoplasmic defects}}, doi = {10.1016/j.stem.2015.09.001}, volume = {17}, year = {2015}, } @article{11077, abstract = {Nucleoporins (Nups) are a family of proteins best known as the constituent building blocks of nuclear pore complexes (NPCs), membrane-embedded channels that mediate nuclear transport across the nuclear envelope. Recent evidence suggests that several Nups have additional roles in controlling the activation and silencing of developmental genes; however, the mechanistic details of these functions remain poorly understood. Here, we show that depletion of Nup153 in mouse embryonic stem cells (mESCs) causes the derepression of developmental genes and induction of early differentiation. This loss of stem cell identity is not associated with defects in the nuclear import of key pluripotency factors. Rather, Nup153 binds around the transcriptional start site (TSS) of developmental genes and mediates the recruitment of the polycomb-repressive complex 1 (PRC1) to a subset of its target loci. Our results demonstrate a chromatin-associated role of Nup153 in maintaining stem cell pluripotency by functioning in mammalian epigenetic gene silencing.}, author = {Jacinto, Filipe V. and Benner, Chris and HETZER, Martin W}, issn = {1549-5477}, journal = {Genes & Development}, keywords = {Developmental Biology, Genetics}, number = {12}, pages = {1224--1238}, publisher = {Cold Spring Harbor Laboratory}, title = {{The nucleoporin Nup153 regulates embryonic stem cell pluripotency through gene silencing}}, doi = {10.1101/gad.260919.115}, volume = {29}, year = {2015}, } @article{11078, abstract = {Aging is associated with the decline of protein, cell, and organ function. Here, we use an integrated approach to characterize gene expression, bulk translation, and cell biology in the brains and livers of young and old rats. We identify 468 differences in protein abundance between young and old animals. The majority are a consequence of altered translation output, that is, the combined effect of changes in transcript abundance and translation efficiency. In addition, we identify 130 proteins whose overall abundance remains unchanged but whose sub-cellular localization, phosphorylation state, or splice-form varies. While some protein-level differences appear to be a generic property of the rats’ chronological age, the majority are specific to one organ. These may be a consequence of the organ’s physiology or the chronological age of the cells within the tissue. Taken together, our study provides an initial view of the proteome at the molecular, sub-cellular, and organ level in young and old rats.}, author = {Ori, Alessandro and Toyama, Brandon H. and Harris, Michael S. and Bock, Thomas and Iskar, Murat and Bork, Peer and Ingolia, Nicholas T. and HETZER, Martin W and Beck, Martin}, issn = {2405-4712}, journal = {Cell Systems}, keywords = {Cell Biology, Histology, Pathology and Forensic Medicine}, number = {3}, pages = {P224--237}, publisher = {Elsevier}, title = {{Integrated transcriptome and proteome analyses reveal organ-specific proteome deterioration in old rats}}, doi = {10.1016/j.cels.2015.08.012}, volume = {1}, year = {2015}, } @article{11075, abstract = {Previously, we identified the nucleoporin gp210/Nup210 as a critical regulator of muscle and neuronal differentiation, but how this nucleoporin exerts its function and whether it modulates nuclear pore complex (NPC) activity remain unknown. Here, we show that gp210/Nup210 mediates muscle cell differentiation in vitro via its conserved N-terminal domain that extends into the perinuclear space. Removal of the C-terminal domain, which partially mislocalizes gp210/Nup210 away from NPCs, efficiently rescues the differentiation defect caused by the knockdown of endogenous gp210/Nup210. Unexpectedly, a gp210/Nup210 mutant lacking the NPC-targeting transmembrane and C-terminal domains is sufficient for C2C12 myoblast differentiation. We demonstrate that the endoplasmic reticulum (ER) stress-specific caspase cascade is exacerbated during Nup210 depletion and that blocking ER stress-mediated apoptosis rescues differentiation of Nup210-deficient cells. Our results suggest that the role of gp210/Nup210 in cell differentiation is mediated by its large luminal domain, which can act independently of NPC association and appears to play a pivotal role in the maintenance of nuclear envelope/ER homeostasis.}, author = {Gomez-Cavazos, J. Sebastian and HETZER, Martin W}, issn = {1540-8140}, journal = {Journal of Cell Biology}, keywords = {Cell Biology}, number = {6}, pages = {671--681}, publisher = {Rockefeller University Press}, title = {{The nucleoporin gp210/Nup210 controls muscle differentiation by regulating nuclear envelope/ER homeostasis}}, doi = {10.1083/jcb.201410047}, volume = {208}, year = {2015}, } @article{11076, abstract = {Nuclear pore complexes (NPCs) are composed of several copies of ∼30 different proteins called nucleoporins (Nups). NPCs penetrate the nuclear envelope (NE) and regulate the nucleocytoplasmic trafficking of macromolecules. Beyond this vital role, NPC components influence genome functions in a transport-independent manner. Nups play an evolutionarily conserved role in gene expression regulation that, in metazoans, extends into the nuclear interior. Additionally, in proliferative cells, Nups play a crucial role in genome integrity maintenance and mitotic progression. Here we discuss genome-related functions of Nups and their impact on essential DNA metabolism processes such as transcription, chromosome duplication, and segregation.}, author = {Ibarra, Arkaitz and HETZER, Martin W}, issn = {1549-5477}, journal = {Genes & Development}, keywords = {Developmental Biology, Genetics}, number = {4}, pages = {337--349}, publisher = {Cold Spring Harbor Laboratory}, title = {{Nuclear pore proteins and the control of genome functions}}, doi = {10.1101/gad.256495.114}, volume = {29}, year = {2015}, } @article{11073, abstract = {Human cancer cells bear complex chromosome rearrangements that can be potential drivers of cancer development. However, the molecular mechanisms underlying these rearrangements have been unclear. Zhang et al. use a new technique combining live-cell imaging and single-cell sequencing to demonstrate that chromosomes mis-segregated to micronuclei frequently undergo chromothripsis-like rearrangements in the subsequent cell cycle.}, author = {Hatch, Emily M. and HETZER, Martin W}, issn = {0092-8674}, journal = {Cell}, keywords = {General Biochemistry, Genetics and Molecular Biology}, number = {7}, pages = {1502--1504}, publisher = {Elsevier}, title = {{Linking micronuclei to chromosome fragmentation}}, doi = {10.1016/j.cell.2015.06.005}, volume = {161}, year = {2015}, } @article{11074, author = {Hatch, Emily M. and HETZER, Martin W}, issn = {0960-9822}, journal = {Current Biology}, keywords = {General Agricultural and Biological Sciences, General Biochemistry, Genetics and Molecular Biology}, number = {10}, pages = {PR397--R399}, publisher = {Elsevier}, title = {{Chromothripsis}}, doi = {10.1016/j.cub.2015.02.033}, volume = {25}, year = {2015}, } @article{11519, abstract = {Faint Lyα emitters become increasingly rarer toward the reionization epoch (z ∼ 6–7). However, observations from a very large (∼5 deg2) Lyα narrow-band survey at z = 6.6 show that this is not the case for the most luminous emitters, capable of ionizing their own local bubbles. Here we present follow-up observations of the two most luminous Lyα candidates in the COSMOS field: “MASOSA” and “CR7.” We used X-SHOOTER, SINFONI, and FORS2 on the Very Large Telescope, and DEIMOS on Keck, to confirm both candidates beyond any doubt. We find redshifts of z = 6.541 and z = 6.604 for “MASOSA” and “CR7,” respectively. MASOSA has a strong detection in Lyα with a line width of 386 ± 30 km s−1 (FWHM) and with very high EW0 (>200 Å), but undetected in the continuum, implying very low stellar mass and a likely young, metal-poor stellar population. “CR7,” with an observed Lyα luminosity of 1043.92±0.05 erg s−1 is the most luminous Lyα emitter ever found at z > 6 and is spatially extended (∼16 kpc). “CR7” reveals a narrow Lyα line with 266 ± 15 km s−1 FWHM, being detected in the near-infrared (NIR) (rest-frame UV; β = −2.3 ± 0.1) and in IRAC/Spitzer. We detect a narrow He II 1640 Å emission line (6σ, FWHM = 130 ± 30 km s−1 ) in CR7 which can explain the clear excess seen in the J-band photometry (EW0 ∼ 80 Å). We find no other emission lines from the UV to the NIR in our X-SHOOTER spectra (He II/O III] 1663 Å > 3 and He II/C III] 1908 Å > 2.5). We conclude that CR7 is best explained by a combination of a PopIII-like population, which dominates the rest-frame UV and the nebular emission, and a more normal stellar population, which presumably dominates the mass. Hubble Space Telescope/WFC3 observations show that the light is indeed spatially separated between a very blue component, coincident with Lyα and He II emission, and two red components (∼5 kpc away), which dominate the mass. Our findings are consistent with theoretical predictions of a PopIII wave, with PopIII star formation migrating away from the original sites of star formation.}, author = {Sobral, David and Matthee, Jorryt J and Darvish, Behnam and Schaerer, Daniel and Mobasher, Bahram and Röttgering, Huub and Santos, Sérgio and Hemmati, Shoubaneh}, issn = {1538-4357}, journal = {The Astrophysical Journal}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, dark ages, reionization, first stars – early universe – galaxies: evolution}, number = {2}, pages = {139}, publisher = {IOP Publishing}, title = {{Evidence for PopIII-like stellar populations in the most luminous Lyα emitters at the epoch of reionisation: Spectroscopic confirmation}}, doi = {10.1088/0004-637X/808/2/139}, volume = {808}, year = {2015}, } @article{11580, abstract = {We present results from the largest contiguous narrow-band survey in the near-infrared. We have used the wide-field infrared camera/Canada–France–Hawaii Telescope and the lowOH2 filter (1.187 ± 0.005 μm) to survey ≈10 deg2 of contiguous extragalactic sky in the SA22 field. A total of ∼6000 candidate emission-line galaxies are found. We use deep ugrizJK data to obtain robust photometric redshifts. We combine our data with the High-redshift(Z) Emission Line Survey (HiZELS), explore spectroscopic surveys (VVDS, VIPERS) and obtain our own spectroscopic follow-up with KMOS, FMOS and MOSFIRE to derive large samples of high-redshift emission-line selected galaxies: 3471 Hα emitters at z = 0.8, 1343 [O III] + Hβ emitters at z = 1.4 and 572 [O II] emitters at z = 2.2. We probe comoving volumes of >106 Mpc3 and find significant overdensities, including an 8.5σ (spectroscopically confirmed) overdensity of Hα emitters at z = 0.81. We derive Hα, [O III] + Hβ and [O II] luminosity functions at z = 0.8, 1.4, 2.2, respectively, and present implications for future surveys such as Euclid. Our uniquely large volumes/areas allow us to subdivide the samples in thousands of randomized combinations of areas and provide a robust empirical measurement of sample/cosmic variance. We show that surveys for star-forming/emission-line galaxies at a depth similar to ours can only overcome cosmic-variance (errors <10 per cent) if they are based on volumes >5 × 105 Mpc3; errors on L* and ϕ* due to sample (cosmic) variance on surveys probing ∼104 and ∼105 Mpc3 are typically very high: ∼300 and ∼40–60 per cent, respectively.}, author = {Sobral, D. and Matthee, Jorryt J and Best, P. N. and Smail, I. and Khostovan, A. A. and Milvang-Jensen, B. and Kim, J.-W. and Stott, J. and Calhau, J. and Nayyeri, H. and Mobasher, B.}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: formation, galaxies: luminosity function, mass function, cosmology: observations, early Universe, large-scale structure of Universe}, number = {3}, pages = {2303--2323}, publisher = {Oxford University Press}, title = {{CF-HiZELS, an ∼10 deg2 emission-line survey with spectroscopic follow-up: Hα, [O III] + Hβ and [O II] luminosity functions at z = 0.8, 1.4 and 2.2 }}, doi = {10.1093/mnras/stv1076}, volume = {451}, year = {2015}, } @article{11581, abstract = {Using wide-field narrow-band surveys, we provide a new measurement of the z = 6.6 Lymanα emitter (LAE) luminosity function (LF), which constraints the bright end for the first time. We use a combination of archival narrow-band NB921 data in UDS and new NB921 measurements in SA22 and COSMOS/UltraVISTA, all observed with the Subaru telescope, with a total area of ∼5 deg2. We exclude lower redshift interlopers by using broad-band optical and near-infrared photometry and also exclude three supernovae with data split over multiple epochs. Combining the UDS and COSMOS samples, we find no evolution of the bright end of the Lyα LF between z = 5.7 and 6.6, which is supported by spectroscopic follow-up, and conclude that sources with Himiko-like luminosity are not as rare as previously thought, with number densities of ∼1.5 × 10−5 Mpc−3. Combined with our wide-field SA22 measurements, our results indicate a non-Schechter-like bright end of the LF at z = 6.6 and a different evolution of observed faint and bright LAEs, overcoming cosmic variance. This differential evolution is also seen in the spectroscopic follow-up of UV-selected galaxies and is now also confirmed for LAEs, and we argue that it may be an effect of reionization. Using a toy model, we show that such differential evolution of the LF is expected, since brighter sources are able to ionize their surroundings earlier, such that Lyα photons are able to escape. Our targets are excellent candidates for detailed follow-up studies and provide the possibility to give a unique view on the earliest stages in the formation of galaxies and reionization process.}, author = {Matthee, Jorryt J and Sobral, David and Santos, Sérgio and Röttgering, Huub and Darvish, Behnam and Mobasher, Bahram}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics}, number = {1}, pages = {400--417}, publisher = {Oxford University Press}, title = {{Identification of the brightest Lyα emitters at z = 6.6: implications for the evolution of the luminosity function in the reionization era}}, doi = {10.1093/mnras/stv947}, volume = {451}, year = {2015}, } @article{11579, abstract = {CR7 is the brightest z = 6.6 Ly α emitter (LAE) known to date, and spectroscopic follow-up by Sobral et al. suggests that CR7 might host Population (Pop) III stars. We examine this interpretation using cosmological hydrodynamical simulations. Several simulated galaxies show the same ‘Pop III wave’ pattern observed in CR7. However, to reproduce the extreme CR7 Ly α/He II1640 line luminosities (⁠Lα/HeII⁠) a top-heavy initial mass function and a massive ( ≳ 107 M⊙) Pop III burst with age ≲ 2 Myr are required. Assuming that the observed properties of Ly α and He II emission are typical for Pop III, we predict that in the COSMOS/UDS/SA22 fields, 14 out of the 30 LAEs at z = 6.6 with Lα > 1043.3 erg s−1 should also host Pop III stars producing an observable LHeII≳1042.7ergs−1⁠. As an alternate explanation, we explore the possibility that CR7 is instead powered by accretion on to a direct collapse black hole. Our model predicts Lα, LHeII⁠, and X-ray luminosities that are in agreement with the observations. In any case, the observed properties of CR7 indicate that this galaxy is most likely powered by sources formed from pristine gas. We propose that further X-ray observations can distinguish between the two above scenarios.}, author = {Pallottini, A. and Ferrara, A. and Pacucci, F. and Gallerani, S. and Salvadori, S. and Schneider, R. and Schaerer, D. and Sobral, D. and Matthee, Jorryt J}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, black hole physics, stars: Population III, galaxies: high-redshift}, number = {3}, pages = {2465--2470}, publisher = {Oxford University Press}, title = {{The brightest Lyα emitter: Pop III or black hole?}}, doi = {10.1093/mnras/stv1795}, volume = {453}, year = {2015}, } @article{11668, abstract = {We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded. We show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto-optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto-optimal, and deterministic mechanisms for bidders with diminishing marginal valuations.}, author = {Colini-Baldeschi, Riccardo and Leonardi, Stefano and Henzinger, Monika H and Starnberger, Martin}, issn = {2167-8383}, journal = {ACM Transactions on Economics and Computation}, keywords = {Algorithms, Economics, Clinching ascending auction, auctions with budgets, Sponsored search auctions}, number = {1}, publisher = {Association for Computing Machinery}, title = {{On multiple keyword sponsored search auctions with budgets}}, doi = {10.1145/2818357}, volume = {4}, year = {2015}, } @article{11669, abstract = {We study individual rational, Pareto-optimal, and incentive compatible mechanisms for auctions with heterogeneous items and budget limits. We consider settings with multiunit demand and additive valuations. For single-dimensional valuations we prove a positive result for randomized mechanisms, and a negative result for deterministic mechanisms. While the positive result allows for private budgets, the negative result is for public budgets. For multidimensional valuations and public budgets we prove an impossibility result that applies to deterministic and randomized mechanisms. Taken together this shows the power of randomization in certain settings with heterogeneous items, but it also shows its limitations.}, author = {Dütting, Paul and Henzinger, Monika H and Starnberger, Martin}, issn = {2167-8383}, journal = {ACM Transactions on Economics and Computation}, keywords = {Algorithmic game theory, auction theory, Clinching auction, Pareto optimality, Budget limits}, number = {1}, publisher = {Association for Computing Machinery}, title = {{Auctions for heterogeneous items and budget limits}}, doi = {10.1145/2818351}, volume = {4}, year = {2015}, } @article{11670, abstract = {Auctions are widely used on the Web. Applications range from sponsored search to platforms such as eBay. In these and in many other applications the auctions in use are single-/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the limited expressiveness that they offer to the bidders. The General Auction Mechanism (GAM) of Aggarwal et al. [2009] takes a first step toward addressing the problem of limited expressiveness by computing a bidder optimal, envy-free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for piecewise linear utility functions with nonidentical slopes and multiple discontinuities. Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are nondegenerate as well as for continuous utility functions the outcome of our mechanism is a competitive equilibrium. We also show how our mechanism can be used to compute approximately bidder optimal, envy-free outcomes for a general class of continuous utility functions via piecewise linear approximation. Finally, we prove hardness results for even more expressive settings.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, issn = {2167-8383}, journal = {ACM Transactions on Economics and Computation}, keywords = {Computational Mathematics, Marketing, Economics and Econometrics, Statistics and Probability, Computer Science (miscellaneous)}, number = {1}, publisher = {Association for Computing Machinery}, title = {{An expressive mechanism for auctions on the web}}, doi = {10.1145/2716312}, volume = {4}, year = {2015}, } @inproceedings{11774, abstract = {Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on Δ. For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful 𝛼-approximation mechanism for conflict-free valuations and yields an 𝒪(𝛼Δ)-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is 𝒪((ΔloglogΔ)/logΔ). The ratios are almost optimal given existing hardness results. For adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio 𝑜(Δ) when the number of items is only logarithmic in the number of bidders.}, author = {Cheung, Yun Kuen and Henzinger, Monika H and Hoefer, Martin and Starnberger, Martin}, booktitle = {11th International Conference on Web and Internet Economics}, isbn = {9783662489949}, issn = {0302-9743}, location = {Amsterdam, Netherlands}, pages = {230–243}, publisher = {Springer Nature}, title = {{Combinatorial auctions with conflict-based externalities}}, doi = {10.1007/978-3-662-48995-6_17}, volume = {9470}, year = {2015}, } @inproceedings{11773, abstract = {Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers. In this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.}, author = {Ben-Zwi, Oren and Henzinger, Monika H and Loitzenbauer, Veronika}, booktitle = {11th International Conference on Web and Internet Economics}, isbn = {9783662489949}, issn = {0302-9743}, location = {Amsterdam, Netherlands}, pages = {104–117}, publisher = {Springer Nature}, title = {{Ad exchange: Envy-free auctions with mediators}}, doi = {10.1007/978-3-662-48995-6_8}, volume = {9470}, year = {2015}, }