I study single-agent learning problems under memory constraints. The first chapter studies time consistency issues in a general class of stationary dynamic environments called Markov Decision Processes with Partial Observation. The agent is restricted to use plans with a fixed memory size, that is, strategies that can be implemented by a finite automaton of fixed size. As this induces a game with absent-mindedness, the ex-ante optimal strategy may not be time-consistent. I find that any ex-ante optimal bounded memory strategy satisfies a weaker form of time consistency, multi-self consistency, a la Piccione & Rubinstein 1997). This means that the agent would not want to deviate from the ex-ante optimal strategy for the current period, assuming he will follow the original strategy from tomorrow on. In the second chapter, I analyze the effects of memory limitations on the endogenous learning behavior of an agent in a standard two-armed bandit problem. I find that under memory constraints, the inclination to choose the currently better alternative does not constrain learning: there is no exploitation/exploration trade-off. Optimally, the memory states reflect the magnitude of the relative ranking of alternatives. After a high payoff from one of the alternatives, the agent optimally moves to a memory state with more pessimistic beliefs on the other, even though no information about the latter alternative is received. For the case where one alternative is substantially more informative than the other, he chooses the latter only for myopic exploitation purposes, and ignores any information about it, suggesting specialization in learning. For the special case with one known safe) alternative, a sufficiently patient agent never ceases experimentation and tries the unknown alternative at least occasionally after any history； this is counter to what theory predicts with unbounded memory, but in agreement with experimental findings. Furthermore, he chooses the safe alternative with more optimistic beliefs than the optimal unbounded memory) cutoff belief, again in conformity with experimental evidence.

Geographic routing has become a popular routing protocol in mobile ad hoc networks (MANETs) because of its simplicity and low overhead. Recent research has recognized its applicability in vehicular mobile ad hoc networks (VANETs) without considering much the particular characteristics in such an environment. Characteristics unique to VANETs such as rapidly and dynamically changing network topology, road-constrained mobility, regular traffic pattern, ample power and storage, intermittent connectivity, and high signal interference from other communicating vehicles and obstacles motivate detailed study into the improvements and optimizations of the existing geographic routing to bring about its adoption in VANETs. To advance geographic routing in VANETs, the thesis first explains the choice of geographic routing amid numerous MANET routing protocols in VANETs. It then makes major contributions of improvements of geographic routing in light of VANETs’ environmental characteristics. These improvements range from eliminating the overhead of planarization and the occurrence of cross-link induced routing loops to cutting the routing inefficiency of the routing’s standard mode of operations. In addition, opportunistic forwarding was utilized to improve the packet delivery. Furthermore, geographic routing was made intelligent to avoid voids and expensive backtracking by using connectivity information obtained proactively in a peer-to-peer fashion. Delay tolerant techniques are also considered to counter intermittent connectivity. Building improvement on top of the other, the paper presents a fully integrated geographic routing solution suitable for vehicular ad hoc networks.

Pedestrian crowd simulation explores crowd behaviors in virtual environments. It is extensively studied in many areas, such as safety and civil engineering, transportation, social science, entertainment industry and so on. As a common phenomenon in pedestrian crowds, grouping can play important roles in crowd behaviors. To achieve more realistic simulations, it is important to support group modeling in crowd behaviors. Nevertheless, group modeling is still an open and challenging problem. The influence of groups on the dynamics of crowd movement has not been incorporated into most existing crowd models because of the complexity nature of social groups. This research develops a framework for group modeling in agent-based pedestrian crowd simulations. The framework includes multiple layers that support a systematic approach for modeling social groups in pedestrian crowd simulations. These layers include a simulation engine layer that provides efficient simulation engines to simulate the crowd model； a behavior-based agent modeling layers that supports developing agent models using the developed BehaviorSim simulation software； a group modeling layer that provides a well-defined way to model inter-group relationships and intragroup connections among pedestrian agents in a crowd； and finally a context modeling layer that allows users to incorporate various social and psychological models into the study of social groups in pedestrian crowd. Each layer utilizes the layer below it to fulfill its functionality, and together these layers provide an integrated framework for supporting group modeling in pedestrian crowd simulations. To our knowledge this work is the first one to focus on a systematic group modeling approach for pedestrian crowd simulations. This systematic modeling approach allows users to create social group simulation models in a well-defined way for studying the effect of social and psychological factors on crowds grouping behavior. To demonstrate the capability of the group modeling framework, we developed an application of dynamic grouping for pedestrian crowd simulations.

We apply computer science techniques to try to solve a selection of problems that arise in economics and electronic commerce. The problems we address and our results are summarized below. The first problem is from the field of Mechanism Design. The goal is to find a procedure for allocating identical items among agents with private values in the manner that maximizes the total utility of the agents. We approach this problem computationally: solutions are found algorithmically rather than through mathematical derivations. Our computational approach yields a nearly optimal solution greatly improving prior results. In the case with 3 agents and 2 items, we were able to find a provably optimal solution. Next, we address a game-theoretic problem of finding Nash Equilibria in auctions. We investigate when a computational procedure finds an equilibrium in first and second price auctions with discrete bids and values. The rest of the thesis is devoted to automated decision making in electronic commerce domains. Three domains are considered: sponsored search, supply chain management, and simultaneous auctions. The last two domains are studied in the context of the SCM and Travel divisions of the Trading Agent Competition TAC). Our contributions to automated decision making are both practical and theoretical. On the practical side, the bidding strategy we designed for sponsored search auctions is currently being used by a large advertiser. Our work on TAC Travel culminated in winning the competition in 2006. In the TAC SCM competition, the agent we built was among the top 5 out of over 20 agents almost every year of the competition. For theoretical contributions, we characterized optimal strategies for bidding in simultaneous auctions when prices are known and complemented this analysis with an empirical comparison of different strategies. We identified that bidding decisions in TAC SCM can be modeled as a non-linear knapsack problem and proved the asymptotic optimality of a greedy algorithm for solving a class of non-linear knapsack problems.

Strategyproof mechanisms provide robust equilibria with minimal assumptions about knowledge and rationality, but can be unachievable in combination with other desirable properties, such as budget-balance, stability against deviations by coalitions, and computational tractability. We thus seek a relaxation of this solution concept, and propose several definitions for general settings with private and quasi-linear utility. We are then able to describe the ideal mechanism according to these definitions by formulating the design problem as a constrained optimization problem. Discretization and statistical sampling allow us to reify this problem as a linear program to find ideal mechanisms in simple settings. However, this constructive approach is not scalable. We thus advocate for using the quantiles of the ex post unilateral gain from deviation as a method for capturing useful information about the incentives in a mechanism. Where this also is too expensive, we propose using the KL-Divergence between the payoff distribution at truthful reports and the distribution under a strategyproof “reference” mechanism that solves a problem relaxation. We prove bounds that relate such quasimetrics to our definitions of approximate incentive compatibility； we demonstrate empirically in combinatorial market settings that they are informative about the eventual equilibrium, where simple regret-based metrics are not. We then design, implement, and analyze a mechanism for just such an overconstrained setting: the first fully expressive, iterative combinatorial exchange ICE). The exchange incorporates a tree-based bidding language TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different, trades and refine these bounds across rounds. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. We are able to prove efficiency under truthful bidding despite using linear pricing that can only approximate competitive equilibrium. Finally, we apply several key concepts from this general mechanism in a combinatorial market for finding the right balance between power and performance in allocating computational resources in a data center.

In this thesis, we take a game-theoretic approach to modeling behavior in peer production systems. Our goal in modeling such systems is both to capture the current behavior of the system and to understand how changes in the incentive structure can lead to more desirable system-wide outcomes. We focus on both modeling specific systems as well as general models that are applicable to a wide variety of systems. The first system that we study is the ESP game. The ESP game is a popular game on the web for labeling images. During play of the ESP game, it seems that users coordinate on easy words. We provide a game-theoretic model that supports this observation. We also study the effect of alternate agent preferences on the equilibrium outcomes and provide a class of reward functions that allow for coordination on more descriptive words as the equilibrium outcome. Our equilibrium analysis focuses on all valuations satisfying a given preference model. The second system that we focus on is Yahoo! Answers. In Yahoo! Answers, it appears that under the “Best Answer” method of assigning points, users prefer to answer later rather than sooner. We provide a simple game-theoretic model of Yahoo! Answers and present equilibrium analysis that supports this observation. We propose two new methods of assigning points, the Approval Voting Scoring Rule and the Proportional Share Scoring Rule, and show that each can improve the equilibrium outcome. We provide an axiomatic characterization showing that no “reasonable” scoring rule can isolate the best possible equilibrium outcome. Finally, we study the combinatorial agency problem introduced by Babaioff et al. 2006). The combinatorial agency model is a variant of the classical principal-agent model of economics and is relevant to many crowdsourcing systems. We provide a characterization of the optimal contract as a function of the principals value for the class of threshold functions. We study the Price of Unaccountability, or the relative loss to the principal due to the strategic behavior of the agents. We compare the Price of Unaccountability across various technology functions and find drastically different results depending on the technology function.

The goal of this dissertation is to understand how network plays a role in shaping certain strategic interactions, in particular biased voting and bargaining, on networks； and to understand how interactions can be made secure when they are constrained by the network topology. Our works take an interdisciplinary approach by drawing on theories and models from economics, sociology, as well as computer science, and using methodologies that include both theories and behavioral experiments. First, we consider biased voting in networks, which models distributed collective decision making processes where individuals in a network must balance between their private biases or preferences with a collective goal of consensus. Our study of this problem is two-folded. On the theoretical side, we start by introducing a diffusion model called biased voter model, which is a natural extension of the classic voter model. Among other results, we show in the presence of biases, no matter how small, there exists certain networks where it takes exponential time to converge to a consensus through distributed interaction in networks. This is a stark and interesting contrast to the well-known result that it always takes polynomial time to converge in the voter model, when there are no biases. On the experimental side, a group human subjects were arranged in various carefully designed virtual networks to solve the biased voting problem. Along with analyses of how collective and individual performance vary with network structure and incentives generally, we find there are well-studied network topologies in which the minority preference consistently wins globally, and that the presence of “extremist” individuals, or the awareness of opposing incentives, reliably improve collective performance Second, we consider bargaining in networks, which has long been studied by economists and sociologists. A basic premise behind the many theoretical study of bargaining in networks is that pure topological differences in agents network positions endow them with different bargaining power. Complementary to these theories, we conduct a series of controlled behavioral experiments, where human subjects were arranged in various carefully designed virtual networks to playing bargaining games. Along with other findings of how individual and collective performance vary with network structures and individual playing styles, we find that the number of neighbors one can negotiate with confers bargaining power, whereas the limit on the number of deals one can close undermines it, and we find that competitions from distant parts of the network, though invisible locally, also play a significant and subtle role in shaping bargaining powers. And last, we consider the question of how interactions in networks can be made secure. Traditional methods and tools from cryptography, for example secure multi-party computation, can be applied only if each party can talk to everyone else directly； but cannot be directly applied if interactions are distributed over a network without completely eradicating the distributed nature. We develop a general compiler that turns each algorithm from a broad class collectively known as message-passing algorithms into a secure one that has exactly the same functionality and communication pattern. And we show a fundamental trade-off between preserving the distributed nature of communication and the level of security one can hope for. vi

Abstract Penalization or regularization is an important integration to the traditional regression method to improve prediction accuracy, speed and adaptability for various problems. Lasso type L1-regularization methods and its variants can reduce the complexity of high dimensional data by feature selection as well as coefficient shrinkage. Fan et al. shows that using an L1-penalty, which he calls “gross-exposure” constraint on the weights in a portfolio, has significant advantages. In particular it can reduce risk and because the L1 penalty sets coefficients to zero, many fewer assets are needed in the portfolio, and are therefore suitable for large-scale portfolio optimization problems. Fan et al. formulated this constrained portfolio risk minimization problem into a convex optimization problem and solved the problem by an efficient least angle regression (LARS) optimizer. However, the implementation of LARS used an approximation to the true optimization criterion. To address this problem, we propose a customized coordinate descent portfolio optimization procedure (CCDPO). The coordinate wise updating scheme can optimize all coefficients of the allocation vector faster than LARS. The warming-up and re-initialization steps in CCDPO prevent the dominant coefficients from growing to extreme values. CCDPO uses the advantage of coefficients scarcity to reduce the optimization load and achieves fast speed. To study the performance of CCDPO, we implement a factor-based covariance estimator for data simulation, and a data integration website for collecting real-life stock price quotes. The optimization results on the simulated data show that CCDPO significantly reduces the portfolio risk. And the penalty factor lambda controls the diversity between empirical risk and actual risk in a similar fashion to the “gross-exposure” constraint. The ex-post analysis of the real-life Yahoo! Finance data indicates that portfolios optimized by CCDPO have significant less risk than those optimized by the non-constrained optimizer.

This dissertation proposes three models that can be use to improve the estimation, contingency planning and tracking of agile software development projects. The first of the three models, a fractional paired comparison method improves on the scalability of the method by reducing the number of comparisons required to estimate a set of user stories without a proportional loss of reliability. The second model postulates that contingency funds should be calculated at the level necessary to implement recovery actions midway through the project. This is not the same calculation as what it would have cost had the same work been planned from the beginning of the project. The third model adapts the use of the Line of Balance Indicator to the tracking of progress in agile software development projects and provides information to ensure that the team is producing at its maximum pace. Key words: software estimation, project tracking, line of balance, calculation of contingency funds, agile development, paired comparisons

Relationships make social media social. But, not all relationships are created equal. We have colleagues with whom we correspond intensely, but not deeply； we have childhood friends we consider close, even if we fell out of touch. Social media, however, treats everybody the same: someone is either a completely trusted friend or a total stranger, with little or nothing in between. In reality, relationships fall everywhere along this spectrum, a topic social science has investigated for decades under the name tie strength, a term for the strength of a relationship between two people. Despite many compelling findings along this line of research, social media does not incorporate tie strength or its lessons. Neither does most research on large-scale social phenomena. In social network analyses, a link either exists or not. Relationships have few properties of their own. Simply put, we do not understand a basic property of relationships expressed online. This dissertation addresses this problem, merging the theories behind tie strength with the data from social media. I show how to reconstruct tie strength from digital traces in online social media, and how to apply it as a tool in design and analysis. Specifically, this dissertation makes three contributions. First, it offers a rich, high-accuracy and general way to reconstruct tie strength from digital traces, traces like recency and a messages emotional content. For example, the model can split users into strong and weak ties with nearly 89% accuracy. I argue that it also offers us a chance to rethink many of social medias most fundamental design elements. Next, I showcase an example of how we can redesign social media using tie strength: a Twitter application open to anyone on the internet which puts tie strength at the heart of its design. Through this application, called We Meddle, I show that the tie strength model generalizes to a new online community, and that it can solve real peoples practical problems with social media. Finally, I demonstrate that modeling tie strength is an important new tool for analyzing large-scale social phenomena. Specifically, I show that real-life diffusion in online networks depends on tie strength i.e., it depends on social relationships). As a body of work, diffusion studies make a big simplifying assumption: simple stochastic rules govern person-to-person transmission. How does a disease spread? With constant probability. How does a chain letter diffuse? As a branching process. I present a case where this simplifying assumption does not hold. The results challenge the macroscopic diffusion properties in todays literature, and they hint at a nest of complexity below a placid stochastic surface. It may be fair to see this dissertation as linking the online to the offline； that is, it connects the traces we leave in social media to how we feel about relationships in real life.