Computer Science and Game Theory
New submissions
[ showing up to 2000 entries per page: fewer  more ]
New submissions for Tue, 25 Aug 20
 [1] arXiv:2008.10187 [pdf, ps, other]

Title: LP Formulations of TwoPlayer ZeroSum Stochastic Bayesian gamesSubjects: Computer Science and Game Theory (cs.GT)
This paper studies twoplayer zerosum stochastic Bayesian games where each player has its own dynamic state that is unknown to the other player. Using typical techniques, we provide the recursive formulas and the sufficient statistics in both the primal game and its dual games. It's also shown that with a specific initial parameter, the optimal strategy of one player in a dual game is also the optimal strategy of the player in the primal game. We, then, construct linear programs to compute the optimal strategies in both the primal game and the dual games and the special initial parameters in the dual games. The main results are demonstrated in a security problem of underwater sensor networks.
 [2] arXiv:2008.10326 [pdf, ps, other]

Title: An IncentiveCompatible Smart Contract for Decentralized CommerceAuthors: Nikolaj Ignatieff Schwartzbach (Department of Computer Science, Aarhus University)Comments: 14 pages, 3 figuresSubjects: Computer Science and Game Theory (cs.GT)
We propose a smart contract that allows two mutually distrusting parties to transact any nondigital good or service by deploying a smart contract on a blockchain to act as escrow. The contract settles disputes by letting parties wager that they can convince an arbiter that they were the honest party. We analyse the contract as an extensiveform game and prove that the honest strategy is secure in a strong gametheoretic sense if and only if the arbiter is biased in favor of honest parties. By relaxing the security notion, we can replace the arbiter by a random coin toss. Finally, we show how to generalize the contract to multiparty transactions in a way that amortizes the transaction fees.
 [3] arXiv:2008.10591 [pdf, ps, other]

Title: Qualitative MultiObjective Reachability for Ordered Branching MDPsComments: 47 pagesSubjects: Computer Science and Game Theory (cs.GT); Logic in Computer Science (cs.LO)
We study qualitative multiobjective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently contextfree MDPs, building on prior results for singletarget reachability on Branching Markov Decision Processes (BMDPs).
We provide two separate algorithms for "almostsure" and "limitsure" multitarget reachability for OBMDPs. Specifically, given an OBMDP, $\mathcal{A}$, given a starting nonterminal, and given a set of target nonterminals $K$ of size $k = K$, our first algorithm decides whether the supremum probability, of generating a tree that contains every target nonterminal in set $K$, is $1$. Our second algorithm decides whether there is a strategy for the player to almostsurely (with probability $1$) generate a tree that contains every target nonterminal in set $K$.
The two separate algorithms are needed: we show that indeed, in this context, "almostsure" $\not=$ "limitsure" for multitarget reachability, meaning that there are OBMDPs for which the player may not have any strategy to achieve probability exactly $1$ of reaching all targets in set $K$ in the same generated tree, but may have a sequence of strategies that achieve probability arbitrarily close to $1$. Both algorithms run in time $2^{O(k)} \cdot \mathcal{A}^{O(1)}$, where $\mathcal{A}$ is the total bit encoding length of the given OBMDP, $\mathcal{A}$. Hence they run in polynomial time when $k$ is fixed, and are fixedparameter tractable with respect to $k$. Moreover, we show that even the qualitative almostsure (and limitsure) multitarget reachability decision problem is in general NPhard, when the size $k$ of the set $K$ of target nonterminals is not fixed.
Crosslists for Tue, 25 Aug 20
 [4] arXiv:2008.09653 (crosslist from math.OC) [pdf, ps, other]

Title: Search for a moving target in a competitive environmentComments: 13 pages, 0 figuresSubjects: Optimization and Control (math.OC); Computer Science and Game Theory (cs.GT); Theoretical Economics (econ.TH); Probability (math.PR)
We consider a discretetime dynamic search game in which a number of players compete to find an invisible object that is moving according to a timevarying Markov chain. We examine the subgame perfect equilibria of these games. The main result of the paper is that the set of subgame perfect equilibria is exactly the set of greedy strategy profiles, i.e. those strategy profiles in which the players always choose an action that maximizes their probability of immediately finding the object. We discuss various variations and extensions of the model.
 [5] arXiv:2008.09724 (crosslist from cs.CR) [pdf, other]

Title: Pricing and Budget Allocation for IoT Blockchain with Edge ComputingComments: 11 pages, 6 figuresSubjects: Cryptography and Security (cs.CR); Computer Science and Game Theory (cs.GT)
Attracted by the inherent security and privacy protection of the blockchain, incorporating blockchain into Internet of Things (IoT) has been widely studied in these years. However, the mining process requires high computational power, which prevents IoT devices from directly participating in blockchain construction. For this reason, edge computing service is introduced to help build the IoT blockchain, where IoT devices could purchase computational resources from the edge servers. In this paper, we consider the case that IoT devices also have other tasks that need the help of edge servers, such as data analysis and data storage. The profits they can get from these tasks is closely related to the amounts of resources they purchased from the edge servers. In this scenario, IoT devices will allocate their limited budgets to purchase different resources from different edge servers, such that their profits can be maximized. Moreover, edge servers will set "best" prices such that they can get the biggest benefits. Accordingly, there raise a pricing and budget allocation problem between edge servers and IoT devices. We model the interaction between edge servers and IoT devices as a multileader multifollower Stackelberg game, whose objective is to reach the Stackelberg Equilibrium (SE). We prove the existence and uniqueness of the SE point, and design efficient algorithms to reach the SE point. In the end, we verify our model and algorithms by performing extensive simulations, and the results show the correctness and effectiveness of our designs.
 [6] arXiv:2008.09757 (crosslist from econ.TH) [pdf]

Title: Constrained Trading NetworksSubjects: Theoretical Economics (econ.TH); Computer Science and Game Theory (cs.GT)
Trades based on bilateral (indivisible) contracts can be represented by a network. Vertices correspond to agents while arcs represent the nonprice elements of a bilateral contract. Given prices for each arc, agents choose the incident arcs that maximize their utility. We enlarge the model to allow for polymatroidal constraints on the set of contracts that may be traded which can be interpreted as modeling limited one forone substitution. We show that for twosided markets there exists a competitive equilibrium however for multisided markets this may not be possible.
 [7] arXiv:2008.09796 (crosslist from math.PR) [pdf, ps, other]

Title: Solving the ThreePlayerGameAuthors: Fangqi LiComments: 5 pagesSubjects: Probability (math.PR); Computer Science and Game Theory (cs.GT)
In this paper we solve the threeplayergame question. A threeplayergame consists of a series of rounds. There are altogether three players. Two players participate in each round, at the end of the round the loser quits and the third player enters the ring and another round starts. The game terminates if all six winlose relationships appear. During each round, two players win with equal probability. One is asked to calculate the expectation of the number of rounds. It turns out to be an exemplary question that involves probabiltiy theory and dynamic programming. It can serve as an instance or exercise in the chapter of conditional expectation of any elementary or advanced textbook on probability.
 [8] arXiv:2008.09815 (crosslist from econ.GN) [pdf]

Title: Competitive ridesourcing market with a thirdparty integratorSubjects: General Economics (econ.GN); Computer Science and Game Theory (cs.GT)
Recently, some transportation service providers attempt to integrate the ride services offered by multiple independent ridesourcing platforms, and passengers are able to request ride through such thirdparty integrators or connectors and receive service from any one of the platforms. This novel business model, termed as thirdparty platformintegration in this paper, has potentials to alleviate the cost of market fragmentation due to the demand splitting among multiple platforms. While most existing studies focus on the operation strategies for one single monopolist platform, much less is known about the competition and platformintegration as well as the implications on operation strategy and system efficiency. In this paper, we propose mathematical models to describe the ridesourcing market with multiple competing platforms and compare system performance metrics between two market scenarios, i.e., with and without platformintegration, at Nash equilibrium as well as social optimum. We find that platformintegration can increase total realized demand and social welfare at both Nash equilibrium and social optimum, but may not necessarily generate a greater profit when vehicle supply is sufficiently large or/and market is too fragmented. We show that the market with platformintegration generally achieves greater social welfare. On one hand, the integrator in platformintegration is able to generate a thicker market and reduce matching frictions; on the other hand, multiple platforms are still competing by independently setting their prices, which help to mitigate monopoly markup as in the monopoly market.
 [9] arXiv:2008.10384 (crosslist from eess.SY) [pdf, other]

Title: An Incentivecompatible Energy Trading Framework for Neighborhood Area Networks with Shared Energy StorageComments: Accepted in IEEE Transactions on Sustainable EnergySubjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT)
Here, a novel energy trading system is proposed for demandside management of a neighborhood area network (NAN) consisting of a shared energy storage (SES) provider, users with nondispatchable energy generation, and an electricity retailer. In a leaderfollower Stackelberg game, the SES provider first maximizes their revenue by setting a price signal and trading energy with the grid. Then, by following the SES provider's actions, the retailer minimizes social cost for the users, i.e., the sum of the total users' cost when they interact with the SES and the total cost for supplying grid energy to the users. A pricing strategy, which incorporates mechanism design, is proposed to make the system incentivecompatible by rewarding users who disclose true energy usage information. A unique Stackelberg equilibrium is achieved where the SES provider's revenue is maximized and the userlevel social cost is minimized, which also rewards the retailer. A case study with realistic energy demand and generation data demonstrates 28\%~~45\% peak demand reduction of the NAN, depending on the number of participating users, compared to a system without SES. Simulation results confirm that the retailer can also benefit financially, in addition to the SES provider and the users.
 [10] arXiv:2008.10385 (crosslist from eess.SY) [pdf, other]

Title: NetworkAware Demandside Management Framework with A Community Energy Storage System Considering Voltage ConstraintsComments: IEEE Transactions on Power SystemsSubjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC)
This paper studies the feasibility of integrating a community energy storage (CES) system with rooftop photovoltaic (PV) power generation for demandside management of a neighbourhood while maintaining the distribution network voltages within allowed limits. To this end, we develop a decentralized energy trading system between a CES provider and users with rooftop PV systems. By leveraging a linearized branch flow model for radial distribution networks, a voltageconstrained leaderfollower Stackelberg game is developed wherein the CES provider maximizes revenue and the users minimize their personal energy costs by trading energy with the CES system and the grid. The Stackelberg game has a unique equilibrium at which the CES provider maximizes revenue and the users minimize energy costs at a unique Nash equilibrium. A case study, with realistic PV power generation and demand data, confirms that the energy trading system can reduce peak energy demand and prevent network voltage excursions, while delivering financial benefits to the users and the CES provider. Further, simulations highlight that, in comparison with a centralized system, the decentralized energy trading system provides greater economic benefits to the users with less energy storage capacity.
Replacements for Tue, 25 Aug 20
 [11] arXiv:2008.09465 (replaced) [pdf, ps, other]

Title: Comparison of Algorithms for Simple Stochastic Games (Full version)Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)
 [12] arXiv:1906.02644 (replaced) [pdf, other]

Title: An Optimal Control Framework for Online Job Scheduling with General Cost FunctionsAuthors: S. Rasoul EtesamiSubjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT)
 [13] arXiv:2008.06495 (replaced) [pdf, other]

Title: Joint Policy Search for Multiagent Collaboration with Imperfect InformationSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Multiagent Systems (cs.MA); Machine Learning (stat.ML)
[ showing up to 2000 entries per page: fewer  more ]