Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.5 (39) << < Пред. | След. > >>    Поиск:
Автор	Тема: На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:41 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =036=> 0153p Iterated Regret Minimization: A New Solution Concept, Joseph Y. Halpern, Rafael Pass, http://ijcai.org/papers09/Abstracts/036.html For some well-known games, such as the Traveler's Dilemma or the Centipede Game, traditional game-theoretic solution concepts — most notably Nash equilibrium — predict outcomes that are not consistent with empirical observations. We introduce a new solution concept, <em>iterated regret minimization,</em> which exhibits the same qualitative behavior as that observed in experiments in many games of interest, including Traveler's Dilemma, the Centipede Game, Nash bargaining, and Bertrand competition. As the name suggests, iterated regret minimization involves the iterated deletion of strategies that do not minimize regret. text: http://ijcai.org/papers09/Papers/IJCAI09-036.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:41 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =037=> 0159p Multi-Step Multi-Sensor Hider-Seeker Games, ED Daniel Halvorson, V.Conitzer, R.Parr, http://ijcai.org/papers09/Abstracts/037.html We study a multi-step hider-seeker game where the hider is moving on a graph and, in each step, the seeker is able to search c subsets of the graph nodes. We model this game as a zero-sum Bayesian game, which can be solved in weakly polynomial time in the players' action spaces. The seeker's action space is exponential in c, and both players' action spaces are exponential in the game horizon. To manage this intractability, we use a column/constraint generation approach for both players. This approach requires an oracle to determine best responses for each player. However, we show that computing a best response for the seeker is NP-hard, even for a single-step game when c is part of the input, and that computing a best response is NP-hard for both players for the multi-step game, even if c = 1. An integer programming formulation of the best response for the hider is practical for moderate horizons, but computing an exact seeker best response is impractical due to the exponential dependence on both c and the horizon. We therefore develop an approximate best response oracle with bounded suboptimality for the seeker. We prove performance bounds on the strategy that results when column/constraint generation with approximate best responses converges, and we measure the performance of our algorithm in simulations. In our experimental results, column/constraint generation converges to near-minimax strategies for both players fairly quickly. http://ijcai.org/papers09/Papers/IJCAI09-037.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:41 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =038=> 0167p Collaborative Multi Agent Physical Search with Probabilistic Knowledge, Noam Hazon, Yonatan Aumann, Sarit Kraus, http://ijcai.org/papers09/Abstracts/038.html This paper considers the setting wherein a group of agents (e.g., robots) is seeking to obtain a given tangible good, potentially available at different locations in a physical environment. Traveling between locations, as well as acquiring the good at any given location consumes from the resources available to the agents (e.g., battery charge). The availability of the good at any given location, as well as the exact cost of acquiring the good at the location is not fully known in advance, and observed only upon physically arriving at the location. However, a-priori probabilities on the availability and potential cost are provided. Given such as setting, the problem is to find a strategy/plan that maximizes the probability of acquiring the good while minimizing resource consumption. Sample applications include agents in exploration and patrol missions, e.g., rovers on Mars seeking to mine a specific mineral. Although this model captures many real world scenarios, it has not been investigated so far. We focus on the case where locations are aligned along a path, and study several variants of the problem, analyzing the effects of communication and coordination. For the case that agents can communicate, we present a polynomial algorithm that works for any fixed number of agents. For non-communicating agents, we present a polynomial algorithm that is suitable for any number of agents. Finally, we analyze the difference between homogeneous and heterogeneous agents, both with respect to their allotted resources and with respect to their capabilities. text: http://ijcai.org/papers09/Papers/IJCAI09-038.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:42 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =039=> 0175p Strengthening Schedules Through Uncertainty Analysis, LM Hiatt, TL Zimmerman, Stephen F. Smith, Reid Simmons, http://ijcai.org/papers09/Abstracts/039.html In this paper, we describe an approach to scheduling under uncertainty that achieves scalability through a coupling of deterministic and probabilistic reasoning. Our specific focus is a class of oversubscribed scheduling problems where the goal is to maximize the reward earned by a team of agents in a distributed execution environment. There is uncertainty in both the duration and outcomes of executed activities. To ensure scalability, our solution approach takes as its starting point an initial deterministic schedule for the agents, computed using expected duration reasoning. This initial agent schedule is probabilistically analyzed to find likely points of failure, and then selectively strengthened based on this analysis. For each scheduled activity, the probability of failing and the impact that failure would have on the schedule's overall reward are calculated and used to focus schedule strengthening actions. Such actions generally entail fundamental trade-offs; for example, modifications that increase the certainty that a high-reward activity succeeds may decrease the schedule slack available to accommodate uncertainty during execution. We describe a principled approach to handling these trade-offs based on the schedule's "expected reward," using it as a metric to ensure that all schedule modifications are ultimately beneficial. Finally, we present experimental results obtained using a multi-agent simulation environment, which confirm that executing schedules strengthened in this way result in significantly higher rewards than are achieved by executing the corresponding initial schedules. text: http://ijcai.org/papers09/Papers/IJCAI09-039.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:42 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =040=> 0181p DCOPs Meet the Real World: Exploring Unknown Reward Matrices with Applications to Mobile Sensor Networks, Manish Jain, Matthew Taylor, M.Tambe, Makoto Yokoo, http://ijcai.org/papers09/Abstracts/040.html Buoyed by recent successes in the area of distributed constraint optimization problems (DCOPs), this paper addresses challenges faced when applying DCOPs to real-world domains. Three fundamental challenges must be addressed for a class of real-world domains, requiring novel DCOP algorithms. First, agents may not know the payoff matrix and must explore the environment to determine rewards associated with variable settings. Second, agents may need to maximize total accumulated reward rather than instantaneous final reward. Third, limited time horizons disallow exhaustive exploration of the environment. We propose and implement a set of novel algorithms that combine decision-theoretic exploration approaches with DCOP-mandated coordination. In addition to simulation results, we implement these algorithms on robots, deploying DCOPs on a distributed mobile sensor network. text: http://ijcai.org/papers09/Papers/IJCAI09-040.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:42 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =041=> 0187p Collaboration and Shared Plans in the Open World: Studies of Ridesharing, Ece Kamar, Eric Horvitz, http://ijcai.org/papers09/Abstracts/041.html We develop and test computational methods for guiding collaboration that demonstrate how shared plans can be created in real-world settings, where agents can be expected to have diverse and varying goals, preferences, and availabilities. The methods are motivated and evaluated in the realm of ridesharing, using GPS logs of commuting data. We consider challenges with coordination among self-interested people aimed at minimizing the cost of transportation and the impact of travel on the environment. We present planning, optimization, and payment mechanisms that provide fair and efficient solutions to the rideshare collaboration challenge. We evaluate different VCG-based payment schemes in terms of their computational efficiency, budget balance, incentive compatibility, and strategy proofness. We present the behavior and analyses provided by the ABC ridesharing prototype system. The system learns about destinations and preferences from GPS traces and calendars, and considers time, fuel, environmental, and cognitive costs. We review how ABC generates rideshare plans from hundreds of real-life GPS traces collected from a community of commuters and reflect about the promise of employing the ABC methods to reduce the number of vehicles on the road, thus reducing CO2 emissions and fuel expenditures. text: http://ijcai.org/papers09/Papers/IJCAI09-041.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:42 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =042=> 0195p Exchanging Reputation Information between Communities: A Payment-Function Approach, Georgia Kastidou, Kate Larson, Robin Cohen, http://ijcai.org/papers09/Abstracts/042.html We introduce a framework so that communities can exchange reputation information about agents in environments where agents are migrating between communities. We view the acquisition of the reputation information as a purchase and focus on the design of a payment function to facilitate the payment for information in a way that motivates communities to truthfully report reputation information for agents. We prove that in our proposed framework, honesty is the optimal policy and demonstrate the value of using a payment-function approach for the exchange of reputation information about agents between communities in multiagent environments. Using our payment function, each community is strengthened: it is able to reason more effectively about which agents to accept and can enjoy agents that are motivated to contribute strongly to the benefit of the community. text: http://ijcai.org/papers09/Papers/IJCAI09-042.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:42 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =043=> 0201p Event-Detecting Multi-Agent MDPs: Complexity and Constant-Factor Approximation, Akshat Kumar, Shlomo Zilberstein, http://ijcai.org/papers09/Abstracts/043.html Planning under uncertainty for multiple agents has flourished with the development of formal models such as multi-agent MDPs and decentralized MDPs. Despite their richness, applicability of these models remains limited due to their computational complexity. We present the class of event-detecting Multi-agent MDPs (eMMDPs), designed to detect multiple mobile targets by a team of sensor agents. We show that eMMDPs are NP-Hard and present a scalable 2-approximation algorithm for solving them using matroid theory and constraint optimization. Its complexity is linear in the state-space and number of agents, quadratic in the horizon, and exponential only in a small parameter that depends on the interaction among the agents. Despite the worst-case approximation ratio of 2, experimental results show that the algorithm produces nearoptimal policies for a range of test problems. text: http://ijcai.org/papers09/Papers/IJCAI09-043.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:42 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =044=> 0208p A Kernel Method for Market Clearing, Sebastien Lahaie, http://ijcai.org/papers09/Abstracts/044.html The problem of market clearing in an economy is that of finding prices such that supply meets demand. In this work, we propose a kernel method to compute nonlinear clearing prices for instances where linear prices do not suffice. We first present a procedure that, given a sample of values and costs for a set of bundles, implicitly computes nonlinear clearing prices by solving an appropriately formulated quadratic program. We then use this as a subroutine in an elicitation procedure that queries demand and supply incrementally over rounds, only as much as needed to reach clearing prices. An empirical evaluation demonstrates that, with a proper choice of kernel function, the method is able to find sparse nonlinear clearing prices with much less than full revelation of values and costs. When the kernel function is not suitable to clear the market, the method can be tuned to achieve approximate clearing. http://ijcai.org/papers09/Abstracts/044.html [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:43 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =045=> 0214p Balancing Utility and Deal Probability for Auction-based Negotiations in Highly Nonlinear Utility Spaces, http://ijcai.org/papers09/Abstracts/045.html Ivan Marsa-Maestre, Miguel A. Lopez-Carmona, Juan R. Velasco, Takayuki Ito, Mark Klein, Katsuhide Fujita Negotiation scenarios involving nonlinear utility functions are specially challenging, because traditional negotiation mechanisms cannot be applied. Even mechanisms designed and proven useful for nonlinear utility spaces may fail if the utility space is highly nonlinear. For example, although both contract sampling and constraint sampling have been successfully used in auction based negotiations with constraint-based utility spaces, they tend to fail in highly nonlinear utility scenarios. In this paper, we will show that the performance of these approaches decrease drastically in highly nonlinear utility scenarios, and propose a mechanism which balances utility and deal probability for the bidding and deal identification processes. The experiments show that the proposed mechanisms yield better results than the previous approaches in highly nonlinear negotiation scenarios. text: http://ijcai.org/papers09/Papers/IJCAI09-045.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:43 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =046=> 0220p Strategyproof Classification with Shared Inputs, Reshef Meir, Ariel D. Procaccia, Jeffrey S. Rosenschein, http://ijcai.org/papers09/Abstracts/046.html Strategyproof classification deals with a setting where a decision-maker must classify a set of input points with binary labels, while minimizing the expected error. The labels of the input points are reported by self-interested agents, who might lie in order to obtain a classifier that more closely matches their own labels, thus creating a bias in the data; this motivates the design of truthful mechanisms that discourage false reports. Previous work [Meir et al., 2008] investigated both decision-theoretic and learning-theoretic variations of the setting, but only considered classifiers that belong to a degenerate class.In this paper we assume that the agents are interested in a shared set of input points. We show that this plausible assumption leads to powerful results. In particular, we demonstrate that variations of a truthful random dictator mechanism can guarantee approximately optimal outcomes with respect to any class of classifiers. text: http://ijcai.org/papers09/Papers/IJCAI09-046.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:43 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =047=> 0226p Argumentation System with Changes of an Agent's Knowledge Base, Kenichi Okuno, Kazuko Takahashi, http://ijcai.org/papers09/Abstracts/047.html This paper discusses a process of argumentation. We propose an algorithm for dynamic treatment of argumentation in which all lines of argumentation are executed in succession, and the agent's knowledge base can change during argumentation. We show that there exists a case in which an agent dynamically loses argumentation that would be considered won by a static analysis. We also show that the algorithm terminates, and describe acceptable arguments that are obtained after the argumentation. text: http://ijcai.org/papers09/Papers/IJCAI09-047.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:43 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =048=> 0233p How Pervasive Is the Myerson-Satterthwaite Impossibility?, Abraham Othman, Tuomas Sandholm, http://ijcai.org/papers09/Abstracts/048.html The Myerson-Satterthwaite theorem is a foundational impossibility result in mechanism design which states that no mechanism can be Bayes-Nash incentive compatible, individually rational, and not run a deficit. It holds universally for priors that are continuous, gapless, and overlapping. Using automated mechanism design, we investigate how often the impossibility occurs over discrete valuation domains. While the impossibility appears to hold generally for settings with large numbers of possible valuations (approaching the continuous case), domains with realistic valuation structure circumvent the impossibility with surprising frequency. Even if the impossibility applies, the amount of subsidy required to achieve individual rationality and incentive compatibility is relatively small, even over large unstructured domains. text: http://ijcai.org/papers09/Papers/IJCAI09-048.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:43 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =049=> 0239p Thou Shalt Covet Thy Neighbor's Cake, Ariel D. Procaccia, http://ijcai.org/papers09/Abstracts/049.html The problem of fairly dividing a cake (as a metaphor for a heterogeneous divisible good) has been the subject of much interest since the 1940's, and is of importance in multiagent resource allocation. Two fairness criteria are usually considered: proportionality, in the sense that each of the n agents receives at least 1/n of the cake; and the stronger property of envy-freeness, namely that each agent prefers its own piece of cake to the others' pieces. For proportional division, there are algorithms that require O(nlogn) steps, and recent lower bounds imply that one cannot do better. In stark contrast, known (discrete) algorithms for envy-free division require an unbounded number of steps, even when there are only four agents.In this paper, we give an Omega(n<sup>2</sup> lower bound for the number of steps required by envy-free cake-cutting algorithms. This result provides, for the first time, a true separation between envy-free and proportional division, thus giving a partial explanation for the notorious difficulty of the former problem. text: http://ijcai.org/papers09/Papers/IJCAI09-049.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:44 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =050=> 0245p Generalised Fictitious Play for a Continuum of Anonymous Players, Zinovi Rabinovich, Enrico Gerding, Maria Polukarov, Nicholas R. Jennings, http://ijcai.org/papers09/Abstracts/050.html Recently, efficient approximation algorithms for finding Nash equilibria have been developed for the interesting class of anonymous games, where a player's utility does not depend on the identity of its opponents. In this paper, we tackle the problem of computing equilibria in such games with continuous player types, extending the framework to encompass settings with imperfect information. In particular, given the existence result for pure Bayes-Nash equilibiria in these games, we generalise the fictitious play algorithm by developing a novel procedure for finding a best response strategy, which is specifically designed to deal with continuous and, therefore, infinite type spaces. We then combine the best response computation with the general fictitious play structure to obtain an equilibrium. To illustrate the power of this approach, we apply our algorithm to the domain of simultaneous auctions with continuous private values and discrete bids, in which the algorithm shows quick convergence. text: http://ijcai.org/papers09/Papers/IJCAI09-050.pdf [Ответ][Цитата]
Стр.5 (39): 1  2  3  4  [5]  6  7  8  9  ...  39 << < Пред. | След. > >>