Search

Your search keyword '"Kash, Ian"' showing total 118 results
Start Over Author "Kash, Ian"
118 results on '"Kash, Ian"'

101. Multiagent Learning in Large Anonymous Games.

Author

Kash, Ian A., Friedman, Eric J., and Halpern, Joseph Y.

Subjects
LEARNING, ALGORITHMS, NASH equilibrium, STATISTICS, BEHAVIOR
Abstract

In large systems, it is important for agents to learn to act effectively, but sophisticated multi-agent learning algorithms generally do not scale. An alternative approach is to find restricted classes of games where simple, efficient algorithms converge. It is shown that stage learning efficiently converges to Nash equilibria in large anonymous games if bestreply dynamics converge. Two features are identified that improve convergence. First, rather than making learning more difficult, more agents are actually beneficial in many settings. Second, providing agents with statistical information about the behavior of others can significantly reduce the number of observations needed. [ABSTRACT FROM AUTHOR]

Published
2011
Full Text
View/download PDF

102. Truthful Mechanisms for Agents that Value Privacy

Author

Chen, Yiling, Chong, Stephen N, Kash, Ian A., Moran, Tal, and Vadhan, Salil P.

Subjects
Theory, Economics, Mechanism design, privacy, differential privacy
Abstract

Recent work has constructed economic mechanisms that are both truthful and differentially private. In these mechanisms, privacy is treated separately from the truthfulness; it is not incorporated in players' utility functions (and doing so has been shown to lead to non-truthfulness in some cases). In this work, we propose a new, general way of modelling privacy in players' utility functions. Specifically, we only assume that if an outcome o has the property that any report of player i would have led to o with approximately the same probability, then o has small privacy cost to player i. We give three mechanisms that are truthful with respect to our modelling of privacy: for an election between two candidates, for a discrete version of the facility location problem, and for a general social choice problem with discrete utilities (via a VCG-like mechanism). As the number n of players increases, the social welfare achieved by our mechanisms approaches optimal (as a fraction of n)., Engineering and Applied Sciences

Published
2013
Full Text
View/download PDF

103. Information Elicitation for Decision Making

Author

Chen, Yiling and Kash, Ian

Subjects
information elicitation, proper scoring rules, decision rules, decision markets, mechanism design, market design, prediction markets, social and behavioral sciences, economics
Abstract

Proper scoring rules, particularly when used as the basis for a prediction market, are powerful tools for eliciting and aggregating beliefs about events such as the likely outcome of an election or sporting event. Such scoring rules incentivize a single agent to reveal her true beliefs about the event. Othman and Sandholm introduced the idea of a decision rule to examine these problems in contexts where the information being elicited is conditional on some decision alternatives. For example, “What is the probability having ten million viewers if we choose to air new television show X? What if we choose Y?” Since only one show can actually air in a slot, only the results under the chosen alternative can ever be observed. Othman and Sandholm developed proper scoring rules (and thus decision markets) for a single, deterministic decision rule: always select the the action with the greatest probability of success. In this work we significantly generalize their results, developing scoring rules for other deterministic decision rules, randomized decision rules, and situations where there may be more than two outcomes (e.g. less than a million viewers, more than one but less than ten, or more than ten million)., Engineering and Applied Sciences

Published
2011

104. Market Manipulation with Outside Incentives

Author

Chen, Yiling, Gao, Xi, Goldstein, Rick David, and Kash, Ian

Abstract

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 influence 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 find 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 sufficiently large and we lose the separability in equilibrium., Engineering and Applied Sciences

Published
2011

105. Software Economies

Author

Bacon, David F., Bokelberg, Eric, Chen, Yiling, Kash, Ian, Parkes, David C., Rao, Malvika, and Sridharan, Manu

Subjects
design, economics, reliability, verification
Abstract

Software construction has typically drawn on engineering metaphors like building bridges or cathedrals, which emphasize architecture, specification, central planning, and determinism. Approaches to correctness have drawn on metaphors from mathematics, like formal proofs. However, these approaches have failed to scale to modern software systems, and the problem keeps getting worse. We believe that the time has come to completely re-imagine the creation of complex software, drawing on systems in which behavior is decentralized, self-regulating, non-deterministic, and emergent---like economies. In this paper we describe our vision for, and prelimary work on, the creation of software economies for both open systems and internal corporate development, and our plans to deploy these ideas within one of the largest developer communities at IBM., Engineering and Applied Sciences

Published
2010
Full Text
View/download PDF

106. Optimal Pricing and Introduction Timing of New Virtual Machines.

Author

Kash, Ian A., Key, Peter B., and Zoumpoulis, Spyros I.

Subjects
CLOUD computing, VIRTUAL machine systems, PRICING, COMPUTER input-output equipment, ELECTRONIC commerce, CONSUMER behavior
Abstract

As the quality of computer hardware increases over time, cloud service providers have the ability to offer more powerful virtual machines (VMs) and other resources to their customers. But providers face several trade-offs as they seek to make the best use of improved technology. On one hand, more powerful machines are more valuable to customers and command a higher price. On the other hand, there is a cost to develop and launch a new product. Further, the new product competes with existing products. Thus, the provider faces two questions. First, when should new classes of VMs be introduced? Second, how should they be priced, taking into account both the VM classes that currently exist and the ones that will be introduced in the future? This decision problem, combining scheduling and pricing new product introductions, is common in a variety of settings. One aspect that is more specific to the cloud setting is that VMs are rented rather than sold. Thus existing customers can switch to a new offering, albeit with some inconvenience. There is indeed evidence of customers' aversion to upgrades in the cloud computing services market. Based on a study of Microsoft Azure, we estimate that customers who arrive after a new VM class is launched are 50% more likely to use it than existing customers, indicating that these switching costs may be substantial. This opens up a wide range of possible policies for the cloud service provider. Our main result is that a surprisingly simple policy is close to optimal in many situations: new VM classes are introduced on a periodic schedule and each is priced as if it were the only product being offered. (Periodic introductions have been noticeable in the practice of cloud computing. For example, Amazon Elastic Compute Cloud (EC2) launched new classes of the m.xlarge series in October 2007, February 2010, October 2012, and June 2015, i.e., in intervals of 28 months, 32 months, and 32 months.) We refer to this pricing policy as Myerson pricing, as these prices can be computed as in Myerson's classic paper (1981). This policy produces a marketplace where new customers always select the newest and best offering, while existing customers may stick with older VMs due to switching costs. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

107. Enabling Spectrum Sharing in Secondary Market Auctions

Author

Kash, Ian, Murty, Rohan Narayana, and Parkes, David C.

Abstract

Wireless spectrum is a scare resource, but in practice much of it is under-used by current owners. To enable better use of this spectrum, we propose an auction approach to dynamically allocate the spectrum in a secondary market. Unlike previous auction approaches, we seek to take advantage of the ability to share spectrum among some bidders while respecting the needs of others for exclusive use. Thus, unlike unlicensed spectrum (e.g. Wi-Fi), which can be shared by any device, and exclusive-use licensed spectrum, where sharing is precluded, we enable efficient allocation by supporting sharing alongside quality-of-service protections. We present SATYA (Sanskrit for “truth”), a strategyproof and scalable spectrum auction algorithm whose primary contribution is in the allocation of a right to contend for spectrum to both sharers and exclusive-use bidders. Achieving strategyproofness in our setting requires appropriate handling of the externalities created by sharing. We demonstrate SATYA’s ability to handle heterogeneous agent types involving different transmit powers and spectrum needs through extensive simulations., Engineering and Applied Sciences

Published
2013
Full Text
View/download PDF

108. Predicting Your Own Effort

Author

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

Abstract

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 such that information is truthfully reported, best effort is exerted by the worker in completing tasks as quickly as possible, and collusion is not possible. We study the factors influencing when a worker will split a task into subtasks, each forming a separate prediction target., Engineering and Applied Sciences

Published
2012

109. Compact Representations of Separable Graphs

Author

Blandford, Daniel K., Blelloch, Guy E., and Kash, Ian A.

Subjects
FOS: Computer and information sciences, 89999 Information and Computing Sciences not elsewhere classified, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We consider the problem of representing graphs compactly while supporting queries efficiently. In particular we describe a data structure for representing n-vertex unlabeled graphs that satisfy an O(nc)-separator theorem, c < 1. The structure uses O(n) bits, and supports adjacency and degree queries in constant time, and neighbor listing in constant time per neighbor. This generalizes previous results for graphs with constant genus, such as planar graphs.We present experimental results using many "real world" graphs including 3-dimensional finite element meshes, link graphs of the web, internet router graphs, VLSI circuits, and street map graphs. Compared to adjacency lists, our approach reduces space usage by almost an order of magnitude, while supporting depth first traversal in about the same running time.

Published
1986
Full Text
View/download PDF

110. Incentive-compatible mechanisms for norm monitoring in open multi-agent systems (Extended abstract)

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al., 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incen-tivised to monitor the actions of other agents for norm violations

111. Incentivising monitoring in open normative systems

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

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 definition 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.

112. Incentive-compatible mechanisms for norm monitoring in open multi-agent systems (Extended abstract)

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al., 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incen-tivised to monitor the actions of other agents for norm violations

113. Incentivising monitoring in open normative systems

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

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 definition 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.

114. Incentive-compatible mechanisms for norm monitoring in open multi-agent systems (Extended abstract)

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al., 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incen-tivised to monitor the actions of other agents for norm violations

115. Incentivising monitoring in open normative systems

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

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 definition 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.

116. Incentivising monitoring in open normative systems

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

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 definition 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.

117. Incentive-compatible mechanisms for norm monitoring in open multi-agent systems (Extended abstract)

Author

Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., Logan, Brian, Alechina, Natasha, Halpern, Joseph Y., Kash, Ian A., and Logan, Brian

Abstract

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al., 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incen-tivised to monitor the actions of other agents for norm violations

118. Robustness And Optimization Of Scrip Systems

Author

Kash, Ian

Abstract

A game theoretic model of scrip systems in analyzed. It is shown that scrip systems have pure strategy equilibria in a natural class of strategies. An algorithm is given that can compute such an equilibrium and the resulting distribution of money (scrip). The effect of varying the total amount of money in the system on efficiency (i.e., social welfare—the total utility of all the agents in the system) is analyzed, and it is shown that by maintaining the appropriate ratio between the total amount of money and the number of agents, efficiency is maximized. This ratio can be found by increasing the money supply up to the point that the system experiences a “monetary crash,” where money is sufficiently devalued that no agent is willing to perform a service. The implications of the presence of altruists, hoarders, sybils, and collusion on the performance of the system are examined. In practice, agents in a scrip system will not have the necessary information to compute this equilibrium. However, a simple learning algorithm is investigated and simulation results are presented that show it enables agents to converge to equilibrium.

Published
2010

Catalog

Books, media, physical & digital resources
See catalog results