Author name cluster

Ian Kash

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

AAAI Conference 2019 Conference Paper

Partial Verification as a Substitute for Money

Sofia Ceppi
Ian Kash
Rafael Frongillo

Recent work shows that we can use partial verification instead of money to implement truthful mechanisms. In this paper we develop tools to answer the following question. Given an allocation rule that can be made truthful with payments, what is the minimal verification needed to make it truthful without them? Our techniques leverage the geometric relationship between the type space and the set of possible allocations.

PDF Details

EWRL Workshop 2018 Workshop Paper

Combining No-regret and Q-learning

Ian Kash
Katja Hofmann

Most reinforcement learning algorithms do not provide guarantees in settings with multiple agents or partial observability. A notable exception is Counterfactual Regret Minimization (CFR), which provides both strong convergence guarantees and empirical results in settings like poker. We seek to understand how these guarantees could be achieved more broadly. To take a first step in this direction, we introduce a simple algorithm, local no-regret learning (LONR), which captures the spirit of CFR, but can be applied in settings without a terminal state. We prove its convergence for the basic case of MDPs and discuss research directions to extend our results to address richer settings with multiple agents, partial observability, and sampling.

PDF Details

EWRL Workshop 2018 Workshop Paper

Learning good policies from suboptimal demonstrations

Yuxiang Li
Katja Hofmann
Ian Kash

Imitating an expert policy is one way to boost reinforcement learning algorithms which, in most cases, rely on random exploration and a huge amount of data. While some major drawbacks of imitation learning, such as compound errors, have been addressed, most results make an implicit hypothesis of having a good (or desired) expert which is usually hard to get in practice. To overcome this obstacle, this paper focuses on learning good policies from suboptimal demonstration data. We systematically investigate the performance of a recent approach under varying assumptions on demonstration quality and show that it performs poorly with suboptimal demonstration data. We then demonstrate the potential to overcome this issue through a performance comparison between learner and demonstrator.

PDF Details

AAAI Conference 2017 Conference Paper

Incentivising Monitoring in Open Normative Systems

Natasha Alechina
Joseph Halpern
Ian Kash
Brian Logan

We present an approach to incentivising monitoring for norm violations in open multi-agent systems such as Wikipedia. In such systems, there is no crisp deﬁnition of a norm violation; rather, it is a matter of judgement whether an agent’s behaviour conforms to generally accepted standards of behaviour. Agents may legitimately disagree about borderline cases. Using ideas from scrip systems and peer prediction, we show how to design a mechanism that incentivises agents to monitor each other’s behaviour for norm violations. The mechanism keeps the probability of undetected violations (submissions that the majority of the community would consider not conforming to standards) low, and is robust against collusion by the monitoring agents.

PDF Details

AAAI Conference 2016 Conference Paper

Using Convolutional Neural Networks to Analyze Function Properties from Images

Yoad Lewenberg
Yoram Bachrach
Ian Kash
Peter Key

We propose a system for determining properties of mathematical functions given an image of their graph representation. We demonstrate our approach for twodimensional graphs (curves of single variable functions) and three-dimensional graphs (surfaces of two variable functions), studying the properties of convexity and symmetry. Our method uses a Convolutional Neural Network which classiﬁes functions according to these properties, without using any hand-crafted features. We propose algorithms for randomly constructing functions with convexity or symmetry properties, and use the images generated by these algorithms to train our network. Our system achieves a high accuracy on this task, even for functions where humans ﬁnd it difﬁcult to determine the function’s properties from its image.

PDF Details

AAAI Conference 2015 Conference Paper

Elicitation for Aggregation

Rafael Frongillo
Yiling Chen
Ian Kash

We study the problem of eliciting and aggregating probabilistic information from multiple agents. In order to successfully aggregate the predictions of agents, the principal needs to elicit some notion of confidence from agents, capturing how much experience or knowledge led to their predictions. To formalize this, we consider a principal who wishes to learn the distribution of a random variable. A group of Bayesian agents has each privately observed some independent samples of the random variable. The principal wishes to elicit enough information from each agent, so that her posterior is the same as if she had directly received all of the samples herself. Leveraging techniques from Bayesian statistics, we represent confidence as the number of samples an agent has observed, which is quantified by a hyperparameter from a conjugate family of prior distributions. This then allows us to show that if the principal has access to a few samples, she can achieve her aggregation goal by eliciting predictions from agents using proper scoring rules. In particular, with access to one sample, she can successfully aggregate the agents’ predictions if and only if every posterior predictive distribution corresponds to a unique value of the hyperparameter, a property which holds for many common distributions of interest. When this uniqueness property does not hold, we construct a novel and intuitive mechanism where a principal with two samples can elicit and optimally aggregate the agents’ predictions.

PDF Details

NeurIPS Conference 2015 Conference Paper

On Elicitation Complexity

Rafael Frongillo
Ian Kash

Elicitation is the study of statistics or properties which are computable via empirical risk minimization. While several recent papers have approached the general question of which properties are elicitable, we suggest that this is the wrong question---all properties are elicitable by first eliciting the entire distribution or data set, and thus the important question is how elicitable. Specifically, what is the minimum number of regression parameters needed to compute the property? Building on previous work, we introduce a new notion of elicitation complexity and lay the foundations for a calculus of elicitation. We establish several general results and techniques for proving upper and lower bounds on elicitation complexity. These results provide tight bounds for eliciting the Bayes risk of any loss, a large class of properties which includes spectral risk measures and several new properties of interest.

PDF Details

AAMAS Conference 2012 Conference Paper

Predicting Your Own Effort

David F. Bacon
Yiling Chen
Ian Kash
David Parkes
Malvika Rao
Manu Sridharan

We consider a setting in which a worker and a manager may each have information about the likely completion time of a task, and the worker also affects the completion time by choosing a level of effort. The task itself may further be composed of a set of subtasks, and the worker can also decide how many of these subtasks to split out into an explicit prediction task. In addition, a worker can learn about the likely completion time of a task as work on subtasks completes. We characterize a family of scoring rules for the worker and manager that provide three properties: information is truthfully reported, best effort is exerted by the worker in completing tasks as quickly as possible; and collusion is not possible. We also study the factors influencing when a worker will split a task into subtasks, each forming a separate prediction target.

PDF

AAAI Conference 2011 Conference Paper

Market Manipulation with Outside Incentives

Yiling Chen
Xi Gao
Rick Goldstein
Ian Kash

Much evidence has shown that prediction markets, when used in isolation, can effectively aggregate dispersed information about uncertain future events and produce remarkably accurate forecasts. However, if the market prediction will be used for decision making, a strategic participant with a vested interest in the decision outcome may want to manipulate the market prediction in order to inﬂuence the resulting decision. The presence of such incentives outside of the market would seem to damage information aggregation because of the potential distrust among market participants. While this is true under some conditions, we ﬁnd that, if the existence of such incentives is certain and common knowledge, then in many cases, there exists a separating equilibrium for the market where information is fully aggregated. This equilibrium also maximizes social welfare for convex outside payoff functions. At this equilibrium, the participant with outside incentives makes a costly move to gain the trust of other participants. When the existence of outside incentives is uncertain, however, trust cannot be established between players if the outside incentive is sufﬁciently large and we lose the separability in equilibrium.

PDF Details