Computer Science - Computer Science and Game Theory Publications (50)


Computer Science - Computer Science and Game Theory Publications

Cloud computing has reached significant maturity from a systems perspective, but currently deployed solutions rely on rather basic economics mechanisms that yield suboptimal allocation of the costly hardware resources. In this paper we present Economic Resource Allocation (ERA), a complete framework for scheduling and pricing cloud resources, aimed at increasing the efficiency of cloud resources usage by allocating resources according to economic principles. The ERA architecture carefully abstracts the underlying cloud infrastructure, enabling the development of scheduling and pricing algorithms independently of the concrete lower-level cloud infrastructure and independently of its concerns. Read More

Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today's life. They have facilitated information dissemination in ways that have been beneficial for their users but they are often used strategically in order to spread information that only serves the objectives of particular users. These properties have inspired a revision of classical opinion formation models from sociology using game-theoretic notions and tools. Read More

We show that the problem of finding an optimal bundle-pricing for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and the optimal solution is guaranteed to be a simple one: the seller picks a price for the grand bundle and a price for each individual item; the buyer can purchase either the grand bundle at the given price or any bundle of items at their total individual prices. We refer to this simple and natural family of pricing schemes as discounted item-pricings. In addition to the hardness result, we show that when the distributions are i. Read More

LTE in unlicensed spectrum (LTE-U) is a promising approach to overcome the wireless spectrum scarcity. However, to reap the benefits of LTE-U, a fair coexistence mechanism with other incumbent WiFi deployments is required. In this paper, a novel deep learning approach is proposed for modeling the resource allocation problem of LTE-U small base stations (SBSs). Read More

The paper defines a family of nested non-cooperative simultaneous finite games to study coalition structure formation with intra and inter-coalition externalities. Every game has two outcomes - an allocation of players over coalitions and a payoff profile for every player. Every game in the family has an equilibrium in mixed strategies. Read More

Zero automata are a probabilistic extension of parity automata on infinite trees. The satisfiability of a certain probabilistic variant of mso, called tmso + zero, reduces to the emptiness problem for zero automata. We introduce a variant of zero automata called nonzero automata. Read More

Advertisement (ad) options have been recently studied as a novel guaranteed delivery (GD) system in online advertising. In essence, an ad option is a contract that gives an advertiser a right but not obligation to enter into transactions to purchase ad inventories such as page views or link clicks from a specific slot at one or multiple pre-specified prices in a specific future period. Compared to guaranteed contracts, the advertiser pays a lower upfront fee but can have greater flexibility and more control in advertising. Read More

With the increasing interest in the use of millimeter wave bands for 5G cellular systems comes renewed interest in resource sharing. Properties of millimeter wave bands such as massive bandwidth, highly directional antennas, high penetration loss, and susceptibility to shadowing, suggest technical advantages to spectrum and infrastructure sharing in millimeter wave cellular networks. However, technical advantages do not necessarily translate to increased profit for service providers, or increased consumer surplus. Read More

In this paper, we study the notion of admissibility for randomised strategies in concurrent games. Intuitively, an admissible strategy is one where the player plays `as well as possible', because there is no other strategy that dominates it, i.e. Read More

Critical infrastructure protection (CIP) is envisioned to be one of the most challenging security problems in the coming decade. One key challenge in CIP is the ability to allocate resources, either personnel or cyber, to critical infrastructures with different vulnerability and criticality levels. In this work, a contract-theoretic approach is proposed to solve the problem of resource allocation in critical infrastructure with asymmetric information. Read More

In this work, we study the social learning problem, in which agents of a networked system collaborate to detect the state of the nature based on their private signals. A novel distributed graphical evolutionary game theoretic learning method is proposed. In the proposed game-theoretic method, agents only need to communicate their binary decisions rather than the real-valued beliefs with their neighbors, which endows the method with low communication complexity. Read More

We investigate approximately optimal mechanisms in settings where bidders' utility functions are non-linear; specifically, convex, with respect to payments (such settings arise, for instance, in procurement auctions for energy). We provide constant factor approximation guarantees for mechanisms that are independent of bidders' private information (i.e. Read More

In this paper, I summarize our work on online fair division. In particular, I present two models for online fair division: (1) one existing model for fair division in food banks and (2) one new model for fair division of deceased organs to patients. I further discuss simple mechanisms for these models that allocate the resources as they arrive to agents. Read More

This paper reconsiders the problem of the absent-minded driver who must choose between alternatives with different payoff with imperfect recall and varying degrees of knowledge of the system. The classical absent-minded driver problem represents the case with limited information and it has bearing on the general area of communication and learning, social choice, mechanism design, auctions, theories of knowledge, belief, and rational agency. Within the framework of extensive games, this problem has applications to many artificial intelligence scenarios. Read More

Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, e.g., those who struggle with contingent reasoning [Li, 2015]. Read More

Recent work on follow the perturbed leader (FTPL) algorithms for the adversarial multi-armed bandit problem has highlighted the role of the hazard rate of the distribution generating the perturbations. Assuming that the hazard rate is bounded, it is possible to provide regret analyses for a variety of FTPL algorithms for the multi-armed bandit problem. This paper pushes the inquiry into regret bounds for FTPL algorithms beyond the bounded hazard rate condition. Read More

The beyond worst-case synthesis problem was introduced recently by Bruy\`ere et al. [BFRR14]: it aims at building system controllers that provide strict worst-case performance guarantees against an antagonistic environment while ensuring higher expected performance against a stochastic model of the environment. Our work extends the framework of [BFRR14] and follow-up papers, which focused on quantitative objectives, by addressing the case of $\omega$-regular conditions encoded as parity objectives, a natural way to represent functional requirements of systems. Read More

In this paper we introduce the novel framework of distributionally robust games. These are multi-player games where each player models the state of nature using a worst-case distribution, also called adversarial distribution. Thus each player's payoff depends on the other players' decisions and on the decision of a virtual player (nature) who selects an adversarial distribution of scenarios. Read More

Strategic decision making involves affective and cognitive functions like reasoning, cognitive and emotional empathy which may be subject to age and gender differences. However, empathy-related changes in strategic decision-making and their relation to age, gender and neuropsychological functions have not been studied widely. In this article, we study a one-shot prisoner dilemma from a psychological game theory viewpoint. Read More

Until now mean-field-type game theory was not focused on cognitively-plausible models of choices in humans, animals, machines, robots, software-defined and mobile devices strategic interactions. This work presents some effects of users' psychology in mean-field-type games. In addition to the traditional "material" payoff modelling, psychological patterns are introduced in order to better capture and understand behaviors that are observed in engineering practice or in experimental settings. Read More

We study a model for switching strategies in the Prisoner's Dilemma game on adaptive networks of player pairings that coevolve as players attempt to maximize their return. We use a node-based strategy model with each player following one strategy (cooperate or defect) at a time with all of its neighbors. We improve on the existing pair approximation (PA) model for this system by using approximate master equations (AMEs). Read More

Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate the acceleration of first-order methods for solving extensive-form games through better design of the dilated entropy function---a class of distance-generating functions related to the domains associated with the extensive-form games. Read More

We suggest a general method for inferring players' values from their actions in repeated games. The method extends and improves upon the recent suggestion of (Nekipelov et al., EC 2015) and is based on the assumption that players are more likely to exhibit sequences of actions that have lower regret. Read More

All-pay auctions, a common mechanism for various human and agent interactions, suffers, like many other mechanisms, from the possibility of players' failure to participate in the auction. We model such failures, and fully characterize equilibrium for this class of games, we present a symmetric equilibrium and show that under some conditions the equilibrium is unique. We reveal various properties of the equilibrium, such as the lack of influence of the most-likely-to-participate player on the behavior of the other players. Read More

The capacity of wireless networks is a classic and important topic of study. Informally, the capacity of a network is simply the total amount of information which it can transfer. In the context of models of wireless radio networks, this has usually meant the total number of point-to-point messages which can be sent or received in one time step. Read More

This paper studies an auction design problem for a seller to sell a commodity in a social network, where each individual (the seller or a buyer) can only communicate with her neighbors. The challenge to the seller is to design a mechanism to incentivize the buyers, who are aware of the auction, to further propagate the information to their neighbors so that more buyers will participate in the auction and hence, the seller will be able to make a higher revenue. We propose a novel auction mechanism, called information diffusion mechanism (IDM), which incentivizes the buyers to not only truthfully report their valuations on the commodity to the seller, but also further propagate the auction information to all their neighbors. Read More

Boolean games are a succinct representation of strategic games wherein a player seeks to satisfy a formula of propositional logic by selecting a truth assignment to a set of propositional variables under his control. The framework has proven popular within the multiagent community, however, almost invariably, the work to date has been restricted to the case of pure strategies. Such a focus is highly restrictive as the notion of randomised play is fundamental to the theory of strategic games -- even very simple games can fail to have pure-strategy equilibria, but every finite game has at least one equilibrium in mixed strategies. Read More

We consider the problem of binary prediction with expert advice in settings where experts have agency and seek to maximize their credibility. This paper makes three main contributions. First, it defines a model to reason formally about settings with selfish experts, and demonstrates that "incentive compatible" (IC) algorithms are closely related to the design of proper scoring rules. Read More

The use of unmanned aerial vehicles (UAVs) as delivery systems of online goods is rapidly becoming a global norm, as corroborated by Amazon's "Prime Air" and Google's "Project Wing" projects. However, the real-world deployment of such drone delivery systems faces many cyber-physical security challenges. In this paper, a novel mathematical framework for analyzing and enhancing the security of drone delivery systems is introduced. Read More

Matrix games like Prisoner's Dilemma have guided research on social dilemmas for decades. However, they necessarily treat the choice to cooperate or defect as an atomic action. In real-world social dilemmas these choices are temporally extended. Read More

We study the game known as Subset Takeaway (Chomp on a hypercube), and give unexpected answers to questions of Gale and Neyman. We show that the number of linear extensions of the lattice of a 7-cube is 630470261306055898099742878692134361829979979674711225065761605059425237453564989302659882866111738567871048772795838071474370002961694720 (roughly $6.3 \cdot 10^{137}$). Read More

The global move towards producing and consuming energy in a clean, efficient and economical way, along with the need for meeting rising consumer demand has led to significant advancements in the design of the smart grid infrastructure. However, the potential of the smart grid remains limited without the integration of renewable energy sources. Energy trading is one way forward. Read More

Motivated by the recently launched mobile data trading markets (e.g., China Mobile Hong Kong's 2nd exChange Market), in this paper we study the mobile data trading problem under the future data demand uncertainty. Read More

This paper studies scenarios of cyclic dominance in a coevolutionary spatial model in which game strategies and links between agents adaptively evolve over time. The Optional Prisoner's Dilemma (OPD) game is employed. The OPD is an extended version of the traditional Prisoner's Dilemma where players have a third option to abstain from playing the game. Read More

We study a static game played by a finite number of agents, in which agents are assigned independent and identically distributed random types and each agent minimizes its objective function by choosing from a set of admissible actions that depends on its type. The game is anonymous in the sense that the objective function of each agent depends on the actions of other agents only through the empirical distribution of their type-action pairs. We study the asymptotic behavior of Nash equilibria, as the number of agents tends to infinity, first by deriving laws of large numbers characterizes almost sure limit points of Nash equilibria in terms of so-called Cournot-Nash equilibria of an associated nonatomic game. Read More

Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short proof of correctness of their algorithm. Read More

Motivated by online display ad exchanges, we study a setting in which an exchange repeatedly interacts with bidders who have quota, making decisions about which subsets of bidders are called to participate in ad-slot-specific auctions. A bidder with quota cannot respond to more than a certain number of calls per second. In practice, random throttling is the principal solution by which these constraints are enforced. Read More

A strong assumption in Bayesian mechanism design is that the distributions of the players' private types are common knowledge to the designer and the players--the common prior assumption. An important problem that has received a lot of attention in both economics and computer science is to repeatedly weaken this assumption in game theory--the "Wilson's Doctrine". In this work we consider, for the first time in the literature, multi-item auctions where the knowledge about the players' value distributions is scattered among the players and the seller. Read More

In this paper, we study a large-scale distributed coordination problem and propose efficient adaptive strategies to solve the problem. The basic problem is to allocate finite number of resources to individual agents such that there is as little congestion as possible and the fraction of unutilized resources is reduced as far as possible. In the absence of a central planner and global information, agents can employ adaptive strategies that uses only finite knowledge about the competitors. Read More

A mixed manna contains goods (that everyone likes), bads (that everyone dislikes), as well as items that are goods to some agents, but bads or satiated to others. If all items are goods and utility functions are homothetic, concave (and monotone), the Competitive Equilibrium with Equal Incomes maximizes the Nash product of utilities: hence it is welfarist (determined utility-wise by the feasible set of profiles), single-valued and easy to compute. We generalize the Gale-Eisenberg Theorem to a mixed manna. Read More

We study Cournot competition among firms in a networked marketplace that is centrally managed by a market maker. In particular, we study a situation in which a market maker facilitates trade between geographically separate markets via a constrained transport network. Our focus is on understanding the consequences of the design of the market maker and on providing tools for optimal design. Read More

There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, existing security game models typically either assume additive utility functions, or that the attacker can attack only one target. Such assumptions lead to tractable analysis, but miss key inherent dependencies that exist among different targets in current complex networks. Read More

We present a three player Bayesian game for which there is no epsilon equilibria in Borel measurable strategies for small enough epsilon, however there are non-measurable equilibria. Read More

The concept of an evolutionarily stable strategy (ESS), introduced by Smith and Price, is a refinement of Nash equilibrium in 2-player symmetric games in order to explain counter-intuitive natural phenomena, whose existence is not guaranteed in every game. The problem of deciding whether a game possesses an ESS has been shown to be $\Sigma_{2}^{P}$-complete by Conitzer using the preceding important work by Etessami and Lochbihler. The latter, among other results, proved that deciding the existence of ESS is both NP-hard and coNP-hard. Read More

This paper studies optimal communication and coordination strategies in cyber-physical systems for both defender and attacker within a game-theoretic framework. We model the communication network of a cyber-physical system as a sensor network which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noises. The sensors communicate with the estimator over a coherent Gaussian multiple access channel. Read More

We study two notions of stability in multiwinner elections that are based on the Condorcet criterion. The first notion was introduced by Gehrlein: A committee is stable if each committee member is preferred to each non-member by a (possibly weak) majority of voters. The second notion is called local stability (introduced in this paper): A size-$k$ committee is locally stable in an election with $n$ voters if there is no candidate $c$ and no group of more than $\frac{n}{k+1}$ voters such that each voter in this group prefers $c$ to each committee member. Read More

In networking and computing, resource allocation is typically addressed using classical sharing protocols as, for instance, the proportional division rule, the max-min fair allocation , or other solutions inspired by cooperative game theory. In this paper, we argue that, describing the resource allocation problem as a cooperative game, such classical resource allocation approaches, as well as associated notions of fairness, show important limitations. We identify in the individual satisfaction rate the key aspect of the challenge of defining a new notion of fairness and, consequently, a resource allocation algorithm more appropriate for the cooperative context. Read More

We consider $\epsilon$-equilibria notions for constant value of $\epsilon$ in $n$-player $m$-actions games where $m$ is a constant. We focus on the following question: What is the largest grid size over the mixed strategies such that $\epsilon$-equilibrium is guaranteed to exist over this grid. For Nash equilibrium, we prove that constant grid size (that depends on $\epsilon$ and $m$, but not on $n$) is sufficient to guarantee existence of weak approximate equilibrium. Read More

Congestion games constitute an important class of non-cooperative games which was introduced by Rosenthal in 1973. In recent years, several extensions of these games were proposed to incorporate aspects that are not captured by the standard model. Examples of such extensions include the incorporation of risk sensitive players, the modeling of altruistic player behavior and the imposition of taxes on the resources. Read More