Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in [8, 44, 39, 9]. On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.

Auctions for government securities: a laboratory comparison of uniform, discriminatory and spanish designs

The Bank of Spain uses a unique auction format to sell government bonds, which can be seen as a hybrid of a uniform and a discriminatory auction. For winning bids above the average winning bid, buyers are charged the average winning bid, otherwise they pay their respective bids. We report on an experiment that compares this auction format to the discriminatory format, used in most other countries, and to the uniform format. Our design is based on a common value model with multi-unit supply and two-unit demand. The results show significantly higher revenue with the Spanish and the uniform formats than with the discriminatory one, while volatility of prices over time is significantly lower in the discriminatory format than in the Spanish and uniform cases. Actual price dispersion is significantly larger in the discriminatory than in the Spanish. Our data also exhibit the use of bid-spreading strategies in all three designs.

Optimal asymptotic bounds for spherical designs

"Vegeu el resum a l'inici del document del fitxer adjunt"

Multi-stage oligopoly models with nested logit demand structures: A simplifying approach

Solving multi-stage oligopoly models by backward induction can easily become a com- plex task when rms are multi-product and demands are derived from a nested logit frame- work. This paper shows that under the assumption that within-segment rm shares are equal across segments, the analytical expression for equilibrium pro ts can be substantially simpli ed. The size of the error arising when this condition does not hold perfectly is also computed. Through numerical examples, it is shown that the error is rather small in general. Therefore, using this assumption allows to gain analytical tractability in a class of models that has been used to approach relevant policy questions, such as for example rm entry in an industry or the relation between competition and location. The simplifying approach proposed in this paper is aimed at helping improving these type of models for reaching more accurate recommendations.

Supporting the reuse of effective CSCL learning designs through social structure representations

Distance and blended collaborative learning settings are usually characterized by different social structures defined in terms of groups' number, dimension, and composition; these structures are variable and can change within the same activity. This variability poses additional complexity to instructional designers, when they are trying to develop successful experiences from existing designs. This complexity is greatly associated with the fact that learning designs do not render explicit how social structures influenced the decisions of the original designer, and thus whether the social structures of the new setting could preclude the effectiveness of the reused design. This article proposes the usage of new representations (social structure representations, SSRs) able to support unskilled designers in reusing existing learning designs, through the explicit characterization of the social structures and constraints embedded either by the original designers or the reusing teachers, according to well-known principles of good collaborative learning practice. The article also describes an evaluation process that involved university professors, as well as the main findings derived from it. This process supported the initial assumptions about the effectiveness of SSRs, with significant evidence from both qualitative and qualitative data.

Management information systems: The balanced scorecard in Spanish public universities

Organisations are becoming increasingly aware of the need for management information systems, due largely to the changing environment and a continuous process of globalisation. All of this means that managers need to adapt the structures of their organisations to the changes and, therefore, to plan, control and manage better. The Spanish public university cannot avoid this changing (demographic, economic and social changes) and globalising (among them the convergence of European qualifications) environment, to which we must add the complex organisation structure, characterised by a high dispersion of authority for decision making in different collegiate and unipersonal organs. It seems obvious that these changes must have repercussions on the direction, organisation and management structures of those public higher education institutions, and it seems natural that, given this environment, the universities must adapt their present management systems to the demand by society for the quality and suitability of the services they provide.

Trends in hours, balanced growth and the role of technology in the business cycle

The present paper revisits a property embedded in most dynamic macroeconomic models: the stationarity of hours worked. First, I argue that, contrary to what is often believed, there are many reasons why hours could be nonstationary in those models, while preserving the property of balanced growth. Second, I show that the postwar evidence for most industrialized economies is clearly at odds with the assumption of stationary hours per capita. Third, I examine the implications of that evidence for the role of technology as a source of economic fluctuations in the G7 countries.

Random assignment of intervention points in two phase single-case designs: data-division-specific distributions

The present study explores the statistical properties of a randomization test based on the random assignment of the intervention point in a two-phase (AB) single-case design. The focus is on randomization distributions constructed with the values of the test statistic for all possible random assignments and used to obtain p-values. The shape of those distributions is investigated for each specific data division defined by the moment in which the intervention is introduced. Another aim of the study consisted in testing the detection of inexistent effects (i.e., production of false alarms) in autocorrelated data series, in which the assumption of exchangeability between observations may be untenable. In this way, it was possible to compare nominal and empirical Type I error rates in order to obtain evidence on the statistical validity of the randomization test for each individual data division. The results suggest that when either of the two phases has considerably less measurement times, Type I errors may be too probable and, hence, the decision making process to be carried out by applied researchers may be jeopardized.

R functions for quantifying nonindependence in standard dyadic and SRM designs

Interdependence is the main feature of dyadic relationships and, in recent years, various statistical procedures have been proposed for quantifying and testing this social attribute in different dyadic designs. The purpose of this paper is to develop several functions for this kind of statistical tests in an R package, known as nonindependence, for use by applied social researchers. A Graphical User Interface (GUI) is also developed to facilitate the use of the functions included in this package. Examples drawn from psychological research and simulated data are used to illustrate how the software works.

Comparing 'visual' effect size indices for single-case designs

Effect size indices are indispensable for carrying out meta-analyses and can also be seen as an alternative for making decisions about the effectiveness of a treatment in an individual applied study. The desirable features of the procedures for quantifying the magnitude of intervention effect include educational/clinical meaningfulness, calculus easiness, insensitivity to autocorrelation, low false alarm and low miss rates. Three effect size indices related to visual analysis are compared according to the aforementioned criteria. The comparison is made by means of data sets with known parameters: degree of serial dependence, presence or absence of general trend, changes in level and/or in slope. The percent of nonoverlapping data showed the highest discrimination between data sets with and without intervention effect. In cases when autocorrelation or trend is present, the percentage of data points exceeding the median may be a better option to quantify the effectiveness of a psychological treatment.

Factors affecting visual analysis in single-case designs

Visual inspection remains the most frequently applied method for detecting treatment effects in single-case designs. The advantages and limitations of visual inference are here discussed in relation to other procedures for assessing intervention effectiveness. The first part of the paper reviews previous research on visual analysis, paying special attention to the validation of visual analysts" decisions, inter-judge agreement, and false alarm and omission rates. The most relevant factors affecting visual inspection (i.e., effect size, autocorrelation, data variability, and analysts" expertise) are highlighted and incorporated into an empirical simulation study with the aim of providing further evidence about the reliability of visual analysis. Our results concur with previous studies that have reported the relationship between serial dependence and increased Type I rates. Participants with greater experience appeared to be more conservative and used more consistent criteria when assessing graphed data. Nonetheless, the decisions made by both professionals and students did not match sufficiently the simulated data features, and we also found low intra-judge agreement, thus suggesting that visual inspection should be complemented by other methods when assessing treatment effectiveness.

Estimating slope and level change in N=1 designs

The current study proposes a new procedure for separately estimating slope change and level change between two adjacent phases in single-case designs. The procedure eliminates baseline trend from the whole data series prior to assessing treatment effectiveness. The steps necessary to obtain the estimates are presented in detail, explained, and illustrated. A simulation study is carried out to explore the bias and precision of the estimators and compare them to an analytical procedure matching the data simulation model. The experimental conditions include two data generation models, several degrees of serial dependence, trend, level and/or slope change. The results suggest that the level and slope change estimates provided by the procedure are unbiased for all levels of serial dependence tested and trend is effectively controlled for. The efficiency of the slope change estimator is acceptable, whereas the variance of the level change estimator may be problematic for highly negatively autocorrelated data series.

Central configurations of nested rotated regular tetrahedra

In this paper we prove that there are only two different classes of central configura- tions with convenient masses located at the vertices of two nested regular tetrahedra: either when one of the tetrahedra is a homothecy of the other one, or when one of the tetrahedra is a homothecy followed by a rotation of Euler angles = = 0 and = of the other one. We also analyze the central configurations with convenient masses located at the vertices of three nested regular tetrahedra when one them is a homothecy of the other one, and the third one is a homothecy followed by a rotation of Euler angles = = 0 and = of the other two. In all these cases we have assumed that the masses on each tetrahedron are equal but masses on different tetrahedra could be different.

Central configurations of nested regular polyhedra for the spatial 2n–body problem

We consider 2n masses located at the vertices of two nested regular polyhedra with the same number of vertices. Assuming that the masses in each polyhedron are equal, we prove that for each ratio of the masses of the inner and the outer polyhedron there exists a unique ratio of the length of the edges of the inner and the outer polyhedron such that the configuration is central.

Central configurations of three nested regular polyhedra for the spatial 3n–body problem

Three regular polyhedra are called nested if they have the same number of vertices n, the same center and the positions of the vertices of the inner polyhedron ri, the ones of the medium polyhedron Ri and the ones of the outer polyhedron Ri satisfy the relation Ri = ri and Ri = Rri for some scale factors R > > 1 and for all i = 1, . . . , n. We consider 3n masses located at the vertices of three nested regular polyhedra. We assume that the masses of the inner polyhedron are equal to m1, the masses of the medium one are equal to m2, and the masses of the outer one are equal to m3. We prove that if the ratios of the masses m2/m1 and m3/m1 and the scale factors and R satisfy two convenient relations, then this configuration is central for the 3n–body problem. Moreover there is some numerical evidence that, first, fixed two values of the ratios m2/m1 and m3/m1, the 3n–body problem has a unique central configuration of this type; and second that the number of nested regular polyhedra with the same number of vertices forming a central configuration for convenient masses and sizes is arbitrary.