bluuebunny/crossref_metadata_2025 huggingface dataset:
Formation of a new framework model of spatial development as a result of transformation of multi-level territorial systems
Authors: Gataullin Rinat
Published: June 2020

The article discusses the content and types of territorial frameworks. Each type of frame is considered as a complete and living structure, when between the elements of which there must be a dynamic proportionality. The economic content of territorial frameworks is considered as a special kind of public goods, the usefulness of which exists in the form of a positive impact of their elements on the development of the economy and improving the quality of life of the population. Signs of certain types of territorial frameworks are given (the focus on meeting a certain group of needs, the specifics in the way of organizing activities, the uniformity of the material and technical base and the mandatory presence of its elements on the territory). Industrial, agricultural, social, infrastructure, construction, environmental and settlement frameworks are considered. A system of criteria for optimizing existing frameworks is proposed. The scheme of forming a framework model of spatial development is also given.
Areas, their linear and point components are considered as elements of frameworks. Areas – the location of agricultural production, forests and areas for settlement, point elements-settlements, natural monuments, linear-rivers, transport arteries, forest belts, etc.
In structural and functional analysis, the main elements of the spatial structure of regions can be identified in the economic framework – points of growth, subregions and special zones of various types, in settlement-a system of interconnected and interacting, hierarchically functioning settlements that form agglomerations and non-agglomeration settlements, in infrastructure development-transport networks, pipelines and navigable rivers.
As it turned out, the planned economic policy in Bashkiria generally takes into account existing imbalances in the development of territorial frameworks and is aimed at overcoming them
Behavior of broilers subjected to different light spectra and illuminances
Authors: Lucena Aline C. , Pandorfi Héliton , Almeida Gledson L. P. , Guiselini Cristiane , Araújo José E. M. , Rodrigues Tatiana P. N. da S.
Published: June 2020

ABSTRACT The ideal illuminance in poultry houses for broiler chickens may lead to improvement in housing efficiency and broiler welfare. In this context, the objective of this research was to evaluate the behavior and welfare of broiler chickens under effect of illuminance by light-emitting diode (LED) in white band (400-760 nm) and blue/green band (470-525 nm). The experiment was conducted from October to December 2017, in the municipality of Carpina, PE, Brazil, and had 384-oneday-old chicks (mixed batch), Cobb 500 strain. The adopted design was completely randomized, in a 4 x 2 factorial scheme, corresponding to four illuminances, 5 lx (I1), 20 lx (I2), 150 lx (I3) and 5-20 lx (5 lx in the 1st, 2nd and 6th weeks and 20 lx in the 3rd, 4th and 5th weeks - I4), and two light spectra using LED bars, RGB type, in white (400-760 nm) color (C1) and blue/green (470-525 nm) dichromatic color (C2), with three repetitions. A continuous lighting program was used, 18 h of light and 6 h of dark per day. Ingestive, posture, comfort and natural behaviors, aggressiveness and discomfort of the broiler were evaluated. Broiler behavioral variables were determined by the frequency of the events and their probability of occurrence by the Chi-square test. Broilers subjected to wavelengths in the blue/green range and illuminance of 20 lx and 5-20 lx showed more significant ingestive and comfort behaviors, which demonstrates better welfare under these housing conditions.
Effects of Mental Disorders on the Emotional Intelligence Levels of Brazilian Medical Students: a Single Center Cross-Sectional Study, 2017-2018
Authors: Coury Marayra Inês França , Duca João Gabriel Menezes , Toledo Júnior Antonio
Published: June 2020

Abstract: Introduction: Recent studies have shown the direct effects of emotional intelligence (EI) on medical practice and, more specifically, on establishing and maintaining a good doctor-patient relationship. The aim was to compare the EI levels of students from different years of medical school and to evaluate other factors that affect EI levels. Method: This was a cross-sectional study of medical students attending the 1st, 3rd and 6th years in a private institution in Belo Horizonte, Minas Gerais, Brazil. A non-probabilistic convenience sample was used. EI levels were evaluated using the Schutte Self-Report EI Test, and demographic and personal data were collected. All volunteers signed the free and informed consent form prior to study inclusion. Statistical analysis used ANOVA, Student’s t-test, Pearson correlation and linear regression. A significance level of 0.05 was adopted. Results: Two hundred twenty-five volunteers were recruited between October/2017 and April/2018. Sixteen (7.1%) were excluded due to incomplete questionnaires. The final sample comprised 209 participants (71 from the 1st year, 69 from the 3rd year and 69 from the 6th year). Most were women (66.0%), 95.2% were single, 10.0% had previously graduated and 16.3% reported a previous mental disorder diagnosis. The mean age was 23.2 (±3.9) years. There was no difference in the EI overall score and in the different EI domains scores among the students from the three years. Pearson’s test showed a weak positive correlation between age and total score (r=0.172; p=0.013) and perception of emotion (r=0.236; p=0.001). Multiple regression showed a significant positive association between age and the total score (p=0.040), Perception of Emotion (padjusted=0.013) and Managing Others’ Emotions (padjusted=0.020). A significant reduction in the total score (padjusted=0.033), in Managing Own Emotions (padjusted<0.001) and in the Managing Others’ Emotions (padjusted=0.025) was found for volunteers who reported a previous mental disorder. Conclusion: High levels of EI were observed in the 3 years. No association was observed between different EI scores and the course year. There was a positive correlation between age and total EI score, Perception of Emotions, Managing Own Emotions and Managing Others’ Emotions. The presence of a mental disorder was associated with a reduction in the total score and the scores for Managing Own Emotions and Managing Others’ Emotions.
Fish biomarker responses to perturbation by drought in streams
Authors: Ondei Luciana de Souza , Teresa Fabrício Barreto , Garcia Danielly Pereira , Felício Andréia Arantes , da Silva Danilo Grünig Humberto , de Almeida Eduardo Alves
Published: June 2020

ABSTRACT Drought can be viewd as a perturbation in running waters and fish are often trapped in isolated pools, where deterioration of water quality may be stressful. We investigated how this extreme condition influences response of oxidative stress biomarkers. The response of the characid Astyanax elachylepis was assessed during the dry and rainy seasons in intermittent and perennial (control) sites in streams from Brazilian savannah (Cerrado). We predicted that the biomarkers would be enhanced in the dry season in intermittent streams only due the environmentally harsh conditions in the few isolated pools that remain filled with water. As predicted, fish from the intermittent stream in the dry season presented higher gill MDA values, indicating greater stress. In the liver, MDA values were higher in the dry season for both intermittent and perennial streams, suggesting a generalized seasonal response. As expected, some antioxidant response enzymes changed in the intermittent sites during the dry season. Therefore, oxidative stress biomarkers vary seasonally, with greater increase in intermittent sites. These evidences contribute for the understanding of the spatio-temporal variation of the fish responses and fish resistance to perturbations by drought in tropical environments.
Padrões culturais e mudanças na tradição em reação à sobrevivência econômica
Authors: Baiardi Amilcar , Laniado Ruthy Nadia
Published: June 2020

Resumo Rápidas e profundas mudanças provocadas na economia brasileira pela globalização econômica levaram à concepção de estratégias de sobrevivência por parte de diferentes agentes, presentes nos vários mercados da economia nacional. No estado da Bahia, os empresários se organizaram em torno da ação coletiva para lidar com as mudanças resultantes do esforço de adaptação da economia local. A tradição regional de relacionamento entre firmas, baseada na eventual e descontínua constituição de grupos de interesse para alcançar objetivos comuns, contrasta com os novos padrões de conduta exigidos em uma economia e sociedade globalizadas. Estes valorizam a cooperação como recurso para proceder à reestruturação de corporações, de mercados e de redes organizacionais, para melhor lidar com a competição internacional. O foco do presente artigo é examinar a relevância da cooperação e da confiança na organização da ação coletiva como uma estratégia implementada por meio de redes para lidar com as mudanças requeridas, sobretudo nos setores onde os atores locais encontram-se em posições mais vulneráveis em relação aos sistemas globalizados.
Criatividade na ação política
Authors: Davel Eduardo Paes Barreto , Oliveira Josiane Silva de , Ventura Andréa Cardoso
Published: June 2020

Resumo A energia da resistência criativa pode descortinar ao pesquisador em Administração e em Estudos Organizacionais vários horizontes e várias possibilidades de teorização relevantes para estimular a prática. Como poderíamos pensar de forma mais estruturada a criatividade como fonte para protestar, subverter e resistir? Como a criatividade poderia abrir novos caminhos para pensar a ação política e crítica em nosso campo de pesquisa? Será que a criatividade poderia ser uma via de resistência ao status quo e abrir caminhos inovadores para teorizarmos sobre a governança climática urbana?
Urgent vs. early-start peritoneal dialysis: patients' profile and outcomes
Authors: Calice-Silva Viviane , Tonial Bruna C. , Ferreira Helen C. , Nerbass Fabiana B.
Published: June 2020

ABSTRACT Introduction: Peritoneal dialysis (PD) has been considered a safe option of therapy in end-stage renal disease patients with urgent need of dialysis. Recently, it was proposed that Urgent-Start-PD (US-PD) be defined when PD starts within 72 hours after catheter placement and “early start” PD (ES-PD) when PD starts between 3 and 14 days after. We aimed to compare demographic and clinical characteristics between patients in US-PD and ES-PD as well as 30-day complications, 6-month hospitalization, and dropout rate. Methods: Adult patients starting PD within 14 days after catheter insertion (October/2016 - February/2019) were included and divided into US-PD group and ES-PD group based on the their PD initiation time. Clinical and demographic data, fill volume for the first PD session, 30-day complications, 6-month hospitalization, and dropout rate were assessed. Results: In our study, 72 patients were analyzed (US-PD=40, ES-PD=32) with mean age of 53.2±15.2 years old. No differences between US-PD and ES-PD regarding demographic characteristics, 30-day complications, 6-month hospitalization, and dropout events were found. The most frequent short-term complication in patients who started PD urgently was leakage. The most common cause of dropout was transfer to HD. Conclusion: Fifty five percent of our sample started PD less than 72 hours after catheter insertion. The lack of difference in the measured outcomes compared to patients that had therapy initiated after this period encourages the use of urgent PD when needed.
LA DIFUSIÓN DE LOS JUEGOS DE LA MAISON DES PETITS EN ESPAÑA
Authors: Gallego Dolores Carrillo , Carrillo Pilar Olivares
Published: June 2020

Resumen El material Discat, creado por Mina Audemars y Louise Lafendel en la Maison des Petits, en Ginebra, fue utilizado por ellas para el aprendizaje matemático de los niños entre 3 y 8 años. El trabajo estudia la difusión de este material en España, entre 1925 y 1936, utilizando como fuentes los libros, artículos de revistas, catálogos de material escolar y anuncios comerciales que se publicaron en España en esa época.
Mechanized harvesting of 'Conilon' coffee clones
Authors: Souza Gustavo Soares de , Lani José Antônio , Infantini Maurício Blanco , Krohling César Abel , Senra João Felipe de Brites
Published: June 2020

Abstract: The objective of this work was to evaluate the speed effect of a coffee harvester and its interaction with 'Conilon' coffee (Coffea canephora) clones on the mechanical harvesting efficiency. The experiment was installed in São Mateus, in the state of Espírito Santo, Brazil, in 2012, with 27 clones of early, intermediate, and late fruit ripening. The first harvest was performed after the plant cuttings at 0.5 m above the ground, in 2016, and the canopy renovation. The plants and the harvester were evaluated in 2018. The coffee harvester was tested at 0.6 and 0.8 km h-1. Measurements were performed for stripping and harvesting efficiencies, fruit loss on the ground, unstripped fruit, defoliation with manual and mechanized harvesting, fruit removal force, and fruit ripening degree. The tests with the coffee harvester indicated a technical feasibility of 88% average harvesting efficiency, and a 15% lower defoliation than the manual harvesting. The harvesting speed of 0.8 km h-1 results in higher stripping and harvesting efficiencies, in a lower percentage of loss on the ground, and in less unstripped fruit, regardless of the evaluated clones. Fruit removal force and ripening degree influence the stripping and harvesting efficiencies and the percentage of unstripped fruit of 'Conilon' coffee.
Theory-Based Causal Transfer:Integrating Instance-Level Induction and Abstract-Level Structure Learning
Authors: Edmonds Mark , Ma Xiaojian , Qi Siyuan , Zhu Yixin , Lu Hongjing , Zhu Song-Chun
Published: June 2020

Learning transferable knowledge across similar but different settings is a fundamental component of generalized intelligence. In this paper, we approach the transfer learning challenge from a causal theory perspective. Our agent is endowed with two basic yet general theories for transfer learning: (i) a task shares a common abstract structure that is invariant across domains, and (ii) the behavior of specific features of the environment remain constant across domains. We adopt a Bayesian perspective of causal theory induction and use these theories to transfer knowledge between environments. Given these general theories, the goal is to train an agent by interactively exploring the problem space to (i) discover, form, and transfer useful abstract and structural knowledge, and (ii) induce useful knowledge from the instance-level attributes observed in the environment. A hierarchy of Bayesian structures is used to model abstract-level structural causal knowledge, and an instance-level associative learning scheme learns which specific objects can be used to induce state changes through interaction. This model-learning scheme is then integrated with a model-based planner to achieve a task in the OpenLock environment, a virtual “escape room” with a complex hierarchy that requires agents to reason about an abstract, generalized causal structure. We compare performances against a set of predominate model-free reinforcement learning (RL) algorithms. RL agents showed poor ability transferring learned knowledge across different trials. Whereas the proposed model revealed similar performance trends as human learners, and more importantly, demonstrated transfer behavior across trials and learning situations.1
Transfer Reinforcement Learning Using Output-Gated Working Memory
Authors: Williams Arthur , Phillips Joshua
Published: June 2020

Transfer learning allows for knowledge to generalize across tasks, resulting in increased learning speed and/or performance. These tasks must have commonalities that allow for knowledge to be transferred. The main goal of transfer learning in the reinforcement learning domain is to train and learn on one or more source tasks in order to learn a target task that exhibits better performance than if transfer was not used (Taylor and Stone 2009). Furthermore, the use of output-gated neural network models of working memory has been shown to increase generalization for supervised learning tasks (Kriete and Noelle 2011; Kriete et al. 2013). We propose that working memory-based generalization plays a significant role in a model's ability to transfer knowledge successfully across tasks. Thus, we extended the Holographic Working Memory Toolkit (HWMtk) (Dubois and Phillips 2017; Phillips and Noelle 2005) to utilize the generalization benefits of output gating within a working memory system. Finally, the model's utility was tested on a temporally extended, partially observable 5x5 2D grid-world maze task that required the agent to learn 3 tasks over the duration of the training period. The results indicate that the addition of output gating increases the initial learning performance of an agent in target tasks and decreases the learning time required to reach a fixed performance threshold.
Representative Solutions for Bi-Objective Optimisation
Authors: Demirovi? Emir , Schwind Nicolas
Published: June 2020

Bi-objective optimisation aims to optimise two generally competing objective functions. Typically, it consists in computing the set of nondominated solutions, called the Pareto front. This raises two issues: 1) time complexity, as the Pareto front in general can be infinite for continuous problems and exponentially large for discrete problems, and 2) lack of decisiveness. This paper focusses on the computation of a small, “relevant” subset of the Pareto front called the representative set, which provides meaningful trade-offs between the two objectives. We introduce a procedure which, given a pre-computed Pareto front, computes a representative set in polynomial time, and then we show how to adapt it to the case where the Pareto front is not provided. This has three important consequences for computing the representative set: 1) does not require the whole Pareto front to be provided explicitly, 2) can be done in polynomial time for bi-objective mixed-integer linear programs, and 3) only requires a polynomial number of solver calls for bi-objective problems, as opposed to the case where a higher number of objectives is involved. We implement our algorithm and empirically illustrate the efficiency on two families of benchmarks.
Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources
Authors: Godet Arthur , Lorca Xavier , Hebrard Emmanuel , Simonin Gilles
Published: June 2020

In this paper, we consider the Parallel Machine Scheduling Problem with Additional Unit Resources, which consists in scheduling a set of n jobs on m parallel unrelated machines and subject to exactly one of r unit resources. This problem arises from the download of acquisitions from satellites to ground stations. We first introduce two baseline constraint models for this problem. Then, we build on an approximation algorithm for this problem, and we discuss about the efficiency of designing an improved constraint model based on these approximation results. In particular, we introduce new constraints that restrict search to executions of the approximation algorithm. Finally, we report experimental data demonstrating that this model significantly outperforms the two reference models.
SPAN: A Stochastic Projected Approximate Newton Method
Authors: Huang Xunpeng , Liang Xianfeng , Liu Zhengyang , Li Lei , Yu Yue , Li Yitan
Published: June 2020

Second-order optimization methods have desirable convergence properties. However, the exact Newton method requires expensive computation for the Hessian and its inverse. In this paper, we propose SPAN, a novel approximate and fast Newton method. SPAN computes the inverse of the Hessian matrix via low-rank approximation and stochastic Hessian-vector products. Our experiments on multiple benchmark datasets demonstrate that SPAN outperforms existing first-order and second-order optimization methods in terms of the convergence wall-clock time. Furthermore, we provide a theoretical analysis of the per-iteration complexity, the approximation error, and the convergence rate. Both the theoretical analysis and experimental results show that our proposed method achieves a better trade-off between the convergence rate and the per-iteration efficiency.
Modelling Diversity of Solutions
Authors: Ingmar Linnea , Garcia de la Banda Maria , Stuckey Peter J. , Tack Guido
Published: June 2020

For many combinatorial problems, finding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single “best solution” and, thus, it is useful to find a representation of the non-dominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in finding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simplified in the model. This paper describes a general framework for finding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.
Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining
Authors: Li Hongbo , Lee Jimmy , Mi He , Yin Minghao
Published: June 2020

Making good decisions at the top of a search tree is important for finding good solutions early in constraint optimization. In this paper, we propose a method employing frequent pattern mining (FPM), a classic datamining technique, to find good subtrees for solving constraint optimization problems. We demonstrate that applying FPM in a small number of random high-quality feasible solutions enables us to identify subtrees containing optimal solutions in more than 55% of problem instances for four real world benchmark problems. The method works as a plugin that can be combined with any search strategy for branch-and-bound search. Exploring the identified subtrees first, the method brings substantial improvements for four efficient search strategies in both total runtime and runtime of finding optimal solutions.
Grammar Filtering for Syntax-Guided Synthesis
Authors: Morton Kairo , Hallahan William , Shum Elven , Piskac Ruzica , Santolucito Mark
Published: June 2020

Programming-by-example (PBE) is a synthesis paradigm that allows users to generate functions by simply providing input-output examples. While a promising interaction paradigm, synthesis is still too slow for realtime interaction and more widespread adoption. Existing approaches to PBE synthesis have used automated reasoning tools, such as SMT solvers, as well as works applying machine learning techniques. At its core, the automated reasoning approach relies on highly domain specific knowledge of programming languages. On the other hand, the machine learning approaches utilize the fact that when working with program code, it is possible to generate arbitrarily large training datasets. In this work, we propose a system for using machine learning in tandem with automated reasoning techniques to solve Syntax Guided Synthesis (SyGuS) style PBE problems. By preprocessing SyGuS PBE problems with a neural network, we can use a data driven approach to reduce the size of the search space, then allow automated reasoning-based solvers to more quickly find a solution analytically. Our system is able to run atop existing SyGuS PBE synthesis tools, decreasing the runtime of the winner of the 2019 SyGuS Competition for the PBE Strings track by 47.65% to outperform all of the competing tools.
D-SPIDER-SFO: A Decentralized Optimization Algorithm with Faster Convergence Rate for Nonconvex Problems
Authors: Pan Taoxing , Liu Jun , Wang Jie
Published: June 2020

Decentralized optimization algorithms have attracted intensive interests recently, as it has a balanced communication pattern, especially when solving large-scale machine learning problems. Stochastic Path Integrated Differential Estimator Stochastic First-Order method (SPIDER-SFO) nearly achieves the algorithmic lower bound in certain regimes for nonconvex problems. However, whether we can find a decentralized algorithm which achieves a similar convergence rate to SPIDER-SFO is still unclear. To tackle this problem, we propose a decentralized variant of SPIDER-SFO, called decentralized SPIDER-SFO (D-SPIDER-SFO). We show that D-SPIDER-SFO achieves a similar gradient computation cost—that is, O(ε−3) for finding an ϵ-approximate first-order stationary point—to its centralized counterpart. To the best of our knowledge, D-SPIDER-SFO achieves the state-of-the-art performance for solving nonconvex optimization problems on decentralized networks in terms of the computational cost. Experiments on different network configurations demonstrate the efficiency of the proposed method.
Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination
Authors: Amanatidis Georgios , Markakis Evangelos , Ntokos Apostolos
Published: June 2020

Several relaxations of envy-freeness, tailored to fair division in settings with indivisible goods, have been introduced within the last decade. Due to the lack of general existence results for most of these concepts, great attention has been paid to establishing approximation guarantees. In this work, we propose a simple algorithm that is universally fair in the sense that it returns allocations that have good approximation guarantees with respect to four such fairness notions at once. In particular, this is the first algorithm achieving a (φ−1)-approximation of envy-freeness up to any good (EFX) and a 2/φ+2 -approximation of groupwise maximin share fairness (GMMS), where φ is the golden ratio. The best known approximation factor, in polynomial time, for either one of these fairness notions prior to this work was 1/2. Moreover, the returned allocation achieves envy-freeness up to one good (EF1) and a 2/3-approximation of pairwise maximin share fairness (PMMS). While EFX is our primary focus, we also exhibit how to fine-tune our algorithm and improve further the guarantees for GMMS or PMMS.Finally, we show that GMMS—and thus PMMS and EFX—allocations always exist when the number of goods does not exceed the number of agents by more than two.
Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives
Authors: Aziz Haris , Chan Hau , Lee Barton , Li Bo , Walsh Toby
Published: June 2020

We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, we prove that the corresponding optimization problem, where the goal is to locate facilities to minimize either the total cost to all agents or the maximum cost of any agent is NP-hard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilities have identical capacities. We then consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that several natural mechanisms studied in the uncapacitated setting either lose strategyproofness or a bound on the solution quality %on the returned solution for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.
Electing Successive Committees: Complexity and Algorithms
Authors: Bredereck Robert , Kaczmarczyk Andrzej , Niedermeier Rolf
Published: June 2020

We introduce successive committees elections. The point is that our new model additionally takes into account that “committee members” shall have a short term of office possibly over a consecutive time period (e.g., to limit the influence of elitist power cartels or to keep the social costs of overloading committees as small as possible) but at the same time overly frequent elections are to be avoided (e.g., for the sake of long-term planning). Thus, given voter preferences over a set of candidates, a desired committee size, a number of committees to be elected, and an upper bound on the number of committees that each candidate can participate in, the goal is to find a “best possible” series of committees representing the electorate. We show a sharp complexity dichotomy between computing series of committees of size at most two (mostly in polynomial time) and of committees of size at least three (mostly NP-hard). Depending on the voting rule, however, even for larger committee sizes we can spot some tractable cases.
Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem
Authors: Gilbert Hugo , Portoleau Tom , Spanjaard Olivier
Published: June 2020

In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. It reveals useful to divide the aggregation problem into several sub-problems. We conclude with numerical tests.
The Complexity of Computing Maximin Share Allocations on Graphs
Authors: Greco Gianluigi , Scarcello Francesco
Published: June 2020

Maximin share is a compelling notion of fairness proposed by Buddish as a relaxation of more traditional concepts for fair allocations of indivisible goods. In this paper we consider this notion within a setting where bundles of goods must induce connected subsets over an underlying graph. This setting received much attention in earlier literature, and our study answers a number of questions that were left open. First, we show that computing maximin share allocations is FΔ2P-complete, even when focusing on consistent scenarios, that is, where such allocations are a-priori guaranteed to exist. Moreover, the problem remains intractable if all agents have the same type, i.e., have the same utility functions, and if either the values returned by the utility functions are polynomially bounded, or the underlying graphs have a low degree of cyclicity (more precisely, have bounded treewidth). However, if these conditions hold all together, then computing maximin share allocations (or checking that none exists) becomes tractable. The result is established via machineries based on logspace alternating machines that use partial representations of connected bundles, which are interesting in their own.
Repeated Multimarket Contact with Private Monitoring: A Belief-Free Approach
Authors: Iwasaki Atsushi , Sekiguchi Tadashi , Yamamoto Shun , Yokoo Makoto
Published: June 2020

This paper studies repeated games where two players play multiple duopolistic games simultaneously (multimarket contact). A key assumption is that each player receives a noisy and private signal about the other's actions (private monitoring or observation errors). There has been no game-theoretic support that multimarket contact facilitates collusion or not, in the sense that more collusive equilibria in terms of per-market profits exist than those under a benchmark case of one market. An equilibrium candidate under the benchmark case is belief-free strategies. We are the first to construct a non-trivial class of strategies that exhibits the effect of multimarket contact from the perspectives of simplicity and mild punishment. Strategies must be simple because firms in a cartel must coordinate each other with no communication. Punishment must be mild to an extent that it does not hurt even the minimum required profits in the cartel. We thus focus on two-state automaton strategies such that the players are cooperative in at least one market even when he or she punishes a traitor. Furthermore, we identify an additional condition (partial indifference), under which the collusive equilibrium yields the optimal payoff.
Lifting Preferences over Alternatives to Preferences over Sets of Alternatives: The Complexity of Recognizing Desirable Families of Sets
Authors: Maly Jan
Published: June 2020

The problem of lifting a preference order on a set of objects to a preference order on a family of subsets of this set is a fundamental problem with a wide variety of applications in AI. The process is often guided by axioms postulating properties the lifted order should have. Well-known impossibility results by Kannai and Peleg and by Barberà and Pattanaik tell us that some desirable axioms – namely dominance and (strict) independence – are not jointly satisfiable for any linear order on the objects if all non-empty sets of objects are to be ordered. On the other hand, if not all non-empty sets of objects are to be ordered, the axioms are jointly satisfiable for all linear orders on the objects for some families of sets. Such families are very important for applications as they allow for the use of lifted orders, for example, in combinatorial voting. In this paper, we determine the computational complexity of recognizing such families. We show that it is Π2p-complete to decide for a given family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for all linear orders on the objects if the lifted order needs to be total. Furthermore, we show that the problem remains coNP-complete if the lifted order can be incomplete. Additionally, we show that the complexity of these problem can increase exponentially if the family of sets is not given explicitly but via a succinct domain restriction.
The Surprising Power of Hiding Information in Facility Location
Authors: Hossain Safwan , Micha Evi , Shah Nisarg
Published: June 2020

Facility location is the problem of locating a public facility based on the preferences of multiple agents. In the classic framework, where each agent holds a single location on a line and can misreport it, strategyproof mechanisms for choosing the location of the facility are well-understood.We revisit this problem in a more general framework. We assume that each agent may hold several locations on the line with different degrees of importance to the agent. We study mechanisms which elicit the locations of the agents and different levels of information about their importance. Further, in addition to the classic manipulation of misreporting locations, we introduce and study a new manipulation, whereby agents may hide some of their locations. We argue for its novelty in facility location and applicability in practice. Our results provide a complete picture of the power of strategyproof mechanisms eliciting different levels of information and with respect to each type of manipulation. Surprisingly, we show that in some cases hiding locations can be a strictly more powerful manipulation than misreporting locations.
Can We Predict the Election Outcome from Sampled Votes?
Authors: Micha Evi , Shah Nisarg
Published: June 2020

In the standard model of voting, it is assumed that a voting rule observes the ranked preferences of each individual over a set of alternatives and makes a collective decision. In practice, however, not every individual votes. Is it possible to make a good collective decision for a group given the preferences of only a few of its members? We propose a framework in which we are given the ranked preferences of k out of n individuals sampled from a distribution, and the goal is to predict what a given voting rule would output if applied on the underlying preferences of all n individuals. We focus on the family of positional scoring rules, derive a strong negative result when the underlying preferences can be arbitrary, and discover interesting phenomena when they are generated from a known distribution.
Solving Online Threat Screening Games using Constrained Action Space Reinforcement Learning
Authors: Sanket Shah , Sinha Arunesh , Varakantham Pradeep , Andrew Perrault , Tambe Milind
Published: June 2020

Large-scale screening for potential threats with limited resources and capacity for screening is a problem of interest at airports, seaports, and other ports of entry. Adversaries can observe screening procedures and arrive at a time when there will be gaps in screening due to limited resource capacities. To capture this game between ports and adversaries, this problem has been previously represented as a Stackelberg game, referred to as a Threat Screening Game (TSG). Given the significant complexity associated with solving TSGs and uncertainty in arrivals of customers, existing work has assumed that screenees arrive and are allocated security resources at the beginning of the time-window. In practice, screenees such as airport passengers arrive in bursts correlated with flight time and are not bound by fixed time-windows. To address this, we propose an online threat screening model in which the screening strategy is determined adaptively as a passenger arrives while satisfying a hard bound on acceptable risk of not screening a threat. To solve the online problem, we first reformulate it as a Markov Decision Process (MDP) in which the hard bound on risk translates to a constraint on the action space and then solve the resultant MDP using Deep Reinforcement Learning (DRL). To this end, we provide a novel way to efficiently enforce linear inequality constraints on the action output in DRL. We show that our solution allows us to significantly reduce screenee wait time without compromising on the risk.
Path Planning Problems with Side Observations—When Colonels Play Hide-and-Seek
Authors: Vu Dong Quan , Loiseau Patrick , Silva Alonso , Tran-Thanh Long
Published: June 2020

Resource allocation games such as the famous Colonel Blotto (CB) and Hide-and-Seek (HS) games are often used to model a large variety of practical problems, but only in their one-shot versions. Indeed, due to their extremely large strategy space, it remains an open question how one can efficiently learn in these games. In this work, we show that the online CB and HS games can be cast as path planning problems with side-observations (SOPPP): at each stage, a learner chooses a path on a directed acyclic graph and suffers the sum of losses that are adversarially assigned to the corresponding edges; and she then receives semi-bandit feedback with side-observations (i.e., she observes the losses on the chosen edges plus some others). We propose a novel algorithm, Exp3-OE, the first-of-its-kind with guaranteed efficient running time for SOPPP without requiring any auxiliary oracle. We provide an expected-regret bound of Exp3-OE in SOPPP matching the order of the best benchmark in the literature. Moreover, we introduce additional assumptions on the observability model under which we can further improve the regret bounds of Exp3-OE. We illustrate the benefit of using Exp3-OE in SOPPP by applying it to the online CB and HS games.
Computing Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games
Authors: Zhang Youzhi , An Bo
Published: June 2020

The study of finding the equilibrium for multiplayer games is challenging. This paper focuses on computing Team-Maxmin Equilibria (TMEs) in zero-sum multiplayer Extensive-Form Games (EFGs), which describes the optimal strategies for a team of players who share the same goal but they take actions independently against an adversary. TMEs can capture many realistic scenarios, including: 1) a team of players play against a target player in poker games; and 2) defense resources schedule and patrol independently in security games. However, the study of efficiently finding TMEs within any given accuracy in EFGs is almost completely unexplored. To fill this gap, we first study the inefficiency caused by computing the equilibrium where team players correlate their strategies and then transforming it into the mixed strategy profile of the team and show that this inefficiency can be arbitrarily large. Second, to efficiently solve the non-convex program for finding TMEs directly, we develop the Associated Recursive Asynchronous Multiparametric Disaggregation Technique (ARAMDT) to approximate multilinear terms in the program with two novel techniques: 1) an asynchronous precision method to reduce the number of constraints and variables for approximation by using different precision levels to approximate these terms; and 2) an associated constraint method to reduce the feasible solution space of the mixed-integer linear program resulting from ARAMDT by exploiting the relation between these terms. Third, we develop a novel iterative algorithm to efficiently compute TMEs within any given accuracy based on ARAMDT. Our algorithm is orders of magnitude faster than baselines in the experimental evaluation.
An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems
Authors: Benabbou Nawal , Leroy Cassandre , Lust Thibaut
Published: June 2020

We propose a new approach consisting in combining genetic algorithms and regret-based incremental preference elicitation for solving multi-objective combinatorial optimization problems with unknown preferences. For the purpose of elicitation, we assume that the decision maker's preferences can be represented by a parameterized scalarizing function but the parameters are initially not known. Instead, the parameter imprecision is progressively reduced by asking preference queries to the decision maker during the search to help identify the best solutions within a population. Our algorithm, called RIGA, can be applied to any multi-objective combinatorial optimization problem provided that the scalarizing function is linear in its parameters and that a (near-)optimal solution can be efficiently determined when preferences are known. Moreover, RIGA runs in polynomial time while asking no more than a polynomial number of queries. For the multi-objective traveling salesman problem, we provide numerical results showing its practical efficiency in terms of number of queries, computation time and gap to optimality.
Expectation-Aware Planning: A Unifying Framework for Synthesizing and Executing Self-Explaining Plans for Human-Aware Planning
Authors: Sreedharan Sarath , Chakraborti Tathagata , Muise Christian , Kambhampati Subbarao
Published: June 2020

In this work, we present a new planning formalism called Expectation-Aware planning for decision making with humans in the loop where the human's expectations about an agent may differ from the agent's own model. We show how this formulation allows agents to not only leverage existing strategies for handling model differences like explanations (Chakraborti et al. 2017) and explicability (Kulkarni et al. 2019), but can also exhibit novel behaviors that are generated through the combination of these different strategies. Our formulation also reveals a deep connection to existing approaches in epistemic planning. Specifically, we show how we can leverage classical planning compilations for epistemic planning to solve Expectation-Aware planning problems. To the best of our knowledge, the proposed formulation is the first complete solution to planning with diverging user expectations that is amenable to a classical planning compilation while successfully combining previous works on explanation and explicability. We empirically show how our approach provides a computational advantage over our earlier approaches that rely on search in the space of models.
Conditional Generative Neural Decoding with Structured CNN Feature Prediction
Authors: Du Changde , Du Changying , Huang Lijie , He Huiguang
Published: June 2020

Decoding visual contents from human brain activity is a challenging task with great scientific value. Two main facts that hinder existing methods from producing satisfactory results are 1) typically small paired training data; 2) under-exploitation of the structural information underlying the data. In this paper, we present a novel conditional deep generative neural decoding approach with structured intermediate feature prediction. Specifically, our approach first decodes the brain activity to the multilayer intermediate features of a pretrained convolutional neural network (CNN) with a structured multi-output regression (SMR) model, and then inverts the decoded CNN features to the visual images with an introspective conditional generation (ICG) model. The proposed SMR model can simultaneously leverage the covariance structures underlying the brain activities, the CNN features and the prediction tasks to improve the decoding accuracy and interpretability. Further, our ICG model can 1) leverage abundant unpaired images to augment the training data; 2) self-evaluate the quality of its conditionally generated images; and 3) adversarially improve itself without extra discriminator. Experimental results show that our approach yields state-of-the-art visual reconstructions from brain activities.
Variational Pathway Reasoning for EEG Emotion Recognition
Authors: Zhang Tong , Cui Zhen , Xu Chunyan , Zheng Wenming , Yang Jian
Published: June 2020

Research on human emotion cognition revealed that connections and pathways exist between spatially-adjacent and functional-related areas during emotion expression (Adolphs 2002a; Bullmore and Sporns 2009). Deeply inspired by this mechanism, we propose a heuristic Variational Pathway Reasoning (VPR) method to deal with EEG-based emotion recognition. We introduce random walk to generate a large number of candidate pathways along electrodes. To encode each pathway, the dynamic sequence model is further used to learn between-electrode dependencies. The encoded pathways around each electrode are aggregated to produce a pseudo maximum-energy pathway, which consists of the most important pair-wise connections. To find those most salient connections, we propose a sparse variational scaling (SVS) module to learn scaling factors of pseudo pathways by using the Bayesian probabilistic process and sparsity constraint, where the former endows good generalization ability while the latter favors adaptive pathway selection. Finally, the salient pathways from those candidates are jointly decided by the pseudo pathways and scaling factors. Extensive experiments on EEG emotion recognition demonstrate that the proposed VPR is superior to those state-of-the-art methods, and could find some interesting pathways w.r.t. different emotions.
Query Rewriting for Ontology-Mediated Conditional Answers
Authors: Andresel Medina , Ortiz Magdalena , Simkus Mantas
Published: June 2020

Among many solutions for extracting useful answers from incomplete data, ontology-mediated queries (OMQs) use domain knowledge to infer missing facts. We propose an extension of OMQs that allows us to make certain assumptions—for example, about parts of the data that may be unavailable at query time, or costly to query—and retrieve conditional answers, that is, tuples that become certain query answers when the assumptions hold. We show that querying in this powerful formalism often has no higher worst-case complexity than in plain OMQs, and that these queries are first-order rewritable for DL-Liteℛ. Rewritability is preserved even if we allow some use of closed predicates to combine the (partial) closed- and open-world assumptions. This is remarkable, as closed predicates are a very useful extension of OMQs, but they usually make query answering intractable in data complexity, even in very restricted settings.