BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Topic overview

Computer Science and Game Theory

1864 works3913 researchers
Open mapBrowse papers

Map preview

Start with the graph, then narrow the list

1864works
3913researchers

Next steps

Use the topic as a working map

Open the full map for clusters, then return here to scan ranked papers and people.

Topic graph

See the topic as a live network

Open full explorer

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Papers in this area

24 paper(s) to start with

Showing a focused slice from 1864 total papers. Open the graph or search to expand the full area.

preprint2017arXiv

Optimal Design of Robust Combinatorial Mechanisms for Substitutable Goods

In this paper we consider multidimensional mechanism design problem for selling discrete substitutable items to a group of buyers. Previous work on this problem mostly focus on stochastic description of valuations used by the seller. However, in certain applications, no prior information regarding buyers' preferences is known. To address this issue, we consider uncertain valuations and formulate the problem in a robust optimization framework: the objective is to minimize the maximum regret. For a special case of revenue-maximizing pricing problem we present a solution method based on mixed-integer linear programming formulation.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Truthful Facility Location with Additive Errors

We address the problem of locating facilities on the $[0,1]$ interval based on reports from strategic agents. The cost of each agent is her distance to the closest facility, and the global objective is to minimize either the maximum cost of an agent or the social cost. As opposed to the extensive literature on facility location which considers the multiplicative error, we focus on minimizing the worst-case additive error. Minimizing the additive error incentivizes mechanisms to adapt to the size of the instance. I.e., mechanisms can sacrifice little efficiency in small instances (location profiles in which all agents are relatively close to one another), in order to gain more [absolute] efficiency in large instances. We argue that this measure is better suited for many manifestations of the facility location problem in various domains. We present tight bounds for mechanisms locating a single facility in both deterministic and randomized cases. We further provide several extensions for locating multiple facilities.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Rational Generating Functions and Integer Programming Games

We explore the computational complexity of computing pure Nash equilibria for a new class of strategic games called integer programming games with difference of piecewise linear convex payoffs. Integer programming games are games where players' action sets are integer points inside of polytopes. Using recent results from the study of short rational generating functions for encoding sets of integer points pioneered by Alexander Barvinok, we present efficient algorithms for enumerating all pure Nash equilibria, and other computations of interest, such as the pure price of anarchy, and pure threat point, when the dimension and number of "convex" linear pieces in the payoff functions are fixed. Sequential games where a leader is followed by competing followers (a Stackelberg--Nash setting) are also considered.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Extending Finite Memory Determinacy to Multiplayer Games

We show that under some general conditions the finite memory determinacy of a class of two-player win/lose games played on finite graphs implies the existence of a Nash equilibrium built from finite memory strategies for the corresponding class of multi-player multi-outcome games. This generalizes a previous result by Brihaye, De Pril and Schewe. We provide a number of example that separate the various criteria we explore. Our proofs are generally constructive, that is, provide upper bounds for the memory required, as well as algorithms to compute the relevant Nash equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each battlefield is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battlefields he wins. This game is commonly used for analyzing a wide range of applications such as the U.S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for finding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for finding the optimal strategies. They first model the problem by a Linear Program (LP) and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it is highly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension technique

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Perturbation Robust Stable Matching

A well known result states that stability criterion for matchings in two-sided markets doesn't ensure uniqueness. This opens the door for a moral question with regard to the optimal stable matching from a social point of view. Here, a new notion of social optimality is proposed. Its novelty is its ability to take into account the possibility of agents to leave the matching after it has already been established. To formalize this real-life scenario, this work includes a well-defined probability model and a social cost function that maintain the general guidelines of leaving-agents situations. Finally, efficient algorithms to optimize this function are developed either under stability constraint or without it.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Comprehensive Survey of Potential Game Approaches to Wireless Networks

Potential games form a class of non-cooperative games where unilateral improvement dynamics are guaranteed to converge in many practical cases. The potential game approach has been applied to a wide range of wireless network problems, particularly to a variety of channel assignment problems. In this paper, the properties of potential games are introduced, and games in wireless networks that have been proven to be potential games are comprehensively discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders

A seminal result of Bulow and Klemperer [1989] demonstrates the power of competition for extracting revenue: when selling a single item to $n$ bidders whose values are drawn i.i.d. from a regular distribution, the simple welfare-maximizing VCG mechanism (in this case, a second price-auction) with one additional bidder extracts at least as much revenue in expectation as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a {\em prior-independent} mechanism, where the seller possesses no information about the distribution, and yet, by recruiting one additional bidder it performs better than any prior-dependent mechanism tailored exactly to the distribution at hand (without the additional bidder). In this work, we establish the first {\em full Bulow-Klemperer} results in {\em multi-dimensional} environments, proving that by recruiting additional bidders, the revenue of the VCG mechanism surpasses that of the optimal (possibly randomized, Bayesian incentive compatible) mechanism. For a given environment with i.i.d. bidders, we term the number of additional bidders needed to achieve this guarantee the environment's {\em competition complexity}. Using th

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Network, Popularity and Social Cohesion: A Game-Theoretic Approach

In studies of social dynamics, cohesion refers to a group's tendency to stay in unity, which -- as argued in sociometry -- arises from the network topology of interpersonal ties between members of the group. We follow this idea and propose a game-based model of cohesion that not only relies on the social network, but also reflects individuals' social needs. In particular, our model is a type of cooperative games where players may gain popularity by strategically forming groups. A group is socially cohesive if the grand coalition is core stable. We study social cohesion in some special types of graphs and draw a link between social cohesion and the classical notion of structural cohesion. We then focus on the problem of deciding whether a given social network is socially cohesive and show that this problem is CoNP-complete. Nevertheless, we give two efficient heuristics for coalition structures where players enjoy high popularity and experimentally evaluate their performances.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the commitment value and commitment optimal strategies in bimatrix games

Given a bimatrix game, the associated leadership or commitment games are defined as the games at which one player, the leader, commits to a (possibly mixed) strategy and the other player, the follower, chooses his strategy after having observed the irrevocable commitment of the leader. Based on a result by von Stengel and Zamir [2010], the notions of commitment value and commitment optimal strategies for each player are discussed as a possible solution concept. It is shown that in non-degenerate bimatrix games (a) pure commitment optimal strategies together with the follower's best response constitute Nash equilibria, and (b) strategies that participate in a completely mixed Nash equilibrium are strictly worse than commitment optimal strategies, provided they are not matrix game optimal. For various classes of bimatrix games that generalize zero sum games, the relationship between the maximin value of the leader's payoff matrix, the Nash equilibrium payoff and the commitment optimal value is discussed. For the Traveler's Dilemma, the commitment optimal strategy and commitment value for the leader are evaluated and seem more acceptable as a solution than the unique Nash

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Nash Equilibria via Duality and Homological Selection

Given a multifunction from $X$ to the $k-$fold symmetric product $Sym_k(X)$, we use the Dold-Thom Theorem to establish a homological selection Theorem. This is used to establish existence of Nash equilibria. Cost functions in problems concerning the existence of Nash Equilibria are traditionally multilinear in the mixed strategies. The main aim of this paper is to relax the hypothesis of multilinearity. We use basic intersection theory, Poincaré Duality in addition to the Dold-Thom Theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Signal to noise in matching markets

In many matching markets, one side "applies" to the other, and these applications are often expensive and time-consuming (e.g. students applying to college). It is tempting to think that making the application process easier should benefit both sides of the market. After all, the applicants could submit more applications, and the recipients would have more applicants to choose from. In this paper, we propose and analyze a simple model to understand settings where both sides of the market suffer from increased number of applications. The main insights of the paper are derived from quantifying the signal to noise tradeoffs in random matchings, as applications provide a signal of the applicants' preferences. When applications are costly the signal is stronger, as the act of making an application itself is meaningful. Therefore more applications may yield potentially better matches, but fewer applications create stronger signals for the receiving side to learn true preferences. We derive analytic characterizations of the expected quality of stable matchings in a simple utility model where applicants have an overall quality, but also synergy with specific possible partners.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Unified Approach to Analyzing Asynchronous Coordinate Descent and Tatonnement

This paper concerns asynchrony in iterative processes, focusing on gradient descent and tatonnement, a fundamental price dynamic. Gradient descent is an important class of iterative algorithms for minimizing convex functions. Classically, gradient descent has been a sequential and synchronous process, although distributed and asynchronous variants have been studied since the 1980s. Coordinate descent is a commonly studied version of gradient descent. In this paper, we focus on asynchronous coordinate descent on convex functions $F:\mathbb{R}^n\rightarrow\mathbb{R}$ of the form $F(x) = f(x) + \sum_{k=1}^n Ψ_k(x_k)$, where $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is a smooth convex function, and each $Ψ_k:\mathbb{R}\rightarrow\mathbb{R}$ is a univariate and possibly non-smooth convex function. Such functions occur in many data analysis and machine learning problems. We give new analyses of cyclic coordinate descent, a parallel asynchronous stochastic coordinate descent, and a rather general worst-case parallel asynchronous coordinate descent. For all of these, we either obtain sharply improved bounds, or provide the first analyses. Our analyses all use a common amortized framework. The

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Congestion Games with Mixed Objectives

We study a new class of games which generalizes congestion games and its bottleneck variant. We introduce congestion games with mixed objectives to model network scenarios in which players seek to optimize for latency and bandwidths alike. We characterize the existence of pure Nash equilibria (PNE) and the convergence of improvement dynamics. For games that do not possess PNE we give bounds on the approximation ratio of approximate pure Nash equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Game-Theoretic Formation of Interconnections Between Networks

We introduce a network design game where the objective of the players is to design the interconnections between the nodes of two different networks $G_1$ and $G_2$ in order to maximize certain local utility functions. In this setting, each player is associated with a node in $G_1$ and has functional dependencies on certain nodes in $G_2$. We use a distance-based utility for the players in which the goal of each player is to purchase a set of edges (incident to its associated node) such that the sum of the distances between its associated node and the nodes it depends on in $G_2$ is minimized. We consider a heterogeneous set of players (i.e., players have their own costs and benefits for constructing edges). We show that finding a best response of a player in this game is NP-hard. Despite this, we characterize some properties of the best response actions which are helpful in determining a Nash equilibrium for certain instances of this game. In particular, we prove existence of pure Nash equilibria in this game when $G_2$ contains a star subgraph, and provide an algorithm that outputs such an equilibrium for any set of players. Finally, we show that the price of anarchy in this game

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Descending Price Optimally Coordinates Search

Investigating potential purchases is often a substantial investment under uncertainty. Standard market designs, such as simultaneous or English auctions, compound this with uncertainty about the price a bidder will have to pay in order to win. As a result they tend to confuse the process of search both by leading to wasteful information acquisition on goods that have already found a good purchaser and by discouraging needed investigations of objects, potentially eliminating all gains from trade. In contrast, we show that the Dutch auction preserves all of its properties from a standard setting without information costs because it guarantees, at the time of information acquisition, a price at which the good can be purchased. Calibrations to start-up acquisition and timber auctions suggest that in practice the social losses through poor search coordination in standard formats are an order of magnitude or two larger than the (negligible) inefficiencies arising from ex-ante bidder asymmetries.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An open reproducible framework for the study of the iterated prisoner's dilemma

The Axelrod library is an open source Python package that allows for reproducible game theoretic research into the Iterated Prisoner's Dilemma. This area of research began in the 1980s but suffers from a lack of documentation and test code. The goal of the library is to provide such a resource, with facilities for the design of new strategies and interactions between them, as well as conducting tournaments and ecological simulations for populations of strategies. With a growing collection of 139 strategies, the library is a also a platform for an original tournament that, in itself, is of interest to the game theoretic community. This paper describes the Iterated Prisoner's Dilemma, the Axelrod library and its development, and insights gained from some novel research.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Subquadratic Algorithms for Succinct Stable Matching

We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally easier and investigate other implications. We give subquadratic algorithms for finding a stable matching in special cases of natural succinct representations of the problem, the $d$-attribute, $d$-list, geometric, and single-peaked models. We also present algorithms for verifying a stable matching in the same models. We further show that for $d = ω(\log n)$ both finding and verifying a stable matching in the $d$-attribute and $d$-dimensional geometric models requires quadratic time assuming the Strong Exponential Time Hypothesis. This suggests that these succinct models are not significantly simpler computationally than the general case for sufficiently large $d$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On-demand or Spot? Selling the cloud to risk-averse customers

In Amazon EC2, cloud resources are sold through a combination of an on-demand market, in which customers buy resources at a fixed price, and a spot market, in which customers bid for an uncertain supply of excess resources. Standard market environments suggest that an optimal design uses just one type of market. We show the prevalence of a dual market system can be explained by heterogeneous risk attitudes of customers. In our stylized model, we consider unit demand risk-averse bidders. We show the model admits a unique equilibrium, with higher revenue and higher welfare than using only spot markets. Furthermore, as risk aversion increases, the usage of the on-demand market increases. We conclude that risk attitudes are an important factor in cloud resource allocation and should be incorporated into models of cloud markets.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Dynamic Spectrum Leasing with Two Sellers

This paper studies dynamic spectrum leasing in a cognitive radio network. There are two spectrum sellers, who are two primary networks, each with an amount of licensed spectrum bandwidth. When a seller has some unused spectrum, it would like to lease the unused spectrum to secondary users. A coordinator helps to perform the spectrum leasing stage-by-stage. As the two sellers may have different leasing period, there are three epochs, in which seller 1 has spectrum to lease in Epochs II and III, while seller 2 has spectrum to lease in Epochs I and II. Each seller needs to decide how much spectrum it should lease to secondary users in each stage of its leasing period, with a target at revenue maximization. It is shown that, when the two sellers both have spectrum to lease (i.e., in Epoch II), the spectrum leasing can be formulated as a non-cooperative game. Nash equilibria of the game are found in closed form. Solutions of the two users in the three epochs are derived.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Formation of coalition structures as a non-cooperative game 2: applications

The paper uses a non-cooperative simultaneous game for coalition structure formation (Levando, 2016) to demonstrate some applications of the introduced game: a cooperation, a Bayesian game within a coalition with intra-coalition externalities, a stochastic game, where states are coalition structures; self-enforcement properties of a non-cooperative equilibrium and a construction of a non-cooperative stability criterion.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Strategyproof Quota Mechanisms for Multiple Assignment Problems

We study the problem of allocating multiple objects to agents without transferable utilities, where each agent may receive more than one object according to a quota. Under lexicographic preferences, we characterize the set of strategyproof, non-bossy, and neutral quota mechanisms and show that under a mild Pareto efficiency condition, serial dictatorship quota mechanisms are the only mechanisms satisfying these properties. Dropping the neutrality requirement, this class of quota mechanisms further expands to sequential dictatorship quota mechanisms. We then extend quota mechanisms to randomized settings, and show that the random serial dictatorship quota mechanisms (RSDQ) are envyfree, strategyproof, and ex post efficient for any number of agents and objects and any quota system, proving that the well-studied Random Serial Dictatorship (RSD) satisfies envyfreeness when preferences are lexicographic.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Mode-Target Games: Reactive Synthesis for Control Applications

In this paper we introduce a class of Linear Temporal Logic (LTL) specifications for which the problem of synthesizing controllers can be solved in polynomial time. The new class of specifications is an LTL fragment that we term Mode-Target (MT) and is inspired by numerous control applications where there are modes and corresponding (possibly multiple) targets for each mode. We formulate the problem of synthesizing a controller enforcing an MT specification as a game and provide an algorithm that requires $O(\sum_i t_i n^2)$ symbolic steps, where $n$ is the number of states in the game graph, and $t_i$ is the number of targets corresponding to mode $i$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Re-incentivizing Discovery: Mechanisms for Partial-Progress Sharing in Research

An essential primitive for an efficient research ecosystem is \emph{partial-progress sharing} (PPS) -- whereby a researcher shares information immediately upon making a breakthrough. This helps prevent duplication of work; however there is evidence that existing reward structures in research discourage partial-progress sharing. Ensuring PPS is especially important for new online collaborative-research platforms, which involve many researchers working on large, multi-stage problems. We study the problem of incentivizing information-sharing in research, under a stylized model: non-identical agents work independently on subtasks of a large project, with dependencies between subtasks captured via an acyclic subtask-network. Each subtask carries a reward, given to the first agent who publicly shares its solution. Agents can choose which subtasks to work on, and more importantly, when to reveal solutions to completed subtasks. Under this model, we uncover the strategic rationale behind certain anecdotal phenomena. Moreover, for any acyclic subtask-network, and under a general model of agent-subtask completion times, we give sufficient conditions that ensure PPS is incentive-compatible fo

0 citations0 reviewsNo code linkedOpen access

People in this topic

12 visible researcher(s)

Ranked from 3913 researcher records connected to this topic.