Characterizing distribution rules for cost sharing games

In noncooperative cost sharing games, individually strategic agents choose resources based on how the welfare (cost or revenue) generated at each resource (which depends on the set of agents that choose the resource) is distributed. The focus is on finding distribution rules that lead to stable allocations, which is formalized by the concept of Nash equilibrium, e.g., Shapley value (budget-balanced) and marginal contribution (not budget-balanced) rules.

Recent work that seeks to characterize the space of all such rules shows that the only budget-balanced distribution rules that guarantee equilibrium existence in all welfare sharing games are generalized weighted Shapley values (GWSVs), by exhibiting a specific 'worst-case' welfare function which requires that GWSV rules be used. Our work provides an exact characterization of the space of distribution rules (not necessarily budget-balanced) for any specific local welfare functions remains, for a general class of scalable and separable games with well-known applications, e.g., facility location, routing, network formation, and coverage games.

We show that all games conditioned on any fixed local welfare functions possess an equilibrium if and only if the distribution rules are equivalent to GWSV rules on some 'ground' welfare functions. Therefore, it is neither the existence of some worst-case welfare function, nor the restriction of budget-balance, which limits the design to GWSVs. Also, in order to guarantee equilibrium existence, it is necessary to work within the class of potential games, since GWSVs result in (weighted) potential games.

We also provide an alternative characterization—all games conditioned on any fixed local welfare functions possess an equilibrium if and only if the distribution rules are equivalent to generalized weighted marginal contribution (GWMC) rules on some 'ground' welfare functions. This result is due to a deeper fundamental connection between Shapley values and marginal contributions that our proofs expose—they are equivalent given a transformation connecting their ground welfare functions. (This connection leads to novel closed-form expressions for the GWSV potential function.) Since GWMCs are more tractable than GWSVs, a designer can tradeoff budget-balance with computational tractability in deciding which rule to implement.

A geometric analysis of convex demixing

Demixing is the task of identifying multiple signals given only their sum and prior information about their structures. Examples of demixing problems include (i) separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis; (ii) decomposing an observed matrix into low-rank and sparse components; and (iii) identifying a binary codeword with impulsive corruptions. This thesis describes and analyzes a convex optimization framework for solving an array of demixing problems.

Our framework includes a random orientation model for the constituent signals that ensures the structures are incoherent. This work introduces a summary parameter, the statistical dimension, that reflects the intrinsic complexity of a signal. The main result indicates that the difficulty of demixing under this random model depends only on the total complexity of the constituent signals involved: demixing succeeds with high probability when the sum of the complexities is less than the ambient dimension; otherwise, it fails with high probability.

The fact that a phase transition between success and failure occurs in demixing is a consequence of a new inequality in conic integral geometry. Roughly speaking, this inequality asserts that a convex cone behaves like a subspace whose dimension is equal to the statistical dimension of the cone. When combined with a geometric optimality condition for demixing, this inequality provides precise quantitative information about the phase transition, including the location and width of the transition region.

I. Impact spallation experiments: fracture patterns and spall velocities. II. Craters in carbonate rocks: an electron paramagnetic resonance analysis of shock damage

This work is divided into two independent papers.

PAPER 1.

Spall velocities were measured for nine experimental impacts into San Marcos gabbro targets. Impact velocities ranged from 1 to 6.5 km/sec. Projectiles were iron, aluminum, lead, and basalt of varying sizes. The projectile masses ranged from a 4 g lead bullet to a 0.04 g aluminum sphere. The velocities of fragments were measured from high-speed films taken of the events. The maximum spall velocity observed was 30 m/sec, or 0.56 percent of the 5.4 km/sec impact velocity. The measured velocities were compared to the spall velocities predicted by the spallation model of Melosh (1984). The compatibility between the spallation model for large planetary impacts and the results of these small scale experiments are considered in detail.

The targets were also bisected to observe the pattern of internal fractures. A series of fractures were observed, whose location coincided with the boundary between rock subjected to the peak shock compression and a theoretical "near surface zone" predicted by the spallation model. Thus, between this boundary and the free surface, the target material should receive reduced levels of compressive stress as compared to the more highly shocked region below.

PAPER 2.

Carbonate samples from the nuclear explosion crater, OAK, and a terrestrial impact crater, Meteor Crater, were analyzed for shock damage using electron para- magnetic resonance, EPR. The first series of samples for OAK Crater were obtained from six boreholes within the crater, and the second series were ejecta samples recovered from the crater floor. The degree of shock damage in the carbonate material was assessed by comparing the sample spectra to spectra of Solenhofen limestone, which had been shocked to known pressures.

The results of the OAK borehole analysis have identified a thin zone of highly shocked carbonate material underneath the crater floor. This zone has a maximum depth of approximately 200 ft below sea floor at the ground zero borehole and decreases in depth towards the crater rim. A layer of highly shocked material is also found on the surface in the vicinity of the reference bolehole, located outside the crater. This material could represent a fallout layer. The ejecta samples have experienced a range of shock pressures.

It was also demonstrated that the EPR technique is feasible for the study of terrestrial impact craters formed in carbonate bedrock. The results for the Meteor Crater analysis suggest a slight degree of shock damage present in the β member of the Kaibab Formation exposed in the crater walls.

Three-dimensional nonlinear inelastic analysis of steel moment-frame buildings damaged by earthquake excitations

The Northridge earthquake of January 17, 1994, highlighted the two previously known problems of premature fracturing of connections and the damaging capabilities of near-source ground motion pulses. Large ground motions had not been experienced in a city with tall steel moment-frame buildings before. Some steel buildings exhibited fracture of welded connections or other types of structural degradation.

A sophisticated three-dimensional nonlinear inelastic program is developed that can accurately model many nonlinear properties commonly ignored or approximated in other programs. The program can assess and predict severely inelastic response of steel buildings due to strong ground motions, including collapse.

Three-dimensional fiber and segment discretization of elements is presented in this work. This element and its two-dimensional counterpart are capable of modeling various geometric and material nonlinearities such as moment amplification, spread of plasticity and connection fracture. In addition to introducing a three-dimensional element discretization, this work presents three-dimensional constraints that limit the number of equations required to solve various three-dimensional problems consisting of intersecting planar frames.

Two buildings damaged in the Northridge earthquake are investigated to verify the ability of the program to match the level of response and the extent and location of damage measured. The program is used to predict response of larger near-source ground motions using the properties determined from the matched response.

A third building is studied to assess three-dimensional effects on a realistic irregular building in the inelastic range of response considering earthquake directivity. Damage levels are observed to be significantly affected by directivity and torsional response.

Several strong recorded ground motions clearly exceed code-based levels. Properly designed buildings can have drifts exceeding code specified levels due to these ground motions. The strongest ground motions caused collapse if fracture was included in the model. Near-source ground displacement pulses can cause columns to yield prior to weaker-designed beams. Damage in tall buildings correlates better with peak-to-peak displacements than with peak-to-peak accelerations.

Dynamic response of tall buildings shows that higher mode response can cause more damage than first mode response. Leaking of energy between modes in conjunction with damage can cause torsional behavior that is not anticipated.

Various response parameters are used for all three buildings to determine what correlations can be made for inelastic building response. Damage levels can be dramatically different based on the inelastic model used. Damage does not correlate well with several common response parameters.

Realistic modeling of material properties and structural behavior is of great value for understanding the performance of tall buildings due to earthquake excitations.

The isolation and partial biochemical analysis of Sindbis virus proteins

Recently, the amino acid sequences have been reported for several proteins, including the envelope glycoproteins of Sindbis virus, which all probably span the plasma membrane with a common topology: a large N-terminal, extracellular portion, a short region buried in the bilayer, and a short C-terminal intracellular segment. The regions of these proteins buried in the bilayer correspond to portions of the protein sequences which contain a stretch of hydrophobic amino acids and which have other common characteristics, as discussed. Reasons are also described for uncertainty, in some proteins more than others, as to the precise location of some parts of the sequence relative to the membrane.

The signal hypothesis for the transmembrane translocation of proteins is briefly described and its general applicability is reviewed. There are many proteins whose translocation is accurately described by this hypothesis, but some proteins are translocated in a different manner.

The transmembraneous glycoproteins E1 and E2 of Sindbis virus, as well as the only other virion protein, the capsid protein, were purified in amounts sufficient for biochemical analysis using sensitive techniques. The amino acid composition of each protein was determined, and extensive N-terminal sequences were obtained for E1 and E2. By these techniques E1 and E2 are indistinguishable from most water soluble proteins, as they do not contain an obvious excess of hydrophobic amino acids in their N-terminal regions or in the intact molecule.

The capsid protein was found to be blocked, and so its N-terminus could not be sequenced by the usual methods. However, with the use of a special labeling technique, it was possible to incorporate tritiated acetate into the N-terminus of the protein with good specificity, which was useful in the purification of peptides from which the first amino acids in the N-terminal sequence could be identified.

Nanomole amounts of PE2, the intracellular precursor of E2, were purified by an immuno-affinity technique, and its N-terminus was analyzed. Together with other work, these results showed that PE2 is not synthesized with an N-terminal extension, and the signal sequence for translocation is probably the N-terminal amino acid sequence of the protein. This N-terminus was found to be 80-90% blocked, also by Nacetylation, and this acetylation did not affect its function as a signal sequence. The putative signal sequence was also found to contain a glycosylated asparagine residue, but the inhibition of this glycosylation did not lead to the cleavage of the sequence.

Real-Time Bayesian Analysis of Ground Motion Envelopes for Earthquake Early Warning

Current earthquake early warning systems usually make magnitude and location predictions and send out a warning to the users based on those predictions. We describe an algorithm that assesses the validity of the predictions in real-time. Our algorithm monitors the envelopes of horizontal and vertical acceleration, velocity, and displacement. We compare the observed envelopes with the ones predicted by Cua & Heaton's envelope ground motion prediction equations (Cua 2005). We define a "test function" as the logarithm of the ratio between observed and predicted envelopes at every second in real-time. Once the envelopes deviate beyond an acceptable threshold, we declare a misfit. Kurtosis and skewness of a time evolving test function are used to rapidly identify a misfit. Real-time kurtosis and skewness calculations are also inputs to both probabilistic (Logistic Regression and Bayesian Logistic Regression) and nonprobabilistic (Least Squares and Linear Discriminant Analysis) models that ultimately decide if there is an unacceptable level of misfit. This algorithm is designed to work at a wide range of amplitude scales. When tested with synthetic and actual seismic signals from past events, it works for both small and large events.

Toppling Analysis of Precariously Balanced Rocks under Earthquake Excitation

Toppling analysis of a precariously balanced rock (PBR) can provide insights into the nature of ground motion that has not occurred at that location in the past and, by extension, realistic constraints on peak ground motions for use in engineering design. Earlier approaches have targeted simplistic 2-D models of the rock or modeled the rock-pedestal contact using spring-damper assemblies that require re-calibration for each rock. These analyses also assume that the rock does not slide on the pedestal. Here, a method to model PBRs in three dimensions is presented. The 3-D model is created from a point cloud of the rock, the pedestal, and their interface, obtained using Terrestrial Laser Scanning (TLS). The dynamic response of the model under earthquake excitation is simulated using a rigid body dynamics algorithm. The veracity of this approach is demonstrated by comparisons against data from shake table experiments. Fragility maps for toppling probability of the Echo Cliff PBR and the Pacifico PBR as a function of various ground motion parameters, rock-pedestal interface friction coefficient, and excitation direction are presented. The seismic hazard at these PBR locations is estimated using these maps. Additionally, these maps are used to assess whether the synthetic ground motions at these locations resulting from scenario earthquakes on the San Andreas Fault are realistic (toppling would indicate that the ground motions are unrealistically high).