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

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

Все темы | Новая тема  Стр.4 (39) << < Пред. | След. > >>    Поиск:
Автор	Тема: На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:38 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =022=> 0067p Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods, Sylvain Bouveret, Ulle Endriss, Jérôme Lang, http://ijcai.org/papers09/Abstracts/022.html While there are several languages for representing combinatorial preferences over sets of alternatives, none of these are well-suited to the representation of ordinal preferences over sets of goods (which are typically required to be monotonic). We propose such a language, taking inspiration from previous work on graphical languages for preference representation, specifically CP-nets, and introduce conditional importance networks (CI-nets). A CI-net includes statements of the form "if I have a set A of goods, and I do not have any of the goods from some other set B, then I prefer the set of goods C over the set of goods D." We investigate expressivity and complexity issues for CI-nets. Then we show that CI-nets are well-suited to the description of fair division problems. text: http://ijcai.org/papers09/Papers/IJCAI09-022.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:38 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =023=> 0073p Planning Games, Ronen I. Brafman, Carmel Domshlak, Yagil Engel, Moshe Tennenholtz, http://ijcai.org/papers09/Abstracts/023.html We introduce planning games, a study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of planning games and adapt game-theoretic solution concepts to these models. In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure. text: http://ijcai.org/papers09/Abstracts/023.html [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:38 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =024=> 0079p Coalitional Affinity Games and the Stability Gap, Simina Branzei, Kate Larson, http://ijcai.org/papers09/Abstracts/024.html We present and analyze coalitional affinity games, a family of hedonic games that explicitly model the value that an agent receives from being associated with other agents. We provide a characterization of the social-welfare maximizing coalition structures, and study the stability properties of affinity games, using the core solution concept. Interestingly, we observe that members of the core do not necessarily maximize social welfare. We introduce a new measure, the stability-gap to capture this difference. Using the stability gap, we show that for an interesting class of coalitional affinity games, the difference between the social welfare of a stable coalition structure and a social welfare maximizing coalition structure is bounded by a factor of two, and that this bound is tight. text: http://ijcai.org/papers09/Papers/IJCAI09-024.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:39 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =025=> 0085p Simple Coalitional Games with Beliefs, G.Chalkiadakis, Edith Elkind, NR Jennings, http://ijcai.org/papers09/Abstracts/025.html We introduce coalitional games with beliefs (CGBs), a natural generalization of coalitional games to environments where agents possess private beliefs regarding the capabilities (or types) of others. We put forward a model to capture such agent-type uncertainty, and study coalitional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coalition structures. For simple games without coalition structures, we then provide a characterization of the core that matches the one for the full information case, and use it to derive a polynomial-time algorithm to check core nonemptiness. In contrast, we demonstrate that in games with coalition structures allowing beliefs increases the computational complexity of stability-related problems. In doing so, we introduce and analyze weighted voting games with beliefs, which may be of independent interest. Finally, we discuss connections between our model and other classes of coalitional games. text: http://ijcai.org/papers09/Papers/IJCAI09-025.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:39 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:39 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =026=> 0091p Commitment Tracking via the Reactive Event Calculus, Federico Chesani, Paola Mello, Marco Montali, Paolo Torroni, http://ijcai.org/papers09/Abstracts/026.html Runtime commitment verification is an important, open issue in multiagent research. To address it, we build on Yolum and Singh's formalization of commitment operations, on Chittaro and Montanari's cached event calculus, and on the SCIFF abductive logic programming proof-procedure. We propose a framework consisting of a declarative and compact language to express the domain knowledge, and a reactive and complete procedure to track the status of commitments effectively, producing provably sound and irrevocable answers. text: http://ijcai.org/papers09/Papers/IJCAI09-026.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:39 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =027=> 0097p Compiling the Votes of a Subelectorate, Yann Chevaleyre, Jérôme Lang, Nicolas Maudet, G. Ravilly-Abadie, http://ijcai.org/papers09/Abstracts/027.html In many practical contexts where a number of agents have to find a common decision, the votes do not come all together at the same time. In such situations, we may want to preprocess the information given by the subelectorate (consisting of the voters who have expressed their votes) so as to ``compile'' the known votes for the time when the latecomers have expressed their votes. We study the amount of space necessary for such a compilation, as a function of the voting rule, the number of candidates, and the number of votes already known. We relate our results to existing work, especially on communication complexity. text: http://ijcai.org/papers09/Papers/IJCAI09-027.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:39 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =028=> 0103p How Hard is it to Control Sequential Elections via Agenda?, V.Conitzer, J.Lang, L.Xia, http://ijcai.org/papers09/Abstracts/028.html Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach is to vote on the issues one at a time, in sequence; however, a drawback is that the outcome may depend on the order in which the issues are voted upon and decided, which gives the chairperson some control over the outcome of the election because she can strategically determine the order. While this is undeniably a negative feature of sequential voting, in this paper we temper this judgment by showing that the chairperson's control problem is, in most cases, computationally hard. text: http://ijcai.org/papers09/Papers/IJCAI09-028.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:40 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =029=> 0109p Preference Functions That Score Rankings and Maximum Likelihood Estimation, Vincent Conitzer, Matthew Rognlie, Lirong Xia, http://ijcai.org/papers09/Abstracts/029.html In social choice, a preference function (PF) takes a set of votes (linear orders over a set of alternatives) as input, and produces one or more rankings (also linear orders over the alternatives) as output. Such functions have many applications, for example, aggregating the preferences of multiple agents, or merging rankings (of, say, webpages) into a single ranking. The key issue is choosing a PF to use. One natural and previously studied approach is to assume that there is an unobserved "correct" ranking, and the votes are noisy estimates of this. Then, we can use the PF that always chooses the maximum likelihood estimate (MLE) of the correct ranking. In this paper, we define simple ranking scoring functions (SRSFs) and show that the class of neutral SRSFs is exactly the class of neutral PFs that are MLEs for some noise model. We also define composite ranking scoring functions (CRSFs) and show a condition under which these coincide with SRSFs. We study key properties such as consistency and continuity, and consider some example PFs. In particular, we study Single Transferable Vote (STV), a commonly used PF, showing that it is a CRSF but not an SRSF, thereby clarifying the extent to which it is an MLE function. This also gives a new perspective on how ties should be broken under STV. We leave some open questions. text: http://ijcai.org/papers09/Papers/IJCAI09-029.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:40 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =030=> 0116p Learning Graphical Game Models, http://ijcai.org/papers09/Abstracts/030.html Quang Duong, Yevgeniy Vorobeychik, Satinder Singh, Michael Wellman Graphical games provide compact representation of a multiagent interaction when agents' payoffs depend only on actions of agents in their local neighborhood. We formally describe the problem of learning a graphical game model from limited observation of the payoff function, define three performance metrics for evaluating learned games, and investigate several learning algorithms based on minimizing empirical loss. Our first algorithm is a branch-and-bound search, which takes advantage of the structure of the empirical loss function to derive upper and lower bounds on loss at every node of the search tree. We also examine a greedy heuristic and local search algorithms. Our experiments with directed graphical games show that (i) when only a small sample of profile payoffs is available, branch-and-bound significantly outperforms other methods, and has competitive running time, but (ii) when many profiles are observed, greedy is nearly optimal and considerably better than other methods, at a fraction of branch-and-bound's running time. The results are comparable for undirected graphical games and when payoffs are sampled with noise. text: http://ijcai.org/papers09/Papers/IJCAI09-030.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:40 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =031=> 0122p Preference Aggregation over Restricted Ballot Languages: Sincerity and Strategy-Proofness, Ulle Endriss, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, http://ijcai.org/papers09/Abstracts/031.html Voting theory can provide useful insights for multiagent preference aggregation. However, the standard setting assumes voters with preferences that are total orders, as well as a ballot language that coincides with the preference language. In typical AI scenarios, these assumptions do not hold: certain alternatives may be incomparable for some agents, and others may have their preferences encoded in a format that is different from how the preference aggregation mechanism wants them. We study the consequences of dropping these assumptions. In particular, we investigate the consequences for the important notion of strategy-proofness. While strategy-proofness cannot be guaranteed in the classical setting, we are able to show that there are situations in our more general framework where this is possible. We also consider computational aspects of the problem. text: http://ijcai.org/papers09/Abstracts/031.html [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:40 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =032=> 0128p Multimode Control Attacks on Elections, Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, http://ijcai.org/papers09/Abstracts/032.html In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections — attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time. text: http://ijcai.org/papers09/Papers/IJCAI09-032.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:40 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =033=> 0134p Charting the Tractability Frontier of Mixed Multi-Unit Combinatorial Auctions, Valeria Fionda, Gianluigi Greco, http://ijcai.org/papers09/Abstracts/033.html Mixed multi-unit combinatorial auctions (MMUCAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i.e., determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from CAs, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out based on constraining their characteristics. The paper precisely fills this gap, by depicting a clear picture of the tractability frontier for MMUCA instances under both structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively. By analyzing these restrictions, a sharp frontier is charted based on various dichotomy results. In particular, tractability islands resulting from the investigation generalize on MMUCAs the largest class of tractable CAs emerging from the literature. text: http://ijcai.org/papers09/Papers/IJCAI09-033.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:41 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =034=> 0140p Computing Equilibria in Multiplayer Stochastic Games of Imperfect Information, Sam Ganzfried, Tuomas Sandholm, http://ijcai.org/papers09/Abstracts/034.html Computing a Nash equilibrium in multiplayer stochastic games is a notoriously difficult problem. Prior algorithms have been proven to converge in extremely limited settings and have only been tested on small problems. In contrast, we recently presented an algorithm for computing approximate jam/fold equilibrium strategies in a three-player no-limit Texas hold'em tournament — a very large real-world stochastic game of imperfect information. In this paper we show that it is possible for that algorithm to converge to a non-equilibrium strategy profile. However, we develop an ex post procedure that determines exactly how much each player can gain by deviating from his strategy, and confirm that the strategies computed in that earlier paper actually do constitute an epsilon-equilibrium for a very small epsilon (0.5% of the tournament entry fee). Next, we develop several new algorithms for computing a Nash equilibrium in multiplayer stochastic games (with perfect or imperfect information) which can provably never converge to a non-equilibrium. Experiments show that one of these algorithms outperforms the original algorithm on the same poker tournament. In short, we present the first algorithms for provably computing an epsilon-equilibrium of a large stochastic game for small epsilon. Finally, we present an efficient algorithm that minimizes external regret in both the perfect and imperfect information case. text: http://ijcai.org/papers09/Papers/IJCAI09-034.pdf [Ответ][Цитата]
Capt.Drew Сообщений: 4179	На: Ai Drew :: IJCAI 09 :: Междунар. ии конфа: Позднее лето-2009 - Коротко о Главном Добавлено: 21 авг 09 6:41 PART-1: AGENT-BASED and MULTI-AGENT SYSTEMS: =035=> 0147p On the Complexity of Compact Coalitional Games, Gianluigi Greco, Enrico Malizia, L.Palopoli, Francesco Scarcello, http://ijcai.org/papers09/Abstracts/035.html A significantly complete account of the complexity underlying the computation of relevant solution concepts in compact coalitional games is provided. The starting investigation point is the setting of graph games, about which various long-standing open problems were stated in the literature. The paper gives an answer to most of them, and in addition provides new insights on this setting, by stating a number of complexity results about some relevant generalizations and specializations. The presented results also pave the way towards precisely carving the tractability frontier characterizing computation problems on compact coalitional games. text: http://ijcai.org/papers09/Papers/IJCAI09-035.pdf [Ответ][Цитата]
Стр.4 (39): 1  2  3  [4]  5  6  7  8  ...  39 << < Пред. | След. > >>