<progress id="hpfzt"><pre id="hpfzt"></pre></progress>
<ruby id="hpfzt"></ruby>
<big id="hpfzt"><p id="hpfzt"></p></big>

<progress id="hpfzt"></progress>

<big id="hpfzt"><pre id="hpfzt"></pre></big>

<i id="hpfzt"></i>

<strike id="hpfzt"><video id="hpfzt"><ins id="hpfzt"></ins></video></strike>
<dl id="hpfzt"></dl>
Mirror operated in collaboration with local support

# Computer Science and Game Theory

## New submissions

[ total of 13 entries: 1-13 ]
[ showing up to 2000 entries per page: fewer | more ]

### New submissions for Tue, 25 Aug 20

[1]
Title: LP Formulations of Two-Player Zero-Sum Stochastic Bayesian games
Subjects: Computer Science and Game Theory (cs.GT)

This paper studies two-player zero-sum 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]
Title: An Incentive-Compatible Smart Contract for Decentralized Commerce
Authors: Nikolaj Ignatieff Schwartzbach (Department of Computer Science, Aarhus University)
Subjects: Computer Science and Game Theory (cs.GT)

We propose a smart contract that allows two mutually distrusting parties to transact any non-digital 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 extensive-form game and prove that the honest strategy is secure in a strong game-theoretic 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]
Title: Qualitative Multi-Objective Reachability for Ordered Branching MDPs
Subjects: Computer Science and Game Theory (cs.GT); Logic in Computer Science (cs.LO)

We study qualitative multi-objective reachability problems for Ordered Branching Markov Decision Processes (OBMDPs), or equivalently context-free MDPs, building on prior results for single-target reachability on Branching Markov Decision Processes (BMDPs).
We provide two separate algorithms for "almost-sure" and "limit-sure" multi-target reachability for OBMDPs. Specifically, given an OBMDP, $\mathcal{A}$, given a starting non-terminal, and given a set of target non-terminals $K$ of size $k = |K|$, our first algorithm decides whether the supremum probability, of generating a tree that contains every target non-terminal in set $K$, is $1$. Our second algorithm decides whether there is a strategy for the player to almost-surely (with probability $1$) generate a tree that contains every target non-terminal in set $K$.
The two separate algorithms are needed: we show that indeed, in this context, "almost-sure" $\not=$ "limit-sure" for multi-target 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 fixed-parameter tractable with respect to $k$. Moreover, we show that even the qualitative almost-sure (and limit-sure) multi-target reachability decision problem is in general NP-hard, when the size $k$ of the set $K$ of target non-terminals is not fixed.

### Cross-lists for Tue, 25 Aug 20

[4]  arXiv:2008.09653 (cross-list from math.OC) [pdf, ps, other]
Title: Search for a moving target in a competitive environment
Subjects: Optimization and Control (math.OC); Computer Science and Game Theory (cs.GT); Theoretical Economics (econ.TH); Probability (math.PR)

We consider a discrete-time dynamic search game in which a number of players compete to find an invisible object that is moving according to a time-varying 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 (cross-list from cs.CR) [pdf, other]
Title: Pricing and Budget Allocation for IoT Blockchain with Edge Computing
Subjects: 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 multi-leader multi-follower 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 (cross-list from econ.TH) [pdf]
Subjects: 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 non-price 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 for-one substitution. We show that for two-sided markets there exists a competitive equilibrium however for multi-sided markets this may not be possible.

[7]  arXiv:2008.09796 (cross-list from math.PR) [pdf, ps, other]
Title: Solving the Three-Player-Game
Authors: Fangqi Li
Subjects: Probability (math.PR); Computer Science and Game Theory (cs.GT)

In this paper we solve the three-player-game question. A three-player-game 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 win-lose 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 (cross-list from econ.GN) [pdf]
Title: Competitive ride-sourcing market with a third-party integrator
Subjects: 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 ride-sourcing platforms, and passengers are able to request ride through such third-party integrators or connectors and receive service from any one of the platforms. This novel business model, termed as third-party platform-integration 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 platform-integration as well as the implications on operation strategy and system efficiency. In this paper, we propose mathematical models to describe the ride-sourcing market with multiple competing platforms and compare system performance metrics between two market scenarios, i.e., with and without platform-integration, at Nash equilibrium as well as social optimum. We find that platform-integration 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 platform-integration generally achieves greater social welfare. On one hand, the integrator in platform-integration 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 mark-up as in the monopoly market.

[9]  arXiv:2008.10384 (cross-list from eess.SY) [pdf, other]
Title: An Incentive-compatible Energy Trading Framework for Neighborhood Area Networks with Shared Energy Storage
Comments: Accepted in IEEE Transactions on Sustainable Energy
Subjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT)

Here, a novel energy trading system is proposed for demand-side management of a neighborhood area network (NAN) consisting of a shared energy storage (SES) provider, users with non-dispatchable energy generation, and an electricity retailer. In a leader-follower 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 incentive-compatible 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 user-level 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 (cross-list from eess.SY) [pdf, other]
Title: Network-Aware Demand-side Management Framework with A Community Energy Storage System Considering Voltage Constraints
Comments: IEEE Transactions on Power Systems
Subjects: 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 demand-side 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 voltage-constrained leader-follower 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 Functions
Subjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT)
[13]  arXiv:2008.06495 (replaced) [pdf, other]
Title: Joint Policy Search for Multi-agent Collaboration with Imperfect Information
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Science and Game Theory (cs.GT); Multiagent Systems (cs.MA); Machine Learning (stat.ML)
[ total of 13 entries: 1-13 ]
[ showing up to 2000 entries per page: fewer | more ]
Æ´ÈýÕÅÓÎÏ·ÏÂÔØ