We introduce a roommate market model, in which 2n people need to be assigned to n rooms, with two people in each room. Each person has a valuation to each room, as well as a valuation to each of other people as a roommate. Each room has a rent shared by the two people living in the room, and we need to decide who live together in which room and how much each should pay. Various solution concepts on stability and envy-freeness are proposed, with their existence studied and the computational complexity of the corresponding search problems analyzed. In particular, we show that maximizing the social welfare is NP-hard, and we give a polynomial time algorithm that achieves at least 2/3 of the maximum social welfare. Finally, we demonstrate a pricing scheme that can achieve envy-freeness for each room.

Strong Stackelberg Equilibrium (SSE) is a fundamental solution concept in game theory in which one player commits to a strategy, while the other player observes this commitment and plays a best response. We present a new algorithm for computing SSE for two-player extensive-form general-sum games with imperfect information (EFGs) where computing SSE is an NP-hard problem. Our algorithm is based on a correlated version of SSE, known as Stackelberg Extensive-Form Correlated Equilibrium (SEFCE). Our contribution is therefore twofold: (1) we give the first linear program for computing SEFCE in EFGs without chance, (2) we repeatedly solve and modify this linear program in a systematic search until we arrive to SSE. Our new algorithm outperforms the best previous algorithms by several orders of magnitude.

An effective way of preventing attacks in secure areas is to screen for threats (people, objects) before entry, e.g., screening of airport passengers. However, screening every entity at the same level may be both ineffective and undesirable. The challenge then is to find a dynamic approach for randomized screening, allowing for more effective use of limited screening resources, leading to improved security. We address this challenge with the following contributions: (1) a threat screening game (TSG) model for general screening domains; (2) an NP-hardness proof for computing the optimal strategy of TSGs; (3) a scheme for decomposing TSGs into subgames to improve scalability; (4) a novel algorithm that exploits a compact game representation to efficiently solve TSGs, providing the optimal solution under certain conditions; and (5) an empirical comparison of our proposed algorithm against the current state-of-the-art optimal approach for large-scale game-theoretic resource allocation problems.

A large body of literature deals with the so-called cake cutting So how would strategic agents behave when faced with problem -- a misleadingly childish metaphor for the the cut and choose protocol? A standard way of answering challenging and important task of fairly dividing a heterogeneous this question employs the notion of Nash equilibrium: each divisible good among multiple agents (see the recent agent would use a strategy that is a best response to the other survey by Procaccia (2013) and the books by Brams agent's strategy. To set up a Nash equilibrium, suppose that and Taylor (1996) and Robertson and Webb (1998)). In particular, the first agent cuts two pieces that the second agent values there is a significant amount of AI work on cake cutting equally; the second agent selects its more preferred piece, (Procaccia 2009; Caragiannis, Lai, and Procaccia 2011; and the one less preferred by the first agent in case of a tie. Brams et al. 2012; Bei et al. 2012; Aumann, Dombb, Clearly, the second agent cannot gain from deviating, as it is and Hassidim 2013; Kurokawa, Lai, and Procaccia 2013; selecting a piece that is at least as preferred as the other. As Brânzei, Procaccia, and Zhang 2013; Brânzei and Miltersen for the first agent, if it makes its preferred piece even bigger, 2013; Chen et al. 2013; Balkanski et al. 2014; Brânzei the second agent would choose that piece, making the and Miltersen 2015; Segal-Halevi, Hassidim, and Aumann first agent worse off. Interestingly enough, in this equilibrium 2015), which is closely intertwined with emerging realworld the tables are turned; now it is the second agent who applications of fair division more broadly (Goldman is getting exactly half of its value for the whole cake, while and Procaccia 2014; Kurokawa, Procaccia, and Shah 2015).

We study efficient algorithms for a natural learning problem in markets. There is one seller with m divisible goods and n buyers with unknown individual utility functions and budgets of money. The seller can repeatedly announce prices and observe aggregate demand bundles requested by the buyers. The goal of the seller is to learn the utility functions and budgets of the buyers. Our scenario falls into the classic domain of ''revealed preference'' analysis. Problems with revealed preference have recently started to attract increased interest in computer science due to their fundamental nature in understanding customer behavior in electronic markets. The goal of revealed preference analysis is to observe rational agent behavior, to explain it using a suitable model for the utility functions, and to predict future agent behavior. Our results are the first polynomial-time algorithms to learn utility and budget parameters via revealed preference queries in classic Fisher markets with multiple buyers. Our analysis concentrates on linear, CES, and Leontief markets, which are the most prominent classes studied in the literature. Some of our results extend to general Arrow-Debreu exchange markets.

We study an important crowdsourcing setting where agents evaluate one another and, based on these evaluations, a subset of agents are selected. This setting is ubiquitous when peer review is used for distributing awards in a team, allocating funding to scientists, and selecting publications for conferences. The fundamental challenge when applying crowdsourcing in these settings is that agents may misreport their reviews of others to increase their chances of being selected. We propose a new strategyproof (impartial) mechanism called Dollar Partition that satisfies desirable axiomatic properties. We then show, using a detailed experiment with parameter values derived from target real world domains, that our mechanism performs better on average, and in the worst case, than other strategyproof mechanisms in the literature.

In a landmark paper in the mechanism design literature, Cremer and McLean (1985) (CM for short) show that when a bidder’s valuation is correlated with an external signal, a monopolistic seller is able to extract the full social surplus as revenue. In the original paper and subsequent literature, the focus has been on ex-post incentive compatible (or IC) mechanisms, where truth telling is an ex-post Nash equilibrium. In this paper, we explore the implications of Bayesian versus ex-post IC in a correlated valuation setting. We generalize the full extraction result to settings that do not satisfy the assumptions of CM. In particular, we give necessary and sufficient conditions for full extraction that strictly relax the original conditions given in CM. These more general conditions characterize the situations under which requiring ex-post IC leads to a decrease in expected revenue relative to Bayesian IC. We also demonstrate that the expected revenue from the optimal ex-post IC mechanism guarantees at most a (|Θ| + 1)/4 approximation to that of a Bayesian IC mechanism, where |Θ| is the number of bidder types. Finally, using techniques from automated mechanism design, we show that, for randomly generated distributions, the average expected revenue achieved by Bayesian IC mechanisms is significantly larger than that for ex-post IC mechanisms.

We study the problem of computing Nash equilibria of zero-sum games.Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battlefields with the goal of winning (i.e., having more troops in) a majority. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S presidential election, to innovative technology competitions, toadvertisement, to sports.However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible.Indeed, despite its importance, only few solutions for special variants of the problem are known. In this paper we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games. In addition to Colonel Blotto, we also show how to compute equilibria in an infinite-strategy variant called the General Lotto game; this involves showing how to prune the strategy space to a finite subset before applying our reduction. We also consider the class of dueling games, first introduced by Immorlica et al. (2011). We show that our approach provably extends the class of dueling games for which equilibria can be computed: we introduce a new dueling game, the matching duel, on which prior methods fail to be computationally feasible but upon which our reduction can be applied.

This paper studies the impact of Time-Of-Use (TOU) tariffs in a competitive electricity market place. Specifically, it focuses on the question of how should an autonomous broker agent optimize TOU tariffs in a competitive retail market, and what is the impact of such tariffs on the economy. We formalize the problem of TOU tariff optimization and propose an algorithm for approximating its solution. We extensively experiment with our algorithm in a large-scale, detailed electricity retail markets simulation of the Power Trading Agent Competition (Power TAC) and: 1) find that our algorithm results in 15% peak-demand reduction, 2) find that its peak-flattening results in greater profit and/or profit-share for the broker and allows it to win against the 1st and 2nd place brokers from the Power TAC 2014 finals, and 3) analyze several economic implications of using TOU tariffs in competitive retail markets.

With the rapid development of urbanization and public transportation system, the number of traffic accidents have significantly increased globally over the past decades and become a big problem for human society. Facing these possible and unexpected traffic accidents, understanding what causes traffic accident and early alarms for some possible ones will play a critical role on planning effective traffic management. However, due to the lack of supported sensing data, research is very limited on the field of updating traffic accident risk in real-time. Therefore, in this paper, we collect big and heterogeneous data (7 months traffic accident data and 1.6 million users' GPS records) to understand how human mobility will affect traffic accident risk. By mining these data, we develop a deep model of Stack denoise Autoencoder to learn hierarchical feature representation of human mobility. And these features are used for efficient prediction of traffic accident risk level. Once the model has been trained, our model can simulate corresponding traffic accident risk map with given real-time input of human mobility. The experimental results demonstrate the efficiency of our model and suggest that traffic accident risk can be significantly more predictable through human mobility.