Essays on Correlated Equilibrium and Voter Turnout

This thesis consists of three essays in the areas of political economy and game theory, unified by their focus on the effects of pre-play communication on equilibrium outcomes.

Communication is fundamental to elections. Chapter 2 extends canonical voter turnout models, where citizens, divided into two competing parties, choose between costly voting and abstaining, to include any form of communication, and characterizes the resulting set of Aumann's correlated equilibria. In contrast to previous research, high-turnout equilibria exist in large electorates and uncertain environments. This difference arises because communication can coordinate behavior in such a way that citizens find it incentive compatible to follow their correlated signals to vote more. The equilibria have expected turnout of at least twice the size of the minority for a wide range of positive voting costs.

In Chapter 3 I introduce a new equilibrium concept, called subcorrelated equilibrium, which fills the gap between Nash and correlated equilibrium, extending the latter to multiple mediators. Subcommunication equilibrium similarly extends communication equilibrium for incomplete information games. I explore the properties of these solutions and establish an equivalence between a subset of subcommunication equilibria and Myerson's quasi-principals' equilibria. I characterize an upper bound on expected turnout supported by subcorrelated equilibrium in the turnout game.

Chapter 4, co-authored with Thomas Palfrey, reports a new study of the effect of communication on voter turnout using a laboratory experiment. Before voting occurs, subjects may engage in various kinds of pre-play communication through computers. We study three communication treatments: No Communication, a control; Public Communication, where voters exchange public messages with all other voters, and Party Communication, where messages are exchanged only within one's own party. Our results point to a strong interaction effect between the form of communication and the voting cost. With a low voting cost, party communication increases turnout, while public communication decreases turnout. The data are consistent with correlated equilibrium play. With a high voting cost, public communication increases turnout. With communication, we find essentially no support for the standard Nash equilibrium turnout predictions.

A generalization of correlated equilibrium: A new protocol

A new correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is introduced for finite games. After randomization over the outcome space, players have the choice either to follow the recommendation of an umpire blindly or freely choose some other action except the one suggested. This scheme can lead to Pareto-better outcomes than the simple extension introduced by [Moulin, H., Vial, J.-P., 1978. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7, 201–221]. The informational and interpretational aspects of soft correlated equilibria are also discussed in detail. The power of the generalization is illustrated in the prisoners’s dilemma and a congestion game.

Generalized correlated equilibrium for two-person games in extensive form with perfect information

A correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is applied for two-person finite games in extensive form with perfect information. Randomization by an umpire takes place over the leaves of the game tree. At every decision point players have the choice either to follow the recommendation of the umpire blindly or freely choose any other action except the one suggested. This scheme can lead to Pareto-improved outcomes of other correlated equilibria. Computational issues of maximizing a linear function over the set of soft correlated equilibria are considered and a linear-time algorithm in terms of the number of edges in the game tree is given for a special procedure called “subgame perfect optimization”.

Approximate knowledge of rationality and correlated equilibria

We extend Aumann's [3] theorem deriving correlated equilibria as a consequence of common priors and common knowledge of rationality by explicitly allowing for non-rational behavior. We replace the assumption of common knowledge of rationality with a substantially weaker notion, joint p-belief of rationality, where agents believe the other agents are rational with probabilities p = (pi)i2I or more. We show that behavior in this case constitutes a constrained correlated equilibrium of a doubled game satisfying certain p-belief constraints and characterize the topological structure of the resulting set of p-rational outcomes. We establish continuity in the parameters p and show that, for p su ciently close to one, the p-rational outcomes are close to the correlated equilibria and, with high probability, supported on strategies that survive the iterated elimination of strictly dominated strategies. Finally, we extend Aumann and Dreze's [4] theorem on rational expectations of interim types to the broader p-rational belief systems, and also discuss the case of non-common priors.

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.

Beyond common priors

One property (called action-consistency) that is implicit in the common prior assumption (CPA) is identified and shown to be the driving force of the use of the CPA in a class of well-known results. In particular, we show that Aumann (1987)’s Bayesian characterization of correlated equilibrium, Aumann and Brandenburger (1995)’s epistemic conditions for Nash equilibrium, and Milgrom and Stokey (1982)’s no-trade theorem are all valid without the CPA but with action-consistency. Moreover, since we show that action-consistency is much less restrictive than the CPA, the above results are more general than previously thought, and insulated from controversies around the CPA.

The prisoners' dilemma, congestion games and correlation

Social dilemmas, in particular the prisoners' dilemma, are represented as congestion games, and within this framework soft correlated equilibria as introduced by Forgó F. (2010, A generalization of correlated equilibrium: A new protocol. Mathematical Social Sciences 60:186-190) is used to improve inferior Nash payoffs that are characteristic of social dilemmas. These games can be extended to several players in different ways preserving some important characteristics of the original 2-person game. In one of the most frequently studied models of the n-person prisoners' dilemma game we measure the performance of the soft correlated equilibrium by the mediation and enforcement values. For general prisoners' dilemma games the mediation value is ∞, the enforcement value is 2. This also holds for the class of separable prisoners’ dilemma games.

Properties of the correlated electronic states of pyrene and hydrogenated pyrene

Approximate calculations are reported on pyrene within the PPP model Hamiltonian using a novel restricted CI scheme which employs both molecular orbital and valence bond techniques. Also reported are detailed full CI results of the PPP model on 2,7-dihydropyrene obtained using the valence bond method. Spectral studies, charge and spin density calculations in ground and excited states, and ring current calculations in the ground state of the molecules are presented. In pyrene, the calculated excitation energies are in good agreement with experiment. The closed structure pi-conjugated molecule pyrene appears to show smaller distortions from the ground state geometry compared with the open structure pi-conjugated molecule 2,7-dihydropyrene. The ground state equilibrium structure of 2,7-dihydropyrene can be viewed as two hexatriene molecules connected by a vinyl crosslink, as is evident from bond order and ring current calculations. This is consistent with the only Kekule resonant structure possible for this molecule.

Multiple-quantum artifacts in single-quantum two-dimensional correlated NMR spectra of strongly coupled spins

Artifacts in the form of cross peaks have been observed along two- and three-quantum diagonals in single-quantum two-dimensional correlated (COSY) spectra of several peptides and oligonucleotides. These have been identified as due to the presence of a non-equilibrium state of kind I (a state describable by populations which differ from equilibrium) of strongly coupled spins carried over from one experiment to the next in the COSY algorithm.

Vapor-liquid equilibrium data for the system n-heptane-n-butyl alcohol at medium pressures

Vapor-liquid equilibrium data for the system n-heptane-n-butyl alcohol at pressures of 1445, 2205, 2965, and 3725 mm. of Hg have been reported. The data are correlated with Chao's modified Redlich-Kister equation.

Density functional theory embedding for correlated wavefunctions

Methods that exploit the intrinsic locality of molecular interactions show significant promise in making tractable the electronic structure calculation of large-scale systems. In particular, embedded density functional theory (e-DFT) offers a formally exact approach to electronic structure calculations in which the interactions between subsystems are evaluated in terms of their electronic density. In the following dissertation, methodological advances of embedded density functional theory are described, numerically tested, and applied to real chemical systems.

First, we describe an e-DFT protocol in which the non-additive kinetic energy component of the embedding potential is treated exactly. Then, we present a general implementation of the exact calculation of the non-additive kinetic potential (NAKP) and apply it to molecular systems. We demonstrate that the implementation using the exact NAKP is in excellent agreement with reference Kohn-Sham calculations, whereas the approximate functionals lead to qualitative failures in the calculated energies and equilibrium structures.

Next, we introduce density-embedding techniques to enable the accurate and stable calculation of correlated wavefunction (CW) in complex environments. Embedding potentials calculated using e-DFT introduce the effect of the environment on a subsystem for CW calculations (WFT-in-DFT). We demonstrate that WFT-in-DFT calculations are in good agreement with CW calculations performed on the full complex.

We significantly improve the numerics of the algorithm by enforcing orthogonality between subsystems by introduction of a projection operator. Utilizing the projection-based embedding scheme, we rigorously analyze the sources of error in quantum embedding calculations in which an active subsystem is treated using CWs, and the remainder using density functional theory. We show that the embedding potential felt by the electrons in the active subsystem makes only a small contribution to the error of the method, whereas the error in the nonadditive exchange-correlation energy dominates. We develop an algorithm which corrects this term and demonstrate the accuracy of this corrected embedding scheme.

Modelling non-adiabatic processes using correlated electron-ion dynamics

Here we survey the theory and applications of a family of methods (correlated electron-ion dynamics, or CEID) that can be applied to a diverse range of problems involving the non-adiabatic exchange of energy between electrons and nuclei. The simplest method, which is a paradigm for the others, is Ehrenfest Dynamics. This is applied to radiation damage in metals and the evolution of excited states in conjugated polymers. It is unable to reproduce the correct heating of nuclei by current carrying electrons, so we introduce a moment expansion that allows us to restore the spontaneous emission of phonons. Because of the widespread use of Non-Equilibrium Green's Functions for computing electric currents in nanoscale systems, we present a comparison of this formalism with that of CEID with open boundaries. When there is strong coupling between electrons and nuclei, the moment expansion does not converge. We thus conclude with a reworking of the CEID formalism that converges systematically and in a stable manner.

Departures from convective equilibrium with a rapidly-varying surface forcing

Convective equilibrium is a long-standing and useful concept for understanding many aspects of the behaviour of deep moist convection. For example, it is often invoked in developing parameterizations for large-scale models. However, the equilibrium assumption may begin to break down as models are increasingly used with shorter timesteps and finer resolutions. Here we perform idealized cloud-system resolving model simulations of deep convection with imposed time variations in the surface forcing. A range of rapid forcing timescales from 1 − 36hr are used, in order to induce systematic departures from equilibrium. For the longer forcing timescales, the equilibrium assumption remains valid, in at least the limited sense that cycle-integrated measures of convective activity are very similar from cycle to cycle. For shorter forcing timescales, cycle-integrated convection becomes more variable, with enhanced activity on one cycle being correlated with reduced activity on the next, suggesting a role for convective memory. Further investigation shows that the memory does not appear to be carried by the domain-mean thermodynamic fields but rather by structures on horizontal scales of 5 − 20km. Such structures are produced by the convective clouds and can persist beyond the lifetime of the cloud, even through to the next forcing cycle.

A mathematical approach to chemical equilibrium theory for gaseous systems—II: extensions and applications

Straightforward mathematical techniques are used innovatively to form a coherent theoretical system to deal with chemical equilibrium problems. For a systematic theory it is necessary to establish a system to connect different concepts. This paper shows the usefulness and consistence of the system by applications of the theorems introduced previously. Some theorems are shown somewhat unexpectedly to be mathematically correlated and relationships are obtained in a coherent manner. It has been shown that theorem 1 plays an important part in interconnecting most of the theorems. The usefulness of theorem 2 is illustrated by proving it to be consistent with theorem 3. A set of uniform mathematical expressions are associated with theorem 3. A variety of mathematical techniques based on theorems 1–3 are shown to establish the direction of equilibrium shift. The equilibrium properties expressed in initial and equilibrium conditions are shown to be connected via theorem 5. Theorem 6 is connected with theorem 4 through the mathematical representation of theorem 1.

Breaking the double-edged sword of effort/trying hard: developmental equilibrium and Longitudinal relations among effort, achievement, and academic self-concept

Ever since the classic research of Nicholls (1976) and others, effort has been recognized as a double-edged sword: whilst it might enhance achievement, it undermines academic self-concept (ASC). However, there has not been a thorough evaluation of the longitudinal reciprocal effects of effort, ASC and achievement,in the context of modern self-concept theory and statistical methodology. Nor have there been developmental equilibrium tests of whether these effects are consistent across the potentially volatile early-to-middle adolescence. Hence, focusing on mathematics, we evaluate reciprocal effects models over the first four years of secondary school, relating effort, achievement (test scores and school grades), ASC, and ASCxEffort interactions for a representative sample of 3,421 German students (Mn age = 11.75 years at Wave 1). ASC, effort and achievement were positively correlated at each wave, and there was a clear pattern of positive reciprocal positive effects among ASC, test scores and school grades—each contributing to the other, after controlling for the prior effects of all others. There was an asymmetrical pattern of effects for effort that is consistent with the double-edged sword premise: prior school grades had positive effects on subsequent effort, but prior effort had non-significant or negative effects on subsequent grades and ASC. However, on the basis of a synergistic application of new theory and methodology, we predicted and found a significant ASC-by-effort interaction, such that prior effort had more positive effects on subsequent ASC and school grades when prior ASC was high—thus providing a key to breaking the double-edged sword.