The von Neumann Minimax Theorem and its relatives and a study of externality in on-line auctions

This work consists of a theoretical part and an experimental one. The first part provides a simple treatment of the celebrated von Neumann minimax theorem as formulated by Nikaid6 and Sion. It also discusses its relationships with fundamental theorems of convex analysis. The second part is about externality in sponsored search auctions. It shows that in these auctions, advertisers have externality effects on each other which influence their bidding behavior. It proposes Hal R.Varian model and shows how adding externality to this model will affect its properties. In order to have a better understanding of the interaction among advertisers in on-line auctions, it studies the structure of the Google advertisements networ.k and shows that it is a small-world scale-free network.

Dynamics in large scale networks

In this thesis we study the properties of two large dynamic networks, the competition network of advertisers on the Google and Bing search engines and the dynamic network of friend relationships among avatars in the massively multiplayer online game (MMOG) Planetside 2. We are particularly interested in removal patterns in these networks. Our main finding is that in both of these networks the nodes which are most commonly removed are minor near isolated nodes. We also investigate the process of merging of two large networks using data captured during the merger of servers of Planetside 2. We found that the original network structures do not really merge but rather they get gradually replaced by newcomers not associated with the original structures. In the final part of the thesis we investigate the concept of motifs in the Barabási-Albert random graph. We establish some bounds on the number of motifs in this graph.

Niagara alternative food projects : networks, discourses and nature /

This thesis undertakes an exploration of the nature of alternative food projects in Niagara. A review of various theoretical approaches to the study of food and agriculture, suggests that actor-network theory offers the most useful lens through which to understand these projects. In particular, actor-network theory facilitates non-dualistic theorisations of power and scale and a commitment to the inclusion of non-humans in the 'social' sciences. The research is based on 19 in-depth interviews with actors involved in various urban and rural projects including community supported agriculture, community gardens, chefs using local seasonal food, a winery that grows organically, the good food box, a value-added small business, and organic producers. The analysis consists of four themes. The first analytical section pays special attention to the prominence of agri-tourism in Niagara, and examines the ways in which the projects in the sample interact with agri-tourist networks. In the second section the discussion focuses on the discourses and practices of resistance among Niagara alternative food actors. The participants' interviews suggest there are more discourses of resistance toward agri-tourist than toward dominant food networks. The third section questions commodity chain theorisations of alternative food projects. In particular, this section shows how the inclusion of non-human actors in an analysis confounds conceptualisations of 'short' and 'local' chains. The final analytical section assesses relations of power in Niagara alternative food projects. Three important conclusions arise from this research. First, Niagara alternative food projects cannot be conceptualised as operating at the 'local' scale. Broadening the scope of analysis to include non-human actors, it becomes apparent that these projects actually draw on a variety of extra-local actors. They are at once local and global. Second, the projects in this sample are simultaneously part of alternative, dominant and agri-tourist networks. While Niagara alternative food projects do perform many of the roles characteristic of alternative food systems, they are also involved in practices of development, business, and class distinction. Thus, alternative food networks should not be understood as separate from and in direct opposition to dominant food networks. Despite the second conclusion, this research determines that Niagara alternative food projects have made significant strides in the reworking of power. The projects represented in this thesis do engage in resistant practices and are associated with increased levels ofjustice.

Scales, networks and uncertainty : an examination of environmental policy-making in Ontario

Through a case-study analysis of Ontario's ethanol policy, this thesis addresses a number of themes that are consequential to policy and policy-making: spatiality, democracy and uncertainty. First, I address the 'spatial debate' in Geography pertaining to the relevance and affordances of a 'scalar' versus a 'flat' ontoepistemology. I argue that policy is guided by prior arrangements, but is by no means inevitable or predetermined. As such, scale and network are pragmatic geographical concepts that can effectively address the issue of the spatiality of policy and policy-making. Second, I discuss the democratic nature of policy-making in Ontario through an examination of the spaces of engagement that facilitate deliberative democracy. I analyze to what extent these spaces fit into Ontario's environmental policy-making process, and to what extent they were used by various stakeholders. Last, I take seriously the fact that uncertainty and unavoidable injustice are central to policy, and examine the ways in which this uncertainty shaped the specifics of Ontario's ethanol policy. Ultimately, this thesis is an exercise in understanding sub-national environmental policy-making in Canada, with an emphasis on how policy-makers tackle the issues they are faced with in the context of environmental change, political-economic integration, local priorities, individual goals, and irreducible uncertainty.

Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.