1,721,305 research outputs found
Extending the alternating-offers protocol in the presence of competition: models and theoretical analysis
Full text linkA Connective Stability Analysis of Complex System Simulation and Control via Multiagent Systems
No full text
Extensive-form perfect equilibrium computation in two-player games
No full textWe study the problem of computing an Extensive-Form Perfect Equilibrium (EFPE) in 2-player games. This equilibrium concept refines the Nash equilibrium requiring resilience with respect to a specific vanishing perturbation, representing mistakes of the players at each decision node. The scientific challenge is intrinsic to the EFPE definition: it requires a perturbation over the agent form, but the agent form is computationally inefficient due to the presence of highly nonlinear constraints. We show that the sequence form can be exploited in a non-trivial way and that, for general-sum games, finding an EFPE is equivalent to solving a suitably perturbed linear complementarity problem. We prove that Lemke's algorithm can be applied, showing that computing an EFPE is PPAD-complete. In the notable case of zero-sum games, the problem is in FP and can be solved by linear programming. Our algorithms also allow one to find a Nash equilibrium when players cannot perfectly control their moves, being subject to a given execution uncertainty, as is the case in most realistic physical settings
An algorithmic game theory study of wholesale electricity markets based on central auction
No full textAd Auctions and Cascade Model: GSP Inefficiency and Algorithms
Full text linkThe design of the best economic mechanism for Sponsored Search Auctions (SSAs) is a central task in computational mechanism design/game theory. Two open questions concern (i) the adoption of user models more accurate than the currently used one and (ii) the choice between Generalized Second Price auction (GSP) and Vickrey–Clark–Groves mechanism (VCG). In this paper, we provide some contributions to answer these questions. We study Price of Anarchy (PoA) and Price of Stability (PoS) over social welfare and auctioneer’s revenue of GSP w.r.t. the VCG when the users follow the famous cascade model. Furthermore, we provide exact, randomized, and approximate algorithms, showing that in real–world settings (Yahoo! Webscope A3 dataset, 10 available slots) optimal allocations can be found in less than 1s with up to 1,000 ads, and can be approximated in less than 20ms even with more than 1,000 ads with an average accuracy greater than 99%
- …
