Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

An investigation into regional differences in educational performance in the National Child Development Study

The National Child Development Study (NCDS) is used to investigate factors which affect children's educational performance over time. Multilevel modelling techniques are used on a subset of the NCDS to investigate variation in educational performance in 11 regions in the UK, and in local education authorities within these regions. Social characteristics of the NCDS members are also analysed. Differences between regions and education authorities are found to be negligible, the main source of variation in achievement being due to differences in social background.

An analysis of masculine and feminine writings in postings within a series of health and social care online undergraduate courses

This study aims to extend understanding of pedagogic dialogue by analysing the effect that the gender of the student has on interaction within a selection of ordinary health and social care on line courses.

Making sense of game based user data: learning analytics in applied games

Digital learning games are useful educational tools with high motivational potential. With the application of games for instruction there comes the need of acknowledging learning game experiences also in the context of educational assessment. Learning analytics provides new opportunities for supporting assessment in and of educational games. We give an overview of current learning analytics methods in this field and reflect on existing challenges. An approach of providing reusable software assets for interaction assessment and evaluation in games is presented. This is part of a broader initiative of making available advanced methodologies and tools for supporting applied game development.

Amplifying applied game development and uptake

The established (digital) leisure game industry is historically one dominated by large international hardware vendors (e.g. Sony, Microsoft and Nintendo), major publishers and supported by a complex network of development studios, distributors and retailers. New modes of digital distribution and development practice are challenging this business model and the leisure games industry landscape is one experiencing rapid change. The established (digital) leisure games industry, at least anecdotally, appears reluctant to participate actively in the applied games sector (Stewart et al., 2013). There are a number of potential explanations as to why this may indeed be the case including ; A concentration on large-scale consolidation of their (proprietary) platforms, content, entertainment brand and credibility which arguably could be weakened by association with the conflicting notion of purposefulness (in applied games) in market niches without clear business models or quantifiable returns on investment. In contrast, the applied games industry exhibits the characteristics of an emerging, immature industry namely: weak interconnectedness, limited knowledge exchange, an absence of harmonising standards, limited specialisations, limited division of labour and arguably insufficient evidence of the products efficacies (Stewart et al., 2013; Garcia Sanchez, 2013) and could, arguably, be characterised as a dysfunctional market. To test these assertions the Realising an Applied Gaming Ecosystem (RAGE) project will develop a number of self contained gaming assets to be actively employed in the creation of a number of applied games to be implemented and evaluated as regional pilots across a variety of European educational, training and vocational contexts. RAGE is a European Commission Horizon 2020 project with twenty (pan European) partners from industry, research and education with the aim of developing, transforming and enriching advanced technologies from the leisure games industry into self-contained gaming assets (i.e. solutions showing economic value potential) that could support a variety of stakeholders including teachers, students, and, significantly, game studios interested in developing applied games. RAGE will provide these assets together with a large quantity of high-quality knowledge resources through a self-sustainable Ecosystem, a social space that connects research, the gaming industries, intermediaries, education providers, policy makers and end-users in order to stimulate the development and application of applied games in educational, training and vocational contexts. The authors identify barriers (real and perceived) and opportunities facing stakeholders in engaging, exploring new emergent business models ,developing, establishing and sustaining an applied gaming eco system in Europe.

Chapter 2: Predicting Newcomer Integration in Online Knowledge Communities by Automated Dialog Analysis

Nistor, N., Dascalu, M., Stavarache, L.L., Tarnai, C., & Trausan-Matu, S. (2015). Predicting Newcomer Integration in Online Knowledge Communities by Automated Dialog Analysis. In Y. Li, M. Chang, M. Kravcik, E. Popescu, R. Huang, Kinshuk & N.-S. Chen (Eds.), State-of-the-Art and Future Directions of Smart Learning (Vol. Lecture Notes in Educational Technology, pp. 13–17). Berlin, Germany: Springer-Verlag Singapur

Professional Educational Psychology and Community Relations Education in Northern Ireland.

This article provides an account of practice-based research of, at least, one-star quality in terms of its contribution to both theory and practice. Aimed at practitioner (as opposed to academic) psychologists, the article addresses a dimension of the practitioner role that has remained silent in the literature. The article makes creative and original connections between school effectiveness, school improvement and education in a divided society. Post 11th September, the article was described as being highly original, significant and relevant to all practising educational psychologists. Concrete evidence for this is gained from, eg: hits on the online electronic version (2002-2003 Annual Report of the Association of Educational Psychologists), citations in reviews of research, and author invitations to present his work at UK and international practitioner psychology conferences. The article is published in the premier journal reporting on quality applied educational research and practice within the United Kingdom and beyond.

Math-Towers: Promoting and supporting online collaborative mathematical exploration

Math-Towers (www.math-towers.ca) is a collaborative mathematics environment for pupils in grades 7 to 9. Using a fantasy adventure game context students are presented with a mathematical challenge, given online tools for working on the problem,and provided with a messaging system by which they may exchange ideas and partial solutions. This paper presents the philosophy behind the design of Math-Towers and work with students that indicates the extent to which we have been successful in meeting our aims. The technical and social problems encountered and revisions made to address these are also described.

Math-Towers: Online Interactive Collaborative Mathematics Explorations & Problem-Solving for Students Ages 11 to 15 years (Grades 6 to 10)

Math-Towers (www.math-towers.ca) is an online resource for students in grades 6 to 10 that supports collaborative problem-solving and investigations. This paper presents the philosophical position motivating the development of Math-Towers and describes how the site presents and motivates the mathematical challenges and supports participants' exploration and collaboration.

Predictors of attitudes toward inclusion of students with special educational needs in future education professionals

One of the main pillars in the development of inclusive schools is the initial teacher training. Before determining if it is necessary to make changes (and of what type) in training programs or curriculum guides related to the attention to diversity and inclusive education, the attitudes of future education professionals in this area should be analyzed. This includes the identification of the relevant predictors of inclusive attitudes. The research reported in this article pursued this objective, doing so with a quantitative survey methodology based on the use of cross-sectional structured data collection and statistical analyses related to the quality of the attitude questionnaire (factor analysis and Cronbach's alpha), descriptive statistics, correlations, hypothesis tests for difference of means, and regression analysis in order to predict attitudes towards inclusion in education. Firstly, the results show that the participants held very positive attitudes toward the inclusion of students with special educational needs. Particularly, older respondents, those with a longer training and, to a lesser extent, women and those who had been in touch with disabled people stood out within this attitude. Secondly, it is evidenced that self-transcendence values ​and, more weakly, contact, function as robust predictors of attitudes of future practitioners towards the inclusion of students with special needs. Some applications for the initial professionalization of educators are suggested in the discussion.

Video games in the classrooms: implications of a disruptive innovation to develop the Multiple Intelligences

The present study aims to identify the framework of personal, organizational and technical variables that contribute to the viability and successful of innovative educational practices with video games within the school context to enhance the multiple intelligences. For this purpose, advantage was taken on the information previously collected through a questionnaire about the views, thoughts and experiences of a group of teachers of childhood and primary education (N=25) who voluntarily participated in a blended training activity from Center of Teachers (CEFIRE) of Valencia, around a community of practice aimed at promoting and advising projects for implementing educational video games in the classroom. The mixed methodology adopted has allowed the following: a) describe the relationship between their degree of development and daily use made of ICT in the classroom, their level of familiarity with video games,  their previous experience to integrate them for educational purposes..., and their participation in projects that focus on game-based learning; b) conduct content analysis of the opinions and thoughts expressed in a forum for teachers on innovation on and methodological strategies adopted reflected in a virtual board; and c) develop a SWOT analysis: Strengths, Weaknesses, Opportunities and Threats inherent in the implementation of experience with video games in the classroom. Among the conclusions, it is highlighted that, even though most did not have specific training or enough technological resources and the planning and implementation of innovation required them a great investment of time, their personal interest, the support given by members of the online community of practice, helped to encourage their activity, along with receptivity, positive attitude and high motivation of students with the experience. These aspects have been crucial to promote successful innovative practices with video games.

Pupil participation in school life: an approach from the educational community

The Convention on the Rights of the Child (CRC, 1989) is currently the most ratified international treaty. Several authors have highlighted its potential for both a moral education and citizenship. However, paradoxically, different studies report its limited or occasional incorporation into school practices. This article explores experiences of participation in schools,the third P of the CRC, from the plurality of voices and actors of the educational community,by means of 14 discussion groups in 11 autonomous communities in Spain. Discourse analysis evidence low levels of student participation in school life. But, at the same time, a favorable educational environment for the development of projects that contribute to child participation is found, as well as for the incorporation of the CRC as a mover and a referential integrator of the different schools projects. However, it is also an educational background conductive to projects for its development, such as the incorporation of the CRC as a referential integrator of the schools projects.

Study of the images for the Visual Arts Education in Secondary Education textbooks: educational implications

In this paper we present the first data from the research conducted to determine the relationship between traditional visual arts and other forms of visual culture closer to the experiences of high school youth. The hypothesis of this research is that while students are nurtured and live primarily with the images provided by the media culture, their textbooks basically refer to the more traditional art images. The research has been limited to a review and analysis of the most common educational materials for teaching visual arts in high school. After the systematization and analysis of the images appeared in textbooks, we have detected three major types: the artistics, those who belong to media culture and others. The most relevant conclusions indicate that: there are hardly any connections between different types of images, they offer a very traditional view of art and they are far removed from the experiences of young book users.

Taiwanese Learners’ Motivation and Attitude Towards Completing an Online Distance Education Course During a One Year Industrial Placement

This mixed methods study investigated language learning motivation in an one-year e-learning course for technological university students to bridge the geographical divide between students on industrial placements when studying graded readers using an e-learning course to improve their English competence and to pass the General English Proficiency Test. Data was collected through questionnaires and course feedback. The results of this study extend Gardner’s socio-educational model in an e-learning environment by adding the new category, Computer Attitudes, which was proven to be highly correlated with Motivation. Although the low proficiency English students had good computer skills, their habits of using the computer for entertainment and their lack of the skill of “technological communication efficacy” caused increased anxiety when using computers and thus provided them with a lower computer confidence over time. Consequently, it is recommended that sound e-learning training should be provided to all of the students prior to embarking on an e-leaning course so that these learners can benefit from online language learning in the future.