?
How to Guide a Present-Biased Agent Through Prescribed Tasks?
P. 3461–3468.
Belova T., Dementiev Y., Fomin F., Golovach P., Ignatiev A.
Publication based on the results of:
Onoprienko A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
We study the algorithmic complexity of the cooperative card game Hanabi. The feature of Hanabi is that players see each other’s cards but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters ofthe game ...
Added: November 23, 2025
Vladlena D. Markvirer, Ekaterina A. Karnaukhova, , in: 023 International Conference on Quality Management, Transport and Information Security, Information Technologies (IT&QM&IS).: Petrozavodsk: IEEE, 2023. P. 152–155.
This article presents an overview of the main algorithms used in resource distribution problems. The description, input and output data, as well as peculiarities and complexity of these algorithms are considered. The paper proposes a modified algorithm for finding vapor combinations in a graph, which allows solving the problem of optimal load distribution between the ...
Added: December 25, 2023
Dementiev Yuriy, Fomin F., Ignatiev A., , in: Thirty-Sixth AAAI Conference on Artificial IntelligenceVol. 36. Issue 9: AAAI-22 Technical Tracks 9.: Palo Alto: AAAI Press, 2022. P. 9724–9731.
One of the most widespread human behavioral biases is the present bias -- the tendency to overestimate current costs by a bias factor. Kleinberg and Oren (2014) introduced an elegant graph-theoretical model of inconsistent planning capturing the behavior of a present-biased agent accomplishing a set of actions. The essential measure of the system introduced by ...
Added: January 26, 2023
Palo Alto: AAAI Press, 2022.
The proceedings have been published in 11 consecutive issues. This issue (volume 36 no. 9) consists of 1131 pages and five tracks:
AAAI Technical Track on Multiagent Systems
AAAI Technical Track on Philosophy and Ethics of AI
AAAI Technical Track on Planning, Routing, and Scheduling
AAAI Technical Track on Reasoning under Uncertainty
AAAI Technical Track on Search and Optimization ...
Added: January 26, 2023
Bychkov A., Pogudin G., ACM Communications in Computer Algebra 2021 Vol. 54 No. 3 P. 119–123
Transformation of a polynomial ODE system to a special quadratic form has been successfully used recently as a preprocessing step for model order reduction methods. However, to the best of our knowledge, there has been no practical algorithm for performing this step automatically with any optimality guarantees.
We present an algorithm that, given a system of ...
Added: October 19, 2021
Springer, 2020.
This book constitutes the proceedings of the 15th International Computer Science Symposium in Russia, CSR 2020, held in Yekaterinburg, Russia, in June 2020.
The 25 full papers and 6 invited papers were carefully reviewed and selected from 49 submissions. The papers cover a broad range of topics, such as: algorithms and data structures; computational complexity, including ...
Added: September 4, 2020
Springer, 2019.
Added: August 4, 2019
Ianovski E., Ong L., Artificial Intelligence 2018 No. 261 P. 1–15
Boolean games allow us to succinctly represent strategic games with binary payoffs in the case where the players' preferences have a structure readily expressible in propositional logic. Since their introduction, the computational aspects of Boolean games have been of interest to the multiagent community, but so far the focus has been exclusively on pure strategy ...
Added: February 25, 2019
Ianovski E., Ong L., Information and Computation 2018 No. 261 P. 488–518
Boolean games are a succinct representation of strategic games with a logical flavour. While they have proved to be a popular formalism in the multiagent community, a commonly cited shortcoming is their inability to express richer utilities than success or failure. In addition to being a modelling limitation, this parsimony of preference has made proving ...
Added: February 25, 2019
Ianovski E., Ong L., , in: Proceedings, Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR-14).: Palo Alto: AAAI Press, 2014.
Boolean games are an expressive and natural formalism through which to investigate problems of strategic interaction in multiagent systems. Although they have been widely studied, almost all previous work on Nash equilibria in Boolean games has focused on the restricted setting of pure strategies. This is a shortcoming as finite games are guaranteed to have ...
Added: February 25, 2019
Springer, 2018.
This book constitutes the refereed post-conference proceedings of the 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, held in Singapore, Singapore, in July 2018. The 31 regular papers presented in this volume were carefully reviewed and selected from 69 submissions. They cover diverse areas of combinatorical algorithms, complexity theory, graph theory and combinatorics, combinatorial optimization, ...
Added: October 23, 2018
Babenko M. A., Artamonov S., , in: 28th International Symposium on Algorithms and Computation, ISAAC 2017Vol. 92.: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2017. P. 1–12.
Let G = (V,E) be an undirected graph, T ⊆ V be a set of terminals. Then a natural combinatorial problem consists in finding the maximum number of vertex-disjoint paths connecting distinct terminals. For this problem, a clever construction suggested by Gallai reduces it to computing a maximum non-bipartite matching and thus gives an O ( m ...
Added: March 1, 2018
Gurvich V., Endre B., Khaled E. et al., International Journal of Game Theory (Германия) 2016 Vol. 45 No. 4 P. 1111–1131
In 1964 Shapley observed that a matrix has a saddle point in pure strategies whenever every its (Formula presented.) submatrix has one. In contrast, a bimatrix game may have no pure strategy Nash equilibrium (NE) even when every (Formula presented.) subgame has one. Nevertheless, Shapley’s claim can be extended to bimatrix games as follows. We ...
Added: February 6, 2017
Berlin: Springer, 2014.
This book constitutes the refereed proceedings of the 22st Annual European Symposium on Algorithms, ESA 2014, held in Wrocław, Poland, in September 2014, as part of ALGO 2014. The 69 revised full papers presented were carefully reviewed and selected from 269 initial submissions: 57 out of 221 in Track A, Design and Analysis, and 12 ...
Added: September 2, 2014
Polyakov I. V., Chepovskiy A., Chepovskiy A., Вестник Новосибирского государственного университета. Серия: Информационные технологии 2013 Т. 11 № 4 С. 77–83
In this paper special data structure for big social graph storing and operating is presented. We discuss mainly graph paths searching, obtaining subgrapths and addition of new edges and vertices. ...
Added: October 17, 2013
Dmitry Romanov, Kravchenko A., , in: Concept Discovery in Unstructured Data. 2nd International Workshop, CDUD 2012, Leuven, Belgium, May 2012, ProceedingsIssue 871.: Leuven: Katholieke Universiteit Leuven, 2012. Ch. 5 P. 40–48.
The goal of the expert search task is nding knowledgeable persons within the enterprise. In this paper we focus on its distinctions from the other information retrieval tasks. We review the existing approaches and propose a new term weighting scheme which is based on analysis of communication patterns between people. The e ectiveness of the proposed ...
Added: March 20, 2013
Babenko M. A., Karzanov A. V., Journal of Combinatorial Optimization 2012 Vol. 24 No. 3 P. 202–228
We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$. A path in $G$ is a \emph{$T$-path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$-path ...
Added: January 27, 2013
Babenko M. A., Algorithmica 2012 Vol. 64 No. 3 P. 362–383
Given a digraph $G = (VG,AG)$, an even factor $M \subseteq AG$ is a set formed by node-disjoint paths and even cycles. Even factors in digraphs were introduced by Geelen and Cunningham and generalize path matchings in undirected graphs. Finding an even factor of maximum cardinality in a general digraph is known to be NP-hard ...
Added: January 27, 2013