Aarhus Universitets segl

English

Du er her: AU » Om AU » Organisation » On Covering Codes and Upper Bounds for the Dimension of S...

Om AU

On Covering Codes and Upper Bounds for the Dimension of Simple Games

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

Dokumenter

Links

Consider a situation with n agents or players, where some of the players form a coalition with a certain collective objective. Simple games are used to model systems that can decide whether coalitions are successful (winning) or not (losing). A simple game can be viewed as a monotone boolean function. The dimension of a simple game is the smallest positive integer d such that the simple game can be expressed as the intersection of d threshold functions, where each threshold function uses a threshold and n weights. Taylor and Zwicker have shown that d is bounded from above by the number of maximal losing coalitions. We present two new upper bounds both containing the Taylor-Zwicker bound as a special case. The Taylor-Zwicker bound implies an upper bound of ( nn/2). We improve this upper bound significantly by showing constructively that d is bounded from above by the cardinality of any binary covering code with length n and covering radius 1. This result supplements a recent result where Olsen et al. showed how to construct simple games with dimension \C\ for any binary constant weight SECDED code C with length n. Our result represents a major step in the attempt to close the dimensionality gap for simple games.

OriginalsprogEngelsk
TitelProcedings of the Thirty-First AAAI Conference on Artiificial Intelligence
Antal sider6
Vol/bind1
Udgivelsesår2017
Sider629-634
ISBN (trykt)978-1-57735-780-3
StatusUdgivet - 2017
BegivenhedAAAI Conference on Articificial Intelligense - California, San Francisco, USA
Varighed: 4 feb. 2017 → 9 feb. 2017
Konferencens nummer: 17
http://www.aaai.org/Conferences/AAAI/aaai17.php

Konference

KonferenceAAAI Conference on Articificial Intelligense
Nummer17
LokationCalifornia
LandUSA
BySan Francisco
Periode04/02/2017 → 09/02/2017
Internetadresse

Se relationer på Aarhus Universitet Citationsformater

Download-statistik

Ingen data tilgængelig

ID: 110697760