No description available.

Sample average approximation (SAA) is a well-known solution methodology for traditional stochastic programs which are risk neutral in the sense that they consider optimization of expectation functionals. In this thesis we establish sample average approximation methods for two classes of non-traditional stochastic programs. The first class is that of stochastic min-max programs, i.e., min-max problems with expected value objectives, and the second class is that of expected value constrained stochastic programs. We specialize these SAA methods for risk-averse stochastic problems with a bi-criteria objective involving mean and mean absolute deviation, and those with constraints on conditional value-at-risk. For the proposed SAA methods, we prove that the results of the SAA problem converge exponentially fast to their counterparts for the true problem as the sample size increases. We also propose implementation schemes which return not only candidate solutions but also statistical upper and lower bound estimates on the optimal value of the true problem. We apply the proposed methods to solve portfolio selection and supply chain network design problems. Our computational results reflect good performance of the proposed SAA schemes. We also investigate the effect of various types of risk-averse stochastic programming models in controlling risk in these problems.

No description available.

This paper studies if the Minimax theorem holds for the behaviour of trained and untrained actors in the field. This is explored with data from 1043 football penalty kicks from professionals of the German Bundesliga and for 268 penalty kicks from untrained players. Minimax makes good predictions about the collective patterns emerging from the behaviour of experienced actors, as well as about their individual strategic actions. However, this is not true for untrained actors. In the next step it is explored if, the professional players learned their behaviour, or if they were selected into their roles because they had the required abilities. The data suggests that the professionals were selected by the competitive conditions of professional sports.

No description available.

Cette thèse est consacrée à l’étude des interactions entre la théorie des jeux et la théorie de l’information, ainsi qu’à leurs applications aux réseaux de communication décentralisés. D’une part, la théorie des jeux apporte des réponses aux problèmes d’optimisation dans lesquels des agents interagissent. Dans un jeu, les joueurs choisissent des actions et obtiennent des gains appelés utilités. Les hypothèses sur l’information que possèdent les joueurs avant de jouer sont fondamentales pour déterminer l’issue d’un jeu, aussi appelée équilibre. Lorsque le même jeu est répété d’étape en étape et que les joueurs n’observent pas les actions passées parfaitement,alors les utilités d’équilibre ne sont pas connues. D’autre part, la théorie de l’information étudie les performances d’un système communicant. De nos jours, les réseaux de communication sont tellement denses qu’ils ne peuvent plus s’organiser autour d’un unique opérateur central. La théorie des jeux est appropriée pour étudier de nouvelles organisations du traitement de l’information dans lesquelles les décisions sont prises localement. Dans un premier temps, au chapitre3, nous étudions le jeu du contrôle de puissance efficace du point de vue énergétique, grâce aux résultats existants pour les jeux répétés. Les émetteurs sont considérés comme des joueurs et choisissent la puissance d’émission du signal, considérée comme leur action. L’objectif d’un joueur est de choisir une puissance optimale pour la qualité de sa propre communication. Même si les joueurs n’observent pas les actions passées de manière parfaite, nous montrons que l’observation du "ratio signal sur interférence plus bruit" est suffisante pour garantir des résultats d’équilibre optimaux pour le réseau de communication. Dans un second temps, nous utilisons les outils de la théorie de l’information pour approfondir l’étude de la circulation de l’information parmi les joueurs. Dans le chapitre 4, un encodeur envoie un signal supplémentaire aux joueurs afin qu’ils observent parfaitement les actions jouées à l’étape précédente. L’observation des joueurs devient suffisamment précise pour nous permettre de retrouver l’ensemble des utilités d’équilibre du jeu répété. Ces résultats sont à leur tour exploités afin de modéliser des réseaux de communication plus réalistes et d’y apporter des solutions nouvelles. Dans le chapitre5, nous approfondissons l’étude des utilités d’équilibre lorsque les joueurs observent les actions passées à travers un canal d’observation arbitraire. Nous démontrons un résultat d’atteignabilité pour un canal multi-utilisateurs avec états qui comporte un encodeur, deux récepteurs légitimes et un espion. Ce résultat nous permet d’étudier les corrélations entre les suites d’actions qu’un groupe de joueurs peut mettre en oeuvre à l’insu d’un joueur opposant. L’étude des canaux multiutilisateurs est un pas en avant vers la caractérisation des utilités d’équilibre dans un jeu répété avec observation imparfaite. / This thesis is devoted to the study of mutual contributions between games theory and informationtheory and their applications to decentralized communication networks. First, game theoryprovides answers to optimization problems in which agents interact. In a game, players chooseactions and obtains gains called utilities. Assumptions about the information possessed by playersbefore play is fundamental to determine the outcome a game, also called equilibrium. When thesame game is repeated from stage to stage and the players do not observe the past actions perfectly,then the equilibrium utilities are not known. On the other hand, information theory studiesthe performance of a communicating system. Nowadays, communication networks are so densethat they can not organize around a single central operator. Game theory is appropriate to explorenew organizations of communication networks in which decisions are taken locally. At first,in Chapter 3, we study the game of power control in terms of energy efficiency, thanks to theexisting results for repeated games. Transmitters are regarded as players and choose the transmissionpower of the signal, considered as their action. The objective of a player is to choose anoptimal power for the quality of its own communication. The players do not observe the pastactions perfectly, but we show that the observation of the "signal over interference plus noiseratio" is sufficient to ensure optimal equilibrium results for the communication network. In a secondstep, we use the tools of the information theory for further study of the flow of informationamong the players. In Chapter 4, an encoder sends an extra signal to the players so that theyperfectly observe the actions chosen in the previous stage-game. The observation of players issufficiently precise to characterize the set of equilibrium utilities of the repeated game. Theseresults are, in turn, used to model new communication networks and to provide more realisticsolutions. In Chapter 5, we deepen the study of equilibrium utilities when players observe thepast actions to through an arbitrary observation channel. We show a rate region is achievablefor the multi-user channel with states which includes an encoder, two legitimate receivers andan eavesdropper. This result allows us to study the correlations over the sequences of actions agroup of players can implement while keeping it secret from an opponent player. The study ofmulti-user channels is a step towards the characterization of equilibrium utilities in a repeatedgame with imperfect monitoring.

This paper studies if the Minimax theorem holds for the behaviour of trained and untrained actors in the field. This is explored with data from 1043 football penalty kicks from professionals of the German Bundesliga and for 268 penalty kicks from untrained players. Minimax makes good predictions about the collective patterns emerging from the behaviour of experienced actors, as well as about their individual strategic actions. However, this is not true for untrained actors. In the next step it is explored if, the professional players learned their behaviour, or if they were selected into their roles because they had the required abilities. The data suggests that the professionals were selected by the competitive conditions of professional sports.

Distributed coordination of multi-agent systems (MASs) has been widely studied in various emerging engineering applications, including connected vehicles, wireless networks, smart grids, and cyber-physical systems. In these contexts, agents make the decision locally, relying on the interaction with their immediate neighbors over the connected communication networks. The study of distributed coordination for the multi-agent system (MAS) with constraints is significant yet challenging, especially in terms of ubiquitous uncertainties, the heavy communication burden, and communication delays, to name a few. Hence, it is desirable to develop distributed algorithms for the constrained MAS with these practical issues. In this dissertation, we develop the theoretical results on robust distributed model predictive control (DMPC) algorithms for two types of control problems (i.e., formation stabilization problem and consensus problem) of the constrained and uncertain MAS and apply robust DMPC algorithms in applications of cooperative marine vehicles. More precisely, Chapter 1 provides a systematic literature review, where the state-of-the-art DMPC for formation stabilization and consensus, robust MPC, and MPC for motion control of marine vehicles are introduced. Chapter 2 introduces some notations, necessary definitions, and some preliminaries. In Chapter 3, we study the formation stabilization problem of the nonlinear constrained MAS with un- certainties and bounded time-varying communication delays. We develop a min-max DMPC algorithm with the self-triggered mechanism, which significantly reduces the communication burden while ensuring closed-loop stability and robustness. Chapter 4 investigates the consensus problem of the general linear MAS with input constraints and bounded time-varying delays. We design a robust DMPC-based consensus protocol that integrates a predesigned consensus protocol with online DMPC optimization techniques. Under mild technical assumptions, the estimation errors propagated over prediction due to delay-induced inaccurate neighboring information are proved bounded, based on which a robust DMPC strategy is deliberately designed to achieve robust consensus while satisfying control input constraints. Chapter 5 proposes a Lyapunov-based DMPC approach for the formation tracking control problem of co-operative autonomous underwater vehicles (AUVs) subject to environmental disturbances. A stability constraint leveraging the extended state observer-based auxiliary control law and the associated Lyapunov function is incorporated into the optimization problem to enforce the stability and enhance formation tracking performance. A collision-avoidance cost is designed and employed in the DMPC optimization problem to further guarantee the safety of AUVs. Chapter 6 presents a tube-based DMPC approach for the platoon control problem of a group of heterogeneous autonomous surface vehicles (ASVs) with input constraints and disturbances. In particular, a coupled inter-vehicle safety constraint is added to the DMPC optimization problem; it ensures that neighboring ASVs maintain the safe distance and avoid inter-vehicle collision. Finally, we summarize the main results of this dissertation and discuss some potential directions for future research in Chapter 7. / Graduate / 2023-04-19

This thesis focuses mainly on the Maximum Independent Set (MIS) problem. Some related graph theoretical combinatorial problems are also considered. As these problems are generally NP-hard, we study their complexity in hereditary graph classes, i.e. graph classes defined by a set F of forbidden induced subgraphs. We revise the literature about the issue, for example complexity results, applications, and techniques tackling the problem. Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution. More specifically, we present polynomial-time algorithms for the MIS problem in: + some subclasses of $S_{2;j;k}$-free graphs (thus generalizing the classical result for $S_{1;2;k}$-free graphs); + some subclasses of $tree_{k}$-free graphs (thus generalizing the classical results for subclasses of P5-free graphs); + some subclasses of $P_{7}$-free graphs and $S_{2;2;2}$-free graphs; and various subclasses of graphs of bounded maximum degree, for example subcubic graphs. Our algorithms are based on various approaches. In particular, we characterize augmenting graphs in a subclass of $S_{2;k;k}$-free graphs and a subclass of $S_{2;2;5}$-free graphs. These characterizations are partly based on extensions of the concept of redundant set [125]. We also propose methods finding augmenting chains, an extension of the method in [99], and finding augmenting trees, an extension of the methods in [125]. We apply the augmenting vertex technique, originally used for $P_{5}$-free graphs or banner-free graphs, for some more general graph classes. We consider a general graph theoretical combinatorial problem, the so-called Maximum -Set problem. Two special cases of this problem, the so-called Maximum F-(Strongly) Independent Subgraph and Maximum F-Induced Subgraph, where F is a connected graph set, are considered. The complexity of the Maximum F-(Strongly) Independent Subgraph problem is revised and the NP-hardness of the Maximum F-Induced Subgraph problem is proved. We also extend the augmenting approach to apply it for the general Maximum Π -Set problem. We revise on classical graph transformations and give two unified views based on pseudo-boolean functions and αff-redundant vertex. We also make extensive uses of α-redundant vertices, originally mainly used for $P_{5}$-free graphs, to give polynomial solutions for some subclasses of $S_{2;2;2}$-free graphs and $tree_{k}$-free graphs. We consider some classical sequential greedy heuristic methods. We also combine classical algorithms with αff-redundant vertices to have new strategies of choosing the next vertex in greedy methods. Some aspects of the algorithms, for example forbidden induced subgraph sets and worst case results, are also considered. Finally, we restrict our attention on graphs of bounded maximum degree and subcubic graphs. Then by using some techniques, for example ff-redundant vertex, clique separator, and arguments based on distance, we general these results for some subclasses of $S_{i;j;k}$-free subcubic graphs.

Ce travail de thèse comporte trois parties. La partie principale s'intéresse au transport des courants polarisés en spin dans des matériaux à base de semi-conducteurs. Nous dérivons et analysons une hiérarchie des modèles allant du niveau microscopique au niveau macroscopique et tenant compte des différents mécanismes de rotation et de relaxation du vecteur spin dans les semi-conducteurs. Les mécanismes essentiels pris en compte sont les couplages spin-orbite et les interactions avec renversement de spin (spin-flip interactions). Une analyse semi-classique (via la transformation de Wigner) de l'équation de Schrödinger avec hamiltonien spin-orbite est présentée. Au niveau cinétique, l'équation de Vlasov (ou Boltzmann) spinorielle est une équation à valeur dans l'ensemble des matrices carrées d'ordre deux hermitiennes et positives. Partant ensuite de la spinor forme de l'équation de Boltzmann (avec différents opérateurs de collisions avec et sans renversement du vecteur spin) et par des techniques d'asymptotiques de diffusion, nous dérivons et analysons plusieurs modèles macroscopiques. Ils sont de type dérive-diffusion, SHE, Energie-Transport, à deux composantes ou spinoriels conservant des effets de rotation et de relaxation du vecteur spin. Nous validons ensuite ces modèles par des cas tests numériques. Deux applications numériques sont présentées : la simulation d'un transistor à effet de rotation de spin et l'étude de l'effet d'accumulation de spin à l'interface entre deux couches semi-conductrices différemment dopées. Dans la seconde partie, nous considérons une équation cinétique de type Boltzmann linéaire dans des domaines où un champ magnétique fort est appliqué. Nous étudions la limite de diffusion en supposant que le champ magnétique est unidirectionnel et tend vers l'infini. Le modèle obtenu est un modèle macroscopique constitué d'une équation diffusive dans la direction parallèle au champ magnétique et d'une dérive représentant l'effet centre-guide en présence d'un champ électrique dans la direction perpendiculaire. Le terme de diffusion contient des moyennes de giration de l'opérateur de collisions utilisé. Nous prouvons la convergence en utilisant des techniques d'entropie pour traiter le comportement diffusif, et en conjuguant par les rotations locales induites par le champ magnétique pour tenir compte des oscillations. Dans la troisième partie de cette thèse, Nous nous intéressons à la description du potentiel de confinement dans des gas d'électrons bidimensionnels. Nous étudions la limite faible longueur de Debye (ou faible température) du système de Schrödinger-Poisson unidimensionnel stationnaire sur un intervalle borné. Les électrons sont supposés dans un mélange d'états avec une statistique de Boltzmann (ou de Fermi-Dirac). En utilisant différentes reformulations du système comme des problèmes de minimisation convexe, nous montrons qu'asymptotiquement seul le premier niveau d'énergie est occupé. Le potentiel électrostatique converge vers une couche limite avec un profil calculé à l'aide d'un système de Schrödinger-Poisson sur le demi axe réel.