Computer Science and Game Theory

Authors and titles for November 2013

[1] arXiv:1311.0198 [pdf, other]

Title: Decomposing Truthful and Competitive Online Double Auctions

Dengji Zhao, Dongmo Zhang, Laurent Perrussel

Comments: 19 pages, 5 figures, unpublished

Subjects: Computer Science and Game Theory (cs.GT)

[2] arXiv:1311.0803 [pdf, other]

Title: When "I cut, you choose" method implies intransitivity

Marcin Makowski, Edward W. Piotrowski

Journal-ref: Physica A: Statistical Mechanics and its Applications (2014) 415C pp. 189-193

Subjects: Computer Science and Game Theory (cs.GT)

[3] arXiv:1311.0913 [pdf, other]

Title: Bidding Games and Efficient Allocations

Gil Kalai, Reshef Meir, Moshe Tennenholtz

Comments: A preliminary version of this paper appeared in the 16th ACM Conference on Economics and Computation (EC-2015). Paper accepted to Games and Economic Behavior

Subjects: Computer Science and Game Theory (cs.GT)

[4] arXiv:1311.0924 [pdf, other]

Title: On the Efficiency of the Walrasian Mechanism

Moshe Babaioff, Brendan Lucier, Noam Nisan, Renato Paes Leme

Subjects: Computer Science and Game Theory (cs.GT)

[5] arXiv:1311.1018 [pdf, other]

Title: Resource Management for Device-to-Device Underlay Communication

Chen Xu, Lingyang Song, Zhu Han

Comments: arXiv admin note: substantial text overlap with arXiv:1211.2065

Subjects: Computer Science and Game Theory (cs.GT); Networking and Internet Architecture (cs.NI)

[6] arXiv:1311.1610 [pdf, other]

Title: Decentralized Dynamics for Finite Opinion Games

Diodato Ferraioli, Paul W. Goldberg, Carmine Ventre

Subjects: Computer Science and Game Theory (cs.GT)

[7] arXiv:1311.1803 [pdf, other]

Title: Strong Stability of Nash Equilibria in Load Balancing Games

Bo Chen, Song-Song Li, Yu-Zhong Zhang

Comments: 17 pages and 4 figures

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM); Optimization and Control (math.OC)

[8] arXiv:1311.2109 [pdf, other]

Title: How to Gamble Against All Odds

Gilad Bavly, Ron Peretz

Subjects: Computer Science and Game Theory (cs.GT); Logic (math.LO)

[9] arXiv:1311.2138 [pdf, other]

Title: The Complexity of Optimal Multidimensional Pricing

Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis

Subjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC)

[10] arXiv:1311.2625 [pdf, other]

Title: Asymptotically Truthful Equilibrium Selection in Large Congestion Games

Ryan Rogers, Aaron Roth

Comments: The conference version of this paper appeared in EC 2014. This manuscript has been merged and subsumed by the preprint "Robust Mediators in Large Games": http://arxiv.org/abs/1512.02698

Subjects: Computer Science and Game Theory (cs.GT); Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS)

[11] arXiv:1311.2655 [pdf, other]

Title: On the Existence of Low-Rank Explanations for Mixed Strategy Behavior

Siddharth Barman, Umang Bhaskar, Federico Echenique, Adam Wierman

Comments: Updated writeup. 19 pages

Subjects: Computer Science and Game Theory (cs.GT)

[12] arXiv:1311.2820 [pdf, other]

Title: Draft Auctions

Nikhil R. Devanur, Jamie Morgenstern, Vasilis Syrgkanis

Subjects: Computer Science and Game Theory (cs.GT)

[13] arXiv:1311.2828 [pdf, other]

Title: Private Matchings and Allocations

Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, Zhiwei Steven Wu

Comments: Journal version published in SIAM Journal on Computation; an extended abstract appeared in STOC 2014

Journal-ref: SIAM Journal on Computing 45(6) 1953--1984 (2016)

Subjects: Computer Science and Game Theory (cs.GT); Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS)

[14] arXiv:1311.3088 [pdf, other]

Title: Endogenous games with goals: side-payments among goal-directed artificial agents

Paolo Turrini

Comments: (under submission)

Subjects: Computer Science and Game Theory (cs.GT)

[15] arXiv:1311.3238 [pdf, other]

Title: Doomsday Equilibria for Omega-Regular Games

Krishnendu Chatterjee, Laurent Doyen, Emmanuel Filiot, Jean-François Raskin

Subjects: Computer Science and Game Theory (cs.GT)

[16] arXiv:1311.3939 [pdf, other]

Title: Local computation mechanism design

Avinatan Hassidim, Yishay Mansour, Shai Vardi

Subjects: Computer Science and Game Theory (cs.GT)

[17] arXiv:1311.4721 [pdf, other]

Title: Economic Efficiency Requires Interaction

Shahar Dobzinski, Noam Nisan, Sigal Oren

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)

[18] arXiv:1311.5417 [pdf, other]

Title: General Privacy-Preserving Verifiable Incentive Mechanism for Crowdsourcing Markets

Jiajun Sun

Comments: This paper has been withdrawn by the author due to a crucial sign error in equation 1 and Figure 1

Subjects: Computer Science and Game Theory (cs.GT); Cryptography and Security (cs.CR)

[19] arXiv:1311.5603 [pdf, other]

Title: Submodular Welfare Maximization

Samira Samadi

Subjects: Computer Science and Game Theory (cs.GT)

[20] arXiv:1311.5728 [pdf, other]

Title: The Prediction value

Maurice Koster, Sascha Kurz, Ines Lindner, Stefan Napel

Comments: 26 pages, 2 tables

Subjects: Computer Science and Game Theory (cs.GT)

[21] arXiv:1311.5925 [pdf, other]

Title: Scheduling a Cascade with Opposing Influences

MohammadTaghi Hajiaghayi, Hamid Mahini, Anshul Sawant

Journal-ref: In proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT), Aachen, Germany, pages 195-206, 2013

Subjects: Computer Science and Game Theory (cs.GT); Social and Information Networks (cs.SI)

[22] arXiv:1311.5934 [pdf, other]

Title: Tipping Points in Schelling Segregation

George Barmpalias, Richard Elwes, Andy Lewis-Pye

Subjects: Computer Science and Game Theory (cs.GT)

[23] arXiv:1311.5966 [pdf, other]

Title: Optimal mechanisms with simple menus

Zihe Wang, Pingzhong Tang

Comments: 25 pages, 11 figures

Subjects: Computer Science and Game Theory (cs.GT)

[24] arXiv:1311.6230 [pdf, other]

Title: Privacy-Preserving Verifiable Incentive Mechanism for Crowdsourcing Market Applications

Jiajun Sun

Subjects: Computer Science and Game Theory (cs.GT)

[25] arXiv:1311.6638 [pdf, other]

Title: $K$-anonymous Signaling Scheme

Binyi Chen, Tao Qin, Tie-Yan Liu

Subjects: Computer Science and Game Theory (cs.GT)

[26] arXiv:1311.6883 [pdf, other]

Title: Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players

Hadi Minooei, Chaitanya Swamy

Comments: Major changes compared to the previous version. Please consult this version

Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)

[27] arXiv:1311.7683 [pdf, other]

Title: Robust Equilibria in Concurrent Games

Romain Brenguier

Comments: 32 pages To appear in FoSSaCS 2016

Subjects: Computer Science and Game Theory (cs.GT)

[28] arXiv:1311.1264 (cross-list from cs.SI) [pdf, other]

Title: Dynamic Network Formation with Incomplete Information

Yangbo Song, Mihaela van der Schaar

Subjects: Social and Information Networks (cs.SI); Computer Science and Game Theory (cs.GT); Physics and Society (physics.soc-ph)

[29] arXiv:1311.1490 (cross-list from cs.CR) [pdf, other]

Title: On Unconditionally Secure Multiparty Computation for Realizing Correlated Equilibria in Games

Ye Wang, Shantanu Rane, Prakash Ishwar

Comments: 4 pages, to appear at GlobalSIP 2013

Subjects: Cryptography and Security (cs.CR); Computer Science and Game Theory (cs.GT); Information Theory (cs.IT)

[30] arXiv:1311.1869 (cross-list from cs.LG) [pdf, other]

Title: Optimization, Learning, and Games with Predictable Sequences

Alexander Rakhlin, Karthik Sridharan

Subjects: Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT)

[31] arXiv:1311.1887 (cross-list from cs.SY) [pdf, other]

Title: Demand Side Management in Smart Grids using a Repeated Game Framework

Linqi Song, Yuanzhang Xiao, Mihaela van der Schaar

Subjects: Systems and Control (eess.SY); Computer Science and Game Theory (cs.GT)

[32] arXiv:1311.2444 (cross-list from cs.DC) [pdf, other]

Title: Flexible Parallel Algorithms for Big Data Optimization

Francisco Facchinei, Simone Sagratella, Gesualdo Scutari

Comments: submitted to IEEE ICASSP 2014

Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Computer Science and Game Theory (cs.GT); Optimization and Control (math.OC)

[33] arXiv:1311.2578 (cross-list from cs.DS) [pdf, other]

Title: Primal Beats Dual on Online Packing LPs in the Random-Order Model

Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking

Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)

[34] arXiv:1311.3141 (cross-list from cs.IT) [pdf, other]

Title: Cloud Compute-and-Forward with Relay Cooperation

Koralia N. Pappi, Panagiotis D. Diamantoulakis, Hadi Otrok, George K. Karagiannidis

Comments: Submitted to IEEE Transactions on Wireless Communications

Subjects: Information Theory (cs.IT); Computer Science and Game Theory (cs.GT); Networking and Internet Architecture (cs.NI)

[35] arXiv:1311.4766 (cross-list from math.CO) [pdf, other]

Title: Notions of Anonymity, Fairness and Symmetry for Finite Strategic-Form Games

Nicholas Ham

Comments: 32 pages

Subjects: Combinatorics (math.CO); Computer Science and Game Theory (cs.GT)

[36] arXiv:1311.6838 (cross-list from cs.LG) [pdf, other]

Title: Learning Prices for Repeated Auctions with Strategic Buyers

Kareem Amin, Afshin Rostamizadeh, Umar Syed

Comments: Neural Information Processing Systems (NIPS 2013)

Subjects: Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT)

[37] arXiv:1311.6863 (cross-list from cs.DM) [pdf, other]

Title: Pairwise Comparisons Simplified

W.W. Koczkodaj, J. Szybowski

Comments: 15 pages, two figures

Subjects: Discrete Mathematics (cs.DM); Computer Science and Game Theory (cs.GT)