Search

Nearly a decade ago, Azrieli and Shmaya introduced the class of λ-Lipschitz games in which every player's payoff function is λ-Lipschitz with respect to the actions of the other players. They showed via the probabilistic method that n-player Lipschitz games with m strategies per player have pure ε-approximate Nash equilibria, for ε ≥ λ√8nlog(2mn). They left open, however, the question of how hard it is to find such an equilibrium. In this work, we develop an efficient reduction from more general games to Lipschitz games. We use this reduction to study both the query and computational complexity of algorithms finding λ-approximate pure Nash equilibria of λ-Lipschitz games and related classes. We show a query lower bound exponential in nλ/ε against randomized algorithms finding ε-approximate pure Nash equilibria of n-player, λ-Lipschitz games. We additionally present the first PPAD-completeness result for finding pure Nash equilibria in a class of finite, non-Bayesian games (we show this for λ-Lipschitz polymatrix games for suitable pairs of values ε and λ) in which both the proof of PPAD-hardness and the proof of containment in PPAD require novel approaches (in fact, our approach implies containment in PPAD for any class of Lipschitz games in which payoffs from mixed-strategy profiles can be deterministically computed), and present a definition of "randomized PPAD". We define and subsequently analyze the class of "Multi-Lipschitz games", a generalization of Lipschitz games involving player-specific Lipschitz parameters in which the value of interest appears to be the average of the individual Lipschitz parameters. We discuss a dichotomy of the deterministic query complexity of finding ε-approximate Nash equilibria of general games and, subsequently, a query lower bound for λ-Lipschitz games in which any non-trivial value of ε requires exponentially-many queries to achieve. We examine which parts of this extend to the concepts of approximate correlated and coarse correlated equilibria, and in the process generalize the edge-isoperimetric inequalities to generalizations of the hypercube. Finally, we improve the block update algorithm presented by Goldberg and Marmolejo to break the potential boundary of a 0.75-approximation factor, presenting a randomized algorithm achieving a 0.7368-approximate Nash equilibrium making polynomially-many profile queries of an n-player 1/n-1-Lipschitz game with an unbounded number of actions.

In this thesis we consider base size and properties of the generating graph for finite groups. Let Ω = {1,...,n}, let Sₙ = Sym({1,...,n}) and let G ≤ Sₙ. A base for G is a sequence Λ = (ω₁, . . . , ωₖ) of points in Ω such that the pointwise stabilizer, G_{ω₁,...,ωₖ} , is the identity. The base size of G, denoted by b(G, Ω) or b(G), is the length of the shortest base. We say that Λ is an irredundant base if G > G_{ω₁} > G_{ω₁,ω₂} > ··· > G_{ω₁,ω₂,...,ωₖ} = 1. If no irredundant base is longer than Λ, then we say that Λ is a maximal irredundant base for G and denote its length by I(G). A group is called large base if it is either a product action or almost simple group, and its socle is one or more copies of the alternating group Aᵣ acting on k-sets. Let G be a primitive subgroup of Sₙ that is not large base. We prove that any irredundant base for G has size at most 5log₂n. This bound is best possible up to a small multiplicative constant and is the first logarithmic bound on the size of an irredundant base for such groups. We show that for any constant c, there are infinitely many primitive groups with maximal irredundant base size at least c times the minimal base size. As a corollary of the first result, the relational complexity of G, denoted RC(G) (see Definition 2.2.10), is at most 5log₂n + 1. In addition the maximal size of a minimal base and the height, denoted B(G) and H(G) (see Definitions 2.2.1 and 2.2.5), are both at most 5log₂n. Furthermore, we deduce that a base for G of size at most 5log₂n can be computed in polynomial time. The generating graph Γ(G) of a finite group G has vertex set the non-identity elements of G, with two elements connected exactly when they generate G. A coclique in a graph is an empty induced subgraph, so a coclique in Γ(G) is a subset of G such that no pair of elements generate G. A coclique is maximal if it is contained in no larger coclique. It is easy to see that the non-identity elements of a maximal subgroup of G form a coclique in Γ(G), but this coclique need not be maximal. Let G = Sₙ or Aₙ. We first determine when the intransitive maximal subgroups of G are maximal cocliques in Γ(G), and when they are not we find the unique maximal coclique in which they are contained. We then show that for sufficiently large n, the imprimitive maximal subgroups of G are all maximal cocliques in Γ(G). In addition, using the result on intransitive maximal subgroups we prove that a conjecture of Cameron, Lucchini, and Roney-Dougal holds for G under certain restrictions on n. Namely we prove that two elements of G have identical sets of neighbours in Γ(G) if and only if they belong to exactly the same maximal subgroups. Finally under another set of restrictions on n we then determine precisely which maximal subgroups are maximal cocliques in Γ(G).

Problem: Complex systems are composed of many interdependent subsystems with a level of complexity that exceeds the ability of a single designer. One way to address this problem is to partition the complex design problem into smaller, more manageable design tasks that can be handled by multiple design teams. Partitioning-based design methods are decision support tools that provide mathematical foundations, and computational methods to create such design processes. Managing the interdependency among these subsystems is crucial and a successful design process should meet the requirements of the whole system which needs coordinating the solutions for all the partitions after all. Approach: Partitioning and coordination should be performed to break down the system into subproblems, solve them and put these solutions together to come up with the ultimate system design. These two tasks of partitioning-coordinating are computationally demanding. Most of the proposed approaches are either computationally very expensive or applicable to only a narrow class of problems. These approaches also use exact methods and eliminate the uncertainty. To manage the computational complexity and uncertainty, we approximate each subproblem after partitioning the whole system. In engineering design, one way to approximate the reality is using surrogate models (SM) to replace the functions which are computationally expensive to solve. This task also is added to the proposed computational framework. Also, to automate the whole process, creating a knowledge-based reusable template for each of these three steps is required. Therefore, in this dissertation, we first partition/decompose the complex system, then, we approximate the subproblem of each partition. Afterwards, we apply coordination methods to guide the solutions of the partitions toward the ultimate integrated system design. Validation: The partitioning-approximation-coordination design approach is validated using the validation square approach that consists of theoretical and empirical validation. Empirical validation of the design architecture is carried out using two industry-driven problems namely the a hot rod rolling problem’, ‘a dam network design problem’, ‘a crime prediction problem’ and ‘a green supply chain design problem’. Specific sub-problems are formulated within these problem domains to address various research questions identified in this dissertation. Contributions: The contributions from the dissertation are categorized into new knowledge in five research domains: • Creating an approach to building an ensemble of surrogate models when the data is limited – when the data is limited, replacing computationally expensive simulations with accurate, low-dimensional, and rapid surrogates is very important but non-trivial. Therefore, a cross-validation-based ensemble modeling approach is proposed. • Using temporal and spatial analysis to manage the uncertainties - when the data is time-based (for example, in meteorological data analysis) and when we are dealing with geographical data (for example, in geographical information systems data analysis), instead of feature-based data analysis time series analysis and spatial statistics are required, respectively. Therefore, when the simulations are for time and space-based data, surrogate models need to be time and space-based. In surrogate modeling, there is a gap in time and space-based models which we address in this dissertation. We created, applied and evaluated the effectiveness of these models for a dam network planning and a crime prediction problem. • Removing assumptions regarding the demand distributions in green supply chain networks – in the existent literature for supply chain network design, there are always assumptions about the distribution of the demand. We remove this assumption in the partition-approximate-compose of the green supply chain design problem. • Creating new knowledge by proposing a coordination approach for a partitioned and approximated network design. A green supply chain under online (pull economy) and in-person (push economy) shopping channels is designed to demonstrate the utility of the proposed approach.

Since Valiant’s establishment of matrix rigidity to analyse circuit complexity, various contributions to the bounds of matrix rigidity of special candidates has bloomed. In this thesis, we cover the following topics: existing explicit and semi-explicit rigidity lower bounds for various families of matrices, Paturi-Pudlák dimensions, rigid sets, connections between data structure lower bounds and rigidity lower bounds and non-rigidity results.

Collective decision making arises in many real life situations, such as elections, matching applicants to job openings, and partitioning students into working groups. Over the past three decades, computer scientists have used techniques from the design and analysis of algorithms and complexity theory to develop social choice theory from a computational perspective, leading to the new research area of computational social choice theory. Broadly speaking, this dissertation makes two kinds of contributions to this new research area. First, we provide new algorithms and hardness results for two settings. In our first setting, we revisit the classical housing markets model in which we seek to compute a suitable reallocation of n houses to n agents, each of whom initially owns a particular house and has strict preferences over the set of n houses. In the variants of this model that we study, graph-based restrictions are imposed on the exchange of houses. More specifically, we consider two cases. In the first case, we are given a graph where the vertex set corresponds to the set of agents, and we assume that two agents can only swap houses if they are adjacent in the graph and the swap is Pareto-improving; thus, in this case, the locations of the agents remain fixed in the graph, while the houses can move around. The second case is similar except we assume that the locations of the houses remain fixed (i.e., each vertex now corresponds to a house) and the agents move around. In our second setting, we consider a variant of the classical coalition formation game, the fractional hedonic game. Such a game can be represented by a directed weighted graph where the set of vertices corresponds to the set of players, and where the weight of an edge (i,j) from player i to player j denotes the value that player i has for player j. Given a partitioning of the players into coalitions, the utility of player i is defined to be the average value that player i assigns to the members of their coalition. We assume that there is a limit on the number of coalitions that can be formed. In this setting, we study the problem of computing a social welfare maximizing partition and the problem of computing a Nash stable partition. We study these two problems for a variety of different graph classes. Second, we design mechanisms without money for new games related to facility location and resource sharing. In the facility location game that we consider, a central planner plans to build a heterogeneous set of facilities (e.g., a school, a water treatment plant) and each agent reports which of these facilities they consider to be “obnoxious”. The location of each agent is assumed to be fixed, and the utility of an agent is based on the minimum distance of the agent to an obnoxious facility. The goal is to design strategyproof mechanisms that maximize either the sum of the agent utilities or the minimum utility of any agent. In the resource sharing game that we consider, agents pool their computational resources in order to better accommodate fluctuations in individual demand over a sequence of rounds, and the agents specify their demand for each round at the outset. We present a group-strategyproof and non-wasteful mechanism that guarantees each agent at least half of the utility they could achieve without sharing their resources.

A major open problem in proof complexity is to prove superpolynomial lower bounds for AC0[p]-Frege proofs. This system is the analog of AC0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years ([Raz87, Smo87]), there are no significant lower bounds for AC0[p]-Frege. Significant and extensive degree lower bounds have been obtained for a variety of subsystems of AC0[p]- Frege, including Nullstellensatz ([BIK+94]), Polynomial Calculus ([CEI96]), and SOS ([GV01]). However to date there has been no progress on AC0[p]-Frege lower bounds.In the first part of this thesis, we study constant-depth extensions of the Polynomial Calculus [GH03]. We show that these extensions are much more powerful than was previously known. Our main result is that small depth (≤ 43) Polynomial Calculus (over a sufficiently large field) can polynomially effectively simulate all of the well-studied semialgebraic proof systems: Cutting Planes, Sherali-Adams, Sum-of-Squares (SOS), and Positivstellensatz Calculus (Dynamic SOS). Additionally, they can also quasi-polynomially effectively simulate AC0[q]-Frege for any prime q independent of the characteristic of the underlying field. They can also effectively simulate TC0-Frege if the depth is allowed to grow proportionally. Thus, proving strong lower bounds for constant-depth extensions of Polynomial Calculus would not only give lower bounds for AC0[p]-Frege, but also for systems as strong as TC0-Frege. In the second part of this thesis, we deal with the flip side of proving new lower bounds for these systems. In this direction, we extend the recent lower bounds of Sokolov [Sok20] for Polynomial Calculus over {±1} variables to show for every prime p > 0, every n > 0 and κ = O(log n) the existence of an unsatisfiable system of polynomial equations over O(n log n) variables of degree O(logn) such that any Polynomial Calculus refutation over F_p with M extension variables, each depending on at most κ original variables requires size exp?Ω(n2/(κ22κ(M + nlog(n)))) .