More Like this

1. Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable

   https://doi.org/10.1609/aaai.v35i6.16668  

   Dehghani, Sina; Saleh, Hamed; Seddighin, Saeed; Teng, Shang-Hua (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   In the classical discrete Colonel Blotto game—introducedby Borel in 1921—two colonels simultaneously distributetheir troops across multiple battlefields. The winner of eachbattlefield is determined by a winner-take-all rule, independentlyof other battlefields. In the original formulation, eachcolonel’s goal is to win as many battlefields as possible. TheBlotto game and its extensions have been used in a widerange of applications from political campaign—exemplifiedby the U.S presidential election—to marketing campaign,from (innovative) technology competition to sports competition.Despite persistent efforts, efficient methods for findingthe optimal strategies in Blotto games have been elusivefor almost a century—due to exponential explosion inthe organic solution space—until Ahmadinejad, Dehghani,Hajiaghayi, Lucier, Mahini, and Seddighin developed thefirst polynomial-time algorithm for this fundamental gametheoreticalproblem in 2016. However, that breakthroughpolynomial-time solution has some structural limitation. Itapplies only to the case where troops are homogeneous withrespect to battlegruounds, as in Borel’s original formulation:For each battleground, the only factor that matters to the winner’spayoff is how many troops as opposed to which sets oftroops are opposing one another in that battleground.In this paper, we consider a more general setting of thetwo-player-multi-battleground game, in which multifacetedresources (troops) may have different contributions to differentbattlegrounds. In the case of U.S presidential campaign,for example, one may interpret this as different typesof resources—human, financial, political—that teams can investin each state. We provide a complexity-theoretical evidencethat, in contrast to Borel’s homogeneous setting, findingoptimal strategies in multifaceted Colonel Blotto gamesis intractable. We complement this complexity result witha polynomial-time algorithm that finds approximately optimalstrategies with provable guarantees. We also study a furthergeneralization when two competitors do not have zerosum/constant-sum payoffs. We show that optimal strategiesin these two-player-multi-battleground games are as hard tocompute and approximate as Nash equilibria in general noncooperative games and economic equilibria in exchange markets. 

   more » « less
2. Probability Distributions on Partially Ordered Sets and Network Interdiction Games

   https://doi.org/10.1287/moor.2021.1140  

   Dahan, Mathieu; Amin, Saurabh; Jaillet, Patrick (December 2021, Mathematics of Operations Research)

   This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset’s elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence problem is relevant for the equilibrium characterization of a generic strategic interdiction game on a capacitated flow network. The game involves a routing entity that sends its flow through the network while facing path transportation costs and an interdictor who simultaneously interdicts one or more edges while facing edge interdiction costs. Using our existence result on posets and strict complementary slackness in linear programming, we show that the Nash equilibria of this game can be fully described using primal and dual solutions of a minimum-cost circulation problem. Our analysis provides a new characterization of the critical components in the interdiction game. It also leads to a polynomial-time approach for equilibrium computation. 

   more » « less
3. Achieving Efficient Collaboration in Decentralized Heterogeneous Teams using Common-Pool Resource Games

   https://doi.org/10.1109/CDC40024.2019.9029753  

   Gupta, Piyush; Bopardikar, Shaunak D.; Srivastava, Vaibhav (December 2019, IEEE Conference on Decision and Control)

   We consider a team of heterogeneous agents that is collectively responsible for servicing and subsequently reviewing a stream of homogeneous tasks. Each agent (autonomous system or human operator) has an associated mean service time and mean review time for servicing and reviewing the tasks, respectively, which are based on their expertise and skill-sets. The team objective is to collaboratively maximize the number of "serviced and reviewed" tasks. To this end, we formulate a Common-Pool Resource (CPR) game and design utility functions to incentivize collaboration among team-members. We show the existence and uniqueness of the Pure Nash Equilibrium (PNE) for the CPR game. Additionally, we characterize the structure of the PNE and study the effect of heterogeneity among the agents at the PNE. We show that the formulated CPR game is a best response potential game for which both sequential best response dynamics and simultaneous best reply dynamics converge to the Nash equilibrium. Finally, we numerically illustrate the price of anarchy for the PNE. 

   more » « less
4. An Efficient Parallel Architecture for Resource-Shareable Reed-Solomon Encoder

   https://doi.org/10.1109/SiPS52927.2021.00035  

   Tang, Yok Jye; Zhang, Xinmiao (October 2021, IEEE Workshop on Signal Processing Systems)

   Reed-Solomon (RS) codes are adopted in many digital communication and storage systems to ensure data reliability. For many of these systems, the encoder and decoder are not active at the same time. In previous designs, RS encoders implemented as linear feedback shift registers in a concatenated structure are reused to compute the syndromes so that the decoder complexity is reduced. However, the parallel versions of such encoders have very long critical path and hence can not achieve high speed. This paper proposes a new parallel resource-shareable RS encoder architecture based on the Chinese Remainder Theorem (CRT). The generator polynomial of RS codes is decomposed into factors of degree one and state transformation is developed to enable the sharing of the hardware units for syndrome computation. As a result, the critical path is reduced to only one multiplier and one adder, regardless of the parallelism. Additionally, by utilizing the property that the degrees of the decomposed polynomial factors are one, optimizations are also developed to greatly simplify the CRT-based encoder. For example encoders of a (255, 229) RS code over GF(2^8), our proposed design can achieve at least 29% higher efficiency in terms of area-time product for moderate or higher parallelisms compared to the previous resource-shareable RS encoder and traditional parallel RS encoders combined with syndrome computation units that implement the same functionality. 

   more » « less
5. Scalable Equilibrium Computation in Multi-agent Influence Games on Networks

   Christia, Fotini; Curry, Michael; Demaine, Erik; Dickerson, John P; Hajiaghayi, MohammadTaghi; Hesterberg, Adam; Knittel, Marina; Milliff, Aidan (April 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   We provide a polynomial-time, scalable algorithm for equilibrium computation in multi-agent influence games on networks, extending work of Bindel, Kleinberg, and Oren (2015) from the single-agent to the multi-agent setting. In games of influence, agents have limited advertising budget to influence the initial predisposition of nodes in some network towards their products, but the eventual decisions of the nodes are determined by the stationary state of DeGroot opinion dynamics on the network, which takes over after the seeding (Ahmadinejad et al. 2014, 2015). In multi-agent systems, how should agents spend their budgets to seed the network to maximize their utility in anticipation of other advertising agents and the network dynamics? We show that Nash equilibria of this game are pure and (under weak assumptions) unique, and can be computed in polynomial time; we test our model by computing equilibria using mirror descent for the two-agent case on random graphs. 

   more » « less