We present a new algorithm for computing pure-strategy ε-Bayes-Nash equilibria (ε-BNEs) in combinatorial auctions with continuous value and action spaces. An essential innovation of our algorithm is to separate the algorithm's search phase (for finding the ε-BNE) from the verification phase (for computing the ε). Using this approach, we obtain an algorithm that is both very fast and provides theoretical guarantees on the ε it finds. Our main technical contribution is a verification method which allows us to upper bound the ε across the whole continuous value space without making assumptions about the mechanism. Using our algorithm, we can now compute ε-BNEs in multi-minded domains that are significantly more complex than what was previously possible to solve. We release our code under an open-source license to enable researchers to perform algorithmic analyses of auctions, to enable bidders to analyze different strategies, and to facilitate many other applications.

The quality of machine translation has increased remarkably over the past years, to the degree that it was found to be indistinguishable from professional human translation in a number of empirical investigations. We reassess Hassan et al.'s 2018 investigation into Chinese to English news translation, showing that the finding of human–machine parity was owed to weaknesses in the evaluation design—which is currently considered best practice in the field. We show that the professional human translations contained significantly fewer errors, and that perceived quality in human evaluation depends on the choice of raters, the availability of linguistic context, and the creation of reference translations. Our results call for revisiting current best practices to assess strong machine translation systems in general and human–machine parity in particular, for which we offer a set of recommendations based on our empirical findings.

We cast the problem of combinatorial auction design in a Bayesian framework in order to incorporate prior information into the auction process and minimize the number of rounds to convergence. We first develop a generative model of agent valuations and market prices such that clearing prices become maximum a posteriori estimates given observed agent valuations. This generative model then forms the basis of an auction process which alternates between refining estimates of agent valuations and computing candidate clearing prices. We provide an implementation of the auction using assumed density filtering to estimate valuations and expectation maximization to compute prices. An empirical evaluation over a range of valuation domains demonstrates that our Bayesian auction mechanism is highly competitive against the combinatorial clock auction in terms of rounds to convergence, even under the most favorable choices of price increment for this baseline.

A well-known problem in combinatorial auctions (CAs) is that the value space grows exponentially in the number of goods, which often puts a large burden on the bidders and on the auctioneer. In this paper, we introduce a new design paradigm for CAs based on machine learning (ML). Bidders report their values (bids) to a proxy agent by answering a small number of value queries. The proxy agent then uses an ML algorithm to generalize from those bids to the whole value space, and the efficient allocation is computed based on the generalized valuations. We introduce the concept of "probably approximate efficiency (PAE)" to measure the efficiency of the new ML-based auctions, and we formally show how the generelizability of an ML algorithm relates to the efficiency loss incurred by the corresponding ML-based auction. To instantiate our paradigm, we use support vector regression (SVR) as our ML algorithm, which enables us to keep the winner determination problem of the CA tractable. Different parameters of the SVR algorithm allow us to trade off the expressiveness, economic efficiency, and computational efficiency of the CA. Finally, we demonstrate experimentally that, even with a small number of bids, our ML-based auctions are highly efficient with high probability.

We consider three important, non-strategyproof assignment mechanisms: Probabilistic Serial and two variants of the Boston mechanism. Under each of these mechanisms, we study the agent’s manipulation problem of determining a best response, i.e., a report that maximizes the agent’s expected utility. In particular, we consider local manipulation strategies, which are simple heuristics based on local, greedy search. We make three main contributions. First, we present results from a behavioral experiment (conducted on Amazon Mechanical Turk) which demonstrate that human manipulation strategies can largely be explained by local manipulation strategies. Second, we prove that local manipulation strategies may fail to solve the manipulation problem optimally. Third, we show via large-scale simulations that despite this non-optimality, these strategies are very effective on average. Our results demonstrate that while the manipulation problem may be hard in general, even cognitively or computationally bounded (human) agents can find near-optimal solutions almost all the time via simple local search strategies.

Computing prices in core-selecting combinatorial auctions is a computationally hard problem. Auctions with many bids can only be solved using a recently proposed core constraint generation (CCG) algorithm, which may still take days on hard instances. In this paper, we present a new algorithm that significantly outperforms the current state of the art. Towards this end, we first provide an alternative definition of the set of core constraints, where each constraint is weakly stronger, and prove that together these constraints define the identical polytope to the previous definition. Using these new theoretical insights we develop two new algorithmic techniques which generate additional constraints in each iteration of the CCG algorithm by 1) exploiting separability in allocative conflicts between participants in the auction, and 2) by leveraging non-optimal solutions. We show experimentally that our new algorithm leads to significant speed-ups on a variety of large combinatorial auction problems. Our work provides new insights into the structure of core constraints and advances the state of the art in fast algorithms for computing core prices in large combinatorial auctions.

Quality assurance in crowdsourcing markets has appeared to be an acute problem over the last years. We propose a quality control method inspired by Statistical Process Control (SPC), commonly used to control output quality in production processes and characterized by relying on time-series data. Behavioral traces of users may play a key role in evaluating the performance of work done on crowdsourcing platforms. Therefore, in our experiment we explore fifteen behavioral traces for their ability to recognize the drop in work quality. Preliminary results indicate that our method has a high potential for real-time detection and signaling a drop in work quality.

In this paper we describe the architecture of the OntoGene Relation mining pipeline and some of its recent applications. With this research overview paper we intend to provide a contribution towards the recently started discussion towards standards for information extraction architectures in the biomedical domain. Our approach delivers domain entities mentioned in each input document, as well as candidate relationships, both ranked according to a confidency score computed by the system. This information is presented to the user through an advanced interface aimed at supporting the process of interactive curation.

Based on recent experiences between a laughing virtual agent and a human user at the intersection AI and humor and laughter, this paper aims to highlight some of the psychological considerations, when conducting AI and humor experiments. The systematic and standardized approach outlined in this paper will demonstrate how to reduce error variance that may be caused by confound variables such as having poor experimental controls. From the necessity of cover stories, protocols and procedures, the differences to the pros and cons of measuring subjectively and objectively and what is required so that both give valid and reliable results are offered as solutions to achieving this goal. Furthermore, the psychological individual differences that need consideration, such as the appreciation of different types of humor, mood, personality variables, for example, trait and state cheerfulness, and gelotophobia- the fear of being laughed at are discussed.

This extended abstract presents a work in progress of using terminological resources from the biomedical domain to systematically study the change of domain terminology over time. In particular we investigate term replacement. In order to study term replacement over time, semantic knowledge like conceptual granularity of a term is necessary. We analyze three popular biomedical terminology resources (UMLS, CTD, SNOMED CT) and show how information provided there can be used to extract lexically distinctive synonym sets that exclude variants. We use the entire PubMed dataset to chronologically study occurrences of extracted synonyms. Our experiments on the disease subsets of three terminologies reveal that the phenomenon of term replacement can be observed in around 60% of the extracted synonym sets.